Plasma Prime design proposal

m0t0k1ch1 BANKEX Foundation Plasma Prime
m0t0k1ch1 see also Plasma Cashflow

---

Abstract

> Below we are going to describe Plasma design based on plasma cashflow improved by RSA accumulators and range chunking. Range chunking simplifies block verification for block observer by compressing history.

RSA accumulator range chunking Plasma Cashflow Plasma range chunking block

---

Segments

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

Plasma Cashflow UTXO UTXO segment segment Plasma

> Each segment is mapped to a prime number generated by the prime hash function, usage of that prime number will be shown later.

segment 使

m0t0k1ch1 segment

> Due to the limitation of prime numbers that we generate with reasonable efforts plasma has a finite set of segments that can belong to different owners during the plasma lifetime.

Plasma segment

> We can say that we may have up to 2^30 different segments in the demo implementation.

2302^{30} segment

---

Segments chunking

> Suppose there exists a segment X . During the time A some transaction that affects X was published, e.g. split or merge transactions.

segment X A X transaction split merge transaction

m0t0k1ch1 segment split merge

> During the time B transactions that affect segments different from A was published.

B A segment transaction

> At the time moment C transaction that affects X , was published, at that moment we want to check the history of that transaction is valid.

C X transaction transaction


> To do that we need to generate proof that covers only transactions related only to range X , and not the whole transaction history of plasma.

X transaction proof Plasma transaction

Examples

> Lets split plasma segments space into the four chunks.

segment 4 chunk

> The image below illustrates scenario when two sequential deposits transactions (txA, txB) creates two segments:

2 deposit transaction txA txB 2 segment

>txA creates the segment (0 - 1.75) that matches to chunk (1 - 2)
>txB creates the segment (1.75 - 5) that matches to chunks (3 - 4) and (5 - 6)

txA segment (0 - 1.75) chunk (1 - 2)
txB segment (1.75 - 5) chunk (3 - 4) (5 - 6)

m0t0k1ch1 < segment (1.75 - 2) txB chunk (1 - 2)


> Note: Deposit transactions are coming from the smart contract, each one located in a separate block, and doesnt have reference to any previous block

deposit transaction block block

> Suppose after N blocks we got following layout of segments inside plasma:

N block Plasma segment


> To verify that C exit is valid, block observer only needs to check the history of the segment that matches to chunks (3 - 4) and (5 - 6). Proof of inclusion of range C to mentioned chunks will include transactions that affect the same two chunks.

C exit chunk (3 - 4) (5 - 6) segment C chunk proof chunk transaction

m0t0k1ch1 chunk (3 - 4) (5 - 6) C D


---

RSA proof of segment inclusion and non-inclusion

> The similar prooving schema was proposed by @vbuterin here. We proposed schema with shorter proofs of inclusion (because we need to proof only inclusion of several numbers) and same proof of non-inclusion.

vbuterin proof of inclusion inclusion proof of non-inclusion


> Lets define boolean functionincluded\mathrm{included}for each aligned slicePiP_iand introduce following auxiliary variablesα\alphaandβ\beta, mapping each aligned slice to two unique prime numbers:

aligned slicePiP_iincluded\mathrm{included}aligned slice 2 α\alphaβ\beta

m0t0k1ch1

α(P)=included(P)QParent(P)!included(Q)\alpha(P) = \mathrm{included}(P) \bigwedge_{Q \in \mathrm{Parent}(P)} ! \mathrm{included}(Q)
β(P)=Qchild(P)P:α(Q)\beta(P) = \exists Q \in \mathrm{child}(P) \cup P : \alpha(Q)

> Then determine following functions:

inclusionproof(P)=Qparent(P)P:α(Q)Rparent(Q)Qβ(R)\mathrm{inclusionproof}(P) = \exists Q \in \mathrm{parent}(P) \cup P : \alpha(Q) \bigwedge_{R \in \mathrm{parent}(Q) \cup Q} \beta(R)
exclusionproof(P)= !β(P)Qparent(P)P!α(Q)\mathrm{exclusionproof}(P) = ~ ! \beta(P) \bigwedge_{Q \in \mathrm{parent}(P) \cup P} ! \alpha(Q)

