# A proposal for Data availability Solution of Plasma EVM

Carl Park([e-mail])
Aiden Park([e-mail])
*Kevin Jeong([e-mail], corresponding)

:::info
[Korean Version Link](https://hackmd.io/s/H1bk0Z-DQ)
:::

## Abstract
This article proposes a model to address the most problematic Data Availability (DA) in [Plasma EVM](https://hackmd.io/m8TXSv2eSkGwsj7ni27Mag?both). This model has a new **'User Request Block'**, which is a way for ensuring vaild Exit for users in case of data withholding, while leaving the judgment on DA entirely to the individual user. It also introduces a **dynamic fee model** to prevent infinite loop attacks by malicious users pretending to behave as if there were DA problems.

<br>

## What were the problems?
The problems with the existing model can be divided into two main types. First, an easy DoS attack using a kind of Sybil Attack is possible during the Confirmation process. The second is that the Confirmation model itself does not fully solve the DA.

Let's take a closer look at the first case. The original purpose was to have the Confirmation process take place and collect the Confirm signature of all transactors in the block and submit it with the hash of the block to resolve DA beforehand. However, if even one transactor refused to confirm or did not respond on time, there was an issue of having to go through a confirmation process again for a new block, except for not confirmed transaction. For example, if an attacker generates transactions using $n$ accounts and then rejects Confirm in just one of $n$ accounts and repeat it one by one, the block cannot be submitted for $n$ Confirm times.

The second problem is that the Confirmation model has serious flaws that cannot solve the DA problem. This is because receive Confirm from only the users who send the transactions contained in the block, not the entire user. That is, users who do not send transactions are omitted during Confirmation process, so even if the operator withholds Block data, there is no way to defend it. For example, the Child Chain has Operator O, User A, and User B. Currently, Child Block #1 contains only transactions sent by user A. A and O conspire to create an invalid block #1 and submit it to the root chain. All it takes to do this is Confirm signature of A. Thus, in this process, B has no means of defending against the DA. The existing model did not guarantee the safety of user's assets because of these problems.

<br>

## New Exit model : User Request Block

### Glossary
**Non-Request Block(NRB)** : Same as nonRequestBlock in Plasma EVM
**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
**Challenge period for computation($CP_{computation}$)** : challenge period for computation challenge of ORB
**Challenge period for withholding($CP_{withholding}$)** : challenge period for withholding of NRB
**Finalized** : Every Block is finalized after their challenge period.
**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**.
<br>

Confirmation does not exist anymore in the new model. In addition, whether DA problem occurs or not, is not judged at all in the process of mining and submitting the block. Instead, users who noticed that there was DA problem in child chain can safely exit by committing an URB based on the most recent defined block including their own and other user's ERUs. Once the URB is committed, then the operator should rebase the unfinalized blocks to reflect the contents of the URB. If it is judged that there are no problems with the user's perspective, users can wait until the operator includes one's Exit request, using ERO instead of ERU like the previous model.

Let's take a closer look through a diagram.

Block#1 is currently in finalized state, and the root chain is submitted up to NRB#5. ORB becomes finalized only after $CP_{computation}$ from the time it is submitted, and NRB also becomes finalized after $CP_{withholding}$ from the time it is submitted. In this diagram, $CP_{computation}$ is set for one hour and $CP_{wiholding}$ is set for one day.

Since the challenge period of ORB#4, $CP_{computation}$ is shorter than the challenge period of NRB#3, $CP_{withholding}$, ORB#4 will be finalized earlier than NRB#3 under normal circumstances. Therefore, NRB#3 is also finalized as soon as ORB#4 is finalized. In other words, if there is no problem, the NRB's challenge period, $CP_{withholding}$ is Creation time of next ORB+$CP_{computation}$.

Now let's say NRB#3 is withheld. Of course, no one can prove that it was actually withheld. However, any user who believes that withholding has occurred can submit an ERU and safely exit the Child Chain through submitting the URB. In here, one who submits URB#2 should include transactions that reflect one's own exit request and other user's ERU on the basis of Block#1, the most recent finalized block. And also one should include all of requests in the ORB submitted previously. However, newly submitted ERO should not be included.

Submission of the URB means a kind of fork by a user. In other words, if the user judges there is data withholding in child chain, one can change the canonical chain by creating a fork. After URB#2 is submitted, the operator must execute the **Rebase** process in which the previously submitted NRB is newly mined and submitted based on URB#2. NRB#3' and NRB#4' submitted should have the same $transactionRoot$ as the existing NRB#3 and NRB#5 respectively. That is, all transactions that were included in the previous NRB should be included in the new NRB'. In addition, the challenge period of NRB#3' and NRB#4' are newly set to $CP_{withholding}$ as users have determined that there was a withholding problem.

<br>

## Fee model against Infinite loop attack

### Infinite loop attack

The new model left the judgment of 'block withholding' to the individual users, and in case of a problem, URB can be submitted for safe Exit at any time. However, there is a fatal vulnerability issue in this model. It is a kind of **infinite loop attack using Rebase**. Malicious users can continuously commit URB regardless of whether there is Withholding or not, thus preventing finalization of subsequent child blocks. This is because, after the URB is submitted, the NRB is Rebased and the challenge period is updated to $CP_{withholding}$. Of course, there are aspects that can waste the resources of the operator, but the most serious problem is that it can prevent proper operation of child chain by making finalization of blocks unavailable.

<br>

### Fee model
We have introduced a model to charge fees for URB and ERU to prevent such attacks.

The design objectives of the fee model are as follows.

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

With repeated emphasis, we cannot judge whether there were actually DA problems with the Child Chain. Therefore, we need to approach the DA problem in terms of probabilities, as described in the first principle. Because the URB is also the last resort for users to secure Exit in the event of DA issue, but it is also a powerful weapon that could seriously impede the child chain's operation if it is used for attack.

There is also a possibility that there was still no real problem with the Child Chain, 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, it should always be possible to efficiently handle user's ERUs through as few URB commits as possible 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 fee model 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 fees 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 fee 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 fee 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.

**Cost of submitting the URB**
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 include as many ERUs as possible. As a result, only a few URBs can efficiently handle the ERUs.

**Cost of ERU**
The cost of exit through the ERU is shown above. $C_{ERU}$ also has a decrease 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 fees based on $N_{ERU}$ in URB submitted.

<br>

### The importance of 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, the total cost 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 as follows:

**Total cost function**

The above curve shows a decrease in total cost 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 Total Cost is the lowest. Even in such cases, it may not be a big problem if the Total cost is high enough.

However, maintaining high Total Cost in situations where $N_{ERU}$ is large enough is necessarily making a problem that also increases the burden on users to Exit. The most desirable form is that the slope of the Total Cost curve is positive or zero and the slope of the $C_{URB}$ and $C_{ERU}$ curve becomes negative, either by modifying the current cost function or by adding other parameters. But this requires further research.

<br>

### Various Cases
The previous section discussed specific types of cost functions. In this section, let's assume various cases and take a brief look at the above model to see if there are any problems.

The first case is when an attacker incites users to submit an ERU. In this case, an attacker would attempt to incite users who does not operate full node in the child chain. However, it is likely that such attempts will not be easy. It is difficult for an attacker to prove that withholding has occurred, whereas honest full node users are more likely to prove that withholding has not occurred. If there is a community related to the plasma chain, then someone can upload the block data and prove that the block hash derived from it is the same as the block hash submitted to the root chain.

Of course there will still be users who don't believe in such proofs, or who want to exit by believing only the information the attacker has provided. Even so, it is not really a big problem. Because we leave the judgment on DA entirely to the individual users. If the user decides that there is a problem and makes an exit through the ERU, no one can stop it.

The second case is when an attacker carries out an attack at a cost. This is also not a major problem. An attacker could only temporarily stop the finalization of blocks in a target child chain, but not the operation itself. Therefore, there will be little inconvenience for users to use the chain.

### References
- [Joseph Poon and Vitalik Buterin, Plasma: Scalable Autonomous Smart Contracts](https://plasma.io/)
- [Plasma EVM](https://ethresear.ch/t/plasma-evm-state-enforceable-construction/3025/11)