TLDR
 Centralized exchanges are unwilling to report their reserves as they disclose the information about their operations and profitability.
 ZKSNARKs 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 ZKSNARK 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 ZKSNARK based Proof of Assets Protocol for Bitcoin Exchanges. [2208.01263] A ZKSNARK 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.

ZKSNARK: ZKSNARK (Pinocchio, Groth16) is an advancement in the zeroknowledge proofs. The Zcash protocol proposed in zcash uses ZKSNARK for constructing decentralized anonymous payments. ZKSNARK is a succinct, noninteractive zeroknowledge proof which facilitates the public verifiability of the proof of a witness. ZKSNARKs enable the prover to convince the verifier on any nondeterministic decision circuits (NPstatements) 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 ZKSNARK scheme.

ZKSNARK toolchain: ZKSNARK uses a trick to convert any NPstatement to a circuit satisfiability problem (Vitalik’s QAP).
 Next, the NPstatement is converted to a nondeterministic 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 NPstatement 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}^{ml}, 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 ZKSNARK 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 ZKSNARK 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 ZKSNARK toolchain. (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 ZKSNARK proof system. We model the nondeterministic 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 ZKSNARK 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

NPstatement 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 NPstatement 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 (256bits) matches the corresponding public key y_i (256bits xcoordinate and 256bits ycoordinate). 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 TableII.

Proof of Assets Protocol:
 We propose the ZKSNARK 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 NPstatement 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 ZKSNARK 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 sciprlab.

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 ZKSNARK 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™ i99900K 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 ZKSNARK 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 ZKSNARK 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 highend 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 FollowUps
 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 ZKSNARK framework.
 We intend to combine these proof of assets protocols with proof of liabilities by proving the membership of customer funds using the setmembership proofs and ZKSNARK 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.