[][src]Crate libra_jellyfish_merkle

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_blob_sets, put_blob_set and get_with_proof. After each put with a blob_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:

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

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

iterator

This module implements JellyfishMerkleIterator. Initialized with a version and a key, the iterator generates all the key-value pairs in this version of the tree, starting from the smallest key that is greater or equal to the given key, by performing a depth first traversal on the tree.

node_type

Node types of JellyfishMerkleTree

restore

This module implements the functionality to restore a JellyfishMerkleTree from small chunks of accounts.

test_helper

Structs

JellyfishMerkleTree

The Jellyfish Merkle tree data structure. See crate for description.

StaleNodeIndex

Indicates a node becomes stale since stale_since_version.

TreeUpdateBatch

This is a wrapper of NodeBatch, StaleNodeIndexBatch and some stats of nodes that represents the incremental updates of a tree and pruning indices after applying a write set, which is a vector of hashed_account_address and new_account_state_blob pairs.

Constants

ROOT_NIBBLE_HEIGHT

The hardcoded maximum height of a JellyfishMerkleTree in nibbles.

Traits

TreeReader

TreeReader defines the interface between JellyfishMerkleTree and underlying storage holding nodes.

TreeWriter

Type Definitions

NodeBatch

Node batch that will be written into db atomically with other batches.

StaleNodeIndexBatch

StaleNodeIndex batch that will be written into db atomically with other batches.