この記事の著者である Dongze は、Ambi テクノロジー コミュニティの小さなパートナーです。彼は現在スタンフォード大学で勉強しており、研究の方向性は暗号化です。この一連の記事は、スタンフォード大学の有名なコース「CS」に関する著者の研究ノートから来ています。 251: 暗号通貨とブロックチェーン技術」。このコースの講師は、暗号学のマスターである Dan Boneh です。
記事の最終号が発行された後、非常に多くの友人がこの記事を読んで気に入ってくれたことに非常に驚きました。それでは、このエピソードを続けましょう！今回はSNARKに焦点を当ててみましょう。
前回の記事を読んだ友人は少し困惑すると思います。なぜこんなに簡単に証明を作成し、長いメッセージを証明できるのでしょうか?私も授業前は同じ疑問を抱き、これは「ブラックテクノロジー」ではないかとさえ思っていましたが、この記事を読めばこの「ブラックテクノロジー」をコントロールする方法が分かると思います。
最初のレベルのタイトル
SNARKの4段階構造
副題
最初のステップ: 有限体を決定する
構築する前に、まず、計算したいすべての数値を含めることができる有限体 (有限体) を決定する必要があります。平たく言えば、非常に大きな数値 p を選択する必要があり、この数値が解決したい問題内のすべての数値よりも大きくなるようにする必要があります。
以前に RSA 暗号化について学んだことのある友人は、この概念に精通しているかもしれません。有限体とは、すべての数値に上限を追加し、数学システム全体の計算空間を決定するものです。これはコンピューターの計算空間と似ています。数値を格納する変数を作成したい場合は、数値を格納する変数を作成するかどうかを考える必要があります。 uint32_t (32 ビット)、または uint64_t (64 ビット) と同じが必要です。有限体を超えるすべての値は直接オーバーフローし、その後戻って 0 から始まります。
数学の世界では、この特性を満たす計算空間は実際に数多くありますが、最も一般的なのは、RSA アルゴリズムで使用される大きな素数を法とする正の整数 (integer mod p) です。前述の数値 p を見つけると、実際には大きな素数になるため、それを使用して計算空間を生成できます。
副題
ステップ2: 演算回路を構築する
デジタル空間を見つけたら、次にやるべきことは、証明したい問題を演算回路で表現することです。
数学演算回路とは何ですか?まず従来の論理回路を見てみましょう。
上の図は、NAND ゲート (NAND) 回路を示しています。この回路の有用性についてあまり知らなくても、2 組の入力信号がそれぞれ AND と OR の 2 つの基本論理ゲートを通過することがわかります。 AND や OR などの基本的な論理ゲートは論理回路の基本的な構成要素であり、スプライシングやスタッキングによって複雑なロジックを実装できます。
算術演算回路についても同様ですが、基本モジュールが論理ゲートから算術演算に変更されています。加算と乗算は最も基本的な算術演算であるため、加算と乗算によって他のすべての計算方法をほぼ実現できるため、算術演算回路の基本モジュールとして「加算ゲート」と「乗算ゲート」を選択できます。算術ゲートを重ね合わせることで、複雑な多項式の「回路」を構築できます。
演算ゲートをよりよく理解するために、上記の NAND ゲートを論理回路から算術演算回路に変換してみましょう。 (Inp0とInp1は元の論理回路と同じと仮定すると、1/0論理信号が入力されます。)
まず AND ゲートを見てみましょう。AND は実際には非常に単純です。なぜなら、AND の結果が 1 になるのは、Inp0 と Inp1 の両方が 1 の場合のみだからです。私たちは、乗算ゲートが AND ゲートの完全な代替品であることをすぐに発見しました。乗算の結果は、両方の入力が 1 の場合にのみ 1 になります。
AND を解いた後、NOT を変換しましょう。NOT は実際には非常に単純です。入力信号は 0 か 1 のみであり、入力信号が 1 から減算される限り、結果は逆になります。加算と乗算しかないため問題が発生することに注意してください。そのため、減算を実装する必要がある場合は、最初に入力信号に定数 -1 を乗算する必要があります。
このような変換を経て、論理回路をデジタル論理回路に変換することに成功しました。同時に、AND と NOT を構築する方法をすでに知っているため、理論的にはこれら 2 つの部分をモジュール化し、複雑なロジックを接続することができます。
これを見ると、演算回路が非常に単純で、論理回路への変換も非常に簡単であるように感じられるかもしれません。しかし実は、これは演算回路の入力が論理回路と同じ0か1であると仮定してきたからです。実際のシナリオでは、演算ゲートの入力値が非常に大きくなる可能性があります (有限フィールドの選択のサイズによって異なります)。だから私たちは方法を見つけなければなりません動作回路への入力を制限する, そのため、機能的には論理回路と同じであるだけでなく、入力値に 2 つの数値 [0,1] のみを取ることができます。
しかし、算術ゲートを使用してそのような関係を表現するにはどうすればよいでしょうか?数学演算回路は実際には複素多項式であるため (たとえば、上図の NAND 回路は Out = 1 - Inp0 * Inp1 になります)、この質問を変形できます。多項式を作成できるか、入力が [0,1] の値の範囲を満たす場合にのみ、0 が出力されますか?最後に、この要件を満たす多項式があることがわかりました。
上記の式の文字列は、数値 n がこの範囲にある場合にのみ、次の多項式が 0 を出力することを意味します。つまり、この多項式から変換した演算回路に上記のInp0とInp1を接続すれば、この演算回路の出力結果が 0 であれば、上記の NAND 演算回路の出力も正しいことがわかります。
上記の値を制限する多項式では 1 つの入力しか制限できないのに、入力が 2 つあるのに、それらの値の範囲を同時に制限するにはどうすればよいのかと疑問に思う人もいるかもしれません。実際、答えは非常に簡単で、同じ多項式をコピーして 2 つを加算するだけです。
これら 2 つの回路では、制約回路の出力が 0 であることを確認するだけで、NAND ゲート回路は正常に動作します。
注意すべき点の 1 つは、論理ゲートは算術ゲートから構築されているため、その論理が動作が非常に遅い副題
ステップ 3: 証明可能な数学演算回路への変換
デジタル計算回路の概念があれば、さまざまな回路モジュールをつなぎ合わせて、証明として使用できる計算回路を生成できます。
まず定義しましょう証明に使えるデジタル演算回路 C(x, w)、具体的な構造は次のとおりです。
簡単に言えば、この回路 C には 2 組の入力があります。
x というラベルが付いた最初の入力セットを、パブリックインプットつまり、誰もが x の値を知ることになります。この x は通常、証明したい問題の特性といくつかの固定された環境変数を表します。
2 番目の入力セットは w と呼ばれます。秘密の入力、証人としても知られています。この一連のデータは、実際に証明を提出した当事者に対する答えであり、証明を提出した当事者だけがそれを知り、他の人はそれを知ることはできません。
C の回路ができたときの目標は次のとおりです。C(x, w) = 0 であることを証明する。言い換えれば、A と B が算術演算回路 C の出力が 0 であり、パブリック入力が x であることを知っているとすると、A は、この出力を構成するプライベート入力値 w を知っていることを証明する必要があります。
この C(x, w) の概念を上記の NAND ゲートの例に置き換えると、NAND ゲートだけでは証明用の回路として十分ではないことがわかります。証明したい問題を再定義できます。NAND ゲートの出力が 0 で、入力 Inp0 の 1 つが 1 であることがわかっている場合、A は、別の入力 Inp1 の値を知っていることを証明したいと考えています。この証明のプロセスでは、NAND ゲートの出力が正しいことを確認するだけでなく、すべての入力値が事前に合意した範囲内にあることを確認する必要もあります。
上で説明したスキームを組み合わせて、NAND 回路の出力と値制約回路を接続して演算回路 C を形成します。x は Inp0、w は Inp1 で、出力を 0 に制約して、完全な NAND ゲート プライバシーを形成します。認証制度。
最終的な証明回路 C が得られたら、この演算回路の複雑さを計算できます。
デジタル演算回路 C がどれほど難しいかを知りたい場合は、その回路に含まれる演算ゲートの数によってその複雑さを説明できます。一般的には を使って表現します。前述のNAND耐力回路同様、おそらく10程度でしょう。
副題
ステップ 4: 非対話型ショートプルーフシステム (SNARK)
3 番目のステップで最終的な証明回路 C とそれに対応する x と w を取得したら、準備はほぼ完了です。残りの部分については、SNARK アルゴリズムに引き渡して証明を生成して検証します。
まず、非対話型証明システム全体の公式の定義を見てみましょう。
SNARK システムは、多くの場合、セットアップ、証明、検証という 3 つのコア アルゴリズムで構成されます。
生成アルゴリズムのセットアップ:
セットアップ アルゴリズムは、決定した回路 C を一連の前処理 (前処理) に組み込み、2 セットのパラメーターを生成します。 Sp は証明者用のパラメータ、Sv は検証者用のパラメータです。これらのパラメータの目的は、双方が短いプルーフを生成および検証できるようにすることです。一般に、生成アルゴリズムの複雑さは回路 C、O(|C|) の複雑さに比例します。
証明アルゴリズム 証明する:
証明アルゴリズムについて話す必要はありませんが、証明者は証明アルゴリズムを使用して証明を生成し、その証明を検証者に送信します。 Prove アルゴリズムは、証明を再生成するときに、前処理されたデータ Sp、パブリック入力 x、およびプライベート入力 w のほぼすべてのデータを使用します。結果として得られる証明の空間計算量は非常に短くなります: |Π| = O(log|C|)。
検証アルゴリズム 検証:
検証アルゴリズムも非常に簡単で、検証者は検証アルゴリズムを使用して、受信した証明を検証します。このアルゴリズムは、検証に合格したかどうかを表す 1/0 の値を返します。検証プロセスでは、相手が提供する証明に加えて、データと公開入力 x も前処理する必要があります。検証の複雑さも非常に小さく、通常は O(|x| + log|C|) です。
これら 3 つのアルゴリズムを使用すると、非常に単純な図を使用して証明システム全体を説明できます。
最初のレベルのタイトル
例：プライベートトランザクションの入出力範囲（Range Proof）
前回の記事を読んだ友人は、プライベート取引 (機密取引) を実行したい場合、取引の最後に 3 セットの証拠を添付する必要があることを覚えているはずです。
最初のグループはピーダーソンの約束、入力と出力の間の数学的関係を証明します。
2番目のグループは、インターバルプルーフ、入力と出力の値がすべて正の整数の範囲内にあることを証明する必要があります。
3番目のグループは、所有権の証明、トランザクションの開始者が本当に非常に多くのトークンを入力として持っていることを証明します。
ピーダーソン氏の約束の履行については、すでに前の記事で説明しました。短い証明の 4 ステップの構造を理解したので、それを詳細に実装する方法がわかります。インターバルプルーフ。
まず、適切な演算回路証明したいことを説明します。 (デフォルトでは正の整数の有限体を使用し、法として非常に大きな素数 p を選択します。)
数値 w があり、この数値 w が負の数ではないことを証明したい場合、まず、それが正の整数の範囲内にある必要があることを証明できます。コンピューター システム内の正の整数は通常 256 ビットを超えないことを考慮すると、問題を弱めることができるためです。数値 w の値が 0 ～ 2^256 であることを証明します。(この条件によれば、有限体によって選択される素数 p は 2^256 より大きい必要があります。)
解決すべき問題が決まったので、この値の関係を加算と乗算でどのように表現するかを考え始めることができます。前の章で、0 と 1 の間の値 n について説明したとき、この値の範囲を制限するために n * (n - 1) = 0 を使用したことを思い出してください。同様に、制約に 0 から 5 までの値を持たせたい場合は、より長い一連の乗算を使用して制約を制約できます。
これを見ると、w の値を制限する方法をすでに知っているかもしれません。同じ方法を使用してこの方程式を拡張し、(w - 1) から (w - 2^{256}) まで連続的に乗算するだけで済みます。わかりました？
簡単そうに聞こえますが、注意深い友人なら、最終回路では次のようなことが起こることに気づくでしょう。2^256あります乗算ゲート。非常に多くの乗算が行われ、加算が行われないため、この回路の複雑さはすでに天文学的です。たとえセットアップを実行したとしても、申年に遭遇することはわからないかもしれないので、この制約の方法は次のとおりであると言います。現実的ではありません。
では、この数値wのスペースを制限する方法はあるのでしょうか？我々はできる2進数の構造をうまく利用しましょう。w が整数で、0 より大きく 2^256 より小さいと規定したいので、2 進数で次のようにすることができます。w を 256 ビットに分割し、各ビットを個別に制約します。この場合、最終的に得られる回路のサイズは、この数値の桁数にのみ比例し、この数値の最大上限には関係しません。複雑さは突然大幅に低下しました。
それはどのように達成されるのでしょうか?まず w を 256 ビットに分割します。
各ビットはバイナリであるため、各ビットの値空間を 0 と 1 に制限する必要があります。
この制約には、ビットごとに 1 つずつ、256 個のコピーが必要です。これらの制約を準備したら、最終的にすべてのビットをまとめて元の状態に復元できることを確認します。
上記の 256+1=257 個の制約回路をすべてつなぎ合わせて、1 つの出力に結合します。最終的に生成された回路は、証明システムの構築に使用できる回路 C です。 C の出力が 0 の場合、入力を表す数値は次の条件を満たす必要があります。
この数値は、256 ビットの 2 進数で表すことができる正の整数です。
この 256 ビットの 2 進数は確かに 2 進数です。 (値は 0 または 1 のみを取ることができます)
これらすべての 256 ビット 2 進数を組み合わせて、入力された数値を復元できます。
バイナリの特性をうまく利用して、最初のレベルのタイトル
例: プライベート トランザクション入力の所有権
間隔証明を解決したら、プライベート トランザクションの最後の証明セットである所有権の証明を完了しましょう。これは、プライベート トランザクションの入力値が妥当であることを証明します。
前回の記事を読んだ友人なら、プライベート トランザクションの所有権を証明するための 2 つのシステムについて説明したことをご存知でしょう。
最初の解決策は、トランザクションが前のトランザクションの出力を直接参照できることですが、これは鶏が先か卵が先かという問題を引き起こします。難しいのは最初のプライベート トランザクションを作成する方法にあります。 2 番目の解決策は、各取引の下に別の新しい証拠を添付して、取引を開始したユーザーの口座残高に実際にそれだけの金額があることを証明することです。
強調したいのは2 番目の証明スキームは、世界国家における取引開始者の口座残高を証明することです。
多くのブロックチェーン シナリオでは、世界全体の状態が巨大な台帳になります。台帳の各行には、特定のユーザーの口座残高が記録されます。
世界全体の状態をより便利に表現するために、私たちはマークル ツリーをよく使用して、巨大な世界台帳を一連の短く整ったマークル ハッシュ値に変換します。アカウントの残高が変更されると、このマークル ハッシュも変更されます。
マークルツリーは実際にはバイナリツリーであり、各ノードは以下の2つの子ノードの値をつなぎ合わせ、対応するハッシュ値を自身の値として計算します。マークル ツリーの構築を容易にするために、最初に最も元の残高値に対してハッシュ計算を実行し、次にそのハッシュ値をマークル ツリーの下部に保存します。
この方法でマークル ツリーを構築すると、出力されたマークル ハッシュ値をコミットメント: 約束が変わらない限り、世界の現状は変わってはいけません。ブロックチェーンでは、データの長いリストのステータスを記録したい場合、通常、スペースを節約するために、データ自体をチェーンに保存するのではなく、チェーン上のすべてのデータのマークルコミットメントを記録します。
世界情勢への取り組みが完了したら、次の質問をします。A が上の図のアカウント 1 である場合、現在 5 元があります。 A さんは、B さんに対して、全世界の状態で、彼女の残高が本当に 5 元であることをどのように証明しますか?
非常に簡単な方法は、A がすべての口座の残高を B に送信し、B が独自にマークル コミットメントの計算を実行することです。 B の計算されたコミットメントが現在の世界国家のコミットメントと等しく、A が自分の口座残高が確かに 5 元であると提出する限り、B は A が本当に 5 元を持っていると信じることができます。
とても良い方法のように思えますが、この方法の問題点は一目瞭然です。この世界には何億ものユーザーがいますが、A が数億行の預金残高を B に提出する必要がある場合、B がこのコミットメントをどのように効率的に計算できるかは言うまでもなく、ネットワーク トラフィックだけでも枯渇してしまいます。そして、そのような証明方法は、すべてのユーザーの残高情報を公開することになり、誰もが絶対に望んでいません。
それでは、口座 1 の残高が現在の世界状態に属していることを効果的に証明するにはどうすればよいでしょうか?この時点で、マークル ツリーの特性を使用してマークル証明を構築できます。
上の図の枝刈りされたマークル ツリーを注意深く観察すると、アカウントの残高 1 がマークル ツリー内の隣接ノードとの最終的な世界国家コミットメントを形成できることを証明する限り、アカウントの残高も証明できることがわかります。アカウント 1 それは世界の現状に属します。
どうやってするの？アカウント 1 の残高から始めましょう。マークルツリーをずっと登ってください。
口座残高 1 を使用して、H1 を計算できます。 H1 を取得した後、H0 の値を組み合わせて H4 を生成できる限り、口座 0 の残高を知る必要がないことがわかりました。同様に、H5 の値と組み合わせることで、最終的に頂点のマークル コミットメント — H6 を生成できます。最終的に、このマークル証明を完了するには、口座残高 1、H0、および H5 の 3 つを提出するだけで済みます。残りのハッシュ値はすべて検証プロセス中に計算できます。これがマークルの証明です。
マークル証明により証明の量を大幅に削減でき、証明プロセス中に世界の状態の他のユーザーの残高が公開されないようにすることもできます。マークル証明は暗号化において非常に役立ち、長さ N のリストに何かが含まれていることを証明するにはサイズ n だけが必要です。私たちは多くの場合、マークル証明を使用して、データ セットが大きなファイルに属していること、ユーザーが大規模な組織に属していることなどを証明します。
マークル証明の原理を理解した後、A が個人取引で残高を証明できることを証明する方法を見てみましょう。
マークル証明の本質は、次のことができるということです。証明したい値から始めてハッシュ値を計算し、隣接するノードのハッシュ値と継続的にマージします。しかし、私たちは非常に致命的な問題を発見しました。世界状態における他の人のバランスを隠すことはできますが、それでも残高を公開する必要があります(そうしないと、最初のハッシュ値 H1 を計算する方法がありません)。これは私たちの個人的な取引の本質に反しています。
このとき、SNARKの力を使う必要があります。副題
ステップ 1: 残高ハッシュを証明する
最初のステップでは、SNARK を使用して、アカウント 1 の残高がハッシュ関数を通過した後にハッシュ値 H1 を取得できることを証明します。
アカウント 1 の残高を非表示にしたいので、この数値を w で表します。 SNARK を適用する前に、算術演算回路で表現しやすいように問題の記述方法を変更する必要もあります。
A 自身が秘密 w = 口座残高 1 を持っているとします。 A と B は両方とも、アカウント 1 の残高のハッシュ値 H1 を事前に知っています (これを x で表すことができます)。数学演算回路 C: Hash(w) - x = 0 を構築できます。 C(x, w) = 0 の場合、Hash(w) = x になります。
表現を簡素化するために、抽象モジュールを使用してグラフ上でハッシュ関数を表現します。実際には、通常、SHA256 ハッシュ関数が使用されます。最終的な回路 C を取得した後、Setup アルゴリズムを使用してパラメーターを生成し、Prove アルゴリズムを使用して短い証明を生成します。
このステップを通じて、公開された x と証明を取得します。この x の値は、アカウント 1 の残高のハッシュ値です。副題
ステップ 2: H1 のマークル証明を完了する
前のステップで H1 を取得できるようになり、H1 が実際に元のワールド状態から生成されたことの証明も提供されました。私たちが今しなければならないことは、H1 から開始して隣接する H0 と H5 をそれぞれ組み合わせて、新しい世界国家コミットメントを生成することです。生成されたコミットメントをブロックチェーンに保存された古いコミットメントと比較すると、アカウント 1 の残高が実際にワールド状態にあると信じることができます。
要約すると、所有権の証明を 2 つのステップに分けました。、最初のステップは、秘密 w がハッシュ関数によって x に変換できることを証明し、次に公開 x が世界国家全体のマークル ツリーに属していることを証明することです。最初のレベルのタイトル
プライベートトランザクションの概要
これを見れば、プライベートトランザクションがどのように実現されるかについて、誰もが大まかに理解できるはずです。ここで、A が個人取引で B に支払いたい場合に何をしなければならないかをまとめてみましょう。
まず、A はネットワーク全体に送信する必要がありますプライベートトランザクションを送信する、このトランザクションにはトランザクションの開始者と受取人が含まれていますが、数量がありません。入力と出力の元の数量が、いくつかの文字化けした文字列に置き換えられます。
このトランザクションの下で、A は入力値と出力値の合計が等しいことを証明するために Pederson コミットメントを添付する必要があります。
次に、A はもう 1 つのパスを追加する必要がありますSNARK によって生成されたインターバルプルーフ(範囲証明)。入力および出力の数値がすべて 0 より大きい正の整数であることを証明します。
最後に、A は所有権の証明これは、彼女が実際にお金が入金されるアカウント w を所有していることを証明します。この所有権の証明は 2 つの部分に分かれており、1 つは SNARK によって生成されたハッシュ値の証明であり、もう 1 つは前のハッシュ値が実際に世界の状態に属していることを証明するマークルの証明です。
最初のレベルのタイトル
つづく
紙面の都合上、今回はここまでとさせていただきます。おそらく誰もがこれを見たことがあり、ゼロ知識証明の「証明」の部分はすでに理解していると思います。おそらく数学的演算回路が何であるか、そして現実の問題をどのように回路に変換するかを知っているでしょう。
気になる人も多いと思いますが、Setup、Prove、Verify の 3 つのアルゴリズムはどのように機能するのでしょうか?次回も、SNARK プルーフ システムの背後にある原理を深く理解するために、引き続き詳しく見ていきましょう。
続きを読む
いつものように、読書リストの一部は記事の最後に記載されており、興味のある友人はそれについてさらに詳しく知ることができます。
IOS
Android