cartesian_merkle_tree

Cartesian Merkle Tree Library

This library provides a complete implementation of Cartesian Merkle Trees with both in-memory and on-chain (Starknet component) capabilities.

Core Library

The in-memory implementation consists of:

• Tree operations (insert, remove, search)
• Cryptographic proof generation and verification
• Utility functions for node management and hashing

Starknet Component

The on-chain component provides:

• Storage-based tree implementation
• All core tree operations as contract functions
• Gas-optimized index management with reuse

Usage Examples

In-Memory Tree

use cartesian_merkle_tree::{CMTree, CMTreeTrait};

let mut tree = CMTreeTrait::new();
tree.insert(42);
assert!(tree.search(42));

let proof = tree.generate_proof(42);
let root = tree.get_root_hash();
assert!(proof.verify(root, 42));

Starknet Component

use cartesian_merkle_tree::components::cmtree_component;

[starknet::contract]
mod MyContract {
    component!(path: cmtree_component, storage: tree, event: TreeEvent);

    [abi(embed_v0)]
    impl CMTreeImpl = cmtree_component::CMTree<ContractState>;
}

Fully qualified path: cartesian_merkle_tree

Modules

Re-exports:

• Structs

• Traits

Modules

Modules

library

Fully qualified path: cartesian_merkle_tree::library

Modules

Modules

Modules

node

Node structure and implementation for Cartesian Merkle Trees.

This module provides the core CMTNode structure that represents individual nodes in the tree, containing key, priority, hash, and child references.

Fully qualified path: cartesian_merkle_tree::library::node

Structs

Traits

Impls

Structs

Structs

CMTNode

A node in the Cartesian Merkle Tree containing key, priority, hash, and child references.

Each node maintains the three essential properties of the CMT: - Key: Used for BST ordering and proof generation - Priority: Randomized value for heap property maintenance - Merkle Hash: Cryptographic commitment to this node and its subtree - Children: References to left and right child nodes

Fully qualified path: cartesian_merkle_tree::library::node::CMTNode

[derive(Drop, Copy, Debug)]
pub struct CMTNode {
    pub key: felt252,
    pub priority: felt252,
    pub merkle_hash: felt252,
    pub left_child: Option<Box<CMTNode>>,
    pub right_child: Option<Box<CMTNode>>,
}

Members

key

The key value for BST ordering and identification

Fully qualified path: cartesian_merkle_tree::library::node::CMTNode::key

pub key: felt252

priority

Randomized priority for heap property (derived from key)

Fully qualified path: cartesian_merkle_tree::library::node::CMTNode::priority

pub priority: felt252

merkle_hash

Merkle hash commitment to this node and its children

Fully qualified path: cartesian_merkle_tree::library::node::CMTNode::merkle_hash

pub merkle_hash: felt252

left_child

Reference to the left child node (keys < this.key)

Fully qualified path: cartesian_merkle_tree::library::node::CMTNode::left_child

pub left_child: Option<Box<CMTNode>>

right_child

Reference to the right child node (keys > this.key)

Fully qualified path: cartesian_merkle_tree::library::node::CMTNode::right_child

pub right_child: Option<Box<CMTNode>>

Traits

Traits

CMTNodeTrait

Fully qualified path: cartesian_merkle_tree::library::node::CMTNodeTrait

pub trait CMTNodeTrait

Trait functions

new

Creates a new CMT node with the specified key and priority.

The node is initialized with no children and a zero Merkle hash. The hash should be updated using update_merkle_hash() after creation.

Arguments

• key - The key value for this node
• priority - The priority value for heap ordering

Returns

A new CMTNode with the specified key and priority

Examples

let key = 42;
let priority = CMTUtilsTrait::calculate_priority(key);
let node = CMTNodeTrait::new(key, priority);
assert_eq!(node.key, key);
assert_eq!(node.merkle_hash, 0);

Fully qualified path: cartesian_merkle_tree::library::node::CMTNodeTrait::new

fn new(key: felt252, priority: felt252) -> CMTNode

new_with_children

Creates a new CMT node with the specified key, priority, and children.

The Merkle hash is automatically calculated based on the key and children hashes. This is typically used during tree rotations or reconstruction.

Arguments

• key - The key value for this node
• priority - The priority value for heap ordering
• left_child - Optional left child node
• right_child - Optional right child node

Returns

A new CMTNode with calculated Merkle hash

Examples

let node = CMTNodeTrait::new_with_children(
    50, priority, Some(left_box), Some(right_box)
);
assert!(node.merkle_hash != 0);

Fully qualified path: cartesian_merkle_tree::library::node::CMTNodeTrait::new_with_children

fn new_with_children(
    key: felt252,
    priority: felt252,
    left_child: Option<Box<CMTNode>>,
    right_child: Option<Box<CMTNode>>,
) -> CMTNode

update_merkle_hash

Updates the Merkle hash of this node based on its key and current children.

This method should be called whenever the node’s children change to maintain the cryptographic integrity of the tree. The hash is computed deterministically using the node’s key and its children’s hashes.

Examples

let mut node = CMTNodeTrait::new(key, priority);
node.left_child = Some(left_child_box);
node.update_merkle_hash(); // Hash now reflects the new child

Fully qualified path: cartesian_merkle_tree::library::node::CMTNodeTrait::update_merkle_hash

fn update_merkle_hash(ref self: CMTNode)

Impls

Impls

CMTNodeImpl

Fully qualified path: cartesian_merkle_tree::library::node::CMTNodeImpl

pub impl CMTNodeImpl of CMTNodeTrait;

Impl functions

new

Creates a new CMT node with the specified key and priority.

The node is initialized with no children and a zero Merkle hash. The hash should be updated using update_merkle_hash() after creation.

Arguments

• key - The key value for this node
• priority - The priority value for heap ordering

Returns

A new CMTNode with the specified key and priority

Examples

let key = 42;
let priority = CMTUtilsTrait::calculate_priority(key);
let node = CMTNodeTrait::new(key, priority);
assert_eq!(node.key, key);
assert_eq!(node.merkle_hash, 0);

Fully qualified path: cartesian_merkle_tree::library::node::CMTNodeImpl::new

fn new(key: felt252, priority: felt252) -> CMTNode

new_with_children

Creates a new CMT node with the specified key, priority, and children.

The Merkle hash is automatically calculated based on the key and children hashes. This is typically used during tree rotations or reconstruction.

Arguments

• key - The key value for this node
• priority - The priority value for heap ordering
• left_child - Optional left child node
• right_child - Optional right child node

