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

無料レッスン

Merkle 木と所属証明

このレッスンのあとで: Merkle の所属証明を、ルートに照らして検証できる。

65分のレッスンコマンド2件ゼロ知識証明ラボ:コミットメント、Schnorr、Fiat-Shamir、Merkle の証明を Python で

長いリストに名前が1つあると示す

Merkle 木は、リスト全体を1つの短いハッシュ、ルートに変えます。所属証明は、リスト全体ではなく少しのハッシュだけで、ある項目がリストにあることを示します。

ゼロ知識の仕組みでは、あるグループの一員であることを示すのに使います。ブロックチェーンでは、支払いがブロックに入っていることを示すのに使います。

このレッスンのゴール

メモ

Merkle の所属証明を、ルートに照らして検証できる。

キーワード

ことばいみ
葉リストの1つの項目のハッシュ
節2つのハッシュをつないだもののハッシュ
ルート木のいちばん上にある、ただ1つのハッシュ
兄弟組になったもう一方のハッシュ
所属証明葉からルートまでの経路にある兄弟たち

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

木はハッシュのハッシュ

すべての項目をハッシュして、葉を作ります。葉を2つずつ組にし、組ごとにハッシュして、1つ上の段を作ります。ハッシュが1つになるまで繰り返します。それがルートです。

どれか1つの項目を変えると、その葉が変わり、親が変わり、ルートまで変わります。だからルートはリスト全体を表します。モジュール37 (ブロックチェーン) ではブロックをハッシュで1列につなぎました。木は2つずつつなぎます。

試そう: 4つの部屋の木

コード: python
import hashlib

def leaf(item):
    return hashlib.sha256(("leaf:" + item).encode()).hexdigest()

def node(left, right):
    return hashlib.sha256(("node:" + left + right).encode()).hexdigest()

# 共用の建物で予約された4つの部屋。
a = leaf("101号室")
b = leaf("102号室")
c = leaf("103号室")
d = leaf("104号室")
left = node(a, b)
right = node(c, d)
root = node(left, right)
print("ルート:", root[:16])

# 103号室が予約済みだという証明: d、次に left。
check = node(left, node(leaf("103号室"), d))
print("103号室の証明でルートになる:", check == root)
# 外側の呼び出しで left と内側の node を入れ替えて、もう一度実行しましょう。

証明は、上へたどる兄弟たち

ある項目がリストにあると示すには、その兄弟を渡します。隣のハッシュ、次に親の隣のハッシュ、と順に続けます。確かめる人は項目をハッシュし、兄弟を正しい側につなぎ、最後の結果をルートと比べます。

8個のリストなら兄弟は3つ、約100万個のリストでも20個で済みます。

dev がリストにあるか確かめる

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

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

ラボの表示を読む

root はルート、proof は証明、list はリストです。

8つの名前から、fb53457810bd44ae で始まるルートができました。4番目の名前 dev の証明は3つのハッシュで、それぞれに置く側が L (左) か R (右) で書いてあります。dev を経路に沿ってハッシュするとルートになったので、答えは True です。同じ証明で名前 dan を試すと False でした。ほかの名前をこのルートに変える経路は、誰にも作れません。

例: 証明の長さ

リストの項目数葉の上の段の数証明のハッシュの数
422
833
10241010
10485762020

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

よくある間違い

注意

「兄弟はどの順番でつないでもよい」と考える人がいます。そうではありません。node(a, b) と node(b, a) は別のハッシュです。項目の位置が側を決めます。その段で位置が偶数なら、兄弟は右に置きます。

merkle.py の関数を一覧にする

コマンド
docker exec jupyter grep -n def merkle.py

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

このラボとソースについて: ゼロ知識証明ラボ:コミットメント、Schnorr、Fiat-Shamir、Merkle の証明を Python で

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