alexandria_merkle_tree

Fully qualified path: alexandria_merkle_tree

Modules

Modules

Modules

merkle_tree

MerkleTree implementation.

Examples

// This version uses the pedersen hash method because the PedersenHasherImpl is in the scope.
use alexandria_data_structures::merkle_tree::{Hasher, MerkleTree, pedersen::PedersenHasherImpl,
MerkleTreeTrait};

// Create a new merkle tree instance.
let mut merkle_tree: MerkleTree<Hasher> = MerkleTreeTrait::new();
let mut proof = array![element_1, element_2];
// Compute the merkle root.
let root = merkle_tree.compute_root(leaf, proof);

// This version uses the poseidon hash method because the PoseidonHasherImpl is in the scope.
use alexandria_data_structures::merkle_tree::{ Hasher, MerkleTree, poseidon::PoseidonHasherImpl,
MerkleTreeTrait };

// Create a new merkle tree instance.
let mut merkle_tree: MerkleTree<PoseidonHasher> = MerkleTreeTrait::new();
let mut proof = array![element_1, element_2];
// Compute the merkle root.
let root = merkle_tree.compute_root(leaf, proof);

Fully qualified path: alexandria_merkle_tree::merkle_tree

Modules

Structs

Traits

Modules

Modules

pedersen

Hasher impls.

Fully qualified path: alexandria_merkle_tree::merkle_tree::pedersen

Impls

Impls

Impls

PedersenHasherImpl

Fully qualified path: alexandria_merkle_tree::merkle_tree::pedersen::PedersenHasherImpl

pub impl PedersenHasherImpl of HasherTrait<Hasher>;

Impl functions

new

Fully qualified path: alexandria_merkle_tree::merkle_tree::pedersen::PedersenHasherImpl::new

fn new() -> Hasher

hash

Fully qualified path: alexandria_merkle_tree::merkle_tree::pedersen::PedersenHasherImpl::hash

fn hash(ref self: Hasher, data1: felt252, data2: felt252) -> felt252

poseidon

Fully qualified path: alexandria_merkle_tree::merkle_tree::poseidon

Impls

Impls

Impls

PoseidonHasherImpl

Fully qualified path: alexandria_merkle_tree::merkle_tree::poseidon::PoseidonHasherImpl

pub impl PoseidonHasherImpl of HasherTrait<Hasher>;

Impl functions

new

Fully qualified path: alexandria_merkle_tree::merkle_tree::poseidon::PoseidonHasherImpl::new

fn new() -> Hasher

hash

Fully qualified path: alexandria_merkle_tree::merkle_tree::poseidon::PoseidonHasherImpl::hash

fn hash(ref self: Hasher, data1: felt252, data2: felt252) -> felt252

Structs

Structs

Hasher

Fully qualified path: alexandria_merkle_tree::merkle_tree::Hasher

[derive(Drop, Copy)]
pub struct Hasher {}

MerkleTree

MerkleTree representation.

Fully qualified path: alexandria_merkle_tree::merkle_tree::MerkleTree

[derive(Drop)]
pub struct MerkleTree<T> { /* private fields */ }

StoredMerkleTree

Efficient MerkleTree with pre-built tree storage for O(log n) proof generation.

When to use StoredMerkleTree vs MerkleTree:

Use StoredMerkleTree when:

• Generating 2+ proofs from the same tree (35% gas savings for multiple proofs)
• Need consistent O(log n) performance for proof generation

Use regular MerkleTree when:

• Only generating 1 proof (70% less gas for single proof)
• Memory/storage is constrained
• Tree data changes frequently (StoredMerkleTree requires rebuilding)

Gas Comparison (8 leaves):

• Single proof: MerkleTree 96k gas vs StoredMerkleTree 165k gas
• Multiple proofs (4x): MerkleTree 378k gas vs StoredMerkleTree 247k gas (35% savings)

Fully qualified path: alexandria_merkle_tree::merkle_tree::StoredMerkleTree

[derive(Drop)]
pub struct StoredMerkleTree<T> { /* private fields */ }

Traits

Traits

HasherTrait

Hasher trait.

Fully qualified path: alexandria_merkle_tree::merkle_tree::HasherTrait

pub trait HasherTrait<T>

Trait functions

new

Fully qualified path: alexandria_merkle_tree::merkle_tree::HasherTrait::new

fn new() -> T

hash

Fully qualified path: alexandria_merkle_tree::merkle_tree::HasherTrait::hash

fn hash(ref self: T, data1: felt252, data2: felt252) -> felt252

MerkleTreeTrait

