Japanese Translation:

本テキストは、ゼロ知識証明（ZKP）の新しい暗号通貨以外の応用例を提示し、解そのものを開示することなく、3 色着色のような NP 完全問題に対する解の存在をどのように証明するかを示しています。著者たちは、ゴールドライヒ、ミカリ、ウィジゲルソンによる先駆的な研究（特に原著の第 23 ページにあるプロトコル 4）を土台としており、その中で検証者が約 $m^2$ 回のラウンド（$m = |E|$ はエッジの数）にわたり、証明者を説得するインタラクティブ・プロトコルを概観しています。各ラウンドにおいて、証明者は有効な着色を置換し、非偶数（

secrets.token_hex()

を推奨）を用いてデータを暗号的ハッシュでロックし、ハッシュ化されたコミットメントを検証者に送信します。その後、検証者はランダムにエッジを選択し、その両端ノードの色を要求します。証明者はそれら特定のハッシュの内容のみを開示することで、完全な解の漏洩を防ぎます。検証者は、ハッシュが開示された内容と一致するか、および 2 つの端点の色が異なるかを確認します。エッジ数が 1,000 のグラフにおいて約 10,000 ラウンド経過すると、不正な証明者が承認される確率は 0.0045% に低下します（$(1 - m^{-1})^{m^2}$ で上限付けられています）。ネットワーク型のデモでは、証明者（サーバー）と検証者（クライアント）のプロセスを分離することで、さらなる誤ったデータ漏洩を防ぎます。3 色着色以外にも、このアプローチは数独などの他の NP 完全問題にも拡張でき、制約は同様のインタラクティブ証明を通じて検証可能です。理論的には、多項時間還元によるグラフの 3 色着色への変換が可能であれば、任意の NP 完全問題はインタラクティブ証明を持つことになりますが、特定のインスタンスについては実用的な制限が存在します（例えば、大きな数の因数分解など）。著者たちは暗号通貨への応用はそれほど興味がないと述べていますが、グラフ理論およびネットワーク型計算における基礎概念は、プライバシー保護データの検証において非常に価値があることを強調しています。

グラフ理論を用いたゼロ知識証明（ZKP）の実装と解説

※本稿は暗号通貨に関するものではありません。作者も暗号通貨には無関心です。

先週、Chris 氏からゼロ知識証明（Zero-Knowledge Proof: ZKP）の実装依頼がありましたが、当初興味はありませんでした。しかし、以下のような誘導質問を受けました。

「暗号通貨とは一切関係のないバージョンの ZKP を作ってみる？」
「それが**グラフ理論（Graph Theory）**に絡んできます。」
「実装はたった 30 行で済みます。」

この提案に非常に興味を抱きました。

ゼロ知識証明（ZKP）の概要

ゼロ知識証明の基本概念は、以下の双方の関係にあります。

証明者 (Prover): 課題の解決策を保有している主張を行う側。
検証者 (Verifier): 証明者が解決策を知っていることを、具体的な解決策を公開せずに納得させる側。

典型的な例として、**グラフの 3 色化問題（Graph Coloring Problem）**が挙げられます。

問題設定: 与えられたグラフに対して、隣り合っているすべての頂点同士が異なる色を持つように着色する問題です。
目標: 「最大 3 つの色」を用いて有効な着色方案を見つけることです。
ZKP の目的: 証明者は有効な着色方案を持っている主張をし、検証者にその「存在」だけを確認させつつ、具体的などの頂点がどの色かという情報は漏らさないようにする仕組みです。

プロトコルの仕組みと実装

Chris 氏との議論を経て、Goldreich, Micali, Widgerson による元論文（PDF）の第 23 ページを精読しました。そこには「プロトコル 4」というインタラクティブなセッションが定義されています。

基本構成

共通入力: グラフ $G(V, E)$（頂点集合 $V$、辺集合 $E$）。
反復回数: 総計 $m^2$ 回（$m = |E|$ は辺の数）を独立した乱数を用いて繰り返します。

実行プロセス（1 ラウンドあたり）

以下のステップは「証明者 (P)」と「検証者 (V)」の間で行われます。

(P1) 証明者のアクション: 箱の準備
- 3 つの色をシャッフル（置換 $\pi$）して新しい着色方案を作成します。
- グラフの各頂点 $i$ に対して、対応する**「施錠された箱」**に入れ込みます。
- この際、箱の中身（色）は鍵がなくても見えません。
(V1) 検証者のアクション: 辺の選定
- 検証者はランダムに辺 $e \in E$ を選び、証明者に送信します。
- （直観：「この辺の両端点の色の確認を求めたい」）
(P2) 証明者の反応: 鍵の開示
- 証明者は送られてきた辺 $e=(u, v)$ の両端点に対応する箱の鍵を送ります。
- これにより、検証者は $u$ と $v$ の色が公開されます。
(V2) 検証者の確認: チェック
- 鍵を開けて中身を確認し、以下の条件を満たすか验证します。
  - 色は集合 ${1, 2, 3}$ から選ばれたものか。
  - 両端点の色は互いに異なるか（$\neq$）。
- もし条件に違反すれば証明を却下、さもなければ次のラウンドへ進みます。

終了条件: 検証者が $m^2$ ラウンドすべてを通り抜ければ、証明が完了（受容）されます。

コーディング：1 ループの実装

本質的な理解のため、反復回数の議論前に「単一のループ（Iteration）」を実装・確認します。

データ構造の準備

# 共有データ：グラフのエッジリスト
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 2)]

