This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
zk-SNARKの構築と事例
TL;DR
証明すべき問題-算術回路-R1CS-多項式
多項式の特性により、検証時間が効果的に短縮され、簡素化が実現されます。
簡単に言うと、多項式を導出する過程でさらに 2 つの乱数が選択され、導出された多項式によって検証者が元の多項式の係数、つまり証明者の秘密の入力を取得するのを防ぐことができます。 ZKを実現するために。
証明が始まる前に、第三者、つまり信頼できる設定が導入され、乱数を選択するという検証者の本来のタスクを信頼できる設定に割り当て、検証者と証明者の間の非対話を実現します。
ZK テクノロジーは、過去 2 年間で Web3 分野で大きな注目を集めてきました。 Rollup を皮切りに、さまざまなトラックで ZK テクノロジーを使用しようとするプロジェクトがますます増えています。その中で、SNARK と STARK は最もよく聞かれる 2 つの用語であり、後の段階での ZK テクノロジーの応用をよりよく理解するために、**この記事では、非技術的な観点から SNARK の証明ロジックを簡略化し、その後、 * * Scroll の zk Rollup ** は、zk プルーフ システムの動作を説明するための例として使用されます。 **
この記事は、基本的なロジックを読みやすく説明することを目的としており、専門用語の使用を極力避け、数学的変換などの詳細には触れません。
2012 年 1 月、カリフォルニア大学バークレー校の教授であるアレッサンドロ キエーザは、SNARK に関する論文を共著し、zk-SNARK という用語を提案しました。
zk-SNARK (正式名 Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge) は、ZK テクノロジーを使用した証明システムです。 **SNARK はスキームのクラスの名前であり、SNARK を実装できるさまざまな組み合わせ方法が多数あることに注意してください。 **
※ゼロナレッジ（Zero-Knowledge）：証明者のみが知っている内容が非表示となり、証明者以外は見ることができません。
zk-SNARKが解決する必要があるのは、検証者が証明者のプライバシーを知らずに効率的に計算結果を検証できるかという「計算検証問題」です。
以下では、zk-SNARK の簡略化された構築プロセスを使用して、システムがゼロ知識を組み合わせて効率的な検証を達成する方法を説明します。 **
Zk-SNARK建設
証明する問題を多項式に変換します
簡単に言うと、SNARK のアイデアは、ステートメントが真であるかどうかの証明を、多項式の等式が真であるかどうかの証明に変換することです。
変換プロセス全体: 検証すべき問題 ➡ 演算回路 ➡ R1CS ➡ 多項式 ➡ 多項式間の変換
確認すべき質問➡演算回路
質問が真であるかどうかを計算によって証明するには、まず証明する質問を計算問題に変換する必要があり、あらゆる計算は算術回路として記述することができます。
演算回路は通常、定数、「加算ゲート」、「乗算ゲート」で構成されており、ゲートを重ね合わせることで複雑な多項式を構成できます。
上図の算術回路によって構築される多項式は次のとおりです: (Inp1+Inp2)*(-1) = 出力
実際の問題を演算回路に直すと非常に複雑ですが、単純に「何かの内容を入力し、その内容が回路で変換され、最終的に結果が出力される」と理解することができます。たった今：
演算回路の概念に基づいて、証明を生成するための演算回路を構築します。
この回路には、公開入力 x と秘密入力 w の 2 セットの入力が含まれています。公開入力ｘは、内容が検証者と証明者の双方に知られている証明対象問題の固定値であることを意味し、秘密入力ｗは、内容が証明者のみに知られていることを意味する。
私たちが構築した演算回路は C( x, w ) = 0、つまり回路に x と w を入力し、最終的な出力結果は 0 です。証明者と検証者が回路の出力が 0 で公開入力が x であることを知っている場合、証明者は秘密の入力 w を知っていることを証明する必要があります。
演算回路➡R1CS
最後に多項式が必要になりますが、演算回路を直接多項式に変換することはできず、両者の仲介としてR1CSが必要となるため、まず演算回路をR1CSに変換します。
R1CS、正式名 Rank-1 Constraints (一次制約システム) は、本質的に行列ベクトル方程式である回路を記述するための言語です。具体的には、R1CS は 3 つのベクトル (a、b、c) のシーケンスであり、R1CS の解はベクトル s です。ここで、s は次の方程式を満たす必要があります。
このうち、 は内積演算を表します。
ここでの具体的な数学的変換については、Vatalik: Quadratic Arithmetic Programs: from Zero to Hero を参照してください。
**R1CS の役割は、各ゲート間のベクトルが上記の関係を満たすように、演算回路内の各ゲートの記述を制限することであることだけを理解する必要があります。 **
R1CS➡多項式
R1CS の媒質を取得したら、それを等価な多項式に変換できます。
次の図に示すように、行列と多項式間の同等の変換を実行できます。
多項式
行列に変換する
上記の等価変換の性質に従って、R1CS を満たす行列の場合、ラグランジュ補間法を使用して多項式の各係数を復元できます。この関係に基づいて、R1CS 行列を多項式関係として導出できます。
注: A、B、C はそれぞれ多項式を表します
多項式は、証明したい問題に対応する R1CS 行列制約に対応します。上記の変換を通じて、多項式が上記の関係を満たす場合、R1CS 行列が正しいことを意味することがわかり、証明者がは演算回路にあり、 の秘密の入力も正しいです。
ここまでの問題は次のように単純化されています: 検証者は数値 x をランダムに選択し、A(x) * B(x)=C(x) が true であることを証明するよう認証者に要求します。は、認証者の秘密の入力が正しいことを意味します。
多項式間の変換
複雑な演算回路ではゲートが数万個あり、各ゲートが R1CS 制約を満たしているかどうかを検証する必要があります。つまり、A(x) * B(x)=C(x) が等しいことを何度も検証する必要がありますが、1 つずつ個別に検証するのは効率が低すぎます。一度にゲートの制約?セックス?
理解を容易にするために、P(x) を導入します。P(x) = A(x) * B(x) – C(x) とします。
解がある限り、どんな多項式も線形多項式に分解できることがわかっています。したがって、P(x) を F(x) と H(x) に分割します。つまり、次のようになります。
この場合、F(x) はパブリックです。これは、H(x) = P(x)/F(x) が存在することを意味するため、検証したい多項式は最終的に次のようになります。
A(x) * B(x) – C(x): 証明者のみが知っている多項式の係数、つまり秘密の入力が含まれます。
F(x) : 検証者と証明者の両方に知られている公開多項式、つまり公開入力。
H(x): 証明者は計算によって知っていますが、検証者は知ることができません。
**証明すべき最後の問題は、多項式 A(x) * B(x) – C(x) = F(x) * H(x) であり、すべての x に当てはまります。 **
これで、多項式を 1 回検証するだけで、すべての制約が行列の関係を満たしていることが検証されます。
**ここでは、証明すべき問題を 1 回だけ検証する必要がある多項式への変換を完了し、システムの単純さを実現しました。 **
しかし、この実装の単純さは検証者の検証時間を短縮することなので、証明サイズはどうなるでしょうか?
**簡単に言えば、証明プロトコルではマークル ツリー構造が使用され、証明のサイズが効果的に削減されます。 **
変換プロセス全体が完了すると、当然のことながら 2 つの問題が発生します。
多項式を使用すると証明が簡単になるためです。ゼロ知識証明の問題は、計算が複数の制約を満たすことを検証することであり、多項式は 1 点で複数の制約を検証できます。つまり、検証者は問題を確認するために n 回検証する必要がありましたが、証明の正しさを高い確率で確認するには 1 回の検証だけで済みます。
これは多項式の特性によって決まります。つまり、任意の点での多項式の計算結果は、その一意の恒等式の表現と見なすことができます。 2 つの多項式の場合、それらは有限数の点でのみ交差します。
上記の d 次の 2 つの多項式: A(x) * B(x) – C(x) および F(x) * H(x) について、それらが等しくない場合、それらは最大 d 点のみになります。交差する、つまり d 点の解は同じです。
多項式の変換が完了したら、多項式の証明の段階に入ります。
多項式が成り立つことを証明します
説明のために、多項式 P(x) = F(x) * H(x) を使用します。
さて、証明者が証明したい問題は、すべての x について、P(x) = F(x) * H(x) です。
証明者と検証者による上記の多項式の検証プロセスは次のとおりです。
しかし、よく考えてみると、上記のプロセスにはいくつかの問題があることがわかります。
上記の問題を解決するために、次の最適化を行います。
最適化後も、証明システムでは検証者と証明者の間で対話が必要であることがわかりました。非対話を実現するにはどうすればよいでしょうか?
非対話型の実装
**非対話性を実現するために、SNARK では信頼できる設定 (セットアップ) が導入されています。 **
つまり、証明を開始する前に、ランダムなチャレンジ ポイントを選択する検証者の権利が信頼できる第三者に渡され、第三者がランダム パラメータ λ を選択した後、暗号化された λ が R1CS 回線に置かれます。このようにして、CRS (Common Reference String、パブリック参照文字列) が生成されます。検証者は CRS から自身の Sv を取得でき、証明者は CRS から自身の Sp を取得できます。
なお、λはSvとSpを生成した後に破棄する必要があるため、λが漏洩すると偽検証による取引の偽造に利用される可能性がある。
zk-SNARK ワークフロー
SNARK の構築プロセスを理解した後、証明を生成できる構築した演算回路に基づいて、zk-SNARK の証明プロセスは次のようになります。
※設定：（C回路、λ）＝（Sv、Sp）
回路Ｃとランダムパラメータλにより、後続の証明者と検証者が使用するランダムパラメータＳｖ、Ｓｐが生成される。
証明者は、ランダム パラメーター Sp、公開入力 x、および秘密入力 w を通じて証明 Π を計算します。
検証者は、ランダム パラメーター Sv、公開入力 x、証明 Π を通じて C(x,w)=0 が存在するかどうかを検証します。同時に、証明が回路 C によって計算されるかどうかを検証します。
ここまででzk-SNARK全体の説明は終わりましたので、実際の適用事例を見ていきましょう。
ケース: Scroll の zk Rollup を例に挙げます
証明システムの役割は、証明者が検証者に 1 つのことを信じるよう説得できるようにすることです。
zk証明システムの場合、zkアルゴリズムによって計算されたZero-Knowledge Proof（ゼロ知識証明）が正しいと検証者に信じ込ませることです。
Scroll の zk Rollup を例として、zk プルーフ システムの動作を説明します。
ロールアップとは、オフチェーンの計算とオンチェーンの検証を指します。 zk ロールアップの場合、トランザクションがオフチェーンで実行された後、証明者はトランザクションの実行後に生成された新しい状態ルートの zk 証明書を生成し、その証明書をオンチェーン検証のために L1 ロールアップ コントラクトに渡す必要があります。
zk Rollup には 2 種類のブロックがあることに注意してください。
※L1ロールアップブロック：イーサリアムに送信されるブロック ※L2ブロック：L2上でユーザーが送信したトランザクションで構成されるブロック
以下は、Scroll の zk Rollup のワークフローです。
上記のプロセスからわかるように、Roller はシステム内の証明者であり、Rollup コントラクトが検証者です。 Roller はオフチェーンで実行されるトランザクションの zk 証明を生成します。ロールアップ コントラクトは証明を検証し、検証に合格すると、ロールアップ コントラクトは送信されたステート ルートを新しいステート ルートとして直接採用します。