異議がなければバッチを信じる
楽観的ロールアップはバッチとルートを投稿し、メインチェーンはそれをそのまま信じます。誰かが異議を出さない限り、何も確かめません。
危なそうに聞こえます。今日は、正直な確認役が1人いれば十分な理由と、メインチェーンが1手だけを再実行して争いに決着をつける方法を見ます。
このレッスンのゴール
メモ
二分探索で、バッチの中の最初のまちがった手を見つけることができる。
キーワード
| ことば | いみ |
|---|---|
| 楽観的ロールアップ | 異議が出ない限り、バッチを正しいとみなすロールアップ |
| トレース | バッチの前のルートと、各手のあとのルートの並び |
| 不正証明 | バッチの1手がまちがっているという証拠 |
| 二分探索 | 範囲を毎回半分にして、1点を見つける方法 |
| チャレンジ期間 | バッチに異議を出せる期間 |
| 確定 | もう異議を出せない状態 |
学生が入力するセルは、このプレビューでは空白です。
トレースで、両者が分かれる場所が分かる
どのバッチにもトレースがあります。バッチの前のルートと、送金を1件適用するごとのルートです。確認役は投稿データを再実行し、自分のトレースを作ります。
最後のルートが違えば、両者は始めでは一致し、終わりでは一致しません。その間のどこかに、初めて分かれる手があります。メインチェーンは、その1手だけを再実行すれば、どちらが正しいか分かります。
二分探索なら、その手がすぐ見つかる
両者は真ん中の手でルートを比べます。そこで一致すれば、誤りは後半にあります。一致しなければ、前半にあります。
質問のたびに、残りが半分になります。16手なら4回、1000手なら10回、100万手なら20回です。本物の争いのゲームは、これをメインチェーンの上で1手ずつ進めます。
うそつきのシーケンサーを捕まえる
docker exec jupyter python3 steps/dispute.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
例: ラボの表示
| 質問 | 尋ねた手 | 答え | まちがった手の範囲 |
|---|---|---|---|
| 1 | 8 | 一致 | 9手目から16手目 |
| 2 | 12 | 不一致 | 9手目から12手目 |
| 3 | 10 | 一致 | 11手目から12手目 |
| 4 | 11 | 不一致 | 11手目 |
学生が入力するセルは、このプレビューでは空白です。
試そう: 32手の二分探索
first_wrong = 21
def agree(i):
return i < first_wrong
good = 0
bad = 32
questions = 0
while bad - good > 1:
middle = (good + bad) // 2
questions = questions + 1
print("質問する手:", middle, "一致:", agree(middle))
if agree(middle):
good = middle
else:
bad = middle
print("最初のまちがった手:", bad, "質問の回数:", questions)
# first_wrong を1に、次に32に変えましょう。質問は何回になりますか。
異議は期限内に出す
バッチがいつまでも未確定では、誰もそれを頼りにできません。そこで、どのバッチにもチャレンジ期間があり、多くは7日です。期間が終わると、バッチは確定します。
ラボの期間は12秒のスロットが50400個で、7.0日です。スロット1000で投稿されたバッチには、スロット51399までは異議を出せて、51400では出せません。
チャレンジ期間が閉じるのを見る
docker exec jupyter python3 steps/window.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
よくある間違い
注意
楽観的ロールアップには、確認役の大半が正直である必要がある、と考える人は多いです。期限内に見張る正直な確認役が1人いれば十分です。争いになった手は、メインチェーンが自分で再実行するからです。必要なのは、データが公開されていることと、期間が十分に長いことです。