Forwarded original title ‘Vitalik explains Binius in detail: an efficient proof system based on binary fields’

この投稿は、特に2019年時点の暗号技術、特にSNARKとSTARKに粗く馴染みのある読者を対象としています。そのような知識がない場合は、まずそれらの記事をお読みいただくことをお勧めします。フィードバックとレビューについては、Justin Drake、Jim Posen、Benjamin Diamond、Radi Cojbasicに特別な感謝を申し上げます。

過去2年間、STARKは、非常に複雑な文を簡単に検証可能な暗号証明を効率的に行うための重要で置き換えがたい技術となっています（例：イーサリアムブロックが有効であることを証明する）。その主な理由は、小さなフィールドサイズです。楕円曲線ベースのSNARKでは、十分に安全であるために256ビットの整数上で作業する必要がありますが、STARKでははるかに小さなフィールドサイズを使用できます。これにより、効率が向上します。最初にゴールディロックスフィールド（64ビット整数）、次にMersenne31およびBabyBear（どちらも31ビット）があります。これらの効率向上のおかげで、ゴールディロックスを使用するPlonky2は、以前のものよりも多くの種類の計算を証明する際に数百倍高速です。

自然な疑問は、この傾向をその論理的結論まで運ぶことができるか、つまり、0と1を直接操作してより速く実行する証明システムを構築できるか、ということです。これは、Biniusが試みていることであり、3年前のSNARKやSTARKとは非常に異なる数学的なトリックを使用しています。この記事では、小さなフィールドが証明生成をより効率的にする理由、バイナリフィールドが独自の強力さを持つ理由、およびBiniusがバイナリフィールド上での証明を効果的に行うために使用するトリックについて述べます。

Binius. この投稿の最後までに、この図のすべての部分を理解できるはずです。

Recap: 有限体

暗号証明システムの主要なタスクの1つは、巨大なデータに対して操作を行いながら、数字を小さく保つことです。大きなプログラムに関する記述を数値を用いた数式に圧縮できれば、その数値が元のプログラムと同じくらい大きい場合、何も得られません。

複雑な算術を行う際に数字を小さく保ちつつ、暗号技術者は一般的に剰余算を使用します。私たちはいくつかの素数「モジュラス」p を選択します。%演算子は「余りを取る」という意味です：15 % 7=1、53 % 10=3 など（答えが常に非負であることに注意してください、つまり例えば −1 % 10=9）。

おそらく、既にモジュラー算術を見たことがあるでしょう。時間の加算や減算の文脈で（例：9:00の4時間後は何時ですか？）。しかし、ここでは、単にある数値で剰余を取るだけでなく、掛け算、割り算、冪乗も行います。

私たちは再定義します:

上記の規則はすべて自己整合的です。例えば、p=7の場合、

5+3=1 (because 8%7=1)

1-3=5 (because -2%7=5)

2*5=3

3/5=2

この種の構造に対するより一般的な用語は、有限体と呼ばれます。有限体は、通常の算術の法則に従う数学的構造ですが、可能な値の数に制限があり、各値を固定サイズで表現できる特性があります。

モジュラー算術（または素体）は有限体の最も一般的なタイプですが、別のタイプもあります：拡張体。おそらく以前に拡張体を見たことがあります：複素数です。新しい要素（𝑖とラベル付け）を「想像」し、𝑖2=−1を満たすと宣言します。その後、通常の数と𝑖の任意の組み合わせを取り、数学を行うことができます：（3𝑖+2）∗（2𝑖+4）= 6𝑖2+12𝑖+4𝑖+8=16𝑖+2。同様に、素体の拡張を行うことができます。私たちはより小さい体上で作業を始めると、素体の拡張はセキュリティを維持するためにますます重要となり、バイナリ体（Biniusが使用する）は実用的な有用性を持つために完全に拡張に依存します。

Recap: 算術化

SNARKsとSTARKsがコンピュータプログラムについて証明する方法は、算術化を通じて行われます：証明したいプログラムに関する文を、多項式を含む数学的な方程式に変換します。方程式の有効な解は、プログラムの有効な実行に対応します。

簡単な例を挙げると、100番目のフィボナッチ数を計算したとします。その数値を証明したいとします。フィボナッチ数を符号化する多項式 𝐹 を作成します。つまり、𝐹(0)=𝐹(1)=1、𝐹(2)=2、𝐹(3)=3、𝐹(4)=5 など、100回のステップで続きます。証明する必要のある条件は、𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) が範囲 𝑥={0,1…98} 全体で成り立つことです。このことを、商を与えることで説得できます。