Returns

A new CMTNode with calculated Merkle hash

Examples

let node = CMTNodeTrait::new_with_children(
    50, priority, Some(left_box), Some(right_box)
);
assert!(node.merkle_hash != 0);

Fully qualified path: cartesian_merkle_tree::library::node::CMTNodeImpl::new_with_children

fn new_with_children(
    key: felt252,
    priority: felt252,
    left_child: Option<Box<CMTNode>>,
    right_child: Option<Box<CMTNode>>,
) -> CMTNode

update_merkle_hash

Updates the Merkle hash of this node based on its key and current children.

This method should be called whenever the node’s children change to maintain the cryptographic integrity of the tree. The hash is computed deterministically using the node’s key and its children’s hashes.

Examples

let mut node = CMTNodeTrait::new(key, priority);
node.left_child = Some(left_child_box);
node.update_merkle_hash(); // Hash now reflects the new child

Fully qualified path: cartesian_merkle_tree::library::node::CMTNodeImpl::update_merkle_hash

fn update_merkle_hash(ref self: CMTNode)

proof

Cartesian Merkle Tree proof generation and verification.

This module provides functionality for:

• Generating cryptographic proofs of key existence or non-existence in CMTrees
• Verifying proofs against tree root hashes
• Supporting both membership and non-membership proofs

Examples

Creating and verifying an existence proof:

let mut tree = CMTreeTrait::new();
tree.insert(50);
tree.insert(30);
tree.insert(70);

let proof = tree.generate_proof_with_path(30);
let root_hash = tree.get_root_hash();
assert!(proof.verify(root_hash, 30));

Generating a non-existence proof:

let mut tree = CMTreeTrait::new();
tree.insert(50);
tree.insert(70);

let proof = tree.generate_proof_with_path(60); // Key doesn't exist
let root_hash = tree.get_root_hash();
assert!(proof.verify(root_hash, 60)); // Non-existence proof verifies

Working with empty trees:

let tree = CMTreeTrait::new();
let proof = tree.generate_proof_with_path(50);
assert!(!proof.existence); // Empty tree always returns non-existence

Fully qualified path: cartesian_merkle_tree::library::proof

Structs

Traits

Impls

Structs

Structs

ProofNode

A node in a Merkle proof path containing key and hash information.

Fully qualified path: cartesian_merkle_tree::library::proof::ProofNode

[derive(Drop, Clone, Debug)]
pub struct ProofNode {
    pub key: felt252,
    pub merkle_hash: felt252,
}

Members

key

The key associated with this proof node

Fully qualified path: cartesian_merkle_tree::library::proof::ProofNode::key

pub key: felt252

merkle_hash

The Merkle hash of this proof node

Fully qualified path: cartesian_merkle_tree::library::proof::ProofNode::merkle_hash

pub merkle_hash: felt252

CMTProof

A Cartesian Merkle Tree proof structure containing all information needed to verify membership or non-membership.

The proof contains sibling information along the path from a leaf to the root, allowing verification of key existence or non-existence in the tree without requiring the full tree structure.

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProof

[derive(Drop, Clone, Debug)]
pub struct CMTProof {
    pub root: felt252,
    pub siblings: Array<felt252>,
    pub siblings_length: u32,
    pub direction_bits: felt252,
    pub existence: bool,
    pub key: felt252,
    pub non_existence_key: felt252,
}

Members

root

The root hash of the tree this proof was generated from

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProof::root

pub root: felt252

siblings

Array containing alternating keys and hashes of sibling nodes along the proof path

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProof::siblings

pub siblings: Array<felt252>

siblings_length

The total number of elements in the siblings array

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProof::siblings_length

pub siblings_length: u32

direction_bits

Bit field indicating the ordering of child hashes when computing parent hashes

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProof::direction_bits

pub direction_bits: felt252

existence

Whether this proof demonstrates key existence (true) or non-existence (false)

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProof::existence

pub existence: bool

key

The key being proven to exist or not exist

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProof::key

pub key: felt252

non_existence_key

For non-existence proofs, the key of the node where the target key would be inserted

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProof::non_existence_key

pub non_existence_key: felt252

Traits

Traits

CMTProofTrait

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProofTrait

pub trait CMTProofTrait

Trait functions

new

Creates a new empty CMTProof with default values.

Returns

A new CMTProof instance with all fields initialized to zero/empty values.

Examples

let proof = CMTProofTrait::new();
assert!(!proof.existence);
assert!(proof.siblings_length == 0);

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProofTrait::new

fn new() -> CMTProof

verify

Verifies a CMT proof against a given root hash and key.

This method reconstructs the Merkle path from the leaf to the root using the sibling information stored in the proof, and checks if the computed root matches the expected root hash.

Arguments

• root_hash - The expected root hash of the tree
• key - The key being verified

Returns

true if the proof is valid, false otherwise

Examples

let mut tree = CMTreeTrait::new();
tree.insert(50);
let proof = tree.generate_proof_with_path(50);
let root = tree.get_root_hash();
assert!(proof.verify(root, 50));

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProofTrait::verify

fn verify(self: @CMTProof, root_hash: felt252, key: felt252) -> bool

calculate_node_hash

Calculates the Merkle hash for a node given its key and child hashes.

This function ensures consistent hash ordering by sorting child hashes before computing the parent hash, maintaining compatibility with the Solidity implementation.

Arguments

• key - The key of the node
• left_hash - Hash of the left child
• right_hash - Hash of the right child

Returns

The computed Merkle hash for the node

Examples

let hash = CMTProofTrait::calculate_node_hash(50, 0, 0);
assert!(hash != 0);

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProofTrait::calculate_node_hash

fn calculate_node_hash(key: felt252, left_hash: felt252, right_hash: felt252) -> felt252

CMTreeProofTrait

Fully qualified path: cartesian_merkle_tree::library::proof::CMTreeProofTrait

pub trait CMTreeProofTrait

Trait functions

generate_proof_with_path

Generates a cryptographic proof for a key in the Cartesian Merkle Tree.

This method creates either an existence proof (if the key is found) or a non-existence proof (if the key is not found) by collecting sibling information along the search path.

Arguments

• key - The key to generate a proof for

Returns

A CMTProof containing all necessary information to verify the key’s presence or absence

Examples

let mut tree = CMTreeTrait::new();
tree.insert(50);

// Generate existence proof
let existence_proof = tree.generate_proof_with_path(50);
assert!(existence_proof.existence);

