How zk-SNARK Improves Gate.io's Proof of Reserves

With over 13 million users, Gate.io fully knows the importance of fund security and has pioneered the industry in taking effective measures. Gate.io was one of the earliest exchanges to implement the proof of reserves (PoR), revealing its PoR as early as May 2020. It was only after FTX misappropriated user assets in 2022, leading to a liquidity crisis and subsequent bankruptcy, that the proof of reserves became widely recognized as a solution for ensuring user fund security and enhancing platform trustworthiness.

Following the FTX incident, Gate.io promptly released its second proof of reserves. Shortly after its release, Ethereum’s founder, Vitalik Buterin, published an article titled “Having a safe CEX: proof of solvency and beyond,” discussing how exchanges can better demonstrate their solvency. The article suggests the integration of advanced technologies like zk-SNARK on top of traditional proof of reserves to ensure a more public, transparent, and authentic PoR. Gate.io plans to use the new technology mentioned in the article to upgrade its proof of reserves, offering users enhanced privacy and genuine asset security.

What is Proof of Reserves?

Proof of Reserves (PoR) refers to the review of balances held by cryptocurrency exchanges or other financial institutions, verifying whether the asset amount recorded by the company corresponds to the actual assets held. If the asset amount in the reserves exceeds the amount of assets deposited by users, i.e., the collateral ratio is greater than 100%, it proves that user funds are backed by real assets on a 1:1 basis.

Before the emergence of PoR, there were also proposals for asset transfers and proof of liabilities to demonstrate that exchanges had sufficient funds.

Asset Transfer - Demonstrating the Exchange Has Sufficient Assets

In 2011, MtGox, then the largest Bitcoin exchange, proved they held certain funds by executing a transaction that moved 424,242 BTC to a previously announced address. This method could only validate assets and could not prove the liabilities of the exchange.

Proof of Liabilities

The liabilities of an exchange are the assets deposited by its users. The simplest way to prove users’ assets is to publish a list containing user accounts and balances. Every user can access this list and check if the balance against their account is correct. However, this method has obvious drawbacks:

1. There’s no guarantee that the list provided by the exchange is authentic.

2. In the process, both the user’s account information and balance are disclosed.

This method could also use a data structure like Merkle to minimize the exposure of user information, leading to the current concept of PoR.

As illustrated, a Merkle tree is a tree-like data structure. The data at the bottom layer is called “leaf nodes,” and the middle can be termed “intermediate nodes.” Two leaf nodes can undergo hashing (processing any input value to obtain a specific value) to produce the value of an intermediate node. Two intermediate nodes are then hashed to get a unique output value for the next-level node. After successive layers of processing, the root node (Root) of the Merkle tree is ultimately obtained. This value is unique, and any change in a leaf node will result in a change in the root node.

