[−][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 256bit 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 4level 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 
node_type  Node types of 
restore  This module implements the functionality to restore a 
test_helper 
Structs
JellyfishMerkleTree  The Jellyfish Merkle tree data structure. See 
StaleNodeIndex  Indicates a node becomes stale since 
TreeUpdateBatch  This is a wrapper of 
Constants
ROOT_NIBBLE_HEIGHT  The hardcoded maximum height of a 
Traits
TreeReader 

TreeWriter 
Type Definitions
NodeBatch  Node batch that will be written into db atomically with other batches. 
StaleNodeIndexBatch 
