Partnered With:

V God: To explore ways to build a secure and centralized trading platform

Read this article in 30 Minutes

This article delves into historical attempts to make CEX more trusting, the limitations of its use of technology, and some powerful ways to rely on advanced techniques such as ZK-SNARKs

Vitalik: Building a Secure, Centralized Exchange -- nbsp; Proof of Solvency and More

Original article by Vitalik Buterin

Double flower (@doublespending)

Special thanks to Balaji Srinivasan and the Coinbase, Kraken and Binance teams for their discussion.

Whenever a big centralized trading platform breaks down, the question that is often asked is whether we can use encryption to solve the problem. Rather than relying on "fiat" schemes such as government licences, auditors, investigations into corporate governance and transfers of legal entities, trading platforms can prove that they hold enough money on their chains to repay users by creating cryptographic certificates.

More ambitiously, trading platforms could set up a system in which depositors' money cannot be withdrawn without their consent. We can try to explore the boundary between the "don't be evil" professional CEX and the "can't be evil" but privacy-leaking DEX on the inefficient chain. This article will delve into historical attempts to make CEX more trusting, the limitations of its use of technology, and some powerful ways to rely on advanced techniques such as ZK-SNARKs.

Balance sheets and Merkle trees: traditional proof of solvency

The earliest attempts by trading platforms to use cryptography to prove they are not cheating users go back a long way. In 2011, MtGox, then the largest bitcoin exchange, proved it owned the money by sending a transaction that moved 424,242 BCTS to a pre-announced address. In 2013, there was discussion about how to solve the other side of the problem: proving the total size of user deposits. If you prove that the user's deposits are equal to X Then you provided proof of solvency: You proved that the trading platform had enough funds to pay back the depositors.

The easiest way to provide proof of deposit is to publish a list. Every user can check their balance in the list, and anyone can check the full list: (i) each balance is non-negative; (ii) The total amount is the amount claimed.

Of course, this undermines privacy, so we can change the scheme a bit: publish a username, salt, balance> List and privately send the user a salt value. But even that would reveal the balance and its distribution. To protect privacy, we adopted a follow-up technique: the Merkle tree technique.

Green: Charlie's node. Blue: Charlie receives the node for proof. Yellow: The root node is exposed to all

The Merkle tree technique puts the user balance table into the Merkle summation tree. In the Merkle summation tree, every node is right. The underlying leaf node represents the balance of each user and the salted hash of the user name. In each higher-level node, the balance is the sum of the balances of the next two nodes, and the hash is the hash of the next two nodes. The Merkle summation proof, like the Merkle proof, is a "branch" of all sister nodes along the path from leaf node to root node.

First, the trading platform sends each user a Merkle summation certificate of their balance. The user can then be sure that his balance is correctly included as part of the total. Simple sample code can be found here.

The privacy leakage under this design is much lower than the disclosure of the full balance table, and can be further reduced by shutering the branches each time Merkel-root is published, but there are still some privacy leakage issues: Charlie knows someone's balance is 164 ETH, two users' balance is 70 ETH, and so on. An attacker who controls multiple accounts can still learn a lot about the users of a trading platform.

An important subtlety of the scheme is the possibility of negative balances: what if a trading platform with a user balance of 1390 ETH but only 890 ETH in reserve tries to make up the difference by adding a balance of -500 ETH under a fake account somewhere in the tree? This possibility doesn't actually break the solution, which is why we specifically use Merkle summation trees instead of regular Merkle trees. Suppose Henry is a fake account controlled by the trading platform, and the trading platform has put -500 ETH on it:

Greta's verification will fail: when the trading platform will have to give Henry a node with a balance of -500 ETH, she will reject the invalid node. Eve and Fred will also fail to verify that the intermediate node above Henry has a balance of -230 ETH, so that node is also invalid! To keep the theft undetected, the trading platform must hope that no one checks its balance certificate in the right half of the tree.

If the trading platform can pick out those 500 ETH users who bother to check their balance sheets, or who are not believed when they complain they have not received their balance sheets, then the trading platform can get away with it. However, the trading platform can also achieve the same effect by excluding these users from the Merkle summation tree. Therefore, if only in terms of liability proof, Merkle tree technology basically meets the requirement. But its privacy features are still less than ideal. You can make improvements with Merkle trees more subtly, such as using satoshi or wei as a separate leaf node. However, it can be done better by using more advanced technology.

Use ZK-SNARKs for privacy and robustness

ZK-SNARKs are a powerful piece of technology. What ZK-SNARKs means to cryptography is akin to artificial intelligence: a general-purpose technology capable of crushing a series of specialized techniques developed decades ago to solve a range of problems. So we can certainly use ZK-SNARKs to greatly simplify and improve privacy in the proof of liability agreement.

We can simply put all users' deposits into the Merkle tree (or, more simply, the KZG promise) and use ZK-SNARK to prove that all balances in the tree are non-negative and add up to some claimed value. If we add a layer of hashing to ensure privacy, then the Merkle branch (or KZG proof) sent to each user will not leak any other user's balance.

