[−][src]Module merkle_trees::compact_merkle_tree

Structs

Compact merkle tree can be seen as a list of trees. A leaf is added to a tree until its full (it has 2^k leaves) Once a tree is full, start adding to a new tree until that is full. Once the current full tree has the same height as the previous full tree, combine both full trees to form a new full tree such that the previous and current form the left and right subtrees of the new full tree respectively. When the various trees don't form a full tree, they can be seen as subtrees of a big n-ary tree. The root of this n-ary tree at any time is the hash of the concatenated roots of all full trees. eg, if there are 4 leaves in total, the n-ary tree is a full binary tree. When there are 5 leaves, the n-ary tree contains 2 subtrees of size 4 and 1. With 6 leaves, the n-ary tree contains 2 subtrees of size 4 and 2. With 7 leaves, the n-ary tree contains 3 subtrees of size 4, 3 and 1. With 8 leaves, the the n-ary tree is a full binary tree of size 8. Lets say we want to insert a few leaves l_0, l_1, l_2,..l_n in an empty tree. Inserting l_0 makes the tree full (with 2^0=1 leaf) with root T_0 so l_1 will be inserted in a new tree with root T_1, making it full as well. Note that since roots T_0 and T_1 have only 1 element so the root hash is same as the leaf hash, i.e. T_0 = hash(l_0) and T_1 = hash(l_1). Now we have 2 full trees of same height (1 in this case) so we combine them to make a new full tree of height 1 more than their height (new tree has height 2 in this case). The root of this new tree is T_2 and T_2 = hash(T_0, T_1). Since T_2 is full, l_2 will be inserted into a new tree T_3 and T_3 = hash(l_2). Also, T_3 is full so l_3 will be inserted in a new tree with root T_4 and T_4 = hash(l_3). We again have 2 tree of same height (1 here) T3, T_4 so we combine them to form a tree of bigger height and root T_5 = hash(T_3, T_4). Now we have 2 more trees of same height, T_2 and T_5. We combine them to form a bigger full tree with root T_6 = hash(T_2, T_5).

InMemoryHashDb

Uses an in-memory vectors for storing leaf and node hashes. Used for testing.

Traits

HashDb

Interface for the database used to store the leaf and node hashes