# 証明者専用：初期着色方案（有効な 3 色化）
coloring = {0: "navy", 1: "darkgreen", 2: "crimson", 3: "navy", 4: "darkgreen"}

# チェックコード（読者のための確認）
# 各エッジの両端色が異なるか、色の総数が 3 以下か確認
assert all(coloring[u] != coloring[v] for u, v in edges)
assert len(set(coloring.values())) <= 3

ステップ P1: 着色の置換と箱への格納

1. 色のシャッフル (Permutation) 色名そのものは意味がないため、既存の色リストをランダムにシャッフルし、新しいマッピングテーブルを作成して適用します。

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()}

# 実行例
permuted_coloring = permute_three_coloring(coloring)

2. 「箱への施錠」を実現する (Hashing) 検証者が中身を見れないようにするため、色をハッシュ化します。Python の標準

hash

関数を使いますが、より堅牢にするなら

hashlib.sha256

を推奨します。

⚠️ 問題点: 同じ色の 2 つの箱には同じハッシュ値が生成されます。これだと構造情報が推定できてしまう可能性があります。

これを回避するため、**Nonce（単回使用番号）**を各色・各節点に追加し、一意性を担保します。

# セキュリティ推奨：secrets モジュールを使用する（random より安全）
import secrets

def nonce():
    return secrets.token_hex(4) 

def box_coloring(coloring):
    # (色, Nonce) のペアを作成
    return {node: (color, nonce()) for node, color in coloring.items()}

def hash_values(boxed_coloring):
    # タプル全体をハッシュ化して箱の ID として使用
    return {k: hash(v) for k, v in boxed_coloring.items()}

この

hashed_coloring

を検証者に送り、ステップ V1 が開始されます。

ステップ V1: 検証者が辺を選定

検証者はグローバルな状態やセッション ID（文脈識別子）を管理する必要があります。

# 検証者専用 (Only verifier)
e = random.choice(edges)
revealed = prover_please_reveal_colors(e)

ステップ P2: 証明者が色と Nonce を開示

証明者は指定された辺の両端点の箱の中身（色 + Nonce）を開示します。

# 証明者専用 (Only prover)
def prover_please_reveal_colors(edge):
    u, v = edge
    return {u: boxed_coloring[u], v: boxed_coloring[v]}

# 例：{3: ('crimson', 'a1b2'), 4: ('navy', 'c3d4')}

疑問: この時点で情報が漏洩していないか？

解決策: 各ラウンドで色はシャッフルされており、開示されるたびに箱を再ハッシュ化（再施錠）するため、検証者は元の色の情報を蓄積できません。

ステップ V2: 検証者の確認処理

検証者は再計算したハッシュ値と受け取った鍵を開けた結果が一致するか確認します。

# 検証者専用 (Only verifier)
for (node, (color, nonce)) in revealed.items():
    assert hashed_coloring[node] == hash((color, nonce)), "Hash mismatch!"
    
# さらに、両端点の色が異なるか確認
assert revealed[u] != revealed[v], "Same color on adjacent nodes!"

確率的な解析

検証者が証明者を信じるには、プロセスを多回反復させる必要があります。論文では、不正を行っているのに気づかずに $m^2$ ラウンドを終える確率は $(1 - m^{-1})^{(m^2)}$ で上界づけられると述べています。これは非常に低い値です。

エッジ数 $m=1000$ の場合のシミュレーション：

m = 1000
for i in range(1, 4600):
    print(f"Round {i}: Probability of failure = {(1 - m**-1)**i}")

4600 ラウンド: 不正の検出確率が 99% に達します（失敗可能性 1%）。
10,000 ラウンド: 失敗可能性は 0.0045% です。
$m^2 = 1,000,000$ ラウンド: 失敗確率は実質ゼロになります。

ネットワーク環境でのデモ構築

単一プロセス内では「証明者」と「検証者」の境界が曖昧になるため、より実践的なデモではサーバー（証明者）とクライアント（検証者）を分離して構成します。

サーバー:
```
hashed_coloring
```
を保持し、ランダムな鍵生成を行う側。
クライアント: 検証ロジックを実行する側。

Chris 氏との協働により、ブラウザで「Run Round」ボタンを押すだけでラウンドを視覚化できるデモが構築されました（API ドキュメント参照）。

他の NP 完全問題への拡張

この手法はグラフの 3 色化に限定されません。他の NP 完全問題にも応用可能です。

サルドク（Sudoku）の例

性質: 「解くのは難しいが、検証するのは容易」。
応用: 81 マスを埋めたことを証明しつつ、具体的な数字配置を漏らさないインタラクティブ証明が可能です。「色」に替えて「行・列・ブロック」を開示するだけです。

多項式時間での帰着（Reduction）

原則として、NP 完全な問題であれば、それをグラフの 3 色化問題などに還元（Polynomial-time Reduction）できれば、同様の ZKP で証明可能です。
例：素因数分解を知っていることの証明なども考えられますが、グラフサイズへの換算には現実的な限界があります。

まとめ

ZKP の面白さ: 「暗号通貨」以外の分野でも、グラフ理論や計算機科学の文脈でインタラクティブな証明は可能です。
実装のコツ:
- 30 行ほどのコードで構成可能なプロトコルが存在します。
- Nonce とハッシュ化により、情報の漏洩を防ぎつつ検証を行います。
- $O(m^2)$ 回の反復によって、確率的に強力な証明が得られます。
結論: この遊びを通じて、インタラクティブ証明の理論と実装を楽しんでいただければ幸いです。

ゼロ知識証明の素早い解説