Research: proof-of-reserves for fully-shielded exchange.

[nathan-at-least]

User story:

An exchange has been a good privacy citizen, receiving all incoming deposits to shielded addresses. How can they prove their reserves without compromising the privacy of users?

• How can the public verify that the exchange does indeed control the reserve total?
• How can a specific user verify that a published reserve total includes their account balance without "double counting" that against other users?
• Can the proof scheme work across multiple private cryptocurrencies traded at the exchange?

Related: This is similar to #77 except it specifically focuses on an exchange offering shielded deposits.

[nathan-at-least]

Here's a stab at a strawman as an existence proof:

Design Overview:

For every user balance, the exchange manages a user-funds z-addr (UFZA). This UFZA is controlled by the exchange on behalf of the user. The exchange provides the Viewing Key for that UFZA to the user. Trades on the exchange between cryptocurrencies must (eventually) "settle" with on-chain UFZA transactions. (This is most likely a killer for real world exchange, but this is just a proof-by-example, so that's acceptable.)

Periodically the exchange publishes a reserves proof which has two parts: A public proof, and per-user proofs.

Reserve Proofs:

The public proof is a new ZKP with public inputs (blockhash, amount, commitment_root). The commitment_root is a compact set membership value where each item is zaddr for each UFZA. The ZKP statement is:

As of block blockhash the amount is the sum of the balance of every UFZA zaddr in the set commitement_root.

The per-user proofs are just the witnesses to the commitment_root for their UFZA zaddrs.

The ZKP proof string along with public inputs are committed to some append-only globally visible record.

Verifying Reserves:

The general public verifies the ZKP proof string against the public parameters. Doing so will require knowing that the public parameter blockhash is indeed a recent valid Zcash block hash. No other out-of-band info is required for this verification.

Individual users needs to verify the general public proof, then they verify that the zaddr of their UFZA is included in the commitment_root given the witness the exchange provided to them.

In order for a user to know their account isn't being "double counted" they must manually watch their UFZA history and ensure it matches their account activity (deposits, withdrawals, and trades). (This part of the example seems the weakest and might be prone to edge cases, like if many users always deposit a similar amount then do not make trades, those users could be tricked with a single UFZA for some period of time.)

Does this strawman meet the requirements? Does it have flaws? If it does meet the requirements, it's an existence proof, and the next step is to just improve the design for realism.