# Plasma EVM 1.0
Carl Park (Onther Inc.)
Aiden Park (Onther Inc.)
Kevin Jeong (Onther Inc.)

:::info
[A Proposal For Data Availability Solution of Plasma EVM](https://hackmd.io/s/ByeGtM5D7) can solve the data withholding attack. This article will be updated.
:::

### Abstract
EVM provides such a powerful turing-complete computation so that ethereum can run a general program, also known as smart contract. Plasma EVM is a new version of Plasma that can execute EVM in plasma chain, and its clients can be based on current ethereum clients (go-ethereum, py-evm, parity). We propose *state-enforceable Plasma construction* to guarantee only valid state submitted to root chain, providing a way to enter and exit account storage between two chains because each chain has identical architecture. Another benefit is that ethereum development tools can be also used in plasma chain.

### Glossary
- NULL_ADDRESS: `0x00` or `0xFF...FF`(`2^160 - 1`) with nonce and signature `v = r = s = 0`, denoted $NA$.
- Transactor: Account who generate transaction, `tx.origin`.
- Root chain: Ethereum blockchain.
- Child chain: Plasma blockchain.
- PETH: ETH in child chain as a coin.
- PETH20: PETH as a ERC20 token.
- PERC20: ERC20 in child chain, corresponding to the ERC20 in root chain.
- Asset: Includs all of (P?)ETH, (P?)ERC20, PETH20.
- RootChain contract: A plasma contract on root chain accepting enter / exit (ETH / ERC20), denoted $R$.
- Requestable contract: Contracts able to accept exit / enter request in both of root and child chain. 2 identical contracts should be deployed in root and chind chain, and $R$ maps two addresses.
- enterRequest: A request to enter something from root chain to child chain. eg) deposit asset, move account storage variable.
- exitRequest: A request to exit asset or account storage from child chain to root chain. Any exit request on root chain immediately updates account storage in child chain. If the update in child chain is rejected(TX reverted), the exit can be challenged with the computation output of the update as proof.
- requestBlock / evenBlock: A block, applying state transition that is enforced by the root chain.
- nonRequestBlock / oddBlock: A block where transactions are only related between accounts in child chain.
- requestChallenge: challenge if `requestBlock` excludes requests or includes invalid requests.
- nullAddressChallenge: challenge if `nonRequestBlock` contains a transacton from NULL_ADDRESS.
- computationChallenge: challenge if `requestBlock` or `nonRequestBlock` have the state computed in a wrong way.
- exitChallenge: challenge if invalid `exitRequest` cannot be accepted in child chain (but the request should be included in `requestBlock`).
- casChallenge: challenge if operator submits block without transactor's confirmation.

### Child Chain
It is supposed that the client is based on the original ethereum client. So most of basic mechanisms are similar with original one. Block, transaction, and receipt have the same structure as ethereum. The child chain has a little changes to adopt this plasma protocol.

1. If an asset(ETH / ERC20) is deposited in RootChain contract, the request is queued on `enterRequests`. Operator(or NULL_ADDRESS) **MUST** generate a transaction to *mint* the asset in the next block. it is the way to enforce state transition from root chain to child chain.

2. If a asset holder wants to exit, he makes a request on root chain with proofs. The request is queued on `exitRequests` and operator (or NULL_ADDRESS) **MUST** generates a transaction to *burn* the asset in the next block.

3. If the exit request is fianlized without challenge in root chain, no more changes happen in child chain. But a contract *in root chain* **MUST** apply the corresponding changes.

4. If the next block doesn't properly include request-related transactions, it can be challenged and the RootChain recover the child chain state to previous block.

Operator submits two types of block, `requestBlock` and `nonRequestBlock`. Let's take a look at how above requests are enforced.

1. Operator **MUST** call `prepareToSubmit` before submit new blocks. The RootChain becomes `WaitingNonRequestBlock`. Then one submits 2 blocks, `nonRequestBlock` and `requestBlock`. New requests during this state are pending until state becomes `AcceptingRequest` again.

