Module flat_tree 

Merkle Tree implementation based on Flat In-Order Tree.

Flat In-Order Tree is described in DEP-0002: https://github.com/datprotocol/DEPs/blob/master/proposals/0002-hypercore.md

A Flat In-Order Tree represents a binary tree as a list, also known as Bin Numbers defined in PPSP RFC 7574: https://datatracker.ietf.org/doc/rfc7574/

We assume the max node index is 63-bit, which limits the max tree depth (level) to 62.

A merkle tree with flat layout is storage friendly (i.e. no fragmentation and grows linearly) with O(1) leaf and node access. It stores all leave nodes, caches the hash of intermediate nodes, and provides efficient merkle path computation for verification purposes.

Structs

FlatTree

Representation of a flat tree of element type T where the 'a is the life-time parameter of the underlying FlatStore.

FullPathIterator

Helper to iterate from a leaf node to the top root (at a level that is equal to full tree depth).

LocalPathIterator

Helper to iterate from a leaf node to one of the roots.

Enums

Pos

Position of a node is either a leaf, a root, or a left or right node.

Constants

MAX_LEVEL

Max tree depth on a 64-bit architecture is 62.

Traits

FlatStore

Abstraction over the underlying storage to allow flexible choice of implementation. For example, an implementation may store multiple trees in a column format, while another may overlay in-memory cache on top of external storage.

Merkleable

Abstraction over binary hash operation. The value of a merkle hash is computed by hashing its left branch and right branch. By default it assumes a value of “zero” if a branch does not exist. The actual hashing algorithm and the value of zeros at a given tree level are implementation dependent.

Functions

level_of_node_index

Return the level of the given node_index.