After the MtGox incident, a lot of Bitcoin exchanges started pursuing audits and creating a proof of solvency / liability to prove to their users they remain solvent. While proving that one owns the required amount of coins is fairly easy, I am wondering - has anyone created a generally acceptable protocol for proving how much an exchange owes its customers based on the account balances in their database without revealing users' private information?
Greg Maxwell has described a way in which this is possible using a blind solvency proof, allowing users to verify that their amounts of Bitcoin are being stored by the system without revealing to an outsider what they are and how many users exist in the system. Clients of the service are able to individually prove their own balances in the tree and raise the alarm if they are not included or if the information is not correct, with the tree then becoming a proof of fraud. The scheme pointedly doesn't verify these funds exist and are spendable by the service.
Details about the system have been collected from IRC quotes, and at least two implementations by molecular and olalonde exist on github.
While proving that one owns the required amount of coins is fairly easy
One exchange, BitStamp has taken it upon themselves to try and create their own "proof of reserves" system by periodically (every few months) accumulating all of their Bitcoin holdings into a single output, in an attempt to prove tht they actually hold all the Bitcoin they should. This mirrors something Mt Gox did in 2011 by moving 424242 BTC at the request of users on IRC. In the process, BitStamp is putting themselves at huge risk of losses. Bit flips errors are pretty common in computers, if they have even a single one when signing that transaction all of their customers money will be destroyed. It reduces their customers privacy, opens them up being physically attacked during that period, all sorts of nastiness. It's not really a solved problem, though it looks simple on the outset.
There is no widely agreed upon protocol for proving solvency in Bitcoin.
The first successful protocol describing proofs of solvency is due to Greg Maxwell who described a Merkle-tree-based solution for proving solvency. Maxwell's solution provides proofs logarithmic in size with respect to the number of creditors. Maxwell's protocol is extensively described by Zak Wilcox. It has the advantage of being easy to understand and to implement. Unfortunately, Maxwell's protocol leaks the number and size of creditor accounts as well as the total liabilities of the exchange.
An alternative mechanism of using a trusted auditor has been applied by Mike Hearn on Bitstamp, Stefan Thomas on Kraken, Antonopoulos on Coinbase and others. These verifications rely on centralized trusted third parties and cannot protect against collusion between the services and the auditors, a property generally undesired in decentralized systems such as bitcoin.
The above problem is addressed by Benedict Bünz, etc. on their provisions paper and an implementation is provided. Unfortunately, their proofs are somewhat more convoluted and require slightly more advanced cryptographic tools (specifically zero-knowledge proofs of knowledge). However, they provide trustless verifiability without sacrificing privacy of total funds or account sizes. However, these new developments are not currently applicable to the current bitcoin blockchain, as provisions only works against pay-to-pubkey UTXOs, not pay-to-pubkey-hash UTXOs which are now standard on bitcoin. Pay-to-pubkey-hash transactions can be used against addresses that have been reused or for which the public keys are known. However, current best practices mandate no address reuse, so this requirement is not perfect.
Based on the provisions paper, a zk-SNARKS proof system which can provide for p2pkh transactions is an interesting research problem with ongoing research. It remains to see if it can be implemented efficiently in a way that proofs are concise and quick. The problem of a trusted setup required by SNARKS must also be addressed by such an implementation.