Using KZG promises is one way to avoid privacy breaches, because there is no need to provide a "sister node" as proof, and a simple ZK-SNARK can be used to prove the sum of the balances and that each balance is non-negative.

We can prove the sum of the balances in the above KZG and its non-negativity by a special ZK-SNARK. Here's a simple example. We introduce an auxiliary polynomial I(x) that "builds out every bit of the user's balance" (for example, let's assume the balance is below 215), where every 16th position tracks the balance guarantee, and the value is 0 only if the actual total equals the claimed total. If z is a primal root of order 128, we can prove that the equation holds:

[1] The interpretation of this polynomial equation.

How to convert these equations to polynomials and later to ZK-SNARK can be found here and elsewhere in my article on ZK-SNARKs. It's not an optimal protocol, but it's easy to make sense of these cryptographic proofs!

With only a few additional equations, the constraint system can be adapted to more complex Settings. For example, in leveraged trading systems, it is acceptable for individual users to have a negative balance, but only if they own enough collateral assets to cover their liabilities. SNARK can be used to justify this more complex constraint, assuring users that a trading platform cannot compromise user assets by secretly exempting certain users.

In the long run, the usefulness of this ZK liability certificate is not limited to user deposits on trading platforms, but could also be used in a broader lending scenario. Anyone making a loan will put the record into a polynomial or tree containing that loan, and the root will be published on the chain. This would allow anyone seeking a loan to provide a zero-knowledge certificate to the lender to show that they have not taken out too many other loans. Eventually, legal innovations could even give loans committed in this way a higher priority than uncommitted loans. This is in line with an idea we discussed in The Decentralized Society: The Search for the Soul of Web3: enabling the concept of on-chain negative credit through some form of "soul bound token".

Proof of assets

The simplest version of proof of assets is the protocol we saw above: In order to prove that you hold X tokens, you simply move X tokens at a predetermined time or carry the message "These funds belong to Binance" with you in the transaction. To avoid paying transaction fees, you can sign an off-link message. Both Bitcoin and Ethereum have standards for off-chain signature information.

There are two practical problems with this simple asset-proof technique:

Cold wallet treatment

Collateral reuse

For security reasons, most trading platforms store most of their users' money in a cold wallet: on an offline computer, trades need to be manually signed and carried over the Internet. The technique is common: my cold wallet, which I used to store my personal money, sits on a permanently offline computer and generates QR codes containing signed transactions, which I then scan with my phone. Because of the large amount of money, the security protocols used by trading platforms are more complex, often involving multi-party calculations among multiple devices, to further reduce the possibility that a single device could be hacked and lead to a key leak. In this context, even creating an additional message to prove control of the address is an expensive operation!

The trading platform can adopt the following ways:

Maintain some long-used public addresses. The trading platform generates several addresses, publishes proof of ownership of each address only once, and then re-uses those addresses. This is by far the simplest solution, although it adds some restrictions on security and privacy.

Hold a lot of addresses, and then randomly prove several addresses. Trading platforms hold many addresses, and may even use each address only once and no longer use it after a single transaction. In this case, the trading platform needs to have a protocol that from time to time randomly selects some addresses that the trading platform must "open" to prove ownership. Some trading platforms already do something similar through auditors, but in principle this technology could be translated into fully automated procedures.

More complicated ZKP way. For example, a trading platform could set up 1/2 multiple signatures for all its addresses, where one copy of the key is different, and the other copy of the same key is stored in some complex but secure way (e.g., 12/16 multiple signatures) in a blind version of an important emergency backup. To protect privacy and avoid giving away all of its addresses, trading platforms can even run zero-knowledge proofs on the blockchain to prove the total balance of addresses on the format chain.

Another major issue is preventing collateral reuse. It is often easy for trading platforms to transfer collateral back and forth to prove reserves, allowing them to muddle through without actually being solvent. Ideally, the proof of solvency should be done in real time and updated after each block. If this is impractical, then the next best thing is to agree on a fixed time for certification between trading platforms, such as every Tuesday at 2pm UTC to certify reserves.

The last question is: can you prove assets in legal tender? Trading platforms not only hold cryptocurrencies, but also fiat currencies within the banking system. Here the answer is yes, but such a process would inevitably rely on the "fiat" trust model: the bank itself could prove the balance, the auditor could prove the balance sheet and so on. Given that fiat money cannot be cryptographically verified, this is the best solution within the framework and is still worth doing.

Another approach is to separate Entity A from Entity B. Entity A runs the trading platform and handles the USDC, which is a stablecoin backed by some asset; B is responsible for handling the flow of cash in and out between the cryptocurrency and the traditional banking system, in this case the USDC itself. Since the "liability" of USDC is only the ERC20 token on the chain, the liability proof can be obtained "easily" and we only have to deal with the asset proof.

