Blind Solvency Proof Scheme

Hi all, this is my first post here. I have been working on a scheme and a related set of tools that an exchange (shared wallet) can use to prove they are solvent within reasonable certainty while protecting the privacy of its user. The scheme is based on gmaxwell's "prove-how-(non)-fractional-your-Bitcoin-reserves-are scheme". (https://iwilcox.me.uk/2014/nofrac-orig).

https://raw.github.com/olalonde/solvency-verifier-extension/master/docs/screenshot.png

Github repository: https://github.com/olalonde/blind-solvency-proof

The specification is still a draft and improvements/criticism/pull requests are welcome. A related white paper will be published some time next week elaborating on the concepts and introducing some new ones. Please use Github issues for technical issues.

Show your support: 1ECyyu39RtDNAuk3HRCRWwD4syBF2ZGzdx

There are 3 components to the scheme: liability proof, asset proof and solvency verification.

Liability proof

https://github.com/olalonde/blind-liability-proof

The liability proof is done by widely publishing the root of the proof tree and distributing partial trees to your users so they can verify they were included in the tree.

Complete proof tree

The complete proof tree is a binary tree where the leaf nodes represent all the user accounts and the interior nodes generated using the NodeCombiner function described below.

The complete tree should be kept private by the operator in order to protect the privacy of its users. Only the root node should be puslished publicly and each individual user should have private access to their own partial proof tree.

Interior node (NodeCombiner function)

Interior nodes are generated using the NodeCombiner function described below.

The node's value is equal to the sum of its two child node's values.

The node's hash is equal to the sha256 of its value concatenated with its child's hashes.

Code:

function NodeCombiner (left_node, right_node) {
  var n = {};
  n.value = left_node.value + right_node.value;
  n.hash = sha256((left_node.value + right_node.value) + '' + left_node.hash + '' + right_node.hash);
  return n;
}

Leaf node

Leaf nodes represent user accounts. They possess the following values:

user: A unique identifier for the user. It is necessary for a user to assess the uniqueness of this value so it is recommended to use their username or email.
nonce: A random nonce to prevent its neighboor node from discovering its user value
value: The user's balance.
hash: A sha256 hash of user concanetated with the nonce.

Root node

The root node of the tree like all interior nodes possesses a hash and a value. This data must be published publicly as a way to prove that all users are part of the same proof tree.

Partial proof tree

A partial proof contains only the nodes from the complete root a given user needs to verify he was included in the tree.

It can be generated by starting from the user's leaf node and moving up the tree until reaching the root node. Then the siblings of each selected node on the path must be added to the tree. The user's leaf sibling which is also a leaf node must be stripped of its user and nonce values so that only the hash and value remain.

Partial trees should be disclosed privately to each individual users so they can verify the proof.

Asset proof

https://github.com/olalonde/bitcon-asset-proof

At the moment, the asset proof is simply done with signing a descriptive message using all your private keys. This method has significant limitations and I would love to hear improvement/alternative suggestions.

Solvency verification

https://github.com/olalonde/solvency-verifier-extension

The solvency verification is done by:

1) Verifying the liability proof
2) Verifying the asset proof
3) Verifying that assets - liabilities >= 0

The Chrome extension currently has some limitations. For one, users must manually verify with other users that they were given the same root hash value. They must also verify that the balance used in the liability proof is correct.

References

Special thanks to gmaxwell for his help on IRC.

IRC log: https://iwilcox.me.uk/2014/nofrac-orig
HN thread: https://news.ycombinator.com/item?id=7277865
Reddit thread: http://www.reddit.com/r/Bitcoin/comments/1yzil4/i_implemented_gmaxwells/

DISCLAIMER: This scheme is a draft and subject to change.

Feedback, questions and constructive criticism are welcome!