primitives.merkle_tree#
Merkle tree commitment using Poseidon2.
Attributes#
Classes#
Query proof containing leaf values and Merkle authentication path. |
|
Variable-arity Merkle tree using Poseidon2 hashing. |
Functions#
|
Transpose data layout for Merkle tree construction. |
Module Contents#
- class primitives.merkle_tree.QueryProof[source]#
Query proof containing leaf values and Merkle authentication path.
Corresponds to C++ MerkleProof in proof_stark.hpp lines 39-69.
- Attributes:
- v: Leaf values at query index - list of columns, each column is a list of elements
For base field polynomials: [[val1], [val2], …] (one element per column) For extension field: [[v0, v1, v2], …] (FIELD_EXTENSION elements per column)
- mp: Merkle path - list of sibling hashes per level, from leaf to root
Each level has (arity - 1) * HASH_SIZE elements
- primitives.merkle_tree.transpose_for_merkle(data: list[int], height: int, width: int, elem_size: int) list[int][source]#
Transpose data layout for Merkle tree construction.
Reorders elements so that those belonging to the same Merkle leaf are contiguous. This matches the pil2-stark C++ memory layout convention.
- class primitives.merkle_tree.MerkleTree(arity: int = 4, last_level_verification: int = 0, custom: bool = False)[source]#
Variable-arity Merkle tree using Poseidon2 hashing.
- merkelize(source: LeafData, height: int, width: int, n_cols: int = 0) None[source]#
Build Merkle tree from source data.
- Args:
source: Flattened leaf data (height * width elements) height: Number of leaves (rows) width: Elements per leaf (columns * elem_size) n_cols: Number of polynomial columns (for query proof extraction)
- get_root() MerkleRoot[source]#
Return the Merkle root commitment.
- get_group_proof(idx: int) list[int][source]#
Generate Merkle proof (siblings only) for leaf at index.
- get_query_proof(idx: int, elem_size: int = 1) QueryProof[source]#
Extract complete query proof with leaf values and Merkle path.
This is the main method for generating query proofs for STARK proofs. It returns both the polynomial values at the query index and the Merkle authentication path.
- Args:
idx: Query index (leaf index in the tree) elem_size: Elements per column (1 for base field, 3 for extension)
- Returns:
QueryProof with: - v: List of column values at idx, each is [elem_size] elements - mp: List of sibling hashes per level, structured for C++ compatibility
- Raises:
ValueError: If source_data not available or idx out of range
- get_last_level_nodes() list[int][source]#
Extract last level verification nodes.
When lastLevelVerification > 0, the verifier needs access to the internal nodes at (total_levels - lastLevelVerification) from bottom. This is equivalent to lastLevelVerification levels below the root.
- Returns:
List of arity^lastLevelVerification * HASH_SIZE elements, or empty list if lastLevelVerification == 0. The actual nodes are at the beginning, followed by zero padding if the actual node count is less than arity^lastLevelVerification.
- static verify_merkle_root(root: MerkleRoot, level: list[int], height: int, last_level_verification: int, arity: int, sponge_width: int) bool[source]#
Verify Merkle root from last-level nodes.
C++ reference: merkleTreeGL.hpp lines 70-99
Computes the root by hashing up from the last level and compares against the expected root.
- Args:
root: Expected root (HASH_SIZE elements) level: Last level nodes (num_nodes * HASH_SIZE elements) height: Tree height (number of leaves) last_level_verification: Number of levels to skip from bottom arity: Tree arity (2, 3, or 4) sponge_width: Hash sponge width
- Returns:
True if computed root matches expected root
- verify_group_proof(root: MerkleRoot, proof: list[list[int]], idx: int, leaf_data: LeafData) bool[source]#
Verify Merkle proof for a leaf.