withhold tolerant exit game

#1

Plasmaのexit時に、fraud proofのために必要な情報を攻撃者がwithholdするのを、インセンティブ的に抑制するexit gameを考えました。

・問題背景
最初に、任意のスマートコントラクトをPlasmaで扱うにはどうすればいいか考えていました。例えば、特定の条件を満たした時tokenを新規発行できるようなものを扱う時(miningで作れるVreathのunitなど)、operatorはその条件を満たしていないにもかかわらず自分の残高を勝手に増やし、そのstateをexitさせることができます。(stateの中身をwithholdすれば、誰もfraud proofできないです。)
いかなる場合でもexit時に不正を排除できる一番シンプルな方法は、もし攻撃者がwitholdしていた場合、チャレンジャーは実際のデータを要求し、攻撃者に正当性を証明させるということです。(そのデータはメインチェーンに書き込みます。)しかしこの方法では、最悪の場合全てのexit時にデータの書き込みが行われ、メインチェーンに大きな負荷を与えます。

・提案アイデア
攻撃者が早くデータを提示するインセンティブを与えるような、withhold tolerant exit gameを考えました。 もしexitがvalidな場合、チェーンには一切情報が残らず、invalidな場合は速やかにfraud proofが行われgameが終了します。
exit時に攻撃者とチャレンジャーの間で、以下のようなgameを行います。ただし、ゲーム開始時にチャレンジャーと攻撃者はそれぞれ10 tokenをdepositしているとします。(チャレンジャーは3の段階でdepositします。)

  1. チャレンジャーはoff-chainで、必要なデータを要求する
  2. 1のデータをもらえ、exitがinvalidなら、exitのfraud proofをする。(データが有ればチャレンジャーはexitがvalidかどうか判定できます。)
  3. もし1でデータが時間内にもらえなかったら(off-chain withhold)、チャレンジャーはon-chainでデータを要求する。(ゲーム開始)
  4. 3の後、もしデータを時間内にもらえ、exitがvalidなら、OKサインをメインチェーンに書きこむ
  5. 3の後、もしデータを時間内にもらえ、exitがinvalidなら、fraud proofをメインチェーンに書きこむ
  6. 3の後でも、まだデータを時間内にもらえなければ(on-chain withhold)、withholdサインをメインチェーンに書きこむ
  7. 4の後、もしexitがvalidなら、operatorは正当性証明をメインチェーンに書きこむ
  8. 4の後、時間内にoperatorが正当性を証明できなければ、exitはinvalidとみなされる。

そして、各段階にそれぞれ、利益と損失を以下のように定義します。
(チャレンジャーの利益・損失, 攻撃者の利益・損失)という表記です。
なお、数値の大きさは一例で、大小関係が重要です。

  1. (0,0)
  2. (8,-8)
  3. N/A
  4. (-1,-2)
  5. (7,-9)
  6. N/A
  7. (-2,-5)
  8. (5,-10)

このルールの下で、チャレンジャー・攻撃者の取る行動を考察してみます。
(1)チャレンジャーの取れる行動
チャレンジャーは、exitがvalidかinvalidかを決めることはできませんが、どのタイミングでデータをもらったことにするか(どのタイミングまでwithholdされていたか)は自由に申告することができます。
また、invalidなものをあえてvalidと言うことはできます。
このような状況で、invalidなものは正直にinvalidだと言わせ、データを受け取ったらすぐにそれを申告させるためには、
①validな時よりinvalidな時の方が利益が大きくなるようにする。
②validでもinvalidでも、早くゲームを終わらせる方が利益が大きくなる(損失が小さくなる)ようにする
上のルールはこの2つの条件を満たしていると思います。

(2)攻撃者の取れる行動
攻撃者は、exitがvalidかinvalidかを決めることはできますが、一度決めた後それを変えることはできません。また、どこまでwithholdするかは自由に決められます。
このような状況で、invalidなexitとwithholdをさせないためには、
①validな時よりinvalidな時の方が損失が大きくなるようにする。
②validでもinvalidでも、早くゲームを終わらせる方が利益が大きくなる(損失が小さくなる)ようにする
上のルールはこれらの条件も満たしています。

