ゼロ知識証明：基礎入門

はじめに

ゼロ知識証明は、暗号学者が生み出した最も強力なツールの一つです。しかし、一般には十分に理解されていません。本記事では、この状況を改善するため、ゼロ知識証明を第一原理から包括的に解説します。ゼロ知識証明を支える理論、数学、暗号技術を取り上げ、Solanaにおける最新の進展、すなわちZK Compressionと相互運用性の未来を誰でも理解できるようにします。

本記事では、Solanaのプログラミングモデルと、ブロックチェーンシステムに固有の暗号プリミティブ（ハッシュ関数、ハッシュポインター、Merkle tree、並行Merkle tree）に関する知識を前提としています。これらの概念に馴染みがない場合は、まず次の過去記事を読むことをおすすめします。

• 暗号ツール入門 — ハッシュ関数とMerkle treeの解説
• Solanaプログラミングモデル：Solana開発入門

本記事はモジュール性を意識して構成されています。これらのトピックが初めての方には、各セクションとサブセクションを順番に読むことをおすすめします。一方、特定のトピックに詳しい場合や、特定の内容だけを学びたい場合は、該当するセクションから直接読み始めても問題ありません。

また、本記事はゼロ知識証明を扱う全2回シリーズの第1回です。ゼロ知識証明：Solanaでの応用に進む前に、まず本記事を読むことを強くおすすめします。

ゼロ知識証明を支える理論

1989年、MITの研究者であるShafi Goldwasser、Silvio Micali（Algorandの創設者）、Charles Rackoffは、The Knowledge Complexity of Interactive Proof Systemsを発表しました。彼らは、ある当事者（証明者）が別の当事者（検証者）とメッセージを交換し、ある数学的命題が真であると納得させるシステムを研究していました。そして初めて、「証明者と検証者の双方が互いを信用していなかったらどうなるか」と問いかけました。ここでの懸念は、メッセージのやり取りを通じて、命題が真であるという事実以外に、検証者がどれほどの情報を得るかという点です。たとえば証明者は、複雑なパズルの解答そのものを明かさずに、解答を知っていると検証者に納得させたいかもしれません。

そもそも、どのような問題を解こうとしているのでしょうか？

グラフ3彩色

グラフ3彩色は、コンピューターサイエンスとグラフ理論における古典的な問題です。グラフの頂点を3色で塗り、隣接する頂点が同じ色にならないようにします。頂点が3つのグラフなら簡単です。しかし、頂点数が増えるほど難易度は急速に高まります。

現実世界での応用例として、大学の時間割作成があります。大規模な大学では、どの学生も授業が重複しないように時間割を作る必要があります。各授業をグラフの頂点として表し、授業間で共通する学生がいる場合に辺を引きます。これにより、共通の学生がいる2つの授業が同じ時間に設定されることを防げます。さらに、教室の収容人数、教授が希望する時間帯、授業を週全体に均等に分散させることなどの制約もあります。したがって、隣接する2つの授業が同じ時間帯にならないよう、各授業に時間帯と教室を割り当てる必要があります。これはグラフ3彩色で実現できます。

ここで、最終的な時間割を外部監査法人が検証しなければならないとします。特定のプライバシー規制により、大学は学生の詳細な履修情報を監査担当者と共有できません。その代わりに大学は、どの学生がどの授業を履修しているかを明かさずに、最終的な時間割が必要な制約を満たしていることを証明しなければなりません。 

そのために大学は、各頂点が授業を表すグラフを作成します。対応する授業に共通の学生が1人以上いる場合、2つの頂点間に辺を引きます。大学は、隣接する2つの授業が同時に設定されないよう、各授業に時間帯を割り当てます。そして暗号コミットメント方式を使い、完成した時間割にコミットします。具体的には、各授業に割り当てられた時間帯の暗号学的ハッシュを作成し、時間帯そのものを明かさずに、そのハッシュを検証者と共有します。次に外部監査法人は、隣接する授業のペアをランダムに選び、割り当てられた時間帯についてチャレンジを行います。大学は、選ばれた隣接授業ペアについてコミット済みの時間帯を開示し、元のコミットメント（ハッシュ）を提示します。これにより外部監査法人は、開示された値を検証できます。外部監査法人が授業の重複がないと納得するまで、チャレンジ、開示、検証という最後の数ステップを繰り返します。これらの手順がリアルタイムで進む様子を確認するには、MITの対話型ゼロ知識3彩色デモを強くおすすめします。

大学は、正しい時間割を知っていることを外部監査法人に証明したいのです。つまり、何かを知っていることを別の当事者に証明したいのです。この問題の優れた点は、NP完全であることです。

NP完全

計算複雑性理論では、次の条件を満たす問題をNP完全と呼びます。

• 問題へのどの入力に対しても、出力は「はい」または「いいえ」のいずれかです
• 答えが「はい」の場合、短い解によってそれを示せます
• 各解が正しいかをすばやく検証でき、総当たりアルゴリズムですべての解候補を試すことで解を見つけられます

NP完全問題が重要なのは、NPクラス内で最も難しい問題を表すためです（つまり、推測した解は多項式時間で簡単に検証できる一方、解を見つけるのは難しいという、非常に難解なパズルの集まりです）。これらの問題は、普遍的にシミュレーションできる点で注目されます。つまり、1つのNP完全問題を高速に解ければ、任意のNP問題をNP完全問題に還元または変換し、その解を多項式時間で見つけられます。NP完全問題の解を検証することも容易です。 

したがって、ゼロ知識証明によって効率的に証明できる問題のクラス全体が存在します。たとえば、次のとおりです。

• 巡回セールスマン問題 — 都市の一覧と各都市間の距離が与えられたとき、各都市を1回ずつ訪問して出発都市に戻る最短経路を求めます。この問題は、物流、経路計画、製造、サプライチェーン管理で幅広く応用されています
• ナップサック問題 — アイテムの集合が与えられたとき、合計重量が所定の上限以下になり、合計価値が最大になるよう、コレクションに含める各アイテムの個数を決定します。金融やリソース配分でよく見られる問題です
• ジョブスケジューリング — 所要時間と期限が定められたジョブの集合が与えられたとき、遅延ジョブによるペナルティの合計が最小になるよう、1台のマシン上でスケジュールします。コンピューティング、製造、プロジェクト管理に幅広い用途があります

さらに、Cook-Levinの定理は、充足可能性問題がNP完全であると述べています。つまり、変数を真または偽の値で置き換え、最終的に真と評価できる任意の問題は、NP完全問題に変換できます。これは、一連の真偽問題に還元できるあらゆる問題を、ゼロ知識証明によって効率的に証明できることを意味します。

ゼロ知識証明の性質

NP完全問題の複雑さと重要性を考えると、このクラスの問題の解を効率的かつ安全に証明することが不可欠です。ゼロ知識証明を使えば、関連情報のプライバシーを損なわずに証明できます。Goldwasser、Micali、Rackoffは、すべてのゼロ知識証明が次の性質を満たす必要があると提唱しました。