where Z(x) = (x-0)(x-1)…(x-98)。もしFとHがこの方程式を満たすことができると証明できれば、Fは範囲内でF(x+2)-F(x+1)-F(x)を満たさなければなりません。さらに、FがF(0)=F(1)=1を満たすことを追加で検証すれば、実際にF(100)は100番目のフィボナッチ数でなければなりません。

もしもっと複雑なことを証明したい場合は、関係 𝐹(𝑥+2)=𝐹(𝑥)+𝐹(𝑥+1) をより複雑な方程式に置き換えます。これは基本的に「𝐹(𝑥+1) は状態 𝐹(𝑥) で仮想マシンを初期化し、1つの計算ステップを実行した際の出力である」と言っています。また、100という数値を100000000などのより大きな数値で置き換えることもでき、より多くのステップを処理できます。

すべてのSNARKおよびSTARKは、多くの個々の値間の関係を表すために単純な方程式を多項式（または時々ベクトルと行列）上で使用するというこの考えに基づいています。すべてが上記のように隣接する計算ステップ間の同等性をチェックすることを含んでいるわけではありません：例えばPLONKは含んでおらず、R1CSも同様です。しかし、最も効率的なものの多くは、同じチェック（または同じ数回のチェック）を多数回強制することで、オーバーヘッドを最小限に抑えることが容易になるため、これを行います。

Plonky2: from 256-bit SNARKs and STARKs to 64-bit… only STARKs

5年前、ゼロ知識証明の異なるタイプをまとめた合理的な要約は次のとおりでした。証明には2種類あります：（楕円曲線ベースの）SNARKと（ハッシュベースの）STARK。技術的には、STARKはSNARKの一種ですが、実際には「SNARK」は楕円曲線ベースのバラエティにのみ言及するために使用され、「STARK」はハッシュベースの構築に言及するために使用されます。 SNARKは小さく、それを非常に速く検証し、簡単にオンチェーンに適合させることができます。 STARKは大きいですが、信頼されたセットアップを必要とせず、量子耐性です。

STARKsは、データを多項式として扱い、その多項式の評価値を多数の点で計算し、その拡張データのMerkleルートを「多項式コミットメント」として利用することで機能します。

ここでの重要な歴史的事実は、楕円曲線ベースのSNARKが最初に広く使われるようになったことです: STARKが効率的に使用されるようになるには、FRIのおかげでおおよそ2018年までかかりました。その時点でZcashはすでに1年以上稼働していました。楕円曲線ベースのSNARKには重要な制限があります: 楕円曲線ベースのSNARKを使用したい場合、これらの方程式の算術演算は楕円曲線上の点の数で剰余を取る必要があります。これは大きな数であり、通常は2256に近いです: 例えば、bn128曲線の場合、21888242871839275222246405745257275088548364400416034343698204186575808495617です。しかし、実際の計算は小さな数値を使用しています: お気に入りの言語で考えると、ほとんどのプログラムで扱われているものは、カウンタ、forループ内のインデックス、プログラム内の位置、TrueまたはFalseを表す個々のビット、およびほとんどが数桁しかない他の要素です。

たとえあなたの「元の」データが「小さな」数字で構成されていても、証明プロセスには、データの商、拡張、ランダムな線形組合せ、およびその他の変換が必要であり、これにより、平均して、フィールドの完全なサイズと同じ大きさのオブジェクトの等しいかそれ以上の数が生成されます。これにより、鍵となる非効率性が生じます：n個の小さな値の計算を証明するには、n個のはるかに大きな値に対してさらに多くの計算を行う必要があります。最初は、STARKsはSNARKsから256ビットフィールドを使用する習慣を継承しました。そのため、同じ非効率性を引き継ぎました。

一部の多項式評価のReed-Solomon拡張。元の値は小さいが、余分な値はすべて、この場合はフィールドの完全なサイズ（2の31乗-1）に拡大します。

2022年に、Plonky2がリリースされました。Plonky2の主な革新は、より小さい素数で剰余算術を行うことでした: 2⁶⁴−2³²+1=18446744069414584321. 今、CPU上でのそれぞれの加算や乗算は常にわずかな命令で行うことができ、すべてのデータをハッシュ化する速度は以前の4倍速くなりました。しかし、これには注意が必要です：このアプローチはSTARKのみです。このように小さな楕円曲線を使用しようとすると、SNARKを使用しようとすると、楕円曲線が安全ではなくなります。

