Permalink
Switch branches/tags
Nothing to show
Find file Copy path
7b46148 Jun 3, 2018
2 contributors

Users who have contributed to this file

@prdn @kesar
58 lines (39 sloc) 4.84 KB

BIP-001: Proof of Solvency, Custody and Off-chain Delegated Proof of Vote

Changelog

  • 2018-04-30: rev.1 published
  • 2018-06-02: rev.1 expanded

Authors

Goals

  • Demonstrate solvency and custody for a certain crypto-currency / digital asset with a transparent and mathematical proof
  • Protect customers' privacy
  • Deliver a transparent vote delegation system for centralised / non-fully-onchain entities

Proposal

  • Every account balance is split into random buckets, maybe within a range that we can determine empirically from Exchange user data, to hide the exact user balance from other users, and anonymise individual users and their wealth.
  • Each account is assigned a asym. keypair per bucket, where Exchange signs the value in the bucket and then shares the key pair confidentially with the user account. The secret key allows the user to prove that they own a public key in case of a dispute.
  • All signed values are published in a public ledger, akin to a Merkle-tree. This Merkle-tree is a tree where each node contains the sum of their children, and ultimately, at the root contains the total sum of the tree. Lookup of a specific node is efficient in time/memory. This tree can be rebuild periodically using the above steps. A user can check their buckets efficiently and verify that the keys they have available are only ever used to sign once.
  • Users can choose to publish their list of public keys, so other users can check that they were not given the same public key. This also incetivices Exchange to not give two users the same public key, as this discovery would be catastrophic to their reputation, even if the chance was small. The more users choose to publish their keys, the higher the confidence in the buckets representing actual users.
  • The top sum needs to be externally verifiable by users. One idea could be to reference enough wallets on the blockchain, so their sum is greater than or equal to the purported sum in the Merkle-tree.
  • One thing to note is that splitting into random buckets is against the game theory optimal strategy for Exchange, but is a trade-off between user privacy and trust in Exchange. It would be more trustworthy the less buckets are in the feed as it is against Exchange interest to report very few users, but the tradeoff is how to keep users exact balance secret.

Future, speculative enhancements

  • Assuming a Merkle-tree, rebuild periodically, but abandon the idea of buckets, it may be possible use homomorphic encryption or zero-knowledge proofs to show that each user has a certain balance, without revealing the exact balance to others than themselves, but design a way such that the root sum can be verified by anybody. Each node should still be able to be tied to an actual user, so they can choose to publish that a node represents them, without revealing their wealth.
  • Assuming a Merkle-tree, but acting as a feed, and keeping the ideas of buckets, we could aggregate daily transaction changes on a user basis and publish negative entries to the Merkle-tree, so it could be updated over time instead of being rebuilt. Extra care would need to be taken in adding noise as to not reveal precise Exchange activity.

Other Applications

Off-chain Delegated Proof of Vote

  • Every account/user can vote for a proposal using his account balance as a stake.
  • A user can split / weight his stake across multiple available options.
  • The user voted option(s) is attached as a signed payload to the relative bucket(s). A single voted option can be split across multiple buckets.

Implementation

  • Antani : official codebase
  • Ballot : implementation of Bitfinex transparent Proof of Liabilities and Delegated Voting system

References

  • Gregory Maxwell : original idea. Similar solution but with limitations. Full tree is not supposed to be publicly available, otherwise the size of each account would be exposed. Even without revealing the full tree, given a user path, siblings nodes leak enough informations to reconstruct all the account balances of the subtree. BIP-001 allows Exchange to publish the full tree while making hard to aggregate and correlate buckets to the user accounts.
  • https://eprint.iacr.org/2015/1008.pdf : more comprehensive solution, that completely hides account balances and total Exchange liabilities. While it's a really robust and complete approach, Exchange holdings are stored on blockchains, often in aggregated cold wallets and quite easy to track down. This consideration removed the requirement of hiding total Exchange liabilities. Also our approach is more suited to support extensions like Vote Delegation.