chamber simple exit gameの提案


#1

Chamberの新しいexit gameの提案です。実装はこちら

背景

問題を簡単に説明すると、

  • オペレーターは正しいトランザクションの前に、不正なトランザクションを含めることができる。
  • 不正にはdouble spendとinvalid historyが存在する
  • 最新の正しいトランザクションをwithholdされる場合がある
    • トランザクションを明らかにする過程で、不正なexitのexit期間を超えてしまう

このようなケースに対応するintarctiveなexit gameを設計するのが非常に難しいというのが、最初のPlasma Cashのexit-gameの抱えていた問題だと認識しています。
これに対してDanのsimple exit game(ethresearchの4917)が提案されました。
このsimple exit gameは、上の問題を解決していますが、二つの問題があるのでは無いかと思っています。

  1. 間にTxがある場合challengeできない、というルールの実装がrangeでは難しい
    • これは同じsegment上のtxを走査するデータ構造の構築がスマートコントラクトでは難しいという話です。最悪priority queueを全走査しなくてはいけない気がします。
  2. challenge可能期間とexit期間より短いということは、challenge可能期間の間隔でオンラインにならなければいけない

Chamberではこれらの問題を解決しました。

  • exit
  • challenge
  • requestHigherPriorityExit

この3種類の関数だけでexit gameを成立させます。
またさらに以下の追加だけで、force includeとcheckpointの問題も解決します。

  • includeSignature
  • challengeTooOldExit

提案

exit

exit開始の際に呼びます。
基本的には通常のexit同じですが、exitは優先度という値を持ちます。
この優先度は通常はブロック番号になりますが、もし同じTxが過去にchallengeで使用されていた場合、その時challengeされたexit(つまり今exitしようとしているTxの親Tx)のブロック番号が優先度になります。またこの時のexitをchildExitとして登録します。
exit期間は1 weekとします。

challenge(exitId, challengeTx)

spent challengeします
もし対象のexitIdにparentExit(相手から見て自分がchildExit)が存在する場合、そのparentExitをspentすることで、double spent challengeも可能です。
もし対象のexitのlowerExitが存在する場合(requestHigherPriorityExitで関連づけられている場合)、lowerExitのchallenge counterがデクリメントされます。またこの時、exit期間が1 day延長されます。

この延長のロジックには少し工夫が必要です。challengeを利用して何度も延長させることができるからです。延長は一度だけ、exit期間の残りが1dayを切っているか過ぎていた場合です。

requestHigherPriorityExit(higherExit, lowerExit)

segmentが被っている二つのexitに対して行うことができます。
二つをhigherExitとlowerExitと呼びます。
higherExitのブロック番号は、lowerExitよりも小さくなければいけません。
このリクエストによってlowerExitのchallenge counterがインクリメントされます。
higherExitに対して、lowerExitを関連付けます。

finalizeExit

以下の場合にexitを確定させ、資金を引き出すことができます

  • challenge counterが0
  • exit期間が過ぎている

その他重要な点

  • challengeで重要なのが、exitしようとしているstateを適切にspentしているか検証することです。送金であればexitの出力のsegmentに、challengeTxの入力のsegmentが含まれている必要がありますし、ロックされた資産であれば適切にアンロックされていることを検証する必要があります。
  • 複数の入力を持つTxにはconfsigが必要です。confsigが必要なTxは、過去にchallenge使用されていても、exitでpriorityが更新されることはありません。これはconfsigがあるTxは、その直前までの履歴が正常でなければ有効にならないため、priorityを更新する必要がないためです。

考察

このexit gameがどう働くか、以下のケースで確認して見ます。

Suppose Alice owns a coin at block 1 and submits a spend to Bob, but the operator puts an invalid state transition in block 2 and then includes Alice’s transaction in block 3 (without making any of the data available). Alice can use the following protocol to exit her coin (cooperatively with Bob):

a) Aliceはblock1でexitを試みます。
b) 1 week以内に、オペレーターはblock 3のTxでchallengeします。
c) Bobはblock3でexitを試みます。priorityはblock 1となります。
d) 1 week以内に、オペレーターはblock 2でexitします。
e) オペレーターはblock 2のexitを、block 3のexitよりも優先度の高いexitとして関連づけようとします(requestHigherPriorityExit(block2, block3))が、block 3のexitのpriorityはblock 1なのでできません。
f) Bobはblock3のexitをfinalizeできます。

その他の機能

force include

atomic swapの様にconf sigが足りない状況に対応できます。
この機能を使用するためにexitとchallengeを少し修正します。

exit

  • exitする時には、confsigが一つ足りない状態でTxを提出できます。
  • これをforce includeと名付けます
  • この場合、exitが確定した場合にはwithdrawalではなく、そのTxがblockから削除されます。
  • 実際にはexit開始時から、そのTxはblockから削除されます。

challenge

  • force includeはexitと同じようにchallengeできます
  • challengeされると、そのTxのblockからの削除を取り消します

requestHigherPriorityExit

exitと同様に、force includeでも、低い優先度のexitを足止めできます。

includeSignature

  • 足りないconf sigを提出します
  • includeSignatureされると、そのTxのblockからの削除を取り消します

checkpoint

challengeTooOldExit

3 weekよりも古いblockのうちで一番新しいTxを、OldestTxと定義します。
challengeTooOldExitでは、OldestTxで、それより前のexitにchallengeできます。つまりOldestTxよりも、古いTxは全て使用不可になります。
これによりOldestTxより古い履歴を持つ必要はありません。