TL;DR
- Centralized exchanges are unwilling to report their reserves as they disclose the information about their operations and profitability.
- ZK-SNARKs solve the problem of privacy concerns in disclosing proof of reserves (PoR) or proof of assets (PoA) of exchanges without revealing either the bitcoin addresses of the exchange or balances associated with those addresses.
- We construct a privacy preserving ZK-SNARK proof system for PoA to prove the knowledge of the private keys corresponding to the bitcoin assets of an exchange. This proof system also generates a pedersen commitment for the balance associated with each bitcoin address to be proved by the exchange.
Core Research Question
How does a centralized exchange prove its bitcoin reserves without revealing either the bitcoin addresses or the value associated with those addresses and at the same time with efficient prover time, proof size and verification time?
Citations
Reddy, Basireddy. (2022). A ZK-SNARK based Proof of Assets Protocol for Bitcoin Exchanges. [2208.01263] A ZK-SNARK based Proof of Assets Protocol for Bitcoin Exchanges.
Background
- Bitcoin public and private keys: Let G \in E be a generator or base point. The public key K (bitcoin address) corresponding to the private key k \in Z_q = \{1, 2, . . . , q ā 1\} is calculated as a scalar multiplication of k with G
-
Pedersen Commitment: Pedersen commitment Pedersen Commitment c \in \mathbb{E} is used to perfectly hide a message m \in \mathbb{Z}_q. Let H \in \mathbb{E} be another generator independent of G and ensure that the discrete logarithm of H for G is unknown. The Pedersen commitment c to a message m is
c = mG + bHWhere b \in \mathbb{Z}_q is a randomly chosen blinding factor. The Pedersen commitment is perfectly hiding and computationally binding under the discrete logarithm assumption.
-
ZK-SNARK: ZK-SNARK (Pinocchio, Groth16) is an advancement in the zero-knowledge proofs. The Zcash protocol proposed in zcash uses ZK-SNARK for constructing decentralized anonymous payments. ZK-SNARK is a succinct, non-interactive zero-knowledge proof which facilitates the public verifiability of the proof of a witness. ZK-SNARKs enable the prover to convince the verifier on any non-deterministic decision circuits (NP-statements) with auxiliary information (witness) and public inputs without revealing the witness. A trusted third party takes the circuit as input and generates a common reference string (CRS) consisting of proving and verification keys needed to prove and verify the statement of the ZK-SNARK scheme.
-
ZK-SNARK tool-chain: ZK-SNARK uses a trick to convert any NP-statement to a circuit satisfiability problem (Vitalikās QAP).
- Next, the NP-statement is converted to a non-deterministic decision circuit C such that the input to the statement is transformed as the input to the circuit C.
- In the next step, the circuit C for NP-statement is converted into arithmetic gates consisting of wires with values (from a field \mathbb{F}_p) connected to multiplication (*) and addition (+) gates.
- Next, we convert the algebraic gates into a Rank1 constraint system (R1CS), which is a group of three vectors (\mathbf{a}, \mathbf{b}, \mathbf{c}) and \textbf{t} is a solution vector to the R1CS such that
\textbf{t}.\textbf{a} * \textbf{t}.\textbf{b} = \textbf{t}.\textbf{c}- The next step is converting R1CS into a Quadratic Arithmetic Program (QAP)/ Quadratic Span Program (QSP) (QSP) form to implement the same logic as in R1CS.p(x) = \left(\sum_{i=0}^{m} a_i u_i(x)\right).\left(\sum_{i=0}^{m} a_i v_i(x)\right) - \left(\sum_{i=0}^{m} a_i w_i(x)\right)The QAP Q computes C iff a prover needs to prove that he knows a secret called witness w = (a_{l+1}, \dots, a_m) \in \mathbb{F}^{m-l}, which satisfies the above equation with public inputs z = (a_0=1,a_1 \dots, a_l) \in \mathbb{F}^{l+1} such that t(x) divides p(x).
-
We stick to the ZK-SNARK framework proposed by Groth in Groth16 as this protocol consists of a shorter proof with 3 group elements (2 elements from group \mathbb{G}_1 and 1 element from group \mathbb{G}_2) compared to 9 group elements in Pinocchio protocol Pinocchio. The ZK-SNARK proof system consists of three phases - (1) In setup phase, a trusted third party takes C as input and generates common reference string (CRS) \sigma = (\sigma_1, \sigma_2) through the ZK-SNARK tool-chain. (2) The prover computes the proof \pi = (A, B, C) for the witness (private input) w using CRS and public input. (3) The verifier verifies the proof from public input, CRS and \pi.
-
Summary
- We propose a proof of assets protocol for a bitcoin exchange based on the ZK-SNARK proof system. We model the non-deterministic statement as a circuit for verifying the knowledge of all the private keys owned by the exchange to prove the total bitcoin assets held by the exchange.
- The exchange acts as a prover of its total assets and the customers of the exchange play the role of a verifier in the ZK-SNARK proof system.
- The exchange as a prover takes the private keys as witness, public keys and the corresponding balances as public inputs. The exchange outputs a Pedersen commitment to the balance (part of the witness) associated with the key pair.
- The proof size is succinct and it does not leak the private keys (witness) used in the proof construction.
Method
-
NP-statement for PoA is as follows
Either I know the private key x_i corresponding to a public key y_i in which case s_i = 1 and c_i is the commitment to the value v_i or I donāt know the private key x_i corresponding to the public key y_i in which case s_i = 0 and c_i is the commitment to the value 0.
-
The arithmetic circuit from the NP-statement is as shown below, which consists of three sub circuits - Scalar multiplication circuit C_{MUL}(.), comparison circuit C_{CMP}(.) and Pedersen commitment circuit C_{PED}(.).
-
Scalar Multiplication Circuit: The circuit C_{MUL}(.) is the scalar multiplication of x_i with base point G. It is used to test whether the exchange E knows the private key x_i (256-bits) matches the corresponding public key y_i (256-bits x-coordinate and 256-bits y-coordinate). We construct P_{add} gadget with 3 arithmetic gates as per point addition for elliptic curve points ecc. The summary of the total number of constraints (or arithmetic gates) required to construct the proof for C_{MUL}(.) circuit is listed as follows
-
Comparison Circuit: The comparison circuit C_{cmp} compares the output of the scalar multiplication y_i^{'} with the input y_i. The circuit ensures the comparison of x, y coordinates of y'_i and y_i to yield a binary output s_i. We also add a constraint to C_{CMP} circuit to ensures that s_i \in \{0,1\} using the operation s_i * s_i = s_i. So, we express the C_{CMP} circuit using two constraints.
-
Pedersen Commitment Circuit: C_{PED} circuit evaluates the Pedersen commitment of b_i = s_i. v_i with a randomly chosen blinding factor r_i which yields an output c_i = b_iG + r_i H. This circuit requires two C_{MUL} circuits, an arithmetic gate for computing b_i. Since the total bitcoin supply is limited to 21 million coins, the value of v_i is bounded by 2^{z}, where z \in [0,MaxSupply]. The summary of the total number of constraints required to construct a proof for C_{PED} circuit is listed in Table-II.
-
Proof of Assets Protocol:
- We propose the ZK-SNARK based PoA protocol with the following public and private inputs for i\in[1, n]
Public input from blockchain: z_i = (y_i, v_i)
Exchangeās private input (witness): w_i = (x_i, s_i, r_i)
Verifierās input from Exchange: c_i, C_{Assets} - Setup phase: The trusted third party generates the CRS \sigma for the NP-statement PoA.
- Prover phase: The exchange \mathcal{E} constructs the proof \pi_i \leftarrow Prove(\sigma, z_i, w_i) and compute c_i and C_{Assets}.
- Verifier phase: The customer verify
b_{1,i} \in \{0,1\} \leftarrow Verify(\sigma, z_i,c_i, \pi_i) and checks C_{Assets} \stackrel{?}{=} \sum_{i = 0}^{n} c_i
- We propose the ZK-SNARK based PoA protocol with the following public and private inputs for i\in[1, n]
Results
-
We have implemented the Proof of Assets protocol in C++ using the libsnark library developed by scipr-lab.
-
The elements in implementation:
- Protoboard: A protoboard is a virtual prototype which collect all the circuits. We allocate all the public and auxiliary inputs used in the ZK-SNARK proof system to the protoboard.
- Gadgets: We construct a PoA\_gadget consists of gadgets for scalar multiplication, comparison and Pedersen commitment to implement circuit C_{PoA}.
- POA \rightarrow generate\_r1cs\_constarints(): The trusted third party constructs the constraint system PoA\_gadget. The PoA\_gadget generates a total of 1702 constraints for each instance (z_i,w_i) of the PoA.
- POA \rightarrow generate\_r1cs\_witness(): The prover uses public and private (witness) inputs to generate witness for all the internal wires of the circuit C_{PoA}.
-
We performed tests on a personal computer with IntelĀ® Coreā¢ i9-9900K CPU @ 3.60 GHz processor with 16 GB RAM with the following metrics- proof construction time by an exchange \mathcal{E}, proof verification time by the customer \mathcal{C}, and the proof size.
-
The proof construction time depends on the number of the ZK-SNARK circuitās constraints. The proof size is the combination of size of 3 group elements of each proof \pi_i and size of the Pedersen commitment to v_i.
-
The set \mathbf{S_{anon}} such that |\mathbf{S_{anon}}| = n is the set of all public keys which is a super set of \mathbf{S_{own}} called the set of public keys for which the exchange knows the private keys. We test the protocol for n = 100, 1000 and 10000. We choose |\mathbf{S_{own}}| as 25\%, 50\% and 75\% of n.
Discussion and Key Takeaways
- The protocol is secure under elliptic curve discrete logarithm assumption since the ZK-SNARK satisfies the completeness, soundness and statistical soundness.
- The results demonstrate that the construction of the proof requires a few hours on an ordinary computer which could be reduced further on a server with high-end processors, which allows the prover to generate proof of assets very frequently.
- The proof size is less than \approx 2 MB for n = 10000. The customer can verify the proofs for all the private keys in the order of minutes.
Implications and Follow-Ups
- We foresee the construction of the proof of assets protocol for bitcoin P2PKH (Pay to Public Key Hash) addresses by proving the knowledge of the hash preimage through the ZK-SNARK framework.
- We intend to combine these proof of assets protocols with proof of liabilities by proving the membership of customer funds using the set-membership proofs and ZK-SNARK mechanism.
Applicability
- The centralized crypto exchanges who hold the crypto assets on behalf of the customers can use this protocol without compromising their privacy.
- The proposed circuit can be used as a first step for proving the assets of the P2PKH addresses of bitcoin and similar cryptocurrencies.