Merkle Trees

Merkle tree representation of user data

Merkle trees are specific data structures with hierarchical flow of information, with non-unique leaves containing information, non-unique branches connecting other leaves and branches, and a unique root that represents the tree as a whole. Merkle trees have historically been used for simple binary information, such as whether or not a particular key (or its hash) is stored inside the data structure.

Special extensions of Merkle trees have held more abstract data, such as a proof of relationship between hashes of data membership within the tree. We can call these Data Merkle trees (DMT).

A subset of Merkle trees is the Sparse Merkle tree (SMT). SMTs are structured in a specific structural order than allows for quick sorting of data elements by specific forward and backward paths. Simplified, the SMT leaf value describes the methods for traveling to and from the leaf and the root. This has the advantage of the SMT guaranteeing uniqueness of all leaves and branches and being able to represent massive amount of data succinctly due to most leaves not being included in the tree.

Gunero will use a unique Merkle tree that is a composite of both SMT and DMT. The base of the tree with the SMT root with the leaves of the SMT being the root of a DMT of the unique data structures that hold user information.

SMT structure:

1. SMT root
2. SMT branch 1 (left, right)
3. SMT branch ...
4. SMT branch 159 (left, right)
5. DMT root

DMT structure:

1. DMT root
2. DMT branch 1 (left, right)
3. DMT branch 2 (left, right)
4. DMT leaf (Public key, Status, Meta, Reserved)