What is zk-SNARKs that can improve Binance’s proof-of-reserve system?

In November 2022, Binance released a proof-of-reserve system using Merkle tree cryptography, allowing users to verify the assets they hold.

Now Binance has improved on this solution with zk-SNARKs, a zero-knowledge proof protocol.

Users can now verify in a secure and private manner that their account’s total net balance is non-negative and that their assets are part of Binance’s published total net balance of users’ assets.

Now take a deep dive into Binance’s new proof-of-reserve proposal. This solution combines zk-SNARK and Merkle tree algorithms to provide users with a new and improved way to verify Binance Reserves.

The Binance development team has been working hard over the past few months to build an advanced Proof of Solvency solution. The FTX storm triggered a crisis of trust that has swept across the industry, and such tools are especially important for centralized digital currency trading platforms at this time. Binance holds all user assets (and reserves) at a 1:1 ratio, and finding a way for customers to successfully verify these facts is an important part of Binance’s plan to restore trust in the industry.

In November 2022, Binance released release a Proof of Reserve system using Merkle tree cryptography technology, allowing users to verify assets held in Binance. The transparency of Binance users’ funds has been successfully improved, but the initial design of the scheme has the following two shortcomings:

1. To protect user privacy, the leaf nodes in the Merkle proof represent the hash value held by the user. Therefore, the Merkle root cannot reflect the total balance of the leaf nodes.

2. If the entity whose reserve is verified adds a fake account with a negative balance under the Merkle tree, the total value of the reserve required will be reduced. The image below, from Vitalik Buterin’s blog , shows this malicious Merkle tree algorithm (although in this case the root node reflects the sum of all leaf node balances, which may have privacy implications).

Now, Binance has a solution to make up for these shortcomings and improve the Binance Proof of Reserve system. After applying the zero-knowledge proof protocol zk-SNARK, Binance can prove:

1. All leaf nodes of the Merkle tree are part of Binance’s published total balance of each asset of the user.
2. Users with negative total net balances (the total dollar value of all assets held by a user) are not included in the Merkle tree.

Go to Binance’s Official Website

Explanation of Negative Balances and Transactions

Binance offers leveraged, pledged lending, and contract trading products, so each user’s crypto asset balance may consist of assets and liabilities . Users may have a negative value on one of their crypto assets, but their total net balance of all their crypto assets should not be negative (since all borrowed coins are collateralized accordingly).

Assume a scenario: Alice deposits 10,000 BUSD in Binance, and then uses 4,000 BUSD as collateral to lend 2 BNB (at the rate of 1 BNB = 1,000 BUSD, assuming that Binance is always over-collateralized).

At this point, Alice’s BNB balance is -1, which is not a valid node in the Merkle tree, and only the status of BNB as an asset. But Alice’s total net balance is still 10,000 BUSD.

Another challenge is the huge user base of Binance. Binance has tens of millions of users, and some users may have more than 300 cryptocurrency assets on the platform, and Binance has to find an effective solution to provide user proof and zk-SNARK proof for users.

In summary, Binance hopes to provide factual proof within a reasonable time frame:

Each Binance user’s assets are part of the total user balance that Binance publishes in the snapshot. Users can use a blockchain browser (like Etherscan for Ethereum wallets or BscScan for BNB Chain wallets) to verify the total user balance published by Binance against the addresses of assets held by Binance.

The total net balance of each user is non-negative, which means that Binance cannot create fake accounts with negative balances to artificially reduce the published reserve value.

Sign up on Binance for free

What are zk-SNARKs?

Before we delve into this solution, a brief overview of the zero-knowledge proof mechanism. Zero-knowledge protocols such as zk-SNARKs are one party (the prover) that proves to another party (the verifier) ​​that the prover has accurately performed a specific computation with specific inputs under specific constraints, without disclosing the inputs. Computations are time-consuming, but this basic mathematical mechanism allows verifiers to evaluate proofs quickly and safely.

The prover (Binance) defines a set of computational limits that it intends to prove. The limit is on circuit definitions that can be expressed in a high-level programming language (here a forked version of gnark).

The prover then does the heavy lifting, hashing all user IDs and balance sheets to generate a proof of computation that satisfies pre-set constraints. To do this, the prover computationally tracks (witnesses) public or private inputs.

The verifier (user) takes the proof and verifies it using the circuit’s public inputs, confirming that the computation was performed accurately subject to all constraints. The verification computation takes very little time compared to the proof time. If the prover does not generate proofs on a pre-defined circuit, valid proofs that can be verified cannot be generated.

Go to Binance’s Official Website

The solution

The basic building blocks of the upgraded Proof of Reserve solution are still Merkle trees. The above example can be shown as:

In addition to the Merkle tree, Binance maintains a global state representing a list of the total net balances of each asset held by each Binance client.

To prove the reserves, Binance generates zk-SNARK proofs for Merkle tree construction. For each user’s combination of balances – leaf nodes of the Merkle tree, the circuit will ensure:

1. The user’s balance of each asset is included in the above global state list.
2. The user’s total net balance is not negative.
3. Changes to the root of the Merkle tree will take effect after the user information is updated to the leaf nodes.

Every time Binance proves the total amount of reserves, Binance publishes:

1. Merkel proof: the hash value of each user (the blue node in the picture above is Alice’s hash value).

2. zk-SNARK proofs and common inputs for all user circuits ( a list of total net balances and Merkle roots for each asset) .

After verifying the Merkle proof, the user can ensure that their balance sheet is included in the Merkle tree. After verifying the Merkle proof, the user can ensure that the construction of the Merkle tree satisfies the constraints defined by the circuit.

The security of this solution relies heavily on the setup of proof keys and verification keys. Binance is working on a decentralized setup for keys. Ethereum ceremonies are a good example of existing decentralized trusted setup ceremonies. Binance will soon have multi-party computation (MPC) solutions that make the setup trustless.

Sign up on Binance for free

Performance

Due to the large number of Binance users whose balances should be included, it is not possible to obtain a single proof of Merkle tree construction covering all users at once. The solution to this problem is to divide the users into batches of 864 people each, which can reduce the circuit size and the parallel proof program size.

Each group has 864 users with 350 different assets, assuming that the balance range of each asset is between [0, 2^64-1]. If the server has 32 cores and 128GB, it takes about 110 seconds to generate a zk proof, and the proof verification time is less than 1 millisecond.

Binance will activate 1000 servers at the same time, which can generate proofs for all accounts within 2 hours. The cost of running the prover server for 1 hour is about 0.56 USD, so it takes about 1000 USD to generate zk proofs covering all users.

Go to Binance’s Official Website

Conclusion

Binance will provide users with the first iteration of proofs generated by this new solution in a subsequent Proof of Reserves announcement. Additionally, Binance will open source user data processors, provers, circuits, and verifiers so that centralized exchanges can easily generate proofs for their users and assets following the model.

Binance hopes that this move will bring the transparency of the digital asset industry to a new level. Binance is also working on a more efficient solution mentioned in Vitalik’s blog, which Binance hopes can be implemented to provide proofs more frequently and at a lower cost.

Sign up on Binance for free