Plasma and validiums: Can we implement unmanaged CEX?

Suppose we wanted to go further: we didn't want to just prove that the trading platform had enough money to pay back its users. Instead, we want to completely prevent transactions from stealing users' money.

One of the first is Plasma, a capacity expansion solution that became popular in the Ethereum research community in 2017 and 2018. Plasma works by splitting the balance into a set of separate "tokens," each of which is assigned an index and placed at a specific location in the Merkle tree on the Plasma block. For a token transfer to be effective, the transaction needs to be placed at the correct place in the tree, and the root of the tree is published on the chain.

A very short diagram of a version of Plasma. The tokens are kept in smart contracts that enforce the Plasma protocol's rules when they are withdrawn.

OmiseGo tried to create a decentralized trading platform based on this protocol, but since then they've moved on to other things -- as far as the Plasma Group is concerned, with their optimistic rollup project Optimism.

Discussions in 2018 about Plasma's limitations (e.g., proving token defragmentation) made Plasma's viability fundamentally questionable. Since the Plasma discussion peaked in 2018, ZK-SNARKs have become even more feasible for scaling out relevant use cases. As we mentioned above, the ZK-SNARKs change everything.

Plasma's updated version is what Starkware calls the validium scheme: essentially the same as ZK-rollup, except that the data is kept down the chain. This construct is applicable to many use cases, and you can imagine it for any scenario where a centralized server needs to prove that it executes code correctly. In validium, the operator cannot steal money, but depending on the implementation details, some user money may be stuck if the operator disappears.

Now it looks great: Far from being a binary choice, CEX and DEX, it turns out, have a range of options that include various forms of hybrid centralization, where you get some benefits, like efficiency, but still have a lot of cryptographic safeguards against most forms of malicious behavior by centralized operators.

However, the remaining basic question is worth considering: how to handle user errors. By far the most important type of error is: what if a user forgets their password, loses their device, is hacked, or cannot access their account?

Trading platforms can solve this problem by first using email recovery, and if even that fails, a more complex recovery via KYC. But to solve these problems, exchanges need real control over these tokens. In order to reasonably recover users' money, trading platforms need to have the same power to steal users' money without cause. It's an inevitable trade-off.

The ideal long-term solution would be to rely on self-hosting, where users could easily use technologies such as multi-tabs and social recovery wallets to help deal with emergencies in the future. In the short term, there are two obvious alternatives, with different costs and benefits:

Another important issue is cross-chain support: trading platforms need to support many different chains. Systems such as Plasma and validiums require coding in different languages to support different platforms, and are not available in their current form on some platforms (notably Bitcoin). This is expected to be solved through technical upgrades and standardization. In the short term, however, this is another reason why today's managed trading platforms remain managed.

Bottom line: Look ahead to a better trading platform

In the short term, there are two distinct categories of trading platforms: managed and unmanaged. Today, the latter category is DEX like Uniswap, and in the future we may see cryptographically constrained CEX where user funds are held in a validium smart contract fashion. We may also see semi-managed trading platforms where we trust them to handle fiat currencies rather than cryptocurrencies.

Both types of trading platforms are here to stay, and the easiest way to improve the backward-compatible security of managed trading platforms is to add proof of reserve. This includes a combination of proof of assets and proof of liabilities. There are still challenges to designing good protocols for both, but we can and should push for both types of technology to go hand in hand, and open source software and programs as much as possible so that all trading platforms can benefit.

In the long run, I'd like to see us move towards all trading platforms being unmanaged, at least for cryptocurrencies. Wallet recovery will exist and may require a highly centralised recovery option for new users of small funds and institutions that need such arrangements for legal reasons, but this can be done at the wallet level rather than within the trading platform. On the fiat side, the movement between the traditional banking system and the cryptocurrency ecosystem can be accomplished through the flow of funds in and out of asset-backed Stablecoins, such as the USDC. However, we still have a long way to go.

[1] [1]

Each of the 16 digits represents a user (the first 15 digits represent the user's balance, and the last digit represents the difference between the total user balance and the stated balance so far). We can see that the above example represents two users (for insight here)

Average declared user balance: 185

Balance of user 1:20 -> 000 0000 0001 0100

The difference: 20-185 = -165

Balance of user 2:50 -> 000 0101 0011 0010

The difference: -165 + 50-185 = -300

Finally, all users are traversed, and the last user has a balance of 0

Four equations explained

Equation 1: The initial value of recursion is 0

Equation 2: Each user balance needs to correspond to KZG commitment

Equation 3: Recursive formula for each user's balance, constrained balance > = 0 and 214

It says the balance is 215. I think it's a clerical error, because according to equation 3, the recursion formula only has 14 values, I(zi) 214,

16 Numbers: I {x} 16 (z) = 0 | I z (x + 1} {16) | I 16 x + {2} (z) & have spent |... | I {16 x + 14} (z) | difference