ゼロ知識証明の簡単な紹介

home blog microblog favorites pl resources bread recipes rss A quick look at zero-knowledge proofs August 7, 2026 共同執筆者 Chris Gregory と共に！注：これは暗号通貨に関するものではありません。私は暗号通貨には関心がありません。Chrisが数週間前に、ゼロ知識証明を実装しないかと私にメッセージを送ってきました。最初は興味がありませんでしたが、彼はこう言いました。「もし、暗号通貨とは全く関係のないバージョンがあると言ったらどうする？グラフ理論が関わるものだと言ったらどうする？30行の実装があると言ったらどうする？」それが興味を引きました。 ゼロ知識証明（ZKP）の考え方は、証明者と検証者の2つの当事者がいるということです。証明者は、問題（一般的にはNP完全問題）の解を持っていると主張します。証明者は、実際の解を共有することなく、その解を持っていることを検証者に納得させることができます。典型的な例は、グラフの3色塗り分けです。つまり、証明者は、与えられた（共有された）グラフに対して、有効な3色塗り分けを持っていると主張します。実際の色の割り当てを明らかにすることなく、それを検証者に納得させたいのです。 簡単に復習すると、グラフの塗り分けとは、与えられたグラフに対して、隣接するノードが同じ色にならないように各ノードに色を割り当てる方法を見つける問題です。3色塗り分けは、最大3色で塗り分けることです。 %0 0 0 1 1 0--1 2 2 0--2 1--2 3 3 2--3 4 4 3--4 4--0 %0 0 0 1 1 0--1 2 2 0--2 1--2 3 3 2--3 4 4 3--4 4--0 どうすればこれを実現できるでしょうか？様々なブログ記事や派手なデモンストレーションは興味深かったのですが、あまり理解を助けませんでした。Chrisと私はしばらくの間堂々巡りを続けましたが、Goldreich、Micali、Widgersonによるオリジナルの論文（PDF）の1つを見ることにしました。私たちはPDFの23ページ（PDF内では713ページと表示）だけを読みましたが、それで十分でした。 論文のプロトコル 論文のプロトコル4は、証明者（P、番号付きステップ）と検証者（V、番号付きステップ）の間でのインタラクティブな3色塗り分け証明セッションを記述しており、ここに再現します。 共通入力：グラフ G(V, E) （n = |V|, m = |E|）。以下の4つのステップは、それぞれ独立したコイン投げを使用して、m²回実行されます。 (P1) 証明者は、φによって誘導される3つの独立集合に3つの色をランダムに割り当て、この3色塗り分けでグラフを色付けし、これらの色を対応する頂点の番号が付けられたn個のロックされた箱に入れます。より具体的には、証明者は置換 π ∈R S₃ を選択し、各 i ∈ V に対して π(φ(i)) を i というラベルの付いた箱に入れ、すべての箱をロックして（キーなしで）検証者に送ります。 (V1) 検証者は、ランダムにエッジ e ∈R E を選択し、証明者に送ります。（直感的には、検証者は e ∈ E の端点の色を調べたいのです。） (P2) e = (u, v) ∈ E の場合、証明者は箱 u と v のキーを検証者に送ることで、u と v の色を明らかにします。それ以外の場合、証明者は何も行いません。 (V2) 検証者は、受け取ったキーを使用して箱 u と v を開き、それらが {1, 2, 3} の異なる要素を含んでいるかどうかを確認します。キーが箱と一致しない場合、または内容が条件に違反する場合、検証者は拒否して停止します。それ以外の場合、検証者は次のイテレーションに進みます。検証者がすべての m² イテレーションを完了した場合、検証者は受け入れます。 イテレーションの回数については後で触れます。まずは1回のイテレーションを試してみましょう。各ステップで、コードに「Only prover」または「Only verifier」と注釈を付け、誰がどのデータを見ることができるかを明確にします。 1回のイテレーション まず、グラフを持つことが何を意味するのかをスケッチすることから始めます。上記の例のグラフvizグラフでは、次のエッジリストデータ構造があります。 # 証明者、検証者間で共有 edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 2)] リスト内の各タプルは、2つの番号付きノード間の接続を表します。派手なものです。無向グラフなので、(0, 1) は (1, 0) と同じ意味なので、両方を含める必要はありません。色を付けることもできます。 # 証明者のみ coloring = {0: "navy", 1: "darkgreen", 2: "crimson", 3: "navy", 4: "darkgreen"} 各キーはノード番号で、各値は色です。グラフの3色塗り分けを見つけるのは遅いですが、検証するのは速いです—エッジの数に対して線形です。有効なサンプル塗り分けであることを検証しましょう。 # 読者向け # 各エッジをチェックして、同じノードに同じ色がないことを確認します assert all(coloring[u] != coloring[v] for u, v in edges) # 使用されている色の総数が3色であることを確認します assert len(set(coloring.values())) <= 3 論文のステップを1つずつ実行し、各ステップに付随するコードを記述していきます。 ヒントとコツ ブログ記事と並行して構築している場合は、random.seed(0) を使用することをお勧めします。これにより、プログラムの実行間でランダム性が変化しなくなります。同様の安定性の理由から、環境変数 PYTHONHASHSEED を 0 に設定することも推奨します。 ステップ P1 最初に行うべきことは、塗り分けを置換することです。つまり、色値を入れ替えますが、3色塗り分けのプロパティは維持します。幸いなことに、これは思っているよりも簡単です。色の名前は3色塗り分けにとって無意味です。エッジに沿って異なるだけであればよいのです。したがって、古い名前と新しい名前の間で全単射（Aが1つのBに対応し、Bは1つのAから来た）のマッピングを行うと、これは保持されます。色をシャッフルし、それらを並べ、テーブルを作成し、それを使用して新しい塗り分けを作成する関数を思いつきました。 import random # 証明者のみ def permute_three_coloring(coloring): all_colors = list(set(coloring.values())) new_colors = random.sample(all_colors, len(all_colors)) permutation = {old: new for old, new in zip(all_colors, new_colors)} return {node: permutation[color] for node, color in coloring.items()} # 例： # {0: "crimson", 1: "navy", 2: "darkgreen", 3: "crimson", 4: "navy"} 次に、色を「ロックされた箱」に入れる必要があります。箱を文字通りロックする1つの方法は、それに一方向関数を適用することです。例えば、ハッシュ関数です。各色をハッシュし、ハッシュ値のみを検証者に渡せば、検証者はそれらを開くことができません。この例では簡潔さのためにPython標準ライブラリのハッシュ関数を使用していますが、hashlib.sha256のような暗号学的ハッシュ関数を使用する方が良いかもしれません。 # 証明者のみ。間違い！ def hash_coloring_wrong(coloring): return {node: hash(color) for node, color in coloring.items()} # 例： # {0: -6789624683659967261, 1: 7846608853949633950, 2: 6009240650600289446, # 3: -6789624683659967261, 4: 7846608853949633950} これらのロックされた箱を検証者に渡すだけでは問題があります。同じ色でロックされた2つの箱は同じハッシュ値を持つことになります。検証者は塗り分けを知ってしまうでしょう。たとえ正確な色が隠されていても、私たちがゼロ知識を放棄したいのは、塗り分けの構造なのです。 これを回避するために、各ノードとその塗り分けに「ナンス」と呼ばれるものを追加できます。つまり、各ノードにランダムなデータがハッシュに詰め込まれ、異なるノードの「darkgreen」ハッシュ値が異なって見えるようになります。 # 証明者のみ def nonce(): return random.randrange(100) def box_coloring(coloring): return {node: (color, nonce()) for (node, color) in coloring.items()} def hash_values(coloring): return {k: hash(v) for (k, v) in coloring.items()} permuted_coloring = permute_three_coloring(coloring) # 例： # {0: "crimson", 1: "navy", 2: "darkgreen", 3: "crimson", 4: "navy"} boxed_coloring = box_coloring(permuted_coloring) # 例： # {0: ("crimson", 33), 1: ("navy", 65), 2: ("darkgreen", 62), # 3: ("crimson", 51), 4: ("navy", 38)} hashed_coloring = hash_values(boxed_coloring) # 例： # {0: -2275004828450249492, 1: 2227921633151400991, 2: -5024343381376265886, # 3: -5381005702768533635, 4: 1164729608819214729} 繰り返しになりますが、ナンスには標準ライブラリの乱数生成器を使用しない方が良いでしょう。secretsモジュール（Python 3.6+）のsecrets.token_hex()のようなものを検討すべきです。hmacモジュールを検討することさえできるかもしれません。 最後に、hashed_coloringを検証者に送信し、ステップV1を開始できます。 ステップ V1 検証者はグラフを知っています（しかし、その色までは知りません）。