// Generate non-existence proof
let non_existence_proof = tree.generate_proof_with_path(60);
assert!(!non_existence_proof.existence);

Fully qualified path: cartesian_merkle_tree::library::proof::CMTreeProofTrait::generate_proof_with_path

fn generate_proof_with_path(self: @CMTree, key: felt252) -> CMTProof

generate_proof_internal

Internal recursive function for generating proof data by traversing the tree.

This function performs a depth-first search through the tree, collecting sibling information and direction bits needed to reconstruct the Merkle path during verification.

Arguments

• node - Current node being examined
• key - Target key to generate proof for
• siblings - Mutable reference to array collecting sibling data
• direction_bits - Mutable reference to bit field for hash ordering
• siblings_count - Mutable reference to count of collected siblings

Returns

A tuple containing:

• bool - Whether the key was found
• felt252 - For non-existence proofs, the key where insertion would occur

Fully qualified path: cartesian_merkle_tree::library::proof::CMTreeProofTrait::generate_proof_internal

fn generate_proof_internal(
    node: @Box<CMTNode>,
    key: felt252,
    ref siblings: Array<felt252>,
    ref direction_bits: felt252,
    ref siblings_count: u32,
) -> (bool, felt252)

calculate_direction_bit

Calculates and updates the direction bits for hash ordering during proof verification.

Direction bits encode whether child hashes were swapped during node hash calculation. This information is essential for correctly reconstructing the Merkle path during verification.

Arguments

• direction_bits - Current direction bits value
• siblings_count - Number of siblings processed so far
• is_swapped - Whether the child hashes were swapped for this level

Returns

Updated direction bits value

Fully qualified path: cartesian_merkle_tree::library::proof::CMTreeProofTrait::calculate_direction_bit

fn calculate_direction_bit(
    direction_bits: felt252, siblings_count: u32, is_swapped: bool,
) -> felt252

Impls

Impls

CMTProofImpl

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProofImpl

pub impl CMTProofImpl of CMTProofTrait;

Impl functions

new

Creates a new empty CMTProof with default values.

Returns

A new CMTProof instance with all fields initialized to zero/empty values.

Examples

let proof = CMTProofTrait::new();
assert!(!proof.existence);
assert!(proof.siblings_length == 0);

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProofImpl::new

fn new() -> CMTProof

verify

Verifies a CMT proof against a given root hash and key.

This method reconstructs the Merkle path from the leaf to the root using the sibling information stored in the proof, and checks if the computed root matches the expected root hash.

Arguments

• root_hash - The expected root hash of the tree
• key - The key being verified

Returns

true if the proof is valid, false otherwise

Examples

let mut tree = CMTreeTrait::new();
tree.insert(50);
let proof = tree.generate_proof_with_path(50);
let root = tree.get_root_hash();
assert!(proof.verify(root, 50));

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProofImpl::verify

fn verify(self: @CMTProof, root_hash: felt252, key: felt252) -> bool

calculate_node_hash

Calculates the Merkle hash for a node given its key and child hashes.

This function ensures consistent hash ordering by sorting child hashes before computing the parent hash, maintaining compatibility with the Solidity implementation.

Arguments

• key - The key of the node
• left_hash - Hash of the left child
• right_hash - Hash of the right child

Returns

The computed Merkle hash for the node

Examples

let hash = CMTProofTrait::calculate_node_hash(50, 0, 0);
assert!(hash != 0);

Fully qualified path: cartesian_merkle_tree::library::proof::CMTProofImpl::calculate_node_hash

fn calculate_node_hash(key: felt252, left_hash: felt252, right_hash: felt252) -> felt252

CMTreeProofImpl

Fully qualified path: cartesian_merkle_tree::library::proof::CMTreeProofImpl

pub impl CMTreeProofImpl of CMTreeProofTrait;

Impl functions

generate_proof_with_path

Generates a cryptographic proof for a key in the Cartesian Merkle Tree.

This method creates either an existence proof (if the key is found) or a non-existence proof (if the key is not found) by collecting sibling information along the search path.

Arguments

• key - The key to generate a proof for

Returns

A CMTProof containing all necessary information to verify the key’s presence or absence

Examples

let mut tree = CMTreeTrait::new();
tree.insert(50);

// Generate existence proof
let existence_proof = tree.generate_proof_with_path(50);
assert!(existence_proof.existence);

// Generate non-existence proof
let non_existence_proof = tree.generate_proof_with_path(60);
assert!(!non_existence_proof.existence);

Fully qualified path: cartesian_merkle_tree::library::proof::CMTreeProofImpl::generate_proof_with_path

fn generate_proof_with_path(self: @CMTree, key: felt252) -> CMTProof

generate_proof_internal

Internal recursive function for generating proof data by traversing the tree.

This function performs a depth-first search through the tree, collecting sibling information and direction bits needed to reconstruct the Merkle path during verification.

Arguments

• node - Current node being examined
• key - Target key to generate proof for
• siblings - Mutable reference to array collecting sibling data
• direction_bits - Mutable reference to bit field for hash ordering
• siblings_count - Mutable reference to count of collected siblings

Returns

A tuple containing:

• bool - Whether the key was found
• felt252 - For non-existence proofs, the key where insertion would occur

Fully qualified path: cartesian_merkle_tree::library::proof::CMTreeProofImpl::generate_proof_internal

fn generate_proof_internal(
    node: @Box<CMTNode>,
    key: felt252,
    ref siblings: Array<felt252>,
    ref direction_bits: felt252,
    ref siblings_count: u32,
) -> (bool, felt252)

calculate_direction_bit

Calculates and updates the direction bits for hash ordering during proof verification.

Direction bits encode whether child hashes were swapped during node hash calculation. This information is essential for correctly reconstructing the Merkle path during verification.

Arguments

• direction_bits - Current direction bits value
• siblings_count - Number of siblings processed so far
• is_swapped - Whether the child hashes were swapped for this level

Returns

Updated direction bits value

Fully qualified path: cartesian_merkle_tree::library::proof::CMTreeProofImpl::calculate_direction_bit

fn calculate_direction_bit(
    direction_bits: felt252, siblings_count: u32, is_swapped: bool,
) -> felt252

tree

Cartesian Merkle Tree implementation combining BST and heap properties.

This module provides a complete implementation of a Cartesian Merkle Tree, which is:

• A binary search tree ordered by keys
• A heap ordered by priorities (randomized based on keys)
• A Merkle tree with cryptographic hash verification
• Self-balancing through treap rotations

