# Plasma EVM 2.1 : State-enforceable, turing-complete plasma
Carl Park (Onther Inc.)
Aiden Park (Onther Inc.)
Kevin Jeong (Onther Inc.)

Kor-Eng Translation : Jay Lee (Adevt Co.)

:::info
[Korean Version(2.1) Link](https://hackmd.io/s/B1r45tQC7)
:::
:::warning
This paper is outdated.
Latest Version of this document is [here](https://github.com/Onther-Tech/papers/blob/master/tech-paper/build/plasma-evm.pdf).
:::

### [Change Logs](https://hackmd.io/s/BJ8v8YggV)
Plasme EVM is updated to 2.1 version, check the change logs above.

## 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 can be submitted to root chain, providing a way to enter and exit account storage between two chains because each chain has identical architecture. Plasma EVM can improve decentralization, performance, reliability and usability of Dapp, by migrating it from current ethereum chain to the plasma chain.

# Glossary
## General
- **Root chain**: Ethereum Blockchain
- **Child chain**: Plasma blockchain.
- **Operator**: Agent that operate child chain
- **NULL_ADDRESS**: `0x00` or `0xFF...FF`(`2^160 - 1`) with nonce and signature `v = r = s = 0`, denoted $NA$.
- **Transactor**: Account which generate transaction, `tx.origin`.
- **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**: A block, applying state transition that is enforced by the root chain.
- **nonRequestBlock**: A block where transactions are only related between accounts in child chain.

<br>

## Challenges

- **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.
- **computationChallenge period**: Period of computation challenge. denoted $CP_{computation}$.
- **exitChallenge**: challenge if invalid `exitRequest` cannot be accepted in child chain (but the request should be included in `requestBlock`).
- **exitChallenge**: Period of exit challenge. denoted $CP_{request}$.
- **Finalized** : After $CP_{computation}$ from its submission, Every block could be deterministically finalized. and Every `exitRequest` could be deterministically finalized after $CP_{request}$.

<br>

## Solution to Data availability problem
* **User-Activated fork ($UAF$)** : Fork activated by user. Exit method for data availability problem.
* **User Request Block ($URB$)** : Request Block submitted by a user. Unlike the existing Request Block, it contains only transactions that reflect the Exit Request for URB of submitter or other user.
* **Operator Request Block ($ORB$)** : Request Block submitted by the Operator. It is same as the requestBlock in Plasma EVM.
* **Exit Request for ORB ($ERO$)** : Exit Request using ORB
* **Exit Request for URB ($ERU$)** : Exit Request using URB
* **Rebase** : If the URB is submitted based on the most recent finalized block, all child blocks that are submitted but not finalized will be located behind the corresponding URB and transactions that conflict with the URB will be reverted. This is called a Rebase.
* **Cost for User Request Block ($C_{URB}$)** : Cost to commiter in commiting $URB$ to Root chain.
* **Cost for Exit Request for URB ($C_{ERU}$)** : Cost to each user in commiting block include $ERU$.
* **Number of Exit Request for URB ($N_{ERU}$)** : Number of $ERU$ included in $URB$
* **Total Cost for User Request Block ($C_{URB}^{total}$)** : Total cost in commiting $URB$ to Root chain. $C_{URB}^{total}$ is calculated as $C_{URB}$ + $N_{ERU}$*$C_{ERU}$.

<br>

---

# 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 few 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. The request is queued on `exitRequests` and operator (or NULL_ADDRESS) **MUST** generate 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.

<!-- TODO: epoch 수정 -->
*<center>Fig 1 : State transition of Root chain contract</center>*

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. Initially, `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`. It can be challenged in any of following circumstances; when it contains a transaction from NULL_ADDRESS (*nullAddressChallenge*) or when the state is transited in a wrong way (*computationChallenge*). A successful challenge recovers child chian from byzantine state.

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

3. Since the second type of 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.

- 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`.

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

*<center>Fig 2 : Request and challenge diagram</center>*

### Epoch
An Epoch has N($N>=2$) blocks, N-1 `nonRequestBlock` and 1 `requestBlock`. The trivial case described in *Fig 2* is where epoch length is 2. But epoch length can be extended to reduce the ratio of `requestBlock` to `nonRequestBlock`.
<br>

## Block submission
Operator submits 3 merkle roots, `stateRoot`, `transactionsRoot`, and `postTransactionalStatesRoot`(or `intermediateStatesRoot`) for each block. If the state is computed in a wrong way, a computation challenge can recover it to the block whose the state is correct. It can be resolved by TrueBit-like verification game, verifying a 'state transition function by transaction' with pre-stateRoot and post-stateRoot.

## Finality
Plasma EVM is capable of checkpointing blocks like Plasma XT if block cannot be challlenged anymore 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$
Challenger: $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 $A^{c}_{s}[k]$ on the basis of $A^{r}_{s}[k]$ and Exit is that changes $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 there should be considerations about 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. 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
*<center>Fig 3 : Enter diagram</center>*

<br>

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
*<center>Fig 4 : Exit diagram</center>*

<br>

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
for `exitChallenge`.

<br>

## 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 contractAddress,
    bytes32 trieKey,
    bytes32 trieValue
  ) returns (bool);
  
  // User can directly make an enter request with trieKey and trieValue.
  function enter(
    address contractAddress,
    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));
  }
}

<br>

# Challenges

## Request Challenge
`requestChallenge` 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 `nonce` is sequentially incremented number by each request. If the actual transaction 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.

<br>

## NullAdress Challenge
This verifies whether `nonRequestBlock` has a transaction that transactor is NULL_ADDRESS.

<br>

## 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.

<br>

## Computation Challenge
Computation challenge verifies whether the operator executes transactions correctly or not, 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 comparing the output with expected output. Ohalo and PARSEC have been implementing solevm, a smart contract running EVM inside EVM. We employ it solevm verify the computation.

*<center>Fig 5 : verification game</center>*

<br>

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

## Challenge period
There are two types of challenge periods in plasma EVM. The first is the challenge period for the block, $CP_{computation}$, and the second is the computation challenge period for the exitRequest, $CP_{request}$. the submitted block and exitRequest could be finalized only if the assigned challenge period is passed without any valid challenge. The length of each challenge period is as follows:

$$ CP_{computation} = 1 day $$

$$ CP_{request} = 1 day $$

The reason why the challenge period for the block is $CP_{computation}$ is that $CP_{computation}$ can cover all kinds of challenges for the block. The result is determined by the challenge, except for the Computation Challenge, to send a single transaction. However, the Computation Challenge requires at least 90 transactions in the worst case, based on the Block Gas Limit of 100 million in the child chain. Thus, $CP_{computation}$ is sufficient time to execute all other kinds of challenges for the block.

The reason $CP_{computation}$ is 1 day is that it takes at least 2 hours to 2 hours 30 minutes for 90 transactions to be submitted, which may vary depending on the network conditions. However, the challenge period would be shortened by changing the current verification method from Verification game to more efficient way through applying zero-knowledge proof.

*<center>Fig 6 : challenge period</center>*

<br>

# Solution to Data availability problem

Plasma EVM presents User-Activated Fork (UAF) and dynamic cost mechanism as a solution to data availability problem (DA problem). It is based on the following documents: [A proposal for Data availability Solution of Plasma EVM](https://hackmd.io/kXWTlmyhSP2vVSIzsenU8w?view)

At Plasma EVM, users can enforce valid state transition by submitting a User Request Block (URB) to create a UAF in the event of a DA problem from the operator's data withholding attack. To prevent confusion caused by reckless fork generated independently of DA problems, we introduce a cost mechanism that dynamically charges the fork.

<br>

## User-Activated Fork
As mentioned above, users aware of DA problem in the child chain can submit URB and exit safely from the child chain. In this case, the parent block of URB should be the last finalized block. Also, URB should only include ERU submitted to the RootChain contract. When URB submitted, the operator must execute the **Rebase** process and submit NRB whose parent block is the submitted URB.

*<center>Fig 7 : UAF diagram 1</center>*

Block#1 is currently in finalized state, and the root chain is submitted up to NRB#5. Suppose that NRB#3 is in the withheld state by the operator and DA problem has occurred. Users can then safely exit the child chain by submitting URB#2 and generating a fork until NRB#3 is finalized. The parent block of the submitted URB must be Block#1, which is the last finalized block as shown in *Fig 7*. In this process, the user submitting the URB should reflect requests contained in previously submitted ORBs. However, newly submitted EROs should not be included in the URB.

<br>

*<center>Fig 8 : UAF diagram 2</center>*

When a URB is submitted and a fork occurs, the operator must execute the **Rebase** process to continue the chain. As shown in *Fig 8*, the operator must submit NRB#3'and NRB#4' with the same $transactionRoot$ as NRB#3 and NRB#5 submitted previously. That is, all transactions that were included in the previous NRB should be included in the new NRB'. In addition, NRB#3' and NRB#4' should be on the basis of URB#2.

### Mass URB
To submit URB, `prepareToSubmitURB` function should be called in the RootChain contract. However, if DA problem occurs, users may call `prepareToSubmitURB` function concurrently to submit URB. In this case, the first user to send a transaction calling `prepareToSubmitURB` is entitled to submit the URB.

Since URB to be submitted is a block containing ERUs submitted to the RootChain contract, the transactions to be included have already been determined before submission. Therefore, this decision for submission right for URB does not matter because the exit request being processed is the same as which user is entitled.

### Extension of chain head
Submission of URB does not always create a fork. If a URB is submitted before a previous URB has been finalized, submission of the URB is considered to extend the chain head, not the fork. Therefore, subsequent URB must be a child block of the previous URB. In this case, of course, the operator must also execute rebase process based on the newly extended chain head.

if URB is submitted after a previously submitted URB has been finalized, subsequent URBs are considered as the fork rather than extension of the chain head. Therefore, the parent block of the submitted URB shall be of the last finalized block. After submission of the corresponding URB, the operator must execute rebase process.
<br>

*<center>Fig 9 : Extension of chain head</center>*

Let's take a closer look at the case of extending the chain head in *Fig 9*. URB#3 was submitted sequentially after submission of URB#2. In this case, the state of URB#3 must be calculated based on URB#2. Therefore, although URB is newly submitted, it does not create the fork based on Block#1, but extends the head of the blockchain containing URB#2. The operator must rebase all existing blocks based on the newly extended URB#3.

<br>

### Invalid URB
*<center>Fig 10 : Invalid URB</center>*

*Fig 10* shows the process when stateRoot of the submitted URB is not valid so the request has challenged. In the figure, URB#3 is submitted by another user based on URB#2 and NRB#3' and NRB#4' in which the operator rebased are submitted. In this situation, the challenge to URB#2 succeeded. This means that all descendant blocks including URB#2 and having URB#2 as an ancestor block are no longer valid. In the case of a penalty for a challenge, the submitters who submitted the URB#2 and another URB with an invalid URB as an ancestor block will be penalized. Operators are not penalized even if they rebase based on invalid URBs.

When submitting a computation challenge for a URB, the challenger must submit a new stateRoot, transactionRoot, and receiptRoot for the URB and its descendant URBs. Also, as with the rebase process, the new transactionRoot must be the same as the transactionRoot of the URB being challenged. In other words, the challenger challenges URB#2 and submits URB#2'and URB#3' at the same time. After the challenge, the operator must rebase the existing NRBs following URB#3'.

### Data availability of URB
URB cannot be the target of Data withholding attack. The reason is as follows: Since the parent block of the URB is always a finalized block and the transactions included in the URB are exposed to the RootChain contract, anyone can know about the correct stateRoot of the URB.
<br>

## Cost mechanism against Infinite fork attack

### Infinite fork attack
In the case of DA problem, user-activated fork method can make anyone exit safely by submitting URB based on last finalized block. But there is a fatal weakness here, the Infinite fork attack using the rebase process. A malicious user can endlessly block the finalization of a block by continuously submitting URBs, regardless of the DA problem. This is because, at the moment when the URB is submitted, the existing unfinalized NRBs must be rebased, which requires placing a new challenge period in the corresponding blocks.
<br>

### Dynamic cost mechanism
We have introduced a dynamic cost mechanism for user-activated fork to prevent such attacks. The design objectives of the cost mechanism are as follows.

**1. If the submission of URB is close to the probability that it is an attack by malicious users, the cost should be high. And if it is close to the probability that it is an escape from a problem, the cost should be set low.
2. The number of URB commits that generate Rebase should be minimized.**

DA problem is hard to tackle because it is very difficult to determine whether DA problem actually occurred in the child chain. Therefore, in Plasma EVM, we need to approach the DA problem in terms of probabilities, as described in the first principle.

There is also a possibility that there was still no real DA problem, even if there were a lot of users who thought that the URB should be commited because of DA problem. Therefore, as specified in the second principle, URB commits should be minimized in all circumstances to ensure sustainable operation of child chain.
<br>

### DA probability
The first principle is a very valid rule in itself, but there is a limit that we can apply it only if we know the probability. In other words, how accurate the probability can be is the key point in this cost mechanism design. What is the best material for calculating the probability? We said earlier that we leave the judgment of the DA to the individual users. If an independent individual makes one's own judgment on DA matters, it is the individual's judgment that is most relevant to the probability of DA problems.

That is, the greater the number of users who believe that there is the DA problem, the greater the likelihood of DA occurrence. On the contrary, if there are fewer users who believe there is DA problem, chances are high that there were no problems with the Child Chain. Therefore, we will design a model that estimates the probability of a DA issue and adjusts the costs for the URB and ERU accordingly through user's judgments about DA problems, i.e. **the number of ERUs**.

Of course, the assumption that all of the accounts submitted the ERU would be independent is very naive. Because of that, an additional cost should be charged for the ERU as well. If an attacker is to make a favorable condition for submission of URB using a number of accounts, one must also pay a full cost for ERUs. There will be of no use to do this attack.

<br>

### Cost function

Let's discuss what types of cost functions should be derived to meet the principles outlined above as much as possible. To satisfy the first principle, the higher the number of ERUs in the URB, the lower the URB's submission costs and the cost of the ERB. In addition, to meet the second principle, it would be desirable to increase the extent of the decreasing cost as the number of ERUs increases.

**$C_{URB}$ : Cost for submitting URB
$C_{ERU}$ : Cost for Exit by ERU
$N_{ERU}$ : The number of ERUs in URB**

As defined above, a cost function meeting the above conditions may be like below.

<div style="text-align:center">

*Fig 11 : Cost function of submitting URB*
</div>

The costs of submitting the URB are as shown above. As $N_{ERU}$(the number of ERUs in the URB) increases, the slope of the curve decreases steeply. If $N_{ERU}$ exceeds the specific point S, $C_{URB}$ is no longer reduced. We will discuss it further below, but the reason setting it not to decrease below a certain level is because we should consider a case which an attacker carry out a kind of sybil attack by creating multiple accounts.

And, as $N_{ERU}$ increases, $C_{URB}$ does not decrease linearly, and the reason why it is this shape is to satisfy the second principle as much as possible. If the cost curve is linear, the marginal cost which is decreased by increasing $N_{ERU}$ is constant, but if it is in the shape of the curve, the marginal cost is increasing as $N_{ERU}$ increases. It is recommended that the user submitting the URB includes as many ERUs as possible. As a result, only a few URBs can efficiently handle the ERUs.

<div style="text-align:center">

*Fig 12 : Deposit amount for submitting URB*
</div>

URB submitters should deposit the $D_{URB}$ with the above submission costs to ensure the validity of the URB. This will be returned to all submitters when the URB is finalized, and all $D_{URB}$ will be confiscated if the challenge against the URB is successful.

However, the challenger who challenges for URB can submit a new URB by depositing only $D_{URB}$.

<div style="text-align:center">

*Fig 14 : Cost function of submitting ERU*
</div>

The cost of exit through the ERU is shown in *Fig 14*. $C_{ERU}$ also decreases as $N_{ERU}$ increases. As with the curve of $C_{URB}$, we are preventing the cost from falling below a certain level to prevent sybil attacks. When user submitted ERU, one should deposit $C_{ERU}$ at $N_{ERU}=0$. The deposit will be returned later except for $C_{ERU}$ based on $N_{ERU}$ in URB submitted.

<br>

### Total cost
You will remember about the sybil attack we talked about when we explained Cost function. If an attacker generates an ERU by generating multiple accounts, there is a risk that the attack cost will be too low if $C_{URB}$ and $C_{ERU}$ become too low. To prevent this, the cost has been prevented from falling below a certain level, which is not in fact a perfect form of preventing such an attack.

Assuming that $N_{ERU}$ was all created by the attacker for convenience, $C_{URB}^{total}$ that the attacker would ultimately be $C_{URB} + C_{ERU}*N_{ERU}$. Based on the cost functions presented above, the form of Total Cost can then be briefly presented in Fig 15.

<div style="text-align:center">

*Fig 15 : Total cost function*
</div>

The above curve shows a decrease in $C_{URB}^{total}$ as $N_{ERU}$ increases. This is because the slope of Total Cost curve becomes a form of decreasing, since the slope of both $C_{URB}$ and $C_{ERU}$ decreases. After all, if an attacker attacks, one will generate $N_{ERU}$ up to the point where $C_{URB}^{total}$ is the lowest. Even in such cases, it may not be a big problem if the $C_{URB}^{total}$ is high enough.

However, maintaining high $C_{URB}^{total}$ in situations where $N_{ERU}$ is large enough is necessarily making a problem that also increases the burden on users to Exit. it requires further research to solve this problem.

<br>

## Issues
### Resolved issues
#### 1. Block withholding attack for specific users
The UAF model can be seen as a form of users sharing the cost for the fork. Therefore, when the operator performs data withholding attack on specific user, the user may be forced to exit through the URB at a high cost alone. However, this can be easily resolved by allowing other users operating a full node to deliver the block to that user over a P2P network. An honest user can always be the target of operator's attack. Therefore, there are enough incentives to share blocks while maintaining P2P connection with other users. it is very likely that the above attack pattern will easily lose its effect.
<br>

#### 2. Withholding attack for some state data that affect specific users
If some of the state data (e.g. user A's cryptokitty ownership) that only affects particular user is changed into invalid state and is then withheld, no other user is motivated to participate in the UAF. As a result, the operator can attack only a specific user, thereby making it possible to maximize the effect of the attack by forcing the user to pay a large cost for URB submission. If such an attack is possible, plasma EVM will be very vulnerable to DA problems. However, such an attack is impossible in plasma EVM.

This is because it is impossible to withhold only a part of a certain state. The object that the operator can withhold means the data that the operator must deliver when propagating the block to another full node. That is, the data that need not be delivered cannot be the subject of withholding. In Ethereum the header and the transactions are delivered when the block is propagated. The header contains root values, such as stateRoot, and the transaction is literally a transaction.

The nodes that have propagated the block go through various verification processes for the corresponding block. The key is to check whether the stateRoot derived by executing the transferred transactions one by one matches the stateRoot of the received header. This also changes the state of the various accounts.

The important thing is that the state database itself is not propagated. Because it does not propagate the state database in the first place, it is impossible to withhold only part of the state. If a block propagated by the operator is only withheld a portion of the data, anyone can recognize DA problem in the process of verifying the block. But the only information that users can see here is that part of the block data to be delivered is missing, and an invalid stateRoot has been submitted to the root chain.

It is impossible to see only stateRoot changes and identify which specific data has changed in that tree, as it is impossible to identify which data has changed in that tree when the root of a Merkel tree has changed. In other words, when some of the blocks withhold, there is no way to verify that your Ether is attacked or another user's cryptokitty is attacked. All that is known is the fact that the operator has made an invalid state transition and has not properly propagated all the data about it. Therefore, the operator cannot make data withholding attack that affects specific user, because all users are always have an incentive to exit through UAF in case of when the data is withheld partially.

<br>

### Unsolved issues
#### 1. Submitting URB to cancel past transactions
The disadvantage of the user-activated fork model is that it is possible to change the valid state by the fork until it is finalized. Let's take a brief look at the following example.

Suppose there is a plasma chain in which Decentralized Exchange (DEX) is running. Token A is actively trading in DEX. Many users sent transaction T an hour ago, which bought A in bulk for 1 Ether. However, the collapse of the cryptographic market caused A to plunge to 0.1 Ether. Also, the block containing all the current Ts is not finalized. In this case, if the cost for UAF is lower than the expected loss for finalization of T, the users who transmitted T will have an incentive to exit their Ether through UAF and change the execution result of T in the newly rebased block, In other words, if gain in revoking past transactions is greater than the cost of UAF, users always have incentives to generate UAF even if there is no DA problem.
<br>

# 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/)
- [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)