ゼロ知識証明テクノロジーの革命的な進歩: Nova アルゴリズムの詳細な調査

金色财经_

2023-09-11 15:35:16

少し前、私はゼロ知識証明技術に関する本を翻訳していました。先月末に基本的な内容を翻訳しました。翻訳には予想よりもかなり時間がかかりました。現在、本書のいくつかの誤記について著者と協議し、最終稿の準備を進めています。

とにかく、ようやく何か新しいものを見る時間ができました。 Novaアルゴリズムから始めましょう~

Nova アルゴリズム関連情報

Nova アルゴリズムを理解するには、次の 3 つの情報が役立ちます。

1.ノバ紙: 2. Nova の潜在的な攻撃とそれに対応する修正: 3. Nova の潜在的な攻撃に関する理解の要約:

この記事は、上記の情報を理解して要約したものです。 **この記事の一部の写真は上記の情報から引用したものであり、この記事では個別にラベルを付けません。 **

IVC から始めましょう

Nova アルゴリズムは、IVC (Incrementally Verifiable Computation) 用の新しいゼロ知識証明アルゴリズムです。 IVC、つまり、同じ関数が前の出力を次の入力として繰り返し計算します。 F 関数の反復計算プロセスは次のとおりです。

z0 は初期入力であり、F 関数の計算によって生成された結果は次の F 関数の入力として使用されます。

リラックス R1CS とスラックコミットメント R1CS

周知のとおり、R1CS はゼロ知識証明技術における回路制約を表現したものです。緩和された R1CS は、R1CS の拡張形式と見なすことができます。 R1CS に基づいて、スカラー u と誤差ベクトル E が加算されます。緩和された R1CS のインスタンスは (E, u, x) で表されます。

緩和されたコミットメント R1CS は、緩和された R1CS に基づいて E ベクトルと W ベクトルをコミットします。スラックコミットメント R1CS のインスタンスは (\bar{E}, u, \bar{W}, x) で表されます。ここで、x と u はパブリック変数です。

折りたたみスキームのための R1CS から緩和された R1CS への拡張。緩和された R1CS の観点から見ると、R1CS は特殊なケースであることに注意してください。つまり、R1CSは「特別な」スラックR1CSでもあります。

折りたたみ方式

直感的に言えば、リレーション R の折りたたみスキームは、リレーション R に準拠する 2 つのインスタンスを複合リレーション R の新しいインスタンスに「折りたたむ」ことです。 Slack R1CS/Relax Commitment R1CS は同様のフォールドを実行できます。折り方はどちらも似ています。 Slack Commitment R1CS の折りたたみスキームは次のとおりです。

折り方全体は 4 つのステップで構成されます。最初のステップでは、証明者 P はクロス項目 T のコミットメント \bar{T} を検証者に送信します。 2 番目のステップでは、検証者はランダムなチャレンジ r を証明者に送信します。 3 番目のステップは、証明者と検証者の両方が実行する必要があるコミットメントの折りたたみです。 4 番目のステップでは、証明者が単独で実行し、2 つのインスタンスの E ベクトルと W ベクトルを折り畳みます。

拡張関数 F' (引数付き関数)

折りたたみスキームでは、折りたたまれた R1CS インスタンスが緩和されます。それでは、これらの緩和された R1CS の例によって証明された計算は何でしょうか?明らかに、これらの計算には折り畳み計算が含まれます。これらの計算は、IVC 計算における F 関数だけでなく、拡張関数 F' とも呼ばれます。拡張関数 F' の計算は主に 2 つの部分で構成されます。

IVC の 1/F 関数

2/ R1CSインスタンスのフォールディング計算

理想的な外観

上記を理解すると、折りのプロセスを想像できます。

このうち、circuitは拡張関数F'に対応する回路である。 acc{1,2,3,4,5,6} はスラックコミットメント R1CS インスタンスです。この回路には 2 つの計算があります: 1/ acc1+acc2->acc3 など、コミットメント R1CS インスタンスの折りたたみを緩和します。 2/ F 関数を計算して、state1 から state2 に、次に state2 から state3 に状態を変更します。

拡張関数 F' に対応する回路自体が R1CS インスタンスであり、緩和された R1CS インスタンスとして表現できることに注意してください。それが図の acc4 と acc6 です。「要約」は、スラック R1CS インスタンスをスラックコミット R1CS インスタンスに変換することです。

2 番目の回路の入力を注意深く見ると、acc3 はフォールディング後の緩和コミットメント R1CS インスタンスであり、acc4 は acc3 が正しいフォールディング結果であることを証明する緩和コミットメント R1CS インスタンスです。これら 2 つのインスタンスは次の折り畳みに入り、acc5 を生成します。 acc3 と acc4 が満足可能なスラックコミットメント R1CS インスタンスである場合、acc3 は 2 つの満足可能なスラックコミットメント R1CS インスタンスから折り畳まれることを意味すると想像できます。つまり、acc1 と acc2 は満足可能なスラックコミットメント R1CS インスタンスです。この種の信頼性は段階的に「順方向」に推定できるため、各回路の F 関数の計算が正しいことが証明されます。一般に、特定の回線に対応する 2 つのスラックコミットメント R1CS インスタンスの充足性により、以前のすべての IVC 計算が正しいことが証明されます。