安全であり続けるために、Plonky2 は拡張フィールドも導入する必要がありました。算術方程式をチェックする際の重要なテクニックは「ランダムな点でのサンプリング」です: 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 に近い場合²⁵⁶, これは明らかに事実です。ただし、2の剰余を持つと⁶⁴−2³²+1, we’re not quite there, and if we drop to 2³¹−1、それは間違いなくそうではありません。1回ラッキーになるまで2億回偽の証拠を作ろうとすることは、攻撃者の能力範囲内です。

これを停止するために、拡張フィールドからrをサンプリングします。たとえば、yを定義できます。³=5、そして1、𝑦と𝑦の組み合わせを取る². これにより、座標の総数がおおよそ2に戻ります⁹³証明者によって計算される多項式の大部分は、この拡大体には含まれません。単に2で割った整数を使用します³¹−1、したがって、引き続き小さなフィールドを使用することにより、すべての効率を得ることができます。ただし、ランダムポイントのチェックとFRI計算は、必要なセキュリティを得るために、このより大きなフィールドにダイブします。

小さな素数からバイナリへ

コンピュータは、大きな数を0と1の連続として表し、それらのビットの上に"回路"を構築して加法や乗法などの計算を行うことで算術を行います。コンピュータは特に16ビット、32ビット、64ビットの整数で計算を最適化しています。2のようなモジュラスでの計算には特に適しています。⁶⁴−2³²+1 と 2³¹-1は、それらの境界内に収まるためだけでなく、それらの境界とよく一致するために選択されています：2を法とする乗算を行うことができます⁶⁴−2³²+1 by doing regular 32-bit multiplication, and shift and copy the outputs bitwise in a few places; this article explains some of the tricks well.

しかし、さらに良いのは、計算を直接バイナリで行うことです。加算が「ただ」XORである場合、1ビット位置から次のビット位置に1 + 1を加算するオーバーフローを気にする必要がないのはどうでしょうか？そして、乗算が同じように並列化できるとしたらどうでしょうか？これらの利点は、True/False値を1ビットで表現できるという利点に加えてすべてが得られます。

バイナリ演算を直接行うことの利点を完全に把握することが、Biniusが試みていることです。BiniusチームのzkSummitプレゼンテーションからの表には、効率の向上が示されています。

同じ「サイズ」であるにもかかわらず、32ビットのバイナリフィールド操作は、31ビットのメルセンヌフィールド上の操作よりも計算リソースを5倍少なく使用します。

単変数多項式から超立方体へ

この推論に納得したとしましょう。そして、ビット（0と1）を使ってすべてを行いたいとします。10億ビットを表す多項式に実際にどのようにコミットしますか？

ここでは、2つの実践的な問題に直面しています:

1. 多くの値を表すために多項式を表すためには、その値が多項式の評価でアクセス可能である必要があります：上記のフィボナッチの例では、 𝐹(0)、 𝐹(1) … 𝐹(100)、そしてより大きな計算では、インデックスは数百万になります。そして、使用するフィールドは、そのサイズに達する数値を含んでいる必要があります。

2. メルクルツリーでコミットしている値について何かを証明するには、（すべてのSTARKが行うように）Reed-Solomonエンコーディングが必要です。例えば、n値を8n値に拡張し、その冗長性を使用して、計算の途中で1つの値を偽造することで悪意のある証明者が不正を行うのを防ぐ必要があります。これには十分に大きなフィールドが必要です。100万の値を800万に拡張するには、多項式を評価するための800万の異なるポイントが必要です。

Biniusの中での重要な考え方は、これら2つの問題を別々に解決し、同じデータを2つの異なる方法で表現することです。まず、多項式そのものです。楕円曲線ベースのSNARK、2019年のSTARK、Plonky2などの他のシステムは、通常、1つの変数に関する多項式：𝐹(𝑥)を扱います。一方、Biniusは、スパルタンプロトコルからインスピレーションを受け、多変量多項式：𝐹(𝑥1,𝑥2…𝑥𝑘)で作業します。実際、各𝑥𝑖が0または1である評価の“超立方体”上に計算トレース全体を表現します。たとえば、フィボナッチ数列を表現し、それらを表現するのに十分な大きさのフィールドをまだ使用している場合、最初の16個を次のように視覚化するかもしれません。

つまり、F(0,0,0,0) は 1 になり、F(1,0,0,0) も 1 になり、F(0,1,0,0) は 2 になります。このような評価の超立方体が与えられると、これらの評価を生成する多重線形 (各変数の次数 1) 多項式が 1 つだけ存在します。したがって、その一連の評価は多項式を表すと考えることができます。実際に係数を計算する必要はありません。