• 完全性 — 証明者が正直であれば、最終的に検証者を納得させられます
• 健全性 — 不正な証明者が、偽の命題を検証者に信じ込ませることはできません
• ゼロ知識性 — 証明者と検証者のやり取りから明らかになるのは、命題が真かどうかだけであり、それ以外の情報は一切明らかになりません

ゼロ知識証明の堅牢な性質を活用すれば、さまざまな状況で、特定の事実や情報を知っていることを、プライバシーを保ちつつ正確に証明できます。後のセクションでは、ブロックチェーンのように高いセキュリティと効率性が求められるアプリケーションで、これがなぜ非常に有用なのかを解説します。

対話型と非対話型

ゼロ知識証明は通常、次の3段階の構造を取ります。

• 証明者が計算の解（witness）を生成し、そのwitnessへの回答に対するコミットメントを送ります
• 検証者がランダムに生成したチャレンジ値を返します
• 証明者がコミットメントとチャレンジに基づいて最終的な証明を計算します

この構造は本質的に対話型です。証明者は何かを知っていると主張し、証明者が検証者をだましている可能性が無視できるほど小さくなるまで、検証者が繰り返しチャレンジします。完成した証明を生成する前に、証明者が1回または複数回の応答を受け取る必要があるため、ほとんどのアプリケーションには適していません。この構成には、本質的に次の課題があります。

• 検証者が証明者と共謀し、偽の証明を作れる可能性があります
• 検証者が偽の証明を作れる可能性があります
• 検証者は秘密の値をどこかに保存する必要があり、漏洩や攻撃のリスクがあります

Fiat-Shamirヒューリスティックは、対話型の知識証明からデジタル署名を作成する手法です。これにより、基礎となる情報を明かさずに、ある事実を公開で証明できます。その考え方は、検証者がランダムなチャレンジ値を証明者に送る代わりに、証明者自身が優れた暗号学的ハッシュ関数などのランダム関数を使ってデジタル署名を計算するというものです。つまり、検証者が計算の500か所を確認してすべて正しいかを調べる代わりに、証明者が計算のMerkle rootを算出し、そのMerkle rootを使って500個のインデックスを疑似ランダムに選び、対応する500本のMerkle branchのデータを提供します。重要なのは、データにコミットするまで、証明者にはどのbranchを開示すべきか分からないことです。

鋭い読者は、計算の抜き取り検査にランダムサンプリングを適用することの致命的な欠陥に気づくかもしれません。計算は本質的に壊れやすいものです。悪意ある証明者が計算の途中で1ビットだけ反転させても、検証者はそれを発見できない可能性があります。計算の各部分を個別に確認せずに、検証者が計算のすべてを確認するにはどうすればよいでしょうか？ 答えは多項式です。

ただし、多項式について説明する前に、かなりの数学を理解する必要があります。

ゼロ知識証明を支える数学

以下の数学分野を網羅的に紹介することが目的ではありません。各セクションだけでも、それぞれ1本の記事にできるほどの内容があります。ここでは、ゼロ知識証明を支える数学的基礎と、その大まかな仕組みを理解し始められるよう、簡潔に紹介します。

また、本記事では正しい数学的表記にも触れます。たとえば、次の集合論のサブセクションでは、∈、∉、⊆という記号を紹介します。結局のところ、これらの記号はすべて、別の何かを表すプレースホルダーです。ゼロ知識証明は初心者向けのトピックではありません。そのため、このテーマを扱う記事の大半は初心者向けではありません。これらの記号の意味まで掘り下げることはなく、 読者が表記を理解していることを前提としています。ゼロ知識証明をより深く学びたい方が必要以上に難しく感じないよう、今の段階でこの表記を紹介することが重要です。表記に惑わされないようにしてください。読み進めていけば、いつかこれらの記号を見たとき、単なるギリシャ文字ではなく、その背後にある概念が見えるようになります。

集合論

集合論は、対象の集まりを研究する数学の一分野です。集合とは、異なる対象の集まりです。これらの異なる対象を、集合の要素またはメンバーと呼びます。たとえば、果物の集まりを考えてみましょう。

集合の表記法では、要素の集まりを波括弧で囲んで集合を表します。これにより、apple、orange、pear、bananaは集合に含まれ、「potato」のようなものは含まれないと分かります。記号∈は集合への所属を示し、「〜の要素である」と読みます。同様に、∉はある要素が指定された集合のメンバーではないことを表します。したがって、次のように表せます。

これは「appleは集合Fruitの要素であり、potatoは集合Fruitの要素ではない」と読みます。

部分集合

別の集合から構成される集合もあります。部分集合とは、別の集合に含まれる要素だけで構成される集合です。たとえば、次の集合があるとします。

集合Citrusは、より大きな集合AllFruitsの部分集合だと言えます。また、先ほどの集合Fruitも、より大きな集合AllFruitの部分集合だと言えます。集合の表記法では、次のように書きます。

なぜ重要なのでしょうか？

集合論は、範囲と制約の概念を理解するうえで不可欠です。次の数論とモジュラー算術のセクションでは、数が特定の範囲内にあるという考え方を見ていきます。たとえば、暗号鍵が取り得る値の集合は次のようになります。

ここで、Kは取り得るすべての鍵の範囲を定義します。この集合に特定の制約を適用し、一部の値だけを有効にするゼロ知識証明を構築できます。たとえば、鍵は1から5までの数でなければならないと指定できます。 

このように集合論は、暗号プロトコルで取り得る入力、出力、状態の集合を定義し、分析するための基礎的な言語、ツール、表記法を提供します。ゼロ知識証明では、要素そのものを明かさずに、その要素が特定の集合や範囲に属することを証明する必要がよくあります。

Khan Academyの基本的な集合表記に関する良質な練習問題もおすすめです。

数論

数論は、整数と算術関数を研究する数学の一分野です。整数は、正数、負数、ゼロを含む、分数ではない数の集合として定義できます。整数の集合をより形式的に定義すると、次のようになります。

ここで、ℤは整数の集合を表し、省略記号は整数が負の無限大から正の無限大まで続くことを示します。たとえば、12は整数であり、-1978649832794275も整数です。

有理数

有理数は、分母（一般的な分数で線の下にある数、つまり除数）がゼロではない分数として表せる数です。たとえば、$(\frac{1}{2}), 74, (\frac{2}{3})$はすべて有理数です。有理数は、pを分子、qを分母とし、qが0ではない分数pqとして表せる数の集合として、より形式的に定義できます。記号ℚは有理数を表します。集合の表記法では、次のように書きます。‍

‍一見すると難しそうですが、これは直前の文で説明した内容そのものです。この複雑に見える数学表記は、「Qは、pとqが整数で、qがゼロではない、pをqで割ったすべての分数の集合である」と読みます。 

実数

実数には、有理数と無理数の両方が含まれます。無理数とは、単純な分数として表せず、小数部分が循環せず、終わることもない数です。たとえば、円周率（π）と$\sqrt{2}$（1.4.1421…）は無理数です。ここでは集合の表記法を省略しますが、実数は記号ℝで表すことを覚えておいてください。

