Vitalik’s latest long article Exit Game Validity Verification for EVM – The Return of Plasma

Validating Game Exits in EVM Vitalik's In-Depth Exploration of the Latest Plasma Implementation

Authors: Vitalik, Limo; Translation: Song Xue, LianGuai

Special thanks to Karl Floersch, Georgios Konstantopoulos, and Martin Koppelmann for their feedback, review, and discussions.

Plasma is a type of blockchain scaling solution that allows all data and computations except deposits, withdrawals, and Merkle roots to be kept off-chain. This enables the possibility of achieving very high scalability without being limited by on-chain data availability. Plasma was initially created in 2017 and has undergone several iterations in 2018, with notable ones being Minimal Viable Plasma, Plasma Cash, Plasma Cashflow, and Plasma Prime. Unfortunately, due to (i) the high costs of client-side data storage and (ii) fundamental limitations of Plasma, it has been largely replaced by Rollup technology outside the domain of payments.

The emergence of Validity Proofs (also known as ZK-SNARKs) gives us reason to reconsider this decision. The biggest challenge for Plasma in making payments feasible, which is client-side data storage, can be efficiently addressed with Validity Proofs. Additionally, Validity Proofs provide various tools that allow us to create a Plasma chain that resembles the Ethereum Virtual Machine (EVM). While the security guarantees of Plasma do not cover all users, as the fundamental reasons that make Plasma-style exit games infeasible for many complex applications still remain, it can still protect a very large portion of assets in practice.

• Interpreting Vitalik’s new work ZK+Plasma Changing the Layer 2 Landscape?
• Is the cryptocurrency industry similar to the early days of the internet?
• Buterin’s Bold Claim Ethereum’s Rollups are the ‘Gold Standard’ while Plasma Requires a Rethink!

This article describes how to extend the ideas of Plasma to achieve such goals.

1. Overview: How Plasma Works

The simplest version of Plasma Cash is Plasma Cash. Plasma Cash works by treating each individual token as a separate non-fungible token (NFT) and tracking a separate history for each token. The Plasma chain has an operator responsible for creating and periodically publishing blocks. The transactions in each block are stored in a sparse Merkle tree: if a transaction transfers ownership of token k, it appears at position k in the tree. When the operator of the Plasma chain creates a new block, they publish the root hash of the Merkle tree on-chain and directly send the Merkle branch corresponding to the tokens owned by each user.

Assuming this is the last three transaction trees in the Plasma Cash chain. Then, assuming all previous trees are valid, we can know that Eve currently owns token 1, David owns token 4, and George owns token 6.

The main risk in any Plasma system is the operator’s misconduct. This can happen in two ways:

1. Publishing invalid blocks (e.g., the operator includes a transaction sending token 1 to Hermione even though Fred didn’t own token 1 at that time).
2. Publishing unavailable blocks (e.g., the operator doesn’t send Bob the Merkle branch for a certain block, preventing him from proving to others that his token is still valid and unused).

If the operator engages in improper behavior related to user assets, it is the user’s responsibility to exit immediately (specifically, within 7 days). When a user (“exiter”) exits, they provide a Merkle proof that demonstrates the transfer of the token from the previous owner to their own account. This initiates a 7-day challenge period, during which others can challenge the exit by providing one of the following three types of Merkle proofs:

1. Non-latest owner: a subsequent transaction, signed by the exiter, that transfers the exiter’s token to someone else;

2. Double spend: a transaction that transfers the token to someone else, which was included before the transaction that transferred the token to the exiter;

3. Invalid history: a transaction that transferred the token prior to the exit (within the past 7 days) without a corresponding expenditure. The exiter can respond by providing the corresponding expenditure; if they fail to do so, the exit will fail.

According to these rules, anyone who owns token k needs to view all Merkle proofs in the past week’s history trees for position k to ensure that they actually own token k and can exit. They need to store all the branches that include the asset transfers so they can respond to challenges and safely exit the state with their tokens.

