Proof of solvency and beyond

Switching to dark mode November 19, 2022 View all posts

Special thanks to Balaji Srinivasan and staff at Coinbase, Kraken, and Binance for the discussion.

Whenever a major centralized exchange blows up, a common question that arises is whether or not we can use cryptographic techniques to fix the problem. Rather than relying solely on "fiat" methods like government licensing, auditors, and reviewing the corporate governance and backgrounds of the people running the exchange, exchanges could create evidence cryptographic assets that show that the funds they hold on-chain are sufficient to cover their liabilities to their users.

Even more ambitiously, an exchange could implement a system where it cannot withdraw a depositor's funds at all without their consent. Potentially, we could explore the full spectrum between the aspiring "don't be mean" CEX and the "can't be mean", but for now ineffective and privacy-evading, on-chain DEX. This article will discuss the history of attempts to bring trades one or two steps closer to no trust, the limitations of these techniques, and some newer and more powerful ideas that build on ZK-SNARKs and d other advanced technologies.

Balance Lists and Merkle Trees: Old-Style Proof of Solvency

The first attempts by exchanges to try to cryptographically prove that they are not cheating their users go back quite a long way. In 2011, the then largest Bitcoin exchange, MtGox, proved it had funds by sending a transaction that moved 424,242 BTC to a pre-advertised address. In 2013, discussions began on how to solve the other side of the problem: proving the total size of customer deposits. If you prove that customer deposits are equal to X ("proof of liability") and you prove private key ownership of X coins ("proof of asset"), then you have proof of solvency: you have proven that the exchange has the funds to repay all of its depositors.

The easiest way to prove deposits is to simply post a list of pairs (username, balance). Each user can check that their balance is included in the list, and anyone can check the complete list to see that (i) each balance is non-negative, and (ii) the total sum is the amount claimed. Of course, this breaks privacy, so we can modify the scheme a bit: publish a list of pairs (hash(username, salt), balance) and send each user privately their salt value. But even that leaks sales, and it leaks the pattern of changes in sales. The desire for privacy leads us to the next invention: the Merkle tree technique.

Green: Charlie's Knot. Blue: Nodes that Charlie will receive as part of his proof. Yellow: root node, publicly visible to all.

The Merkle tree technique involves placing the array of customer balances into a Merkle sum tree. In a Merkle sum tree, each node is a (balance, hash) pair. The lower layer leaf nodes represent the balances and salted username hashes of individual customers. In each upper layer node, the balance is the sum of the two balances below, and the hash is the hash of the two nodes below. A Merkle sum proof, like a Merkle proof, is a "branch" of the tree, consisting of the sibling nodes along the path from a leaf to the root.

The exchange would send each user a Merkle sum proof of their balance. The user would then have...