MerkleTree trait defining operations for Merkle tree construction and verification.

Fully qualified path: alexandria_merkle_tree::merkle_tree::MerkleTreeTrait

pub trait MerkleTreeTrait<T>

Trait functions

new

Create a new merkle tree instance.

Returns

• MerkleTree<T> - A new merkle tree with the specified hasher type

Fully qualified path: alexandria_merkle_tree::merkle_tree::MerkleTreeTrait::new

fn new() -> MerkleTree<T>

compute_root

Compute the merkle root of a given proof by iteratively hashing with proof elements.

Arguments

• self - The merkle tree instance
• current_node - The starting leaf node (felt252 hash value)
• proof - Array of sibling hashes needed to compute the root

Returns

• felt252 - The computed merkle root hash

Fully qualified path: alexandria_merkle_tree::merkle_tree::MerkleTreeTrait::compute_root

fn compute_root(ref self: MerkleTree<T>, current_node: felt252, proof: Span<felt252>) -> felt252

verify

Verify that a leaf belongs to the merkle tree with the given root.

Arguments

• self - The merkle tree instance
• root - The expected merkle root hash
• leaf - The leaf value to verify
• proof - Array of sibling hashes for verification path

Returns

• bool - True if the leaf is valid for the given root, false otherwise

Fully qualified path: alexandria_merkle_tree::merkle_tree::MerkleTreeTrait::verify

fn verify(ref self: MerkleTree<T>, root: felt252, leaf: felt252, proof: Span<felt252>) -> bool

compute_proof

Generate a merkle proof for a specific leaf at the given index. WARNING: This rebuilds the entire tree and is O(n) complexity. Use StoredMerkleTree for efficiency.

Arguments

• self - The merkle tree instance
• leaves - Array of all leaf values in the tree (will be sorted)
• index - The index of the leaf to generate proof for

Returns

• Span<felt252> - Array of sibling hashes forming the merkle proof

Fully qualified path: alexandria_merkle_tree::merkle_tree::MerkleTreeTrait::compute_proof

fn compute_proof(ref self: MerkleTree<T>, leaves: Array<felt252>, index: u32) -> Span<felt252>

StoredMerkleTreeTrait

StoredMerkleTree trait defining operations for efficient Merkle tree with pre-computed storage.

Fully qualified path: alexandria_merkle_tree::merkle_tree::StoredMerkleTreeTrait

pub trait StoredMerkleTreeTrait<T>

Trait functions

new

Create a new stored merkle tree instance from leaves. Pre-computes and stores all levels for efficient proof generation.

Arguments

• leaves - Array of leaf values to build the tree from

Returns

• StoredMerkleTree<T> - A new stored merkle tree with pre-computed levels

Fully qualified path: alexandria_merkle_tree::merkle_tree::StoredMerkleTreeTrait::new

fn new(leaves: Array<felt252>) -> StoredMerkleTree<T>

get_root

Get the merkle root of the stored tree.

Arguments

• self - The stored merkle tree instance

Returns

• felt252 - The merkle root hash

Fully qualified path: alexandria_merkle_tree::merkle_tree::StoredMerkleTreeTrait::get_root

fn get_root(ref self: StoredMerkleTree<T>) -> felt252

get_proof

Generate a merkle proof for a specific leaf at the given index. Efficient O(log n) operation using pre-stored tree levels.

Arguments

• self - The stored merkle tree instance
• index - The index of the leaf to generate proof for

Returns

• Span<felt252> - Array of sibling hashes forming the merkle proof

Fully qualified path: alexandria_merkle_tree::merkle_tree::StoredMerkleTreeTrait::get_proof

fn get_proof(ref self: StoredMerkleTree<T>, index: u32) -> Span<felt252>

verify

Verify that a leaf belongs to the merkle tree.

Arguments

• self - The stored merkle tree instance
• leaf - The leaf value to verify
• proof - Array of sibling hashes for verification path

Returns

• bool - True if the leaf is valid, false otherwise

Fully qualified path: alexandria_merkle_tree::merkle_tree::StoredMerkleTreeTrait::verify

fn verify(ref self: StoredMerkleTree<T>, leaf: felt252, proof: Span<felt252>) -> bool

get_leaf_count

Get the number of leaves in the tree.

Arguments

• self - The stored merkle tree instance

Returns

• u32 - The number of leaves in the tree

Fully qualified path: alexandria_merkle_tree::merkle_tree::StoredMerkleTreeTrait::get_leaf_count

fn get_leaf_count(ref self: StoredMerkleTree<T>) -> u32

storage_proof

