Plasma Prime design proposal

Layer 2 Plasma
9

Plasma cashflow with S[NT]ARK exclusion proofs

Here is Plasma design proposal update from BANKEX Foundation team.

Abstract

Plasma cashflow brings the idea of plasma slice space, the critical problem of that design is that the size of exclusion proofs is growing excessively during the plasma lifetime.

In that document, we describe plasma design that uses S[NT]ARK based exclusion proof to bypass the computation complexity of RSA accumulator.

Slices

Similar to plasma cashflow this proposal is based on the UTXO model where each unspent output defines ownership of a specific slice. Length of the slice is equal to a value of the asset that was deposit to plasma.

Block structure

We propose the following block structure:

block

Notes: TX Netto is actually transaction content without signatures. A transaction can include one or two signatures, two - in case of atomic swap and one in all case of a split and merge.

struct Block {
    BlockHeader header,
    Transactions[] transactions
}

struct BlockHeader {
    SumMerkleRoot sumMerkleRoot
}

struct Transaction {
    TransactionContent content,
    Signatures[] signatures
}

struct TransactionContent {
    Input[] inputs,
    Output[] outputs,
    uint64 maxBlockIndex
}

struct Input
{
    uint160 owner, 
    uint64 blockIndex, 
    uint32 txIndex, 
    uint8 outputIndex, 
    Slice amount
}

struct Output
{
    uint160 owner, 
    Slice amount
}

struct Slice
{
    uint256 begin 
    uint256 end
}

One transaction may have multiple txIndex values because it can be fragmented to different slices.

SumMerkleRoot

We use SumMerkleTree to quickly verify that there’s no overlap between different transaction slices in the block and efficient generation of inclusion proof.

We build the tree in the following way:

node.length = left.length + right.lengh
node.hash = Hash(left.length, left.hash, right.lengh, right.hash)

The leaf of this tree corresponds to the transaction hash of the transaction or null hash.

Length of the leaf is the length of the corresponding slice in the transaction.

Note: Each transaction in the block can produce more than one leaf of this tree in case transaction contains more than one slice inside.

Similar structure is proposed here. Our approach differs because we store only one tx hash or zero hash inside each leaf.

Short exclusion proof

Read more at the link here.

Merkle proof

We are planning to use Pedersen hash function. The computation of Merkle proofs onchain is expensive by the gas. That’s why we put all proofs into the zk-SNARK. SNARK computation is expensive too, but we can use the Truebit protocol to make it cheaper.

Deposits, withdrawals, and fragmentation

The slice-based model may have a problem of excessive fragmentation since withdrawing leave a void between slices. To solve that plasma operator we can:

  • Make deposits to the voids
  • Split deposits to the several voids
  • Take extra fee for the withdrawal that makes significant fragmentation

Note: Exit is possible with part of UTXO (one of the slices in the transaction)

Exit game

Priority increasing game (it is like @kfichter’s special exit). Not multisig case.

  1. Alice publishes the transaction on mainnet plasma contract.
  2. Bob can challenge the submission by presenting spend of inputs of the transaction with another hash
  3. If the submission is unchallenged, we consider the transaction included into the block of youngest input of the transaction

Priority increasing game. Multisig case.

  1. Alice publishes the unsigned transaction on mainnet plasma contract. Alice must be an owner of any of input or outputs of the transaction. If Alice is an owner of any of inputs, Alice must present the signature.
  2. Bob can present remain signatures.
  3. Anybody can challenge the submission by presenting spend of inputs of the transaction with another hash
  4. If the submission is unchallenged, we consider the transaction included into the block of youngest input of the transaction. If the submission is unchallenged, but the signatures are not collected, we consider all transactions with the same hash from the plasma blockchain to be removed.

Exit game

  1. Exiter publish the exit output
  2. Anybody can challenge the output for spend or non-inclusion
  3. Anybody can present an output with an earlier priority. If this output is unchallenged by spend, exit (1) is challenged.

Bibliography

Plasma call #16
@karl, Plasma cash spec
Plasma cashflow spec
@kfichter, More Viable Plasma
@snjax, Short S[NT]ARK exclusion proofs for Plasma