ゼロ知識証明の力:zk-SNARKsの深堀り

この記事では、このテクノロジーを数学を使用して解読し、情報を明かすことなく知識の真実を証明する方法を示します。

編纂:DODOリサーチ

著者: 0xAlpha 共同創設者 @DeriProtocol

紹介

Zk-SNARK(ゼロ知識簡潔な知識の非対話的議論)は、検証者が特定の関係を満たす特定の知識(証人と呼ばれる)を持っていることを、知識自体に関する情報を明らかにすることなく確認することを可能にします。

特定の問題に対して zk-SNARK を生成するには、次の 4 つの段階があります。

• 問題(または関数)を演算回路に変換します。
• 次に、この回路を行列方程式に変換します。
• この行列方程式は、さらに、特定の最小多項式で割り切れる多項式に変換されます。
• 最後に、この分割可能性は、証明が行われる有限体上の楕円曲線点で表されます。

最初の 3 つのステップは、元のステートメントの表現を変換するだけです。 最後のステップでは、準同型暗号化を使用して、3番目のステップのステートメントを暗号化された空間に投影し、証明者がその中のミラーリングされたステートメントを検証できるようにします。 このプロジェクションが非対称暗号化を利用していることを考えると、手順 3 のステートメントから元のステートメントにバックトラックして、ゼロ知識の漏洩を確実にすることは現実的ではありません。

この記事を読むために必要な数学的背景は、STEM大学1年生に期待される代数レベルに匹敵します。 挑戦的な唯一の概念は、楕円曲線暗号かもしれません。 これに慣れていない人のために、その逆関数が未解決のままであることを念頭に置いて、特別な基底を持つ指数関数と考えることができます。

この記事では、次の表記規則に従います。

