0.2.7 


0.2.6 

0.2.2 

0.1.7 

0.1.0 

#14 in #leafnode
37 downloads per month
Used in 37 crates
(3 directly)
1MB
18K
SLoC
This module provides algorithms for accessing and updating a Merkle Accumulator structure
persisted in a keyvalue store. Note that this doesn't write to the storage directly, rather,
it reads from it via the HashReader
trait and yields writes via an in memory HashMap
.
Merkle Accumulator
Given an ever growing (append only) series of "leaf" hashes, we construct an evolving Merkle Tree for which proofs of inclusion/exclusion of a leaf hash at a leaf index in a snapshot of the tree (represented by root hash) can be given.
Leaf Nodes
Leaf nodes carry hash values to be stored and proved. They are only appended to the tree but never deleted or updated.
Internal Nodes
A nonleaf node carries the hash value derived from both its left and right children.
Placeholder Nodes
To make sure each Leaf node has a Merkle Proof towards the root, placeholder nodes are added so
that along the route from a leaf to the root, each node has a sibling. Placeholder nodes have
the hash value ACCUMULATOR_PLACEHOLDER_HASH
A placeholder node can appear as either a Leaf node or a nonLeaf node, but there is at most one placeholder leaf at any time.
Frozen Nodes & Nonfrozen Nodes
As leaves are added to the tree, placeholder nodes get replaced by nonplaceholder nodes, and when a node has all its descendants being nonplaceholder, it becomes "Frozen"  its hash value won't change again in the event of new leaves being added. All leaves appended (not counting the one possible placeholder leaf) are by definition Frozen.
Other nodes, which have one or more placeholder descendants are NonFrozen. As new elements are appended to the accumulator the hash value of these nodes will change.
Leaf Count
Given a count of the number of leaves in a Merkle Accumulator it is possible to determine the shape of the accumulator  which nodes are filled and which nodes are placeholder nodes.
Example: Logical view of a Merkle Accumulator with 5 leaves:
Nonfzn
/ \
/ \
/ \
Fzn2 Nonfzn
/ \ / \
/ \ / \
Fzn1 Fzn3 Nonfzn [Placeholder]
/ \ / \ / \
L0 L1 L2 L3 L4 [Placeholder]
Position and Physical Representation
As a Merkle Accumulator tree expands to the right and upwards, we number newly frozen nodes monotonically. One way to do it is simply to use inorder index of nodes, and this is what we do for the inmemory representation. We call the stated numbers identifying nodes below simply "Position", and unless otherwise stated, this is the inorder position.
For writing to disk however, we write all the children of a node before the parent. Thus for disk write order, it is more convenient to use the postorder position as an index. And with that we can map a Merkle Accumulator into a keyvalue storage: key is the postorder position of a node, and the value is hash value it carries.
We store only Frozen nodes, and generate nonFrozen nodes on the fly when accessing the tree. This way, the physical representation of the tree is appendonly, i.e. once written to physical storage, nodes won't be either modified or deleted.
Here is what we persist for the logical tree in the above example:
Fzn2(6)
/ \
/ \
Fzn1(2) Fzn3(5)
/ \ / \
L0(0) L1(1) L2(3) L3(4) L4(7)
When the next leaf node is persisted, the physical representation will be:
Fzn2(6)
/ \
/ \
Fzn1(2) Fzn3(5) Fzn4(9)
/ \ / \ / \
L0(0) L1(1) L2(3) L3(4) L4(7) L5(8)
The numbering corresponds to the postorder traversal of the tree.
To think in keyvalue pairs:
<key><value>
 0  hash_L0 
 1  hash_L1 
 2  hash_Fzn1 
 ...  ... 
Dependencies
~47–64MB
~1.5M SLoC