What methods can an exchange website use to prove that it actually has all its users' bitcoins?
These are the requirements:
User privacy is a must. No one should be able to tell how many bitcoins an account has (besides his own).
Total number of accounts should be kept secret.
Total number of bitcoins should be kept secret (if possible).
I've came across gmaxwell's transcript but it seems to lack many core details and I couldn't really grasp it in it's entirety.
We start out with the exchange having two things. It has a set of Bitcoin addresses that it owns, each of which has some balance. It also has a set of accounts, each of which it owes some number of Bitcoin to. The objective is to prove that the exchange controls each Bitcoin address on that list and that the total of all account debts is less than the total balance of all accounts, without revealing anyone's balance to anyone else or any totals.
To do this, the exchange must first assign accounts to Bitcoin addresses such that no single address is overspent. This may require moving Bitcoins around. Now, the exchange assembles a giant merkle radix tree. From the root are inner nodes that are indexed by the Bitcoin address they link to. When you reach a Bitcoin address, the nodes contains balances, so if an address contains, say, 10 Bitcoins, the child nodes have balances that add up to no more than 10. Off the balance nodes are account nodes -- these hold the individual user accounts. Each user account node is signed with the key corresponding to the Bitcoin address.
The exchange now publishes the hash of the tip of this tree. Any user who wishes to challenge the exchange will be given the following:
Every node that leads to their account node.
Every other inner node that hangs off the address node their account node hangs off.
This doesn't tell them any totals, since they have no address nodes but the one their account is assigned to. This doesn't let them see anyone else's balance, since they only have their own account node.
They can now confirm that there is a real Bitcoin address that the exchange controls (because their account node is signed with that key) and that a portion of that balance equal to what they are owed has been uniquely assigned to them.
It might not have been there at the point you read it, since I've been adding to it lately, but there's an accompanying page with pretty diagrams, implementations and implementation notes which will probably be clearer.
(I'd add this as a comment but don't have the reputation.)
This is quite late but we actually wrote a paper on exactly this topic:
https://freedom-to-tinker.com/2015/10/26/provisions-how-bitcoin-exchanges-can-prove-their-solvency/
Bitcoin exchanges can proof solvency while maintaining privacy for both themselves and their customers:
In fact non of the customers balances nor the exchanges addresses or the total number of bitcoin stored at the exchange are revealed.
A binary tree is constructed at a particular point in time, such that the account ID and account balance of each user is recorded a leaf node, and each parent node contains the sum of account values of its children, then the root node is the total account balance at that time.
The exchange then hashes the data in each leaf node, and for each parent node calculates the hash of the concatenation of hashes for its children (like a merkel tree), and finally publishes the merkel root hash.
If any user wants to challenge the authenticity of the hash, the exchange then reveals to the user of all the hashes and the node balance (but not the account IDs) belonging to the nodes on the path of the binary tree between the root and the leaf node associated with the user's account, and the hashes of the immediate sibling nodes, so user can verify that the merkle hash is indeed calculated correctly using his true account balance.
