Cartesian Merkle Tree

Artem Chystiakov, Oleh Komendant, Kyrylo Riabov · 2025

Read Cartesian Merkle Tree by Artem Chystiakov, Oleh Komendant, Kyrylo Riabov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-10944.txt.

Introduction

Artem Chystiakov, Oleh Komendant, and Kyrylo Riabov introduce the Cartesian Merkle Tree in a 2025 paper. The structure blends three known forms, a binary search tree for ordering, a heap for priority, and a Merkle tree for hash based proof. It is deterministic, so the same data always builds the same tree, which aids verification across parties.

Insertions, updates, and removals each run in logarithmic time, and storage grows in line with the number of elements. Membership and non membership can both be proved through Merkle authentication paths. The authors pitch the structure for zero knowledge systems, blockchains, and other protocols that need efficient, verifiable data handling.

Catalog record

CREATORArtem Chystiakov, Oleh Komendant, Kyrylo Riabov
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-10944

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Cartesian Merkle Tree Artem Chystiakov, Oleh Komendant, Kyrylo Riabov Abstract This paper introduces the Cartesian Merkle Tree, a deterministic data structure that combines the properties of a Binary Search Tree, a Heap, and a Merkle tree. The Cartesian Merkle Tree supports insertions, updates, and removals of elements in O ⁡ ( log ⁡ n ) O(\log n) time, requires n n space, and enables membership and non-membership proofs via Merkle-based authentication paths. This structure is particularly suitable for zero-knowledge applications, blockchain systems, and other protocols that require efficient and verifiable data structures. 1 Introduction Cartesian Merkle Tree (CMT) research is motivated by the increasing demand for efficient and secure data structures in cryptographic, blockchain, and zero-knowledge (ZK) systems. Traditional Merkle trees, such as Sparse Merkle Trees (SMT) [ ide24 ] , are widely used but have limitations in terms of balance and efficiency. CMTs integrate binary search tree properties for key-based organization and heap properties for priority balancing, data storage optimization, elements retrieval, and proof generation. To ensure determinism, the priority value for an element is derived from its key using a predefined algorithm, such as a hash function. CMTs offer an efficient alternative to SMTs, reducing memory usage while preserving the key properties of the latter. One of the key features of CMT is that it stores useful data in every node, unlike SMTs which only store it in the leaves. The time complexity of the operations is still O(\log n) , with the only trade-off being a Merkle proof size at worst two times larger than SMTs. 2 Background Merkle trees are fundamental to many cryptographic protocols, enabling efficient and secure proofs of data inclusion. They are widely used across various systems, ranging from maintaining validator sets in Ethereum to storing the state of zero-knowledge layer-2 rollups. The primary strength of Merkle trees lies in their ability to prove the inclusion of data in a highly compact and efficient manner. Although the standard Merkle tree structure is binary, there are variations, such as the Merkle-Patricia tree, which utilizes sixteen child nodes per branch, optimizing performance in specific contexts. Despite these advances, Merkle trees still face challenges related to storage and operational complexity. Typically, they require O(\log n) operations and 2n storage for binary trees. While vanilla Merkle trees are often impractical for on-chain usage, they are still frequently utilized in off-chain whitelists and similar applications. However, two significant Merkle tree modifications have emerged that unlock the full potential of the data structure: Incremental Merkle Trees (IMT) and Sparse Merkle Trees (SMT). 2.1 Incremental Merkle Tree IMT is a push-only data structure that can be used on-chain to build the tree, but requires an off-chain service to generate inclusion proofs. IMT is currently used by TornadoCash for anonymizing depositors, by Semaphore to store group membership commitments, and by the BeaconChain deposit smart contract to manage the list of Ethereum validators. Unlike standard Merkle trees, IMTs do not store individual elements. Instead, they are merely used to “build” the root. IMTs require \log n storage, with inclusion proofs also having O(\log n) complexity. Importantly, IMTs cannot be used independently without an off-chain service, as the entire tree must be reconstructed to generate an inclusion proof. 2.2 Sparse Merkle Tree Until recently, SMTs were regarded as one of the most efficient data structures, particularly in the context of blockchain technologies and ZK systems. For instance, SMT is used by Scroll to maintain its ZK rollup state, by Rarimo to store ZK-provable national passport-based identity data, and by iden3 to manage custom-issued on-chain identities. SMT is a particularly fascinating data structure. Unlike IMT, SMT does not require any off-chain services. It is deterministic, meaning the structure of the tree remains identical for a given set of elements, regardless of their insertion order. The position of an element in the tree is determined by its bitwise prefix: if a 0 is encountered, the left child is selected; if a 1 is encountered, the right child is chosen. This results in the tree size being constrained by the bitwise length of this prefix. However, reaching depths of 97 or more is currently infeasible due to limitations within the EVM stack. In practice, the size of the tree without collisions cannot exceed 2^{50} , or approximately 1.12\times 10^{15} (one quadrillion) elements, according to the Birthday Problem [ Wik25 ] . 3 Data Structure Description A Cartesian Merkle Tree can be seen as a standard Cartesian tree or Treap with the additional data Merkleization property. Each element in CMT corresponds to a point on a two-dimensional plane, with the key k representing the X-coordinate and the priority p representing the Y-coordinate. In traditional Cartesian trees [ Wik25a ] , the value of p is typically chosen at random, which contributes to a more balanced tree structure. However, if p is deterministically derived from k , then the same key will always produce the same point on the plane. As a result, the structure of the CMT becomes deterministic. Let \texttt{e}=\texttt{k} be a new entry in the tree T , where k is the key of the entry. The entry e may also optionally have a field v , the value. The node where this data element e is stored is determined based on the information contained in e . Let H be a cryptographically secure hash function that returns the hash result for an arbitrary number of values. Let \texttt{p}=P_{H}({\texttt{e}}) be the priority of the element e , where P_{H} can be any deterministic algorithm that transforms the values of e into a number. Let \texttt{node}=(\texttt{k},\texttt{p},\texttt{mh}) be any node in the tree T , where mh is the Merkle Hash value of the node, calculated as follows: mh=H(\texttt{entry}\parallel\texttt{leftChildMH}\parallel\texttt{rightChildMH}) Here, leftChildMH and rightChildMH are the Merkle hash values of the node’s children, sorted in ascending order, and entry is the node’s useful payload. If a child is absent, its hash value is considered to be 0 . The node where e should be stored is determined by the following rules: \texttt{leftChild.k}\leq\texttt{e.k}\leq\texttt{rightChild.k} \texttt{leftChild.p}\leq\texttt{e.p}\hskip 10.00002pt\text{and}\hskip 10.00002pt\texttt{rightChild.p}\leq\texttt{e.p} The first rule ensures the binary search tree property, while the second rule maintains the min-heap property. k: 15 p: 200 mh: (15,2.mh,4.mh) k: 10 p: 100 mh: (10,0,1.mh) k: 20 p: 90 mh: (20,0,5.mh) k: 5 p: 50 mh: (5,0,0) k: 0 p: 0 mh: 0 k: 0 p: 0 mh: 0 k: 0 p: 0 mh: 0 k: 18 p: 70 mh: (18,0,0) k: 0 p: 0 mh: 0 k: 0 p: 0 mh: 0 k: 0 p: 0 mh: 0 1. 3. 2. 4. 5. k \xrightarrow{} BST p \xrightarrow{} Heap mh \xrightarrow{} Merkle Tree Figure 1: Example of CMT Function CalculateMH( key , leftChildMH , rightChildMH ) : /* Sort leftChildMH, rightChildMH in ascending order */ if \texttt{leftChildMH}<\texttt{rightChildMH} then return H( \texttt{key}||\texttt{leftChildMH}||\texttt{rightChildMH} ) ; else return H( \texttt{key}||\texttt{rightChildMH}||\texttt{leftChildMH} ) ; Function RightRotate( node ) : /* Save pointers to the left child and its right child */ currentLeftChild \leftarrow node.leftChild ; newLeftChild \leftarrow currentLeftChild.rightChild ; /* Perform the right rotation by updating the pointers */ currentLeftChild.rightChild \leftarrow node ; node.leftChild \leftarrow newLeftChild ; /* Update the mh value of the node after rotation */ node.mh \leftarrow CalculateMH( node.e.k ,

Read the complete text