> It is obviously to check, that

inclusionproof(P)inclusionproof(Q),Qchild(P)\mathrm{inclusionproof}(P) \Rightarrow \mathrm{inclusionproof}(Q), \forall Q \in \mathrm{child}(P)
exclusionproof(P) !inclusionproof(Q),Qchild(P)P\mathrm{exclusionproof}(P) \Rightarrow ~ !\mathrm{inclusionproof}(Q), \forall Q \in \mathrm{child}(P) \cup P
inclusionproof(P) !exclusionproof(Q),Qchild(P)P\mathrm{inclusionproof}(P) \Rightarrow ~ ! \mathrm{exclusionproof}(Q), \forall Q \in \mathrm{child}(P) \cup P

> In plasma we use the following properties to get only necessary parts of plasma history.

---

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.

tx netto signature transaction transaction 1 2 signature 2 signature atomic swap split merge

struct Block {
BlockHeader header,
Transactions[] transactions
}
struct BlockHeader {
SumMerkleRoot sumMerkleRoot,
uint2048, RSAAccumulator,
RSAInclusionProof RSAChainProof
}
struct RSAInclusionProof {
uint2048 b,
uint256 r
}
struct Transaction {
TransactionContent content,
Signatures[] signatures
}
struct TransactionContent {
Input[] inputs,
Output[] outputs,
uint64 maxBlockIndex
}
struct Input
{
uint160 owner,
uint64 blockIndex,
uint32 txIndex,
uint8 outputIndex,
Segment amount
}
struct Output
{
uint160 owner,
Segment amount
}
struct Segment
{
uint256 begin
uint256 end
}

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

segment 1 transaction txIndex

SumMerkleRoot

> We use SumMerkleTree to quickly verify that theres no overlap between different transaction segments in the block and efficient generation of inclusion proof.

sum Merkle tree 使
block segment
inclusion proof

> We build the tree in the following way:

tree

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

m0t0k1ch1 node length hash

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

tree leaf transaction hash null hash

> Length of the leaf is the length of the corresponding segment in the transaction.

leaf length transaction segment length

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

block transaction 2 segment tree 2 leaf

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

leaf 1 transaction hash zero hash

m0t0k1ch1 Plasma Cashflow
m0t0k1ch1 Plasma Cashflow segment transaction 1 block
m0t0k1ch1 (7-8)


---

Deposits, withdrawals, and fragmentation

> Segment based model may have a problem of excessive fragmentation since withdrawing leave a hole between segments. To solve that plasma operator we can:

segment withdrawal leaf hole fragmentation Plasma operator

>Make deposits to the holes
>Take extra fee for the withdrawal that makes significant fragmentation

deposit hole
fragmentation withdrawal

> Note: Exit possible with part of UTXO (one of the segments)

UTXO segment 1 exit

---

Exit game

Force inclusion of the transaction

m0t0k1ch1 transaction force inclusiontransaction block

> This idea is proposed in Plasma Cashflow spec. A transaction may be force included into a block by following game:

Plasma Cashflow transaction game block

m0t0k1ch1 force inclusion
m0t0k1ch1 atomic swap

>1. Somebody can present the unsigned transaction (corresponding TransactionContent structure) and the bond
>2. Anybody can commit signatures (with auto refund the gas)
>3. Anybody can challenge the transaction by presenting spend of inputs (including withdrawals) or non-inclusion proof for inputs
>4. If the transaction is challenged, the challenger takes the bond. Else if all signatures collected, the transaction is included into a special block with the same exit priority as the oldest input of the transaction. In both cases (signatures collected or not) the transaction is considered to be removed from all other blocks

1. TransactionContent transaction bond
2. signature gas
3. withdrawal inputs spend inputs non-inclusion proof transaction challenge
4. transaction challenge challenger bond challenge signature transaction input exit priority block
signature transaction block

