Plasma XT における checkpointing（原案）

---.icon

Introduction

Checkpoints are one solution to the above problem. If we can properly construct regular intervals in which the state of a coin is considered “finalized”, then it’s possible to reduce the total proof size significantly (to some relatively small constant). Generally, this is accomplished by having the operator attest to the current state and allow for a challenge period in which this state may be contested. If no one shows that the state is invalid, then the checkpoint is considered finalized.

checkpoint は上記の問題の 1 つの解決策である。コインの状態が「ファイナライズされた」とみなせるような一定のインターバルを適切に設けることができる場合、proof の総サイズをかなり（比較的小さい一定の値まで）削減することが可能である。大まかに言うと、オペレータに現在の状態を証明させ、この状態に関する challenge 期間を設けることによって、上記が達成される。状態が不正であることを誰も示せなかった場合、checkpoint はファイナライズされたとみなされる。

---.icon

Naive Checkpoints

Checkpoints are really hard to get right! Let’s look at the following (flawed) checkpoint construction to illustrate some of the challenges:

checkpoint は本当に難しい！いくつかの課題を説明するため、以下の（欠陥のある）checkpoint 構成を見てみよう。

Every N blocks, the operator publishes a Merkle state root. This root is derived from a Merkle tree in which each leaf node represents the current valid owner of each coin in the tree. So if user A owns coin 0, then the operator will place A's address at the 0th (first) leaf in the tree.

N ブロック毎にオペレータは Merkle state root を公開する。この root は Merkle tree に由来しており、各 leaf ノードは tree 内の各コインの現在の正当な保有者を表す。よって、ユーザー A がコイン 0 を保有していた場合、オペレータは 0 番目（最初）の leaf に A のアドレスを配置する。

The operator places a bond on this action. Any user can prove that the state is invalid (and therefore claim the operator’s bond) by showing that the operator has lied about the owner of a certain coin. If no successful challenges take place after some amount of time, then the checkpoint is considered finalized.

オペレータはこの行為についての担保を提出する。オペレータがあるコインの保有者について嘘をついていることを示すことで、ユーザーは誰でもその状態が不正であることを証明することができる（そして、オペレータの担保を獲得する）。一定時間が経過しても challenge が成功しなかった場合、checkpoint はファイナライズされたとみなされる。

Why is this design flawed? It comes down to the (really hard) problem of data availability. If the operator publishes a state root but does not publish the tree itself, then it’s impossible for anyone to challenge the checkpoint. You can’t prove that something is invalid if you can’t even validate it in the first place.

なぜこのデザインに欠陥があるのか？その理由は、（本当に難しい）データの availability に関する問題に帰着する。オペレータが state root を公開したが tree 自体を公開しなかった場合、誰も checkpoint に challenge することはできない。検証さえできないのであれば、不正を証明することはできない。

Because we don’t know if the checkpoint is valid or not, we have to assume that the operator is trying to steal some money. Once the checkpoint finalizes, the checkpoint state becomes the “true” state. The only solution is for all of the coin owners to exit before the checkpoint finalizes. Even worse, since we can’t prove the operator did something bad, we can’t punish the operator. We never want to force a user to act within some time-frame if the user won’t receive some sort of bounty for doing so.

checkpoint が正当かどうかわからない場合、オペレータがお金を盗もうとしていると仮定する必要がある。一度 checkpoint がファイナライズされると、checkpoint の状態は「真」となる。唯一の解決策は、コインの保有者全員が checkpoint がファイナライズされる前に exit することである。さらによくないのは、オペレータが何か悪事を働いたことが証明できなければ、オペレータを処罰するとができないということ。ユーザーが対価として何らかの報酬金を受け取ることができない場合、時間制限つきでユーザーを強制的に行動させることは望ましくない。

---.icon

Fancy Checkpoints

It turns out we can (sort of) solve the data availability problem by taking advantage of a few interesting observations. Let’s go back to first principles - in the above example, no one can challenge the operator because no one knows if the data is valid or not. So, what if we could design a system so that someone will know if the operator is trying to cheat?

いくつかの興味深い見解をうまく活用することで、（ある種の）データの availability 問題は解決できる。最初の原則に戻ろう。上記の例では、データが正当かどうかわからない場合、誰もオペレータに challenge することができない、と言っている。ここで、オペレータが不正を行おうとしているかを知ることができるシステムを設計できるとしたらどうだろうか？

Well, we can! We just need to rely on some signatures. The basic idea here is that each user that wants to have their coin checkpointed will sign off on their coin in the checkpoint. Generally, this means that the operator has proof that each coin holder that wants their coin checkpointed has confirmed the checkpoint to be correct. Then, if the operator claims to have your permission but doesn’t, you know the operator is trying to cheat and the operator can be punished.

