How zk-SNARKs Improve Binance’s Proof of Reserves System
Main Takeaways
In November 2022, Binance released its Proof of Reserves system utilizing Merkle tree cryptography to allow users to verify their holdings.
Binance has now improved its solution by implementing zk-SNARKs, a form of zero-knowledge proof.
Users can now check that each account’s total net balance is non-negative and that all user assets are part of Binance’s claimed total net balance of user assets – in a private and secure manner.
Take a look under the hood of Binance’s new proof-of-reserves solution. Combining zk-SNARKs and Merkle tree information, it gives users a new and improved way of verifying the state of Binance’s reserves.
Over the last few months, Binance’s dev team has been hard at work building advanced proof-of-solvency solutions. Such tools have become critical for centralized crypto exchanges amid the crisis of trust that engulfed the industry in the wake of the FTX collapse. User funds stored on Binance are backed at a 1:1 ratio, plus reserves, and finding a way to prove this to the public seamlessly has become a major part of Binance’s plan to restore industry trust.
In November 2022, we released our proof-of-reserves system utilizing a Merkle tree cryptographic technique to allow users to verify their holdings on Binance. Although an advancement in Binance’s user fund transparency push, the initial design of this solution had two shortcomings:
To protect user privacy, leaf nodes in Merkle proof represented the hash of users’ holdings – thus, the Merkle root couldn’t reflect the sum of its leaf nodes’ balance information.
The entity whose reserves were 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 such a malicious Merkle tree (although, in this case, the root reflects the sum of all leaf nodes’ balances, which can introduce privacy issues).
We now have a solution that can remedy these shortcomings and thus strengthen Binance’s proof-of-reserves system. Relying on zero-knowledge proof protocols, zk-SNARKs, we can prove that:
All leaf nodes of the Merkle tree have contributed to Binance’s claimed total user balance of each asset.
There is no user with a negative total net balance (an overall USD value of all assets the user holds) included in the Merkle tree.
A Word on Negative Balances and Performance
Since Binance offers margin, crypto loans, and futures trading products, each user’s balance of each crypto asset may be comprised of assets and liabilities. A user’s balance of a particular crypto asset can be negative, but their total net balance across all crypto assets should not be negative (as all loans are fully collateralized).
In this hypothetical scenario, let’s say that Alice had deposited 10,000 BUSD to Binance, then used 4,000 BUSD as collateral to borrow 2 BNB (at a rate of 1 BNB = 1,000 BUSD, assuming that Binance is always over-collateralizing). The following table shows Alice’s balance sheet.
If Alice then trades 1 BNB for 1,000 BUSD with Bob (who had also deposited 10,000 BUSD), their balance sheet would look like this after the trade is matched:
In this case, Alice’s BNB balance will amount to -1, which is not a valid node in a Merkle tree and that only covers one asset: BNB. However, if we are looking at total net balances, Alice is still at 10,000.
Another challenge comes from the sheer scale of Binance’s user base. A viable solution has to generate user proof and zk-SNARK proof for tens of millions of users, some of whom may hold more than 300 crypto assets on our platform.
All in all, we want to provide proof of the following facts within a reasonable time window:
Each Binance user’s assets are part of our claimed total user balance shown in the snapshot. Users can verify our claimed total user balance against the assets held at Binance-controlled addresses using a blockchain explorer (like Etherscan for Ethereum wallets or BscScan for BNB Chain wallets).
Each user’s total net balance is non-negative, which means Binance didn’t create dummy accounts with a negative balance to reduce the size of our verified reserves artificially.
What Are zk-SNARKs?
Before we dive into the details of our solution, a brief overview of the zero-knowledge proof mechanism is in order. Zero-knowledge protocols like zk-SNARK allow one party, the prover, to demonstrate to another party, the verifier, that the prover had executed certain computations accurately with certain inputs under certain constraints, all without disclosing the inputs. The computation might be time-consuming, but the underlying mathematical mechanism can help the verifier assess the proof quickly and securely.
The prover (Binance) starts with defining a set of constraints of the computation it wants to prove. The constraints are defined in circuits that can be expressed in a higher-level programming language (in our case, a forked version of gnark.)
The prover then executes the heavy computation, hashing all users’ ids and balance sheets, and generates proof of the computation meeting the constraints set out previously. To do so, it uses the computation trace (witness) and public or private inputs.
The verifier (user) gets the proof and verifies it with the public input of the circuit to satisfy itself that the computation has been executed accurately with all constraints met. The verification computation takes an extremely short time compared to the proving time. If the prover does not generate the proof on the pre-defined circuits, it cannot produce valid proof to pass the verification.
To take a deeper look under zk-SNARKs’ hood, you can refer to this series of articles.
Our Solution
The fundamental building block of the upgraded proof-of-reserves solution is still a 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 balances of each asset that each Binance customer holds.
To prove our reserves, we will generate zk-SNARK proof for the construction of the Merkle tree. For each user’s balance set – a leaf node of the Merkle tree – our circuit would make sure that:
Every asset’s balance of this user is included in the global state list mentioned above.
The user’s total net balance is not negative.
The change of the Merkle tree root is valid after updating this user’s information to the leaf node hash.
Please refer to this technical specification and our source code for the circuit (constraints) for implementation detail.
In each instance of proving our reserves, we will publish:
1. The Merkle proof: the hashes for each user (for Alice, represented by blue nodes in the above picture).
2. zk-SNARK proofs and public input (a hash of the list of total net balances of each asset and the Merkle root) of the circuit for all users.
By verifying the Merkle proof, users can make sure their balance sheet is included in the Merkle tree root. By verifying the zk-SNARK proof, users can make sure the construction of the Merkle tree meets the constraints defined in the circuit.
The security of this solution relies heavily on the setup of the proving key and verification key. We are working on a decentralized setup of the keys. When it comes to existing decentralized trusted setup ceremonies, the Ethereum ceremony offers a good example. We are very close to having an MPC solution to make the setup trustless.
Performance
Given the number of Binance users whose balances should be included, there’s no way to get a single proof of the Merkle tree construction that would cover all users at once. A solution to this is splitting users into batches of 864 each so as to have a smaller-scale circuit and parallel proving procedures.
For a batch that contains 864 users where each user owns 350 different assets, suppose each asset balance is in the range [0, 2^64-1]. With a 32-core 128GB server, zk proof generation time is about 110 seconds, and proof verification time is less than 1 millisecond.
Binance will start 1000 provers at the same time so as to generate proof for all accounts in 2 hours. The cost of this prover server for one hour is about 0.56 USD, so the total cost of generating all zk proofs covering all users would be about 1000 USD.
Conclusion
We will provide the first iteration of proof for users generated by this new solution in a subsequent proof-of-reserves announcement. Also, we have open-sourced our user data processor, prover, circuit, and verifier, so that every centralized exchange relying on the same model as we do can generate proof for their users and assets easily.
We hope this will be instrumental in pushing the transparency of the digital asset industry to a new level. We are also working on implementing the solution mentioned in Vitalik’s blog to achieve better performance, which will allow us to provide the proof more frequently at a lower cost.
As this is the first version of our zk-SNARK, we are looking forward to receiving community feedback so we can continue to improve the system.