Expanding to fungible tokens

The above design applies to NFTs. However, more commonly used are fungible tokens such as ETH and USDC. One way to apply Plasma Cash to fungible tokens is to simply consider each token’s small denomination (e.g., 0.01 ETH) as a separate NFT. However, this would result in high gas costs for exiting.

A solution is to optimize by treating many adjacent tokens as a single unit that can be transferred or exited together. There are two ways to achieve this:

Almost unchanged use of Plasma Cash but with a complex algorithm that allows for fast computation of Merkle trees for very large quantities of objects if many adjacent objects are the same. This is not difficult to implement in practice; you can find a Python implementation here.

Use Plasma Cashflow, which simply represents many adjacent tokens as a single object.

However, both of these methods encounter fragmentation issues: if you receive 0.001 ETH from hundreds of people (each buying you a cup of coffee), there will be many places in the Merkle tree with 0.001 ETH, so actually exiting this ETH would still require submitting many individual exit requests, making the gas cost ineffective. Fragment consolidation protocols have been developed, but implementing them can be tricky.

Alternatively, we can redesign the system to consider a more traditional “unspent transaction output” (UTXO) model. When you exit a token, you need to provide the past week’s history of these tokens, and anyone can challenge your exit by proving that these historical tokens have already been exited.

Extraction of the 0.2 ETH UTXO on the bottom right can be canceled by showing the extraction of any UTXO in its history, as shown in green in the figure. It is important to note that the UTXOs on the left middle and bottom left are predecessors, but the UTXO on the top left is not. This method is similar to the sequential coloring idea based on colored coins protocol from around 2013.

There are many techniques to achieve this. In all cases, the goal is to track the concept of what is the “same token” at different points in history to prevent the “same token” from being extracted twice.

Challenges in Expanding to EVM

Unfortunately, promoting Plasma from payments to EVM is much more difficult. One key challenge is that many state objects in the EVM do not have explicit “owners”. The security of Plasma depends on each object having an owner who is responsible for observing and ensuring the availability of data on the chain and exiting the object in case of any issues. However, many Ethereum applications do not work this way. For example, Uniswap liquidity pools do not have a single owner.

Another challenge is that the EVM does not attempt to limit dependencies. The ETH held in account A in block N may come from anywhere in block N-1. To exit to a consistent state, the EVM Plasma chain needs to have an exit game where, in extreme cases, someone hoping to exit using information from block N may need to pay fees and publish the entire state of block N on-chain: gas fees can reach millions of dollars. UTXO-based Plasma schemes do not have this issue: each user can exit their assets from the latest block where they have possession of the data.

The third challenge is that the unlimited dependencies in the EVM make it more difficult to align incentives and proof of correctness for all parties. The validity of any state depends on everything else, so proving anything requires proving everything. In this case, fixing the fault often cannot make incentives compatible because there are data availability issues. One particularly annoying problem is that we lose a guarantee that exists in UTXO-based systems where the state of an object cannot change without the consent of the owner. This guarantee is very useful because it means that owners always know the latest provable state of their assets and simplifies the exit game. Without this guarantee, creating an exit game becomes more difficult.

II. How Validity Proofs Help Alleviate Many of These Issues

The most fundamental role that validity proofs can play in improving Plasma chain design is to prove the validity of each Plasma block on-chain. This greatly simplifies the design space: it means that the only thing we need to worry about is unavailable blocks from the operator, not invalid blocks. Taking Plasma Cash as an example, it eliminates concerns about historical challenges. This reduces the branches that users need to download from one branch per block per week to one branch per asset.

In addition, withdrawals made in the latest state (in the ordinary case of honest operators, all withdrawals will come from the latest state) are not affected by challenges from the latest owners, so on a proven-validity Plasma chain, these withdrawals will not be affected by any challenges. This means that withdrawals can be instant in normal circumstances!

Extending to EVM: Parallel UTXO Graph

