序章

前回の投稿では、SNARKのコンセプトと必要な基本プロパティを紹介しました。この一連の投稿の主な目的、つまり、あらゆる計算用の zk-SNARK を構築する方法を念頭に置いて、この投稿では、多項式の知識を証明するための SNARK の作成について紹介します。すべての要件を満たさない 1 つの構築から出発し、「完全な」ゼロ知識 SNARK となるプロトコルを終了するという手順で段階的に実行していきます。

多項式の ZK-SNARK

zk-SNARK は、SNARK ではない単純な構造から始めて、目標を達成するまで新しい技術で改良しながら、段階的に構築していきます。

最初のステップ: Schwartz — Zippel 補題

証明者 P が検証者 V に、有限体 F の係数をもつ n 次の特定の多項式の知識を納得させられるプロトコルを作成したいと考えています。言い換えれば、P は次の形式の多項式を知っていると V に納得させたいのです。

a_1、a_2、…、a_n ∈ F がこの多項式の n 根であると仮定します。したがって、p(x) は次のように書くことができます。

V が多項式 p(x) の d < n 根を知っていると仮定します。

次に、問題を再定式化できます。今、P は次のような多項式 h(x) を知っていることを V に証明したいと考えています。

多項式 t(x) をターゲット多項式と呼びます。次のような形式になっていることに注目してください。

zk-SNARK の最初のバージョンは、Schwartz — Zippel 補題に基づいています。F を体、f: F^m → F を次数 n の多変数多項式とします。次に、任意の有限集合 S ⊆ F について、次のようになります。

補題が示しているのは、u ∈ Sm を一様にランダムにとった場合、u が f の根の集合である確率は最大でも n / |S| であるということです。S を有限体 F とみなした場合、この確率は小さいことがわかります。場のサイズは n に比べて非常に大きくなります。

矛盾しているように思えるかもしれませんが、この補題により多項式 f の知識を証明することができます。p のすべての係数を知っていることを証明する必要はありませんが、任意の s ∈ Fm のペア (s, f(s)) を計算する方法を知っていることだけを証明する必要があります。Schwartz — Zippel 補題は、zk-SNARK で必要な効率を提供します。

最初のプロトコル

P は多項式 p(x) を知っており、V は p(x) の d < n 根を知っているか、または同等に、V はターゲット多項式 t(x) を知っていることを思い出してください。P は t(x) も知っています。

私たちの最初のアプローチは次のとおりです。

1. V はランダムな値 s を受け取り、t = t(s) を計算します。V は s を P に送信します。
2. P は多項式を計算します

4. V は、p = t · h が等しいかどうかをチェックします。

P が多項式 p(x) を知っている場合、h(x) を計算できるため、P は p = h · t となる値 h と p も計算できるため、このプロトコルは正しいです。一方、このプロトコルは、Schwartz - Zippel 補題により効率的でもあります。

それにもかかわらず、たとえ P が p(x) を知らなくても、証明者はターゲット多項式を使用して t = t(s) を計算できるため、このプロトコルは堅牢ではありません。彼はランダムな h を取得して p = h · t を計算し、そのペア (h, p) を V に送信し、V はそのペアを有効なものとして受け入れることができます。

P が V を欺くことができる重要な点は、P が評価点 s を知っていることであることがわかります。P が評価点 s を知らずに p を評価できる場合、このトリックは不可能です。これは、2 番目のステップである準同型難読化、つまり準同型隠蔽につながります。

第 2 ステップ: 準同型難読化

プロトコルを堅牢にするためには、その点を知らなくても、その点に関する多項式を評価できる必要があります。

離散対数問題の難易度に基づいてこれを行います。古典的なコンピューターの場合、離散対数問題は計算上実行不可能です。次数 p で要素 g によって生成される巡回群 G では、既知の に対して = ga (mod p) となる要素 a を決定します。

したがって、離散対数多項式の硬さを仮定すると、 = ga (mod p) を計算することで値 a を難読化できます。 の受信者だけでは値 a を学習できません。この手法の興味深い点は、べき乗にはいくつかの準同型特性があることです。