よって、2者にとって最適な行動は、exitがvalidなときはそもそもゲームを始めないこと、invalidなときはゲームを始める前にfraud proofさせることになります。どちらも最小限のメインチェーンへの書き込みで済むので、負荷を最小化することができます。

もしチャレンジャーと攻撃者が共謀していた場合、このgameは成り立たなくなりますが、exit検証期間中に何度もこのgameを行えるならば、少なくとも一人のチャレンジャーが攻撃者と共謀していない時、正しくfraud proofされます。

このgameで、不正なexitはほぼ全て防ぐことが可能になりうるので、任意のスマートコントラクトを扱える可能性が高いと思います。

皆さんのご意見いただけると嬉しいです。

1 Like
#2

「stateの中身」と表現するより、「アカウントモデルの子チェーンで、状態遷移を引き起こすTxの存在証明(txのmerkle treeのinclusion proof)」と表現したほうがいいのかな?

1 Like
#3

基本的にWithholdingと組み合わせたInvalid History Exitでオペレーターが金を盗みたい時、Plasma Contractに預けてあるものを根こそぎ奪いたいと思うんですよね、このときのrisk exposureは1PRE(Plasma Risk Exposure)としましょうか。それで、このゲームのようなインセンティブが成り立つための、 10 token が一体どのくらいの経済価値なのかを求めましょう。

仮に 10token=1PRE だとします。攻撃は抑止できますが、双方準備できないので、ありえないですね。

10token=0.01PRE とします。双方ギリギリ準備できるかもです。でも、チャレンジャーのほうが相対的に金を用意するのが難しそうに見えます。金がなさそうなときを狙った不意打ちもありえそうです。金がなくなるまで攻撃者は連打してくるのもありえそうです。チャレンジャーが50発くらいで力尽きたら悠々と金を抜けますね。

というわけで、しんどいのではないかなと思います。

1 Like
#4

ご意見ありがとうございます!

①攻撃者の攻撃成功時の利益が莫大
②チャレンジャーの資金的体力
この2つが大きなネックになってしまうのですね。

Vreathでの話になってしまい恐縮ですが、①と②の課題については以下のように対策を考えています。