2. First one, `nonRequestBlock`, **MUST** contain all transactions not related to the enter & exit requests. If there is no transaction generated in child chain, `transactionsRoot`, `postTransactionalStatesRoot` will point `emptyTrie`. Those blocks have **odd** block number. It can be challenged if it contains a transaction from NULL_ADDRESS (*nullAddressChallenge*) OR the state is transited in a wrong way (*computationChallenge*), recovering child chian from byzantine.

- After operator submits `nonRequestBlock`, RootChan becomes `WaitingRequestBlock`.

3. Since the second block contains only transactions related to the request, the `requestBlock` should contain only state-enforcing transactions, applying enter & exit, related to NULL_ADDRESS and contact account. It is also called `evenBlock`.

- If `requestBlock` includes non request-related transactions or excludes a request that is going to be included, the challenged block is reverted. This kind of challenge is called `requestChallenge`.
- After operator submits `requestBlock`, RootChan becomes `AcceptingRequest`.

4. From now on, a token holder in child chain can make transaction to transfer ERC20 to other users. But the transaction requires gas. A newbie in child chain doesn't have PETH in child chain. It can be solved make fee payment to be delegated to other account. `Stamina` contract handles this kind of fee delegation. (See [EVM Compatible Gas Delegated Transaction Execution Architecture](https://hackmd.io/ruNllAk4REieq0dxYzIltw))

`evenBlock` enforces how the state should change in the child chain by the RootChain. If the operator doesn't apply the enforcement properly, it can be challenged and the block reverted to previous block. (*requestChallenge*)

*<center>Request and Challenge Diagram</center>*

*<center>RootChain contract state transition diagram</center>*

#### Epoch
An Epoch has N blocks, N-1 `nonRequestBlock` and 1 `requestBlock`. The trivial case described above is where epoch length is 2. But epoch length can be extended to reduce the ratio of `requestBlock` to `nonRequestBlock`.