難読化された 2 つの値の積は、関連する値を平文で加算した難読化と同じです。

多項式を評価したい場合

点 x = s に関して、評価者に正確な点を知らせずに多項式全体を難読化する必要があります。

また、x = r のすべての難読化された値の累乗を、1 から多項式の次数まで計算する必要があります。

これらすべての要素を使用して、点 x =r 上の多項式 p の難読化された評価を計算できることに注目してください。それはそう：

準同型隠蔽の例

有限体 F = ℤ127 および g = 3 を生成器として考えてみましょう。P が多項式 p(x) = 4x2 + 3x + 1 を知っており、V が P に点を知らせずに点 x = 2 に関する多項式を評価してもらいたいと仮定します。次の手順でそれを行うことができます。

1. V は、0 から多項式の次数 n = 2 までの x = 2 のすべてのべき乗を計算します。

1.b. 32 (mod 127) = 9

1.c. 34 (mod 127) = 81

そしてペア (9, 81) を P に送信します。

2. P は、x の値を知らなくても、x = 2 での p(x) の評価を計算できます。実際、V から受け取った情報を使用して、次のように計算できます。

第 2 プロトコル

証明者がその難読化された点で多項式を評価できるように点を難読化する方法がわかったので、最初のプロトコルを改良します。P は多項式 p(x) を知っており、V は p(x) の d < n 根を知っているか、または同等に、V はターゲット多項式 t(x) を知っていることを思い出してください。P は t(x) も知っています。

2 番目のプロトコルは次のとおりです。

1. V はランダムな値 s を受け取り、t = t(s) を計算します。
2. V は次のべき乗を計算して P に送信します。

4. 値 を使用して、P は前の例の命令に従って g^p = g^{p(s)} および g^h = g*{h(s)} を計算します。

5. P は g^p と g^h を V に送信します。

6. V は、次の恒等式が成立するかどうかをチェックします: g^p = (g^h)^t

最初のプロトコルで検出された欠陥は修正されていますが、この 2 番目のプロトコルはまだ堅牢ではないことがわかります。確かに、P は引き続き、z_p = (z_h)^t となる値 zp と zh を使用し、それらを g^p と g^h であるかのように V に送信できます。P は、ランダムな r を取得し、z_h = g^r を計算し、z_p = (g^t)^r を設定することでこれを行うことができます。値 z_p は、V によって送信された難読化されたべき乗を使用して計算できます。

この状況を回避するには、V によって送信された難読化されたべき乗のみを使用して g^p と g^h が計算されるようにする必要があります。

3 番目のステップ: 指数の知識の仮定