これは可能である！署名を用いるだけでよい。コインに checkpoint を打ちたい各ユーザーは、checkpoint にてコインを承認する、というのが基本的なアイデアである。大まかに言うと、これは、各コイン保有者が checkpoint が正しいことを承認したという証明をオペレータが持つことを意味する。すると、オペレータが「あなたに承認されている」と主張しているが実はそうでない場合、オペレータが不正を行おうとしていることがわかり、オペレータを処罰することができる。

Cryptoeconomic Aggregate Signatures

The idea here is that instead of publishing full signatures for every user, the operator only publishes a claim that a certain owner has provided a signature (in the form of a bitfield). For example, if we have 4 coins, and owner of coins 0 and 3 have provided signatures, then the operator would publish the bitfield “1001”. If, however, the owner of coin 3 did not provide a signature and the operator published that bitfield, then the owner of coin 3 could challenge by requesting the operator provide the owner’s signature. So our signatures are suddenly down to one bit per coin!

これは、全ユーザーの完全な署名を公開する代わりに特定のコイン保有者が署名を提出したという主張をオペレータが（ビットフィールド形式で）公開する、というアイデアである。例えば、4 つのコインが存在し、0 番目のコインの保有者と 3 番目のコインの保有者が署名を提出した場合、オペレータは「1001」というビットフィールドを公開する。3 番目のコインの保有者が署名を提出していないのにオペレータが「1001」というビットフィールドを公開してしまった場合、3 番目のコインの保有者はオペレータに対して署名の提出を要求することで challenge できる。こうすることで、署名は 1 コインあたり 1 bit まで小さくなる。

Checkpoint Zones

But wait, wouldn’t one bit per coin still be too expensive to put on-chain? Well, yes. Our scheme just requires putting the bitfield in calldata, so things work out to about 100k gas (currently ~$0.25) per 8192 coins = ~1 kilobyte. This is too much gas if we want to checkpoint many coins (millions) at the same time, so we turn to “checkpoint zones”.

ちょっと待った。1 コインあたり 1 bit でもオンチェーンに乗せるには高コストではないだろうか？このスキームが要求するのは上記のビットフィールドを calldata に含めることだけなので、8,192 コイン ＝ 〜 1 kilobyte あたり 100k gas（現在だと 0.25 ドル弱）程度となる。（数百万個の）たくさんのコインを同時に checkpoint を打ちたい場合、これは非常に高コストである。そこで、「checkpoint zones」に着目する。

Checkpoint zones effectively checkpoint some coins at a time. Every coin will be scheduled to be checkpointed on some regular basis. For example, coins 0-8191 might be checkpointed during one block, and coins 8192-16383 might be checkpointed in the next. By checkpointing on a rolling basis, we make sure that we’re always inside of the gas limit, even if we need to checkpoint millions of coins.

checkpoint zones によって、複数のコインに対して効率良く checkpoint を打つことができる。全てのコインに定期的に checkpoint を打つのである。例えば、あるブロックで 0 〜 8,191 番目のコインに checkpoint を打ち、次のブロックで 8,192 〜 16,383 番目のコインに checkpoint を打ち、といったように。定期的に checkpoint を打つことで、数百万のコインに checkpoint を打つ必要がある場合でも、gas は常に確実に gas limit 内に抑えられる。

---.icon

Challenging a Checkpoint

Users can challenge invalid checkpoints. Checkpoints can be invalid if the operator places a 1 at the index of a certain coin but the true owner hasn’t signed off on that checkpoint. Only the true owner knows if they’ve signed off or not, so each coin owner is responsible for verifying the bitfield in each checkpoint. Luckily, the user is already required to be online regularly to look for invalid exits on their coins, so we’re not changing any assumptions behind Plasma Cash.

ユーザーは不正な checkpoint に challenge できる。オペレータが特定のコインのインデックスに 1 を配置したが、そのコインの保有者は checkpoint を承認していなかった場合、checkpoint は不正となる。承認したかどうかは本当の保有者のみが知っているので、各コインの保有者は各 checkpoint におけるビットフィールドを検証する責任がある。ユーザーは保有するコインの不正な exit を発見するために定期的にオンラインであることを常時要求されるので、幸運なことに、Plasma Cash における前提を何も変更しないで済む。

