https://iwilcox.me.uk/2014/proving-bitcoin-reservesProving Your Bitcoin Reserves
Seeing as Coindesk are pointing to this with the link text “Greg Maxwell”, I’d like to make clear from the outset: this page is just Zak Wilcox (me) describing Greg’s idea using more words and diagrams. I also wrote one of the implementations of it, and helped develop an informal standard for it. All mistakes are mine, not Greg Maxwell’s/Peter Todd’s.
Summary
Given the historical tendency of exchanges/wallet sites to be suspected of holding only a fraction of customers’ Bitcoin, it’s becoming important to customers of these sites to be able to verify these sites really hold the bitcoins they claim to. It’s (theoretically) fairly straightforward to do so without revealing too much about customers using a Merkle tree-based technique, although there are quite a few practical considerations and limitations to take into account and the system described relies on customers actually bothering to check.
Presence of this feature does not affect the standard advice: do not leave coins in third-party control for any longer than necessary.
Outline
Still some stubs to fill out; bear with me.
Preamble
Simple flat listings of accounts/balances
The Merkle approach to proving liabilities
Properties (stub)
Details
Common concerns/pitfalls (stub)
Implementations
Proving assets
A survey of which exchanges/wallets are offering what auditability
Preamble
In the context I heard it, I think this was compared to a trend towards provably fair gambling becoming a standard on betting sites. Wouldn’t it be great if this became standard to the degree that customers could (and would) avoid exchanges that didn’t offer it? Consider asking your exchange whether they’d do this, and if not, how they do guarantee they hold their stated fraction.
A side-effect of implementing any proof is that customers have somewhat greater assurance that their exchange is reconciling their accounts to some degree, at some interval. This can be important if accounting is thrown off by some node/accounting implementation bug, as happened in the reference client when actors unknown started deliberately submitting mutated (“malleated”) versions of transactions on a significant scale.
This page is a work in progress and text will come and go, assertions be made and replaced with contradictions, until it settles down. It uses the term ‘exchange’ to cover anyone holding, and with sufficient keys to spend, coins on your behalf without your involvement; that includes many web wallets, betting sites, escrow-based trading sites and probably other types too. The term ‘evil exchange’ means an exchange determined to hold reserves totalling less than its stated fraction of obligations.
Simple flat listings of accounts/balances
If an exchange’s users are informed about and accepting of the privacy implications, and if the business is comfortable that information about the number of customers and their balances is neither commercially sensitive nor a security risk, the exchange can publish a flat list of the balance of every account. To maximise privacy without complicating the implementation too much, the exchange could list balance, hash(login . nonce) for each account (notes in the Merkle description below explain the considerations for login and nonce). As with the Merkle description below, the signed list would need to be published in such a way that customers could be sure they were all checking their balances against the same information even if the exchange were evil.
The Merkle approach to proving liabilities
Timeline:
2013-03-01: Greg Maxwell and Peter Todd discuss the problem and solution (starting from “<@petertodd> OK, so there’s a goal: an library for auditable off-chain transactions.”)
2013-05-08: I hear of the idea from Greg Maxwell and publish the transcript
2013-05-18: Peter Todd describes it in a talk at the Bitcoin 2013 Conference
2014-02: MtGox suspends withdrawals, causing provability of solvency to become a hot topic
All mistakes are mine, not Greg’s/Peter’s.
Properties of the Merkle approach
Aim: an abundantly clear picture of what the Merkle approach does/doesn’t (and what any approach can at best) achieve, to minimise misunderstandings.
Presence of this feature does not affect the standard advice: do not leave coins in third-party control for any longer than necessary.
This system only works if a significant proportion of customers regularly carry out the check they’re empowered to perform.
This system doesn’t aim to give a customer a way to make a verifiable public complaint about a disagreement between them and a competently evil exchange
- . It merely gives you the means check your own belief of the exchange’s liability/obligation to you is included in their publicly declared one, and to let you make an informed decision about whether to continue doing business with them if those numbers differ.
While it may make long cons and hiding of thefts much more difficult, this system doesn’t protect against (claimed) theft of coins from an exchange, nor against an evil exchange absconding with customer funds.
- A competently evil exchange would be careful not to simultaneously tell you it owed you coins and omit them from published liabilities. It would instead just deny all knowledge of your deposit there, and proving that sort of thing false/true is outside the scope of this page. However, you could make a verifiable complaint if an incompetently evil exchange told you they held 100BTC of yours but published its liability to you as 50BTC, or 0BTC, or pretended it didn’t know you.
Details of the Merkle approach
(See also the short/focussed and optionally the longer, more exploratory IRC transcripts, but the description below should now be useable alone.)
Suppose customers use their e-mail address as the unique-to-customer part (collisions here are pretty unlikely) and the accounts database looks like:
E-mail Balance
satoshi@example.com 3333
gavin@example.com 1
pieter@example.com 42
nils@example.com 0
jeff@example.com 50
wladimir@example.com 600
greg@example.com 2.718282
Customers are assigned random nonces. (To keep examples small here, I’m using much shorter nonces than you’d use in practice.)
E-mail Balance Nonce (hex)
satoshi@example.com 3333 ab00
gavin@example.com 1 40ed
pieter@example.com 42 b569
nils@example.com 0 70d1
jeff@example.com 50 457a
wladimir@example.com 600 3fb3
greg@example.com 2.718282 33ad
Hashes are computed over the concatenated fields. To keep diagrams practical here, I’m stringifying all inputs and taking only the first 4 bytes of the result, i.e.:
hexstr(
firstfourbytes(
sha256(
concat( str(e-mail), str(balance), hexstr(nonce) )
)
)
)
So for the first account:
hexstr( firstfourbytes( sha256( "
satoshi@example.com3333ab00" ))) = e4fd9d12
(A real implementation would probably feed binary encodings of balance and nonce to the hash function and would insert a separator between each field to eliminate room for clever overlaps that might let an evil exchange present the same node to multiple customers. The only reason I haven’t used separators here is that I’d have to redraw the original diagram.)
E-mail Balance Nonce (hex) Hash
satoshi@example.com 3333 ab00 e4fd9d12
gavin@example.com 1 40ed 60248b27
pieter@example.com 42 b569 174c7c2d
nils@example.com 0 70d1 12aceafd
jeff@example.com 50 457a e1bb96c1
wladimir@example.com 600 3fb3 a2cec836
greg@example.com 2.718282 33ad ab50f328
Accounts are then inserted as leaves into a binary tree connected by incomplete interior nodes. The tree can be arranged arbitrarily both in terms of shape and placement of customers, although if the tree is always balanced and random a customer could roughly infer the total number of customers.
hen internal nodes’ values are computed using the node combiner. Again, for simplicity I’m stringifying/encoding/truncating. The combination of the leftmost pair of leaves would be calculated as:
parent.sum = left.sum + right.sum = 2.718282 + 1 = 3.718282
parent.hash = firstfourbytes( sha256( concat( str(parent.sum), hexstr(left.hash), hexstr(right.hash) )))
= firstfourbytes( sha256( "3.718282ab50f32860248b27" ))
= firstfourbytes( 4fdd5968686c6a8f68b10579fbeaefcbde45d4fe8b0023861e937fc95daaeb11 )
= 4fdd5968
After combining all nodes
In this tiny example, the path-to-root is almost as big as publishing a flat list of accounts — but more private and less commercially revealing. The path-to-root grows less quickly than a flat list would though. To give Satoshi (balance 3333) his path-to-root, the exchange would extract the following part of the tree:
Actually the exchange need only provide Satoshi with his nonce and the nodes with bold boxes; everything else can (and should) be provided by the user or computed during checking, and it’s more compact. My Clojure implementation and Olivier’s JS one both take this approach.
To ensure that an evil exchange couldn’t tell two customers with identical balances that the same single node represents them (i.e. give them the same path-to-root), each leaf hash should include an input unique to the customer. This is probably best chosen by the customer to maximise uniqueness. If customer ID were used then an evil exchange could give multiple customers the same ID, so it’s not ideal. If login name were used, an evil exchange could exploit collisions.
To ensure that customers can’t infer things about other nodes they see on the path-to-root they’re given, each leaf hash should include a nonce input that’s random and known only to the exchange and the customer. Otherwise a customer might combine guessed balances with known/guessed unique-to-customer inputs, to link the two together and follow them over time. Provided this nonce has enough good entropy, the unique-to-customer input above can be public. A fresh nonce should be generated for each customer for each declaration of assets/liabilities.
An evil exchange can play a similar customer pairing trick if hashes don’t change when sibling balances swap places. Either leaf hashes should include the balance, as above, or internal hashes should include both child balances unsummed. If neither hash meets this constraint then the evil exchange could pair two customers with identical balances as siblings and feed different versions of the tree to each. For example, suppose:
the leaf hash input is crc32( join("|", name, nonce ) )
the internal hash input is crc32( join("|", str(left.sum + right.sum), hexstr(left.hash), hexstr(right.hash) ) )
there are only two users:
user tyler has nonce “turtle” and a balance of 100
user cameron has nonce “canary” and a balance of 100
The evil exchange gives tyler this valid tree:
root: sum: 100; hash: crc32( join(“|”, str(100 + 0), “01C29E82”, “5A486B26” )) = crc32( “100|01C29E82|5A486B26” ) = F38E7221
left (you): sum: 100; hash: crc32( “tyler|turtle” ) = 01C29E82
right: sum: 0; hash: crc32( “cameron|canary” ) = 5A486B26
It can simultaneously give cameron this valid tree:
root: sum: 100; hash: crc32( join(“|”, str(0 + 100), “01C29E82”, “5A486B26” )) = crc32( “100|01C29E82|5A486B26” ) = F38E7221
left: sum: 0; hash: crc32( “tyler|turtle” ) = 01C29E82
right (you): sum: 100; hash: crc32( “cameron|canary” ) = 5A486B26
Both users are assured their balance is declared in the liability tree yet the exchange only needs to prove assets of 100.
Each time the exchange publishes a liability tree hashroot, customers want to maximise the number of checks (i.e. the chance of detecting underdeclaration of liabilities). Customers also want hashroots published frequently enough to make it impractical for an evil exchange to reduce assets below stated fractions inbetween asset/liability declarations. An evil exchange would want to minimise the window for checking and publish only the latest hashroot. In practice perhaps these factors would find a common ground at an interval of a day/week/month or so, although in theory a really good exchange could sign and publish all historical hashroots and e-mail out each customer’s path-to-root to them, and a really good customer could check their path-to-root asynchronously and never leave a tree unchecked.
An evil exchange might want to provide a unique, entirely fabricated path-to-root to each customer, in which the only genuine node was the customer’s own and the tree underdeclared liabilities. A good exchange would publish the hashroot by some agreed medium that all customers could access and be sure to have the same view of. One way might be for the exchange to submit a transaction to the network each time which spent to the same, well-publicised address, and which included an OP_RETURN output that included the signed hashroot. (While such outputs are generally considered poor use of a shared resource, at the rate of a couple of hundred bytes or so each day per exchange, this would be pretty insignificant; however, there are other ways to accomplish this.)
Greg Maxwell points out that it’s possible to implement this protocol under a zero knowledge proof and achieve zero information leakage with the right techniques, although that’s substantially more complex to implement. (If you’re working on doing that, you should contact Greg since he knows how to keep ECDSA verification outside of the ZKP).
Common concerns/pitfalls
Aim: address most common “but couldn’t the exchange just …” objections and non-obvious implementation details that would weaken it.
For now: the worry I’ve seen most often expressed is of the exchange falsely zeroing balances of dormant accounts whose owners won’t check, and/or introducing fake accounts with negative balances, in leaves where that could be hidden; gmaxwell addresses this in discussions on HN (1, 2, 3) and Reddit.
Implementations
Python: Nick/OnTheMargin/ConceptPending/CryptX.io’s implementation.
JavaScript:
Olivier Lalonde’s implementation (also packaged on npmjs.org) which fits into a wider solvency proof framework. Olivier also proposes a (work-in-progress) serialisation format which would make interoperability between publishers/checkers easier and allow implementations to share tests.
ConceptPending’s implementation also now includes client-side verification code in JS (as well as the original Python).
Clojure: My implementation, accepting the accounts.json part of the serialisation format and (so far) producing complete trees only.
C++:
Bifubao‘s implementation.
Kraken‘s implementation.
Ruby: Jan Han Xie’s implementation for open source engine/exchange peat.io.
Proving control of assets
The intuitive and straightforward solution is to sign a statement of ownership with all relevant private keys. Olivier Lalonde wrote an implementation of this. You’d want the statement to include some information only known recently to demonstrate that the signature was made recently, to ensure signatures hadn’t been generated ahead of time on cold storage coins for which keys had been lost; the last few block heights and hashes would be ideal. Customers would verify the signature and that the UTXOs spendable with the keys amounted to the stated fraction of the declared obligations (or more).
Most exchanges would probably already doing signmessage using keys in the hotwallet, so will already be doing a little better anyway: demonstrating that they pay out withdrawals using (some subset of) those UTXOs spendable using the same key(s) used for signmessage.
This might be open to a “signing as a service” attack where an evil exchange would pay someone else holding keys to a lot of coins (say, the Winklevii) to sign a statement with keys able to spend the same amount as the declared assets but which the exchange had no access to, or access to only part of.
However, while there may be elaborate (and probably impractical) protocols that could prove direct, exclusive ownership of the private keys, there are rapidly diminishing returns to proving much more than (possibly indirect) signing control, because it doesn’t prove the exchange is willing to return the coins, only that it could if it wanted to — it can never protect against the exchange absconding (or the deal with the Winklevii ending) the moment after the latest proof was obtained.
Ultimately there’s only one foolproof way for an exchange to prove that it’s both able and willing to return all assets on demand: return them all at once. Exchanges couldn’t do this without a break in trading, but it’s possible to send all coins to previously established 1-of-2 escrow addresses where the exchange holds one of the keys and the customer holds the other. The exchange could let the transaction gain some fixed number of confirmations; if the customer spent them during this time, that would be considered like any other withdrawal; if not, they’d be automatically sent back to the hot wallet. This would likely be incompatible with daily withdrawal limits some exchanges impose in order to comply with money laundering regulations, though, at least for larger deposits.
Who’s using what proof of reserves
Comboy of Bitcoinity has encouraged people to ask their exchanges for this and has offered a bounty of free promotion above his live charts (replacing the existing “This place is waiting for some serious exchange” placeholder).
Bifubao: a cofounder of this Chinese wallet site (the classic shared wallet kind) e-mailed to say it will shortly go live using the Merkle tree approach; unfortunately I don’t speak/read any Chinese so can’t check the wallet itself out, but they’ve open-sourced some code to produce and to check their tree. They’ll use signmessage to prove assets, but on their cold wallet only (at least to begin with).
Bitalo has said their multisig approach means you don’t need this; I’ve not looked into it but the most straightforward implementation of multisig-based wallets, where you have two keys and the wallet site has a third and all transactions require 2-of-3, should let you verify they hold your funds.
BitBargain.co.uk provides a flat list declaration of anonymised liabilities and uses signmessage to prove control of corresponding hot/cold assets, as of 2014-03-05. The declaration is only directly available to sellers — the biggest coinholders there — but buyers can ask any seller to verify that a balance is included in the liabilities list. BitBargain openly and actively discourages users from keeping coins on the site, charging buyers a (very small, declared) storage fee after some time.
BitGo appears to use a 2-of-3 system like Bitalo.
BitPay: jgarzik said (2014-03-04) “As a payment processor and not a wallet, BitPay pays out as soon as possible, aiming for zero reserves. BitPay really does not want to hold cash or bitcoins for any length of time. For USD, we pay out within 24 hours, sometimes sooner. For BTC, the same. We hold funds for hours at most.”
Bitstamp said “Bitstamp is now performing quarterly financial audits and will post our financial reports on our web site.” on 2014-02-25. On 2014-03-06 Bitstamp made a statement that a nameless third party carried out an audit 3 months earlier (November 22nd/23rd 2013) and found no problems, but since they don’t name the auditor and the report by the auditor remains unpublished, customers have no way to decide whether they trust the auditor or the audit. If the statement from Firestartr were signed in a verifiable way by them, and if you had reason to trust Firestartr, it might count for something; without that, it essentially means nothing. (It doesn’t seem to be possible to independently archive the solvency article or Firestartr statements, probably owing to their use of Incapsula.)
Bittylicious.co.uk said (2014-03-04) “No concrete plans but when some sort of [best practice is available], I certainly will consider it” and added that coins are only held on the site on behalf of sellers, not as a general wallet site.
BitQuick asks sellers to fund each offer separately and completely before it’s live, and BitQuick now publishes the deposit address used to fund any offer you can see on their books. This appears solid from the PoV of verifying an offer is included in declared obligations, although as buyers deposit to sellers’ bank accounts, presumably including a name they’re given, buyers can presumably connect the name to the addresses used to fund the offer, which is hardly private. They still need to be signing to prove they hold the reserves, I think; this may also be open to a “signing-as-a-service” subversion otherwise.
BitX: essentially “just trust us”: “we would like to confirm that BitX does indeed keep a full reserve of all user balances”. Yeah, well, worried Gox customers were told “coins are safe” as late as 24th Feb (by support) and 8th Feb (by management, in person).
Buttercoin: Benn Hoffman said “We’re also working out the details of how to prove that the amount we hold is equal to the deposits we’ve received (less withdrawals), just have to do it without compromising customer privacy.” and indicated an interest in the Merkle approach (“It’s mostly just a matter of figuring out how to integrate it and having the time to do it.”).
Coinbase decided to get an external spot-audit done; I can’t resist drawing a parallel to MtGox’s invitation to Roger Ver. I’ve no reason to mistrust Antonopoulos, but then I’ve no reason to trust him, either; if I were a Coinbase customer or ever planned to be, this wouldn’t reassure me much.
Coinfloor.co.uk said [“Coinfloor’s system holds 100% of funds in cold storage and each withdrawal is [multisig]-signed by 3 people within Coinfloor […]. Our policy prevents any unintended withdrawals from happening and insures against a loss of client funds, either via internal theft, external theft/coercion or poor handling of private keys.”](
http://blog.coinfloor.co.uk/post/78226840526/coinfloors-bitcoin-security); this doesn’t really tell you anything useful (100% of liabilities, or just of the fraction they hold? One person could emulate 3-of-n, and despite use of the word “policy” I interpet “insures against” as “prevents”, not as “we insure your deposits against loss”.) It doesn’t follow that you could verify the assets/liabilities so I think this currently amounts to “trust us”, although this announcement pre-dates Gox’s public solvency issues so perhaps there’s more to come from Coinfloor.
CoinKite claims to let you verify your balance somehow; presumably they’re reusing addresses, have an address per customer and will signmessage for you on demand? I’m not a customer so probably can’t usefully test and haven’t looked into it, but please read their description.
Coinsetter expressed reservations about the Merkle approach, saying “[…] we feel it has limitations. For instance, although it does a reasonable job of red flagging fraudulent accounting, it doesn’t cryptographically tie accounting balances to actual assets.” They invited ideas and implementations from the community. At first glance their objection seems to boil down to “fungibility”, but I’m sure I’m missing something.
CryptX.io has said it will launch with support for the Merkle approach and has provided an implementation in Python.
FYBSE: response on comboy’s post was a disappointing “if you have any doubts, just e-mail us”, missing the point. As said above for BitX: worried Gox customers were told “coins are safe” as late as 24th Feb (by support) and 8th Feb (by management, in person).
Justcoin seemed interested but non-committal.
Just-Dice: ‘dooglus’ said “I’ve been proving solvency by publishing a complete list of account balances” but seemed interested in the more private Merkle approach.
Kraken: Jesse responded that they didn’t feel the transparency of the Merkle approach was worth the privacy trade-off, saying they prefer external audit, expected early in the week starting March 3rd (I’m not sure by what method). He also stated explicitly that they strictly separate client funds (i.e. they do not commingle). Update 2013-03-23: they appear to have started work on a C++ implementation.
peat.io: (in beta) Implemented the Merkle proof-of-liabilities 2014-03-18.
TrustedCoin appears to use a 2-of-3 system like Bitalo/BitGo.
To Do
more on hiding negative balances:
extent to which it’s a problem
importance of delivering proofs unsolicited
proof-of-fairness-like countermeasures to randomise the tree layout (I expect there’s a way for the exchange to commit to a layout being random, and for a customer to verify that their node was placed using that randomness, in such a way that exchanges would really struggle to falsely zero out dormant accounts, but I’ve not thought it through)
use CRC32 in examples (easier to read, more clearly a toy) and rerender diagrams
review more implementations
include serialisation proposal from olalonde
review more uses
refresh survey; read and update, or follow:
Coinkite’s updated posting
Bifubao’s dedicated blog post — note though that at one point they were, and they may still be, publishing the entire tree which means there’s no privacy benefit to using Merkle trees (you might as well publish a flat list).
CleverCoin, in case they add it
Kraken did a couple of asset audits paired with Merkle declarations of liabilities; let’s hope they’re heading towards automated, more frequent asset proofs.
796.com provides partial proof of assets
Bitfinex did the same kind of audit as Kraken
diagram-ify no-balance-in-leaf-hash pairing
expand on need for separators
Dotty-ize/Graphviz-ize/rhizome-ize olalonde’s test data for a less noddy example tree
Revise and uncomment section about best practices, being to push proofs out rather than let users tell the exchange who is checking and who is not, since that info could be used by an evil exchange to hide negative balances near non-checking/dormant accounts in the tree
Point out that PRNGs not explicitly described as secure should be avoided for nonces, and that ideally nonces should be assigned before leaves are randomly distributed through the tree so that users don’t see any sequentially generated RNG output
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.0 Generic License.
