More Viable Plasma における exit の優先度
m0t0k1ch1.icon More Viable Plasma の提案の中から exit の優先度に関する部分をピックアップ
---.icon
Introduction
This proposal replaces output-age priority with something we call “youngest-input” priority. Basically, the exit priority of an output is now the age of its youngest input. We claim that this construction is safe (honest clients cannot have money stolen) as long as clients don’t spend any outputs included after any invalid or witheld transaction.
この提案は、出力の年齢を基準とした優先度を 「最も若い入力」を基準とした優先度 に置き換える。基本的には、出力を exit する際の優先度は、最も若い入力（となっている出力）の年齢を基準とする。クライアントが、不正なトランザクションもしくはオペレータに withhold されているトランザクションによって生まれた出力を使用しない限り、この構成は安全である（誠実なクライアントがお金を盗まれることはない）。
m0t0k1ch1.icon 「若い」というとちょっとややこしいので、「新しい」と思った方が分かりやすい気はする
m0t0k1ch1.icon 最後の 1 文は前提として重要
We show that if there exists an “out of nowhere” input, then any transactions stemming from that input would have an even higher queue number than the “out of nowhere” itself. Therefore, valid outputs will be processed first.
「どこからともなくやってきた」入力が存在する場合、それに由来するトランザクション（の出力）は「どこからともなくやってきた」入力（となっている出力）自体よりも exit の優先度が低くなることを示す。よって、正当な出力の exit が先に処理される。
m0t0k1ch1.icon 証明は以下
---.icon
Safety Proof
TX is the transaction space, of the form (inputs, outputs), where inputs and outputs are sets of integers representing position in the Plasma chain:
TX はトランザクションであり、(inputs, outputs) の形式で表される。inputs と outputs は Plasma チェーンにおける位置を表す整数のセット。
$ TX : ((I_1, I_2, \ldots, I_n), (O_1, O_2, \ldots, O_m))
For all$ t \in TX, we define the “inputs” function$ I(t) = (I_1, I_2, \ldots, I_n)and the “outputs” function$ O(t) = (O_1, O_2, \ldots, O_n)
全ての$ t \in TXについて、「入力」関数$ I(t) = (I_1, I_2, \ldots, I_n)と「出力」関数$ O(t) = (O_1, O_2, \ldots, O_n)を定義する。
Transactions have older inputs than outputs, more formally:
トランザクションの入力は出力よりも古い。より形式的に表現すると以下。
$ \max{(I(t))} < \min{(O(t))}
m0t0k1ch1.icon 入力は他のトランザクションの出力を指すので、実質出力
We also define the mapping$ T_nwhich maps a Plasma chain’s first$ ntransaction indices to its first$ ntransactions.
Plasma チェーン内における$ n個のトランザクションのインデックスと$ n個のトランザクションのマップ$ T_nも定義する。
$ T_n : (0, n \rbrack \rightarrow TX
m0t0k1ch1.icon 文章だと分かりにくいけど、$ T_nは$ \{0 \Rightarrow t_0, 1 \Rightarrow t_1, \ldots, (n - 1) \Rightarrow t_{n-1}\} 的なマップのこと
m0t0k1ch1.icon Plasma チェーンに含まれる全てのトランザクションを時系列で通し番号をつけて並べたようなイメージ
As a shortcut,
以下のような略記を用いる。
$ t_i = T_n(i)
We define the priority number (“lower exits first”, “lower is better”) of a transaction,$ p(t), as:
トランザクションの優先度$ p(t)（「小さい方が優先的に exit できる」「小さい方が優先度が高い」）を以下のように定義する。
$ p(t) = \max{(I(t))}
m0t0k1ch1.icon これが Minimal Viable Plasma からの変更点であり、「最も若い入力」と表現されていたもの
m0t0k1ch1.icon exit したい出力を含むトランザクションがより新しい入力を含んでいるほど、exit の優先度が低くなる
We say that a transaction$ t_kstems from a transaction$ t_j(an output from$ t_jeventually chains into an input of$ t_k) if the following holds:
以下のような場合、「トランザクション$ t_kはトランザクション$ t_jに由来する（$ t_jのある出力を辿っていくと、どこかで$ t_kの入力になっているような状態）」と言うことにする。
$ stems\_from(t_j, t_k) = (O(t_j) \cap I(t_k) \neq \emptyset) \lor (\exists{t} : stems\_from(t_j, t) \land stems\_from(t, t_k))
m0t0k1ch1.icon 一見難しそうな式に見えるが、言ってることは簡単だと思う
m0t0k1ch1.icon $ \capは共通集合、$ \lorは論理和、$ \landは論理積、$ \existsは「条件を満たすようなものが少なくとも 1 つ存在する」
m0t0k1ch1.icon まず、右辺は論理和なので、どちらかの条件が成立すれば正となる
m0t0k1ch1.icon 右辺の前半は$ t_jの出力のどれかが直接$ t_kの入力になっているかどうか
m0t0k1ch1.icon 右辺の後半は再帰的になっているので少し分かりにくいが、結局は$ t_jの出力のどれかが（直接ではなくとも）回り回って$ t_kの入力になっているかどうか（トランザクション鎖として繋がっているかどうか）
A transaction$ t_iwith$ ninputs is considered an “out of nowhere” transaction if any input “points to itself”:
ある入力が「自身を指す」場合、$ n個の入力を持つトランザクション$ t_iは「どこからともなくやってきた」トランザクションとみなす。
$ \exists j \in \lbrack 0, n) : I(t_i)_j = \max{(O(t_{i - 1}))} + j
m0t0k1ch1.icon $ i 番目のトランザクションの$ j番目の入力が、$ i - 1番目のトランザクションの（存在しない）$ \max{(O(t_{i-1})) + j}番目の出力を指すことを「自身を指す」と表現してる模様
m0t0k1ch1.icon 決定論的でシーケンシャルな ID づけができれば、という前提？具体的な手法についてはここで言及するつもりはない？
Let$ t_vbe some transaction and$ t_{nw}be an out of nowhere transaction such that, from our previous definition:
$ t_vを適当なトランザクションとし、$ t_{nw}をどこからともなくやってきたトランザクションとすると、上記の定義から以下が成立する。
$ \max{(I(t_v))} < \max{(I(t_{nw}))}
and therefore by our definition of$ p(t):
よって、優先度は以下のようになる。
$ p(t_v) < p(t_{nw})
So$ p(t_v)will exit before$ p(t_{nw}). We now need to show that for any$ t' that stems from$ t_{nw},$ p(t_v) < p(t')as well. Because$ t'stems from$ t_{nw}, we know that:
よって、$ p(t_v)は$ p(t_{nw})より優先的に exit される。同様に、$ t_{nw}に由来するあらゆる$ t'についても$ p(t_v) < p(t')であることを示す必要がある。$ t'は$ t_{nw}に由来するので、以下が正となる。
$ (O(t_{nw}) \cap I(t') \neq \emptyset) \lor (\exists t : stems\_from(t_{nw}, t') \land stems\_from(t, t'))
m0t0k1ch1.icon 前述の$ t_jと$ t_kの式に$ t_{nw}と$ t'を代入しただけ
If the first is true, then we can show$ p(t_{nw}) < p(t'):
1 つ目の条件が正だった場合、以下のように$ p(t_{nw}) < p(t')を示すことができる。
$ p(t') = \max{(I(t'))} \geq \max{(I(t') \cap O(t_{nw}))} \geq \min{(O(t_{nw}))} > \max{(I(t_{nw}))} = p(t_{nw})
m0t0k1ch1.icon 数式で書くとあれだけど、順番に考えると当然のことを言ってるだけ
Otherwise, there’s a chain of transactions from$ p_{nw}to$ p'for which the first is true, and therefore the inequality holds by transitivity.
そうでなければ、2 つ目の条件が正となるような$ p_{nw}から$ p'へのトランザクション鎖が存在するため、不等式は推移的に成立する。
m0t0k1ch1.icon the first って書いてあるけど、the second の間違い？（the second として訳した）
m0t0k1ch1.icon ざっくり言うと、$ t_{nw}の出力のどれかが直接$ t'の入力になっているパターン（1 つ目の条件が成立するパターン）でも大丈夫なら、間接的に繋がってるパターン（2 つ目の条件が成立するパターン）も必然的に大丈夫だよねということ