Crate jmt

Expand description

This module implements JellyfishMerkleTree backed by storage module. The tree itself doesn’t persist anything, but realizes the logic of R/W only. The write path will produce all the intermediate results in a batch for storage layer to commit and the read path will return results directly. The public APIs are only new, put_value_sets, put_value_set and get_with_proof. After each put with a value_set based on a known version, the tree will return a new root hash with a TreeUpdateBatch containing all the new nodes and indices of stale nodes.

A Jellyfish Merkle Tree itself logically is a 256-bit sparse Merkle tree with an optimization that any subtree containing 0 or 1 leaf node will be replaced by that leaf node or a placeholder node with default hash value. With this optimization we can save CPU by avoiding hashing on many sparse levels in the tree. Physically, the tree is structurally similar to the modified Patricia Merkle tree of Ethereum but with some modifications. A standard Jellyfish Merkle tree will look like the following figure:

                                    .──────────────────────.
                            _.─────'                        `──────.
                       _.──'                                        `───.
                   _.─'                                                  `──.
               _.─'                                                          `──.
             ,'                                                                  `.
          ,─'                                                                      '─.
        ,'                                                                            `.
      ,'                                                                                `.
     ╱                                                                                    ╲
    ╱                                                                                      ╲
   ╱                                                                                        ╲
  ╱                                                                                          ╲
 ;                                                                                            :
 ;                                                                                            :
;                                                                                              :
│                                                                                              │
+──────────────────────────────────────────────────────────────────────────────────────────────+
 .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.  .''.
/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \/    \
+----++----++----++----++----++----++----++----++----++----++----++----++----++----++----++----+
 (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )
 (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )
 (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )
 (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )  )
 (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (  (
 ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■  ■

 ■: the [`Value`] type this tree stores.

A Jellyfish Merkle Tree consists of InternalNode and LeafNode. InternalNode is like branch node in ethereum patricia merkle with 16 children to represent a 4-level binary tree and LeafNode is similar to that in patricia merkle too. In the above figure, each bell in the jellyfish is an InternalNode while each tentacle is a LeafNode. It is noted that Jellyfish merkle doesn’t have a counterpart for extension node of ethereum patricia merkle.

Modules§

proof: Merkle proof types.
restore: This module implements the functionality to restore a JellyfishMerkleTree from small chunks of key/value pairs.
storage: Contains types used to bridge a JellyfishMerkleTree to the backing storage recording the tree’s internal data.

Structs§

JellyfishMerkleIterator: An iterator over all key-value pairs in a JellyfishMerkleTree.
JellyfishMerkleTree: A Jellyfish Merkle tree data structure, parameterized by a TreeReader R and a SimpleHasher H. See crate for description.
KeyHash: A hashed key used to index a JellyfishMerkleTree.
MissingRootError: An error that occurs when the state root for a requested version is missing (e.g., because it was pruned).
RootHash: A root of a JellyfishMerkleTree.
TransparentHasher: A trivial implementation of SimpleHasher that simply returns the first 32 bytes of the provided data. This is useful to avoid hashing data when testing, and facilitate debugging specific tree configurations.

Traits§

SimpleHasher: A minimal trait representing a hash function. We implement our own rather than relying on Digest for broader compatibility.

Functions§

ics23_spec

Type Aliases§