この例はもちろんイラスト用です。実際には、ハイパーキューブに行くポイントは、個々のビットを扱えるようにすることです。“Binius-native”にフィボナッチ数を数える方法は、より高次元のキューブを使用し、各セットの例えば16ビットを数値を保存するために使用することです。これには、ビットの上で整数の加算を実装するためのいくつかの巧妙さが必要ですが、Biniusを使用すればそれほど難しくありません。

今、私たちは消去符号化に移ります。STARKsの動作方法は次のとおりです: 𝑛個の値を取り、Reed-Solomonに拡張してより多くの値になります（通常は8𝑛、通常は2𝑛から32𝑛の間）、その後、拡張からいくつかのMerkleブランチをランダムに選択し、それらにいくつかのチェックを行います。ハイパーキューブは各次元で長さ2を持ちます。したがって、それを直接拡張することは実用的ではありません: 16の値からMerkleブランチをサンプリングするのに十分な「スペース」がありません。代わりに、ハイパーキューブを正方形だと思い込むのです!

シンプルビニウス - 例

See こここのプロトコルのPython実装のため。

例を挙げて、便宜上通常の整数を使用します（実際の実装では、これはバイナリフィールド要素になります）。最初に、コミットするハイパーキューブを取り、それを正方形としてエンコードします。

今、私たちはReed-Solomonを拡張しました。つまり、各行をx = {0, 1, 2, 3}で評価される3次多項式として扱い、同じ多項式をx = {4, 5, 6, 7}で評価します。

数字が急速に増加することに注意してください！これが実装時に常に通常の整数の代わりに有限体を使用する理由です：例えば、整数を11で割った余りを使用した場合、最初の行の拡張は単に[3, 10, 0, 6]になります。

自分で拡張して数字を検証したい場合は、ここで遊んでみることができます私の単純なReed-Solomon拡張コードはここにあります.

次に、この拡張機能を列として扱い、列のMerkleツリーを作成します。 Merkleツリーのルートは私たちのコミットメントです。

ここで、証明者がある時点でこの多項式の評価を証明したいと仮定しましょう r={r0,r1,r2,r3} 。Binius には、他の多項式コミットメントスキームよりもやや弱いニュアンスが 1 つあります: 証明者は、マークル ルートにコミットするまで s を知らないか、推測できないはずです (言い換えれば、r はマークル ルートに依存する擬似乱数値である必要があります)。これにより、このスキームは「データベース検索」には役に立たなくなります(例:「OK、あなたは私にマークルルートを与えました、今私にP(0,0,1,0)を証明してください!」)。しかし、私たちが実際に使っているゼロ知識証明プロトコルは、一般的に「データベース検索」を必要としません。ランダムな評価点で多項式をチェックするだけで済みます。したがって、この制限は私たちの目的には問題ありません。

仮に𝑟={1,2,3,4}を選択すると、（この時点で多項式の値は−137になります；確認できますこのコードで）. 今、実際に証明を行うプロセスに入ります。 𝑟を2つの部分に分割します: 最初の部分{1,2}は、行内の列の線形結合を表し、2番目の部分{3,4}は行の線形結合を表します。 列部分の「テンソル積」を計算します。

そして、行の部分に関しては、

これは、各セットから1つの値のすべての可能な積のリストを意味します。行の場合、次のようになります:

[(1-r2)(1-r3), (1-r3), (1-r2)r3、r2*r3]

r={1,2,3,4}を使用する（つまり、r2=3およびr3=4）:

[(1-3)(1-4), 3(1-4),(1-3)4,34] = [6, -9 -8 -12]

今、この既存の行の線形結合を取ることにより、新しい「行」𝑡′を計算します。つまり、次のように取ります：

ここで起こっていることを部分評価として見ることができます。もし、全体のテンソル積 ⨂𝑖=03(1−𝑟𝑖,𝑟𝑖) を全ての値の完全なベクトルで掛け合わせたら、評価値 𝑃(1,2,3,4)=−137 が得られます。ここでは、評価座標の半分しか使用しない部分テンソル積を掛け合わせ、𝑁値のグリッドを𝑁値の行に縮小しています。この行を他の誰かに渡すと、他の半分の評価座標のテンソル積を使用して残りの計算を完了することができます。