①の解決法
Vreathのtoken baseのモデルでしたら、contractのstateをaddressごとに分割することが可能です。
例えば、Bobが所有者のERC20 token "T"をexitしようと思った時、account baseでしたらTのcontract stateをまるごと扱う・まるごとexitするような形式になると思うのですが、token baseの場合「BobがTをいくら持っている」とアドレスごとに分割されたstateだけが対象になります。(exitは一回に一人分だけと制約すると、攻撃者はcontractのstate丸ごとを一度にexitすることはできなくなります。)
分割された関連stateのみで正当性を証明できるというのは、こちらのスライドの50枚目がわかりやすいかと思います。(https://www.slideshare.net/SoraSuegami/vreath-meetup-in-january-2019?fbclid=IwAR3X_Hh9gTqkutT8ab8hQeHQd_UVc23oJcWPjizthNIJMHM8fUJQdA-L0IY) AliceがTを10持っていて、それをBobに送ってBobのTの残高が10になったという取引の場合、変更前のAliceのstate(Tを10枚)、変更前のBobのstate(Tを0枚)、input data(amountが10)というデータを表すTxさえあれば、メインチェーン側で正しいoutput stateを計算できます。また、あるstateに紐付けられたmeta dataを書き換えたい場合、そのstate前の変更前のものと書きこむmeta dataを表すTxを示せば、正しいoutput stateを計算できます。
以上のように、exitするstate数が少なく済むことから、攻撃成功時の利益はそれほど高くならないと予想されます。(Bobの残高しか奪えないので)

②の解決法
このexit gameのチャレンジャーは、exitされる子チェーンのユーザーだけでなく、メインチェーンの人たちも対象として考えています。例えば、メインチェーンのvalidatorが兼任するという形です。二重支払い攻撃ではなく不正な状態遷移を防ぐ場合、子チェーンのユーザーの協力がなくても大丈夫です。なぜなら、攻撃者はどこまでもwithholdしようと思っても、最後は正当性を証明しないといけないからです。例え小チェーンの全ユーザーがoperatorと共謀していたとしても、不正なものを正しいと証明することはできないです。
このように、チャレンジャーの資産は最大でメインチェーンvalidatorの資産程度なので、チャレンジャーの資金的体力は攻撃者より高いぐらいではないかと考えています。

半分宣伝みたいな回答になってしまい、申し訳ありません。

#5

①Exit する人間はどうやってその Exit が valid であることを証明しますか?
ユーザが自分の残高を勝手に増やす操作を許容した時その動作が valid であることを証明できるのはオペレータ(子チェーンの管理者)しかいないように見えます。
Vreath のように新規発行の条件を満たしていることをオンチェーンの情報無しで証明することが出来れば問題ないですがそうでない場合は valid であることを容易に証明出来ない問題が発生します。

②Exitor が valid であることを証明できない(or しないとき)の問題
Exitor がチャレンジャーからの要求を無視した(またはvalidであることを証明できない)場合、チャレンジャーは Exitor が不正しているかしていないかを判別できません。
そのような場合、以下の条件が満たされている場合チャレンジャーはチャレンジをします。

チャレンジが成功する確率を P とします。
チャレンジに成功した際の利益を X チャレンジに失敗した際の損失を Y とすると
チャレンジャーがチャレンジをした時得られる期待値は P * X - (1-P) * Y になります。
期待値が > 0 の場合、チャレンジをする。そうでない場合はチャレンジしません。

適切な XY の値(正確には X > (1/P-1) * Y であるような値)にするとチャレンジャーは必ずチャレンジします。
しかし、チャレンジ処理は全てメインチェーンに対するトランザクションなのでメインチェーンの負荷を減らすという本来の目的が損なわれます。(全チャレンジャーがメインチェーンに我先にとチャレンジを投げる状況が発生する)

逆に X < (1/P-1) * Y であるような値を設定するとチャレンジャーの期待値が下回りチャレンジをしなくなります。


書いてて思ったけど②は①が解決している場合に大した問題にはならなそうなのと
①が解決していない場合にそもそも根本的にまずい気がしますね。

任意のスマートコントラクトについてコレで解決するのは厳しそうな気がします。
(ただし、条件を絞るとこれがベストプラクティスになりうる)

1 Like
#6

ご意見ありがとうございます!

①どうやってuserはexitの正当性を証明するか
確かに、もしユーザーが正当性を証明できるraw stateやtxを持っていなかった場合、自分一人の力でexitの正当性を証明するのは不可能になります。UIとして、誰かに送金してもらうときには送金者の残高がvalidであることを証明できるデータをもらっておくなど、自分のstateの正当性を証明できるデータはあらかじめユーザーが持っておく必要がありそうです。
これをdepositされた段階から全て持っておくとデータ量が膨大になりますが、Plasma XTなどと併用すると必要なデータ量を減らせます。

②チャレンジの期待値について
攻撃者がデータをwithholdしなかった時、exitがvalidな場合はゲームを始めないこと、invalidな場合はゲームを始めずfraud proofすることが、利益の期待値が最大になる行動になります。(withholdされなければ、exitがvalidかinvalidかは確率的な事象ではなく、決定事項になります。)そのため、validなexitの場合はメインチェーンにtxを一切書き込まないで済みます。
チャレンジが成功するか失敗するか不透明なのは、攻撃者がデータをwithholdした時です。データがない状態でexitがinvalidであると考えられる確率は、容易には計算できなさそうです。しかし、チャレンジ成功時の報酬を損失に比べて十分大きくすれば、何人かにはチャレンジの報酬期待値が正だと判断してもらえると考えています。(これだけだと、みんなチャレンジしてメインチェーンへの負荷が大きくなりそうですが、一方で攻撃者にはデータをwithholdしないインセンティブがあるので、ゲーム自体がそれほど頻繁に行われないと思います。)

1 Like