なぜ重要なのでしょうか？

数論は、特定の数の集合（有理数など）を研究するため、集合論と深く結びついています。こうした集合は、数学や暗号の問題で範囲や制約を定義する基礎としてよく使われます。 

数論と集合論がどのようにつながっているかも分かります。たとえば、すべての整数の集合ℤは有理数ℚの部分集合だと言えます。これは、上の集合表記による実数の定義で、分子と分母が整数であると述べていることから明らかです。

モジュラー算術

モジュラー算術は時計算とも呼ばれ、法と呼ばれる特定の値に達した後、数が「一周して戻る」整数の演算体系です。無限の数の集合を扱う代わりに、最初の正の数n個を使って計算するという考え方です。

時計

1から12までの数字があるアナログ時計を考えてみましょう（今の時代、デジタルではなく針のある時計だと説明しなければならないのは残念です）。11時の2時間後を知りたい場合、13時にはなりません。一周して1時になります。これは$11 + 2 \equiv 1 \pmod{12}$と表せます。正しい数学的表現は$13 \bmod 12 = 1$です。プログラマーには、$13 \% 12 = 1$という形式の剰余演算がお馴染みでしょう。

剰余演算

n mod kと書く場合、nをkで割った余りを求めることを意味します。これは剰余演算と呼ばれます。たとえば、次のとおりです。

• 25 mod 3は、25を3で割ることを意味します。$25 = 8 \times 3 + 1$なので、余りは1です
• 15 mod 4は、15を4で割ることを意味します。$15 = 3 \times 4 + 3$なので、余りは3です

モジュラー算術では、余りは常に非負です。

なぜ重要なのでしょうか？

モジュラー算術を理解することは極めて重要です。制約下での数の振る舞いを理解でき、暗号技術に役立つためです。モジュラー算術は多くの暗号アルゴリズムの基礎であり、コンピューターサイエンス、工学、データの安全な取り扱いと暗号化が必要なあらゆる分野で使われています。

計算x + y = zを考えてみましょう。素数p = 17で定義される有限体を扱うとします（これについてはすぐ後で説明します。今は、17で一周する0から16までのすべての整数の集合だと考えてください）。この体での計算は、(x + y) mod p = zとなります。x = 12、y = 15の場合、計算は次のようになります。‍

ここでモジュラー算術を使うと、素数pで定義される扱いやすい値の範囲内で計算できます。 コンピューターやプロセッサーの容量は有限であるため、これは特に重要です。通常はu32やu64のような固定サイズ整数を扱います。モジュラー算術により、値がこの範囲内に収まることを保証できます。さらに、素数を使うことで複雑性が一段加わります。セキュリティを強化し、特定の数学的性質をより予測可能で信頼できるものにするため、暗号学の観点から不可欠です。

たとえば、zk-SNARKsでは、計算値を特定の扱いやすい範囲内に保つためにモジュラー算術が使われます。また、所定の数の集合上で算術回路を作成するためにも使われます。これにより、効率的に検証できる形で計算を表現できます。ここで証明者は、x、y、zの値を明かさずに、この計算を実行したことを証明する必要があります。

モジュラー算術の問題を実際に解く経験を積むには、Art of Problem Solvingの問題集とJoseph Zollerのモジュラー算術演習を強くおすすめします。 

群論

群論は、群と呼ばれる代数構造を研究する数学の一分野です。群とは、群の公理と呼ばれる次の条件を満たす演算と要素の集合です。

• 閉性 — どの算術計算の結果も、その集合内の別の要素になります
• 結合性 — 3つ以上の要素に同じ演算を行う場合、要素をどのようにまとめても結果は同じです
• 単位元 — ほかの任意の要素と演算しても、その要素の値が変わらない要素が存在します
• 逆元 — ほかの要素と演算した結果が単位元になる要素が存在します

形式的には、次のように定義されます。

• 閉性 — aとbが群のメンバーなら、演算の結果（多くの場合、$a \times b$、$ab$、$a \circ b$、または$ab$と表します）も群のメンバーです。形式的には、$\forall a, b \in G \mid a \circ b \in G$と書けます。これは「集合G内の要素aとbのすべての値について、aとbの演算結果はGに含まれる」と読めます
• 結合性 — a、b、cが群のメンバーなら、(ab)c = a(cb)です。形式的には、$\forall a, b, c \in G \mid (a \circ b) \circ c = a \circ (b \circ c)$と書けます。これは「集合G内の要素a、b、cのすべての値について、aとbを演算してからcと演算した結果は、bとcを演算してからaと演算した結果に等しい」と読めます
• 単位元 — 群のすべての要素aについて、演算$e \circ a = a \circ e = a$を満たす要素eが群内に存在します。形式的には、$\exists e \in G \mid \forall a \in G \mid e \circ a = a \circ e = a$と書きます。これは「集合Gに要素eが存在し、集合G内のすべての要素aについて、eの後にaを演算した結果は、aの後にeを演算した結果と等しく、どちらもaに等しい」と読めます
• 逆元 — 群内の各要素aについて、$a \circ b = b \circ a = e$を満たす要素bが群内に存在します。ここで、eは単位元です。形式的には、$\forall a \in G \mid \exists b \in G \mid a \circ b = b \circ a = e$と書きます。これは「集合G内のすべての要素aについて、集合G内に要素bが存在し、aの後にbを演算した結果は、bの後にaを演算した結果と等しく、どちらも単位元に等しい」と読めます

この数学用語を、例を使って分かりやすく説明できます。加法における整数の集合を考えてみましょう。この集合は4つの群の公理をすべて満たすため、群を形成すると言えます。

• 閉性 — 2つの整数を足すと、別の整数になります
• 結合性 — $(5 + 4) + 3 = 5 + (4 + 3)$
• 単位元 — 任意の整数にゼロを足しても値が変わらないため、数のゼロが単位元です。たとえば、$7 + 0 = 0 + 7 = 7$です
• 逆元 — 任意の整数の逆元は、その符号を反転した数です。両方を足すと単位元になるためです。たとえば、$5 + (-5) = 0$です。これは$n + (-n) = 0$と一般化できます

さらに難しい例として、乗法におけるゼロ以外の有理数の集合$\mathbb{Q} = \left\{ \frac{a}{b} \mid a, b \in \mathbb{Z}, b \ne 0 \right\}$を考えてみましょう。これも集合を形成します。

• 閉性 — 2つのゼロ以外の有理数を掛けると、ゼロ以外の有理数になります
• 結合性 — $ab \times cd \times ef = ab \times (cd \times ef)$
• 単位元 — ゼロ以外の任意の有理数に1を掛けても値が変わらないため、数の1が単位元です。たとえば、$\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$です
• 逆元 — ゼロ以外の任意の有理数の逆元は、その逆数（分子と分母を入れ替えた数）です。結果が単位元である1になるためです。たとえば、$\frac{3}{5} \times \frac{5}{3} = 1$です

部分群

