A Transpose Merkle Tree (TMT) is a data structure wherein interim nodes are transposed such that the walk from the leaf node to the root node essentially contains the Merkle branch(proof). The leaf & root nodes remain in the same position/s as in a standard Merkle tree.
This post includes,
- a highly efficient algorithm to compute the TMT with only
O(3 log n)
space complexity (primary memory). - a compact pre-ready data-structure, that can be persisted in a graph database(Neo4j), and can readily serve Merkle branch/paths trivially, traversal (by DB engine) of only
O(log n)
nodes.
The algorithm needs to store only the node-id, left-child-id, right-child-id for each height of the Merkle tree, hence the 3 log n
. And the recursive algorithm shown below simultaneously constructs the intermediate nodes & transposes them appropriately upto the final root node recursively, with this simple structure. The time complexity of TMT construction is comparable to the standar