Vitalik: How Can Centralized Exchanges Prove Their Funds?

Whenever a significant centralized exchange collapses, a common question arises: can we use cryptographic technology to solve the problem? Exchanges could create cryptographic proofs showing that the funds they hold on-chain are sufficient to cover their liabilities to users, instead of just relying on “legal” methods like government permissions, auditor reviews, and checking the personal backgrounds of those managing and operating the exchange. Exchanges could establish a system where it’s fundamentally impossible to withdraw depositors’ funds without their consent. Potentially, we could explore the entire spectrum between ambitious, good-hearted CEXs that “do not do bad things” and on-chain DEXs that “cannot do bad things” but are currently inefficient and leak privacy. This article will delve into historical attempts to make transactions closer to trustless, the limitations of these technologies, and some newer, more powerful ideas using ZK-SNARKs and other advanced technologies.

Balance Sheets and Merkle Trees: Old-School Proof of Solvency

The earliest attempts by exchanges to use cryptographic methods to prove they were not defrauding their users can be traced back a long way. In 2011, the largest Bitcoin exchange at the time, MtGox, proved they had funds by transferring 424242 BTC to a pre-announced address. In 2013, discussions began on how to prove the other side of the equation: the total size of customer deposits. If you prove customer deposits equal X (a “liability proof”) and prove ownership of the private keys for X coins (an “asset proof”), you have proof of solvency: you’ve shown the exchange has the funds to repay all depositors.

The simplest method to prove deposits was to publish a list of (username, balance) pairs. Each user could check if their balance was included, and anyone could verify the entire list to ensure (i) each balance is non-negative, and (ii) the total equals the claimed amount. However, this breaches privacy, so a slight modification could be made: publish a list of (hash(username, salt), balance) pairs and privately send each user their salt value. But even this leaks balance information and patterns of balance changes. The desire to protect privacy brings us to the next invention: Merkle tree (also known as hash tree) technology.

Green: Charlie node. Blue: David node, which is also the node that Charlie will receive as part of his proof. Yellow: Root node, publicly displayed to everyone.

Merkle tree technology involves placing a client’s balance sheet into a Merkle sum tree. In this tree, each node is a (balance, hash) pair. The bottom layer leaf nodes represent individual clients’ balances and salted hash values of their usernames. In each higher-level node, the balance is the sum of the two balances below, and the hash value is the hash of the two nodes below. A Merkle sum proof, like a Merkle proof, is a “branch” of the tree, composed of sibling nodes on the path from leaf to root.

Exchanges send each user a Merkle sum proof of their balance to prove their holdings. Users then have an assurance that their balance is correctly included as part of the total. A simple code example can be found here.

Privacy leakage in this design is much lower than in a fully public list and can be further reduced by shuffling branches each time the root is published. However, some privacy leakage still exists. Charlie can know that someone has a balance of 164 ETH, that the sum of two users’ balances is 70 ETH, etc. An attacker controlling many accounts can still learn a lot about the exchange’s users.

A subtle but important aspect of this scheme is the possibility of negative balances: What if an exchange with a customer balance of 1390 ETH only has 890 ETH in reserves and tries to cover the shortfall by adding a -500 ETH balance under a fictitious account in the tree? It turns out this possibility doesn’t break the scheme, although this is precisely why we need Merkle sum trees instead of regular Merkle trees. Suppose Henry is a fictitious account controlled by the exchange, where -500 ETH is placed.

Greta’s proof verification will fail: the exchange will have to offer her Henry’s -500 ETH node, which she will reject as it is invalid. Eve and Fred’s verification will also fail since the total ETH on the intermediate nodes above Henry is -230, rendering them invalid too! To escape theft, the exchange will have to hope that no one on the right half of the entire tree checks their balance proof.

If the exchange can identify users worth 500ETH, and they believe these users either won’t bother to check the proof or won’t be believed when they complain about never receiving a proof, then the exchange can confidently escape punishment for theft. However, the exchange could also achieve the same effect by excluding these users from the tree.

Therefore, for the sole purpose of demonstrating proof of liabilities, Merkle tree technology is essentially as good as the proof-of-liabilities scheme. But its privacy attributes are still not ideal. You can use Merkle trees more cleverly, for instance, by making each satoshi or wei an individual leaf, but ultimately, with more modern techniques, there are better ways to achieve this.

Improving Privacy and Robustness with ZK-SNARKs

ZK-SNARKs are a powerful technology, potentially to cryptography what transformers are to artificial intelligence: a universally potent technology that completely overwhelms a plethora of issues in specific technologies developed decades ago. Naturally, we can use ZK-SNARKs to greatly simplify and enhance the privacy in the proof of liability protocols.

