8

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.

Improve this question
1

4 Answers 4

Reset to default
5

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:

  1. Every node that leads to their account node.

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

Improve this answer
7
  • I think it's more useful to focus on proof of cold storage funds. After all, you expect the exchange to forward the balances on the addresses given to users to a cold storage address.
    – Emre Kenci
    Oct 26, 2014 at 9:22
  • @AntonA. Well that's very easy. The exchange can simply provide the list of cold storage addresses it uses, and sign that list with the keys corresponding to each such address. The problem is, say an exchange proves they have 11,000 BTC in cold storage, and they prove that -- how do I know that they don't owe 83,000 BTC to their customers?
    – David Schwartz
    Oct 26, 2014 at 9:23
  • True. Something like this: audit.btctrader.com. But that question remains in your approach as well doesn't it? Because in an exchange, we expect the deposited bitcoins to co-mingle with others. The balances on bitcoin addresses won't be tied to actual user balances.
    – Emre Kenci
    Oct 26, 2014 at 9:27
  • @AntonA. That question does not remain in my approach. It allows the exchange to prove that it really holds a particular amount of funds and that the total amount it owes to all its customers is less than that. (It perfectly well supports a single address holding funds that belong to more than one customer.)
    – David Schwartz
    Oct 26, 2014 at 9:29
  • True. Unless they choose to use a cold storage. What do you think about publishing user balances as a randomized table and give individual users the chance to go and check their balances on that table with the random string generated for their balance. Perhaps you can show a single user's total balance in a random number of rows. If you make that table dynamic for each viewing, you can prevent some privacy issues.
    – Emre Kenci
    Oct 26, 2014 at 9:34
1

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

Improve this answer
1

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.

Improve this answer
0

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.

Improve this answer
3
  • Do you mean that everytime I do a trade on the exchange (e.g. buy/sell 30 BTCs), actual bitcoin transactions need to be made on the blockchain?
    – Pacerier
    Mar 9, 2014 at 4:38
  • 1
    No. This has nothing to do with the blockchain. The proof of solvency just needs to establish two things (1) sum of customer accounts (the liability of the exchange) and (2) a sizable cold storage (the asset of the exchange) at the same time. The merkel tree solves (1), and a signed message verifiable by the cold storage address solves (2).
    – uminatsu
    Mar 9, 2014 at 4:50
  • No I'm trying to look for a solution that does not require publicizing the total number of accounts and bitcoins in the exchange. In other words, all 50k users can themselves prove that their coins exist in the exchange, but they will have no other info besides that, since that is the bare minimum required for audit.
    – Pacerier
    Mar 9, 2014 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.