The structure maintains logarithmic time complexity for insertions, deletions, and searches while providing cryptographic proof capabilities through Merkle hashes.

Examples

Creating and using a new tree:

let mut tree = CMTreeTrait::new();
tree.insert(50);
tree.insert(30);
tree.insert(70);

assert!(tree.search(50));
let root_hash = tree.get_root_hash();

Working with multiple operations:

let mut tree = CMTreeTrait::new();
tree.insert(10);
tree.insert(20);
tree.insert(5);

assert!(tree.remove(10));
assert!(!tree.search(10));
assert!(tree.search(20));

Getting cryptographic verification:

let mut tree = CMTreeTrait::new();
tree.insert(42);
let hash = tree.get_root_hash();
assert!(hash != 0); // Non-empty tree has non-zero hash

Fully qualified path: cartesian_merkle_tree::library::tree

Structs

Traits

Impls

Structs

Structs

CMTree

A Cartesian Merkle Tree combining binary search tree, heap, and Merkle tree properties.

The tree maintains three invariants simultaneously: 1. BST Property: Left subtree keys < node key < right subtree keys 2. Heap Property: Parent priority >= child priorities 3. Merkle Property: Each node’s hash depends on its key and children’s hashes

Fully qualified path: cartesian_merkle_tree::library::tree::CMTree

[derive(Drop, Copy, Debug)]
pub struct CMTree {
    pub root: Option<Box<CMTNode>>,
}

Members

root

The root node of the tree, None for empty trees

Fully qualified path: cartesian_merkle_tree::library::tree::CMTree::root

pub root: Option<Box<CMTNode>>

Traits

Traits

CMTreeTrait

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait

pub trait CMTreeTrait

Trait functions

new

Creates a new empty Cartesian Merkle Tree.

Returns

An empty CMTree with no root node

Examples

let tree = CMTreeTrait::new();
assert_eq!(tree.get_root_hash(), 0);
assert!(!tree.search(42));

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::new

fn new() -> CMTree

insert

Inserts a key into the Cartesian Merkle Tree.

The insertion maintains all three tree properties (BST, heap, Merkle) through:

1. BST insertion based on key comparison
2. Treap rotations to maintain heap property based on priority
3. Merkle hash updates for cryptographic integrity

Priority is deterministically calculated from the key, ensuring consistent tree structure.

Arguments

• key - The key to insert into the tree

Examples

let mut tree = CMTreeTrait::new();
tree.insert(42);
assert!(tree.search(42));

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::insert

fn insert(ref self: CMTree, key: felt252)

insert_node

Internal recursive function for inserting a node while maintaining tree properties.

Performs BST insertion based on key comparison, then checks and restores heap property through rotations if necessary. Updates Merkle hashes along the insertion path.

Arguments

• current - The current node being examined
• new_node - The node to insert

Returns

The root of the subtree after insertion and any necessary rotations

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::insert_node

fn insert_node(current: Box<CMTNode>, new_node: Box<CMTNode>) -> Box<CMTNode>

restore_heap_property

Restores the heap property by performing rotations when a child has higher priority than parent.

This function checks if the specified child violates the heap property (child priority > parent priority) and performs the appropriate rotation to restore it. This maintains the treap invariant.

Arguments

• node - The node to check and potentially rotate
• check_left - Whether to check the left child (true) or right child (false)

Returns

The root of the subtree after any necessary rotation

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::restore_heap_property

fn restore_heap_property(node: Box<CMTNode>, check_left: bool) -> Box<CMTNode>

search

Searches for a key in the Cartesian Merkle Tree.

Performs a standard BST search using key comparisons to navigate the tree. Time complexity is O(log n) on average due to the randomized heap property.

Arguments

• key - The key to search for

Returns

true if the key exists in the tree, false otherwise

Examples

let mut tree = CMTreeTrait::new();
tree.insert(42);
assert!(tree.search(42));
assert!(!tree.search(100));

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::search

fn search(self: @CMTree, key: felt252) -> bool

search_node

Internal recursive function for searching a key starting from a given node.

Performs BST traversal by comparing keys and recursively searching the appropriate subtree.

Arguments

• node - The current node being examined
• key - The key to search for

Returns

true if the key is found in the subtree, false otherwise

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::search_node

fn search_node(node: @Box<CMTNode>, key: felt252) -> bool

get_root_hash

Returns the Merkle hash of the tree’s root node.

The root hash serves as a cryptographic commitment to the entire tree structure and contents, enabling efficient verification of tree state and proof validation.

Returns

• 0 for empty trees
• The Merkle hash of the root node for non-empty trees

Examples

let tree = CMTreeTrait::new();
assert_eq!(tree.get_root_hash(), 0);

let mut tree = CMTreeTrait::new();
tree.insert(42);
assert!(tree.get_root_hash() != 0);

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::get_root_hash

fn get_root_hash(self: @CMTree) -> felt252

remove

Removes a key from the Cartesian Merkle Tree.

Removal maintains all tree properties through a rotation-based approach:

1. Locate the target node using BST search
2. For nodes with children, rotate them toward a leaf position
3. Remove the node once it becomes a leaf
4. Update Merkle hashes along the removal path

Arguments

• key - The key to remove from the tree

Returns

true if the key was found and removed, false if the key wasn’t in the tree

Examples

let mut tree = CMTreeTrait::new();
tree.insert(42);
assert!(tree.remove(42));
assert!(!tree.search(42));
assert!(!tree.remove(100)); // Non-existent key

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::remove

fn remove(ref self: CMTree, key: felt252) -> bool

remove_node

Internal recursive function for removing a node while maintaining tree properties.

This function handles the BST deletion process, including special handling for nodes with two children by delegating to rotation-based removal.

Arguments

• node - The current node being examined
• key - The key to remove

Returns

A tuple containing:

• The new root of this subtree (None if subtree becomes empty)
• Whether the key was found and removed

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::remove_node

fn remove_node(node: Box<CMTNode>, key: felt252) -> (Option<Box<CMTNode>>, bool)

rotate_to_leaf_and_remove

Rotates a node with two children toward a leaf position, then removes it.

This function implements the treap deletion strategy for nodes with both children: repeatedly rotate the node down the tree based on child priorities until it becomes a leaf, then remove it. This maintains both BST and heap properties.

Arguments

• node - The node to rotate and remove
• key - The key being removed (for verification)

Returns

The new root of this subtree after rotation and removal

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::rotate_to_leaf_and_remove

fn rotate_to_leaf_and_remove(node: Box<CMTNode>, key: felt252) -> Option<Box<CMTNode>>

