Data Availability problem in implementing Plasma design

Part 1 : UTXO model and Data Availability problem

Before starting off

A lot of research on solving scalability problem is published day by day. If I take my eyes off that for a few days, should I feel like being left behind… and maybe try following up them my butt off.

It’s not only my problem these days, I guess… How about you guys?

So I decided to introduce scalability solutions for ones like me. In the middle of so many research, I have made up my mind to pick up Plasma and Data Availability problem. Actually we are developing Plasma solution named as Plasma EVM.

Articles in this series:

1. Definition of Data availability and Solutions in UTXO model
2. General Computation Model and Data availability
3. Solutions in General Computation Model

• General Computation Model : It has states of each accounts, like Ethereum, which can compute and store with the virtual machine like EVM.

What the heck is Data Availability?

Data Availability problem is the problem that can’t make proof based on transaction data that is needed to validate.

There is two cases on Data Availability :

• Dishonest Full Node: A full node propagate invalid block or transaction to light node, so the light node can’t validate.
• Block Withholding: Miner makes a block but not propagate the block to nodes.(full node or light node)

All of two case have to be considered in implementing Plasma but in the case of Dishonest Full Node problem, it should be considered after making light nodes and allow light nodes to verify block in Plasma chain. On the other hand, Block Withholding should be considered when implementing exit process that is main feature of Plasma design.

So we have to consider all of them, but the latter is needed to handle in advance and should consider the former.

Only Proof of Concept(POC) is suggested these days, so Block Withholding problem is important for engineers who actually implement Plasma like us.

So it would be worth that we discuss Block withholding problem in this article.

Start off understanding Data availability — Fraud proof

In order to understand Data Availability problem, you need to first understand the concept of fraud proof. Assume that an attacker makes a block that is invalid in some way(e.g. the post-state root is wrong, or some transaction is invalid or mal-formatted). After that, it is possible for user to make fraud proof on the invalid block.

The process of creating fraud proof, that is, reconstructing state based on the transaction data which is needed to validate and then, computing merkle root of the state. In the process of that, see if there is some error in the processing; if there is, that block is invalid.

We can make the exit game with this fraud proof in Plasma.

Figure 1. exit game with fraud proof

(1) User A request exit of some invalid transaction putting down a deposit.

(2) User B who notice that the exit request of User A is invalid create the fraud proof and then challenge on that exit.

(3) It is proved that the fraud proof is valid in Main Chain. So the exit request of User A is rejected and then slash User A’s deposit.

(4) User B who succeed in challenge is rewarded with some portion of the User A’s deposit.

or another case,

(1) User A request exit of valid transaction also putting down a deposit.

(2) User B make invalid fraud proof challenging on that exit. Also B put down a deposit.

(3) It turns out the fraud proof is invalid in Main Chain and then User A’s exit request is accepted in Main Chain. and send back User A’s deposit.

(4) Slash the deposit of User B who submit the fraud proof which is invalid.

Data availability in Plasma

This way is simple and perfect. It seems that anyone that has valid transaction data can exit impartiality while others can’t exit with invalid transaction data. But this exit game has serious problem.

What if miner(or operator) make a block that contains invalid transaction and submit to Main Chain but not propagate Users in Plasma Chain? If then, users are not able to prove invalid transaction data because they can’t make the fraud proof on that.

Here is a scenario.

Figure 2. operator withhold a block from users

(1) User A send 10PETH to User S

(2) Operator O record the invalid transaction in block(e.g. the transaction of A sending 10PETH to O) and submit to Main Chain but not propagate to A and S

(3) O try to exit with the invalid transaction

(4) S notice that there is block withholding but can’t exit with transaction (1). because S didn’t get the block.

(5) A also notice that so try to exit with the transaction prior to transaction(1). but there is a chance that O challenge on A.( O can make the fraud proof based on the invalid transaction from (2) )

As see the above, Data Availability is problematic so that validators can not the fraud proof.