本当の姿

ゼロ知識証明に詳しい友人は、楕円曲線が多項式コミットメントスキームでよく使用されることを知っています。スカラー領域上の対応する多項式コミットメントは、楕円曲線の基本領域によって表されます。 R1CS 回路は通常、スカラードメインで表されます。よく見てください、上の図の「要約」にはドメイン変換が含まれています。つまり、サーキットに対応するスラックコミットメント R1CS インスタンスをフォールドしたい場合は、それを別のサーキットに「フォールド」する必要があります。このとき、楕円曲線サイクルを導入する必要があります。2 つ以上の楕円曲線の間で、一方の曲線のスカラー領域は他方の曲線の基底領域と同じです。偶然にも、この曲線のスカラー領域は次の曲線と同じです。前の曲線のベースドメイン。このような楕円曲線ループを使用すると、「理想的な外観」を実現できます。

折り工程全体を 2 つの回路に分けて折ります。上部は回路 1 の折り目、下部は回路 2 の折り目と呼ぶことができます。 2 つの回路間の関係の正式な表現は、論文「Nova に対する潜在的な攻撃とそれに対応する修正」の 8 ページにあります。 U はフォールドインスタンスを表し、u は R1CS インスタンスに対応するリラックスインスタンスを表します。サーキット 1 はサーキット 2 に対応するスラックコミットメント R1CS インスタンスを折りたたむのに対し、サーキット 2 はサーキット 1 に対応するスラックコミットメント R1CS インスタンスを折りたたむことに注意してください。回路 2 の主な目的は、回路 1 に対応するスラックコミットメント R1CS インスタンスを崩壊させることであり、回路内の関数計算は無意味です。代わりに、F 関数が回路 1 に実装されています。「理想的な外観」と組み合わせると、U{i+2}^2、u{i+2}^1、u{i+2}^2、U{i+2}^1 の充足可能性を大まかに推測できます。は証明の重要な部分です。

それは、「回路」が 2 つの部分に分割され、それぞれの回路がもう一方の回路の中に折り畳まれているからです。インスタンス間にはバインディングの問題がいくつかあります。u インスタンスと U インスタンスの間のバインディング、および 2 つの回線間を通過する u インスタンスのバインディングです。これらのバインディングの問題を解決するために、x_0/x_1 パブリック変数が回路に導入されます。ここで、x_1 は、u インスタンスにバインドされた回路出力 U インスタンスと現在の F 関数の出力を指定します (目的は、回路構成は簡略化しているため、図には反映されていません）。 U インスタンスの H_1 結果が回路に導入され、u インスタンスが満足可能であれば、x_0/x_1 は実数かつ信頼できる、つまり U に「束縛されている」と考えます。 x_0 は入力 u と U の間のバインド関係を確立し、x_1 は出力 u と U の間のバインド関係を確立します。

たとえば、回路後半の入力として u{i+1}^1 を使用すると、回路 2 を通過し、その出力は u{i+1}^2.x0 = u{i+1 }^1.x1、したがって、回路の上部に入力されるとき、u{i+1}^2 が満たされる場合、その x_0 は U_{i の H1 の結果と等しくなるはずです。 +1}^2。これは回路 1 でチェックされます。このようにして、2 つの回路間で正しいインスタンスが渡されることが保証されます。

IVC の証明

IVC が特定の反復で正しく計算されていることを証明するには、次の情報を論理的に証明する必要があります。

次の図に示すように、4 つのインスタンスが満たされることを証明することに加えて、2 つの x1 の間の結合関係を証明することも必要です。

この情報が正しいかどうかを確認するには、追加の証明回路の実装が必要です。つまり、IVC 計算の証明は回路の証明となります。繰り返し回数が多い計算であれば、本来は回路内で繰り返しを1回ずつ行う必要があったと考えられますが、今回は4つの回路インスタンスの充足性と結合関係を検証するだけで済みます。パフォーマンスの向上は大幅です。

攻撃とアルゴリズムの修正

上の図を見て直感的に思うのですが、上の回路と下の回路のインスタンスは「分離」されており、拘束力が無いように感じます。実際、これが攻撃の構造です。

偽造された U_i^1 と U{i+1}^2 は、偽造されていますが、充足可能なインスタンスです。 u{i+1}^1 を鍛造し、鍛造された U インスタンスに対応するように x_0 と x_1 を変更します。明らかに、u{i+1}^1 インスタンスは満たされません。満たされていない場合でも、回路 2 の回路は満たされますが、出力 U{i+1}^1 インスタンスは満たされません。 u{i+1}^2 が正常に構築された場合、回路 1 は満足のいく u{i+2}^1 および U_{i+2}^2 を構築し、x1 の結合関係を満たすことができます。このようにして、最終的な偽造証明の半分が最初に構築されます。対称性を通じて、下半分の出力インスタンスを構築できます。 2 つの構築の結果を「つなぎ合わせる」ことによって、IVC 計算の証明を偽造することができます。

修正されたチェックロジックは次のとおりです。