プルーバは、この新しい行𝑡′と、いくつかのランダムにサンプリングされた列のMerkle証明を検証者に提供します。これは𝑂(𝑁)データです。われわれの説明的な例では、プルーバが最後の列のみを提供するようにします。実際の生活では、セキュリティを確保するために、プルーバは数ダースの列を提供する必要があります。

今、私たちはReed-Solomonコードの線形性を利用しています。使用している主要な特性は次のとおりです：Reed-Solomon拡張の線形結合を取ると、線形結合のReed-Solomon拡張と同じ結果が得られます。この種の「順序の独立性」は、両方が線形である2つの操作がある場合によく起こります。

検証者はまさにこれを行います。 彼らは𝑡′の拡張を計算し、証明者が以前に計算した列の同じ線形結合を計算します（ただし、証明者が提供した列にのみ）。 そして、これら2つの手順が同じ答えを与えることを検証します。

この場合、𝑡′を拡張して同じ線形結合（[6,−9,−8,12]）を計算すると、両方とも同じ答え（−10746）が得られます。これは、Merkleルートが「善意で」（または少なくとも「十分に近い」）構築され、𝑡′と一致することを証明します：少なくとも大部分の列が互換性があり、𝑡′と互換性があります。

ただし、検証者はまだ1つだけ確認する必要があります：実際に{𝑟0..𝑟3}で多項式の評価をチェックします。これまで、検証者の手順のいずれも、証明者が主張した値に実際に依存していませんでした。したがって、ここでそのチェック方法を説明します。評価点の「列部分」とラベル付けしたもののテンソル積を取ります。

この例では、r={1,2,3,4}となるため、選択された列の半分は{1,2}となります。これは、

そして、今度は𝑡′のこの線形結合を取ります：

これは、多項式を直接評価した場合に得られる答えと完全に等しい

上記は、「単純な」Biniusプロトコルの完全な説明にかなり近いものです。これには、たとえば、データが行と列に分割されるため、フィールドのサイズが半分で済むなど、すでにいくつかの興味深い利点があります。しかし、これでは、バイナリで計算を行うことの利点を完全に実現するにはほど遠いものです。このためには、完全なBiniusプロトコルが必要になります。しかし、その前に、バイナリフィールドについてより深く理解しましょう。

バイナリフィールド

最小の可能なフィールドは2で割った算術であり、それは非常に小さく、その加算と乗算の表を書き出すことができます。

私たちは、拡張を取ることでより大きなバイナリフィールドを作ることができます： 𝐹2（2を法とする整数）から始めて、𝑥2=𝑥+1と定義した場合、次の加法と乗法の表が得られます。

この構築を繰り返すことで、バイナリフィールドを任意の大きさに拡張できることがわかりました。実数上の複素数の場合、新しい要素𝑖を追加できますが、それ以上追加することはできません(四元数は存在しますが、数学的に奇妙です、例: 𝑎𝑏≠𝑏𝑎)。有限体では、新しい拡張を永遠に追加できます。具体的には、要素を次のように定義します:

そしてその先へ。これはしばしばタワー構造と呼ばれ、各々の連続した拡張が新しい層をタワーに加えると見なされるためです。これは任意のサイズのバイナリフィールドを構築する唯一の方法ではありませんが、Biniusが利用する独自の利点があります。

これらの数値はビットのリストとして表現できます、例えば1100101010001111。最初のビットは1の倍数を表し、2番目のビットは𝑥0の倍数を表し、その後のビットは次のような倍数を表します: 𝑥1、𝑥1∗𝑥0、𝑥2、𝑥2∗𝑥0、などなど。このエンコーディングは素敵なので、分解することができます。

これは比較的一般的でない表記ですが、私はバイナリフィールド要素を整数として表現するのが好きです。より有意ビットが右側にあるビット表現を取ります。すなわち、1=1、𝑥₀=01=2, 1+𝑥₀=11=3, 1+𝑥₀+𝑥₂=11001000=19、など。この表現では、1100101010001111は61779です。

バイナリフィールドでの加算はXORだけです(ちなみに減算も同様です); これはつまりx+x=0となることに注意してください。2つの要素x*yを乗算するには、非常に単純な再帰アルゴリズムがあります: 各数値を半分に分割します。

その後、乗算を分割します：

最後のピースは少しトリッキーです。なぜなら、縮小規則を適用し、𝑅𝑥∗𝑅𝑦∗𝑥𝑘2 を 𝑅𝑥∗𝑅𝑦∗(𝑥𝑘−1∗𝑥𝑘+1) に置き換えなければならないからです。掛け算を行う効率的な方法は他にもあります。カラツバ法や高速フーリエ変換の類似物などですが、それらについては興味を持った読者にそれらを見つけ出す演習として残しておきます。

