ゼロ知識証明の簡単な紹介
A quick look at zero-knowledge proofs (bernsteinbear.com)
要約
この記事は、暗号通貨とは無関係なゼロ知識証明(ZKP)の概念を、グラフ理論と短いコード実装を用いて解説しています。証明者と検証者の間で、証明者が問題の解を共有せずに、その解を持っていることを検証者に納得させる仕組みを、グラフの3色塗り分け問題を例に説明しています。
全文翻訳
ゼロ知識証明の簡単な紹介
注: これは暗号資産に関するものではありません。私は暗号資産には関心がありません。
Chrisが先週、ゼロ知識証明を実装しないかと私にメッセージを送ってきました。当初は興味がありませんでしたが、彼はこう言いました。
暗号資産とは全く関係のないバージョンがあると言ったらどうしますか?グラフ理論が関わると言ったらどうしますか?30行で実装できるものがあると言ったらどうしますか?
それは興味深い話でした。
ゼロ知識証明(ZKP)のアイデアは、証明者(prover)と検証者(verifier)の2つの当事者がいるというものです。証明者は、一般的にNP完全問題である問題の解を持っていると主張します。証明者は、実際の問題の解を共有することなく、検証者にそのことを納得させることができます。
典型的な例は、グラフの3彩色問題です。つまり、証明者は、与えられた(共有された)グラフに対して、有効な3彩色を持っていると主張します。しかし、実際の色割り当てを明らかにすることなく、検証者にそれを納得させたいのです。
簡単に復習すると、グラフ彩色とは、与えられたグラフに対して、隣接するノードが同じ色にならないように各ノードに色を割り当てる問題です。3彩色とは、最大3色で彩色することです。
どうやってこれを実現するのでしょうか?様々なブログ記事や見た目の派手なデモンストレーションは興味深かったのですが、あまり理解を深める助けにはなりませんでした。
Chrisと私はしばらくの間堂々巡りを続けましたが、Goldreich、Micali、Widgersonによるオリジナルの論文の一つ(PDF)を見てみることにしました。私たちは主に23ページ(PDFでは713ページと表示)だけを読みましたが、それで十分でした。
論文のプロトコル
論文のプロトコル4は、証明者(P、番号付きステップ)と検証者(V、番号付きステップ)の間で行われるインタラクティブな3彩色証明セッションを記述しており、ここに再現します。
共通入力 グラフ
G(V, E)(n = |V|,m = |E|)。以下の4つのステップは
m²回実行され、毎回独立したコイン投げを使用します。(P1) 証明者は、
φによって誘導される3つの独立集合への色の割り当てをランダムに選択し、この3彩色でグラフを彩色し、対応する頂点の番号が付けられたn個のロックされた箱にこれらの色を入れます。より具体的には、証明者は置換π ∈R S₃を選択し、箱i(∀i ∈ V)にπ(φ(i))を配置し、すべての箱をロックして(キーなしで)検証者に送信します。(V1) 検証者は、エッジ
e ∈R Eをランダムに選択し、証明者に送信します。(直感的には、検証者はe ∈ Eの端点の色の検査を要求します。)(P2) もし
e = (u, v) ∈ Eならば、証明者は箱uとvのキーを検証者に送信することによって、uとvの色を明らかにします。そうでなければ、証明者は何も行いません。(V2) 検証者は、受信したキーを使用して箱
uとvを開き、それらが{1, 2, 3}の異なる2つの要素を含んでいるかどうかを確認します。キーが箱と一致しない場合、または内容が条件に違反する場合は、検証者は拒否して停止します。そうでなければ、検証者は次のイテレーションに進みます。検証者がすべての
m²イテレーションを完了した場合、それは受け入れます。
イテレーションの回数については後で戻ります。今のところ、1回のイテレーションだけを試してみましょう。各ステップで、コードに「証明者のみ」または「検証者のみ」と注釈を付け、誰がどのデータを見ることができるかを明確にします。
1回のイテレーション
まず、グラフを持つことが何を意味するのかをスケッチすることから始めます。上記の例のGraphvizグラフでは、以下のエッジリストデータ構造があります。
# 証明者と検証者の間で共有
edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (0, 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
それでは、論文のステップを一つずつ実行し、各ステップを補足するコードを記述していきます。
ヒントとコツ
ブログ記事と並行して構築している場合、ランダムシードを random.seed(0) に設定することをお勧めします。これにより、プログラムの実行間でランダム性が変化しなくなります。同様の安定性の理由から、hash を使用している場合は、環境変数 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"}
次に、色を「ロックされた箱」に入れる必要があります。箱を比喩的にロックする一つの方法は、一方向関数を適用することです。例えば、ハッシュ関数です。各色をハッシュしてから、ハッシュ値のみを検証者に渡せば、検証者はそれを開くことができません。
この例では簡潔さのために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つの箱は、同じハッシュ値を持つことになります。検証者は彩色を知ってしまうでしょう。たとえ実際の色が隠されていても、私たちがゼロ知識を放棄して与えたいのは、彩色の構造なのです。
これを回避するために、「ナンス」(nonce)と呼ばれるものを各ノードとその彩色に追加できます。つまり、各ノードにはランダムなデータがハッシュに詰め込まれるため、異なるノードの「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
検証者はグラフを知っていますが(色ではなく)、検査する任意の辺を選択できます。検証者は、選択した任意の辺が3彩色条件を満たしていることを確認したいのです。検証者は、任意の辺 e の開示を要求します。
# 検証者のみ
e = random.choice(edges)
revealed = prover_please_reveal_colors(e)
これは、暗黙的にグローバル状態(証明者がどの「セッション」が検証者とアクティブであるかを知っていること)に依存しています。複数の検証者や同時セッションなどがある場合、通信で何らかのコンテキスト識別子をスレッドで渡す必要があるかもしれません。
ステップ P2
この要求を受け取った証明者は、エッジ内の各ノードの色とナンスを送信します。
# 証明者のみ
def prover_please_reveal_colors(edge):
u, v = edge
return {u: boxed_coloring[u], v: boxed_coloring[v]}
# 例:
# {3: ('crimson', 51), 4: ('navy', 38)}
この時点で、彩色に関する情報が漏洩しているため、疑わしく思うかもしれません。
1つのエッジの色を明らかにすることは問題ないことに注意してください。なぜなら、1)各ラウンドで色が一度シャッフルされ、2)エッジを開示するたびに(これも各ラウンドで)ボックスロックプロトコルを適用するため、検証者はイテレーション間で色に関する情報を蓄積しないからです。
ステップ V2
検証者は、色+ナンスがステップP1で各ノードに与えられたハッシュ値にハッシュされることを確認できます。これにより、証明者がラウンド中に色を変更していないことが保証されます。これは、検証者と証明者が同じハッシュ関数(およびhashを使用する場合は同じハッシュシード)を使用していることに依存します。
検証者はまた、エッジの両端の2つの色の値が、公開で合意された色のセットのメンバーであることを確認する必要があります。そうでない場合、証明者はすべてのノードを異なる色で彩色する可能性があります。
# 検証者のみ
for (node, (color, nonce)) in revealed.items():
assert hashed_coloring[node] == hash((color, nonce)), f"Hash mismatch!"
assert color in all_colors, f"Invalid color {color}!"
その後、検証者は2つの色の値が異なることを検査できます。これにより、証明者は検証者がどのエッジを検査したいかを知る方法がなかったため、グラフが適切に3彩色されていることについて、わずかな信頼性(1つのエッジについて何かを知っているため 1/|E|)が得られます。
これらの条件のいずれかがチェックアウトしない場合、検証者は拒否します。
確率
検証者が3彩色について証明者を信頼するには、少なくとも数回のラウンドを実行する必要があります。
論文はさらに、「検証者が受け入れる(つまり、検出なしに m² ラウンドすべてを完了する)確率は (1 - m⁻¹)^(m²) で上から抑えられる」と主張しています(ここで m = |E|)。これはかなり良いです。大きなグラフ(例えば1000エッジ)の場合、これはかなり速く減少します。
m = 1000
for i in range(1, 4600):
print("(1 - m⁻¹)^round = ", (1 - m**-1)**i)
4600ラウンドでは、「不正行為」の可能性は1%です。10,000ラウンドでは、0.0045%の「不正行為」の可能性があります。 m² = 1,000,000 ラウンドでは、これは非常に低いです。
ネットワーク化されたデモ
「証明者」と「検証者」を示すコメント付きの単一プロセスで実行されるPythonコードを書くことは、あまり満足のいくものではありません。データが誤って漏洩する可能性を少しも排除しません。証明者と検証者の間にプロセスバリアやネットワークバリアのようなものがあれば、もっと満足のいくものになるでしょう。
このため、Chrisと私はサーバー(証明者)とクライアント(検証者)のデモを用意しました。「ラウンドを実行」をクリックすると、1ラウンド実行され(順列化された色が表示されます)、ドキュメントページにアクセスしてAPIドキュメントを確認し、自分でクライアントを構築できます!
(このメッセージのすぐ下にグラフが表示されない場合は、サーバーが起動するまでしばらくお待ちください。)
他のNP完全問題のエンコーディング
この時点で、グラフの有効な3彩色を持っていることを、3彩色に関するいかなる情報も学習することなく検証するために、ゼロ知識インタラクティブ証明を使用する方法を示しました。それで、どうしたのでしょう?他に証明できることはないのでしょうか?3彩色インタラクティブ証明は、実用的な応用がない単なるこじつけのパーティートリックなのでしょうか?
さて…
Sudoku
Sudokuパズルは、解くのが難しく、検証するのが簡単な問題のもう一つの例です。81マスを埋めて、すべての行、列、ボックスが1から9の数字を満たす制約を満たすことはアルゴリズム的に困難ですが、検証者は非常に迅速です。
Sudokuを解いたことを証明したいが、解決策に関する情報を一切渡したくないとしましょう。3彩色と非常に類似したインタラクティブ証明を実行できます!色をシャッフルする代わりに、数字をシャッフルします。エッジを明らかにする代わりに、行、列、ボックスを明らかにします。
次にバスに乗っているときに隣の人がSudokuの解決策を見せてほしいと頼んできたら、まず90,000ステップの簡単な手順を踏んでもらうように頼んでください!
還元(Reduction)
難しい問題があり、その解を計算したが、インタラクティブ証明を実行するための明白なアルゴリズムを手元に持っていないとしましょう。上記の論文の著者のおかげで、問題がNP完全であれば、それに対するインタラクティブ証明があることを知っています!
多項式時間還元(polynomial time reduction)の力を使用します。私たちは(何らかの方法で)問題をグラフとその3彩色に変換し、その後、上記のステップとコードに従います!「何らかの方法で」が難しい部分ですが、異なるNP完全問題間の変換に関する多くの研究が存在します。
例えば、非常に大きな合成数の素因数を知っていることのゼロ知識証明を作成したいかもしれません。残念ながら、2桁の数でさえグラフは数千ノードになるため、3彩色への還元は実際には限界があり、3彩色への還元よりも洗練された証明技術を使用する方が良いでしょう。
まとめ
少し調査を行った結果、ゼロ知識証明の最も一般的な実世界でのユースケース(年齢確認、暗号資産など)は、私たちにとってあまり興味深いものではないと判断しました。しかし、グラフ、計算理論、ネットワークコンピューティングは楽しめました。皆さんもインタラクティブ証明を楽しんでいただけたなら幸いです。