The simplest thing we can do is put all user deposits in a Merkle tree (or more simply, a KZG commitment) and use a ZK-SNARK to prove that all balances in the tree are non-negative and collectively add up to a claimed value. Adding a layer of hashing for privacy, giving each user a Merkle branch (or KZG proof) will not reveal any other users’ balances.

Using KZG commitments is a method to avoid privacy leaks, as it eliminates the need to provide “sibling nodes” as proof. A simple ZK-SNARK can be used to prove the sum of balances and that each balance is non-negative. We can use a specialized ZK-SNARK to prove the sum and non-negativity of balances in the aforementioned KZG. Here’s a simple example that achieves this. We introduce an auxiliary polynomial, which “establishes the bits of each balance” (for illustrative purposes, let’s assume balances are within ), and every 16 positions track a running total with an offset, so the sum is zero only when the actual total is consistent with the declared total. If z is the -128th root of unity, we can prove the following equation.

The first value in an effective setup is 0 0 0 0 0 0 0 0 0 0 1 2 5 10 20 -165 0 0 0 0 0 0 0 0 1 3 6 12 25 50 -300… To understand how such equations can be transformed into polynomial checks and then into ZK-SNARKs, refer to my article on ZK-SNARKs for further explanation here and here . While not an optimal protocol, it indeed demonstrates that cryptographic proofs of this type are not as mysterious these days!

With just a few additional formulas, such systems of constraints can be adapted to more complex scenarios. For instance, in a leveraged trading system, it is acceptable for individual users to have negative balances, provided they have sufficient other assets to cover funds with some collateral. A SNARK can be used to prove this more complex constraint, reassuring users that the exchange will not risk their funds by secretly exempting other users from the rules.

In the longer term, this kind of ZK debt proof could potentially be used not only for customer deposits at exchanges but also for a broader range of loans. Whenever anyone takes a loan, they would put a record into a polynomial or tree containing that loan, with the root of this structure being published on the chain. This would allow anyone seeking a loan to provide ZK proof to lenders that they haven’t borrowed too much from other loans. Ultimately, legal innovations might even make loans committed in this way have a higher priority than uncommitted loans. This leads us in the same direction as an idea discussed in “Decentralized Society: Finding the Soul of Web3“: establishing a concept of negative reputation or collateral on the chain through some form of “soulbound token”.

Proof of Assets

The simplest version of asset proof is the protocol we’ve seen above: to prove you hold X amount of coins, you just need to move X coins at a pre-agreed time or in a transaction that includes the message “These funds belong to Binance” in its data field. To avoid transaction fees, you can alternatively sign an off-chain message; both Bitcoin and Ethereum have standards for off-chain signature messages.

This simple asset proof technique has two practical issues:

1. “Cold storage” processing.

2. Dual use of collateral.

For security reasons, most exchanges keep the majority of their clients’ funds in “cold storage”: on offline computers where transactions need to be manually signed and transferred to the internet. The cold storage setup I once used for personal funds involved a permanently offline computer, generating a QR code containing the signed transaction, which I could scan with my phone. Modern exchange protocols are more complex, often involving multi-party computations between several devices. Given such setups, even an extra message to prove control over an address is an expensive operation!

A transaction can take several paths:

• Maintain a few publicly known long-term addresses. The exchange generates several addresses, publishes proof of ownership for each once, and then reuses these addresses. This is by far the simplest scheme, though it does add some restrictions on how to protect security and privacy.

• Set up many addresses, randomly proving a few. The exchange could have many addresses, perhaps using each only once and retiring them after a transaction. In this case, the exchange might have a protocol to randomly select a few addresses that must be “opened” to prove ownership. Some exchanges have already done something similar with auditors, but in principle, this technique could become a fully automated process.

• More complex ZKP options. For example, an exchange could set all its addresses as 1/2 multi-signatures, where each address’s key is different, and the other is a blinded version of some “major” emergency backup key, stored in a complex but highly secure way, like a 12/16 multi-signature. To protect privacy and avoid exposing its entire set of addresses, an exchange could even run a zero-knowledge proof on the blockchain, proving the total balance of all addresses with this format on the chain.

Another major issue is preventing the dual use of collateral. Exchanges could easily shuttle collateral back and forth between each other for reserve proof, pretending to be solvent when they are not. Ideally, solvency proof would be real-time, updating the proof after every block. If this isn’t practical, a less ideal option is to coordinate a fixed schedule among different exchanges, for example, proving reserves every Tuesday at 14:00 UTC.

The last question is: can we do asset proof on fiat currency? Exchanges don’t just hold cryptocurrencies; they also hold fiat currencies within the banking system. Here, the answer is: yes, but such a process will inevitably rely on the “fiat” trust model: the bank itself can prove balances, auditors can prove balance sheets, etc. Considering fiat cannot be cryptographically verified, this is the best that can be done within that framework, but it’s still worth doing.

