合言葉を言わずに、知っていると示す
あるサイトが、あなたがパスワードを知っているか確かめたいとします。ふつうはパスワードを送るので、サイトもそれを持つことになります。ゼロ知識証明は、秘密を見せずに、その秘密を知っていると相手に納得させる方法です。このラボはとても小さな数で考え方を見せます。学ぶためのおもちゃで、実際に使えるほど安全ではありません。
このレッスンが終わると
メモ
証明者が秘密を明かさずに、それを知っていると検証者に納得させる仕組みを説明できます。
キーワード
- 証明者:秘密を知っていると主張する人。
- 検証者:その主張を確かめる人。
- チャレンジ:検証者がランダムに選ぶ問い。
- コミットメント:あとで開けられ、途中で変えられない、封をした値。
- ゼロ知識:検証者は主張が正しいことだけを知り、ほかには何も知らないこと。
- Merkle ルート:リスト全体を表す、1つの短いハッシュ。
はじめに:もう知っていること
メモ
頭の中で答えてください。1. ハッシュは長いメッセージを何に変えますか。2. 公平なコインを2回投げると、2回とも表になる確率はどれくらいですか。3. サイトがパスワードをそのまま保存してはいけないのはなぜですか。答え: 短い指紋に変える。4分の1。ファイルを読んだ人が誰でも手に入れてしまうから。
始める前に
メモ
レッスンの上のバーにある ラボを開始 を押し、動いていると表示されるまで待ちます。コンテナはひとつ、jupyter だけで、ターミナルからは docker exec jupyter でその中の Python を使います。これはコンテナの中でコマンドをひとつ実行する命令です。JupyterLab のリンクを押すと、ポート 8888 の画面が開きます。下の 実行 ボタンは、それぞれのコマンドをラボのターミナルに、同じセッションの中で順番に入力します。様子を見たいときや自分で入力したいときは、バーの ターミナルを開く(新しいタブ) を押します。
何度も繰り返すと、運が証明に変わる
洞窟に2本の道があり、鍵のかかった扉でつながっています。証明者は片方の道から入り、検証者はどちらの道から出てくるかを叫びます。合言葉を知っていれば、証明者は毎回通れます。20回中20回です。ごまかす人は、当てずっぽうが合ったときしか通れません。1000人のうち、1回目を通るのは493人、2回目は243人、10回目のあとは誰も残りません。運だけで20回通る確率は、1048576回に1回です。表示は英語で、cheaters はごまかす人、rounds はラウンドです。
docker exec jupyter python3 steps/cave.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
コミットメントは封をした封筒
スクリプトは、手の rock(グー)とランダムなソルトを合わせたハッシュを公開し、どちらも秘密にしておきます。あとで開けます。ソルトと一緒に rock で開くと True、paper(パー)では False なので、手は変えられません。ソルトがないと、当てる人が3つの手をハッシュして一致するものを見つけます。手を隠しているのはソルトです。
docker exec jupyter python3 steps/commit.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
Schnorr は秘密の数を知っていると示す
秘密は x = 65、公開鍵は y = 227 です。証明者が t を送り、検証者がチャレンジ c = 77 を送り、証明者が s = 38 と答えます。検証者は1つの式を確かめて True を得ますが、65 は一度も見ません。次にスクリプトは、同じランダムな k で2つ目のチャレンジに答えます。すると x が65と求まってしまいます。証明者は k を決して使い回してはいけません。
docker exec jupyter python3 steps/schnorr.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
確認
ヒント
検証者が t を見たあとでチャレンジを選ぶのはなぜですか。答え: 証明者が先にチャレンジを知っていたら、秘密を知らなくても、それに合う t を作れてしまうからです。
にせのやり取りも、本物とそっくりに見える
このスクリプトは x を知りません。先にチャレンジと答えを選び、それに合う t を作ります。確認は通ります。つまり、やり取りの記録は第三者には何の証明にもなりません。だからこそ、秘密について何も漏らさないのです。
docker exec jupyter python3 steps/simulate.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
ハッシュが検証者の代わりをする
Fiat-Shamir は、検証者のランダムなチャレンジを、公開鍵、t、メッセージのハッシュに置き換えます。すると証明者は1人で証明を作れ、誰でもそれを確かめられます。チャレンジは14になりました。証明は自分のメッセージでは通り、別のメッセージでは通りません。
docker exec jupyter python3 steps/fiatshamir.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
Merkle の証明は、名前がリストにあると示す
8つの名前を2つずつハッシュし、その組をまた2つずつハッシュして、1つのルートまで重ねます。dev がリストにあると示すには、8つの名前全部ではなく、兄弟のハッシュを3つ渡します。dev から経路をたどってハッシュするとルートになるので、答えは True です。同じ証明で名前 dan を試すと False です。
docker exec jupyter python3 steps/membership.pyここでは表示のみで、実行されません。「ラボを開始」を押すと、自分のラボのターミナルに入力できます。
よくある間違い
注意
ゼロ知識とは、検証者が何ひとつ知らないことだ、と考える人は多いです。検証者は1つだけ知ります。主張が正しいということです。知らないのは秘密そのものと、秘密を見つける手がかりです。何も教えない証明では、誰も納得しません。
ノートブックでの同じ作業
バーから JupyterLab を開き、start.ipynb をダブルクリックします。Schnorr の確認、Fiat-Shamir の証明、Merkle の証明を実行します。セルをクリックして Shift と Enter を押すと実行します。最後のセルは自分の問いを書く場所で、zk.py は全部を読み通せる短さです。
最後の確認
ヒント
見返さずに答えてください。1. 何度も繰り返すと、ごまかす人が捕まるのはなぜですか。2. ハッシュのコミットメントを当てられないようにしているのは何ですか。3. Schnorr の証明者が同じ k を2回使うと、どうなりますか。4. Fiat-Shamir で検証者の代わりをするのは何ですか。答え: 1回ごとに確率が半分になるから。ランダムなソルト。秘密が求まってしまう。ハッシュ。
先生へ
ヒント
このレッスンは、ラボで進めるレッスンの小さな例です。手順と実行ボタンがレッスンで、ラボは生徒ひとりひとりのコピーです。ラボはサービスがひとつで、Python の標準ライブラリだけで書いたゼロ知識証明が入った JupyterLab です。自動採点はありません。生徒は自分のノートブックを JupyterLab からダウンロードして、分かったことの一文といっしょに提出します。学習のポイント:1. ランダムなチャレンジを繰り返すと、ごまかしはまず通らない。2. コミットメントは値を隠し、固定する。3. Schnorr は秘密を知っていることを示し、Fiat-Shamir はそれを非対話型にする。よくある思い込み:検証者は何ひとつ知らないと考えること。数はわざと小さく、安全ではありません。用意するもの:ラボとブラウザー。ヒント:最初の実行の前に、扉を2つ使って教室で洞窟のゲームをしてください。ご自分のモジュールにコピーして変更するか、レッスンビルダーのラボメニューから一から作ってください。