Plasma snapp - fully verified plasma chain

Layer 2 Plasma
29

Version 0.3
This new version has the big advantage that the receiver does not need to be online at all. Still, he epoch version might be better for more sophisticated protocols than just transfers, as eg. exchanges.
In this new version, the exit priority is no longer based on the last touch of the owners leave. It is calculated based on the height of the plasma chain block, from which a user wants to withdraw.

Plasma snapp:

TL;DR

The following specification outlines a new plasma version which utilizes snarks to prove its integrity and validity. Via an interlinking between exit requests and deposits with the correctness proof of a block - the snark -, we are able to specify an implementation without any need for exit challenge games and confirmation signatures. Unfortunately, the concept of exit queues is still needed.

Removing the exit games and confirmation signatures allow us to remove much of the complexity of plasma, which is currently hindering the implementation of more sophisticated protocols beyond simple token-transfers. This proposed version will facilitate to integrate more protocols into plasma by making the snarks itself handling these protocol advancements.

Introduction:

Over the last half a year, there has been made tremendous advancements regarding fully verifiable plasma chains. New signature mechanism and hashing mechanism were found, helping to reduce proving times significantly.

These advancements enable the following with reasonable timings:

  • storing the complete state of a plasma chain encoded as a StateRootHash on ethereum

  • this StateRootHash can be updated by a central operator by providing a snark proving a valid state transition

  • A valid state transition is proven within the snark by opening one or several leaves of the merkle tree describing the current state, checking the user’s signatures, doing predefined operations, updating the leaf and finally recalculate the stateRootHash.