Another approach is to cleanly separate an entity that runs the exchange and deals with asset-backed stablecoins like USDC from another entity that handles the cash inflow and outflow process between cryptocurrencies and the traditional banking system (USDC itself). Since USDC’s “liabilities” are just on-chain ERC20 tokens, the liability proof is “free,” only requiring asset proof.

Plasma and Validiums: Can We Make CEXs Unfettered?

Suppose we want to go further: we don’t just want to prove that the exchange has the funds to repay users’ money. Instead, we want to completely prevent the exchange from stealing users’ funds.

The first major attempt in this regard was Plasma, an extension solution popular in the Ethereum research community in 2017 and 2018. Plasma works by splitting the balance into a set of individual “coins,” each assigned an index and located at a specific position in the Merkle tree of a Plasma block. A valid transfer of a coin requires placing the transaction at the correct position in the tree, with the root of the tree being published on the chain.

A simplified schematic of a version of Plasma. Coins are stored in a smart contract, and the Plasma protocol rules are forcibly executed during withdrawal.

OmiseGo attempted to build a decentralized exchange on this protocol, but since then, they have shifted to other ideas. In this regard, the Plasma group itself has also evolved, now becoming the Optimism project, focusing on optimistic EVM rollups.

The technological limitations of Plasma, as conceived in 2018 (such as proving coin fragmentation), are not worth considering. Since the peak of Plasma discourse in 2018, ZK-SNARKs have become more viable in use cases related to expansion. As mentioned earlier, ZK-SNARKs have changed everything.

A more modern version of the Plasma concept is what Starkware calls validium: essentially the same as ZK-rollup, except the data is stored off-chain. This structure can be used for many use cases, particularly where a centralized server needs to run some code and prove its correct execution. In a validium, operators cannot steal funds, though depending on the implementation details, some user funds might get stuck if the operator disappears.

All of this is very promising: the relationship between CEX and DEX is far from binary opposition. In fact, there’s a whole spectrum of options, including various forms of hybrid centralization, where you can enjoy benefits like efficiency while still having numerous cryptographic safeguards to prevent centralized operators from most forms of abuse.

However, in the right half of this design space, it is necessary to discuss a fundamental issue: handling user errors. So far, the most critical type of error is: What should be done if users forget their passwords, lose their devices, are hacked, or otherwise lose access to their accounts?

Exchanges can address this issue: first through email recovery, and if that fails, through more complex forms of recovery via KYC. However, to be able to resolve such issues, exchanges need to have actual control over the coins. To have the ability to rightfully restore access to user accounts, exchanges need to have the power that could also potentially be misused to steal funds from those accounts. This is an unavoidable trade-off.

The ideal long-term solution relies on self-custody, supplemented by technologies like multi-signature and social recovery wallets, to help users handle emergencies. But in the short term, there are two apparent alternative solutions, each with distinctly different costs and benefits.

Conclusion: Better Exchanges in the Future

In the short term, there are two distinct categories of exchanges: custodial and non-custodial. Today, the latter is represented by DEXes like Uniswap. In the future, we might also see cryptographically “constrained” CEXes, where users’ funds are held in something akin to a validium smart contract. We might also witness the emergence of semi-custodial exchanges, where we trust them with fiat rather than cryptocurrency.

Both types of exchanges will continue to exist. The simplest backward-compatible way to enhance the security of custodial exchanges is to increase the proof of reserves. This involves a combination of asset proof and liability proof. Developing well-structured protocols for both presents technical challenges, but we should make progress in both areas as much as possible, and open source the software and processes so that all exchanges can benefit.

In the longer term, I hope we move increasingly towards all exchanges being non-custodial, at least in terms of cryptocurrency. Wallet recovery will exist for new users dealing with small amounts and for institutions that need such arrangements for legal reasons. Highly centralized recovery options may be necessary, but this can be done at the wallet level, not within the exchange itself. The way magic.link interacts with platforms like Polymarket is an example of this approach. In terms of fiat, the flow between the traditional banking system and the crypto ecosystem can be facilitated by local cash inflow/outflow processes for asset-backed stablecoins, like USDC. However, achieving this goal fully will take some time.

Special thanks to Balaji Srinivasan, as well as the staff at Coinbase, Kraken, and Binance for their discussions.

Disclaimer：

1. This article is reprinted from [Chaincatcher] . All copyrights belong to the original author [Vitalik]. If there are objections to this reprint, please contact the Gate Learn team, and they will handle it promptly.
2. Liability Disclaimer: The views and opinions expressed in this article are solely those of the author and do not constitute any investment advice.
3. Translations of the article into other languages are done by the Gate Learn team. Unless mentioned, copying, distributing, or plagiarizing the translated articles is prohibited.