あとから変えられない入札
コミットメントとは、秘密の値に今のうちに封をして、あとで開ける値のことです。開けたときに、途中で変えていないことも示せます。封をした封筒と同じ働きです。
ゼロ知識証明も、封をした入札のオークションも、公平なオンラインゲームも、ここから始まります。
このレッスンのゴール
メモ
値へのコミットメントを作り、それが正しく開くかを確かめることができる。
キーワード
| ことば | いみ | れい |
|---|---|---|
| コミットメント | あとで開ける、封をした値 | |
| 開封 | 封を解く、値とソルトの組 | |
| ソルト | ハッシュの前に混ぜる、ランダムな文字列 | |
| 隠蔽性 | コミットメントから値が分からないこと | |
| 拘束性 | 別の値としては開けないこと | |
| 群 | 数の集まりと、それを組み合わせる1つの方法 | 1019 で割った余りでの 4 のべき |
学生が入力するセルは、このプレビューでは空白です。
コミットメントの2つの役目
1つ目は、値を隠すことです。コミットメントを見ても、中身は分かりません。2つ目は、値に縛ることです。公開したら、入れた値としてしか開けません。
縛るのはハッシュです。同じハッシュになる2つの入力は、誰にも見つけられません。隠すのはランダムなソルトです。ソルトは誰にも当てられません。
手にコミットして開く
docker exec jupyter python3 steps/commit.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
ラボの表示を読む
rock はグー、paper はパー、scissors はチョキ、salt はソルトです。
スクリプトが公開したコミットメントは 4e219afe2a8aa485 で始まります。ソルトと一緒に rock で開くと True、paper では False でした。これが拘束性です。次に、ソルトなしでコミットしました。当てる人が3つの手をすべてハッシュすると、rock が一致しました。値が3通りしかなければ、ハッシュだけでは何も隠せません。隠すのはソルトです。
試そう: 封をした3つの入札
import hashlib
def commit(value, salt):
return hashlib.sha256((salt + ":" + value).encode()).hexdigest()
# 中古のノートパソコンへの、封をした3つの入札。誰かが開ける前に公開します。
bids = [["イネス", "120", "q81z"], ["ジョー", "95", "t4kk"], ["カイ", "130", "m2pa"]]
for bid in bids:
print(bid[0], "が公開:", commit(bid[1], bid[2])[:12])
# あとでカイが「入札は140だった」と言います。開くでしょうか。
print("カイが140で開くと:", commit("140", "m2pa") == commit("130", "m2pa"))
# 140 を 130 に変えて、もう一度実行しましょう。
ペダーセン・コミットメントは群を使う
ラボには群もあります。G = 4 のべきを、P = 1019 で割った余りで計算したものです。全部で Q = 509 個あります。もう1つの数 H = 9 も、同じ群に入っています。
数 m とランダムな r へのペダーセン・コミットメントは、G の m 乗と H の r 乗の積を P で割った余りです。ランダムな r が m を隠します。H を G のべきで書く方法を誰も知らない限り、拘束性が保たれます。
小さな群で42にコミットする
docker exec jupyter python3 steps/pedersen.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
例: ラボの表示
| コミットメント | m | r | 値 |
|---|---|---|---|
| commit(42)、r = 100 | 42 | 100 | 130 |
| commit(42)、r = 7 | 42 | 7 | 278 |
| commit(20) と commit(22) の積 | 20 + 22 | 11 + 30 | 630 |
| commit(42)、r = 41 | 42 | 41 | 630 |
学生が入力するセルは、このプレビューでは空白です。
ペダーセン・コミットメントは足せる
同じ42から130と278ができたので、同じ値が繰り返されても気づかれません。そして2つのコミットメントを掛けると630になり、20 + 22 と 11 + 30 へのコミットメントと同じでした。封をしたまま、数を足せるのです。
証明の仕組みは、これで秘密の和を確かめます。ただし元が509個しかないと、誰でもすべてのべきを試して拘束性を破れます。
よくある間違い
注意
「値をハッシュすれば隠せる」と考える人がいます。隠せるのは、値の候補がとても多いときだけです。投票、じゃんけんの手、小さな数なら、当てる人はすべての候補をハッシュします。必ず長いランダムなソルトを混ぜましょう。