ゼロ知識証明ラボ:コミットメント、Schnorr、Fiat-Shamir、Merkle の証明を Python で

このラボでは、生徒ひとりひとりに専用の JupyterLab を渡します。中には、Python だけで書いたゼロ知識証明が入っていて、全部を読み通せる短さです。何度も繰り返す洞窟のゲーム、ハッシュのコミットメントとペダーセン・コミットメント、Schnorr の識別プロトコル、それを非対話型にする Fiat-Shamir、所属証明つきの Merkle 木、範囲の確認がついた小さな算術回路です。9本の短いスクリプトが、それぞれの考え方がどう動くかを、毎回同じ結果で表示します。

数はわざと小さくしてあり、どの値も1行に収まります。安全ではありません。群の元は509個しかなく、すべてを試して秘密を見つけるスクリプトもあります。攻撃のラボでもありません。どのコピーもインターネットにも、ほかの生徒にもつながらず、何もダウンロードされません。

生徒が学ぶこと

知識の証明とは何か、そしてその3つの性質です。正直な証明者は必ず通り、ごまかす人が洞窟のゲームを20回通るのはおよそ100万回に1回で、検証者は答え以外に何も知りません。ハッシュとソルトで値にコミットして開き、2つのペダーセン・コミットメントを開けずに足し、秘密65、公開鍵227で Schnorr を実行し、証明者がランダムな数を使い回すと秘密が漏れるのを見ます。シミュレーターは確認に通る記録をにせて作れるので、記録が何も漏らさないことが分かります。Fiat-Shamir でプロトコルを誰でも確かめられる証明に変え、3つのハッシュの Merkle 証明で8つのうち1つの名前がリストにあることを確かめ、小さな回路のゲートで証人を確かめます。これは SNARK が証明する主張です。応用暗号、セキュリティ、ブロックチェーンの講座に向いています。正確な文言は、お使いの資格団体の単元で確認してください。ここには引用していません。

ブラウザーで実行する

ラボは jupyter というサービスをひとつ起動します。このサービスは、zk.py、merkle.py、circuit.py、はじめのノートブック、短いスクリプトを作業フォルダーに書き出し、何もダウンロードしません。JupyterLab はトークンを求めません。プラットフォームの入口が、開いている人をすでに知っているからです。ラボの横のターミナルには専用の Python がないので、docker exec jupyter に続けて実行するコマンドを書き、ラボの Python を使います。

  1. コンテナーのページを開く. バーの「つくる」を開き、「コンテナーを実行」を選びます。ページは誰でも開けて、Git ラボと SQL ラボはアカウントなしで起動できます。ほかのラボには無料アカウントが必要です。アカウントを作成してサインインし、「起動」を押します。
  2. ラボを探す. 「サンプルラボ」のカードにすべてのサンプルが並んでいます。ゼロ知識証明:コミットメント、Schnorr、Merkle 証明を探します。
  3. 「起動」を押す. 「起動」はそのまま1回の操作で実行します。「先にファイルを編集」は compose ファイルを開くので、起動する前に変更できます。
  4. 開く. ラボのページのバーに JupyterLab というリンクがあります。押すとブラウザーで JupyterLab が開くので、ファイルエディターで zk.py を読みます。次に「ターミナルを開く」を押し、docker exec jupyter python3 steps/schnorr.py と入力すると、Schnorr の証明が1回確かめられ、ランダムな数を使い回した2つの答えから秘密が求まる様子が表示されます。

生徒に提出してもらうもの

これらのファイルを使って、自分で選んだ問いに答える自分のノートブックを提出してもらいます。たとえば、ごまかしが通る確率を決めた値まで下げるには洞窟のゲームを何回すればよいか、Schnorr の証明者がランダムな数を使い回すと何が起きるか、16個や1024個の項目なら Merkle 証明はどれくらいの長さか、などです。JupyterLab の File、Download でダウンロードします。そこに、分かったことを自分の言葉で1、2文書いてもらいます。自動では採点されません。この文が、理解できたかどうかを示します。さらに力を見たいときは、にせて作った記録がなぜ、プロトコルが何も漏らさないことを示すのかを説明してもらいます。

このラボの基本レッスン