Impls

Impls

CMTreeImpl

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeImpl

pub impl CMTreeImpl of CMTreeTrait;

Impl functions

new

Creates a new empty Cartesian Merkle Tree.

Returns

An empty CMTree with no root node

Examples

let tree = CMTreeTrait::new();
assert_eq!(tree.get_root_hash(), 0);
assert!(!tree.search(42));

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeImpl::new

fn new() -> CMTree

insert

Inserts a key into the Cartesian Merkle Tree.

The insertion maintains all three tree properties (BST, heap, Merkle) through:

1. BST insertion based on key comparison
2. Treap rotations to maintain heap property based on priority
3. Merkle hash updates for cryptographic integrity

Priority is deterministically calculated from the key, ensuring consistent tree structure.

Arguments

• key - The key to insert into the tree

Examples

let mut tree = CMTreeTrait::new();
tree.insert(42);
assert!(tree.search(42));

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeImpl::insert

fn insert(ref self: CMTree, key: felt252)

insert_node

Internal recursive function for inserting a node while maintaining tree properties.

Performs BST insertion based on key comparison, then checks and restores heap property through rotations if necessary. Updates Merkle hashes along the insertion path.

Arguments

• current - The current node being examined
• new_node - The node to insert

Returns

The root of the subtree after insertion and any necessary rotations

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeImpl::insert_node

fn insert_node(mut current: Box<CMTNode>, new_node: Box<CMTNode>) -> Box<CMTNode>

restore_heap_property

Restores the heap property by performing rotations when a child has higher priority than parent.

This function checks if the specified child violates the heap property (child priority > parent priority) and performs the appropriate rotation to restore it. This maintains the treap invariant.

Arguments

• node - The node to check and potentially rotate
• check_left - Whether to check the left child (true) or right child (false)

Returns

The root of the subtree after any necessary rotation

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeImpl::restore_heap_property

fn restore_heap_property(node: Box<CMTNode>, check_left: bool) -> Box<CMTNode>

search

Searches for a key in the Cartesian Merkle Tree.

Performs a standard BST search using key comparisons to navigate the tree. Time complexity is O(log n) on average due to the randomized heap property.

Arguments

• key - The key to search for

Returns

true if the key exists in the tree, false otherwise

Examples

let mut tree = CMTreeTrait::new();
tree.insert(42);
assert!(tree.search(42));
assert!(!tree.search(100));

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeImpl::search

fn search(self: @CMTree, key: felt252) -> bool

search_node

Internal recursive function for searching a key starting from a given node.

Performs BST traversal by comparing keys and recursively searching the appropriate subtree.

Arguments

• node - The current node being examined
• key - The key to search for

Returns

true if the key is found in the subtree, false otherwise

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeImpl::search_node

fn search_node(node: @Box<CMTNode>, key: felt252) -> bool

get_root_hash

Returns the Merkle hash of the tree’s root node.

The root hash serves as a cryptographic commitment to the entire tree structure and contents, enabling efficient verification of tree state and proof validation.

Returns

• 0 for empty trees
• The Merkle hash of the root node for non-empty trees

Examples

let tree = CMTreeTrait::new();
assert_eq!(tree.get_root_hash(), 0);

let mut tree = CMTreeTrait::new();
tree.insert(42);
assert!(tree.get_root_hash() != 0);

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeImpl::get_root_hash

fn get_root_hash(self: @CMTree) -> felt252

remove

Removes a key from the Cartesian Merkle Tree.

Removal maintains all tree properties through a rotation-based approach:

1. Locate the target node using BST search
2. For nodes with children, rotate them toward a leaf position
3. Remove the node once it becomes a leaf
4. Update Merkle hashes along the removal path

Arguments

• key - The key to remove from the tree

Returns

true if the key was found and removed, false if the key wasn’t in the tree

Examples

let mut tree = CMTreeTrait::new();
tree.insert(42);
assert!(tree.remove(42));
assert!(!tree.search(42));
assert!(!tree.remove(100)); // Non-existent key

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeImpl::remove

fn remove(ref self: CMTree, key: felt252) -> bool

remove_node

Internal recursive function for removing a node while maintaining tree properties.

This function handles the BST deletion process, including special handling for nodes with two children by delegating to rotation-based removal.

Arguments

• node - The current node being examined
• key - The key to remove

Returns

A tuple containing:

• The new root of this subtree (None if subtree becomes empty)
• Whether the key was found and removed

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeImpl::remove_node

fn remove_node(node: Box<CMTNode>, key: felt252) -> (Option<Box<CMTNode>>, bool)

rotate_to_leaf_and_remove

Rotates a node with two children toward a leaf position, then removes it.

This function implements the treap deletion strategy for nodes with both children: repeatedly rotate the node down the tree based on child priorities until it becomes a leaf, then remove it. This maintains both BST and heap properties.

Arguments

• node - The node to rotate and remove
• key - The key being removed (for verification)

Returns

The new root of this subtree after rotation and removal

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeImpl::rotate_to_leaf_and_remove

fn rotate_to_leaf_and_remove(node: Box<CMTNode>, key: felt252) -> Option<Box<CMTNode>>

utils

Utility functions for Cartesian Merkle Trees.

This module provides the core utility functions for CMT operations:

• Priority calculation using cryptographic hashing
• Merkle hash computation with consistent ordering
• Tree rotation operations for maintaining heap property
• Helper functions for child node management

The utilities ensure deterministic behavior and cryptographic security through the use of Poseidon hashing for both priorities and Merkle commitments.

Examples

Computing priorities:

let key = 42;
let priority = CMTUtilsTrait::calculate_priority(key);

Computing Merkle hashes:

let hash = CMTUtilsTrait::calculate_merkle_hash(key, left_hash, right_hash);
assert!(hash != 0);

Performing tree rotations:

let rotated = CMTUtilsTrait::right_rotate(node_box);
// Tree structure is now rotated while maintaining properties

Fully qualified path: cartesian_merkle_tree::library::utils

Traits

Impls

Traits

Traits

CMTUtilsTrait

Fully qualified path: cartesian_merkle_tree::library::utils::CMTUtilsTrait

pub trait CMTUtilsTrait

Trait functions

calculate_priority

Calculates a deterministic priority for a given key using Poseidon hashing.

The priority is used to maintain the heap property in the treap structure. Using cryptographic hashing ensures the priorities are effectively randomized while remaining deterministic for the same key.

Arguments

• key - The key to calculate priority for

Returns

A felt252 priority value derived from the key

Examples

