Plasma Prime design proposal
m0t0k1ch1.icon BANKEX Foundation が提案した Plasma Prime の設計を把握する
---.icon
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 の検証が単純化する。
---.icon
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.icon 素数とマッピングされているのは 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.
デモ実装では、最大で$ 2^{30}個の異なる segment を持つことができるだろう。
---.icon
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.icon 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 履歴の正当性を確認したい。
https://gyazo.com/43e79849bc6217c70312e2c059bc350c
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.icon < segment (1.75 - 2) は分割して動かせるだろうから、txB は chunk (1 - 2) ともマッチするのでは？
https://gyazo.com/29fdc514af975a898f120f1d4ed5bb75
Note: Deposit transactions are coming from the smart contract, each one located in a separate block, and doesn’t 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 配置になったと仮定する。
https://gyazo.com/95e48e5f00d20b8f2d923ffd15402d90
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.icon chunk (3 - 4) と (5 - 6) を跨いでるのであれば、C じゃなくて D の話じゃないのかしら？
https://gyazo.com/1a8aefc4eb2ee2a823fdecd523f650ed
---.icon
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 に関しては同じである。 https://gyazo.com/405e7deef7920acec87e621157b48f73
Let’s define boolean function$ \mathrm{included}for each aligned slice$ P_iand introduce following auxiliary variables$ \alphaand$ \beta, mapping each aligned slice to two unique prime numbers:
aligned slice$ P_iを引数として真偽値を返す関数$ \mathrm{included}を定義する。また、aligned slice を 2 つの一意な素数にマッピングする補助的な変数$ \alphaと$ \betaを導入する。
m0t0k1ch1.icon ちょっとよくわからないので後回し
$ \alpha(P) = \mathrm{included}(P) \bigwedge_{Q \in \mathrm{Parent}(P)} ! \mathrm{included}(Q)
$ \beta(P) = \exists Q \in \mathrm{child}(P) \cup P : \alpha(Q)
Then determine following functions:
$ \mathrm{inclusionproof}(P) = \exists Q \in \mathrm{parent}(P) \cup P : \alpha(Q) \bigwedge_{R \in \mathrm{parent}(Q) \cup Q} \beta(R)
$ \mathrm{exclusionproof}(P) = ~ ! \beta(P) \bigwedge_{Q \in \mathrm{parent}(P) \cup P} ! \alpha(Q)
It is obviously to check, that
$ \mathrm{inclusionproof}(P) \Rightarrow \mathrm{inclusionproof}(Q), \forall Q \in \mathrm{child}(P)
$ \mathrm{exclusionproof}(P) \Rightarrow ~ !\mathrm{inclusionproof}(Q), \forall Q \in \mathrm{child}(P) \cup 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.
---.icon
Block structure
We propose the following block structure:
以下のような block 構造を提案する。
https://gyazo.com/59269becb8681f89ab996d1c501886ef
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 の場合。
code:structure.txt
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 there’s 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 を構築する。
code:smt.txt
node.length = left.length + right.length
node.hash = Hash(left.length, left.hash, right.length, right.hash)
m0t0k1ch1.icon 各 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.icon Plasma Cashflow の場合は、同じ segment を操作する transaction が 1 block 内に複数存在してもよい？
m0t0k1ch1.icon 下図で言うところの (7-8)
https://gyazo.com/bed9b21e06c2d1a6e075231f39a22411
---.icon
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 することは可能。
---.icon
Exit game
Force inclusion of the transaction
m0t0k1ch1.icon まずは transaction の force inclusion（transaction を強制的に 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.icon force inclusion の話って、なんで今まで出てこなかったんだろう？
m0t0k1ch1.icon 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.icon gas の払い戻しは bond から？
m0t0k1ch1.icon 4 の「特別な block」は、具体的にはどんな block？deposit block と同じようなイメージでよい？
m0t0k1ch1.icon 下図を見るとイメージは湧く
https://gyazo.com/86d21b6230d8bfe9fa3f2272f10c74f0
Standard exit game
1. Somebody starts the exit process from segment$ \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$ \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.icon 4 の「全員」っていうのは、ひっくり返せない challenge に成功した challenger 全員のこと（下図最下部参照）
m0t0k1ch1.icon challenge request については以下
Challange request
m0t0k1ch1.icon 下図の点線の中の話だと思う
1. Anybody present output$ \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$ \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. 誰でも、$ \lbrack x_1, x_2 \rbrackに含まれ、かつ exit 中の transaction よりも古い output を提出することができる
2. 誰でも spend を提出することで challenge できる
spend は上記の標準的な exit game で exit 中の output よりも新しい必要はない
3. 誰でも challenge をより古い output で置き換えることができる
4. 1 の challenger は、transaction から$ \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.icon 1 は「$ \lbrack x_1, x_2 \rbrackの中に部分的な UTXO あるからダメ！」という感じだと思う
m0t0k1ch1.icon 1 の challenger が challenge しなおす（4 を行う）チャンスは 1 回だけってこと？
m0t0k1ch1.icon 5 の challenger が得る bond は、1 の challenger が提出した bond という認識でよい？
m0t0k1ch1.icon 下図を見るとイメージは湧く
https://gyazo.com/2914425e70f907e45c01ba60537c7d5a
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 を用いる。
code:txproof.txt
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 bit：tx netto proof 用
inputs or outputs or max block index の場合は 0
signature の場合は 1
5 bits：inputs と outputs と max block index のための Merkle proof 用
3 bits：signature のための Merkle proof 用
m0t0k1ch1.icon ？？？
m0t0k1ch1.icon leaf のフォーマットの話をしてる？
Exit game methods
code:withdrawal.txt
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);
---.icon
RSA proof of chain validity
m0t0k1ch1.icon ？？？
m0t0k1ch1.icon とりあえず訳してみたものの、何を目的とした何の提案なのか、分からない。。。
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 には含まれない。
Let’s put into each block header special prime number and the proof that this number is included into$ \lbrack A_{n - 1}, A_n \rbrack.
各 block header に特別な素数を含め、この素数が$ \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 には、指数関数的な除算とモジュロ演算がないので。
.svg?sanitize=true){kind=link}