If the operator places a 1 in the bitfield for a user that did not sign off on a signature, then the user will challenge. This challenge includes the user’s latest transaction in the history, attesting that the user is indeed the owner. The operator can then respond by either showing a signature from the owner or with a later transaction proving that the challenger is not really the owner. Multiple challenges may exist on the same coin at the same time, but only one bond will be paid per coin.

ユーザーが署名によって承認していないビットフィールドにオペレータが 1 を配置した場合、ユーザーは challenge することができる。この challenge には最新のトランザクションが含まれ、これによってユーザーがコインの保有者であることを証明する。オペレータは、保有者による署名、もしくは challenge しているユーザーが本当の保有者ではないことを証明するより新しいトランザクションを示すことで応答できる。同じコインに対して同時に複数の challenge が存在することがあるかもしれないが、報酬が支払われるのは 1 コインあたり 1 回だけである。

There’s a potential attack vector if the operator submits very many 1s in the bitfield at the same time, because each user that didn’t sign off will have to submit a challenge. To get around this, we define a maximum number of challenges that may be open per checkpoint at any one time (probably 256). If more than this max number of challenges are open at any one time, then the checkpoint is invalidated. This basically ensures that not everyone needs to challenge and we don’t overload the root chain with challenges.

オペレータが同時にビットフィールドに非常に多くの 1 を配置した場合、これは攻撃に繋がる可能性がある。なぜなら、承認していない各ユーザーが challenge を提出する必要があるから。これを回避するため、1 checkpoint に対して提出できる challenge の最大数（256 程度）を定義する。この最大数を超える chellenge が提出された場合、checkpoint は無効となる。これによって、全員が challenge する必要がないことと、challenge によって親チェーンに過負荷をかけないことが基本的に保証される。

---.icon

Caveats

Gas Cost

As we stated before, the bitfield grows with the total number of coins in the Plasma Cash chain, so things get more expensive as the total number of coins increases. This checkpoint scheme is a good solution for even many millions of coins, but might need to be revisited if we ever reach many tens of millions or even hundreds of millions of coins.

前述した通り、ビットフィールドは Plasma Cash チェーンの総コイン数とともに大きくなるので、総コイン数が増加するにつれてより高コストになっていく。この checkpoint スキームは数百万個のコインに対しても有効な解決策だが、コインが数千万個もしくは数億個に達した場合、再考する必要がある。

Liveness

We’re assuming that a user will be live at least once during the checkpoint challenge period. This doesn’t change any assumptions of Plasma Cash if we make the checkpoint challenge period at least as long as the exit challenge period.

checkpoint に対する challenge 期間の間、ユーザーは少なくとも 1 回はオンラインになることを仮定している。checkpoint に対する challenge 期間を少なくとも exit に対する challenge 期間と同じすれば、前提は Plasma Cash と何も変わらない。

Griefing

By Operator

The operator can grief a user by refusing to checkpoint a coin (always putting 0 in the bitfield). If there’s a 0 at some index, it’s impossible to tell if the operator didn’t receive a signature or is simply refusing to include it. This doesn’t harm any security, but means that we’re falling back on Plasma Cash-sized transaction history lengths. We could probably implement some sort of manual checkpointing as an on-chain transaction, but we want to avoid that if possible.

オペレータは、checkpoint を打つことを拒否する（常にビットフィールドに 0 を配置する）ことでユーザーを苛ませることができる。どこかのインデックスに 0 が存在した場合、オペレータが署名を受け取っていないのか、もしくは単に署名を含めることを拒否しているだけなのかを判断することは不可能である。この問題はセキュリティを損ねることはないが、結局 Plasma Cash 規模のトランザクション履歴が必要になってしまう。オンチェーンなトランザクションとして何らかの手動 checkpointing を実装することはできるかもしれないが、可能であれば避けたい。

By Users

Users can grief other users by making lots of open challenges and invalidating the checkpoint. If the open challenges aren’t valid, then this attack is very costly as each challenge requires a bond. This also doesn’t harm security, but might be annoying. We need to determine the optimal bond size that makes this attack as costly as possible without making it too costly to submit a challenge. Again, this case simply means that we fallback on the guarantees and security properties of Plasma Cash.

ユーザーは、大量の challenge を提出して checkpoint を無効にすることで他のユーザーを苛ませることができる。提出された challenge が正当でない場合、この攻撃は非常に高コストである。なぜなら、各 challenge には担保が必要だから。この問題もセキュリティを損ねることはないが、迷惑である。challenge の提出が可能な限り高コストになり過ぎないようにしつつも、この攻撃が高コストとなるような、最適な担保サイズを決定する必要がある。こういったケースも、結局は Plasma Cash と同等の保証・セキュリティとなってしまう。