原作者: ヴィタリック・ブテリン
オリジナル編集: Kate、MarsBit
この記事は主に、2019 年時代の暗号、特に SNARK と STARK に一般的に精通している読者を対象としています。まだの方は、まずこれらの記事を読むことをお勧めします。フィードバックとコメントをくださった Justin Drake、Jim Posen、Benjamin Diamond、Radi Cojbasic に心より感謝いたします。
過去 2 年間で、STARK は、非常に複雑なステートメント (イーサリアム ブロックが有効であることの証明など) の簡単に検証可能な暗号証明を効率的に生成できる、重要かつかけがえのないテクノロジーになりました。主な理由の 1 つは、フィールド サイズが小さいことです。楕円曲線ベースの SNARK では、十分なセキュリティを確保するために 256 ビット整数を処理する必要がありますが、STARK ではより小さいフィールド サイズを使用できるため、より効率的です。まず、Goldilocks フィールドです。 (64 ビット整数) 、次に Mersenne 31 と BabyBear (両方とも 31 ビット)。これらの効率の向上により、Goldilocks を使用した Plonky 2 は、広範囲の計算を証明する際に前バージョンよりも数百倍高速になりました。
当然の疑問は、この傾向を論理的な結論に導き、0 と 1 を直接操作することでより高速に動作する証明システムを構築できるかということです。それはまさに Binius がやろうとしていることであり、3 年前の SNARK や STARK とは大きく異なる多くの数学的トリックを使用しています。この投稿では、フィールドが小さいと証明生成がより効率的になる理由、バイナリ フィールドが他に類を見ないほど強力である理由、およびバイナリ フィールドの証明を非常に効率的にするために Binius が使用するトリックについて説明します。
ビニウス、この記事を読み終えるまでに、この図のすべての部分を理解できるはずです。
復習: 有限体
暗号証明システムの重要なタスクの 1 つは、数値を小さく保ちながら大量のデータを操作することです。大規模なプログラムに関するステートメントを、いくつかの数値を含む数式に凝縮できても、その数値が元のプログラムと同じくらい大きい場合は、何も得られません。
数値を小さく保ちながら複雑な演算を実行するために、暗号学者はモジュラー演算を使用することがよくあります。素数「モジュロ」p を選択します。 % 演算子は「剰余を取る」ことを意味します: 15% 7 = 1、53% 10 = 3 など。 (答えは常に負ではないことに注意してください。たとえば、-1% 10 = 9 となります)
時間の加算と減算のコンテキストで剰余算術を見たことがあるかもしれません (たとえば、9 時から 4 時間後は何時ですか? しかし、ここでは、数値を剰余として加算および減算するだけでなく、乗算もできます)そして割って指数をとります。
次のように再定義します。
上記のルールはすべて自己矛盾がありません。たとえば、p= 7 の場合、次のようになります。
5+3 = 1 (8% 7 = 1 であるため)
1-3 = 5 (-2% 7 = 5 のため)
2*5=3
3/5 = 2
この構造のより一般的な用語は有限体です。有限体は、通常の算術の法則に従う数学的構造ですが、取り得る値の数が限られているため、各値を固定サイズで表すことができます。
モジュロ算術 (または素数フィールド) は最も一般的なタイプの有限フィールドですが、拡張フィールドという別のタイプもあります。拡張子フィールド「複数形」を見たことがあるかもしれません。新しい要素を「想像」し、それに i というラベルを付け、それを使って計算します: (3 i+ 2)*(2 i+ 4) = 6 i*i+ 12 i+ 4 i+ 8 = 16 i+ 2。同様に素数体の拡張を取ることができます。より小さなフィールドを扱い始めると、セキュリティ上、素数フィールドの拡張がますます重要になります。一方、バイナリ フィールド (Binius によって使用される) は、実用性を得るために完全に拡張に依存します。
復習：算数
SNARK と STARK コンピューター プログラムを証明する方法は算術演算です。証明したいプログラムに関するステートメントを取得し、それを多項式を含む数式に変換します。方程式の効率的な解法は、プログラムの効率的な実行に対応します。
簡単な例として、100 番目のフィボナッチ数を計算し、それが何であるかを証明したいとします。フィボナッチ数列をエンコードする多項式 F を作成しました。つまり、F(0)=F(1)=1、F(2)=2、F(3)=3、F(4)=5 など、合計となります。 100段階の。証明する必要がある条件は、x={ 0, 1 … 98 } の全範囲において F(x+ 2)=F(x)+F(x+ 1) であることです。商を与えると納得できます。
ここで、Z(x) = (x-0) * (x-1) * …(x-98)。 . F が存在し、H がこの式を満たすと仮定できる場合、F は範囲内で F(x+ 2)-F(x+ 1)-F(x) を満たす必要があります。さらに、F(0)=F(1)=1 が満たされていることを確認すると、F(100) は実際には 100 番目のフィボナッチ数になるはずです。
より複雑なことを証明したい場合は、「単純な」関係 F(x+ 2) = F(x) + F(x+ 1) をより複雑な方程式に置き換えます。基本的には、「F(x+ 1) ) は次のとおりです」となります。仮想マシンを状態 F(x) で初期化し、計算ステップを実行した結果。より多くのステップに対応できるように、数値 100 をより大きな数値 (100000000 など) に置き換えることもできます。
すべての SNARK と STARK は、多項式 (場合によってはベクトルや行列) に対する単純な方程式を使用して、単一の値間の大きな関係を表現するという考えに基づいています。すべてのアルゴリズムが上記のように隣接する計算ステップ間の等価性をチェックするわけではありません。たとえば、PLONK はチェックしませんし、R 1 CS もチェックしません。ただし、同じチェック (または同じいくつかのチェック) を複数回実行すると、オーバーヘッドを最小限に抑えることが容易になるため、最も効率的なチェックの多くはこれを実行します。
Plonky 2: 256 ビット SNARK および STARK から 64 ビットへ...STARK のみ
5 年前、さまざまなタイプのゼロ知識証明の合理的な要約は次のとおりでした。証明には、(楕円曲線ベース) SNARK と (ハッシュベース) STARK の 2 種類があります。技術的には、STARK は SNARK の一種ですが、実際には、「SNARK」は楕円曲線ベースのバリアントを指すのによく使用され、「STARK」はハッシュ ベースの構造を指すのに使用されます。 SNARK は小さいため、非常に迅速に確認でき、チェーンに簡単に取り付けることができます。 STARK は大きいですが、信頼できるセットアップを必要とせず、量子耐性があります。
STARK は、データを多項式として扱い、その多項式の計算を計算し、拡張データのメルケル根を「多項式コミットメント」として使用することによって機能します。
ここで重要な歴史の一部は、楕円曲線ベースの SNARK が最初に広く使用されるようになったということです。FRI のおかげで STARK が十分に効率的になったのは 2018 年頃になってからで、その時までに Zcash は 1 年以上実行されていました。楕円曲線ベースの SNARK には重要な制限があります。楕円曲線ベースの SNARK を使用する場合、これらの方程式の演算は楕円曲線上の点係数を使用して実行する必要があります。これは大きな数で、通常は 2 の 256 乗に近い値です。たとえば、bn 128 曲線は 21888242871839275222246405745257275088548364400416034343698204186575808495617 です。しかし、実際の計算では小さな数値が使用されます。お気に入りの言語で作られた「実際の」プログラムについて考えてみると、そこで使用されるもののほとんどはカウンター、for ループ内のインデックス、プログラム内の位置であり、これらは True または 1 ビットの False を表します。 、その他、ほとんどの場合、数桁の長さしかないもの。
「元の」データが「小さい」数値で構成されている場合でも、証明プロセスでは商、展開、ランダムな線形結合、その他のデータ変換を計算する必要があり、その結果、平均サイズが同じかそれ以上のオブジェクトが生成されます。フィールドのすべてのサイズは同じサイズです。これにより、重要な非効率が生じます。n 個の小さな値の計算を証明するには、n 個のはるかに大きな値についてさらに多くの計算を実行する必要があります。当初、STARK は 256 ビット フィールドを使用する SNARK の習慣を引き継いだため、同じ非効率性に悩まされました。
多項式評価に対するリードソロモン拡張。元の値は小さいですが、追加の値はフィールドのフルサイズ (この場合は 2^31-1) に拡張されます。
2022 年に Plonky 2 がリリースされます。 Plonky 2 の主な革新は、より小さな素数を法とする算術演算です: 2 の 64 乗 – 2 の 32 乗 + 1 = 18446744067414584321。現在では、各加算や乗算は常に CPU 上の数命令で実行でき、すべてのデータをまとめてハッシュする処理は以前より 4 倍高速になっています。しかし、問題があります。このアプローチは STARK でのみ機能します。 SNARK を使用しようとすると、このような小さな楕円曲線では楕円曲線は安全ではなくなります。
セキュリティを確保するために、Plonky 2 では拡張フィールドも導入する必要があります。算術方程式をチェックするための重要なテクニックは「ランダム ポイント サンプリング」です。H(x) * Z(x) が F(x+ 2)-F(x+ 1)-F(x) に等しいかどうかをチェックしたい場合は、座標 r をランダムに選択し、H(r)、Z(r)、F(r)、F(r+ 1)、および F(r+ 2) を証明するための多項式コミットメント証明を提供し、H(r) * Z( r) F(r+ 2)-F(r+ 1)- F(r) に等しいか。攻撃者が事前に座標を推測できれば、証明システムを騙すことができます。これが、証明システムがランダムでなければならない理由です。しかしこれは、攻撃者がランダムに推測できないほど大きなセットから座標をサンプリングする必要があることも意味します。係数が 2 の 256 乗に近い場合、これは明らかに当てはまります。しかし、法量が 2 の 64 乗 - 2 の 32 乗 + 1 になるにはまだ到達しておらず、2 の 31 乗 - 1 に下げると、確かにそうではありません。 。幸運が訪れるまで 20 億回も証拠を偽造しようとすることは、攻撃者の能力の範囲内であることは間違いありません。
これを防ぐために、拡張フィールドから r をサンプリングします。たとえば、y 3 = 5 で y を定義し、1、y、y 2 の組み合わせを取得できます。これにより、座標の総数は約 2^93 に増加します。証明者が計算する多項式のほとんどは、この拡張領域には入らず、2^31-1 を法とする単なる整数であるため、小さな領域を使用しても最大限の効率が得られます。しかし、ランダム ポイント チェックと FRI 計算は、必要なセキュリティを実現するために、このより大きな領域を実際に調査します。
小さな素数から二進数まで
コンピューターは、大きな数値を 0 と 1 のシーケンスとして表し、これらのビットの上に加算や乗算などの演算を実行する「回路」を構築することによって算術演算を実行します。コンピューターは、16 ビット、32 ビット、および 64 ビットの整数用に特に最適化されています。たとえば、2 の 64 乗 - 2 の 32 乗 + 1 と 2 の 31 乗 - 1 が選択されたのは、これらの境界に適合するためだけでなく、これらの境界によく適合するためでもあります。これは、通常の 32 ビット乗算を実行して、2^64 - 2^32 + 1 を法とする乗算を実行し、ビットごとにシフトして出力をいくつかの場所にコピーすることによって行われます。この記事では、いくつかのトリックについて詳しく説明しています。
ただし、より良いアプローチは、バイナリで直接計算を実行することです。 1 + 1 をあるビットから次のビットに加算する際の「キャリー」オーバーフローを心配する必要がなく、加算が「単なる」 XOR になるとしたらどうなるでしょうか?同じ方法で乗算をさらに並列化できたらどうなるでしょうか?これらの利点はすべて、1 ビットを使用して true/false 値を表現できることに基づいています。
直接バイナリ計算のこれらの利点を活用することは、まさに Binius がやろうとしていることです。 Binius チームは、zkSummit でのスピーチで効率の向上を実証しました。
「サイズ」はほぼ同じですが、32 ビット バイナリ フィールド演算に必要な計算リソースは 31 ビット メルセンヌ フィールド演算の 5 分の 1 です。
多項式から超立方体まで
この推論を信じて、すべてをビット (0 と 1) で実行したいとします。多項式を使用して 10 億ビットを表すにはどうすればよいでしょうか?
ここで 2 つの実際的な問題に直面します。
1. 多項式が多数の値を表すには、多項式の評価中にこれらの値にアクセスできる必要があります。上記のフィボナッチの例では、F( 0)、F( 1) … F( 100)、大規模な計算では、指数が数百万に達することがあります。使用するフィールドには、このサイズまでの数値が含まれている必要があります。
2. マークル ツリーで提出する値を証明するには (すべての STARK と同様)、その値のリードソロモン エンコードが必要です。たとえば、悪意のある証明者が計算中に値を偽造することによる不正行為を防ぐために、冗長性を使用して値を n から 8n に拡張します。これには十分な大きさのフィールドも必要です。100 万の値を 800 万にスケールするには、多項式を評価するために 800 万の異なる点が必要です。
Binius の重要なアイデアは、同じデータを 2 つの異なる方法で表すことによって、これら 2 つの問題を別々に解決することです。まず、多項式自体です。楕円曲線ベースの SNARK、2019 年版の STARK、Plonky 2 などのシステムは、通常、1 つの変数 F(x) で多項式を扱います。一方、Binius は Spartan プロトコルからインスピレーションを得て、多変量多項式 F(x 1, x 2,… xk) を使用します。実際、計算の軌跡全体を計算「ハイパーキューブ」上で表し、各 xi は 0 または 1 のいずれかになります。たとえば、フィボナッチ数列を表現したいが、それを表現するのに十分な大きさのフィールドを使用する場合、最初の 16 個は次のように考えることができます。
つまり、F(0, 0, 0, 0) は 1 である必要があり、F(1, 0, 0, 0) も 1 である必要があり、F(0, 1, 0, 0) は 2 である必要があります。 F(1, 1, 1, 1)= 987 まで。このような計算の超立方体が与えられると、これらの計算を生成する多変量線形 (各変数の次数が 1) 多項式が存在します。したがって、この値のセットは多項式の表現として考えることができ、係数を計算する必要はありません。
もちろん、この例は単なる説明のためのものです。実際には、ハイパーキューブに入る最大のポイントは、個々のビットを処理できるようにすることです。フィボナッチ数を計算する「Binius ネイティブ」の方法は、高次元の立方体を使用し、たとえば 16 ビットの各グループを使用して数値を格納することです。整数をビット単位で足し算するのは工夫が必要ですが、Binius の場合はそれほど難しくありません。
次に、イレイジャーコーディングについて見てみましょう。 STARK の仕組みは次のとおりです。n 個の値を取得し、リードソロモンがそれらをより多くの値 (通常は 8n、通常は 2n から 32n の間) に拡張し、拡張からいくつかのマークル分岐をランダムに選択し、ある種のチェックを実行します。超立方体の長さは各次元で 2 です。したがって、それを直接拡張することは現実的ではありません。16 個の値からマークル ブランチをサンプリングするのに十分な「余地」がありません。どうしようか？超立方体が正方形であると仮定しましょう。
シンプルなビニウス - 例
このプロトコルの Python 実装については、ここを参照してください。
便宜上、フィールドとして通常の整数を使用する例を見てみましょう (実際の実装では、バイナリ フィールド要素が使用されます)。まず、送信するハイパーキューブを正方形としてエンコードします。
次に、リードソロモンを使用して正方形を拡張します。つまり、各行を x ={ 0, 1, 2, 3 } で評価される 3 次多項式として扱い、同じ多項式を x ={ 4, 5, 6, 7 } で評価します。
数値はすぐに膨れ上がる可能性があるので注意してください。実際の実装では、通常の整数ではなく、常に有限フィールドを使用するのはこのためです。たとえば、11 を法とする整数を使用した場合、最初の行の展開は単に [3, 10, 0, 6] になります。
拡張機能を試してここの数字を自分で確認したい場合は、ここで私の単純なリードソロモン拡張コードを使用できます。
次に、この拡張子を列として扱い、その列のマークル ツリーを作成します。メルケルの木の根は私たちのコミットメントです。
ここで、証明者がある時点でこの多項式 r={r 0, r 1, r 2, r 3} の計算を証明したいと仮定します。 Binius には、他の多項式コミットメント スキームよりも弱いという微妙な違いがあります。証明者は、マークル根にコミットする前に s を知らないか、推測できる必要はありません (つまり、r は擬似乱数値である必要があります)。これにより、このスキームは「データベース検索」には役に立たなくなります (例: 「オーケー、マークル ルートを教えてくれたので、P(0, 0, 1, 0) を見せてください!」)。しかし、私たちが実際に使用するゼロ知識証明プロトコルは通常、「データベース検索」を必要とせず、ランダムな評価点で多項式をチェックするだけです。したがって、この制限は私たちの目的に適しています。
r={ 1, 2, 3, 4 } を選択したとします (多項式は -137 と評価されます。このコードを使用して確認できます)。さて、証明の手続きに入ります。 r を 2 つの部分に分割します。最初の部分 {1, 2} は行内の列の線形結合を表し、2 番目の部分 {3, 4} は行の線形結合を表します。列部分の「テンソル積」を計算します。
ライン部分の場合:
これは、各セット内の値のすべての可能な積のリストを意味します。行の場合は次のようになります。
[( 1-r 2)*( 1-r 3)、( 1-r 3)、( 1-r 2)*r 3、r 2*r 3 ]
r={1, 2, 3, 4} を使用する (つまり、r 2 = 3 および r 3 = 4):
[( 1-3)*( 1-4), 3*( 1-4),( 1-3)* 4, 3* 4 ] = [ 6, -9 -8 -12 ]
ここで、既存の行の線形結合を取得して、新しい「行」 t を計算します。つまり、次のようになります。
ここで起こっていることは部分的な評価であると考えることができます。完全なテンソル積とすべての値の完全なベクトルを乗算すると、P(1, 2, 3, 4) = -137 という計算が得られます。ここでは、評価された座標の半分のみを使用して部分テンソル積を乗算し、N 値グリッドをルート N 値の行に単純化します。この行を他の人に渡すと、その人は評価された座標の残りの半分のテンソル積を使用して残りの計算を行うことができます。
証明者は、次の新しい行 t およびいくつかのランダムにサンプリングされた列のマークル証明を検証者に提供します。この例では、証明者に最後の列のみを提供させますが、実際には、適切なセキュリティを実現するには、証明者は数十の列を提供する必要があります。
ここで、リードソロモン符号の線形性を利用します。私たちが使用する重要な特性は、リード ソロモン展開の線形結合を行うと、線形結合のリード ソロモン展開と同じ結果が得られるということです。この「順序の独立性」は通常、両方の操作が線形である場合に発生します。
バリデーターはまさにこれを行います。彼らは t と、証明者が以前に計算したのと同じ列 (証明者によって提供された列のみ) の線形結合を計算し、両方の手順で同じ答えが得られることを検証しました。
この場合、t を拡張して同じ線形結合 ([6,-9,-8, 12]) を計算すると、両方とも同じ答えが得られます: -10746。これは、メルケル首相の根が「善意」で構築された (または少なくとも「親密な」) ものであることを証明します。十分な)、それは t と一致します。少なくとも大多数の列は相互に互換性があります。
しかし、検証者はもう 1 つチェックする必要があります。多項式 {r 0 …r 3 } の評価をチェックすることです。これまでの検証者のステップはどれも、実際には証明者が主張する値に依存していません。このようにして確認します。計算点としてラベルを付ける「列部分」のテンソル積を取得します。
この例では、r={ 1, 2, 3, 4 } なので、選択された列の半分は { 1, 2 } になります)、これは次と等しくなります。
ここで、次の線形結合 t を使用します。
これは、多項式を直接解いた場合と同じ結果になります。
上記は、「単純な」Binius プロトコルの完全な説明に非常に近いものです。これにはすでに興味深い利点がいくつかあります。たとえば、データが行と列に分割されているため、半分のサイズのフィールドが 1 つだけ必要になります。ただし、これではバイナリでのコンピューティングの利点を最大限に活用することはできません。このためには、完全な Binius プロトコルが必要です。まず、バイナリ フィールドについて詳しく見てみましょう。
バイナリフィールド
可能な最小の領域は算術モジュロ 2 です。これは非常に小さいため、加算テーブルと乗算テーブルを作成できます。
拡張により、より大きなバイナリ フィールドを取得できます。F 2 (2 を法とする整数) から開始して、x を定義します ( x 2 乗 = x + 1 )。次の加算テーブルと乗算テーブルが得られます。
この構築を繰り返すことで、バイナリ フィールドを任意の大きなサイズに拡張できることがわかりました。実数に対する複素数とは異なり、新しい要素は追加できますが、それ以上の要素は追加できません (四元数は存在しますが、数学的に奇妙です。たとえば、ab は ba に等しくありません)。有限フィールドを使用すると、いつでも新しい要素を追加できます。拡張子。具体的には、要素を次のように定義します。
等.......これは、連続する各拡張がタワーに新しい層を追加しているように見えるため、タワー構造と呼ばれることがよくあります。これは任意のサイズのバイナリ フィールドを構築する唯一の方法ではありませんが、Binius が利用する独自の利点がいくつかあります。
これらの数値はビットのリストとして表すことができます。たとえば、1100101010001111。最初の桁は 1 の倍数を表し、2 桁目は x 0 の倍数を表し、その後の桁は次の x 1 の倍数を表します: x 1、x 1*x 0、x 2、x 2*x 0、およびすぐ。このエンコーディングは分解できるので便利です。
これは比較的珍しい表記法ですが、私はバイナリ フィールド要素を整数として表現し、より効率的なビットを右側に配置することを好みます。つまり、1 = 1、x 0 = 01 = 2、1+x 0 = 11 = 3、1+x 0+x 2 = 11001000 = 19 などとなります。この式では 61779 になります。
バイナリ フィールドでの加算は単なる XOR です (ちなみに、減算も同様です)。これは、任意の x に対して x+x= 0 を意味することに注意してください。 2 つの要素 x*y を乗算するには、各数値を半分に分割するという非常に単純な再帰アルゴリズムがあります。
次に、乗算を分割します。
最後の部分は、単純化ルールを適用する必要があるため、唯一少し難しい部分です。カラツバのアルゴリズムや高速フーリエ変換に似た、乗算を行うより効率的な方法がありますが、興味のある読者が理解するための演習として残しておきます。
2 進数フィールドの除算は、乗算と逆算を組み合わせて実行されます。 「シンプルだが遅い」逆転法は、一般化されたフェルマーの小定理を応用したものです。より複雑ですが、より効率的な反転アルゴリズムもここにあります。ここのコードを使用して、バイナリ フィールドの加算、乗算、除算を行うことができます。
左: 4 ビットのバイナリ フィールド要素の加算テーブル (つまり、1、x 0、x 1、x 0x 1 のみで構成)。右: 4 桁の 2 進フィールド要素の乗算表。
このタイプのバイナリ フィールドの利点は、「通常の」整数とモジュロ演算の最良の部分のいくつかを組み合わせていることです。通常の整数と同様、バイナリ フィールド要素には制限がなく、自由に拡張できます。ただし、モジュロ演算と同様に、特定のサイズ制限内の値を操作すると、すべての結果も同じ範囲内に収まります。たとえば、42 を累乗すると、次のようになります。
255 ステップを経ると、42 の 255 乗 = 1 に戻ります。正の整数や剰余演算と同様に、これらは通常の数学的法則に従います: a*b=b*a、a*(b+c)=a * b+a*c、奇妙な新しい法律さえあります。
最後に、バイナリ フィールドを使用すると、ビットの処理が簡単になります。2 k ビットに適合する数値を使用して計算を行う場合、すべての出力も 2 k ビットに適合します。これにより、恥ずかしさを避けることができます。イーサリアムの EIP-4844 では、BLOB の各「ブロック」はデジタル モジュール 52435875175126190479447740508185965837690552500527637822603658699938581184513 である必要があるため、バイナリ データをエンコードするには、一部のスペースを破棄し、追加の A チェックを行う必要があります。各要素に 2 の 248 乗未満の値が格納されるようにする。これは、CPU と理論的に最適な FPGA および ASIC 設計の両方で、バイナリ フィールド操作がコンピュータ上で超高速であることも意味します。
これが意味するのは、例で見たように、整数の「爆発」を完全に回避する方法で、そして非常に「爆発的な」方法で、上で行ったリードソロモン符号化のようなことを実行できるということです。ネイティブ」方式、コンピューターが得意とする種類のコンピューティング。バイナリ フィールドの「分割」属性 - 1100101010001111 = 11001010+ 10001111*x 3 を実行し、ニーズに応じて分割する方法も、多くの柔軟性を実現するために重要です。
ビニウスを完了する
このプロトコルの Python 実装については、ここを参照してください。
ここで、「フル Binius」に進むことができます。これは、「シンプル Binius」を (i) バイナリ フィールドで作業し、(ii) 単一ビットをコミットできるように適応させます。このプロトコルは、ビット マトリクスの見方を行ったり来たりするため、理解するのが困難です。もちろん、暗号化プロトコルを理解するのに通常かかるよりも理解するのに時間がかかりました。しかし、バイナリ フィールドを理解すると、良いニュースは、Binius が依存している「より難しい数学」は存在しないということです。これは楕円曲線のペアではなく、ここにはさらに深い代数幾何学のウサギの穴があります。必要なのは二値体だけです。
チャート全体をもう一度見てみましょう。
ここまでで、ほとんどのコンポーネントについては理解できたはずです。ハイパーキューブをグリッドに「平坦化」するというアイデア、行の組み合わせと列の組み合わせを評価点のテンソル積として計算するというアイデア、「リード・ソロモン展開してから行の組み合わせを計算する」と「行の組み合わせを計算する」というテストそしてリード - ソロモン拡張間の等価性のアイデアは、単純な Binius に実装されています。
「Complete Binius」の新機能は何ですか?基本的には次の 3 つのことです。
超立方体および正方形の個々の値はビット (0 または 1) でなければなりません。
拡張プロセスでは、ビットを列にグループ化し、それらがより大きなフィールド要素であると一時的に想定することで、ビットをより多くのビットに拡張します。
行結合ステップの後に、展開をビットに変換する要素ごとの「ビットへの分解」ステップがあります。
両方のケースについて順番に説明します。まず、新規拡張プロセスです。リードソロモン コードには基本的な制限があります。n を k*n に拡張したい場合は、座標として使用できる k*n 個の異なる値を持つフィールドで作業する必要があります。 F 2 (別名ビット) ではそれはできません。したがって、私たちが行うことは、隣接する F 2 の要素を一緒に「パック」して、より大きな値を形成することです。この例では、一度に 2 ビットを { 0 , 1 , 2 , 3 } 要素にパックします。拡張機能には計算ポイントが 4 つしかないため、これで十分です。 「実際の」証明では、一度に 16 ビットを返す可能性があります。次に、これらのパックされた値に対してリードソロモン コードを実行し、再度ビットにアンパックします。
さて、行の組み合わせです。 「ランダムなポイントで評価する」チェックを暗号的に安全にするために、かなり大きな空間 (ハイパーキューブ自体よりもはるかに大きい) からポイントをサンプリングする必要があります。したがって、超立方体の内部の点はビットですが、超立方体の外部で計算される値ははるかに大きくなります。上記の例では、「行の組み合わせ」は [11, 4, 6, 1] になります。
ここで疑問が生じます。ビットを結合してより大きな値にし、その上でリードソロモン拡張を行う方法はわかっていますが、より大きな値のペアに対して同じことをどのように行うのでしょうか?
Binius のトリックは、ビット単位で処理することです。各値の 1 ビットを調べて (たとえば、「11」とラベル付けしたものは [1, 1, 0, 1])、行ごとに展開します。オブジェクトの展開処理を実行します。つまり、各要素の行 1、次に x 0 行、次に x 1 行、次に x 0x 1 行というように展開プロセスを実行します (まあ、おもちゃの中で例ではそこで停止しましたが、実際の実装では 128 行に達します (最後の行は x 6*…*x 0))
レビュー：
ハイパーキューブ内のビットをグリッドに変換します
次に、各行の隣接するビット グループをより大きなフィールド要素として扱い、算術演算を実行して行をリードソロモン拡張します。
次に、各列のビットの行の組み合わせを取得し、各行のビット列を出力として取得します (4 x 4 より大きい正方形の場合はかなり小さくなります)。
次に、出力を行列として表示し、そのビットを行として表示します。
なぜそうなるのでしょうか? 「通常の」数学では、数値をビットにスライスし始めると、(通常は) 線形演算を任意の順序で実行して同じ結果を得る機能が機能しなくなります。たとえば、数値 345 から始めて、8 を掛け、次に 3 を掛けると、8280 が得られます。これら 2 つの演算を逆にすると、8280 も得られます。しかし、2 つのステップの間に「ビットごとに分割」操作を挿入すると、動作が破綻します。8 倍を実行してから 3 倍を実行すると、次のようになります。
しかし、これを 3 回実行し、さらに 8 回実行すると、次のようになります。
しかし、タワー構造で構築されたバイナリ フィールドでは、このアプローチは機能します。その理由は、それらの分離可能性にあります。大きい値と小さい値を乗算すると、各セグメントで起こったことは各セグメントに残ります。 1100101010001111 に 11 を掛けると、これは 1100101010001111 の最初の分解と同じになります。
次に、各成分に同じ 11 を個別に掛けます。
それらを一緒にします
一般に、ゼロ知識証明システムは、多項式に関するステートメントを作成すると同時に、基礎となる評価に関するステートメントを表すことによって機能します。フィボナッチの例で見たように、F(X+ 2)-F(X+ 1)-F(X) = Z( X)*H(X) は、フィボナッチ計算のすべてのステップを同時にチェックします。ランダムな点での評価を証明することで、多項式に関するステートメントをチェックします。このランダムな点のチェックは、多項式全体のチェックを表します。多項式が一致しない場合、特定のランダムな座標で一致する可能性は低いです。
実際には、非効率の主な理由の 1 つは、実際のプログラムで扱う数値のほとんどが小さいことです (for ループのインデックス、True/False 値、カウンターなど)。ただし、マークル証明ベースのチェックを安全にするために必要な冗長性を提供するためにリードソロモン エンコーディングを使用してデータを「拡張」すると、「余分な」値のほとんどがフィールド全体のサイズを占めてしまいます。元の値が小さい場合。
この問題を解決するには、このフィールドをできるだけ小さくしたいと考えています。 Plonky 2 では 256 ビット数値から 64 ビット数値まで引き下げられ、その後 Plonky 3 ではさらに 31 ビット数値まで引き下げられました。しかし、これでも最適とは言えません。バイナリ フィールドを使用すると、単一ビットを処理できます。これにより、エンコードが「高密度」になります。実際の基になるデータが n ビットの場合、エンコードは n ビットになり、拡張は 8 * n ビットになり、追加のオーバーヘッドは発生しません。
さて、このチャートをもう一度見てみましょう。
Binius では、多線形多項式である超立方体 P(x 0, x 1,…xk) を扱います。ここで、個々の評価は P( 0, 0, 0, 0), P( 0, 0, 0, 1 ) から P (1, 1, 1, 1)、気になるデータを保存します。特定の点での計算を実証するために、同じデータを正方形として「再解釈」します。次に、リードソロモン エンコーディングを使用して各行を拡張し、ランダムなマークル分岐クエリのセキュリティに必要なデータの冗長性を提供します。次に、行のランダムな線形結合を計算し、新しく結合された行に実際に関心のある計算値が含まれるように係数を設計します。この新しく作成された行 (128 行のビットに再解釈される) と、マークル分岐を持つランダムに選択されたいくつかの列が検証者に渡されます。
次に、バリデーターは「拡張された行の組み合わせ」(より正確には、拡張された行の組み合わせ) と「拡張された行の組み合わせ」を実行し、その 2 つが一致することを検証します。次に、列の組み合わせを計算し、証明者が主張した値が返されるかどうかを確認します。これが私たちの証明システム (というよりも、証明システムの重要なコンポーネントである多項式コミットメント スキーム) です。
まだ説明していないことは何ですか?
行を拡張する効率的なアルゴリズム。バリデーターの計算効率を実際に向上させるために必要です。ここで説明するように、バイナリ フィールドで高速フーリエ変換を使用します (ただし、この投稿では再帰的展開に基づいていない非効率的な構造を使用しているため、正確な実装は異なります)。
算術。 1 変量多項式は、F(X+ 2)-F(X+ 1)-F(X) = Z(X)*H(X) などの操作を実行して、計算内の隣接するステップを関連付けることができるため便利です。ハイパーキューブでは、「次のステップ」は「X+1」よりもはるかに解釈しにくいです。 X+k (k のべき乗) を実行することもできますが、このジャンプ動作では Binius の重要な利点の多くが犠牲になります。解決策は Binius の論文で紹介されています。セクション 4.3 を参照してください)。しかし、これ自体が深いウサギの穴です。
特定の値のチェックを安全に行う方法。フィボナッチの例では、重要な境界条件、F(0)=F(1)=1 および F(100) の値をチェックする必要があります。しかし、「生の」Binius では、既知の計算ポイントでチェックするのは安全ではありません。いわゆるサムチェックプロトコルを使用して、既知の計算チェックを未知の計算チェックに変換する非常に簡単な方法がいくつかありますが、ここでは説明しません。
最近広く使用されているもう 1 つの技術であるルックアップ プロトコルは、超効率的な証明システムを作成するために使用されます。 Binius は、多くのアプリケーション検索プロトコルと組み合わせて使用できます。
平方根検証時間を超えています。平方根は高価です。Bit の Binius の 2 の 32 乗の証明の長さは約 11 MB です。他の証明システムを使用して「Binius 証明の証明」を作成することで、この問題を補うことができます。これにより、Binius 証明の効率が向上し、証明サイズが小さくなります。もう 1 つのオプションは、(通常の FRI と同様に) 多対数サイズの証明を作成する、より複雑な FRI-binius プロトコルです。
ビニウスが「SNARKフレンドリーさ」に与える影響。基本的な要約は、Binius を使用する場合、計算を「算術に適した」ものにすることを心配する必要がなくなるということです。「通常の」ハッシュは、従来の算術ハッシュ、つまり 2 の 32 乗または 2 を法とする乗算よりも効率的ではなくなりました。乗算係数などに比べれば、もはや頭の痛い問題ではありません。しかし、これは複雑なテーマです。すべてがバイナリで行われると、多くのことが変わります。
今後数か月以内にバイナリフィールドベースの証明技術がさらに改善されることを願っています。
