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

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

<p>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:</p>

<ol>
<li><p>Every node that leads to their account node.</p></li>
<li><p>Every other inner node that hangs off the address node their account node hangs off.</p></li>
</ol>

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

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

CC BY-SA 3.0
2014-10-26T09:22:07.463Z
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 K.
CC BY-SA 3.0
2014-10-26T09:23:41.840Z
@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
CC BY-SA 3.0
2014-10-26T09:27:47.257Z
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 K.
CC BY-SA 3.0
2014-10-26T09:29:04.030Z
@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
CC BY-SA 3.0
2014-10-26T09:34:55.247Z
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 K.
CC BY-SA 3.0
2014-10-26T09:37:14.803Z
@AntonA. Read my answer. I've explained precisely how to do that. (I don't know what you mean about cold storage. The whole point is to prove you have sufficient funds in cold storage.)
David Schwartz
CC BY-SA 3.0
2014-10-26T09:38:26.227Z
Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/18160/discussion-between-anton-a-and-david-schwartz).
Emre K.
CC BY-SA 3.0
2014-03-09T06:33:31.517Z
2014-03-09T07:39:56.660Z
2014-03-09T07:39:56.660Z
David Schwartz
<p>It might not have been there at the point you read it, since I've been adding to it lately, but there's an <a href="https://iwilcox.me.uk/2014/proving-bitcoin-reserves" rel="nofollow">accompanying page</a> with pretty diagrams, implementations and implementation notes which will probably be clearer.</p>

<p><em>(I'd add this as a comment but don't have the reputation.)</em></p>

CC BY-SA 3.0
2014-03-13T14:16:58.740Z
2014-03-13T14:16:58.740Z
ZakW
<p>This is quite late but we actually wrote a paper on exactly this topic:</p>

<p><a href="https://freedom-to-tinker.com/2015/10/26/provisions-how-bitcoin-exchanges-can-prove-their-solvency/" rel="nofollow">https://freedom-to-tinker.com/2015/10/26/provisions-how-bitcoin-exchanges-can-prove-their-solvency/</a></p>

<p>Bitcoin exchanges can proof solvency while maintaining privacy for both themselves and their customers: </p>

<p>In fact non of the customers balances nor the exchanges addresses or the total number of bitcoin stored at the exchange are revealed.</p>

CC BY-SA 3.0
2016-10-25T17:00:54.773Z
2016-10-25T17:00:54.773Z
Benedikt Bünz
<p>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. </p>

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

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

CC BY-SA 3.0
2014-03-09T04:38:48.237Z
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
CC BY-SA 3.0
2014-03-09T04:50:39.787Z
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
CC BY-SA 3.0
2014-03-09T04:57:55.457Z
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
CC BY-SA 3.0
2014-03-09T04:21:28.117Z
2014-03-09T04:21:28.117Z
uminatsu
<p>What methods can an exchange website use to prove that it actually has all its users' bitcoins?</p>

<p>These are the requirements:</p>

<ul>
<li><p>User privacy is a must. No one should be able to tell how many bitcoins an account has (besides his own).</p></li>
<li><p>Total number of accounts should be kept secret.</p></li>
<li><p>Total number of bitcoins should be kept secret (if possible).</p></li>
</ul>

<p><sub>I've came across <a href="https://iwilcox.me.uk/2014/nofrac-orig" rel="nofollow">gmaxwell's transcript</a> but it seems to lack many core details and I couldn't really grasp it in it's entirety.</sub></p>

CC BY-SA 3.0
2014-05-24T16:45:18.457Z
Also see https://www.bifubao.com/
Pacerier
<exchanges><cryptography><trust><proof-of-solvency>
How can a bitcoin exchange prove its solvency while maintaining privacy?
Pacerier
# How can a bitcoin exchange prove its solvency while maintaining privacy?

(Asked by: username_0 on 2014-03-09)

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](https://iwilcox.me.uk/2014/nofrac-orig) but it seems to lack many core details and I couldn't really grasp it in it's entirety.

**Tags:** exchanges, cryptography, trust, proof-of-solvency

> **Comments:**
> **username_0**: Also see https://www.bifubao.com/  

---

## 4 answers

### Answer by username_1 on 2014-03-09. Score: 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.

> **Comments:**
> **username_2**: 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.  
> **username_1**: @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?  
> **username_2**: 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.  
> **username_1**: @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.)  
> **username_2**: 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.  
> **username_1**: @AntonA. Read my answer. I've explained precisely how to do that. (I don't know what you mean about cold storage. The whole point is to prove you have sufficient funds in cold storage.)  
> **username_2**: Let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/18160/discussion-between-anton-a-and-username_1-username_1).  

---

### Answer by username_3 on 2014-03-13. Score: 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](https://iwilcox.me.uk/2014/proving-bitcoin-reserves) 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.)*


---

### Answer by username_4 on 2016-10-25. Score: 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.


---

### Answer by username_5 on 2014-03-09. Score: 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.

> **Comments:**
> **username_0**: 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?  
> **username_5**: 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).  
> **username_0**: 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.  

---