部分群とは、群の中にある群です。群Gの部分群HがGの部分集合であると言うには、次の群の公理を満たす必要があります。

• 閉性 — aとbがHに含まれる場合、両者の演算結果もHに含まれなければなりません
• 結合性 — この公理は、より大きな群Gから継承されます 
• 単位元 — Gの単位元はHにも含まれなければなりません 
• 逆元 — H内のすべての要素aについて、abとbaがどちらも単位元になるような要素bもH内に存在しなければなりません

典型的な例は、加法における偶数の集合が、加法における整数の集合の部分群になることです。

• 閉性 — 2つの偶数を足すと、別の偶数になります
• 結合性 — この公理は整数から継承されます。たとえば、$2 + (4 + 6) = (2 + 4) + 6$です
• 単位元 — 任意の偶数にゼロを足しても値が変わらないため、数のゼロが単位元です。ゼロは整数の集合にも含まれます
• 逆元 — 任意の偶数の逆元も偶数です。たとえば、$4 + (-4) = 0$となり、0は単位元なので、4の逆元は-4です

より難しい例にも応用できます。乗法におけるゼロ以外のすべての有理数の集合（ℚ*）を考えてみましょう。ℚ*が、乗法におけるゼロ以外の実数の集合（ℝ*）の部分群であることを証明できます。

• 閉性 — aとbがゼロ以外の有理数なら、その積abもゼロ以外の数です。たとえば、$\frac{1}{2} \times \frac{3}{4} = \frac{3}{8}$であり、これはゼロ以外の有理数です
• 結合性 — 有理数の乗法は結合的です。たとえば、$(\frac{1}{2} \times \frac{3}{4}) \times \frac{5}{6} = \frac{1}{2} \times (\frac{3}{4} \times \frac{5}{6})$です
• 単位元 — ゼロ以外の任意の有理数に1を掛けても変わらないため、数の1が単位元です。たとえば、$\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$です
• 逆元 — ゼロ以外のすべての有理数$a = \frac{p}{q}$には、乗法逆元$a^{-1} = \frac{q}{p}$があります。これもゼロ以外の有理数であり、掛け合わせると単位元になります。たとえば、a = $\frac{2}{3}$とします。$\frac{2}{3} \times \frac{3}{2} = 1$なので、逆元は$\frac{3}{2}$です

ℚ*は群の公理をすべて満たすため、群を形成します。さらに、ℚ*はℝ*の部分集合であり、その性質を継承するため、ℚ*はℝ*の部分群であると言えます。

なぜ重要なのでしょうか？

群は、さまざまな数学的・暗号学的概念と構造の基礎を成します。たとえば、RSAや楕円曲線暗号などの暗号システムは、群とその演算の性質に大きく依存しています。部分群を理解すると、より小さく扱いやすい部分集合を調べることで、大きな群の構造を理解できます。群は、対称性、演算、変換を理解するための基本的な枠組みを提供します。これは、次の体に関するセクションに進むうえで不可欠です。

体

体とは、加法と乗法について体の公理を満たし、可換な除法代数（ゼロによる除算を除き、常に除算できる代数）を成す要素の集合です。体の公理は通常、加法と乗法のペアとして記述されます。

• 加法
  • 結合性： $(a + b) + c = a + (b + c)$
  • 交換性： $a + b = b + a$
  • 分配性： $a(b + c) = ab + ac$
  • 単位元： $a + 0 = 0 + a = a$
  • 逆元： $a + (-a) = 0$
• 乗法
  • 結合性： $(ab)c = a(bc)$
  • 交換性： $ab = ba$
  • 分配性：$(a + b)c = ac + bc$
  • 単位元： $(a + b)c = ac + bc$
  • 逆元： $a \times a^{-1} = a^{-1} \times a = 1, \text{ if } a \ne 0$

有限体と生成元

有限体とは、要素の集合が有限である体です。有限体はガロア体とも呼ばれます。要素の数を、その体の位数または濃度と呼びます。要素数は必ず素数のべきになります。有限体の優れた点は、体内の要素にどのような算術演算を行っても、結果が体内に留まることです。すべての演算が体の位数を法として実行され、値が一周するためです。

すべての有限体には生成元があります。生成元は、べき乗によって体内のすべての要素を生成できます。つまり、体内のすべての要素を得るまで、生成元の指数を1ずつ増やせます。したがって生成元とは、そのべき乗によって体のゼロ以外のすべての要素を生成できる、体内の要素です。

たとえば、p = 7を法とする整数の集合を取り、体$\mathbb{Z}_7 = \{0, 1, 2, 3, 4, 5, 6\}$があるとします。$\mathbb{Z}_7^*$の生成元g（つまり、$\mathbb{Z}_7$のゼロ以外の要素による乗法群）を見つけるには、g1、g2、g3などが体のゼロ以外のすべての要素を生成できることを確認する必要があります。

3が生成元かどうか確認してみましょう。

3のべき乗は、$\mathbb{Z}_7$のゼロ以外のすべての要素を生成します。したがって、3は乗法群$\mathbb{Z}_7^*$の生成元です。

なぜ重要なのでしょうか？

暗号学は有限集合を扱う科学です。これは、離散対数問題、暗号化、Diffie-Hellman鍵交換、楕円曲線などのトピックに取り組むうえで不可欠な基礎知識です。生成元を使えば、暗号化された多項式を復号せずに演算できます（つまり、準同型暗号です）。つまり、基礎となる値のプライバシーを保ちながら、暗号化されたデータを計算できます。このセクションを理解することは、ゼロ知識証明の「ゼロ知識」の部分を理解するうえで不可欠です。

特定のパラメーターを使った有限体の生成と、その基礎理論をPythonで対話的に確認できるBill’s Security Siteもおすすめです。 

関数

関数とは、独立変数と従属変数という2つの変数間の関係を定義する式、規則、法則です。この2つの変数は、それぞれ原因と結果として説明されることもあります。この関係は通常、y = f(x)と表され、「xのf」と読みます。各xの値には一意のyの値が対応します。つまり、同じxに対して*f(x)*が複数の値を持つことはありません。

関数は1対1または多対1になり得ます。これは濃度と呼ばれることがよくあります。つまり、あるxの値が一意のyの値に対応する場合もあれば、複数のxの値が同じyの値に対応する場合もあります

$y = 3x + 4$で定義される直線を考えてみましょう。これは線形関数であり、xの値を代入すると、対応するyの値が返されます。この2つの値を組み合わせると、直線上の点になります。たとえば、式を$f(x) = 3x + 4$と書き換え、x = 1のときを計算すると、$f(1) = 7$になります。関数は複数の変数を持つこともできます。たとえば、三角形の面積の公式$A = \frac{bh}{2}$を考えてみましょう。ここで、A（面積）はb（底辺）とh（高さ）の両方の関数として定義されます。

定義域と値域

関数の定義域は、関数が受け取れるすべての入力値（独立変数）の集合です。関数の値域は、関数が生成できるすべての出力値（従属変数）の集合です。

関数$y = 2x + 2$の場合は次のようになります。