let priority1 = CMTUtilsTrait::calculate_priority(42);
let priority2 = CMTUtilsTrait::calculate_priority(42);
assert_eq!(priority1, priority2); // Deterministic

let priority3 = CMTUtilsTrait::calculate_priority(43);
assert!(priority1 != priority3); // Different keys give different priorities

Fully qualified path: cartesian_merkle_tree::library::utils::CMTUtilsTrait::calculate_priority

fn calculate_priority(key: felt252) -> felt252

calculate_merkle_hash

Calculates the Merkle hash for a node given its key and children hashes.

The hash is computed using Poseidon with consistent ordering: the key is hashed first, followed by the children hashes in sorted order (smaller hash first). This ensures deterministic hashing regardless of the tree’s structure.

Arguments

• key - The key of the node
• left_child_mh - Merkle hash of the left child (0 if None)
• right_child_mh - Merkle hash of the right child (0 if None)

Returns

The computed Merkle hash for the node

Examples

let hash = CMTUtilsTrait::calculate_merkle_hash(50, 100, 200);
assert!(hash != 0);

// Hash is independent of child order
let same_hash = CMTUtilsTrait::calculate_merkle_hash(50, 200, 100);
assert_eq!(hash, same_hash);

Fully qualified path: cartesian_merkle_tree::library::utils::CMTUtilsTrait::calculate_merkle_hash

fn calculate_merkle_hash(key: felt252, left_child_mh: felt252, right_child_mh: felt252) -> felt252

get_child_hash

Extracts the Merkle hash from an optional child node.

This helper function safely retrieves the hash from a child node reference, returning 0 for None children (representing empty subtrees).

Arguments

• child - Reference to an optional boxed child node

Returns

The child’s Merkle hash, or 0 if the child is None

Examples

let hash = CMTUtilsTrait::get_child_hash(@Some(child_box));
let zero_hash = CMTUtilsTrait::get_child_hash(@Option::None);
assert_eq!(zero_hash, 0);

Fully qualified path: cartesian_merkle_tree::library::utils::CMTUtilsTrait::get_child_hash

fn get_child_hash(child: @Option<Box<CMTNode>>) -> felt252

right_rotate

Performs a right rotation on the given node to maintain heap property.

Right rotation moves the left child up to become the new root of this subtree, with the original node becoming the right child. This operation maintains both BST ordering and is used to restore heap property when needed.

    X                    Y
   / \    right_rotate  / \
  Y   C   ----------->  A   X
 / \                       / \
 A   B                     B   C

Arguments

• node - The node to rotate (becomes right child after rotation)

Returns

The new root of the subtree (originally the left child)

Panics

Panics if the node has no left child

Examples

let rotated = CMTUtilsTrait::right_rotate(node_box);
// Tree structure is now rotated while preserving BST and heap properties

Fully qualified path: cartesian_merkle_tree::library::utils::CMTUtilsTrait::right_rotate

fn right_rotate(node: Box<CMTNode>) -> Box<CMTNode>

left_rotate

Performs a left rotation on the given node to maintain heap property.

Left rotation moves the right child up to become the new root of this subtree, with the original node becoming the left child. This operation maintains both BST ordering and is used to restore heap property when needed.

  X                        Y
 / \      left_rotate     / \
A   Y     ----------->   X   C
   / \                  / \
  B   C                A   B

Arguments

• node - The node to rotate (becomes left child after rotation)

Returns

The new root of the subtree (originally the right child)

Panics

Panics if the node has no right child

Examples

let rotated = CMTUtilsTrait::left_rotate(node_box);
// Tree structure is now rotated while preserving BST and heap properties

Fully qualified path: cartesian_merkle_tree::library::utils::CMTUtilsTrait::left_rotate

fn left_rotate(node: Box<CMTNode>) -> Box<CMTNode>

Impls

Impls

CMTUtilsImpl

Fully qualified path: cartesian_merkle_tree::library::utils::CMTUtilsImpl

pub impl CMTUtilsImpl of CMTUtilsTrait;

Impl functions

calculate_priority

Calculates a deterministic priority for a given key using Poseidon hashing.

The priority is used to maintain the heap property in the treap structure. Using cryptographic hashing ensures the priorities are effectively randomized while remaining deterministic for the same key.

Arguments

• key - The key to calculate priority for

Returns

A felt252 priority value derived from the key

Examples

let priority1 = CMTUtilsTrait::calculate_priority(42);
let priority2 = CMTUtilsTrait::calculate_priority(42);
assert_eq!(priority1, priority2); // Deterministic

let priority3 = CMTUtilsTrait::calculate_priority(43);
assert!(priority1 != priority3); // Different keys give different priorities

Fully qualified path: cartesian_merkle_tree::library::utils::CMTUtilsImpl::calculate_priority

fn calculate_priority(key: felt252) -> felt252

calculate_merkle_hash

Calculates the Merkle hash for a node given its key and children hashes.

The hash is computed using Poseidon with consistent ordering: the key is hashed first, followed by the children hashes in sorted order (smaller hash first). This ensures deterministic hashing regardless of the tree’s structure.

Arguments

• key - The key of the node
• left_child_mh - Merkle hash of the left child (0 if None)
• right_child_mh - Merkle hash of the right child (0 if None)

Returns

The computed Merkle hash for the node

Examples

let hash = CMTUtilsTrait::calculate_merkle_hash(50, 100, 200);
assert!(hash != 0);

// Hash is independent of child order
let same_hash = CMTUtilsTrait::calculate_merkle_hash(50, 200, 100);
assert_eq!(hash, same_hash);

Fully qualified path: cartesian_merkle_tree::library::utils::CMTUtilsImpl::calculate_merkle_hash

fn calculate_merkle_hash(key: felt252, left_child_mh: felt252, right_child_mh: felt252) -> felt252

get_child_hash

Extracts the Merkle hash from an optional child node.

This helper function safely retrieves the hash from a child node reference, returning 0 for None children (representing empty subtrees).

Arguments

• child - Reference to an optional boxed child node

Returns

The child’s Merkle hash, or 0 if the child is None

Examples

let hash = CMTUtilsTrait::get_child_hash(@Some(child_box));
let zero_hash = CMTUtilsTrait::get_child_hash(@Option::None);
assert_eq!(zero_hash, 0);

Fully qualified path: cartesian_merkle_tree::library::utils::CMTUtilsImpl::get_child_hash

fn get_child_hash(child: @Option<Box<CMTNode>>) -> felt252

right_rotate

Performs a right rotation on the given node to maintain heap property.

