Bitcoin Forum
December 13, 2024, 07:15:11 AM *
News: Latest Bitcoin Core release: 28.0 [Torrent]
 
   Home   Help Search Login Register More  
Pages: [1]
  Print  
Author Topic: Using the confidential transaction sum for proof of reserves  (Read 1218 times)
TierNolan (OP)
Legendary
*
Offline Offline

Activity: 1232
Merit: 1104


View Profile
August 09, 2016, 01:57:28 PM
Merited by ABCbits (1)
 #1

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.

Code:
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.

Code:
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.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
Carlton Banks
Legendary
*
Offline Offline

Activity: 3430
Merit: 3080



View Profile
August 09, 2016, 07:00:49 PM
 #2

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?

Vires in numeris
TierNolan (OP)
Legendary
*
Offline Offline

Activity: 1232
Merit: 1104


View Profile
August 09, 2016, 10:40:40 PM
 #3

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 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.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
adam3us
Sr. Member
****
expert
Offline Offline

Activity: 404
Merit: 362


in bitcoin we trust


View Profile WWW
August 10, 2016, 11:15:37 AM
 #4

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


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.


hashcash, committed transactions, homomorphic values, blind kdf; researching decentralization, scalability and fungibility/anonymity
DumbFruit
Sr. Member
****
Offline Offline

Activity: 433
Merit: 267


View Profile
August 10, 2016, 01:01:09 PM
 #5

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

By their (dumb) fruits shall ye know them indeed...
TierNolan (OP)
Legendary
*
Offline Offline

Activity: 1232
Merit: 1104


View Profile
August 10, 2016, 02:43:11 PM
 #6


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.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
gmaxwell
Moderator
Legendary
*
expert
Offline Offline

Activity: 4284
Merit: 8816



View Profile WWW
August 11, 2016, 10:18:21 AM
Merited by ABCbits (1)
 #7

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.
Pages: [1]
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!