Fully qualified path: alexandria_merkle_tree::storage_proof

Free functions

Structs

Enums

Traits

Impls

Free functions

Free functions

verify

Verify Starknet storage proof. For reference see:

(state)

• ( pathfinder_getproof APIendpoint)
• ( pathfinder storageimplementation)

Arguments

• expected_state_commitment - state root proof is going to be verified against
• contract_address - contract_address of the value to be verified
• storage_address - storage_address of the value to be verified
• proof - ContractStateProof representing storage proof

Returns

• felt252 - value at storage_address if verified, panic otherwise.

Fully qualified path: alexandria_merkle_tree::storage_proof::verify

pub fn verify(
    expected_state_commitment: felt252,
    contract_address: felt252,
    storage_address: felt252,
    proof: ContractStateProof,
) -> felt252

Structs

Structs

BinaryNode

Represents a binary node in a Merkle Patricia Trie

A binary node contains exactly two children, commonly used in Merkle trees to represent internal nodes that split paths into left and right branches. This structure is fundamental for Starknet’s storage proof verification.

Fields

• left - Hash of the left child node
• right - Hash of the right child node

Fully qualified path: alexandria_merkle_tree::storage_proof::BinaryNode

[derive(Drop, Serde)]
pub struct BinaryNode { /* private fields */ }

EdgeNode

Represents an edge node in a Merkle Patricia Trie

An edge node compresses a path of nodes in the trie, storing both the compressed path and the hash of the child node. This optimization reduces the depth of the trie when consecutive nodes have only one child, improving efficiency in Starknet storage proofs.

Fields

• path - The compressed path as a felt252 value
• child - Hash of the child node at the end of this path
• length - Length of the compressed path in bits

Fully qualified path: alexandria_merkle_tree::storage_proof::EdgeNode

[derive(Drop, Copy, Serde)]
pub struct EdgeNode { /* private fields */ }

ContractData

Represents contract-specific data needed for storage proof verification

This structure contains all the necessary information about a contract’s state, including its class hash, nonce, state hash version, and the storage proof itself.

Fields

• class_hash - The hash of the contract’s class
• nonce - The contract’s current nonce
• contract_state_hash_version - Version identifier for the contract state hash format
• storage_proof - Array of TrieNode representing the storage proof path

Fully qualified path: alexandria_merkle_tree::storage_proof::ContractData

[derive(Destruct, Serde)]
pub struct ContractData { /* private fields */ }

ContractStateProof

Represents a complete contract state proof for verification

This structure contains all components needed to verify a contract’s state against the Starknet global state commitment, including the class commitment, contract proof, and contract-specific data.

Fields

• class_commitment - The commitment hash for contract classes
• contract_proof - Array of TrieNode representing the contract proof path
• contract_data - ContractData containing contract-specific information and storage proof

Fully qualified path: alexandria_merkle_tree::storage_proof::ContractStateProof

[derive(Destruct, Serde)]
pub struct ContractStateProof { /* private fields */ }

Enums

Enums

TrieNode

Represents a node in a Merkle Patricia Trie

This enum encapsulates the two types of nodes that can exist in a Merkle Patricia Trie: binary nodes (which have exactly two children) and edge nodes (which compress paths).

Variants

• Binary - A binary node with left and right children
• Edge - An edge node with a compressed path and single child

Fully qualified path: alexandria_merkle_tree::storage_proof::TrieNode

pub enum TrieNode {
    Binary: BinaryNode,
    Edge: EdgeNode,
}

Variants

Binary

Fully qualified path: alexandria_merkle_tree::storage_proof::TrieNode::Binary

Binary: BinaryNode

Edge

Fully qualified path: alexandria_merkle_tree::storage_proof::TrieNode::Edge

Edge: EdgeNode

Traits

Traits

BinaryNodeTrait

Fully qualified path: alexandria_merkle_tree::storage_proof::BinaryNodeTrait

pub trait BinaryNodeTrait

Trait functions

new

Creates a new BinaryNode with the specified left and right child hashes

Arguments

• left - Hash of the left child node
• right - Hash of the right child node

Returns

• BinaryNode - A new BinaryNode instance with the specified children

Fully qualified path: alexandria_merkle_tree::storage_proof::BinaryNodeTrait::new

fn new(left: felt252, right: felt252) -> BinaryNode

EdgeNodeTrait

Fully qualified path: alexandria_merkle_tree::storage_proof::EdgeNodeTrait

pub trait EdgeNodeTrait

Trait functions

new

Creates a new EdgeNode with the specified path, child hash, and path length

Arguments