バイナリフィールドでの除算は、乗算と逆数を組み合わせて行われます。逆数を行う「単純ですが遅い」方法は、一般化されたフェルマーの小定理の応用です。また、より複雑ですが効率的な逆数アルゴリズムもあります。Gate詳細は、ここ. あなたは使用することができますここにコードバイナリフィールドの加算、乗算、および除算を自分で試してみる。

左側：4ビットバイナリフィールド要素の加算テーブル（即ち、1、𝑥の組み合わせだけで構成される要素）₀，𝑥₁そして 𝑥₀𝑥₁).

Right: 4ビットバイナリフィールド要素の乗算テーブル。

この種のバイナリフィールドの美しいところは、「通常の」整数とモジュラー算術の最良の部分を組み合わせていることです。通常の整数のように、バイナリフィールド要素は無制限です：望む限り拡張できます。ただし、モジュラー算術のように、特定のサイズ制限内の値に対する操作を行う場合、すべての答えも同じ境界内に留まります。たとえば、42の累乗を取ると、次のようになります：

255ステップ後、42に戻ります²⁵⁵ = 1. 正の整数や剰余算術と同様に、彼らは通常の数学的法則に従います: ab=ba、a(b+c)=ab+a*c、いくつかの奇妙な新しい法律もあります。

最後に、バイナリフィールドを使用すれば、ビットを簡単に扱うことができます：2に収まる数字で計算を行う場合^kビットが適合する 2k ビットになるように出力されるため、恥ずかしい状況を避ける。Ethereum の EIP-4844 では、blob の各「ブロック」はデジタルモジュール 52435875175126190479447740508185965837690552500527637822603658699938581184513 でなければならず、バイナリデータをエンコードするためには、一部のスペースを捨てて追加の A チェックを行い、各要素が 2 より小さい値を格納していることを確認する必要がある。²⁴⁸これは、バイナリフィールド演算がコンピューター上で非常に高速であることを意味します - CPUと理論的には最適なFPGAおよびASICデザインの両方がそうであるということも意味します。

これが意味するところは、上記で行ったリード・ソロモン符号化のようなことを、私たちが見たように整数の「爆発」を完全に回避する方法で行うことができるということです。そして、非常に「爆発的」な方法で行うことができます。コンピューターが得意な種類の計算、つまり「ネイティブ」な方法です。バイナリフィールドの「分割」属性 - 1100101010001111=11001010+10001111*x のやり方₃そして、私たちのニーズに応じてそれを分割することも、多くの柔軟性を実現するために重要です。

フルビニウス

見るこここのプロトコルのPython実装用

今、私たちは「フルビニウス」に到達できます、「シンプルビニウス」を調整して(i)バイナリフィールド上で機能し、(ii)個々のビットにコミットできます。このプロトコルは理解が難しいです、なぜならビットの行列を見る方法を行ったり来たりするからです、これは通常、暗号プロトコルを理解するのにかかる時間よりも私にとって理解するのに時間がかかりました。しかし、一度バイナリフィールドを理解すれば、ビニウスが依存する「難しい数学」はありません。これは楕円曲線対、代数幾何学のどんどん深いウサギ穴があるわけではないです。ここでは、バイナリフィールドが必要です。

再度、全体の図を見てみましょう：

今では、ほとんどのコンポーネントに精通しているはずです。ハイパーキューブをグリッドに「平坦化」するアイデア、評価点のテンソル積として行の組み合わせと列の組み合わせを計算するアイデア、そして「Reed-Solomon拡張してから行の組み合わせを計算する」、そして「行の組み合わせを計算してからReed-Solomon拡張する」間の同値性を確認するアイデアは、すべて単純なBiniusにありました。

「完全なBinius」での新機能は基本的に3つあります:

• ハイパーキューブおよび正方形の個々の値は、ビット（0または1）である必要があります
• 拡張プロセスは、ビットをより多くのビットに拡張します。ビットを列にグループ化し、一時的にそれらがより大きなフィールド要素であるかのように見せかけます。
• 行の組み合わせステップの後、要素ごとの「ビットに分解」ステップがあり、そのステップでは拡張を再びビットに変換します

