Proof of Reserves and Merkle Tree

Vitalik Buterin’s article Having a safe CEX: proof of solvency and beyond highlights the challenge centralized exchanges face in verifying user assets and ensuring sufficient reserves to honor user deposits. Therefore, exchanges need a way to prove that they have enough reserve assets to fully repay these assets when requested by users, meaning they need to demonstrate that the value of their reserve assets exceeds the value of user deposits. This proof is known as Proof of Reserves and is called 100% reserve audit proof at Gate.io.

The simplest way to prove deposits is by publishing a list of (username, and balance) pairs. Each user can check if their balance is included in the list, and anyone can verify the complete list to ensure all balances are non-negative and the sum matches the claimed amount by the exchange. However, this compromises privacy. To address this, a slight modification is made: publishing a list of (hash(username, salt), balance) pairs and privately sending each user their salt value. But even this reveals balances and balance changes. To protect privacy, a further innovation is introduced: the Merkle tree.

（Figure 1 Source：https://vitalik.ca/general/2022/11/19/proof_of_solvency.html）

The Merkle tree technique organizes user balance data into a Merkle sum tree. In this tree structure, each node consists of a (balance, hash) pair. The leaf nodes at the bottom represent individual user balances and the salted hash of their usernames. In each higher-level node, the balance is the sum of the two balances below it, and the hash is the hash of the two nodes below it. The Merkle sum proof, similar to a Merkle proof, represents a “branch” of the tree made up of sibling nodes from leaf to root. The exchange provides each user with the Merkle sum proof of their balance, enabling them to verify that their balance is correctly included in the exchange’s total balance.

This design significantly enhances privacy compared to a fully public list. Additionally, privacy leakage can be further minimized by shuffling the “branches” whenever the “root” is published. However, there are still some remaining issues. For example, Charlie learns that someone has 164 ETH, and the balances of two users add up to 70 ETH, among other information (see Figure 1). An attacker who controls multiple accounts could still deduce sensitive information about exchange users.

Limitations of Merkle Tree-based Proof of Reserves

While the Merkle tree-based proof of reserves has been effective in ensuring the security of user assets, there are still some issues with this approach:

1. Front-end Fraud: The Merkle tree data is stored on the internal servers of the exchange, and the exchange controls the front-end pages that users interact with. The exchange can potentially return fake pages to deceive users, leading to the possibility of front-end fraud.
2. Malicious Merkle Tree Algorithm Attack: A centralized exchange (CEX) can create fake accounts with negative balances after misappropriating funds. For example, if a user had assets worth $1,000 and the exchange misappropriated $500, the user’s balance displayed on the interface would still show $1,000. If the Merkle tree proof is issued based on $1,000, it would appear that the exchange’s actual assets ($500) are less than the user’s deposited assets ($1,000), indicating insufficient reserve funds. However, by creating a fake account with a balance of -$500, the exchange can make the Merkle tree show that its actual assets ($500) equal the user’s deposited assets (1,000 - 500 = $500), resulting in a normal PoR output.
3. Potential privacy issues for attackers with multiple accounts.

Zero-Knowledge Proof and zk-SNARK

Zero-knowledge proofs have gained widespread attention in various use cases due to their potential to enhance security, protect user privacy, and support scalability in Layer-2 networks.

Zero-knowledge proofs enable one party to prove to another party that a statement is true without revealing any additional information. They contribute to increased privacy by reducing the amount of shared information between participants and support scalability by allowing proofs to be verified faster without validating the entire dataset.

zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) is a zero-knowledge proof technology proposed in a joint paper by Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer in 2012. zk-SNARK allows one party to prove to another party that they know a secret without revealing the secret itself, thus proving the correctness of a logical expression without exposing any information. In traditional zero-knowledge proofs, the prover must interact with the verifier multiple times to generate the proof. However, in zk-SNARK, once the parameters (especially the public parameters) and the proof are generated, the verifier can verify the correctness of the proof without needing multiple interactions with the prover.

For example, imagine you have a treasure map that leads to the exact location of the buried treasure. You want to prove to someone that you know the treasure’s location without revealing the contents of the map or the actual location of the treasure. Using zk-SNARK technology, you would create a puzzle piece of the treasure map. You select a small piece of the puzzle (a proof) and show it to the other person, which is enough to convince them that you know how the complete puzzle fits together, i.e., the treasure’s location, without needing to see the entire puzzle. However, to accomplish this, you must obtain some special markings from a reputable printing factory to authenticate your puzzle pieces.

The implementation of zk-SNARKs is based on elliptic curve cryptography and polynomial mathematics. This technique employs mappings to transform inputs into polynomials and utilizes mathematical concepts such as the order of elliptic curves and the discrete logarithm to validate that the constraints on the polynomials are satisfied. It leverages special algorithms for data compression, thereby enabling efficient execution of mathematical computations.

Therefore, using zk-SNARKs can significantly streamline and enhance privacy in reserve proof protocols. By incorporating all user deposits into a Merkle tree and employing zk-SNARKs to attest that all balances are non-negative and sum up to a claimed value, it’s possible to affirm that an exchange has the capacity to fully cover its liabilities if the publicly disclosed assets on the blockchain exceed this value.

Integrating zk-SNARKs with Merkle trees facilitates the simultaneous verification of data integrity and consistency while preserving the privacy of transactions. Provers can use zk-SNARKs to demonstrate that they possess a Merkle proof meeting specific conditions without revealing the details of the proof. For exchanges, this approach offers a way to prove they have sufficient funds to meet all obligations while safeguarding user privacy.

Gate.io’s Zero-Knowledge Reserve Upgrade

In summary, Gate.io’s zero-knowledge proof technology addresses two key issues with the proof of reserves:

1. Allowing users to prove ownership of certain assets without revealing any sensitive information
2. Eliminating the possibility of a malicious Merkle tree algorithm attack by ensuring that the Merkle tree does not contain users with negative net balances, as described in the previous section

Gate.io has upgraded its proof of reserves using zk-SNARK, taking a significant step as a leading exchange in protecting user asset security. With this upgrade, users can view reserve proofs in real-time, and the first batch of supported assets will cover the top 100 by market capitalization. As an industry leader, has open-sourced the code and will continue to drive industry development and explore a more secure and privacy-enhancing encrypted future with this zero-knowledge-proof upgrade.

Further Readings:

• How zk-SNARK Improves Gate.io’s Proof of Reserves
• What is Proof-of-Reserves (PoR)?