### Block Submission
Operator submits [CAS](https://ethresear.ch/t/cryptoeconomic-signature-aggregation/1659) and 3 merkle roots, `stateRoot`, `transactionsRoot`, and `postTransactionalStatesRoot` for each block. An exit requires merkle proof of account's state(PETH balance or account storage's value) at a specific block. If the state is computed in a wrong way, a computation challenge can recover the block where the state is correct. It is resolved by TrueBit-like verification game, verifying a 'state transition function by transaction' with pre-stateRoot and post-stateRoot.

### Block Withholding Attack (DISCUSSION NEEDED)
Plasma MVP prevents operator from withholding block by requiring transactor to confirm that the transaction was included in the block. If the transactor witnesses that operator withheld block (one cannot verify the submitted block data), one can exit the UTXO to be spent by the transaction if one doesn't confirmed.

Plasma EVM employs a similar confirmation model like MVP, but only submits **only confirmed** blocks. Operator seals a block with transactions before submiting to root chain. One broadcasts the block data to network participants. If all transactors broadcast confirmation signature, operator aggregates the confirm-sigs. A cryptoeconomic aggregated signature with `m = block data, B={111...111} where B.bitLength == Block.transactions.length, s = signature of [m, B] signed by operator` is submitted with merkle roots. If operator set $B_i = 1$ but $TX_i.sender$ doesn't confirmed, the CAS can be challenged and operator is forced to report confirm-sig of $i$th transaction.

If transactor doesn't confirmed a sealed block, operator makes a new sealed block without the not-confirmed transaction and requests a new confirm-sigs. Through this interative & iterative `Send TX` -> `Seal Block` **<->** `Request Confirm Sigs` -> `Submit Block` steps, submitted blocks guarantee that block data is available to all transactors. But this approach cannot completely solve the attack.

If a block has not been successfully challenged during challenge period, it is considered as **finalized**.

But if plasma chain runs on BFT-style consensus mechanism(like Tendermint, PBFT), there is no need to consider this attack becuase at lease one honest node can provide the data that others are withholding.

### Finality
Plasma EVM is capable of checkpointing blocks like Plasma XT if block cannot be reverted after challenge period. With finality, the RootChain contract can be efficiently implemented.

### Account Storage Enter & Exit
In Plasma EVM, any type of account's storage variable is free to move between root chain and child chain. The reason why storage variable is available for Enter & Exit request is that storage is Trie, and any value inside a storage can be accessed with its key. Enter & Exit mean moving a account's **single storage variable** in one chain onto a corresponding contract in another chain.

#### Notation
NULL_ADDRESS: $NA$
Operator: $O$
User of plasma: $U$
Chllenger: $Ch$
RootChain contract: $a_R$

Requestable contract account in root chain: $a_r$
Requestable contract account in child chain: $a_c$
*(There is only one contract account for each chain)

Stroage variable of account in root chain: $σ[a_r]s[k]$, simply $A^{r}_{s}[k]$
Stroage variable of account in child chain: $σ[a_c]s[k]$, simply $A^{c}_{s}[k]$
(where $k$ is $trieKey$ and $A_s$ is $σ[a]s$)

Let *arbitrary storage variable in the trie* be $A_s[k]$ and *both requestable contract account in root and child chain* be $a_r$ and $a_c$. Then the storage variables of them are respectively $A^{r}_{s}[k]$ and $A^{c}_{s}[k]$. Enter & Exit of storage variable can be defined as moving it between $A^{r}_{s}[k]$ and $A^{c}_{s}[k]$. Enter is an operation that changes the state of $A^{c}_{s}[k]$ on the basis of $A^{r}_{s}[k]$ and Exit is that changes the state of $A^{r}_{s}[k]$ on the basis of the $A^{c}_{s}[k]$. However, specific methods of changing the state may vary for each implementation. To apply storage changes, it is **necessary** that $a_r$ and $a_c$ should have same bytecode, which means both contracts have same storage layout. (This can be verified by comparing the codeHash of both contacts)

There is no need for all variables to be requestable. This is because there are variables that do not need an request, and it should be considered who can make a request on variables. For example, if anyone has the right to request other's token balance, this will raise a big problem. Nobody can claim one's tokens, it's everyone's. Therefore, we want to resolve this by placing a logic inside the function of the contact in advance. This is possible because it can be checked using the order in which the variable is declared and trieKey. Further details of this will be covered in the pseudo code section below.

The specific process of `Enter` and `Exit` is as follows.

#### Enter

1. User $U$ calls `enter()` in $a_R$ with arguments of $a_r$, `trieKey`, and `trieValue` in order to enter $A^{r}_{s}[k]$ to correspoding $a_c$.
2. In `enter()`, `applyRequestInRootchain()` of $a_r$ is called.
3. If step 2 is reverted, the enter request is cancelled. Otherwise, an `enterRequest` is generated in $R$.
4. $O$ must include a transaction from $NA$ that processes the `enterRequest` in next `requestBlock`. If $O$ does not properly include it, then $Ch$ can challenge on this by `requestChallenge`.
5. In the transaction from step 4, $NA$ executes `applyRequestInChildchain()` in accordance with the `enterRequest` in $a_c$. $A^{c}_{s}[k]$ is successfully changed to $A^{c}_{s}[k]'$. If this step is not properly executed, then $Ch$ can challenge on this by `computationChallenge`.

#### Exit

1. User $U$ calls `startExit()` in $a_R$ with arguments of $a_r$, `trieKey` and `trieValue` in order to exit $A^{c}_{s}[k]$ to correspoding $a_r$.
2. `exitRequest` of $U$ is generated in $a_R$ and it is included in next `requestBlock` by $O$. If $O$ does not include it, then $Ch$ can challenge on this by `requestChallenge`.
3. In the next `requestBlock`, there is a transaction that $NA$ executes `applyRequestInChildchain()` in $a_c$ in accordance with the `exitRequest`. If *step 3* is not properly executed, $Ch$ also can challenge by `computationChallenge`.
4. If *step 3* is properly executed but the transaction is reverted, then $Ch$ can challenge on the `exitRequest` by `exitChallenge` using the transaction output as a proof.
5. If there is no challenge in *step4*, `exitRequest` can be considerd as `finalized`. But If `exitChallenge` is proved right, the `exitRequest` is cancelled.
6. $U$ can finalize `exitRequest` by calling `finalizeExit()` in $a_R$. $a_R$ calls `applyRequestInRootchain()` in $a_r$. By the result of execution of `applyRequestInRootchain()`, $A^{r}_{s}[k]$ is successfully changed to $A^{r}_{s}[k]'$. Contract developer **MUST** make sure that `applyRequestInRootchain()` in $a_r$ should not be thrown. This change is mandatory, and the validity of exit only can be cheked in `applyRequestInChildChain()` in $a_c$ that can be used as a proof for `exitChallenge`.

#### RootChain and Requestable Contract
The RootChain contract in root chain *has* `RequestableRootChain` interface. Requestable contracts can make an `enterRequest` to enter its storage variable from $a_r$ to $a_c$. User can also directly make an enter request with `rootchain.enter`.

interface RequestableRootChain {
  function getExitFinalized(uint256 requestId) public returns(bool);
  
  function startExit(
    address contractAdderess,
    bytes32 trieKey,
    bytes32 trieValue
  ) returns (bool);
  
  // User can directly make an enter request with trieKey and trieValue.
  function enter(
    address contractAdderess,
    bytes32 trieKey,
    bytes32 trieValue
  ) returns (bool);

  // Requestable contract can initialize an enter request with proper
  // trieKey and trieValue. This makes user not to take care of what is exact
  // trieKey for `balances[requestor]`.
  function makeEnterRequest(
    address requestor,
    bytes32 trieKey,
    bytes32 trieValue
  ) returns (bool);
  
  // finalize exits 
  function finalizeExit() public returns (bool);
}

interface Requestable {
  // check the request is applied or not in root chain.
  function setRequestApplied(uint256 requestId) internal returns (bool);
  function getRequestApplied(uint256 requestId) internal returns (bool);

  // Apply storage changes in root chain for exit and enter reuqests.
  // For enter request, This is called in the middle of `rootchain.enter`
  // or `rootchain.makeEnterRequest` to initialize an enter request.
  // If this returns true, the enter request is queued into `enterRequests`.
  // For exit request, This is called in  `rootchain.finalizeExit`.
  function applyRequestInRootChain(
    bool isExit,
    uint256 requestId,
    address requestor,
    bytes32 trieKey,
    bytes32 trieValue
  ) external returns (bool success);
  
  function applyRequestInChildChain(
    bool isExit,
    uint256 requestId,
    address requestor,
    bytes32 trieKey,
    bytes32 trieValue
  ) external returns (bool success);
}

An example of simple requestable token contract would be implemented as below.

contract RequestableToken is Requestable {
  // 3 requestable variables.
  address owner;     // `owner` is stored at bytes32(0).
  uint totalSupply;  // `totalSupply` is stored at bytes32(1).
  
  // `balances[addr]` is stored at keccak256(bytes32(addr), bytes32(2)).
  mapping(address => uint) balances; 
  
  RequestableRootChain rootchain;
  address NULL_ADDRESS = address(0); // or 0xFF..FF

  // this is only called by the RootChain contract in root chain 
  // when i) enterRequest is initialized or
  //     ii) exitRequest is finalized
  function applyRequestInRootChain(
    bool isExit,
    uint256 requestId,
    address requestor,
    bytes32 trieKey,
    bytes32 trieValue
  ) external returns (bool success) {
    require(msg.sender == address(rootchain));
    require(!getRequestApplied(requestId)); // check double applying

    if (isExit) {
      // exit must be finalized.
      require(rootchain.getExitFinalized(requestId));

      if(bytes32(0) == trieKey) {
        // only owner (in child chain) can exit `owner` variable.
        // but it is checked in applyRequestInChildChain and exitChallenge.
        
        // set requestor as owner in root chain.
        owner = requestor;
      } else if(bytes32(1) == trieKey) {
        // no one can exit `totalSupply` variable.
        // but do nothing to return true.
      } else if (keccak256(requestor, 2) == trieKey) { 
        // this checks trie key equals to `balances[requestor]`.
        // only token holder can exit one's token.
        // exiting means moving tokens from child chain to root chain.
        balances[requestor] += uint(trieValue);
      } else {
        // cannot exit other variables.
        // but do nothing to return true.
      }
    } else {
      // apply enter
      if(bytes32(0) == trieKey) {
        // only owner (in root chain) can enter `owner` variable.
        require(owner == requestor); 
        // do nothing in root chain
      } else if(bytes32(1) == trieKey) {
        // no one can enter `totalSupply` variable.
        revert(); 
      } else if (keccak256(bytes32(requestor), bytes32(2)) == trieKey) {
        // this checks trie key equals to `balances[requestor]`.
        // only token holder can enter one's token.
        // entering means moving tokens from root chain to child chain.
        require(balances[requestor] >= uint(trieValue));
        balances[requestor] -= uint(trieValue);
      } else {
        // cannot apply request on other variables.
        revert();
      }
    }
    
    setRequestApplied(requestId);
    return true;
  }

  // this is only called by NULL_ADDRESS in child chain 
  // when i) exitRequest is initialized by startExit() or
  //     ii) enterRequest is initialized
  function applyRequestInChildChain(
    bool isExit,
    uint256 requestId,
    address requestor,
    bytes32 trieKey,
    bytes32 trieValue
  ) external returns (bool success) {
    require(msg.sender == NULL_ADDRESS);

    if (isExit) { 
      if(bytes32(0) == trieKey) {
        // only owner (in child chain) can exit `owner` variable.
        require(requestor == owner); 

        // do nothing when exit `owner` in child chain
      } else if(bytes32(1) == trieKey) {
        // no one can exit `totalSupply` variable.
        revert(); 
      } else if (keccak256(bytes32(requestor), bytes32(2)) == trieKey) {
        // this checks trie key equals to `balances[tokenHolder]`.
        // only token holder can exit one's token.
        // exiting means moving tokens from child chain to root chain.
        
        // revert provides a proof for `exitChallenge`.
        require(balances[requestor] >= uint(trieValue)); 
        
        balances[requestor] -= uint(trieValue);
      } else { // cannot exit other variables.
        revert();
      }
    } else { // apply enter
      if(bytes32(0) == trieKey) {
        // only owner (in root chain) can make enterRequest of `owner` variable.
        // but it is checked in applyRequestInRootChain.
        
        owner = requestor;
      } else if(bytes32(1) == trieKey) {
        // no one can enter `totalSupply` variable.
      } else if (keccak256(bytes32(requestor), 2) == trieKey) {
        // this checks trie key equals to `balances[tokenHolder]`.
        // only token holder can enter one's token.
        // entering means moving tokens from root chain to child chain.
        balances[requestor] += uint(trieValue);
      } else { 
        // cannot apply request on other variables.
      }
    }

    return true; 
  }
  
  // make an enter request for `owner` variable.
  function enterOwner() external returns (bool) {
    require(msg.sender == owner);
    
    require(rootchain.makeEnterRequest(msg.sender, bytes32(0), owner));
    
    return true;
  }
  
  // make an enter request for `balances[msg.sender]`.
  // If user know trieKey, one can call `rootchain.enter` directly.
  function enterBalance(uint amount) exernal returns (bool) {
    // it is also checked in applyRequestInRootChain
    require(balances[msg.sender] >= amount);
    
    bytes32 trieKey = keccak256(bytes32(msg.sender), bytes32(2));
    
    // this subtracts `balances[msg.sender]` by `amount`
    require(rootchain.makeEnterRequest(msg.sender, trieKey, amount);
    
    return true;
  }
  
  // User can get the trie key of one's balance and make an enter request directly.
  function getBalanceTrieKey(address who) public pure returns (bytes32) {
    return keccak256(bytes32(who), bytes32(2));
  }
}

### Challenges

#### CAS Challenge
If operator sign off on the block with transactors' confirmation but transactor notices that the block include transaction one doesn't confirmed, the transactor can challenge on it. If operator cannot disprove the challenge by providing the confirmation signature, the block is reverted and operator should submit a valid block with all transactions confirmed.

#### Request Challenge
Request Challenge requires the RootChain contract to know the way of constructing transaction data with some parameters to verify valid request. We know that `from` is NULL_ADDRESS, `to` is the ChildChain contract, `value` should always be 0, `data` is defined by request type and parameters, and finally `nonce` is sequentially incremented number by each request. If the actual data is not matched with the data constructed by RootChain contract, the `requestBlock` is reverted to previous `nonReqeustBlock`. The request's computation can be verified in computation challenge.

#### NullAddress Challenge
It just verify that `nonRequestBlock` has a transaction that transactor is NULL_ADDRESS.

#### Exit Challenge
In the case where an `exitRequest` was included in `requestBlock` and the corresponding transaction was *reverted*, the `exitRequest` **MUST** be deleted from the RootChain contract. Exit challenge on the invalid `exitRequest` process it with proof of the reverted transaction. But to challenge on the exit request, the block, where the request is applied, should be finalized because the transaction may be reverted in invalid block, but it may not be reveretd in valid block. So the exit challenge can be initialized after the `requestBlock` is finalized.

#### Computation Challenge
Computation challenge verify operator execute transaction correctly, meaning the state is transited in predefined ways(eg. smat contract bytecode). If operator submits wrong `stateRoot`, it can be challenged with `txData`, `preStateRoot`, and `postStateRoot`, using TrueBit-like verification game.

$$postState = STF_{tx}(preState, TX_i)$$

$$postState = postTransactionalStates[i]$$

$$
preState=\begin{cases}
postTransactionalStates[i-1] & \text{if}\ i>0 \\
previousStateRoot & \text{otherwise}\end{cases}$$

We can verify whether the computation is correct or not by simulating $STF_{tx}$ in RootChain contract and by comparing the output to already submitted output.

#### Verification Game
TrueBit proposed *verification game* to verify outsourced computation. But the last step of the game is doing one computation on Ethereum and checking the output and expected output. Ohalo and PARSEC have been implementing solevm, a smart contract running EVM inside EVM. We employ it solevm verify the computation.


However, to use [fee-delegated chain](https://hackmd.io/s/SkxNKAXU7), we have to extend solevm to cover transaction execution over EVM.

### Future Works

#### Sybil Attack
Iterative and interactive confirmation model is vulnerable to sybil attack if attacker send many transactions and refuse to confirm one transaction for each confirm-sig request. This makes number of iteration of `Seal Block` and `Request Confirm Sigs` up to the number of transactions attacker sent unless other transactors are honest and online.

### References
- [Joseph Poon and Vitalik Buterin, Plasma: Scalable Autonomous Smart Contracts](https://plasma.io/)
- [Minimal Viable Plasma](https://ethresear.ch/t/minimal-viable-plasma/426)
- [Plasma Cash](https://ethresear.ch/t/plasma-cash-plasma-with-much-less-per-user-data-checking/1298)
- [Plasma XT](https://ethresear.ch/t/plasma-xt-plasma-cash-with-much-less-per-user-data-checking/)
- [Cryptoeconomic aggregated signature](https://ethresear.ch/t/cryptoeconomic-signature-aggregation/)
- [PARSEC Labs, PLASMA - FROM MVP TO GENERAL COMPUTATION](https://parseclabs.org/files/plasma-computation.pdf)
- [Why Smart Contracts are NOT feasible on Plasma](https://ethresear.ch/t/why-smart-contracts-are-not-feasible-on-plasma/2598)
- [TrueBit, A scalable verification solution for blockchains ](https://people.cs.uchicago.edu/~teutsch/papers/truebit.pdf)