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
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.
What is Proof of Liabilities?PoR is a useful tool for proving that a custodian holds enough assets to cover its deposits; however, it isn’t enough. A custodian could easily take out a loan to accumulate sufficient assets to pass a PoR audit. However, the custodian may then lack enough assets to repay both the loan and the user deposits. A Proof of Liabilities (PoL) is an audit of a custodial platform’s debts and liabilities. Essentially, this involves a third-party auditor creating a complete list of a custodial platform’s liabilities just like a PoR audit tabulates assets and user deposits. If the total number of assets exceeds the total amount of user deposits and liabilities, then the company is solvent. It is also common to verify that depositors have precedence over creditors in the event of a bankruptcy declaration. This would ensure that, if a custodian lacked the resources needed to cover both user deposits and loans, depositors would be paid back before creditors.
What is Proof of Solvency?Proof of Solvency (PoS) is an all-in-one audit that combines PoR and PoS audits. Users of a custodial platform should look for a PoS audit performed by a third-party auditor. PoR is not enough on its own because it lacks visibility into a custodian’s debts, and a third-party audit is essential to prove that all deposits and liabilities were included in the audit. However, a PoS audit, like any security audit, is only a snapshot. A company that undergoes an audit one day could invest and lose assets the next. This is why some platforms are working to provide users with ongoing visibility into the state of their deposits.
Proving the Solvency of Custodial PlatformsOperating at a fractional reserve can be appealing for custodial platforms and is not necessarily a bad thing. Many traditional financial institutions hold only a fractional reserve, freeing up capital to use for investments that offer the potential for either rewards or losses. However, these institutions may also be bailed out by the government if something goes wrong. Cryptocurrency custodians likely lack the same guarantees, so users should know whether or not their assets are secure and whether the platform holds full reserves. A PoS audit can provide valuable information for users’ risk calculations.
For over 30 years, Marin Ivezic has been protecting critical infrastructure and financial services against cyber, financial crime and regulatory risks posed by complex and emerging technologies.
He held multiple interim CISO and technology leadership roles in Global 2000 companies.