Merkle Sum Tree
Last updated
Last updated
A popular , useful when dealing with larger data structures, is a . In a Merkle Tree, each data entry is hashed and inserted as a tree leaf. Each leaf is hashed with the sibling one to produce a middle node. This process is repeated for each tree level until it reaches a single node at the top, called the Merkle Root, which is a commitment to the entire data set.
Merkle Trees are especially useful when you want to prove the existence (typically known as "inclusion proofs") of a specific piece of entry data within a large set without revealing the entire set in a time-efficient manner.
Summa uses a modified version of a Merkle Tree as a cryptographic commitment scheme, which is a Merkle Sum Tree. In the context of Summa, the Merkle Sum Tree data entries are the Custodian liabilities. At the same time, the Root represents a commitment to the state of the liabilities.
Each entry of a Merkle Sum Tree is a pair of a username and the associated balance.
Each Leaf Node contains a hash and a balance. A leaf node exists for each entry.
The hash is equal to H(username, balance)
.
The balance of a leaf node is equal to the balance of the associated entry
Each Middle Node contains a hash and a balance.
The hash is equal to H(LeftChild.balance + RightChild.balance, LeftChild.hash, RightChild.hash)
The balance is equal to the sum of the balances of the two child nodes
The Root Node is the last Middle Node of the tree. Analogously to a traditional Merkle Tree, the hash of the root represents a blinding and hiding commitment to the state of the entries. In addition to a traditional Merkle Tree, the Merkle Root contains a balance that represents the sum of the balances of the tree entries.
While the example uses a balance in only a single cryptocurrency (ETH), Summa's Merkle Sum Tree supports multiple cryptocurrencies.
The core properties of the used by Summa are:
Note that Summa uses the "broken" version of Maxwell's Merkle Sum Tree ( paragraph 4.1). Nevertheless, the usage of this tree, in conjunction with zero knowledge proof, allows us to .