1 はじめに
ZK-SNARK は、エンティティが他の情報を明らかにすることなく、何かが真実であることを証明できる暗号証明システムです。
ZK-SNARK は、ブロックチェーンや検証可能なコンピューティングなど、複数のアプリケーションや分野で役立ちます。注目すべきブロックチェーン アプリケーションの 1 つが ZK-Rollups で使用されています。
ZK-Rollups は、状態遷移の正当性を証明するために ZK-SNARK (または他の暗号証明システム) を利用する他のブロックチェーン (イーサリアムなど) の上に構築された第 2 層ブロックチェーンです。つまり、新しいネットワーク更新が行われる (トランザクションの新しいバッチが追加される) たびに、新しいネットワーク状態が計算され、この状態の有効性の証明が生成されます。重要なのは、この証明を生成するために必要なエンティティは 1 つだけであり、その後は誰でもその有効性を信頼できるということです。
ZK-Rollups によって提供される望ましいプロパティは通常、(i) スケーラビリティおよび/または (ii) プライバシー保護です。スケーラビリティのみが必要な場合、ZK ロールアップは有効性ロールアップと呼ばれることもあります。
イーサリアムの EVM を拡張するように設計された ZK-Rollups で証明を計算するには、ZK-EVM を使用できます。厳密に定義すると、ZK-EVM はゼロ知識証明 (ZKP) の生成を担当する一連の暗号プログラム (回路) ですが、口語的には EVM 対応の汎用 ZK-Rollup 全体を指すこともあります。
2.ZK-SNARKの定義
SNARK は、特定のステートメントが真実であることの簡潔な証拠です。形式的には、特定の問題に対する正しい解決策を生成するアルゴリズムの実行トレースに関する知識を実証します。むしろ、追跡を実行する非公開および非定数値の知識を示します。これらの値は全体として証人と呼ばれることがよくあります。証人の要素、つまりアルゴリズムへの入力の部分は、アルゴリズムの実行前に存在し、実行トレースの他の要素によって決定されないため、独立した証人を構成します。アルゴリズムが解決する問題インスタンスを指定する実行トレースの公開された非定数値は、公開ステートメントと呼ばれます。
ZK-SNARK は、Zero-Knowledge Succinct Non-Interactive Knowledge Argument の略です。
S - シンプルさ
シンプルさ - 証明は「短く」、検証時間は「速い」です。
「短い」証明とは、証明のサイズが証人のサイズに比べて線形以下であることを意味します。
「速い」検証時間とは、検証者の実行時間が (i) 証人のサイズにおいて線形未満であり、(ii) 公的主張において線形であることを意味します。
しかし実際には、「簡潔」であるだけでなく「対数多項式レベル」であることも必要です。
これは、証拠サイズと検証時間は証人の規模にほとんど依存しないことを意味します。
π のサイズが、証人 w のサイズの対数の 2 乗の定数倍 (十分に大きい w の場合) より速く増加しないことを証明します。
証明のサイズは、特定の ZK-SNARK プロトコルによって異なります。 Plonky2 の場合は O(log^2(|w|)) ですが、これは「最悪の」ケースです。たとえば、古典的な PLONK と Groth16 の場合、証明のサイズは O(1) であり、これは定数です。
検証時間 t_v は、証人 w の対数の 2 乗の定数倍を超えてはならず、公開宣言 x のサイズに線形である必要があります (x と w は、どちらか一方のみがサイズを変更する場合に十分な大きさになります)。
N - 非対話型 - 検証者からデータを受信せずにプルーフの生成が行われます。
ARK - 知識証明 - 通常の証明と似ていますが、サウンドは多項式で制限された証明者に対してのみ成立しますが、証明ではサウンドは計算的に制限されていない証明者に対して成立します。次のセクションではサウンドの概念について説明します。
ZK - 知識ゼロ - 証人の開示はありません。
3. ZK-SNARKの特性
ZK-SNARK には、以下に説明する 3 つの主要なプロパティがあります。
完全性: 証明者がアルゴリズムの正しい実行軌跡を知っている場合、検証者は証明者がこの知識を持っていると信じなければなりません。
知識の健全性: 証明者が実際に正しい実行軌跡を知らない限り、証明者はそれを知っていると検証者に納得させることはできませんが、非常に低い確率が存在します。
ゼロ知識: 検証者は、実行軌跡が正しいということ以外、実行軌跡について何も知りません。
4.PLONKish ZK-SNARKプルーフシステム
4.1 PLONKish ZK-SNARK とその機能の概要
ZK-SNARK 証明システムを特定のアルゴリズムに適用するには、有限体上の連立方程式を知る必要があります。これらの方程式は、アルゴリズムの実行軌跡テーブル (実行軌跡を保存するデータ構造）を使用して、計算の整合性を確保します。この方程式系 (制約系とも呼ばれます) を表現するために使用される言語は、算術と呼ばれます。
PLONKish ZK-SNARK 証明システムは、古い証明システムよりも高い表現力を持つ演算を使用します。 1 つ目では、制約変数に対して任意の多項式形式の制約システム方程式を使用できますが、古い証明システム (つまり、R1CS に基づくシステム) では、これらの方程式は 1 次および 2 次多項式の形式でした。この機能により、PLONKish ZK-SNARK 証明システムは証明者の計算効率にプラスの影響を与え、さまざまなアルゴリズムへの適用が容易になります。そのため、近年、古典的な PLONK、Halo2、Kimchi、Plonky2、HyperPlonk など、多くの PLONKish ZK-SNARK 証明システムが登場しています。
Taiko では、KZG 多項式コミットメント スキームに基づいた Halo2 証明システムのバリアントを使用します。
PLONKish ZK-SNARK 証明システムは 3 つのコンポーネントで構成されています。
4.2 コミットメント計画
Promise スキームを使用すると、コミッターは、メッセージ自体を明らかにすることなく、コミッターをメッセージにバインドする Promise と呼ばれる値を公開できます。次に、コミッターはコミットメントを開いて、コミットされたメッセージまたはその一部を検証者に公開し、検証者は公開された情報がコミットメントと一致するかどうかを確認できます。
著者によって、コミットメント スキームを構成するアルゴリズムの数が異なります。ただし、これらのアルゴリズムのうち少なくとも 4 つについては言及する必要があります。
セットアップ: いくつかの初期パラメータを入力として受け取り、セットアップ パラメータを生成します。設定は、(i) コミットする内容 (たとえば、単項多項式コミットメント スキームの場合、コミットする多項式の係数領域と最大次数を指定します)、および (ii) ビット単位のセキュリティ レベルを指定します。セキュリティ レベルは次のように簡単に定義できます。暗号化システムを破るのに O(2^n) 時間がかかる場合、暗号化システムのセキュリティ レベルは n ビットです。
Promise: 設定されたパラメータに基づいてメッセージを生成する Promise。
部分開始: メッセージの選択された部分 (たとえば、一部のパラメーターのコミットされた単項多項式の値) に固有の部分開始証明を生成し、パラメーターを設定します。
検証: 部分的にオープンな構成証明を使用し、パラメーターを設定して、証明者によって公開された情報が、指定されたコミットメントに対応するメッセージの指定された部分であるかどうかを確認します。
*一部のコミットメント スキームでは、「セットアップ」アルゴリズムと「オープン」アルゴリズムが存在しない場合があります (たとえば、ハッシュ関数を使用して大きな値をコミットする場合)。
コミットメント プランには次の特徴がある必要があります。
バインド: 証明者が特定のメッセージにコミットすると、証明者はコミットしたメッセージにバインドされます。
非表示: メッセージに関する情報を一切公開しないという約束。隠蔽は完全なもの、つまり部分的に開いた証明がメッセージの照会されていない部分に関する情報を明らかにしないもの (例: KZG コミットメント)、または非完全なもの、つまり部分的に開いた証明が前述の情報の一部を明らかにするもの (例: FRI ベース) の場合があります。多項式コミットメント)。
コミットメント スキームは、ターゲット オブジェクトに基づいて、単一要素コミットメント、セット コミットメント、ベクトル コミットメント、多項式コミットメントなどのいくつかのタイプに分類できます。
多項式コミットメント スキームは、PLONKish ZK-SNARK 証明システムで直接使用される唯一のタイプです。上記の証明システム (古典的な PLONK、Halo2、Kimchi、Plonky2 など) では、一変量多項式コミットメント スキームが非常に重要です。ただし、現在、多線形多項式コミットメント スキームに基づいた新しい PLONKish ZK-SNARK メソッドがいくつかあります (例: HyperPlonk)。
4.3 インタラクティブな Oracle 証明
インタラクティブなオラクル証明は、検証者が証明者のメッセージを取得するために「オラクルにアクセス」し、確率的な方法でメッセージをクエリでき、証明者のメッセージ全体を読む必要がないインタラクティブな証明です。
4.4 フィアット・シャミールヒューリスティック
Fiat-Shamir ヒューリスティックは、(パブリック コインの) インタラクティブな引数を非インタラクティブな引数に変換する方法を提供します。直感的には、バリデーターのランダムなチャレンジを前のメッセージのハッシュに置き換えるというアイデアですが、詳細は一般に未指定です。
*パブリックコインプロトコルは、バリデーターがランダムな要素のみを送信するプロトコルです。
4.5 PLONK スタイル ZK-SNARK 証明システムの動作原理
ZK-SNARK証明システムでは、修正されたインタラクティブなOracle証明方法が証人の知識を証明するために使用されます。これは、多項式コミットメントを使用してOracleに証明者のメッセージへのアクセスを提供し、Fiat-Shamirヒューリスティックを通じて対話型フリーにします。このセクションでは、指定されたコンストラクターについて詳しく説明します。
ZK-SNARK 証明システムをアルゴリズムに適用するには、対応する制約システムを構築する必要があることを思い出してください。これを構築できるようにするには、アルゴリズムの実行トレース テーブルの構造とその中の定数値を定義します。 「回路」という用語は、定数と対応する制約システムのみが入力された実行トレース テーブルの複雑な構造を指すために使用されます。アルゴリズムの実行インスタンスの ZK-SNARK 証明を生成するには、アルゴリズムの回路と実行トレース テーブル (つまり、定数、証人、および公開宣言値）の組み合わせ。
PLONK スタイルの ZK-SNARK 証明システムで使用される追跡テーブルの構造を考えてみましょう。このようなテーブルのすべての列は 3 つのタイプのいずれかに属し、Halo2 で使用される用語に従って名前を付け、次のように説明します。
固定列 - セルには実行トレース テーブルの定数が含まれます。
インスタンス列 - パブリック宣言値を格納するために使用されます。
提案列 - すべての証人データが保存される場所 (独立した証人の値と計算された秘密の結果を含む)。
要約すると、次のことに注意してください。
実行トレース テーブル (PLONKish タイプ) = 固定カラム + インスタンス カラム + 提案カラム; 回路 = 定数のみを含む実行トレース テーブル + 制約システム; 回路インスタンス = 回路 + テーブル内の監視 + テーブル内のパブリック宣言; 構成: (回路、公開声明、独立した証人値) → 回路インスタンス; ZK-SNARK 証明システムを特定のアルゴリズムに適用 = 回路を記述 + 合成プロセスを定義。
この文脈で「回路」という用語が広く使用されているのはなぜですか?当初、R1CS ベースの ZK-SNARK 証明システムしか利用できなかったときは、出力がゼロでなければならない制約システムを算術回路の形式で表すのが便利でした。 PLONKish SNARK の文脈では、「回路」という用語が歴史的な理由から使用されていると私たちは考えています。とにかく、ZK-SNARK の古いバージョンで使用されていた演算回路を簡単に考えてみましょう。
R1CS ベースの SNARK の算術回路は、有限体上の n 変数多項式を定義し、評価スキームを備えています。最初は、有向非巡回グラフ (DAG) として表されます。
それには以下が含まれます：
パブリック入力 x。パブリック宣言値を指定するために使用されます。
秘密の入力 w、独立した監視値を指定するために使用されます。
有限体の加算と乗算を指定するために使用される算術ゲート。
有理数の分野における算術回路の例を見てみましょう。
下から開始して、図の最も低いゲート、つまり (2 x 4 = 8) および (4 + 11 = 15) を操作し、これらの値を中間値として保存します。
次に、1 行上 (2 行目) に移動し、(前の段階で取得した) 2 つの中間値の合計、つまり (8 + 15 = 23) を計算します。
ゲートは 3 つしかなく、すべて通過したため、最終出力は 23 になります。
PLONKish ZK-SNARK 証明システムが回路インスタンスを合成した後、各インスタンス実行トレース テーブルの列は、次の方法で有限体上の多項式としてエンコードされます。 C_j(x) が列 j を記述する多項式で、ω が 2^k 番目の原始根であるとします。ここで、2^k がテーブル インスタンスの初期の高さよりわずかに大きくなるように k が選択されます。テーブル インスタンスには、2^k 行を含むようにランダムな行 (推奨される列にゼロ以外のセルのみ) が設定され、C_j(ω^i) は j 番目の行の i 番目の行の値に設定されます。指定されたテーブル インスタンスの列。ゼロ知識属性のパディングの役割については後で説明します。
「ω は 2^k 番目の原始根である」という文は、ω^(2^k) = 1 であり、2^k 未満の任意の正の整数 t に対して ω^t ≠ 1 であることを意味します。
制約系は、x の代わりに「x の ω の累乗」を代入して、その中の変数を列多項式から取得した対応する多項式に置き換えることによって、多項式形式に変換されます。
たとえば、制約システム方程式 s(i) * (a(i) * b(i) - c(i+1)) = 0 を考えてみましょう。これは、s(i) がゼロ以外の場合、a(i) * b(i) は c(i+1) に等しくなければならないことを意味します。ここで、a、b、c は推奨列、s は固定列、i は現在の行番号です。
この制約は、次のようにすべての 2^k 行に適用できます。 S(x)、A(x)、B(x)、および C(x) をそれぞれ列 a、b、c、および s の多項式とします。したがって、私たちは次のことを望んでいます。
これは、このセット内のすべての要素が S(x) * (A(x) * B(x) - C(x * ω)) のルートでなければならないことを意味します。したがって、この多項式は次のように割り切れる必要があります。
ω は 2^k 次の原始根であるためです。
Z(x) = x^(2^k) - 1 は、ω によって生成される巡回乗法群の要素であるすべての x について 0 であるため、「消失多項式」と呼ばれます。したがって、S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0 は、上記の制約がすべての 2^k 行に当てはまることを意味します。
P_0(x)、P_1(x)、...、P_m(x) がすべての 2^k 行に適用される制約であり、考慮された多項式 S(x) * (A(x) * B(x) と一致すると仮定します)上記 ) - C(x * ω)) も同様の形式になります。 α が検証者によって有限体からランダムに選択された場合、
これは、非常に高い確率で、これらすべての制約がすべての 2^k 行で満たされることを意味します。この方程式は、次のような商多項式 T(x) を見つけることができることを意味します。
したがって、検証者が、m 個の制約すべてを満たす実行トレース テーブルの内容を非常に高い確率で知っていると信じるためには、ランダムに選択された α に対して、証明者が出現回数 P_0 を持っていることを証明するだけで済みます。 (x)、P_1(x )、...、P_m(x) 内の提案された列多項式と商多項式 T(x) は、この多項式を満たします。検証者は、証明者に、Z(x) の非根点 ζ の中から検証者が選択したランダムな点で特定の多項式の値を見つけ、その点で方程式の両辺を評価するように依頼することでこれを行うことができます。 ζ. 証明者はおそらくこれらの多項式を知っていると思います。この方法は、Schwartz-Zippel 補題によって証明できます。
プルーフの生成を非対話型にするには、対話型バージョンの検証者によって生成されるすべてのランダム値を、Fiat-Shamir ヒューリスティックを使用して取得する必要があります。
証明者をその提案多項式と商多項式 T(x) にバインドするには、多項式コミットメント スキームが使用されます。証明者はこれらの多項式に対してコミットメントを行い、これらのコミットメントを ξ で (または、何らかの制約が行 i および i + q に影響を与える場合は ξ * ω^q で) オープンし、(I) これらのコミットメント、(II) 値を含む証明を作成します。 ξ (または必要に応じて ξ * ω^q 上) での多項式の計算、および (III) 対応する公開証明。実際には、証明を短くするには、複数の開口部を使用します。つまり、すべての多項式点の値に対して小さな証明を生成します。したがって、証明は簡潔です。
ゼロ知識特性を満たすために、証明者によってランダムに選択された行が実行トレース テーブルのインスタンスに追加され、その高さは 2^k 行になります。非表示にするデータが提案列にのみ含まれているため、これらの行には提案列にゼロ以外のセルしかありません。これは、プロポーザル列多項式を構築する前に実行して、コミットメント開始期間中に明らかにされる「パラメータ値」ペアの数が、各多項式にランダムに追加されるペアの数よりも少なくなるようにします。したがって、各プロポーザル列多項式について、コミットメントがオープンされた後にそれを回復するために必要な情報の量は、証人情報の量よりも多くなります。この状況では知識がゼロになります。
前処理フェーズでは、実行回路のすべてのインスタンスが同じ計算の一部を実行します。これには、固定列多項式と多項式コミットメント スキームのコミットメントの設定と計算が含まれます。これらの計算によって生成されたデータの部分は検証者によって使用され、多くの場合検証キーと呼ばれます。同様に、証明キーの概念も定義できます。基礎となる多項式コミットメント スキームによって、前処理フェーズ中に信頼設定が行われるかどうかが決まります。
