Skip to main content

CartesianMerkleTree

Overview​

License: MIT​

library CartesianMerkleTree

Cartesian Merkle Tree Module

A magnificent ZK-friendly data structure based on a Binary Search Tree + Heap + Merkle Tree. Short names: CMT, Treaple. Possesses deterministic and idempotent properties. Can be used as a substitute for a Sparse Merkle Tree (SMT).

Gas usage for adding and removing 1,000 elements to a CMT with the keccak256 and poseidon hash functions is detailed below:

Keccak256:

  • CMT.add - 249k
  • CMT.remove - 181k

Poseidon:

  • CMT.add - 896k
  • CMT.remove - 746k

Usage Example:​

using CartesianMerkleTree for CartesianMerkleTree.UintCMT;

CartesianMerkleTree.UintCMT internal uintTreaple;
...
uintTreaple.initialize(80);

uintTreaple.add(100);

uintTreaple.getRoot();

CartesianMerkleTree.Proof memory proof = uintTreaple.getProof(100, 0);

uintTreaple.verifyProof(proof);

uintTreaple.getNodeByKey(100);

uintTreaple.remove(100);

Structs info​

UintCMT​

struct UintCMT {
    CartesianMerkleTree.CMT _treaple;
}

UintCMT *

Bytes32CMT​

struct Bytes32CMT {
    CartesianMerkleTree.CMT _treaple;
}

Bytes32CMT *

AddressCMT​

struct AddressCMT {
    CartesianMerkleTree.CMT _treaple;
}

AddressCMT *

CMT​

struct CMT {
    mapping(uint64 => CartesianMerkleTree.Node) nodes;
    uint64 merkleRootId;
    uint64 nodesCount;
    uint64 deletedNodesCount;
    uint32 desiredProofSize;
    bool isCustomHasherSet;
    function (bytes32,bytes32,bytes32) view returns (bytes32) hash3;
}

Defines the structure of the Cartesian Merkle Tree.

Parameters:

NameTypeDescription
nodesmapping(uint64 => struct CartesianMerkleTree.Node)A mapping of the treaple's nodes, where the key is the node's index, starting from 1 upon node addition.
merkleRootIduint64The index of the root node.
nodesCountuint64The total number of nodes within the Cartesian Merkle Tree.
deletedNodesCountuint64The total number of the deleted nodes within the Cartesian Merkle Tree.
desiredProofSizeuint32The desired proof size of the CMT proofs.
isCustomHasherSetboolIndicates whether custom hash function has been configured (true) or not (false).
hash3function (bytes32,bytes32,bytes32) view returns (bytes32)A hash function accepting three arguments.

Node​

struct Node {
    uint64 childLeft;
    uint64 childRight;
    bytes16 priority;
    bytes32 merkleHash;
    bytes32 key;
}

Describes a node within the Cartesian Merkle tree, including its children, hash, priority and key.

Parameters:

