It is possible for an exchange to prove their total reserves using a Merkle tree approach, see
here for the thread and
here for a description.
With the Merkle tree system, it is possible to prove that the total of all the account balances are equal to the sum in the root of the tree. This rests on the assumption that all users check their balances.
If they don't, then the tree is checked on a random sampling basis.
Confidential transactions enables proving that a list of numbers add up to a given amount without actually saying what the numbers are. The only information about the numbers that it gives is a range proof.
It says "all these numbers add up to X" and for each number "this number is between 0 and N inclusive". This gives all the benefits of the tree sum.
Exchanges could do something like the following.
At close of business on Fridays, the exchange emails all customers an individual message signed with their proof of reserve public key.
As of close of business on XX/YY/20ZZ, you have 22.01234567 coins.
Your customer unique id is 654321.
The blinding factor for your account this week is 4a3...23c715f.
The exchange then publishes a list of ids, balances (in confidential format) and range proofs. It also has to publish the total of the balances and the sum of the blinding factors.
As of close of business on XX/YY/20ZZ, our customers balances are as follows:
000001, <balance as compressed point>, <range proof>
000002, <balance as compressed point>, <range proof>
....
071234, <balance as compressed point>, <range proof>
The total balance is 96532.87654321.
The blinding factor sum is <32 byte big endian integer>.
This combined message should also be signed by the exchange's proof of reserve public key.
This weekly document can be verified by anyone. Elliptic curve maths is slower than just checking hashes, so it would be slower than the tree system. On the plus side, the entire sum is checked, rather than random sampling of people who actually check the tree. At 10ms per entry, an exchange with 50,000 customers would take less than 10 minutes. At least one of the 50k customers would check it weekly.
This has two advantages over the Merkle approach
- negative balances are impossible [*]
- doesn't leak balance info to neighbors in the tree
By emailing all customers weekly, it means that customers can prove what their reserves should be. Without that, customers who detect fraud might be accused of falsely accusing the exchange.
It makes it easier for customers to get back and check their historical records.
A customer might be dormant on the exchange, but still vigilant in checking that their email was properly signed.
This makes it much harder for the exchange to pick out which customer balances that they can tamper with safely. Even if they find a "real" dormant account, there is always the risk that a customer might check their emails.
[
*] With the sum-tree, they can be hidden by collusion with customers.