How this can be in done in detail, you can find over here: [https://github.com/barryWhiteHat/roll_up

](https://github.com/barryWhiteHat/roll_up)

However, snarks do not solve the problems associated with data unavailability. Also, the snarks need to be aware of any incoming deposit request to the plasma chain and outgoing withdrawal requests. This post will describe a solution for these two remaining issues.

Proving valid state transactions

In this model, the state is described by leaves of the StateMerkleTree. Each leaf is a list of a

[public key, amount of token, blockheight of last transfer].

The plasma contract is aware of the current state, as we store it as the variable StateRootHash in the contract.
State transitions are tracked on the smart contract via the list of StateRootHashes:
StateRootHash_1 -> StateRootHash_2 -> … -> StateRootHash_n.
The plasma contracts also stores the verification keys of the snarks of 3 different programs: P_transfer, P_deposit, and P_exits for 3 different kinds of state changes. These verification keys allow the plasma contract verifying that the state changes for a new block are actually valid ones.

Let us call the program checking the correctness of a state transition based on transfer P_transfer:

P_transfer(StateRootHash_i, current block, [witness transactions data]) = (StateRootHash_(i+1))

A transaction is a value transfer from one leaf to another leaf. P_transfers checks the following:

  • Leaf of sending account exists

  • Leaf of sending account has the needed balance for transfer

  • The transfer transaction is signed by the private key associated with the public key stored in the sending leaf and the transaction is intended for the current block height

  • Subtracts balance from sending leaf, updates the epoch of last transfer, updates the StateRootHash

  • Leaf of receiving account exists

  • Updates balance of receiving leave

The witness transaction data will be used by the snark proof, but they will never touch the rootchain. It is only needed to create once the witness of the snark.

This is pretty straightforward. But how do we make the plasma chain aware of deposits and withdrawal? We think the following trick will do the job:

The information of several deposits, which are sent to the plasma contract, can be hashed together to a depositHash by the plasma contract. By requiring the snark proof to take the depositHash as a public variable, we can enforce the snark proof to process all deposits.

The program P_deposit checking the correctness of deposits would look like this

P_deposit(StateRootHash_i, DepositHash_i, [witness deposit data]) = (StateRootHash_(i+1))

A deposit is a value transfer into an empty leaf. Whether a leaf is empty, we will store on the ethereum mainchain in a mapping: leafOccupation. P_deposit does the following:

  • Insert public key and deposit amount into the leaf

  • Updates the StateRootHash

The same can be done for exits: All exit requests can be collected by the plasma contract. The user submits the exit request to the plasma contract by submitting his address and the height at which he would like to withdraw. This height is in most cases the first unavailable block. The operator is required to react upon each exit request by submitting the withdraw-able balance of the requested height from the plasma chain. Then these information [address, balance, StateRootHash of block of height for request] are hashed together in an exitRequestHash and by making it a public input the snark, we can enforce the snark to process this exit request.

P_exit(StateRootHash_i, ExitRequestHash_i,[witness exit data]) = (StateRootHash_(i+1))

A withdrawal tries to exit all balance out of a leaf. The snark checks the following:

  • Leaf has not sent out a transaction in the last 40k transfer blocks (equals 7 days) or withdrawal balance is 0
  • Leaf stored exactly the predefined balance at the specific height or withdrawal balance is 0.
  • Either the leaf in the latest state does not have a higher block-height of last transfer as the block-height, from which we are currently withdrawing or withdrawal balance must be 0.
  • Deletes the complete leaf, updates StateRootHash

Unfortunately, exits with a fraction of the balance are not supported by this protocol.

Note that the operator needs to set the withdrawal balance, as only he knows for sure the current balance. Still, the snark enforces the operator to set the correct balance, as otherwise he will not be able to find a proof. If someone makes an exit request, which is not valid, the operator will set the balance in the exit to 0. Exit request against non-occupied leaves is prevented by the plasma smart contract.

These three different programs allow the operator to append the plasma chain with 3 different block types (deposits, transfers and exits) by sending over the respective snark prover key. The plasma smart contract would enforce that registered pending exits would be processes at first, forcing the operator to submit exit blocks, before deposit or blocking transfer blocks. Likewise, if there are deposits pending for several blocks, then the plasma contract would force the plasma operator to include deposit blocks before any transfer blocks are accepted. Only if there are no pending deposits or withdrawals, then the plasma chain allows appending transfers blocks.

Roll back of the tip of unavailable chains

This above construction interlinks very well deposits and exits with the snark proofs. Unfortunately, it can not prevent the data unavailability case. It could always happen that the operator would publish a StateRootHash and nobody knows the content of this new state. Using priority queues for exits and an unwinding mechanism, we can solve the problem:

If the chain operator stops publishing new valid blocks for 3 days, then the plasma root chain contract would allow swapping the operators. Then anyone else can extend the plasma snapp chain provided that the new operator hands in valid snark for his new blocks.

If no one can build on the tip of the plasma chain, then the last block of the plasma chain will be removed and we wait for people building on the second-highest block. We will continue this removal process of the plasma chain tip until it is extended again by another operator. If clients are storing all the data of the plasma chain, then they could always become the operator themselves in such a situation. Thus, if they do not agree with the reversal of a block of the chain tip, they need to become the operator. This is a fair mechanism, as everyone can stop the rollback of the history.

Payment receivers should only acknowledge their payment as accepted, once they have the complete new state of the plasma chain. Then they could theoretically always prevent the rollback of their received transaction by becoming the plasma operator themselves.

Becoming a plasma operator is a heavy task, but on the other side, we could also incentivize this heavily by slashing the original operator and rewarding the new operator with these slashed funds: During the plasma chain creation, the operator has to make a deposit of x ether. If the plasma chain was stopped and the operator swapped, then the new operator would receive a fraction of this ether per submitted valid block. This ensures that the plasma chain is continued for quite sometime after the original operator was switched and everyone has the chance to leave the chain.

But there is one hook, rolling back transactions of unavailable blocks might be fine, but unwinding withdrawals is not possible. However, there is a workaround: We require that

  • Exits are processed only 40k transfer-blocks (7 days) after max( block-height of last transfer in leaf, block-height of plasma chain block, from which the balance should be read).
  • Exit requests are bundled per block: Only if all withdrawal requests from a certain block-height are processed, then the plasma smart contract will allow the withdrawal of the actual funds.
  • In order to have full security, users have to send an exit request for their funds at least 40k blocks after the data unavailability.

If a users wants to withdraw, he sends a request to the plasma root-contract with the blockheight n: the blockheight of the plasma chain from which his balance should be withdrawn. In the unhappy case, this would be the first unavailable block. The plasma contract then requires the operator to process this exit before the operator could hand in the transfer block of height max( block-height of last transfer, block-height of actual withdrawal request).+40k +1.

Using this delayed mechanism, users funds are safe:

Imagine the block n is the first unavailable block.

  1. If the operator keeps on building blocks but stops building new blocks before the block n+40k is finished, then all exits processed must be “old” accounts, which either were not touched since the data unavailability or the users are not aware of the . Even when blocks are unrolled until n, we require the new chain with the new blocks to include the same exits, but without paying for the exits again. Thus no funds are lost.

  2. If the operator keeps on building blocks and goes beyond the n+40 k, then every user should have already registered their exit and the plasma contract would have made sure that it would have been withdrawn. The operator could then potentially revert his transaction without reverting the withdrawal, but since all users anyways have already withdrawn their funds, nothing would be left to steal.

Note: In order to make this mechanism work, everyone needs to know when their transaction might have been included into the plasma chain. Especially, the scenario needs to be prevented where the operator produces unavailable blocks and includes in these blocks old transactions of somebody and thereby prevents this person to withdraw. Hence, every transaction submitted by a customer should be valid only for a specific block. This will be checked by the snark.

Note2: This specification has the nice property that we can use any hash function for the state Merkle tree within the snarks, as these hash functions do not need to be executed in the evm at all. This is a huge benefit. Only the deposits and exits need to be done with keccak, as here the evm will need to execute them as well.