They can’t notice that operator make some invalid transaction and can’t create the fraud proof against invalid transaction because operator do not propagate the block to validator.

Operator also can simply interrupt the exit from users not propagating a block. If so, Is there any Solutions to find out the malfeasance of an operator? It is very hard to resolve.

Full nodes in Plasma chain can bring up that Operator is block withholding. But that is only guess not proof. So operator can say that he published the block while he actually did not publish.

Validators can’t make a decision exactly because of the network bandwidth. A block is reached to validators at different times in asynchronous environment. see as follows,

(1) Operator O make a block containing an invalid transaction and withhold.

(2) Full node user S doubt if it is block withholding. so bring it up.

(3) Then, Operator O remove the block and make an invalid block submitting to main chain. and then, publish to the child chain.

So full node user or general user can’t notice exactly that operator is actually withholding block.

Solutions for Data availability in UTXO model

From now on, there is a lot of researches to resolve Data availability problem.

• Plasma MVP- conformation sig

They mitigate the problem by prepare / commit

For example,

Figure 3. Plasma MVP — Conformation Sig

(1) User A send 10PETH to User S (TX_1) — prepare phase

(2) Operator O submit block B_1 containing TX_1

(3) A check out if it contains TX_1 in B_1 by the root hash and then, sign TX_1 for conformation — commit phase

(4) S send 5PETH to A(TX_2)

(5) At this time, O submit block B_2 containing forged TX_2 that send PETH to O. and withhold the block.

(6) O start exit but it is impossible. because S has not signed TX_2 for conformation yet.

(7) S notice the block withholding and can start the exit with TX_1 and conformation signature.

But this solution is limited in UTXO model and is cumbersome to sign it twice when sending transaction.

David Knott plasma map without confirmation

Instead of signing twice, suggest two rules for exit game.

1. A transaction must be included within two blocks of the time it was created.
2. A transaction’s input must be created at least 3 child chains blocks before.

The first rule prevents the operator from withholding a transaction from a block for an infinite time. The second rule limits the exit game to at most 3 steps: the exit request, the challenge, and rechallenge request.

A possible example like that,

Figure 4. no confirmation scenario

t+0: (1) User A send 10 PETH to User S (TX_1)

t+1: (2) Operator O withhold TX_1

t+2: (3) Operator O make an invalid block and submit the hash to Main Chain. but not publish it.

t+2: (4) S notice that block B is withheld but can’t exit because lack of TX_1 data.

t+2: (5) A request exit based on the previous transaction.

t+3: (6) O make a block containing TX_1 and submit to Main Chain.

t+4: (7) O challenge the exit request from A.

t+4: (8) S notice TX_1 so S rechallenge O’s Challenge.

But this model is based on UTXO. and like above, at most have to compute three times a merkle root.

UTXO Model, General Computation Model, Data Availability

These solutions efficiently mitigate Data Availability problem in UTXO model. but UTXO model has a problem that is hard to make dapp(Decentralized application), like on Ethereum.

It’s quite reasonable to describe that it is similar to make a smart contract with script language of bitcoin.

If Child Chain has same data structure as Main chain(i.e. Ethereum), it is able to make a smart contract with high level programming language as Solidity or Vyper. Also, it is possible to use dev tools used in Ethereum.

Nevertheless, what makes to use UTXO model instead of General Computation model? The problem is that it is difficult to process the exit as does in UTXO model.(Why Smart contracts are NOT feasible on Plasma)

So It needs to create a new exit process in General Computation model.

In next series, I’m going to explain why it is important implementing General Computation model. Also, why it is hard to implement solving Data Availability problem, and how we solve Data Availability problem.

Reference

Vitalik — A-note-on-data-availability-and-erasure-coding

ethresear.ch — Why Smart contracts are NOT feasible on Plasma

PARSEC — PLASMA FROM MVP TO GENERAL COMPUTATION

David Knott — Plasma MVP without Confirmations