Zero-Knowledge Proof Basics は、このラボで進める小さなレッスンです。生徒は洞窟のゲームを何度も繰り返し、手にコミットして開き、Schnorr プロトコルを実行し、記録をにせて作り、ハッシュで証明を非対話型にし、Merkle 証明で名前が1つリストにあることを確かめます。

無料の個人アカウントでは「ホーム」にある Basics モジュールに入っていて、どの学校もライブラリーの Basics フォルダーからコピーできます。あえて小さくしてあり、ラボで進めるレッスンがどういうものかを先生に見せる役目です。あとはラボが受け持ちます。変更したいときは、自分のモジュールにコピーしてください。大学向けモジュール「ゼロから作るゼロ知識証明」も、同じラボで進めます。

GitHub のコード

compose ファイルには Dockerfile がありません。公開されている既存のイメージをひとつだけ使います。Jupyter Docker Stacks の scipy-notebook を日付つきのタグに固定し、権限のない専用アカウントとメモリ 512 MB で動かします。おもちゃのコードは Python の標準ライブラリだけを使います。イメージのライセンスは BSD-3-Clause で、私たちは再配布していません。起動のたびに、固定の文章から Python ファイルをすべて書き出し、ランダムな選択はすべて固定のシードから作るので、どのコピーも同じ結果を表示し、何もダウンロードされません。限界もあります。群と体がとても小さいので、ここにあるものは何も安全ではありません。また、本物の回路の言語や証明の仕組みはラボで動かないので、回路は普通の Python のゲートで表し、証明の仕組みは言葉で説明します。ラボを止めると何も残らないので、生徒は先にノートブックをダウンロードします。

課題として出す

何を提出するかを課題に書いておきます。

  1. ラボを作る. モジュールで課題を追加し、「コンテナーラボ」のカードを選んでから「GitHub リポジトリ」を選びます。https://github.com/mitsurutech/lab-zk-lab とブランチ main を指定します。compose ファイルは既定の compose.yaml です。変更したい場合は、たとえば別の群や回路の別の主張を使うときは、先にリポジトリをフォークしてください。
  2. 公開して試す. 「公開」すると、確認したコミットに固定されるので、あとでリポジトリを変更しても、すでに出したラボは変わりません。まず自分のコピーを起動してください。
  3. 配布する. ほかの課題と同じように配布します。期限を付けることもでき、課題には何をするか、何を提出するかを書いておきます。
  4. 提出物を採点する. 生徒のコピーを開いて提出された内容を確認し、採点します。足りない場合は理由を書いて差し戻します。

このラボを試す、そして費用

無料の個人アカウントで、このラボの基本レッスンに取り組めます。毎月、ほとんどのレッスンに足りる無料クレジットがあり、カードは要りません。クラスで使う場合、学校は最初の365日間、生徒50人まで無料で、その後は生徒1人あたりの年額です。すべてのラボが含まれ、教職員は無料です。

よくある質問

トークンやパスワードを入力しなくてよいのはなぜですか。
ラボのウェブページには、プラットフォームの入口を通ってしか届きません。入口はあなたが誰かをすでに知っていて、あなたとモジュールを教える先生だけを通します。そのため JupyterLab はトークンなしで起動します。ほかの人が届くマシンでは、この設定で動かさないでください。
ターミナルで docker exec jupyter を使うのはなぜですか。
ラボのターミナルにはいくつかのクライアントが入っていますが、Python はありません。docker exec jupyter は、Python のあるラボのコンテナーの中でコマンドを実行します。JupyterLab にも、File、New、Terminal で開く自分のターミナルがあります。
実際に使えるほど安全ですか。
いいえ。群の元は509個、体は97なので、どの値も1行に収まり、すべてを試せば秘密が見つかります。それを行うスクリプトもあります。実際のシステムは約256ビットの数と、審査済みのライブラリを使います。このラボは考え方を学ぶためのものです。
ラボで Noir や本物の SNARK は動きますか。
いいえ。ラボは起動しても何もダウンロードしない既製のイメージ1つで、回路の言語も証明器も入っていません。回路は小さな体の上の Python のゲートで表します。これは SNARK が証明する主張そのもので、証明の仕組みが何を加えるかはレッスンで説明します。