• 負の無限大から正の無限大まで、どの数でも使えるため、定義域はすべての実数です。たとえば、次のとおりです。
  • x = 2.5なら、$y = 2(2.5) + 2 = 7$です 
  • x = -9234525なら、$y = 2(-9234525) + 2 = -18469048$です
• 負の無限大から正の無限大まで、どの数でも生成できるため、値域もすべての実数です。たとえば、次のとおりです。
  • y = -50を求めるには、-50 = 2x + 2を解き、x = -26を得ます 
  • y = 0を求めるには、0 = 2x + 2を解き、x = 0を得ます

なぜ重要なのでしょうか？

関数は、多項式を理解するうえで不可欠です。多項式は、さまざまなべき乗を持つ変数とその係数を含む特殊な関数です。多項式は、暗号プロトコルを構築する基礎となる基本的な代数構造です。次のセクションでは、多項式の性質とゼロ知識証明における重要性を詳しく見ていきます。

関数をより深く理解するには、Paul’s Online Notesの練習問題に取り組むことをおすすめします。

多項式

多項式とは、複数の変数と係数から成り、加法、減法、乗法、および変数の非負整数乗のみを使う関数です。多項式は通常、次の形式で記述されます。‍

ここで、$a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$は係数で、xは変数です。係数がゼロではない変数xの最大のべき指数を、多項式の次数と呼びます。

多項式は、単一の変数を含む一変数多項式（上に示した形式）と、複数の変数を含む多変数多項式（例：$P(x, y) = a_nx^ny^n + a_{n-1}x^{n-1}y^{n-1} + \cdots + a_1xy + a_0$）に分類できます。Sum-Checkは、多変数多項式を使用するプロトコルの一例です。ただし、ほとんどの場合、ゼロ知識証明に必要な変数は1つだけです。

次数に基づく多項式の一般的な名称は次のとおりです。

• 0次 — ゼロではない定数（例：$P(x) = 6$）
• 1次 — 線形（例：$P(x) = 2x - 7$）
• 2次 — 二次（例：$P(x) = 8x^2 - 3x + 1$）
• 3次 — 三次（例：$P(x) = 3x^3 - 4x$）

次数が最大でも $d$ である相異なる2つの多項式は、最大 $d$ 個の点でしか交わりません（たとえば、一次関数と三次関数を等しいと置いた場合、最大3回交わります）。この性質は、共通点を求める方法に由来します。2つの多項式が交わる場所を求めるには、両者を等しいと置きます。次のサブセクションでは、多項式の根、つまり与えられた多項式がx軸と交わる場所を求める練習をします。代数学の基本定理によれば、次数 $d$ の多項式が持つ解は最大 $d$ 個であり、したがって共通点も最大 $d$ 個です。

多項式の根 

多項式の根（零点）とは、多項式がゼロになる x の値です。言い換えると、$P(x)$ が多項式である場合、根 $r$ は方程式 $P(r) = 0$ の解です。根を求めるには、多項式の因数分解を理解している必要があります。因数分解とは、何を掛け合わせれば与えられた量になるかを求めることです。たとえば、12は複数の方法で因数分解できます。

一般的な因数分解の方法は、数を正の素因数に完全に分解することです。因数分解では、すべての項に共通する最大公約数（GCF）から始めるのが常に最善です。たとえば、

上の例では、両方の項（6xと3）が3で割り切れるため、GCFは3です。したがって、因数は3と $2x + 1$ です。分配法則を逆に適用すると、$3 \times 2x$ と $3 \times 1$ になります。根を求めるとは、$P(x) = 0$ のときの x を解くことです。

2項からなる多項式の因数分解は簡単です。グラフが与えられている場合はさらに簡単で、多項式がx軸と交わる場所が根になります。ただし、次数が3以上になると複雑になる場合があります。より詳しい説明については、記事「多項式の因数分解を解説」を読むことをおすすめします。 

さまざまな多項式を因数分解する際の細かな違いを正確に理解していなくても、この記事の残りを読むうえでは問題ありません。ここでは、多項式が別の値と等しくなる場合に注目します。この例では、多項式がゼロになる場合に注目します。後ほど、ある多項式が別の多項式と等しい場合や、2つの多項式の差が恒等的にゼロ（つまり、すべての係数がゼロ）になる場合を扱います。これには、与えられた多項式が特定の根を持つかどうかの確認が伴います。

Schwartz-Zippelの補題 

Schwartz-Zippelの補題は、多項式方程式が常に成り立つかどうかを確認するための確率的な手法です。ランダムな点で多項式を評価し、その結果がゼロかどうかを確認します。

変数 $x_1, x_2, \ldots, x_n$ を含む複雑な方程式を想像してください。この方程式が単なる項の無作為な集まりではなく多項式である場合、Schwartz_Zippelの補題を使うと、これらの変数のあらゆる値について方程式が成り立つかどうかを検証できます。

仕組みは次のとおりです。

• $P(x_1, x_2, \ldots, x_n)$ を全次数が d（つまり、各項における指数の合計の最大値）の多項式とします
• 体から有限集合 S を選びます（数の集合を選ぶようなものです）
• 集合 S から各変数 $x_1, x_2, \ldots, x_n$ の値をランダムに選びます

この補題によれば、ランダムに選ばれたこれらの点で P がゼロになる確率は最大でも $\frac{d}{S}$ です。つまり、多項式がゼロでない場合、偶然によってゼロに見える可能性は非常に低いということです。これは、多項式恒等式を効率的に検証する必要があるゼロ知識証明で特に有用です。

Lagrange補間

Lagrange補間は、与えられた点の集合を通る多項式を構築する方法です。Lagrange多項式は、与えられた各点を通る最小次数の多項式です。n 個の点に対して、すべての点を通る次数 n-1 の多項式を作成できます。たとえば、平面上に2点がある場合、その両方を通る直線を定義できます。平面上に3点がある場合、すべての点を通る二次多項式（つまり $y = ax^2 + bx + c$）を定義できます。以降も同様です。

なぜ重要なのでしょうか？

多項式は、無限量の情報を格納できる単一の数学的対象です。多項式を整数のリストと考えれば、これは明らかです。したがって、多項式間の1つの方程式で、数値間の無限個の方程式を表現できます。誰かが多項式間のある方程式を検証できれば、暗黙的に考えられるすべての方程式を同時に検証していることになります。このようにして、悪意のある証明者の脅威から非対話型証明を保護し、特定の計算をランダムに抜き取り検査する必要をなくします。 

また、多項式には証明の作成に役立つ性質がいくつかあります。

• ある多項式について十分な数の点が与えられれば、多項式全体を復元できます
• 多項式の入力をわずかに変更するだけで出力が大きく変わる場合があるため、誤りを検出しやすくなります
• 多項式は計算上の誤りを検出して訂正できます。これは、消失訂正符号によってデータに耐障害性を持たせる仕組みに似ています（これはTurbineの動作に不可欠です）