順番に両方を説明します。最初に、新しい拡張手順です。リード・ソロモン符号には、𝑛個の値を𝑘∗𝑛個の値に拡張する場合、座標として使用できる𝑘∗𝑛個の異なる値を持つフィールドで作業する必要があるという基本的な制限があります。 𝐹₂（別名、ビット）、それはできません。そして私たちが行うのは、隣接する 𝐹 を「パック」することです₂ここでは、2ビットずつ要素を{0,1,2,3}に詰め込んでいます。 なぜなら、拡張機能には4つの評価点しかないため、それで十分だからです。 「実際の」証明では、おそらく一度に16ビットをまとめてバックアップするでしょう。 その後、これらのパックされた値でリード・ソロモン符号を実行し、再びビットに戻します。

今、行の組み合わせです。 「ランダムな点で評価する」を暗号的に安全にするためには、その点がかなり大きな空間からサンプリングされる必要があります。ハイパーキューブ自体よりもはるかに大きい空間からサンプリングされるため、ハイパーキューブ内の点はビットですが、ハイパーキューブの外の評価ははるかに大きくなります。上記の例では、「行の組み合わせ」は[11,4,6,1]となります。

これは問題を提起します：ビットのペアをより大きな値に組み合わせ、その後にリード・ソロモン拡張を行う方法はわかっていますが、はるかに大きな値のペアに対して同じことをする方法はどのようにすればよいのでしょうか？

Biniusのトリックは、ビット単位で行うことです：各値の個々のビットを見ます（例えば、「11」とラベル付けしたものは[1,1,0,1]です）、そして行方向に拡張します。つまり、各要素の1行で拡張手順を実行し、次に𝑥0行、次に「𝑥」を実行します。₁“行、次に𝑥₀∗𝑥₁行、など（まあ、おもちゃの例ではそこで停止しますが、実際の実装では128行まで進むことがあるでしょう（最後の行は𝑥になります₆∗ …∗ 𝑥₀)).

要約:

• 超立方体内のビットを取り、それらをグリッドに変換します
• 次に、各行の隣接するビットグループをより大きなフィールド要素として扱い、それらに算術演算を行って行をReed-Solomonで拡張します
• 次に、各列のビットの行の組み合わせを取り、出力として各行の(4x4より大きい場合ははるかに小さい)ビットの列を取得します
• その後、出力を行列として見て、そのビットを再び行として扱います

なぜこれが機能するのですか？通常の数学では、数字を桁ごとに分割し始めると、(しばしば)順番を変えて線形操作を行い同じ結果を得る能力は機能しなくなります。例えば、数字345から始めて、8を掛けてから3を掛けると8280になりますが、これらの操作を逆に行っても、やはり8280になります。しかし、2つの手順の間に「桁ごとに分割」操作を挿入すると、破綻します：8を掛けてから3を掛けると、次のようになります：

しかし、3倍してから8倍すると、次のようになります:

しかし、タワー構造で構築されたバイナリフィールドでは、このアプローチは機能します。その理由は、それらが分離可能であることにあります：大きな値に小さな値を掛けると、各セグメントでの処理が各セグメントに留まります。1100101010001111を11で乗算すると、1100101010001111の最初の因数分解と同じになります。

そして、それぞれのコンポーネントを11倍にします。

すべてをまとめる

一般的に、ゼロ知識証明システムは、多項式に関する文を作成することによって基礎となる評価に関する文を同時に表現します：フィボナッチの例で見たように、𝐹(𝑋+2)−𝐹(𝑋+1)−𝐹(𝑋)=𝑍(𝑋)∗𝐻(𝑋) は、フィボナッチ計算のすべてのステップを同時にチェックします。我々は、ランダムな点での評価を証明することで、多項式に関する文をチェックします。このランダムな点でのチェックは、全体の多項式をチェックする代わりに立っています：もし多項式方程式が一致しない場合、特定のランダム座標で一致する確率は非常に低いです。

実際には、効率の低下の主要な原因の1つは、実際のプログラムでは、ほとんどの数値が小さなものであることから来ています： forループ内のインデックス、True / False値、カウンターなどです。しかし、Reed-Solomon符号化を使用してデータを「拡張」し、Merkleプルーフベースのチェックを安全にするために必要な冗長性を与えると、ほとんどの「余分な」値が、元の値が小さい場合でも、フィールドの全サイズを占有するようになります。

これを解決するために、フィールドを可能な限り小さくしたいと考えています。 Plonky2は、256ビットの数値を64ビットの数値に減らし、Plonky3はさらに31ビットまで減らしました。しかし、これでも最適ではありません。バイナリフィールドを使用すると、個々のビットを処理できます。これにより、エンコードが「密」になります：実際の基礎データがnビットである場合、エンコードもnビットになり、拡張部分は8 * nビットになり、余分なオーバーヘッドはありません。