SNARK を定義するときに共通の仮定が 1 つあります。2q + 1 も素数であるような素数 q を考えてみましょう。ℤ_{2q + 1} の ga 生成器を考えてみましょう。q, g および g' = g^ とすると、x ≠ g、y ≠ g'、および y = x^ となるペア (x, y) を見つけたいとします。指数知識の仮定 (KEA) では、ペア (x, y) を見つける唯一の方法は、値 c ∈ ℤ_q を取得し、最初に x = g^c を計算し、次に y = (g')^ を取得することであると述べています。 c.

KEA は、(x, y) のペアを取得したい場合、それを行う唯一の方法は、x = g^c となる指数 c を知ることであることを意味します。つまり、KEA プロパティを持つペア (x, y) を取得するには、g の累乗を使用する必要があります。

KEA を使用する以下のプロトコルは、P が V によって渡される乗法部分群の生成子である g の特定のべき乗を返すことを保証します。

1. V はランダムな値 を受け取り、g' = g^ (mod 2q + 1) を計算します。
2. V はペア (g, g') を P に送信し、(b, b') = (g, g') となるペア (b, b') を要求します。
3. P は値 c を受け取り、b = g^c (mod 2q + 1)、b' = (g')^c (mod 2q + 1) を計算し、ペア (b, b') を V に送信します。
4. V は b' = b^ (mod 2q + 1) かどうかをチェックします。

P は g と g' の両方に同じ累乗 c を使用し、V によって提供される値のみを使用できました。

第三のプロトコル

証明者 P が難読化されたドメイン上の値 s のべき乗を確実に出力する適切なプロトコルを構築する準備ができました。

1. V はランダムな値 s を受け取り、t = t(s) を計算します。
2. V はランダムな値 を受け取り、t( · s) を計算します。
3. V は、次の一連の難読化された値 を計算し、それらを P に送信します。
4. V は、次の一連の難読化された値を計算します。

5. P は多項式 h(x) を計算します。

6. を使用して、P は p(s) と h(s) を g^p = g^{p(s)} および g^h = g^{h(s)} とともに計算します。

7. を使用して、P は g^{p'} = g^{p( · s)} とともに p(s) と h(s) を計算します。

8. P は g^p、g^h、g^{p'} を V に送信します。

9. V は、P が自分に送信した情報のみを使用して難読化された値の計算を行ったことを確認します。これを行うために、V は g^p = g^{p'} かどうかをチェックします。

10. V は、次の恒等式が成立するかどうかをチェックします: g^p = (g^h)^{t(s)}。

このプロトコルは、SNARK に必要な特性を満たしています。正確で、堅牢で、効率的です。次のセクションでは、非対話性とゼロ知識について扱います。

注:上記のプロトコルのステップ 6 と 7 は、準同型隠蔽の例に従って実行されます。

ゼロ知識

これまでに提示したプロトコルでは、P に既知の多項式の係数 ci は非常に具体的であり、V は P から得られる gp、gh、gp' を使用してそれらに関する情報を学習しようと試みることができます。 V は何も学習しないため、P はこれらの値を隠す必要があります。

P によって送信された値を非表示にする戦略は、以前に使用した手順に従います。P はランダムな を取得し、それを使用して V との通信で送信された値を非表示にします。正確には、g^p、g^h、g を送信する代わりに、 ^{p'}、P は (g^p)^、(g^h)^、および (g^{p'})^ を計算して送信します。次に、V は の下に隠された値の検証を実行します。

実際、V が実行する必要がある検証手順は、この非表示でも引き続き有効です。

したがって、3 番目のプロトコルをゼロ知識にするために、ステップ 8 を置き換えて、P が難読化された値を送信できるようにします。

非対話性

私たちが提示したさまざまなプロトコルでは、証明者と検証者間の対話が必要です。これは、プロトコルの正しさが検証者によって選択された秘密の値 s と に依存するためです。

上記のプロトコルのいずれかを別の検証者 V' で繰り返したい場合、V' は新しい値 s' と ' を選択する必要があります。V によって生成された値を使用すると、P が V と共謀し、V が値 s と を P に明らかにした場合に、P が不正行為を行うことが可能になる可能性があります。

上記の状況を回避するには、プロトコルを非対話型にする必要があります。これは、パブリックで信頼され、再利用可能なパラメーターを使用することで実現できます。これは、ジェネレーター g を使用してこれらのパラメーターを難読化することで実現できます。それにも関わらず、使用されている難読化技術が準同型であっても、隠蔽された値の積を使用した明確なメッセージの追加のみが許可されますが、難読化されたドメイン内で明確な値の積を実行することは許可されず、このステップは検証時に重要です。多項式とその根の正しさ。

この問題を解決するペアリングを紹介します。ペアリングには次のプロパティがあることを思い出してください。

このプロパティにより、難読化されたドメイン内の製品の同等性をチェックできます。

したがって、プロトコルを非対話型にするための最初のステップは、秘密のランダム値 s と を取得し、それらを難読化することです (g^、、)。

これらの累乗を計算すると、秘密の値 s と を削除し、Common Reference String (CRS) として知られる難読化された値をブロードキャストできます。CRS 値は通常、次のように保存されます。

1. 評価キー: (、)。
2. 検証キー: (g^, g^{t(s)})。

最終プロトコル: 多項式の知識のための zk-SNARK

ここで、ターゲット多項式 t(x) が与えられた場合に、n 次の多項式 p(x) に関する知識を証明するための zk-SNARK を定義します。

パラメータ設定

1. 各当事者は 2 つの秘密値 s と をランダムに受け取ります。
2. 各当事者は g、、 を計算します。
3. 値 s と は破棄されます。
4. 1 つは評価キー ( と ) をブロードキャストします。
5. 1 つは検証キー g^, g^{t(s)} をブロードキャストします。

1. P が p(x) を知っていると仮定すると、P は多項式 h(x) を計算します。
2. P は、p(x) と h(x) を評価し、評価キーに含まれる値を使用して gp(s) と gh(s) を計算します。
3. P は、評価キーを使用して値 g^{p( · s)} を計算します。
4. P はランダムな値 をとります。
5. P は証明 π = (g^{ · p(s)}, g^{ · h(s)}, g^{ · p( · s)}) = (g^{ · p }、g^{ · h}、g^{ · p'})。

V が π = (g^{ · p}, g^{ · h}, g^{ · p'}) にアクセスできると仮定すると、次のことを確認します。

私たちは、zk-SNARK の定義に必要なすべての特性を満たすプロトコルを設定することができました。簡潔さ (証明はある点で多項式をチェックするだけであるため)、ゼロ知識、および非対話型 (CRS を使用するため) ）。

CRSの生成

Zk-SNARK は、Common Reference String (CRS) として知られる非表示の値のセットを使用することで非対話型にできます。これらの非表示の値 (この場合は と の形式) は、秘密の値 s と に由来しており、非表示の値が導出された後はこれらの値を破棄する必要があります。CRS の生成が重要であることに注意してください。CRS の生成を 3 番目の参加者に委任する場合、参加者が値 s と を破棄することを誰もが信頼する必要があるからです。サードパーティは単一障害点になります。

単一障害点を回避したい場合は、値 s と が回復できないことを保証するために、単一の正直な参加者だけで十分な CRS を生成する分散方法が必要です。

前の例で構築した SNARK に CRS を使用してみましょう。s と を秘密として使用し、隠れた値と累乗 g^、、 を計算する必要があることを思い出します。

新しいプロトコルでは、単一のサードパーティによって生成された値 s と を、3 人のユーザー A、B、C によって生成された値 s_{ABC} と _{ABC} に置き換えます。メカニズムを n 人のユーザーに拡張するのは簡単です。 。

プロトコルは次のとおりです。

1. ユーザー A はペア (sA、A) を生成し、計算してブロードキャストします。

3. B ブロードキャスト:

4. C はランダムなペア (sC、C) を取得し、計算してブロードキャストします。

このプロトコルは、この値のペアを知る参加者が一人もいない状態で、s_{ABC} = s_A · s_B · s_C および _{ABC} = _A · _B · _C の隠し値を生成します。

それにもかかわらず、これらの隠された値が正しく計算されたことを参加者が確認できるプロトコルが必要です。各ユーザーによって生成された値が要件を満たしていること、つまり、値のセット が各ユーザーの s 値の gs 乗であること、およびセット が正しく計算されていることを確認する必要があります。そのために、各 (g^s)^i が実質的に gs の i 乗であることを確認します。これは、次の等式が成り立つことを確認することで実行できます。このチェックは、各参加者 U に関連付けられたすべての値 sU および U に対して各参加者によって実行されます。

必要な検証はこれだけではありません。また、各参加者が前の参加者からの正しい値を使用していることを確認する必要もあります。これを行うには、各参加者は、あるユーザーの非表示のパブリック パラメーターを別の参加者の出力と組み合わせて使用​​します。たとえば、C は、以下を検証することによって、A からの CRS 情報を使用して、B によって生成された CRS の中間値をチェックできます。

結論

これまでのところ、多項式の知識を証明するために、完全な詳細を備えた SNARK を最初から作成する方法を学びました。次回の最後の投稿では、上記の構築をあらゆる計算に拡張します。そのために、2 次算術プログラム、QAP、およびランク 1 制約システム R1CS という 2 つの重要な概念を導入します。ただし、後者については特に紹介しません (潜在的なメッセージとして表示されます)。

参考文献

ジョルディ・エレーラ・ジョアンコマルティ、クリスティーナ・ペレス・ソラ、クリプトグラフィア・アヴァンサダ。講義ノート。カタルーニャ放送大学、2022年。