Right rotation moves the left child up to become the new root of this subtree, with the original node becoming the right child. This operation maintains both BST ordering and is used to restore heap property when needed.

    X                    Y
   / \    right_rotate  / \
  Y   C   ----------->  A   X
 / \                       / \
 A   B                     B   C

Arguments

• node - The node to rotate (becomes right child after rotation)

Returns

The new root of the subtree (originally the left child)

Panics

Panics if the node has no left child

Examples

let rotated = CMTUtilsTrait::right_rotate(node_box);
// Tree structure is now rotated while preserving BST and heap properties

Fully qualified path: cartesian_merkle_tree::library::utils::CMTUtilsImpl::right_rotate

fn right_rotate(node: Box<CMTNode>) -> Box<CMTNode>

left_rotate

Performs a left rotation on the given node to maintain heap property.

Left rotation moves the right child up to become the new root of this subtree, with the original node becoming the left child. This operation maintains both BST ordering and is used to restore heap property when needed.

  X                        Y
 / \      left_rotate     / \
A   Y     ----------->   X   C
   / \                  / \
  B   C                A   B

Arguments

• node - The node to rotate (becomes left child after rotation)

Returns

The new root of the subtree (originally the right child)

Panics

Panics if the node has no right child

Examples

let rotated = CMTUtilsTrait::left_rotate(node_box);
// Tree structure is now rotated while preserving BST and heap properties

Fully qualified path: cartesian_merkle_tree::library::utils::CMTUtilsImpl::left_rotate

fn left_rotate(node: Box<CMTNode>) -> Box<CMTNode>

components

Fully qualified path: cartesian_merkle_tree::components

Modules

Modules

Modules

cmtree_component

On-chain Cartesian Merkle Tree contract implementation

This contract provides persistent storage for CMT nodes and operations, allowing for on-chain tree manipulation with gas-efficient storage patterns.

Fully qualified path: cartesian_merkle_tree::components::cmtree_component

Modules

Structs

Traits

Groups:

dispatchers

• Structs

• Traits

Modules

Modules

cmtree_component

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component

Modules

Free functions

Structs

Enums

Traits

Modules

Modules

__external_CMTree

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::__external_CMTree

__l1_handler_CMTree

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::__l1_handler_CMTree

__constructor_CMTree

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::__constructor_CMTree

Free functions

Free functions

unsafe_new_component_state

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::unsafe_new_component_state

pub fn unsafe_new_component_state<TContractState>() -> ComponentState<TContractState>

Structs

Structs

Storage

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::Storage

    [storage]
pub struct Storage { /* private fields */ }

ComponentState

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::ComponentState

pub struct ComponentState<TContractState> {}

Enums

Enums

Event

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::Event

pub enum Event {}

Traits

Traits

HasComponent

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::HasComponent

pub trait HasComponent<TContractState>

Trait functions

get_component

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::HasComponent::get_component

fn get_component(self: @TContractState) -> @ComponentState<TContractState>

get_component_mut

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::HasComponent::get_component_mut

fn get_component_mut(ref self: TContractState) -> ComponentState<TContractState>

get_contract

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::HasComponent::get_contract

fn get_contract(self: @ComponentState<TContractState>) -> @TContractState

get_contract_mut

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::HasComponent::get_contract_mut

fn get_contract_mut(ref self: ComponentState<TContractState>) -> TContractState

emit

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::HasComponent::emit

fn emit<
    S,
    impl IntoImp: Into<
        S, cartesian_merkle_tree::components::cmtree_component::cmtree_component::Event,
    >,
>(
    ref self: ComponentState<TContractState>, event: S,
)

InternalFunctionsTrait

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait

pub trait InternalFunctionsTrait<TContractState, +HasComponent<TContractState>>

Trait functions

initializer

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::initializer

fn initializer(ref self: ComponentState<TContractState>)

allocate_node_index

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::allocate_node_index

fn allocate_node_index(ref self: ComponentState<TContractState>) -> u64

free_node_index

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::free_node_index

fn free_node_index(ref self: ComponentState<TContractState>, index: u64)

read_node

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::read_node

fn read_node(self: @ComponentState<TContractState>, index: u64) -> CMTNodeStorage

write_node

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::write_node

fn write_node(ref self: ComponentState<TContractState>, index: u64, node: CMTNodeStorage)

update_node_hash

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::update_node_hash

fn update_node_hash(ref self: ComponentState<TContractState>, index: u64) -> felt252

insert_node

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::insert_node

fn insert_node(
    ref self: ComponentState<TContractState>,
    current_index: u64,
    new_index: u64,
    new_key: felt252,
    new_priority: felt252,
) -> u64

restore_heap_property

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::restore_heap_property

fn restore_heap_property(
    ref self: ComponentState<TContractState>, node_index: u64, check_left: bool,
) -> u64

right_rotate

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::right_rotate

fn right_rotate(ref self: ComponentState<TContractState>, node_index: u64) -> u64

left_rotate

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::left_rotate

fn left_rotate(ref self: ComponentState<TContractState>, node_index: u64) -> u64

search_node

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::search_node

fn search_node(self: @ComponentState<TContractState>, node_index: u64, key: felt252) -> bool

remove_node

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::remove_node

fn remove_node(
    ref self: ComponentState<TContractState>, node_index: u64, key: felt252,
) -> (u64, bool)

rotate_to_leaf_and_remove

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::rotate_to_leaf_and_remove

fn rotate_to_leaf_and_remove(
    ref self: ComponentState<TContractState>, node_index: u64, key: felt252,
) -> u64

generate_proof_internal

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::InternalFunctionsTrait::generate_proof_internal

fn generate_proof_internal(
    self: @ComponentState<TContractState>,
    node_index: u64,
    key: felt252,
    ref siblings: Array<felt252>,
    ref direction_bits: felt252,
    ref siblings_count: u32,
) -> (bool, felt252)

UnsafeNewContractStateTraitForCMTree

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::UnsafeNewContractStateTraitForCMTree

pub trait UnsafeNewContractStateTraitForCMTree<TContractState>

Trait functions

unsafe_new_contract_state

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::cmtree_component::UnsafeNewContractStateTraitForCMTree::unsafe_new_contract_state

fn unsafe_new_contract_state() -> TContractState

__external_ICMTreeForwardImpl

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::__external_ICMTreeForwardImpl

__l1_handler_ICMTreeForwardImpl

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::__l1_handler_ICMTreeForwardImpl

__constructor_ICMTreeForwardImpl

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::__constructor_ICMTreeForwardImpl