m0t0k1ch1 gas bond
m0t0k1ch1 4 block blockdeposit block
m0t0k1ch1


Standard exit game

>1. Somebody starts the exit process from segment[x1,x2]\lbrack x_1, x_2 \rbrackand attach his output to this process and set the bond.
>2. (1) can be challenged by non-inclusion proof or spend (including withdrawals) immediately and get the bond
>3. Anybody can start a special challenge request.
>4. If the game is challenged by challenge requests, the bond is split to all

1. segment[x1,x2]\lbrack x_1, x_2 \rbrack exit bond
2. non-inclusion proof withdrawal spend challenge bond
3. challenge request
4. game challenge request challenge bond

m0t0k1ch1 4 challenge challenger
m0t0k1ch1 challenge request

Challange request

m0t0k1ch1

>1. Anybody present output[x1,x2]\in \lbrack x_1, x_2 \rbrackolder than the output of tx exiting
>2. Anybody can challenge him presenting the spend. The spend must not be newer than output exiting in standard exit game.
>3. Anybody can replace the challenge presented an older challenge
>4. Challenger (1) can continue challenge game selecting utxo[x1,x2]\in \lbrack x_1, x_2 \rbrackfrom tx in remained challenge
>5. Same as (2) or (3)
>6. The first challenger in (2-3) gets the gas refund. The second challenger in (5) get the bond. Or challenge request is considered to be completed.

1. [x1,x2]\lbrack x_1, x_2 \rbrack exit transaction output
2. spend challenge
spend exit game exit output
3. challenge output
4. 1 challenger transaction [x1,x2]\lbrack x_1, x_2 \rbrack output challenge game
5. 2 3
6. 2 3 challenger gas 5 challenger bond
5 challenge challenge request

m0t0k1ch1 1 [x1,x2]\lbrack x_1, x_2 \rbrack UTXO
m0t0k1ch1 1 challenger challenge 4 1
m0t0k1ch1 5 challenger bond 1 challenger bond
m0t0k1ch1




Merkle proof structure

> We use two kinds of sum Merkle proof:

2 sum Merkle proof

>Standard sum Merkle proof to proof mapping from segment to transaction
>Full sum Merkle proof to prove inclusion of all segments corresponding the transaction

segment transaction sum Merkle proof
transaction segment inclusion sum Merkle proof

> We use standard Merkle proof inside the transaction:

transaction Merkle proof

1 bit for tx netto proof (must be zero for outputs, inputs, max_blockid and must be one for signatures)
5 bits for Merkle proof for outputs, inputs, and maxBlockId
3 bits for Merkle proof for signatures.

1 bittx netto proof
inputs or outputs or max block index 0
signature 1
5 bitsinputs outputs max block index Merkle proof
3 bitssignature Merkle proof

m0t0k1ch1
m0t0k1ch1 leaf

Exit game methods

function withdrawal(Input point,
RSAInclusionProof proof) external payable returns (bool);
function withdrawalChallangeSpend(Input point,
Transaction tx, FullSumMerkleProof txProof, uint8 spendIndex,
RSAInclusionProof spendInclusionProof) external returns (bool);
function withdrawalChallangeBlock(
Input point, SumMerkleProof txProof,MerkleProof inputProof,
uint64 maxBlockIndex, MerkleProof maxBlockIndexProof
) external returns (bool);

---

RSA proof of chain validity

m0t0k1ch1
m0t0k1ch1

> Plasma owner can potentially fork RSA accumulator chain. Then the spend may be included into any subsegment of blocks, but not included into the segment to which the subsegment belongs.

Plasma owner RSA accumulator spend block subsegment subsegment segment

> Lets put into each block header special prime number and the proof that this number is included into[An1,An]\lbrack A_{n - 1}, A_n \rbrack.

block header [An1,An]\lbrack A_{n - 1}, A_n \rbrack

> If the operator forks the chain, he does not present the proof, because we have no division and modulo operations in exponential rate in RSA.

operator proof RSA