ゼロ知識証明は、特定の計算を証明するためのものです。多項式は特定の特性を持つように作成できるため、この用途で非常に有用です。証明したい計算やデータポイントの集合があるとします。最も簡単な方法は、それを多項式にエンコードし、その性質を利用して証明を作成することです。

• 特定の点で $P(x)$ を評価すると元のデータまたは特定の計算結果が得られるように、データを多項式 $P(x)$ にエンコードします
• 多項式が指定された基準（たとえば、すべての値が範囲内にあること）を満たすように、制約多項式 $C(x)$ を作成します。たとえば、$C(x) = (P(x) - 0)(P(x) - 1)$ により、$P(x)$ が0または1であることを保証できます
• 問題を、$P(x)$ がデータセットまたは計算に関する特定の条件を満たすことの証明へと変換します
• これらの条件をエンコードし、$P(x)$ の倍数となる既知の多項式 $H(x)$ を作成します
• 証明者は、$P(x)$ と関連する多項式の評価値からMerkleツリーを作成して値をコミットし、ルートハッシュを検証者に送信します
• 検証者は複数の点をランダムに選択し、それらの点における $P(x)$ と $C(x)$ の値を提示するよう証明者に求めます
• 検証者は、提示された値をコミット済みのルートハッシュおよび想定される多項式の関係と照合します

多項式がどれほど大きくても問題ありません。多項式コミットメントを使用するため、多項式間の方程式を短時間で検証できます。これは、証明を作成するための非常に簡潔で効率的な方法です。あらゆる誤りが増幅され、Fiat-Shamirヒューリスティックなどの手法を使うことで、これらの証明を非対話型にできます。そのため、追加のやり取りなしで誰でも検証できます。 

理解を深めるために、次の練習問題に取り組むことをおすすめします。

• 多項式の練習問題
• 多項式の零点を求める練習問題
• 多項式の因数分解：解答付きの非常に難しい問題

Khan Academyにも、多項式、方程式、関数についての充実した単元があります。

次に、多項式コミットメントをより深く理解するため、ゼロ知識証明の基盤となる暗号技術を見ていく必要があります。

ゼロ知識証明を支える暗号技術

対称暗号と非対称暗号について見ていきましょう。

対称暗号

対称暗号は、平文の暗号化と暗号文の復号に同じ鍵を使用する暗号化技術です。単一の鍵を使用するには、その鍵を秘密に保つ必要があるため、この鍵は一般に秘密鍵またはプライベートキーと呼ばれます。しかし、これは安全に通信する前に、2者間で秘密鍵を共有する必要があることも意味します。そのため、秘密鍵を安全に管理、配布することは難しく、適切に扱わなければ漏洩する可能性があります。この欠点はあるものの、対称暗号は高速かつ効率的で、他の暗号方式よりも必要な計算能力とメモリが少なくなります。

一般的な対称暗号アルゴリズムには、次のものがあります。

Advanced Encryption Standard（AES）

Advanced Encryption Standard（AES）は、データの保護に世界中で広く使用されているRijndaelブロック暗号の一種です。128、192、256ビットの鍵長をサポートします。

ChaCha20

ChaCha20は、Daniel J. Bernsteinが開発した最新の効率的なストリーム暗号です。加算・ローテート・XOR（ARX）演算を活用するSalsa20ストリーム暗号の一種です。256ビットの鍵、64ビットのnonce、64ビットのカウンターを512ビットのキーストリームブロックに写像するため、ユーザーは定数時間でキーストリーム上の任意の位置を効率的に参照できます。

対称暗号は堅牢かつ効率的ですが、安全に鍵を交換する方法が必要です。その1つがDiffie-Hellman鍵共有です。これは、安全でない通信路上で2者が秘密鍵を安全に共有できるようにします。ただし、この方法は非対称暗号の原理に基づいており、次のセクションで説明します。

非対称暗号

非対称暗号は公開鍵暗号とも呼ばれ、関連する鍵のペア（公開鍵と秘密鍵）を使用して情報を暗号化および復号する方式です。公開鍵は公開されますが、秘密鍵は秘匿されます。送信者がメッセージを暗号化する場合、受信者の公開鍵を使用します。受信者は、受信後に対応する秘密鍵を使用してメッセージを復号します。公開鍵で暗号化されたデータは、秘密鍵でのみ復号できます。したがって、復号鍵を共有する必要がないため、非対称暗号では安全でない通信路上でも安全に通信できます。

非対称暗号には、秘密鍵を共有しないため高いセキュリティを実現できるという利点があります。また、公開鍵を自由に共有できるため鍵の配布が簡単になり、デジタル署名も可能になります。ただし、非対称暗号は対称暗号よりも計算負荷が高く、低速です。鍵ペアの管理も、特にユーザー数が多く、鍵ペアを直感的に扱えないシステムでは複雑になる場合があります。 

一般的な非対称暗号アルゴリズムには、次のものがあります。

• Rivest-Shamir-Adleman（RSA） — 安全なデータ転送に使われる、最も古く、最も広く利用されている公開鍵暗号方式の1つです。1970年代に開発され、2つの大きな素数の積を因数分解することが実用上困難である点に依存しています
• 楕円曲線暗号（ECC） — 有限体上の楕円曲線の代数構造に基づく公開鍵暗号のアプローチです。RSAと同等のセキュリティをより短い鍵長で実現し、計算を高速化してストレージ要件を削減できます。Solanaは鍵ペアの生成にEd25519楕円曲線を使用しています

デジタル署名

デジタル署名は公開鍵暗号の重要な要素であり、メッセージ、ソフトウェア、デジタル文書の真正性と完全性を検証する方法を提供します。デジタル署名は送信者の秘密鍵を使用して作成され、対応する公開鍵にアクセスできる人なら誰でも検証できます。これにより、正当な送信者からメッセージが送られ、改ざんされていないことを確認できます。

デジタル署名で一般的に使用されるアルゴリズムには、次のものがあります。

• Digital Signature Algorithm（DSA） — モジュラ冪乗（法の下で行われる冪乗）と離散対数問題に基づくアプローチです
• Elliptic Curve Digital Signature Algorithm（ECDSA） — 楕円曲線暗号を使用し、より短い鍵長でより高いレベルのセキュリティを実現するDSAの一種です

離散対数問題

離散対数問題とは、方程式 $g^k \equiv h \pmod{p}$ において指数 k を求める問題です。ここで、

• gは既知の底（つまり生成元）です
• hは既知の結果（つまり群の元）です
• pは素数（つまり群の位数）です
• kは未知の指数（つまり底gに対するhの離散対数）です

簡単に言うと、g、h、p の値が分かっているとき、k を求めるのが離散対数問題です。たとえば、方程式 $2^k \equiv 9 \pmod{23}$ が与えられた場合、目的はkを求めることです。

離散対数問題を効率的に解くことは、特に数値が大きい場合に困難だと考えられています。この難しさは、Solana、ElGamal暗号、Digital Signature Algorithm（DSAおよびECDSA）、Diffie-Hellman鍵共有など、さまざまな暗号システムのセキュリティの基盤になっています。