In the case of EVM, the proven-validity also allows us to do some clever things: they can be used to achieve a parallel UTXO graph for ETH and ERC20 tokens, and prove the equivalence between the UTXO graph and EVM state through SNARK. Once you have this, you can implement a “regular” Plasma system on the UTXO graph.

This allows us to bypass many complexities of EVM. For example, in an account-based system, someone could edit your account without your consent (increasing their balance by sending tokens to it), but this fact doesn’t matter because Plasma builds not on the EVM state itself, but on the UTXO state that exists parallel to the EVM, and any tokens you receive will be independent objects.

Extending to EVM: Total State Exits

There have been simpler schemes proposed for creating “plasma EVM”, such as Plasma Free and this prior article from 2019. In these schemes, anyone can send a message on L1, forcing operators to either include a transaction or make a specific branch of the state available. If the operators fail to do so, the chain starts rolling back blocks. The chain stops rolling back as soon as someone publishes a full copy of the whole state or at least publishes all data that users marked as potentially lost. Withdrawals may require a bounty to be paid, which compensates the user for their gas share of publishing such a large amount of data.

The weakness of these schemes is that in normal circumstances, they do not allow for instant withdrawals, as there is always the possibility of the chain needing to roll back to the latest state.

III. Limitations of the EVM Plasma Scheme

While these schemes are powerful, they cannot provide comprehensive security guarantees for all users. The most obvious case where they break down is when specific on-chain objects have no clear economic “owner.”

Let’s consider the case of a CDP (Collateralized Debt Position), which is a smart contract where a user has locked tokens that can only be released once the user repays the debt. Suppose a user has locked 1 ETH (worth approximately $2000 at the time of writing) in a CDP, with a debt of 1000 DAI. Now, if the Plasma chain stops releasing blocks and the user refuses to exit, the user can never exit. Now, the user has a free option: if the price of ETH drops below $1000, they walk away and forget about the CDP; if the price of ETH remains above $1000, they eventually claim it. On average, malicious users like this can make money by doing this.

Another example is the privacy system, such as Tornado Cash or privacy pools. Consider a privacy system with five depositors:

The ZK-SNARK in the privacy system hides the connection between the token owners entering and leaving the system.

Assume only the orange one exits, and at this time, the Plasma chain operator stops releasing data. We also assume that we use the UTXO graph method with a first-in, first-out rule, so each token is matched with the token directly below it. Then, the orange one can extract the pre-mixed and post-mixed tokens, and the system will treat them as two separate tokens. If the blue one tries to withdraw their pre-mixed tokens, the latest state of the orange one will replace it; meanwhile, the blue one will have no information to withdraw the post-mixed tokens.

If you allow the other four depositors to extract the privacy contract itself (which would replace the deposit), and then withdraw the tokens on L1, this problem can be solved. However, actually implementing such a mechanism requires additional efforts from privacy system developers.

There are other methods to solve privacy issues, such as the Intmax method, which involves placing several bytes in a chain-style aggregate with operators similar to Plasma that pass information between users.

Uniswap LP positions also have similar issues: if you swap USDC for ETH in a Uniswap position, you can try to withdraw the pre-trade USDC and post-trade ETH. If you collude with the Plasma chain operator, liquidity providers and other users will not be able to access the post-trade state, and therefore they will not be able to withdraw the post-trade USDC. Special logic is needed to prevent such situations from occurring.

Conclusion

In 2023, Plasma is an underrated design space. Rollup is still the gold standard and has unparalleled security properties. This is particularly true from the perspective of developer experience: nothing beats the simplicity for application developers, without even considering ownership graphs and incentive flows in the application.

However, Plasma allows us to completely bypass data availability issues and significantly reduce transaction costs. Plasma can bring significant security upgrades to chains that would otherwise become verification chains. ZK-EVM finally realizes this year, providing an excellent opportunity to explore this design space again and propose more efficient structures to simplify developer experience and protect user funds.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!