長いリストに名前が1つあると示す
Merkle 木は、リスト全体を1つの短いハッシュ、ルートに変えます。所属証明は、リスト全体ではなく少しのハッシュだけで、ある項目がリストにあることを示します。
ゼロ知識の仕組みでは、あるグループの一員であることを示すのに使います。ブロックチェーンでは、支払いがブロックに入っていることを示すのに使います。
このレッスンのゴール
メモ
Merkle の所属証明を、ルートに照らして検証できる。
キーワード
| ことば | いみ |
|---|---|
| 葉 | リストの1つの項目のハッシュ |
| 節 | 2つのハッシュをつないだもののハッシュ |
| ルート | 木のいちばん上にある、ただ1つのハッシュ |
| 兄弟 | 組になったもう一方のハッシュ |
| 所属証明 | 葉からルートまでの経路にある兄弟たち |
学生が入力するセルは、このプレビューでは空白です。
木はハッシュのハッシュ
すべての項目をハッシュして、葉を作ります。葉を2つずつ組にし、組ごとにハッシュして、1つ上の段を作ります。ハッシュが1つになるまで繰り返します。それがルートです。
どれか1つの項目を変えると、その葉が変わり、親が変わり、ルートまで変わります。だからルートはリスト全体を表します。モジュール37 (ブロックチェーン) ではブロックをハッシュで1列につなぎました。木は2つずつつなぎます。
試そう: 4つの部屋の木
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 でした。ほかの名前をこのルートに変える経路は、誰にも作れません。
例: 証明の長さ
| リストの項目数 | 葉の上の段の数 | 証明のハッシュの数 |
|---|---|---|
| 4 | 2 | 2 |
| 8 | 3 | 3 |
| 1024 | 10 | 10 |
| 1048576 | 20 | 20 |
学生が入力するセルは、このプレビューでは空白です。
よくある間違い
注意
「兄弟はどの順番でつないでもよい」と考える人がいます。そうではありません。node(a, b) と node(b, a) は別のハッシュです。項目の位置が側を決めます。その段で位置が偶数なら、兄弟は右に置きます。
merkle.py の関数を一覧にする
docker exec jupyter grep -n def merkle.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。