行列: 太字の大文字 (例: ある;明示的な形式で記述 \
ベクトル: 矢印付きの小文字で、明示的な形式 [ ];既定では、すべてのベクトルは列ベクトルです \
スカラー: 通常の文字で表されます

例として、次の質問を取り上げましょう。

f(x)=x^3+x^2+5 (1)

アリスが真実を知っていることを証明したいとします。 アリスが証明のためにzk-SNARKを生成するために必要な手順全体を見ていきます。
この質問は、制御フロー (if-then-else など) を伴わないため、単純すぎるように思えるかもしれません。 ただし、制御フローを持つ関数を算術式に変換することは難しくありません。 たとえば、次の問題 (プログラミング言語では "関数") について考えてみます。

f(x, z):
if(z == 1):
x xx + xを返します。バツ+5
然も無くば：
xx+5 を返します。

この問題を次の算術式に書き直すと(zが(0,1)に属すると仮定)、式(1)ほど複雑ではありません。

f(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)

この記事では、式(1)を議論の基礎として使用し続けます。

ステップ1:演算回路

式 (1) は、次の基本的な算術演算に分解できます。

これは、次の演算回路に相当します。

また、式(2)を4つの「一次制約」のセットと呼び、各制約は回路内の算術ゲートの関係を記述します。 一般に、n 個の主制約のセットは、次に説明する 2 次演算プログラム (QAP) として要約できます。

ステップ2:マトリックス

まず、「witness」ベクトルを次のように定義しましょう。

ここで、Y、S1、S2、およびS3は、式(2)のように定義される。
通常、m 個の入力と n 個の演算ゲート (つまり、 n-1 の中間ステップと最終出力)、この証人ベクトルは (m+n+1) 次元になります。 実際のケースでは、数値 n が非常に大きくなる可能性があります。 たとえば、ハッシュ関数の場合、n は通常 1000 単位です。

次に、3つのn(m+n+1)行列A,B,Cを構築して、式(2)を次のように書き直します。

式(3)は、式(2)の別の表現であり、各セット(ai、bi、ci)は回路内のゲートに対応します。 これは、行列方程式を明示的に展開することで確認できます。

したがって、LHS=RHSは式(2)とまったく同じであり、行列方程式の各行は主要な制約(つまり、回路内の算術ゲート)に対応します。

構築の手順 (A、B、C) は省略しましたが、実際には比較的簡単です。 (A, B, C)、つまり(ai, bi, ci)の各行の内容を決定するために、対応する主要な制約に従ってそれらを行列に変換するだけで済みます。 最初の行を例にとると、最初の主制約 x に x を掛けたものを s1 に等しくするには、[0,1,0,0,0]、[0, 1,0,0,0]、[0,0,0,0,1,0,0] にベクトル s を掛ける必要があることが簡単にわかります。

以上で、演算回路を行列式(3)に変換することに成功しました。 同時に、マスタリングする必要があるオブジェクトも証人ベクトルsに変更しました。

ステップ3:多項式

それでは、z に関する多項式の集合を定義する n(n+m+*1) 行列 PA を作成しましょう。

関数が {1, 2, 3, 4} で次の値を取るようにすると、条件が満たされます。

次に、Aを次のように書き直すことができます。

これらは、従来の方法を使用して解くことができる 6 つの変数を含む 4 組の線形方程式です。 ただし、この場合にPAを解くより効率的な方法は、問題の特殊性を利用するラグランジュ補間です。 ここでは、少し面倒ですが簡単なPAを解くプロセスをスキップします。

同様に、PBとPCをBとCに分けて構築します。次に、行列方程式を次のように書き直すことができます。

各行を個別に観察すると、これら 4 つの行が 4 つの異なるポイントで評価された同じ式に対応していることがわかります。 したがって、上記の行列方程式は次と同等です。

ステップ3:楕円曲線ポイント

式 (4) を次のように書き換えます。

ここで、i(z)=1 は、方程式を統一するために使用される z の自明な 0 次多項式にすぎません - すべての項は 2 次です。 その必要性は、まもなく明らかになるでしょう。 この方程式には、z の多項式の加算と乗算のみが含まれていることに注意してください。

算術演算、加算(+)と乗算(X)も、楕円曲線点の有限場の対応する演算にマッピングされることに注意してください。 記号 と は、混乱を避けるために使用され、これらが再定義されたフィールド操作であることを示します。

次に、実際の手順について詳しく説明します。

楕円曲線暗号

楕円曲線の一般理論は、この記事の範囲をはるかに超えています。 本明細書において、楕円曲線は素体 Fp から関数 E への写像として定義され、ここで E は y^2=x^3+ax+b となるような点を含む (楕円曲線点、略して ECP と呼ばれる)。

ここまでは通常の算術について説明してきましたが、素数体に移行する場合、数値の算術演算はモジュラ演算を使用して実行されることに注意してください。 たとえば、a+b=a+b(mod p) のようになりますが、ここで p は Fp の次数です。

一方、2つの楕円曲線点の加算は、次のように定義されます。

具体的には、2つのECPのPとQを添加すると、次のようになります。

線PQと曲線Rの交点を求め、それを-(P+Q)と定義します。
曲線上のRの「ミラー」点R'に反転します。
したがって、楕円曲線点P+Q=R'の加算を定義します。

このルールは、1 つの ECP の追加が使用される特殊なケースにも適用され、その場合はその点への接線が使用されることに注意してください。

ここで、点Gをランダムに選択し、数値1をそれにマッピングするとします。 (この「初期マッピング」は少し恣意的に聞こえます。 これについては後ほど説明します)。 そして、Fp に属する任意の n について、次のように定義します。

E(N)=G+G+G+.....+G=G に n を掛けた値

演算式があります。 演算 +G を "generator" (g と表記) として定義します。 この場合、上記の定義は以下と同等です。

加算を定義すると、次の線形関係が明らかになります。

したがって、Fp の線形関係 (または制約) は、このマッピングによって暗号化された空間 B に保持されます。 たとえば、Fp の方程式 l + m = n は次のようになります。

しかし、アリスが証明したい方程式(5)は二次形式なので、十分に線形ではありません。 二次項を扱うためには、暗号化された空間で乗算を定義する必要があります。 これはペア、または双一次マップと呼ばれ、次のセクションで説明します。

バイリニア マップ

G1、G2、GT が素数次数 g のグループであるとします。 ペア関数、または共一次写像は、次のように定義されます。

共通参照文字列

これを「証明の鍵」(PK)と呼んでいます。 E()内のベクトルの表現は、楕円曲線の点のベクトルとして理解されるべきであり、各点は対応するベクトル要素からマッピングされることに注意してください。 したがって、これらの11個のベクトルは、実際には62(= 4 2 + 6 3+6 3 +6 3)の楕円曲線点で構成されています。 これらの 62 個の ECP は、証明者である Alice に提供されます。 一般的なシナリオでは、m 個の入力と n 個の主制約がある問題の場合、PK には 2n + 3(m+n+1)*3 = 11n + 9m + 9 個の ECP が含まれます。

同時に、次の計算が実行されます。

このプロセス全体を「検証キー」(VK)と呼びます。 ここでは 7 つの楕円曲線点 (ECP) のみが関与しており、検証者に提供する必要があります。 問題に関与する入力と主要な制約の数に関係なく、VK は常に 7 つの ECP で構成されることに注意してください。

さらに、「信頼できるセットアップ」とPKとVKを生成するプロセスは、特定の問題に対して一度だけ実行する必要があることに言及する価値があります。

証明と検証

公開鍵 (PK) を取得したら、Alice は次の楕円曲線点 (ECP) を計算します。

これらの9つの楕円曲線の点は、知識のゼロ知識の簡潔な非対話的な議論(zk-SNARK)にとって重要です。

アリスは基本的に、公開鍵の楕円曲線の点に対して線形結合を実行しているだけであることに注意してください。 これは特に重要であり、検証中に厳密にチェックされます。

さて、アリスはzk-SNARKの証明を提示し、最後に3つのステップで行われる検証プロセスへと導いてくれます。

まず、最初の 8 つの楕円曲線の点が、共通の参照文字列内のそれらの点の線形結合であることを確認する必要があります。

免責事項：

1. この記事は[chaincatcher]から転載しています。 すべての著作権は原作者[0xAlpha Co-founder @ DeriProtocol]に帰属します。 この転載に異議がある場合は、 Gate Learn チームに連絡していただければ、迅速に対応いたします。
2. 免責事項:この記事で表明された見解や意見は、著者のものであり、投資アドバイスを構成するものではありません。
3. 記事の他言語への翻訳は、Gate Learnチームによって行われます。 特に明記されていない限り、翻訳された記事を複製、配布、盗用することは禁止されています。