Diffie-Hellman鍵共有

Diffie-Hellman鍵共有は、公開された通信路上で暗号鍵を安全に交換する方法です。  最も単純な原型の実装（有限体Diffie-Hellman）は次のとおりです。

• AliceとBobは、大きな素数 p（法）と、p を法とする原始根である底 g（生成元）という2つの数値に公開の場で合意します 
• Aliceは秘密の整数 a を選び、Bobに $A \equiv g^a \pmod{p}$ を送信します
• Bobは秘密の整数 b を選び、Aliceに $B \equiv g^b \pmod{p}$ を送信します
• Aliceは $s \equiv B^a \pmod{p}$ を計算します 
• Bobは $s = A^b \pmod{p}$ を計算します 

これで、AliceとBobは同じ秘密値を持ちます。これは、次のように両方の計算で同じ秘密値 s が得られるためです。

この共有秘密値 s は対称暗号の鍵として使用でき、AliceとBobは安全に通信できます。Diffie-Hellman鍵共有のセキュリティは、離散対数問題の難しさに依存しています。秘密値 a と b を知らなければ、盗聴者が共有秘密値を導出することは計算上不可能です。これは一方向関数として知られており、計算は比較的簡単ですが、逆算は極めて困難です。

有限体Diffie-Helman鍵共有は安全で広く利用されていますが、安全性を確保するには長い鍵が必要です。たとえば、AliceとBobが公開の場で法として23を選んだ場合、n mod 23の結果は23通りしかないため、はるかに簡単に解読されてしまいます。そのため、計算負荷が高く、効率が低くなる可能性があります。こうした課題に対処するため、楕円曲線暗号（ECC）は、はるかに短い鍵長と高速な計算で同じレベルのセキュリティを実現する、より効率的な代替手段を提供します。

楕円曲線

楕円曲線は方程式 $y^2 = x^3 + ax + b$ で定義されます。ここで、a と b は定数です。楕円曲線暗号とは、端的に言えば、与えられた楕円曲線上の点を扱うことです。これらの曲線には、暗号技術に役立つ固有の性質がいくつもあります。たとえば、

• 点の加算 — 与えられた楕円曲線上の2点 P と Q に対し、その和 R = P + Q も曲線上の点になります。Preethi Kasireddyによる記事「ゼロ知識証明のための苦痛のない暗号技術ガイド」では、楕円曲線上の点を加算する方法が分かりやすく説明されています
• スカラー倍算 — 与えられた楕円曲線上の点 P と整数 k に対し、スカラー倍算とは点 P をそれ自身に k 回加算する処理です。これにより、曲線上に別の点（つまり kP）が生成されます。これは秘密鍵から公開鍵を生成するために使用されます
• 離散対数問題 — 楕円曲線上の離散対数問題は、整数における同等の問題よりはるかに解くのが困難です。点 P と q = kP が与えられた場合、曲線パラメータが適切に選択されていれば、k を求めることは計算上不可能です。つまり、楕円曲線は従来のシステムと同等のセキュリティをはるかに短い鍵長で提供できるため、より効率的です

ここまでに学んだ群論の知識を使うと、特定の楕円曲線方程式は次の公理群を満たすと言えます。

• 任意の2点を加算すると、第3の点が得られます
• 2点を加算する順序は結果に影響しません
• 3点以上を加算する場合、加算する順序は結果に影響しません
• 単位元があります（つまり、曲線上の任意の点にゼロを加えると同じ点になります）

この群構造をさらに詳しく学ぶには、Georgie Bumpusによる「楕円曲線暗号」を読むことを強くおすすめします。 

楕円曲線は、RSAなどの従来の暗号システムと同じレベルのセキュリティを、はるかに短い鍵長で提供します。たとえば、ECCの256ビット鍵は、RSAの3072ビット鍵と同等のセキュリティを提供します。これには次のような利点があります。

• 鍵長が短いほど、暗号化と復号が高速になります
• 鍵と証明書に必要な容量が少なくなります
• 鍵が短いほど送信データ量が減るため、ブロックチェーンなど帯域幅が限られた環境で有利です

Montgomery曲線

Montgomery曲線は、有限体上で方程式 $By^2 = x^3 + Ax^2 + x$ によって定義される楕円曲線です。ここで A と B は定数、Bはゼロではなく、A は-2でも2でもありません。これらの曲線が特別なのは、Montgomeryラダーを使用して楕円曲線の乗算をより効率的に実装できるためです。 

Montgomeryラダーは基本的に、Montgomery曲線上の点 P とスカラー k を受け取り、無限遠点と P で2点を初期化し、スカラー k の各ビットを最上位ビットから最下位ビットまで更新します。重要なのは、2つの点を保持し、スカラー k のビットにかかわらず一定の演算手順で更新することです。

これが重要な理由はいくつかあります。

• サイドチャネル攻撃への耐性があります。サイドチャネル攻撃とは、特定のプロトコルやアルゴリズムの実装または設計によって収集できる付加情報に基づく攻撃です。非常に、非常にマニアックですが、深掘りすることをおすすめします。この種の攻撃には、計算中のハードウェアによる消費電力の変動を利用するものから、漏洩した電磁放射を利用するものまであります
• y座標は不要です。スカラー倍算はx座標のみを使用して実行できるためです
• 定数時間で動作します。つまり、特定の計算にかかる時間が入力値に依存しません

Montgomery曲線は、Montgomery形式の曲線Curve25519を使用する鍵共有用のX25519アルゴリズムなど、暗号プロトコルで広く使用されています。このアルゴリズムは、TLSなどの一般的なプロトコルへの実装を含む、現代の安全な通信の基盤です。 

Edwards曲線

Edwards曲線は、方程式 $x^2 + y^2 = 1 + d x^2 y^2$ によって定義される楕円曲線の一種です。ここで d は1ではない非ゼロの定数です。  

これらの曲線が重要な理由は次のとおりです。

• 点演算の効率性 — Edwards曲線上の2点の加算は、他の形式の楕円曲線と比べて効率的です。点の加算と倍算の式が単純で、必要な体演算も少ないため、高速に計算できます
• 統一加算公式 — Edwards曲線は統一加算公式を使用します。つまり、点の加算と点の倍算に同じ式を使用できます。これにより、実装エラーの可能性が低下し、セキュリティが向上します
• 完全性 — d が特定の値である場合、Edwards曲線は完全です。つまり、加算則は例外なく、考えられるすべての入力に対応します。
• サイドチャネル攻撃への耐性 — Montgomery曲線と同様に、Edwards曲線は演算パターンが均一で予測可能なため、サイドチャネル攻撃への耐性があります。

広く使用されているEdwards曲線の1つに、方程式 $x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$ で定義されるEdwards25519があります。この曲線は効率的な算術演算と256ビットの鍵長で知られています。その署名方式は、Solana、OpenSSH、Torなど、さまざまなセキュリティプロトコルやシステムに実装されています。MoneroはEdwards25519を鍵ペア生成の基盤として使用しています。