Reserve Proof in Merkle Trees (Source: Vitalik）

In this method, the total assets held by an exchange on behalf of its users are determined by accumulating values layer by layer. However, even after inserting both the user account and balance data directly into the leaf nodes, there remains a minor risk of information leakage. Taking the illustration as an example, the user marked in green (Charlie) can access partial information of David, as well as the balances of Alice and Bob on the left side. Consequently, there have been technical improvements in the leaf nodes:

1. As shown in the illustration, the user account ID is hashed together with a specific value.

2. User balances are dispersed. For instance, Charlie’s 10ETH could be split into two 5ETH amounts and placed in two different leaf nodes.

3. The user ID and balance are hashed separately, and then the resultant values are hashed once more. Gate.io’s reserve fund proof uses this method.

Despite these advancements at the leaf node level, one issue remains unresolved: negative balances. In practice, after users deposit cryptocurrencies, they engage with exchange products like leveraged trading and perpetual contracts. If losses occur, the maximum loss should be 100% of the principal, meaning a user’s account balance should always be greater than or equal to zero.

Typically, negative balances are initiated by malicious exchanges. For example, if an exchange misappropriates 500ETH, under standard calculations, the assets the exchange actually holds could be less than the required collateral, possibly even less than 100%, revealing the misappropriation. However, the exchange might create an account, like the one named Henry with a balance of -500ETH in the given illustration, to make the Merkle tree’s total asset value equal to or less than the assets the exchange holds after misappropriation, thereby fabricating an illusion of a collateral rate greater than 100%.

Impact of Negative-value Accounts on Merkle Trees Illustration (Source: Vitalik）

To address this issue, exchanges like Gate.io have started using the zk-SNARK zero-knowledge proof technology to enhance their reserve proofs.

What are Zero-Knowledge Proofs and zk-SNARKs?

A zero-knowledge proof is a technique by which one party can prove something to another without revealing confidential information. To illustrate this concept with a simple example: If User A knows User B’s phone number and User C inquires if User A knows it, User A can dial B’s number on the spot to verify they indeed have it, without disclosing the actual number to User C. This process, which preserves user privacy yet confirms knowledge, exemplifies the “zero-knowledge proof” mechanism.

In the realm of cryptocurrencies, zero-knowledge proofs allow users to demonstrate ownership of a private key without exposing the key itself or any electronic signature. Cryptocurrency trading platforms hope to validate the status of their reserve funds without disclosing sensitive user information like individual account balances.

zk-SNARK stands for a succinct, non-interactive zero-knowledge proof technique. It undergoes an “initial trusted setup” to produce a Common Reference String (CRS) that all provers can directly access. This is analogous to an examination grading system where zk-SNARK directly uploads the correct answers. Examinees can then verify their responses (by sending their solution for a question to a backend system, which immediately provides the correct or incorrect outcome), making the process highly efficient.

With zk-SNARK, users can attest to knowing the original value that’s been hashed without revealing the actual content of that value. Without disclosing specific amounts, values, or addresses, users can also verify the validity of a transaction. It’s commonly used in private transactions. In the design of reserve proofs, zk-SNARK can pre-define constraints, eliminate non-zero accounts, and ensure user privacy.

How Gate.io Utilizes zk-SNARKs to Enhance Reserve Proofs

Gate.io integrates zk-SNARK technology with Merkle trees to create more transparent, privacy-protected, and tamper-resistant reserve proofs.

Implementation Process

1. Cold Wallet Authorization
   All cold and hot wallets transfer a specific random amount to an address designated by the auditing firm to verify ownership. The auditing firm then summarizes the balances from these addresses to determine the total amount controlled by the exchange (including both user and proprietary funds).

2. User Balance Snapshot
   At a specific moment in time, a snapshot is taken of users’ balances on the platform. Actual account equities are calculated using data such as outstanding orders, borrowed amounts, interest owed, and unrealized profits/losses.

3. Exporting Balances
   The encrypted UID and balance of every user are provided to the auditing firm for the purpose of calculating the aggregate user assets and publishing a Merkle number.

4. Batch Processing of User Assets
   The exchange’s net assets are confirmed to be the sum of each user’s net assets. Then, based on the net assets of users, a Merkle tree is constructed.
   (The primary reason for batch processing is that Gate.io has 13 million users. Processing all user data at once would place extreme demands on hardware and software. Batch processing is more time and cost-efficient without compromising security or data privacy.)

5. Implementing Circuit Constraints
   ① Before a user’s net assets are inserted into the Merkle tree, the node corresponding to that user’s ID is empty.
   ② Based on the user’s asset list and the price of each asset, calculate the user’s total assets/liabilities. Total assets must always exceed total liabilities.
   ③ Add the user’s assets/liabilities to the exchange’s assets/liabilities.
   ④ Using the user’s ID, total assets/liabilities, and asset list, compute the user status hash. Insert the user’s status into the Merkle tree to get a new Merkle Root.
   ⑤ Before creating an operation for one user, the tree’s root hash value must match the hash value of the root node after creating an operation for the subsequent user.
   (Constraint ① prevents untruthful node data, ② prevents accounts with negative values, and ⑤ ensures user data remains unchanged before and after operations.)

6. Generating Reserve Proof
   Using the zk-SNARK circuit, determine the number of user assets and then issue a reserve proof report.

For a more detailed explanation of the reserve calculation process and code implementation, click here.

Performance

On a machine with 32 cores and 128GB of RAM, it takes 15 days to compute the asset proofs for 10 million users. Reserve proof calculations can be parallelized; thus, with 10 machines, it only takes 1.5 days.

Conclusion

The introduction of zk-SNARKs is a significant upgrade for Gate.io’s reserve proofs and an essential step in protecting user assets. This superior safety and privacy protection boosts user confidence and sets a new standard for the cryptocurrency industry. As an industry leader, Gate.io has now open-sourced its code, hoping to promote more transparent and secure industry developments. In the future, Gate.io will continue its spirit of innovation, exploring and pioneering a more secure, comprehensive privacy-protected cryptographic future alongside its users.

References

• Gate.io 100% Proof of Reserves Audit Certificate
• Open-source code
• Blog article by Vitalik