今度は、図を三度目に見てみましょう：

Biniusでは、多変数多項式に取り組んでいます：ハイパーキューブ 𝑃(x₀,x₁,…x_k)、個々の評価𝑃(0,0…0)、𝑃(0,0…1)から𝑃(1,1,…1)までが、我々が関心を持つデータを保持しています。点での評価を証明するには、同じデータを正方形として「再解釈」します。次に、ビットグループに対するReed-Solomon符号化を使用して、各行を拡張して、ランダムMerkleブランチクエリに安全性を確保するために必要な冗長性をデータに与えます。その後、行のランダムな線形結合を計算し、新しい結合された行が実際に我々が関心を持つ評価を保持するように設計された係数で行います。この新しく作成された行（これは128行のビットとして再解釈されます）、およびいくつかのランダムに選択されたMerkleブランチを持つ列が検証者に渡されます。

検証者はその後、「拡張の行の組み合わせ」（あるいはむしろ、拡張のいくつかの列）と「行の組み合わせの拡張」を行い、その2つが一致することを検証します。その後、列の組み合わせを計算し、証明者が主張している値を返すかどうかを確認します。そして、これが私たちの証明システム（あるいはむしろ、証明システムの主要な構築ブロックである多項式コミットメントスキーム）です。

何をカバーしませんでしたか？

• 実際に検証者の計算効率を実現するために必要な行を拡張する効率的なアルゴリズムを用います。バイナリフィールド上での高速フーリエ変換を使用します、ここ（ただし、実際の実装は異なりますが、この投稿では、再帰的な拡張に基づかない効率の悪い構造を使用しているため、違うことになります）。
• アリスメタイゼーション。一変数多項式は便利です。なぜなら、F(X+2)-F(X+1)-F(X) = Z(X)*H(X)のようなことができ、計算の隣接するステップを関連付けることができるからです。ハイパーキューブでは、「次のステップ」という言葉は「X+1」と比べてはるかに解釈が難しいです。X+k、kの累乗を使用することもできますが、このジャンプする挙動はBiniusの多くの主要な利点を犠牲にするでしょう。その解決策は次のように提示されています。Binius paper（セクション4.3を参照）、しかし、これ自体が非常に複雑な問題です。
• 特定値のチェックを実際に安全に行う方法。フィボナッチの例では、キーの境界条件をチェックする必要があります: F(0)=F(1)=1およびF(100)の値。しかし、「生の」Biniusでは、事前に既知の評価点でチェックすることは安全ではありません。既知の評価チェックを未知の評価チェックに変換する簡単な方法がいくつかあり、それはサムチェックプロトコルと呼ばれるものを使用して行われますが、ここではそれについては触れませんでした。
• 最近注目されているProofシステムを超効率的にする方法として使用されるルックアッププロトコル。 Biniusは多くのアプリケーションでルックアッププロトコルと組み合わせることができます。
• 平方根の検証時間を超える。平方根は高価です：Biniusの証明のビットは約11 MBです。これを補うために、他の証明システムを使用して「Biniusの証明」を行うことで、Biniusの効率性と小さな証明サイズの両方を得ることができます。もう1つのオプションは、はるかに複雑なFRI-Biniusプロトコルで、ポリ対数サイズの証明（通常のFRIのように）を生成します。
• Biniusが「SNARKに適したもの」としてどのように影響するか。基本的な要約は、Biniusを使用すると、計算を「算術に適した」ものにする必要があまりないことです。「通常の」ハッシュは伝統的な算術ハッシュよりも効率的ではなくなり、乗算モジュロやモジュロは乗算モジュロよりも大きな頭痛にはならなくなります。しかし、これは複雑なトピックです。すべてが2進数で行われると多くのことが変わります。

これから数ヶ月で、バイナリフィールドベースの証明技術にさらなる改善が期待されています。

免責事項：

1. この記事は[から転載されていますPanews]. 原題は「Vitalik详解Binius:基于二进制字段的高效证明系统」。すべての著作権は原著作者に帰属します[Vitalik Buterin*]. If there are objections to this reprint, please contact the Gate Learnチーム、そして彼らは迅速に対処します。
2. 責任の免責事項：この記事で表現されている意見および見解は著者個人のものであり、投資アドバイスを構成するものではありません。
3. 他の言語への記事の翻訳は、Gate Learnチームによって行われます。特に言及がない限り、翻訳された記事のコピー、配布、または盗用は禁止されています。