IRC transcript of gmaxwell describing his prove-how-(non)-fractional-your-Bitcoin-reserves-are scheme

Posted: 2014-02-27

Very slightly edited and reordered. I also have a page with more information on implementations, more explicit implementation details, diagrams, pitfalls, asset proofs and a survey of exchanges/wallets who have said they do/will/won’t prove their reserves.

Wednesday 08 May 2013 03:11 BST

<gmaxwell>   iwilcox: the idea is simple enough. Two halves. First you show how
             much funds you have via signmessage for actual coins on the chain.
             Thats easy enough.

<gmaxwell>   Then you need to prove how much you should have. This is a little
             tricker. You could just publish EVERYONE's balances e.g.  by
             account ID but thats undesirable for privacy and commercial reasons.

<gmaxwell>   But I described a way prove how much you should have without doing

<gmaxwell>   Here is how:   Say you have a collection of "nodes",   Each node
             has two fields.  node.value and node.hash.  create a node for
             every account.  E.g. I have 1 BTC, and my accounthash is 0.  so
             value=1 and hash=0.

             [Note: The leaf hash is intended to be H(login .  balance .
              nonce) --- or something with equivalent properties; see my
              detail page linked above for more. --iwilcox]

<gmaxwell>   Now I define a NodeCombiner function:
               node NC(left_node, right_node) = {
                    n = new node;
                    n.value = left_node.value + right_node.value;
                    n.hash = sha256(left_node.value + right_node.value || left_node.hash || right_node.hash;

<gmaxwell>   you take all your users and arrange them in a binary tree, that
             can have any shape you want.. e.g. a whole bunch of interior
             nodes.. ultimately connecting up to some root node.  And you use
             the NodeCombiner function to fill in the values of all the
             interior nodes up the tree.

<Cusipzzz>   each user can verify their balance is covered by site owners
             funds, but can't see the total, or # of accounts?

<gmaxwell>   This is like the merkel trees used for transactions in bitcoin,
             except there is an additional value sum along with the hashes.

<gmaxwell>   The site then publishes the root hash and value widely where
             everyone can see it. ... and when you connect the site gives you
             your account balances and just the interior nodes between you and
             the root so you can verify that your account is included in
             the root but can't tell much about anything else.

             [Note: actually, all the site should give you is the immediate
              children of nodes on the root path, not the nodes themselves;
              see my detail page linked above for more.  --iwilcox]

<gmaxwell>   so it changes the problem from:
                 {prove how much they have, prove how much they should have}
                 {prove how much they have, _say_ how much they should have,
                     prove that your account was included in that total}

<gmaxwell>   one point about this is that it doesn't prevent fractional
             reserve --- but if used well, it prevents *dishonest* fractional

<Cusipzzz>   and doesn't prevent the site owner from going MIA with the full
             reserve funds :)

<iwilcox>    That kind of absconding owner is unlikely to care much for proving
             they don't fractionally-reserve beyond stated fractions.

<gmaxwell>   Cusipzzz: indeed, but it can inhibit long cons or prevent them
             from hiding theft.

<Cusipzzz>   you have to reveal # of accounts? some people would not want to
             reveal nuber of active accounts

<gmaxwell>   nope. not that either