なぜ重要なのでしょうか？

楕円曲線は、その効率性とセキュリティを強化する性質により、ゼロ知識証明で極めて重要です。楕円曲線を使用すると、より小さく高速な証明を作成できます。これは、実用的な実装には不可欠です。ゼロ知識に関連する進展を扱う際にさらに詳しく分析しますが、さまざまなアカウントやトランザクションの制約がある高負荷なコンピューティング環境では、小さく高速な証明が極めて重要です。この特性により、ゼロ知識証明はロールアップの構築に適しています。L2上のすべての処理が有効であることを示す簡潔な証明を生成し、L1上で検証できるためです。

結局のところ、楕円曲線はモジュラ算術の代替手段だと考えてください。楕円曲線では、特定の点を得ることが大幅に難しくなります。従来のモジュラ算術で $g^a \bmod n$ を使用するとします。ここで、g は生成元、n は大きな素数、a は秘密鍵です。離散対数問題で前述したように、秘密鍵を保護するには非常に大きな素数が必要です。楕円曲線は、より短い鍵長で効率的な代替手段を提供し、大幅に向上したパフォーマンスで同じレベルのセキュリティを実現します。

ランダム性

暗号技術の基本要素であるランダム性がなければ、この記事の他の内容はどれも意味をなしません。値が予測可能で偏っているシステムに、どうして安全性を期待できるでしょうか。真のランダム性を実現するのは困難ですが、次のようないくつかの理由から不可欠です。

• 鍵生成 — 暗号鍵は、予測不可能で安全なものにするため、ランダムに生成する必要があります
• Nonceとソルト — Nonce（1回だけ使用される数値）とソルト（ハッシュ化の前にデータへ追加されるランダムな値）は、それぞれリプレイ攻撃を防ぎ、事前計算攻撃から保護します
• 安全なプロトコル — ランダム性は公平性とセキュリティを確保し、攻撃者が悪用できる予測可能性やパターンを防ぐために使用されます

ほとんどの乱数生成器は、暗号学的に検証できる乱数を生成できません。そのため操作を受けやすく、ユースケースも限られます。しかし、検証可能ランダム関数はこの問題を解決します。

検証可能ランダム関数

検証可能ランダム関数（VRF）は、ランダムな出力と、その出力が与えられた入力から正しく生成されたことを示す証明を生成する暗号プリミティブです。VRFは予測不可能でなければなりません。つまり、秘密の入力を知らない人には、その出力がランダムな値と区別できない必要があります。その安全性は、秘密の指数 d を知らずに $y = h^d \bmod n$ を計算することは困難であるというRSA仮定と、ハッシュ関数 H の安全性に依存します。 

VRFの主な手順は次のとおりです。

• 鍵生成 — ユーザーは、公開鍵としてRSA鍵のペア（e、n）を、秘密鍵として（d、n）を生成します。公開鍵の e は指数、n は法です。秘密鍵の d は秘密の指数です
• 計算 — 入力 x が与えられると、ユーザーはVRFの出力 y と証明 π を計算します。まず、H を暗号学的ハッシュ関数として、ハッシュ h = H(x) を計算します。次に、ハッシュのRSA署名である $y = h^d \bmod n$ を計算します。最後に、証明 π = (h, y) を計算します
• 検証 — 公開鍵（e、n）、入力 x、出力 y、証明 π = (h, y) が与えられると、誰でもハッシュ h が $H(x)$ と等しいこと、およびRSA方程式を検証する $y^e \equiv h \pmod{n}$ を確認することで、VRF出力の正しさを検証できます‍

VRFは、ランダム性が予測不可能でありながら検証可能である必要があるコンセンサスプロトコルでよく使用されます。Algorand、Cardano、Internet Computer、PolkadotなどのL1は、ブロック生成者をランダムに選択するため、コンセンサスメカニズムでVRFを使用しています。Chainlinkは、公正である可能性が高く検証可能な値を生成するため、ユーザーとブロックチェーンの間の抽象化レイヤーとしてChainlink VRFを提供しています。Pyth Entropyも、信頼性が高く安全なランダム性の供給源を提供しています。

セレモニーとTrusted Setup

暗号セレモニーとは、重要な暗号計算を安全かつ管理された環境で実行するプロトコルまたはイベントです。暗号セレモニーには、主に次の種類があります。

• 鍵生成セレモニー — 単一の主体が鍵生成プロセスを制御できないように、暗号鍵を生成します
• パラメータ生成セレモニー — 複数の当事者が使用する暗号パラメータを作成します
• マルチパーティ計算（MPC）セレモニー — 単一の当事者がプロセスを侵害できないように、複数の当事者が共同で暗号計算を実行します

Trusted Setupセレモニーは、暗号プロトコルの実行に必要な暗号パラメータの集合を生成するために設計された特別なイベントまたはプロセスです。対話型および非対話型ゼロ知識証明のセクションでは、証明の最初のステップとして、証明者と検証者が使用する何らかの値に合意する必要があると説明しました。Trusted Setupセレモニーでは、単一の参加者がプロセスを制御できないように、複数の参加者がセットアップにランダム性を提供します。各参加者はランダムな値を生成し、それを他の参加者が提供した値と組み合わせます。組み合わせた出力が、誰もが信頼できるパラメータの集合になります。 

このプロセスは極めて重要です。すべての参加者が共謀した場合、無効な主張に対する証明を生成してシステムを破ることができるためです。しかし、誠実な参加者が1人でもいれば、パラメータの安全性は確保されます。 

Zcashは、チェーンのプライバシー機能を立ち上げるためにTrusted Ceremonyを使用したことでよく知られています。Ethereumでも、スケーリングへの取り組み（EIP-4844 / proto-dankshardingなど）に暗号学的基盤を提供するための、協調型の公開セレモニーであるKZG Ceremonyが行われました。 

zk-STARKなど、一部のゼロ知識証明システムではTrusted Setupが不要である点に注意してください。これについては、2本目の記事でさらに詳しく説明します。

まとめ

この記事では、ゼロ知識証明を支える基礎理論、数学、暗号技術について解説しました。ゼロ知識証明とは何か、という問いに答えるために必要な知識は以上です。ここからは、学んだ内容をSolanaなどのネットワークに応用し、ゼロ知識証明をめぐる議論と開発全体に貢献していきます。

ゼロ知識証明に関する全2回シリーズの第2回かつ最終回となる、その名もゼロ知識証明：Solanaでの応用で、この分析を続けます。 

ここまでお読みいただき、ありがとうございます、anon！以下にメールアドレスを入力して、Solanaの最新情報をお見逃しなく。さらに深く掘り下げる準備はできましたか？ Heliusブログの最新記事をチェックして、今すぐSolanaの旅を続けましょう。

参考資料

• 真のランダム性は存在するのか？
• 楕円曲線 — Computerphile
• NP完全計算量クラス入門
• 鍵交換問題 — Computerphile
• Khan Academyの暗号学ユニット
• 公開鍵暗号方式 — Computerphile
• 対話型証明システムの知識複雑性