## What are Merkle Trees and Proofs?

Proof of Reserves and Proof of Liabilities can use Merkle trees to prove certain facts while keeping data anonymous. To understand how these schemes work, it is useful to understand Merkle trees first. A Merkle tree is designed to securely summarize a set of data. This means that, given the root value of the tree and some internal node values, it is possible to prove that a particular piece of data is included in the tree. One application of Merkle trees is to prove that a set of transactions are included in a particular block in the digital ledger. The image above shows a Merkle tree that summarizes the various transactions that are included within a block. Each internal node within the tree contains the hash of its children. For example, the node labeled*Hash 0*contains the hash of

*Transaction 0*, and the node labeled

*Hash 0-1*contains the hash of the concatenated values of nodes

*Hash 0*and

*Hash 1*. Merkle trees are able to securely summarize data because of hash function collision resistance. With a secure, cryptographic hash function, it is infeasible to find two different inputs that produce the same hash output. Since Merkle trees are built of hash functions, it’s infeasible to find two Merkle trees of the same size with the same root value. This property makes it possible to prove that a particular piece of data exists within a Merkle tree without the need to reveal any of the other values. For example, it is possible to prove that Transaction 0 is included in the tree above given the values of

*Hash 1*,

*Hash 2-3*, and the root hash via the following process:

- Calculate
*Hash 0*as the hash of*Transaction 0* - Calculate
*Hash 0-1*by concatenating the values of*Hash 0*and*Hash 1*and hashing the result - Calculate the root hash by concatenating the values of
*Hash 0-1*and*Hash 2-3*and hashing the result - Validate that the calculated root hash value matches the provided root hash value

*Transaction 0*was included in the block as long as the provided root hash is correct. Since root hashes are included in block headers and are protected by blockchain immutability, this is a safe assumption. For Proof of Reserves and Proof of Liability, another important feature of hash functions is that they are one-way functions. This means that, given the value of

*Hash 1*, it is impossible to calculate the value of

*Transaction 1*. This is a useful feature when the set of data being proven is sensitive and shouldn’t be disclosed.

## What is Proof of Reserves?

Many of the failed custodial cryptocurrency platforms maintained fractional reserves, meaning that they only retained enough assets to cover a fraction of user deposits. This is problematic because a bank run on the platform could quickly drain these reserves, leaving users unable to withdraw their deposits. A Proof of Reserves (PoR) audit is performed by a third-party auditor and provides an anonymized cryptographic proof that a custodian holds adequate reserves to cover deposits and that an individual’s deposit is covered by those reserves. PoR uses a Merkle tree like the one described above to prove the set of user balances deposited in the protocol. This starts by snapshotting the set of user balances at a particular point in time and then anonymizing that list of balances. This anonymization can be accomplished by concatenating the balance with a unique identifier known to the exchange and the user. From this set of anonymized balances, the auditor builds a Merkle tree like the one above. Once the tree has been generated, the auditor or custodial platform can publish the tree without the associated balances — i.e. publishing only the values labeled as*Hash X*in the tree above. With knowledge of their own balance and unique identifier, a user can easily determine that their deposit was correctly recorded in the PoR audit. If many users individually validate that their balance is correct and attest to this, then the Merkle Tree is likely accurate and the platform has revealed all of the balances that it has received to the auditor. If the auditor knows the complete deposited value and users have validated that this value is correct, the other half of a PoR audit is the custodian proving that they have sufficient assets to cover these deposits. This can be accomplished by digitally signing messages using private keys associated with accounts that hold sufficient reserves. Since anyone can verify the value of an account on the blockchain, this is also a publicly verifiable proof. This approach to a PoR scheme relies on an auditor to tabulate and publish the total balance of user deposits. Alternatively, a PoR audit could use a Merkle sum tree, in which each node contains both the hash of its children and the sum of their values. However, publishing such a tree either leaks information about users’ balances or provides imperfect information. The use of zero-knowledge proofs for PoR audits is an area of research that could address these issues.