The collapse of FTX has severely eroded user trust in centralized crypto exchanges. Most investors have finally realized the importance of owning the keys to their digital assets and have moved record volumes of tokens from exchanges to non-custodial wallets.
These events brought about a wave of urgency for centralized exchanges to provide reliable proof that they hold more assets than liabilities. In a blog post on Nov. 19, Ethereum co-founder Vitalik Buterin analyzed the cryptographic methods deployed so far by exchanges to become trustless, including the limitations of such methods.
He also suggested new techniques for centralized exchanges to achieve trustlessness involving zero-knowledge Succinct Non-Interactive Argument of Knowledge (ZK-SNARKs) and other advanced technologies.
Binance, Coinbase, and Kraken, along with a16z general partner and former Coinbase CTO Balaji Srinivasan, contributed to the post.
Proving solvency through balance lists and Merkle trees
In 2011, Mt. Gox was one of the first exchanges to provide proof of solvency by transferring 424,242 BTC from a cold wallet to a pre-announced Mt. Gox address. It was later revealed that the transaction may have been misleading since the transferred assets may not have been moved from a cold wallet.
In 2013, discussions began on how exchanges could prove the total size of their user deposits. The idea was that if exchanges proved their total user deposits, i.e., their total liabilities, along with their ownership of an equivalent amount of assets, i.e, proof-of-assets, then it would prove their solvency.
In other words, if the exchanges could prove that they held assets equal to or more than their user deposits, it would prove their capability of paying back all users in case of withdrawal requests.
The easiest way for exchanges to prove total user deposits was to simply publish a list of usernames along with their account balances. However, this violated user privacy, even if the exchanges only published a list of hash and balances. Therefore, the Merkle tree technique, which enables the verification of large data sets, was introduced.
In the Merkle tree technique, the table of user balances is inserted into a Merkle sum tree, in which each node, or leaf, is a balance and hash pair. The lowermost layer of nodes contains individual user balances and salted username hashes. As you move up the tree, each node represents the sum of the balances of the two nodes below it and the sum of the hashes of the two nodes under it.
While the leak of privacy is limited in Merkle trees compared to public lists of names and balances, it is not completely immune, Buterin wrote. Hackers that control a large number of accounts in an exchange can potentially gain significant knowledge about the exchange’s users, he added.
Buterin also noted:
“… the Merkle tree technique is as good as a proof-of-liabilities scheme can be, if only achieving proof of liabilities is the goal. But its privacy properties are still not ideal.
You can go a little bit further by using Merkle trees in more clever ways, like making each satoshi or wei a separate leaf, but ultimately with more modern tech there are even better ways to do it.”
The use of ZK-SNARKs
Exchanges can put all user balances into a Merkle tree or a KZG commitment and use a ZK-SNARK to prove that all balances are non-negative and add up to the total deposit value claimed by the exchange. Adding a layer of hashing to improve privacy would ensure that no exchange user can learn anything about other user balances.
“In the longer-term future, this kind of ZK proof of liabilities could perhaps be used not just for customer deposits at exchanges, but for lending more broadly. “
In other words, borrowers could provide ZK-proofs to lenders ensuring them that the borrowers do not have too many open loans.
The easiest version of proving exchanges own assets was the method deployed by Mt. Gox. Exchanges simply move their assets at a pre-agreed time or in a transaction where the data field indicates which exchange owns the assets. Exchanges could also avoid the gas fee by signing an off-chain message.
However, this technique has two major problems – dealing with cold storage and dual use of collateral. Most exchanges keep the majority of their assets in cold storage to keep them secure, which means “making even a single extra message to prove control of an address is an expensive operation!” Buterin wrote.
To deal with the problems, Buterin noted that exchanges could use a few public addresses in the long term. The exchanges could generate a few addresses, prove their ownership once, and use the same addresses repeatedly. However, this presents challenges in preserving privacy and security.
Alternatively, exchanges could have many addresses and prove their ownership of a few randomly selected addresses. Moreover, exchanges could also use ZK-proofs to ensure privacy preservation and provide the total balance of all on-chain addresses, Buterin said.
The second issue is ensuring that exchanges do not shuffle collateral to fake solvency. Buterin said:
“Ideally, proof of solvency would be done in real-time, with a proof that updates after every block. If this is impractical, the next best thing would be to coordinate on a fixed schedule between the different exchanges, eg. proving reserves at 1400 UTC every Tuesday.”
The last issue is providing proof-of-assets for fiat currencies. Crypto exchanges hold both digital assets and fiat currencies. According to Buterin, since fiat currency balances are not cryptographically verifiable, providing proof of assets requires dependence on “fiat trust models”. For instance, banks that hold fiat for exchanges can attest to the available balances and auditors can attest balance sheets.
Alternately, exchanges could create two separate entities — one that deals with asset-backed stablecoins and another one that handles the bridging between fiat and crypto. Buterin noted:
“Because the “liabilities” of USDC are just on-chain ERC20 tokens, proof of liabilities comes “for free” and only proof of assets is required.”
The use of Plasma and validiums
To prevent exchanges from stealing or misusing customer funds altogether, exchanges could use Plasma. A scaling solution that became popular in Ethereum research circles in 2017-2018, Plasma splits up the balance into different tokens, where each token is assigned an index and has a particular position in the Merkle tree of a Plasma block.
However, since the advent of Plasma, ZK-SNARKs has emerged as a “more viable” solution, Buterin noted. The modern version of Plasma is a validium, which is the same as ZK-rollups but data is stored off-chain. However, Buterin warned:
“In a validium, the operator has no way to steal funds, though depending on the details of the implementation some quantity of user funds could get stuck if the operator disappears.”
The drawbacks of full decentralization
The most common problem with fully decentralized exchanges is that users could lose access to their accounts if they get hacked, forget their password or lose their devices. Exchanges can solve this problem through e-mail recovery and other advanced forms of account recovery through know-your-customer details. But this would require the exchange to have control over the user’s funds.
“In order to have the ability to recover user accounts’ funds for good reasons, exchanges need to have power that could also be used to steal user accounts’ funds for bad reasons. This is an unavoidable tradeoff.”
The “ideal long-term solution,” according to Buterin, is relying on self-custody with multi-sig and social recovery wallets. In the short term, however, users need to select between centralized and decentralized exchanges based on the trade-off they are comfortable with.
|Custodial exchange (eg. Coinbase today)||User funds may be lost if there is a problem on the exchange side||Exchange can help recover account|
|Non-custodial exchange (eg. Uniswap today)||Users can withdraw even if the exchange acts maliciously||User funds may be lost if the user screws up|
Conclusions: the future of better exchanges
In the short term, investors need to choose between custodial exchanges and non-custodial exchanges or decentralized exchanges like Uniswap. However, in the future, some centralized exchanges may evolve, which will be cryptographically constrained so the exchange cannot steal user funds, by holding balances in a validium smart contract, Buterin said.
The future may also bring about half-custodial exchanges where users trust the exchange with fiat but not cryptocurrencies, he added.
While both types of exchanges will continue to co-exist, the simplest way to enhance the safety of custodial exchanges is to add proof-of-reserves, Buterin noted. This would include a combination of proof-of-assets and proof-of-liabilities.
In the future, Buterin hopes that all exchanges will evolve to become non-custodial, “at least on the crypto side.” Centralized wallet recovery options would exist, “but this can be done at the wallet layer rather than within the exchange itself,” he said.
On the fiat side, exchanges could deploy the cash-in and cash-out processes native to fiat-backed stablecoins like USDT and USDC. But “it will still take a while before we can fully get there,” Buterin cautioned.