クリーム色の背景、色付き表示、高コントラスト、大きな文字のほうが読みやすいですか?配色と文字を選ぶと、すべてのページに一度で反映されます。

無料レッスン

楽観的ロールアップと不正証明

このレッスンのあとで: 二分探索で、バッチの中の最初のまちがった手を見つけることができる。

70分のレッスンコマンド2件ロールアップラボ:バッチ、不正証明、データ可用性、引き出しを Python で

異議がなければバッチを信じる

楽観的ロールアップはバッチとルートを投稿し、メインチェーンはそれをそのまま信じます。誰かが異議を出さない限り、何も確かめません。

危なそうに聞こえます。今日は、正直な確認役が1人いれば十分な理由と、メインチェーンが1手だけを再実行して争いに決着をつける方法を見ます。

このレッスンのゴール

メモ

二分探索で、バッチの中の最初のまちがった手を見つけることができる。

キーワード

ことばいみ
楽観的ロールアップ異議が出ない限り、バッチを正しいとみなすロールアップ
トレースバッチの前のルートと、各手のあとのルートの並び
不正証明バッチの1手がまちがっているという証拠
二分探索範囲を毎回半分にして、1点を見つける方法
チャレンジ期間バッチに異議を出せる期間
確定もう異議を出せない状態

学生が入力するセルは、このプレビューでは空白です。

トレースで、両者が分かれる場所が分かる

どのバッチにもトレースがあります。バッチの前のルートと、送金を1件適用するごとのルートです。確認役は投稿データを再実行し、自分のトレースを作ります。

最後のルートが違えば、両者は始めでは一致し、終わりでは一致しません。その間のどこかに、初めて分かれる手があります。メインチェーンは、その1手だけを再実行すれば、どちらが正しいか分かります。

二分探索なら、その手がすぐ見つかる

両者は真ん中の手でルートを比べます。そこで一致すれば、誤りは後半にあります。一致しなければ、前半にあります。

質問のたびに、残りが半分になります。16手なら4回、1000手なら10回、100万手なら20回です。本物の争いのゲームは、これをメインチェーンの上で1手ずつ進めます。

うそつきのシーケンサーを捕まえる

コマンド
docker exec jupyter python3 steps/dispute.py

ここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。

例: ラボの表示

質問尋ねた手答えまちがった手の範囲
18一致9手目から16手目
212不一致9手目から12手目
310一致11手目から12手目
411不一致11手目

学生が入力するセルは、このプレビューでは空白です。

試そう: 32手の二分探索

コード: python
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人いれば十分です。争いになった手は、メインチェーンが自分で再実行するからです。必要なのは、データが公開されていることと、期間が十分に長いことです。

このラボとソースについて: ロールアップラボ:バッチ、不正証明、データ可用性、引き出しを Python で

授業で使いますか?このモジュールを学生に割り当てると、教員用ガイド、自動採点つきの課題、学生ごとのラボを使えます。