NameTypeDescription
childLeftuint64The index of the left child node.
childRightuint64The index of the right child node.
prioritybytes16The priority of the node that counts as keccak256(key)
merkleHashbytes32The hash of the node, calculated as follows: - H(k |
keybytes32The key associated with the node.

Proof​

struct Proof {
    bytes32 root;
    bytes32[] siblings;
    uint256 siblingsLength;
    uint256 directionBits;
    bool existence;
    bytes32 key;
    bytes32 nonExistenceKey;
}

Represents the proof of a node's (non-)existence within the Cartesian Merkle tree.

Parameters:

NameTypeDescription
rootbytes32The root hash of the Cartesian Merkle tree.
siblingsbytes32[]An array of sibling hashes can be used to get the Cartesian Merkle Root.
siblingsLengthuint256The number of siblings to be used for evidence.
directionBitsuint256A path from the root to the node.
existenceboolIndicates the presence (true) or absence (false) of the node.
keybytes32The key associated with the node.
nonExistenceKeybytes32The non-existence key of the auxiliary node in case when existence is false.

Errors info​

TreapleNotInitialized​

error TreapleNotInitialized()

TreapleAlreadyInitialized​

error TreapleAlreadyInitialized()

TreapleNotEmpty​

error TreapleNotEmpty()

ZeroDesiredProofSize​

error ZeroDesiredProofSize()

ProofSizeTooSmall​

error ProofSizeTooSmall(uint256 attemptedIndex, uint256 maxIndex)

ZeroKeyProvided​

error ZeroKeyProvided()

KeyAlreadyExists​

error KeyAlreadyExists()

NodeDoesNotExist​

error NodeDoesNotExist()

Modifiers info​

onlyInitialized​

modifier onlyInitialized(CartesianMerkleTree.CMT storage treaple)

Functions info​

initialize​

function initialize(
    CartesianMerkleTree.UintCMT storage treaple,
    uint32 desiredProofSize_
) internal

The function to initialize the Cartesian Merkle tree. Under the hood it sets the desired proof size of the CMT proofs, therefore can be considered alias function for the setDesiredProofSize.

Requirements:

  • The desired proof size value must be greater than 0.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.UintCMTself.
desiredProofSize_uint32The desired proof size of the CMT proofs.

setHasher​

function setHasher(
    CartesianMerkleTree.UintCMT storage treaple,
    function(bytes32, bytes32, bytes32) view returns (bytes32) hash3_
) internal

The function to set a custom hash function, that will be used to build the Cartesian Merkle Tree.

Requirements:

  • The tree must be empty.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.UintCMTself.
hash3_function (bytes32,bytes32,bytes32) view returns (bytes32)The hash function that accepts three arguments.

setDesiredProofSize​

function setDesiredProofSize(
    CartesianMerkleTree.UintCMT storage treaple,
    uint32 desiredProofSize_
) internal

The function to set a desired proof size, that will be used to build the Cartesian Merkle Tree proofs.

Requirements:

  • The desired proof size value must be greater than 0.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.UintCMTself.
desiredProofSize_uint32The desired proof size of the CMT proofs.

add​

function add(
    CartesianMerkleTree.UintCMT storage treaple,
    uint256 key_
) internal

The function to add a new element to the uint256 treaple. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.UintCMTself.
key_uint256The key of the element.

remove​

function remove(
    CartesianMerkleTree.UintCMT storage treaple,
    uint256 key_
) internal

The function to remove an element from the uint256 treaple. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.UintCMTself.
key_uint256The key of the element.

getProof​

function getProof(
    CartesianMerkleTree.UintCMT storage treaple,
    uint256 key_,
    uint32 desiredProofSize_
) internal view returns (CartesianMerkleTree.Proof memory)

The function to get the proof if a node with specific key exists or not exists in the CMT. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.UintCMTself.
key_uint256The key of the element.
desiredProofSize_uint32The desired siblings length in the proof.

Return values:

NameTypeDescription
[0]struct CartesianMerkleTree.ProofCMT proof struct.

verifyProof​

function verifyProof(
    CartesianMerkleTree.UintCMT storage treaple,
    CartesianMerkleTree.Proof memory proof_
) internal view returns (bool)

The function to verify the proof for inclusion or exclusion of a node in the CMT. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.UintCMTself.
proof_struct CartesianMerkleTree.ProofThe CMT proof struct.

Return values:

NameTypeDescription
[0]boolTrue if the proof is valid, false otherwise.

getRoot​

function getRoot(
    CartesianMerkleTree.UintCMT storage treaple
) internal view returns (bytes32)

The function to get the root of the Cartesian Merkle Tree. Complexity is O(1).

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.UintCMTself.

Return values:

NameTypeDescription
[0]bytes32The root of the Cartesian Merkle Tree.

getNode​

function getNode(
    CartesianMerkleTree.UintCMT storage treaple,
    uint256 nodeId_
) internal view returns (CartesianMerkleTree.Node memory)

The function to get the node by its index. Complexity is O(1).

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.UintCMTself.
nodeId_uint256The index of the node.

Return values:

NameTypeDescription
[0]struct CartesianMerkleTree.NodeThe node.

getNodeByKey​

function getNodeByKey(
    CartesianMerkleTree.UintCMT storage treaple,
    uint256 key_
) internal view returns (CartesianMerkleTree.Node memory)

The function to get the node by its key. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.UintCMTself.
key_uint256The key of the element.

Return values:

NameTypeDescription
[0]struct CartesianMerkleTree.NodeThe node.

getDesiredProofSize​

function getDesiredProofSize(
    CartesianMerkleTree.UintCMT storage treaple
) internal view returns (uint256)

The function to get the desired proof size value.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.UintCMTself.

Return values:

NameTypeDescription
[0]uint256The desired proof size value.

getNodesCount​

function getNodesCount(
    CartesianMerkleTree.UintCMT storage treaple
) internal view returns (uint64)

The function to get the number of nodes in the Cartesian Merkle Tree.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.UintCMTself.

Return values:

NameTypeDescription
[0]uint64The number of nodes in the Cartesian Merkle Tree.

isCustomHasherSet​

function isCustomHasherSet(
    CartesianMerkleTree.UintCMT storage treaple
) internal view returns (bool)

The function to check if custom hash function is set.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.UintCMTself.

Return values:

NameTypeDescription
[0]boolTrue if custom hash function is set, otherwise false.

initialize​

function initialize(
    CartesianMerkleTree.Bytes32CMT storage treaple,
    uint32 desiredProofSize_
) internal

The function to initialize the Cartesian Merkle tree. Under the hood it sets the desired proof size of the CMT proofs, therefore can be considered alias function for the setDesiredProofSize.

Requirements:

  • The desired proof size value must be greater than 0.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.Bytes32CMTself.
desiredProofSize_uint32The desired proof size of the CMT proofs.

setHasher​

function setHasher(
    CartesianMerkleTree.Bytes32CMT storage treaple,
    function(bytes32, bytes32, bytes32) view returns (bytes32) hash3_
) internal

The function to set a custom hash function, that will be used to build the Cartesian Merkle Tree.

Requirements:

  • The tree must be empty.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.Bytes32CMTself.
hash3_function (bytes32,bytes32,bytes32) view returns (bytes32)The hash function that accepts three arguments.

setDesiredProofSize​

function setDesiredProofSize(
    CartesianMerkleTree.Bytes32CMT storage treaple,
    uint32 desiredProofSize_
) internal

The function to set a desired proof size, that will be used to build the Cartesian Merkle Tree proofs.

Requirements:

  • The desired proof size value must be greater than 0.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.Bytes32CMTself.
desiredProofSize_uint32The desired proof size of the CMT proofs.

add​

function add(
    CartesianMerkleTree.Bytes32CMT storage treaple,
    bytes32 key_
) internal

The function to add a new element to the bytes32 treaple. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.Bytes32CMTself.
key_bytes32The key of the element.

remove​

function remove(
    CartesianMerkleTree.Bytes32CMT storage treaple,
    bytes32 key_
) internal

The function to remove an element from the bytes32 treaple. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.Bytes32CMTself.
key_bytes32The key of the element.

getProof​

function getProof(
    CartesianMerkleTree.Bytes32CMT storage treaple,
    bytes32 key_,
    uint32 desiredProofSize_
) internal view returns (CartesianMerkleTree.Proof memory)

The function to get the proof if a node with specific key exists or not exists in the CMT. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.Bytes32CMTself.
key_bytes32The key of the element.
desiredProofSize_uint32The desired siblings length in the proof.

Return values:

NameTypeDescription
[0]struct CartesianMerkleTree.ProofCMT proof struct.

verifyProof​

function verifyProof(
    CartesianMerkleTree.Bytes32CMT storage treaple,
    CartesianMerkleTree.Proof memory proof_
) internal view returns (bool)

The function to verify the proof for inclusion or exclusion of a node in the CMT. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.Bytes32CMTself.
proof_struct CartesianMerkleTree.ProofThe CMT proof struct.

Return values:

NameTypeDescription
[0]boolTrue if the proof is valid, false otherwise.

processProof​

function processProof(
    function(bytes32, bytes32, bytes32) view returns (bytes32) hash3_,
    CartesianMerkleTree.Proof memory proof_
) internal view returns (bytes32)

The function to process the proof for inclusion or exclusion of a node in the CMT. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
hash3_function (bytes32,bytes32,bytes32) view returns (bytes32)The hash function that accepts three arguments.
proof_struct CartesianMerkleTree.ProofThe CMT proof struct.

Return values:

NameTypeDescription
[0]bytes32The calculated root hash from the proof.

getRoot​

function getRoot(
    CartesianMerkleTree.Bytes32CMT storage treaple
) internal view returns (bytes32)

The function to get the root of the Cartesian Merkle Tree. Complexity is O(1).

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.Bytes32CMTself.

Return values:

NameTypeDescription
[0]bytes32The root of the Cartesian Merkle Tree.

getNode​

function getNode(
    CartesianMerkleTree.Bytes32CMT storage treaple,
    uint256 nodeId_
) internal view returns (CartesianMerkleTree.Node memory)

The function to get the node by its index. Complexity is O(1).

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.Bytes32CMTself.
nodeId_uint256The index of the node.

Return values:

NameTypeDescription
[0]struct CartesianMerkleTree.NodeThe node.

getNodeByKey​

function getNodeByKey(
    CartesianMerkleTree.Bytes32CMT storage treaple,
    bytes32 key_
) internal view returns (CartesianMerkleTree.Node memory)

The function to get the node by its key. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.Bytes32CMTself.
key_bytes32The key of the element.

Return values:

NameTypeDescription
[0]struct CartesianMerkleTree.NodeThe node.

getDesiredProofSize​

function getDesiredProofSize(
    CartesianMerkleTree.Bytes32CMT storage treaple
) internal view returns (uint256)

The function to get the desired proof size value.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.Bytes32CMTself.

Return values:

NameTypeDescription
[0]uint256The desired proof size value.

getNodesCount​

function getNodesCount(
    CartesianMerkleTree.Bytes32CMT storage treaple
) internal view returns (uint64)

The function to get the number of nodes in the Cartesian Merkle Tree.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.Bytes32CMTself.

Return values:

NameTypeDescription
[0]uint64The number of nodes in the Cartesian Merkle Tree.

isCustomHasherSet​

function isCustomHasherSet(
    CartesianMerkleTree.Bytes32CMT storage treaple
) internal view returns (bool)

The function to check if custom hash function is set.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.Bytes32CMTself.

Return values:

NameTypeDescription
[0]boolTrue if custom hash function is set, otherwise false.

initialize​

function initialize(
    CartesianMerkleTree.AddressCMT storage treaple,
    uint32 desiredProofSize_
) internal

The function to initialize the Cartesian Merkle tree. Under the hood it sets the desired proof size of the CMT proofs, therefore can be considered alias function for the setDesiredProofSize.

Requirements:

  • The desired proof size value must be greater than 0.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.AddressCMTself.
desiredProofSize_uint32The desired proof size of the CMT proofs.

setHasher​

function setHasher(
    CartesianMerkleTree.AddressCMT storage treaple,
    function(bytes32, bytes32, bytes32) view returns (bytes32) hash3_
) internal

The function to set a custom hash function, that will be used to build the Cartesian Merkle Tree.

Requirements:

  • The tree must be empty.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.AddressCMTself.
hash3_function (bytes32,bytes32,bytes32) view returns (bytes32)The hash function that accepts three arguments.

setDesiredProofSize​

function setDesiredProofSize(
    CartesianMerkleTree.AddressCMT storage treaple,
    uint32 desiredProofSize_
) internal

The function to set a desired proof size, that will be used to build the Cartesian Merkle Tree proofs.

Requirements:

  • The desired proof size value must be greater than 0.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.AddressCMTself.
desiredProofSize_uint32The desired proof size of the CMT proofs.

add​

function add(
    CartesianMerkleTree.AddressCMT storage treaple,
    address key_
) internal

The function to add a new element to the address treaple. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.AddressCMTself.
key_addressThe key of the element.

remove​

function remove(
    CartesianMerkleTree.AddressCMT storage treaple,
    address key_
) internal

The function to remove an element from the address treaple. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.AddressCMTself.
key_addressThe key of the element.

getProof​

function getProof(
    CartesianMerkleTree.AddressCMT storage treaple,
    address key_,
    uint32 desiredProofSize_
) internal view returns (CartesianMerkleTree.Proof memory)

The function to get the proof if a node with specific key exists or not exists in the CMT. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.AddressCMTself.
key_addressThe key of the element.
desiredProofSize_uint32The desired siblings length in the proof.

Return values:

NameTypeDescription
[0]struct CartesianMerkleTree.ProofCMT proof struct.

verifyProof​

function verifyProof(
    CartesianMerkleTree.AddressCMT storage treaple,
    CartesianMerkleTree.Proof memory proof_
) internal view returns (bool)

The function to verify the proof for inclusion or exclusion of a node in the CMT. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.AddressCMTself.
proof_struct CartesianMerkleTree.ProofThe CMT proof struct.

Return values:

NameTypeDescription
[0]boolTrue if the proof is valid, false otherwise.

getRoot​

function getRoot(
    CartesianMerkleTree.AddressCMT storage treaple
) internal view returns (bytes32)

The function to get the root of the Cartesian Merkle Tree. Complexity is O(1).

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.AddressCMTself.

Return values:

NameTypeDescription
[0]bytes32The root of the Cartesian Merkle Tree.

getNode​

function getNode(
    CartesianMerkleTree.AddressCMT storage treaple,
    uint256 nodeId_
) internal view returns (CartesianMerkleTree.Node memory)

The function to get the node by its index. Complexity is O(1).

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.AddressCMTself.
nodeId_uint256The index of the node.

Return values:

NameTypeDescription
[0]struct CartesianMerkleTree.NodeThe node.

getNodeByKey​

function getNodeByKey(
    CartesianMerkleTree.AddressCMT storage treaple,
    address key_
) internal view returns (CartesianMerkleTree.Node memory)

The function to get the node by its key. Complexity is O(log(n)), where n is the max depth of the treaple.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.AddressCMTself.
key_addressThe key of the element.

Return values:

NameTypeDescription
[0]struct CartesianMerkleTree.NodeThe node.

getDesiredProofSize​

function getDesiredProofSize(
    CartesianMerkleTree.AddressCMT storage treaple
) internal view returns (uint256)

The function to get the desired proof size value.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.AddressCMTself.

Return values:

NameTypeDescription
[0]uint256The desired proof size value.

getNodesCount​

function getNodesCount(
    CartesianMerkleTree.AddressCMT storage treaple
) internal view returns (uint64)

The function to get the number of nodes in the Cartesian Merkle Tree.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.AddressCMTself.

Return values:

NameTypeDescription
[0]uint64The number of nodes in the Cartesian Merkle Tree.

isCustomHasherSet​

function isCustomHasherSet(
    CartesianMerkleTree.AddressCMT storage treaple
) internal view returns (bool)

The function to check if custom hash function is set.

Parameters:

NameTypeDescription
treaplestruct CartesianMerkleTree.AddressCMTself.

Return values:

NameTypeDescription
[0]boolTrue if custom hash function is set, otherwise false.