Main takeaways:
- In February 2023, Binance announced an improvement to its Proof of Reserves system by incorporating zero-knowledge proofs.
- Binance collaborates with Polyhedra Network to develop the industry’s first open-source Proof of Reserves system that meets the strictest accounting standards.
- The new solution uses a cryptographic tool, polynomial commitment, to eliminate the need of a new trusted setup and increase efficiency.
Proof of Reserves is critical for centralized exchanges and the cryptocurrency industry, as it builds trust and transparency between exchanges and their users. This mitigates concerns about insolvency or fraudulent practices. The continuous development of Proof of Reserves solutions, such as the incorporation of zero-knowledge proofs, lays the foundation for the long-term growth and stability of the cryptocurrency ecosystem.
In November 2022, Binance announced the industry’s first Proof of Reserves implementation using Merkle trees. In February 2023, Binance improved the Proof of Reserves system with zkSNARKs, which provide strong privacy and security.
We are excited to share a new solution based on Vitalik’s second proposal, which uses polynomial commitments and offers two key advantages.
1. Simpler trust assumptions. Binance’s previous solution uses Groth16, a general-purpose zk-SNARK. As discussed in the previous post, its security relies heavily on the setup of the proving key and verification key. Running a new trusted setup for Binance’s Proof of Reserves system is challenging in practice.
By using polynomial commitment, centralized exchanges are able to simplify the trust assumptions. The new Proof of Reserves system is built on top of existing setups conducted by third parties and community members, eliminating the need for a new trusted setup. This enhances the security of the Proof of Reserves system.
2. Better efficiency. This new solution leverages customization in modern zero-knowledge proofs, introduced in the Plonk protocol by Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. This allows the system to work with polynomial commitment and results in orders-of-magnitude speedups compared with a general-purpose proof system like Groth16.
The new solution is a highly optimized proof system designed for proof-of-reserves, incorporating numerous cutting-edge techniques developed over the past two to three years. It enables the proof system to scale to hundreds of millions of users and several hundred different token types, generating proofs within just a few hours. This makes proof-of-reserves both practical and cost-effective for any financial institutions, including exchanges and banks.
In the rest of the blog post, we will explore the concepts of polynomial commitment and explain how customization helps centralized exchanges achieve a new level of privacy, integrity, and scalability for proof-of-reserves.
What is polynomial commitment?
In the previous proof-of-reserves solution, users’ data was stored in a Merkle tree data structure. The zk-SNARK performs the reserves proof over data within this Merkle tree. To ensure data integrity, users could verify that the Merkle tree has correctly stored their asset records using a Merkle tree membership proof.
In the new version, we use polynomial commitment. Now, users’ data is represented as a polynomial and committed through a polynomial commitment scheme as a point on the elliptic curve (x, y). The zk-SNARK performs the same reserves proof over the data encoded in this polynomial.
Users can validate that their asset records are accurately represented in the polynomial committed in point (x, y) through a polynomial opening proof. This proof allows a user to see if its record is correctly included in the polynomial, while maintaining the confidentiality of other users’ records.
The following table summarizes the similarities and differences between Merkle tree and polynomial commitment.
| Merkle tree | Polynomial commitment | |
|---|---|---|
| Structure | Binary tree with elements as leaf nodes | Polynomial with elements encoded at specific points |
| Unique Representation | Root hash | point on the elliptic curve (x, y), i.e., a commitment of the polynomial |
| Construction | O(n) time complexity | O(n) time complexity |
| Proof Size | O(logn) proof size | O(1) proof size |
| Proof Verification | O(logn) time complexity | O(1) time complexity |
| Privacy | Reveals only the leaf node of the element | Reveals only the element at a specific point |
| Security | Based on cryptographically secure hash functions | Based on elliptic curves cryptocurrency |
| Integrity | Infeasible to find different trees with the same root hash | Infeasible to find different polynomials with the same commitment |
Using the polynomial commitment, we maintain the same privacy, security, and integrity guarantees. Moreover, polynomial commitment introduces the potential for modern zero-knowledge proof protocols that are efficient and have simple security assumptions, eliminating the need for a new trusted setup for proof-of-reserves while preserving efficiency.
What is a customized proof system?
The previous proof-of-reserves system features Groth16, a zk-SNARK protocol designed by Jens Groth in 2016. This proof system is general-purpose, meaning that it can prove and verify any statement in zero-knowledge proofs. Binance’s former proof-of-reserves implementation was based on this system.
Upon further examination of modern zero-knowledge proof techniques, we find that a general-purpose proof system does not take advantage of the uniform structure of proof-of-reserves. In contrast, a customized proof system, which exploits the inherent structure and uniformity of proof-of-reserves, can significantly outperform general-purpose ones. Customization has emerged as a promising approach in zero-knowledge proof systems to optimize the performance tailored to specific applications.
For example, non-negative balance checks are a core component of proof-of-reserves. These checks are highly uniform and structured, as they verify that the balance of each token is non-negative for every user.
As a general-purpose proof system, Groth16 does not differentiate between uniform and non-uniform computation. It processes the balance of each token for each user sequentially, one at a time. In essence, Groth16 is similar to a programming language that does not support “for-loops”. As a result, a programmer must unroll the loop and express the same computation in multiple lines of codes, leading to a substantial overhead in proof generation.
Groth16:
User 1 has a non-negative balance for Token 1
User 1 has a non-negative balance for Token 2
…
User 1 has a non-negative balance for Token N
…
User M has a non-negative balance for Token 1
…
User M has a non-negative balance for Token N
Customized proof system:
For i from 1 to M:
For j from 1 to N:
User i has a non-negative balance for Token j
Binance has developed a customized proof system specifically tailored for proof-of-reserves. Crucially, this proof system leverages the uniform structure by expressing the system as a circuit with highly customized gates. This is akin to expressing the per-user, per-token non-negative checks as 3-line codes, as demonstrated above, using “for-loops” to explicitly indicate repetitions.
This customization technique has been employed, albeit in different contexts, in numerous modern zero-knowledge proof protocols, such as Goldwasser-Kalai-Rothblum protocol and the TurboPlonk protocol introduced by Ariel Gabizon and Zachary J. Williamson.
Customization results in a significant speedup to proof generation and makes the new solution orders-of-magnitude faster than the Groth16 solution, even without requiring a new trusted setup. Furthermore, customization enables the use of other modern techniques, such as rematerialization and streaming proof generation, to minimize the memory footprint. We believe that customization paves the way for future optimization of proof-of-reserves.
Conclusion
We are thrilled to unveil our new Proof of Reserves system, which enhances security and delivers unprecedented efficiency through the use of polynomial commitment and a customized proof system. By eliminating the need for a new trusted setup, this solution has achieved a breakthrough in trust and transparency between the exchange and the users.
Soon, we will open-source our updated solution, including the prover and verifier, along with a detailed technical explanation. We invite developers, researchers, and industry partners to review and collaborate on this new technology. By working together, we can continue to refine and optimize the Proof of Reserves system, ensuring a safer and more reliable infrastructure for everyone. We remain committed to providing the highest levels of security and performance for our users while continuously working to improve our Proof of Reserves system.
We are working closely with Binance to keep improving the Proof of Reserves system. The new Proof of Reserves system marks a significant milestone in Binance’s commitment to ensuring the highest level of security and transparency standards in the industry. We are eager to contribute to the cryptocurrency ecosystem’s ongoing growth and stability with the wider community to develop and implement future innovations.
Glossary:
Merkle Tree: A cryptographic tree data structure in which each non-leaf node represents the hash of its child nodes, and leaf nodes contain data. This data structure is used to provide data integrity guarantees.
Polynomial Commitment: a cryptographic technique that encodes data in a polynomial and allows efficient proof of evaluations at specific points while maintaining privacy and integrity.
zk-SNARK: A cryptographic proof system that enables a prover to convince a verifier about a particular computation without revealing secret information, ensuring privacy and integrity.
Elliptic Curve: A type of mathematical curve used in cryptography that can be used for modern zero-knowledge proofs.
Rematerialization: A programming technique to reduce memory usage by reconstructing intermediate values during proof generation, thereby minimizing the memory footprint.
Streaming: A method allowing for generating proofs in a streaming manner, decreasing the memory consumption during proof generation.