Structs

Structs

CMTNodeStorage

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::CMTNodeStorage

[derive(Drop, Copy, Debug, Serde, starknet::Store)]
pub struct CMTNodeStorage {
    pub key: felt252,
    pub priority: felt252,
    pub merkle_hash: felt252,
    pub left_child_index: u64,
    pub right_child_index: u64,
}

Members

key

The key value for BST ordering and identification

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::CMTNodeStorage::key

pub key: felt252

priority

Randomized priority for heap property (derived from key)

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::CMTNodeStorage::priority

pub priority: felt252

merkle_hash

Merkle hash commitment to this node and its children

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::CMTNodeStorage::merkle_hash

pub merkle_hash: felt252

left_child_index

Storage index of the left child node (0 = no child)

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::CMTNodeStorage::left_child_index

pub left_child_index: u64

right_child_index

Storage index of the right child node (0 = no child)

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::CMTNodeStorage::right_child_index

pub right_child_index: u64

ProofData

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ProofData

[derive(Drop, Clone, Debug, Serde)]
pub struct ProofData {
    pub root: felt252,
    pub siblings: Array<felt252>,
    pub siblings_length: u32,
    pub direction_bits: felt252,
    pub existence: bool,
    pub key: felt252,
    pub non_existence_key: felt252,
}

Members

root

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ProofData::root

pub root: felt252

siblings

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ProofData::siblings

pub siblings: Array<felt252>

siblings_length

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ProofData::siblings_length

pub siblings_length: u32

direction_bits

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ProofData::direction_bits

pub direction_bits: felt252

existence

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ProofData::existence

pub existence: bool

key

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ProofData::key

pub key: felt252

non_existence_key

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ProofData::non_existence_key

pub non_existence_key: felt252

Traits

Traits

ICMTree

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTree

pub trait ICMTree<TContractState>

Trait functions

insert

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTree::insert

fn insert(ref self: TContractState, key: felt252)

remove

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTree::remove

fn remove(ref self: TContractState, key: felt252) -> bool

search

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTree::search

fn search(self: @TContractState, key: felt252) -> bool

get_root_hash

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTree::get_root_hash

fn get_root_hash(self: @TContractState) -> felt252

generate_proof

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTree::generate_proof

fn generate_proof(self: @TContractState, key: felt252) -> ProofData

verify_proof

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTree::verify_proof

fn verify_proof(self: @TContractState, proof: ProofData, root_hash: felt252, key: felt252) -> bool

UnsafeNewContractStateTraitForICMTreeForwardImpl

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::UnsafeNewContractStateTraitForICMTreeForwardImpl

pub trait UnsafeNewContractStateTraitForICMTreeForwardImpl<TContractState>

Trait functions

unsafe_new_contract_state

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::UnsafeNewContractStateTraitForICMTreeForwardImpl::unsafe_new_contract_state

fn unsafe_new_contract_state() -> TContractState

dispatchers

• Structs

• Traits

Structs

Structs

ICMTreeDispatcher

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeDispatcher

Part of the group: dispatchers

[doc(group: "dispatchers")]
[derive(Copy, Drop, starknet::Store, Serde)]
pub struct ICMTreeDispatcher {
    pub contract_address: ContractAddress,
}

Members

contract_address

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeDispatcher::contract_address

pub contract_address: ContractAddress

ICMTreeLibraryDispatcher

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeLibraryDispatcher

Part of the group: dispatchers

[doc(group: "dispatchers")]
[derive(Copy, Drop, starknet::Store, Serde)]
pub struct ICMTreeLibraryDispatcher {
    pub class_hash: ClassHash,
}

Members

class_hash

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeLibraryDispatcher::class_hash

pub class_hash: ClassHash

ICMTreeSafeLibraryDispatcher

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeSafeLibraryDispatcher

Part of the group: dispatchers

[doc(group: "dispatchers")]
[derive(Copy, Drop, starknet::Store, Serde)]
pub struct ICMTreeSafeLibraryDispatcher {
    pub class_hash: ClassHash,
}

Members

class_hash

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeSafeLibraryDispatcher::class_hash

pub class_hash: ClassHash

ICMTreeSafeDispatcher

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeSafeDispatcher

Part of the group: dispatchers

[doc(group: "dispatchers")]
[derive(Copy, Drop, starknet::Store, Serde)]
pub struct ICMTreeSafeDispatcher {
    pub contract_address: ContractAddress,
}

Members

contract_address

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeSafeDispatcher::contract_address

pub contract_address: ContractAddress

Traits

Traits

ICMTreeDispatcherTrait

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeDispatcherTrait

Part of the group: dispatchers

pub trait ICMTreeDispatcherTrait<T>

Trait functions

insert

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeDispatcherTrait::insert

fn insert(self: T, key: felt252)

remove

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeDispatcherTrait::remove

fn remove(self: T, key: felt252) -> bool

search

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeDispatcherTrait::search

fn search(self: T, key: felt252) -> bool

get_root_hash

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeDispatcherTrait::get_root_hash

fn get_root_hash(self: T) -> felt252

generate_proof

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeDispatcherTrait::generate_proof

fn generate_proof(self: T, key: felt252) -> ProofData

verify_proof

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeDispatcherTrait::verify_proof

fn verify_proof(self: T, proof: ProofData, root_hash: felt252, key: felt252) -> bool

ICMTreeSafeDispatcherTrait

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeSafeDispatcherTrait

Part of the group: dispatchers

pub trait ICMTreeSafeDispatcherTrait<T>

Trait functions

insert

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeSafeDispatcherTrait::insert

fn insert(self: T, key: felt252) -> Result<(), Array<felt252>>

remove

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeSafeDispatcherTrait::remove

fn remove(self: T, key: felt252) -> Result<bool, Array<felt252>>

search

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeSafeDispatcherTrait::search

fn search(self: T, key: felt252) -> Result<bool, Array<felt252>>

get_root_hash

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeSafeDispatcherTrait::get_root_hash

fn get_root_hash(self: T) -> Result<felt252, Array<felt252>>

generate_proof

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeSafeDispatcherTrait::generate_proof

fn generate_proof(self: T, key: felt252) -> Result<ProofData, Array<felt252>>

verify_proof

Fully qualified path: cartesian_merkle_tree::components::cmtree_component::ICMTreeSafeDispatcherTrait::verify_proof

fn verify_proof(
    self: T, proof: ProofData, root_hash: felt252, key: felt252,
) -> Result<bool, Array<felt252>>