The main point

• In November 2022, Binance released a Proof of Reserves system that uses Merkle tree cryptography to allow users to verify their holdings.

• Binance has now enhanced its solution by implementing zk-SNARK, a form of zero-knowledge proof.

• Users can now check that the total net balance of each account is non-negative and that all user assets are part of the total net balance of user assets claimed by Binance – privately and securely.

Take a look at how Binance's new proof-of-reserve solution works. By combining zk-SNARK and Merkle tree information, users have a new and better way to verify the status of Binance reserves.

Over the past few months, the Binance development team has been hard at work building a state-of-the-art proof-of-solvency. The tool has become a crucial tool for centralized crypto exchanges amid the crisis of confidence that hit the industry following the collapse of FTX. User funds held on Binance are backed at a 1:1 ratio, plus reserves, and finding a way to prove this to the public without problems has been a major part of Binance's plan to restore industry confidence.

In November 2022, we released a proof-of-reserve system using the Merkle tree cryptography technique to allow users to verify their holdings on Binance. While this is progress in driving transparency of Binance users' funds, the initial design of this solution had two flaws:

1. To protect user privacy, the leaf nodes in the Merkle proof represent the user's ownership hash – thus, the Merkle root cannot reflect the amount of balance information of its leaf nodes.

2. Entities whose reserves are in the process of being verified could potentially add a negative balance under a fake account somewhere in the tree to make the total required reserves appear smaller. The following diagram from Vitalik Buterin's blog shows an example of a malicious Merkle tree (although in this case the roots reflect the sum of the balances of all the leaf nodes which could raise privacy issues).

We now have a solution that can fix this flaw and thereby strengthen Binance's proof-of-reserves system. By relying on the zero-knowledge proof protocol, zk-SNARK, we can prove that:

1. All leaf nodes of the Merkle tree have contributed to the total user balance that Binance claims for each asset.

2. No users with a negative total net balance (the entire USD value of all assets owned by the user) are included in the Merkle tree.

A Word about Negative Balances and Performance

Because Binance offers margin, crypto lending, and futures trading products, each user's balance of each crypto asset can consist of both assets and liabilities. A user's balance of a particular crypto asset can be negative, but their total net balance across all crypto assets cannot be negative (as all loans are fully collateralized).

In this hypothetical scenario, let's say Alice has deposited 10,000 BUSD into Binance, then used 4,000 BUSD as collateral to borrow 2 BNB (at a rate of 1 BNB = 1,000 BUSD, assuming that Binance always overcollateralizes). The following table shows Alice's balance sheet.

If Alice then trades 1 BNB for 1,000 BUSD with Bob (who has also deposited 10,000 BUSD), their balance sheet would look like this after the trades are matched:

In this case, Alice's BNB balance would total -1, which is not a valid node in the Merkle tree and only includes one asset: BNB. However, if we look at the total net balance, Alice is still 10,000 BUSD.

Another challenge comes from the scale of Binance's user base. A viable solution should generate user proofs and zk-SNARK proofs for tens of millions of users, some of whom may own more than 300 crypto assets on our platform.

Overall, we would like to provide evidence of the following facts within a reasonable time:

1. Each Binance user's assets are part of our claimed user's total balance shown in the snapshot. Users can verify our claimed total user balance based on assets held at addresses controlled by Binance using a blockchain explorer (such as Etherscan for Ethereum wallets or BscScan for BNB Chain wallets).

2. The total net balance of each user is non-negative. This means that Binance does not create dummy accounts with negative balances to artificially reduce the size of our verified reserves.

What is zk-SNARK?

Before we dive into the details of our solution, a brief overview of the zero-knowledge proof mechanism is in order. Zero-knowledge protocols such as zk-SNARK allow one party, namely the prover, to demonstrate to another party, namely the verifier, that the prover has executed a certain computation accurately with certain inputs under certain constraints, all without disclosing the input. Computation may be time consuming, but the underlying mathematical mechanisms can help verifiers assess evidence quickly and safely.

The prover (Binance) starts by defining the set of computational constraints it wants to prove. Constraints are defined in circuits that can be expressed in a high-level programming language (in our case, a forked version of gnark.)

The prover then executes heavy computation, hashes the ids and balance sheets of all users, and produces a computational proof that satisfies the pre-defined constraints. To do so, it uses computational traces (witnesses) and public or private inputs.

The verifier (user) obtains a proof and verifies it with public input from the circuit to satisfy itself that the computation has been executed accurately with all constraints met. Verification computation takes a very short time compared to proof time. If the prover does not produce a proof on a predefined circuit, the prover cannot produce a valid proof to pass verification.

For a deeper look at how zk-SNARK works, you can check out this series of articles.

Our Solution

The fundamental building block of an improved proof-of-reserves solution is still the Merkle tree. For the example above, it would look like this:

In addition to the Merkle tree, we also maintain a global state that represents a list of the total net balance of each asset owned by each Binance customer.

To prove our contingency, we will construct a zk-SNARK proof for Merkle tree construction. For each set of user balances – the leaf nodes of the Merkle tree – our circuit will ensure that:

1. The balance of each asset of this user is included in the global state list mentioned above.

2. The user's total net balance is not negative.

3. Merkle tree root changes take effect after updating this user information to the leaf node hashes.

Please see this technical specification and our source code for the circuit (limitations) for implementation details.

In each proof-of-suggestion example, we will publish:

1. Merkle Proof: hash for each user (for Alice, represented by the blue node in the picture above).

2. Proof of zk-SNARK and public input (hash of the list of total net balances of each asset and Merkle root) of the circuit for all users.

By verifying the Merkle proof, users can ensure their balance sheet is included in the root of the Merkle tree. By verifying the zk-SNARK proof, users can ensure that the Merkle tree construction satisfies the constraints specified in the circuit.

The security of this solution relies heavily on setting up proof keys and verification keys. We are working on setting up decentralized keys. Talking about existing decentralized trust-based setup ceremonies, Ethereum ceremonies offer a good example. Soon we will have an MPC solution for trustless setup.

Performance

Given the number of Binance users whose balances must be included, there is no way to obtain a single proof from Merkle tree construction that would include all users at once. The solution to this is to divide users into batches of 864 each so as to have smaller scale circuits and parallel proof procedures.

For a batch of 864 users where each user has 350 different assets, suppose each asset balance is in the range [0, 2^64-1]. With a 32-core 128GB server, the zk proof generation time is about 110 seconds, and the proof verification time is less than 1 millisecond.

Binance will start 1000 proofs at the same time to generate proofs for all accounts within 2 hours. The server cost of this proof for one hour is about 0.56 USD, so the total cost to generate all zk proofs covering all users is about 1000 USD.

Conclusion

We will provide the first user proof iterations generated by this new solution in our next proof-of-reserve announcement. Additionally, we have open-sourced our user data processors, provers, circuits, and verifiers, so that any centralized exchange that relies on the same model as we do can generate proofs for their users and assets with ease.

We hope this will play an important role in pushing the transparency of the digital asset industry to a new level. We are also working to implement the solutions mentioned in Vitalik's blog to achieve better performance, which will allow us to provide evidence more frequently at lower costs.

As this is the first version of our zk-SNARK, we hope to receive feedback from the community so we can continue to improve the system.

Code & Further Reading

• Our source code

• Binance proof-of-reserves: What is a Merkle tree

• Binance Academy - Improving Crypto Transparency with Zero-Knowledge Proof

• Vitalik's Blog: Having a safe CEX: proof of solvency and beyond