5P;1R Jellyfish Merkle Tree
This is a post in a series of articles I’m writing called “5 points & 1 resource” (think tl;dr but 5p;1r), where I summarize a list of 5 concepts that would have helped me start learning or re-learning a certain topic. It is intentionally far from a complete source of data.
- An Addressable Merkle Tree (AMT) is a cryptographically authenticated deterministic data structure backed by a key-value store database used for account-based (non-UTXO-based) systems to map keys (i.e. addresses) to arbitrary binary data in each leaf node.
- An Addressable Radix Merkle Tree (ARᵣMT) [Fig. 3] is a generalization of an AMT, a binary tree, where r > 2. With a key size of h bits, and each node having at most r children, the height of the tree is logᵣ(2ʰ). The tradeoffs of r are:
- A large r is good for read-heavy applications but results in greater write amplification and higher storage costs when updating internal path nodes.
- A small r is good for write-heavy applications, but results in higher I/O when querying or updating the tree.
3. A Sparse Merkle Tree (SMT) [Fig. 2] is an AMT which accounts for the fact that Perfect Merkle Trees are never needed for account-based models since most keys will not have data, thereby removing the need to store 2ʰ keys. The two main optimizations are:
- Empty Subtrees are replaced with a constant default placeholder node value.
- Single-Leaf Subtrees are replaced with one node reflecting the one leaf value.
4. A Jellyfish Merkle Tree (JMT) is a Sparse Addressable Radix Merkle Tree with r=16 (Sparse AR₁₆MT) that balances the tradeoff of storage, compute, read and write operations using two node types: Internal Node and Leaf (Data) Node. It optimizes for Log-Structured Merge-tree (LSM-tree) based key-value storage databases (e.g. RocksDB) by using Version-Based Node Keys whereby a monotonically increasing version number (i.e. # of transaction applied to the state) is prefixed to the node path in order to [Table 1]:
- Enable version-based sharding
- Automatically sort node updates written (i.e. appended) to disk in lexicographic order, reducing the disk bandwidth and IOPS of LSM-tree compaction.
5. A JMT has an average Merkle Proof size of Θ(𝑙𝑜𝑔(num_existent_leaves)) and is split into three types [Fig. 4,5]:
- Inclusion proof — A path to the node leaf with the appropriate key exists.
- Exclusion proof (other node) — The leaf node in the path followed contains a key different from what’s expected.
- Exclusion proof (empty node) — An empty (i.e. default placeholder) node exists along the path to the leaf node with the expected key.
There’s no better reference than the original white paper: Jellyfish Merkle Tree, but personally, I’d use my annotated version of the available at bafybeid5cdhsbqskrwwn5m2q7md5g2ldt6hihvzrt26ty6jbxqnza4gaie or s3.olshansky.info/JellyfishMerkleTreeWhitepaperReview.pdf.