• path - The compressed path as a felt252 value
• child - Hash of the child node at the end of this path
• length - Length of the compressed path in bits

Returns

• EdgeNode - A new EdgeNode instance with the specified parameters

Fully qualified path: alexandria_merkle_tree::storage_proof::EdgeNodeTrait::new

fn new(path: felt252, child: felt252, length: u8) -> EdgeNode

ContractDataTrait

Fully qualified path: alexandria_merkle_tree::storage_proof::ContractDataTrait

pub trait ContractDataTrait

Trait functions

new

Creates a new ContractData instance with the specified parameters

Arguments

• class_hash - The class hash of the contract
• nonce - The nonce of the contract
• contract_state_hash_version - The version of the contract state hash
• storage_proof - Array of TrieNode representing the storage proof

Returns

• ContractData - A new ContractData instance

Fully qualified path: alexandria_merkle_tree::storage_proof::ContractDataTrait::new

fn new(
    class_hash: felt252,
    nonce: felt252,
    contract_state_hash_version: felt252,
    storage_proof: Array<TrieNode>,
) -> ContractData

ContractStateProofTrait

Fully qualified path: alexandria_merkle_tree::storage_proof::ContractStateProofTrait

pub trait ContractStateProofTrait

Trait functions

new

Creates a new ContractStateProof instance with the specified parameters

Arguments

• class_commitment - The class commitment hash
• contract_proof - Array of TrieNode representing the contract proof
• contract_data - ContractData containing contract-specific information

Returns

• ContractStateProof - A new ContractStateProof instance

Fully qualified path: alexandria_merkle_tree::storage_proof::ContractStateProofTrait::new

fn new(
    class_commitment: felt252, contract_proof: Array<TrieNode>, contract_data: ContractData,
) -> ContractStateProof

Impls

Impls

BinaryNodeImpl

Trait for creating and manipulating BinaryNode instances

Fully qualified path: alexandria_merkle_tree::storage_proof::BinaryNodeImpl

pub impl BinaryNodeImpl of BinaryNodeTrait;

Impl functions

new

Creates a new BinaryNode with the specified left and right child hashes

Arguments

• left - Hash of the left child node
• right - Hash of the right child node

Returns

• BinaryNode - A new BinaryNode instance with the specified children

Fully qualified path: alexandria_merkle_tree::storage_proof::BinaryNodeImpl::new

fn new(left: felt252, right: felt252) -> BinaryNode

EdgeNodeImpl

Trait for creating and manipulating EdgeNode instances

Fully qualified path: alexandria_merkle_tree::storage_proof::EdgeNodeImpl

pub impl EdgeNodeImpl of EdgeNodeTrait;

Impl functions

new

Creates a new EdgeNode with the specified path, child hash, and path length

Arguments

• path - The compressed path as a felt252 value
• child - Hash of the child node at the end of this path
• length - Length of the compressed path in bits

Returns

• EdgeNode - A new EdgeNode instance with the specified parameters

Fully qualified path: alexandria_merkle_tree::storage_proof::EdgeNodeImpl::new

fn new(path: felt252, child: felt252, length: u8) -> EdgeNode

ContractDataImpl

Fully qualified path: alexandria_merkle_tree::storage_proof::ContractDataImpl

pub impl ContractDataImpl of ContractDataTrait;

Impl functions

new

Creates a new ContractData instance with the specified parameters

Arguments

• class_hash - The class hash of the contract
• nonce - The nonce of the contract
• contract_state_hash_version - The version of the contract state hash
• storage_proof - Array of TrieNode representing the storage proof

Returns

• ContractData - A new ContractData instance

Fully qualified path: alexandria_merkle_tree::storage_proof::ContractDataImpl::new

fn new(
    class_hash: felt252,
    nonce: felt252,
    contract_state_hash_version: felt252,
    storage_proof: Array<TrieNode>,
) -> ContractData

ContractStateProofImpl

Fully qualified path: alexandria_merkle_tree::storage_proof::ContractStateProofImpl

pub impl ContractStateProofImpl of ContractStateProofTrait;

Impl functions

new

Creates a new ContractStateProof instance with the specified parameters

Arguments

• class_commitment - The class commitment hash
• contract_proof - Array of TrieNode representing the contract proof
• contract_data - ContractData containing contract-specific information

Returns

• ContractStateProof - A new ContractStateProof instance

Fully qualified path: alexandria_merkle_tree::storage_proof::ContractStateProofImpl::new

fn new(
    class_commitment: felt252, contract_proof: Array<TrieNode>, contract_data: ContractData,
) -> ContractStateProof