Bitcoin Forum

It is possible for an exchange to prove their total reserves using a Merkle tree approach, see here (https://bitcointalk.org/index.php?topic=669086.0) for the thread and here (https://iwilcox.me.uk/2014/proving-bitcoin-reserves) 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 (https://people.xiph.org/~greg/confidential_values.txt) 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.


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.


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.

Interesting. Certainly a big improvement on Mike Hearn's methodology for auditing Bitstamp reserves (which essentially amounted to Mike doing a public "thumbs up").

Can't seem to find the CT thread, can anyone remember the prerequisites for mainnet CT?

I can't find one either. 

There was a thread (https://bitcointalk.org/index.php?topic=1085436.0) on "compact confidential transactions", which is a different scheme.

It would require a hard fork.  The output value would need to be replaced with a EC points.  You also need range proof support.

The exception is if there is only 1 output.  In that case, you don't need a range proof.

They also embed some encrypted information in transaction so the receiver can handle it.  This doesn't require extra transaction size though.

From memory, the range proofs require 32 bytes per possible output level and a 32 byte initialization value. 

For a 1 bit (2 level) proof, that is 64 + 32 = 96 bytes.  2 bits is 4 levels, so 4 * 32 + 32 = 160.  3 bits is 8 levels which gives 8 * 32 + 32 = 288. 

2 bits (4 levels) has the smallest size per bit (96 vs 80 vs 96).  This means that they use radix-2 in their range proofs.

For 32 bit range proofs, that is 2560 bytes required for the range proof.

For outputs that have less than 32 bits of variation, a smaller range proof can be used.

Actually you can soft-fork CT.  https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2016-January/012194.html

The main challenge is size.  I believe I have a way to reduce the range proof from 2.5kB per proof to 2kB per proof but it is still large.

Mimble Wimble is interesting also in making an aggregatable CT which allows the bloat to be more than reclaimed at least as far as catchup goes. (More total bandwidth used, but less bandwidth to catchup as catchup becomes proportional to UTXO size + a smaller overhead per historic transaction).  Maybe the historic transaction overhead can be removed.

Thread;
https://bitcointalk.org/index.php?topic=1085273.0

Fair enough.  It moves the entire set of CTs into a data structure.  Old clients just verify the total of the confidential transaction outputs.

It is a complex soft fork like segregated witness which adds additional data structures to the blockchain.

Since the "nuclear option" can completely replace the rules with another set of rules, "soft fork" can mean a very extensive change, depending on where you place the line.


Something weird must have happened to the forum's search feature.  "Confidential transactions" was not hitting that thread.

CT for solvency proofs is well known, I posted about it here (someplace) on the liabilities side some time ago.

Whats even more interesting is that private assets side is also possible in Bitcoin today:

http://crypto.stanford.edu/~dabo/pubs/abstracts/provisions.html

Unfortunately there is relatively little interest from most exchanges in these tools.