Binius STARKsの分析と最適化

1. イントロダクション楕円曲線ベースのSNARKとは異なり、STARKはハッシュベースのSNARKと見なすことができます。STARKの現在の非効率の主な課題の1つは、実際のプログラムのほとんどの値が比較的小さいこと、例えばforループのインデックス、ブール値、カウンターなどです。しかし、Merkleツリーベースの証明のセキュリティを確保するため、Reed-Solomon符号化がデータを拡張するために使用されます。これにより、元の値自体が小さくても、多数の冗長な値がフィールド全体を占有する結果になります。この非効率性への対処策として、フィールドサイズを縮小することが主要な戦略となっています。

表1に示されるように、STARKの第1世代はコーディング幅が252ビットで、第2世代は64ビット、第3世代は32ビットでした。第3世代でコーディング幅が減少しましたが、依然として著しい無駄があります。一方、バイナリフィールドは直接ビットレベルの操作が可能で、最小限の無駄でコンパクトかつ効率的なエンコーディングが可能です。この効率性は、STARKの第4世代で実現されています。

テーブル1：STARKs派生パスゴールディロックス、ベビーベア、メルセンヌ31などの有限体と比較すると、最近注目されているバイナリ体研究は1980年代にさかのぼります。今日、バイナリ体は暗号学で広く使用されており、顕著な例には次のようなものがあります:

• Advanced Encryption Standard (AES)は、- 𝐹28- フィールド;- Galois Message Authentication Code (GMAC), based on the - F2128会場- field;- QRコードは、リード・ソロモン符号化を利用しています。- 𝐹28- フィールド;- SHA-3コンテストのファイナリストであるGrøstlハッシュ関数をベースにした、元のFRIおよびzk-STARKプロトコル- 𝐹28- フィールドは、再帰ハッシュアルゴリズムに適しています。小さいフィールドが使用される場合、フィールドの拡張操作はセキュリティを確保するためにますます重要になります。Biniusが使用するバイナリフィールドは、セキュリティと実用性を両立させるために、完全にフィールドの拡張に依存しています。プルーバー操作に関与する多くの多項式計算は、拡張フィールドに入る必要がなく、基底フィールドでのみ操作する必要があるため、小さいフィールドで高い効率を実現しています。ただし、ランダムポイントのチェックとFRI計算は、必要なセキュリティレベルを確保するために、より大きな拡張フィールドで実行する必要があります。

バイナリフィールドに基づいた証明システムを構築する際の2つの実用的な課題があります。第1に、STARKsでのトレース表現に使用されるフィールドサイズは、多項式の次数よりも大きい必要があります。第2に、STARKsでのMerkleツリーコミットメントに使用されるフィールドサイズは、Reed-Solomonエンコーディング拡張後のサイズよりも大きくする必要があります。

Biniusは、2つの問題に対処するための革新的なソリューションであり、同じデータを2つの異なる方法で表現します。まず、単変量多項式ではなく多変量（具体的には多線形）多項式を使用し、その評価を通じて計算トレース全体を「ハイパーキューブ」上で表現します。第二に、ハイパーキューブの各次元の長さが2であるため、STARKsのような標準的なReed-Solomon拡張を実行することはできませんが、ハイパーキューブは正方形として扱うことができ、この正方形に基づいてReed-Solomon拡張を実行することができます。この方法は、セキュリティを確保するだけでなく、エンコーディング効率と計算性能を大幅に向上させます。

2. ビニウスの原則ほとんどの最新のSNARKシステムの構築は、通常、次の2つのコンポーネントで構成されています:

• 情報理論に基づく多項式インタラクティブオラクル証明（PIOP）：証明システムの中核であるPIOPは、計算関係を入力から検証可能な多項式方程式に変換します。異なるPIOPプロトコルにより、証明者は検証者との相互作用を通じて多項式を段階的に送信することができます。これにより、検証者はわずかな多項式評価のみをクエリとして使用して計算の正確性を確認することができます。PLONK PIOP、Spartan PIOP、HyperPlonk PIOPなどのさまざまなPIOPプロトコルは、多項式式を異なる方法で扱うため、全体的なSNARKシステムのパフォーマンスと効率に影響を与えます。- 多項式コミットメントスキーム(PCS):PCSは、PIOPによって生成された多項式方程式が有効であることを証明するために使用される暗号化ツールです。これにより、証明者は多項式にコミットし、多項式に関する追加情報を明らかにすることなくその評価を検証できます。一般的なPCSスキームには、KZG、Bulletproofs、FRI(Fast Reed-Solomon IOPP)、Brakedownがあり、それぞれが異なるパフォーマンス特性、セキュリティ保証、および適用可能なシナリオを提供します。異なるPIOPとPCSスキームを選択し、適切な有限体または楕円曲線と組み合わせることにより、異なる特性を持つ証明システムを構築できます。例えば、

• Halo2: PLONK PIOPをBulletproofs PCSと組み合わせ、Pasta曲線上で動作します。Halo2は拡張性を考慮して設計されており、ZCashプロトコルで以前使用されていた信頼性のあるセットアップを排除します。- Plonky2：PLONK PIOPとFRI PCSを組み合わせ、Goldilocksフィールドに基づいています。 Plonky2は効率的な再帰に最適化されています。これらのシステムを設計する際に、選択されたPIOP、PCS、有限体または楕円曲線の互換性は、正確性、パフォーマンス、およびセキュリティを確保するために重要です。これらの組み合わせは、SNARK証明のサイズ、検証の効率に影響を与え、システムが信頼できるセットアップなしで透明性を実現できるかどうか、および再帰証明や証明集約などの高度な機能をサポートすることができます。

Biniusは、HyperPlonk PIOPとBrakedown PCSを組み合わせ、バイナリフィールドで動作します。具体的には、Biniusは効率とセキュリティの両方を実現するために、5つの主要な技術を組み込んでいます:

• バイナリフィールドのタワーに基づいた算術：これはBiniusの計算基盤を形成し、バイナリフィールド内での簡略化された操作を可能にします。- HyperPlonkの積と順列のチェック:Biniusは、HyperPlonkの積と順列のチェックをPIOPに適応させ、変数とその順列間の安全で効率的な一貫性を確保します。- 新しい多線形シフトの引数：この最適化は、小さなフィールド内での多線形関係の検証を改善し、全体的な効率を向上させます。- Lassoルックアップ引数の改善:このプロトコルには、この高度な引数により、より柔軟で安全なルックアップメカニズムが組み込まれています。- 小場多項式コミットメントスキーム(PCS):Biniusは、小場に合わせたPCSを採用し、大場に共通するオーバーヘッドを削減し、バイナリ場での効率的な証明システムを可能にします。これらの革新により、Biniusは、コンパクトで高性能なバイナリフィールドに最適化されたSNARKシステムを提供し、堅牢なセキュリティとスケーラビリティを維持しています。

2.1 有限フィールド：バイナリフィールドのタワーに基づく算術バイナリフィールドのタワーは、効率的な計算と効率的な算術化という2つの主要な要因により、高速で検証可能な計算を実現する上で重要な役割を果たします。バイナリフィールドは、高度に効率的な算術演算をサポートするため、パフォーマンスに敏感な暗号アプリケーションに理想的です。さらに、その構造により、バイナリフィールドで実行された演算は、コンパクトで簡単に検証可能な代数的形式で表現できるため、算術化プロセスを簡素化できます。これらの特性と、バイナリフィールドのタワーの階層構造との組み合わせにより、Biniusのようなスケーラブルな証明システムに特に適しています。

"canonical"という用語は、2進フィールド内の要素のユニークで直接的な表現を指します。たとえば、最も基本的な2進フィールド$\mathbb{F}2において

, 任意のビットストリングキャンベディレクトリエクトリマップトアクビットビナリフィルドデレメント. ディスディファースフロムプリマフィエルドス, ウィチドノトオフアンニカルレプリセントワイソフリディーリメント. アルソウガ32ビットプリマフィエルドカンフィットウィン32ビットス, ノートヴェリ32ビットストリングカヌニクエリリコレスポンドトオフィエルデレメント, ウェレアスビナリフィエルドスプロビデトディスオネマッピング. インプリメフィエルドス

\mathbb{F}_p$ 、一般的な縮約方法には、バレット縮約、モンゴメリ縮約、およびメルセンヌ-31やゴールディロックス-64などの特定の有限体用の専門の縮約方法が含まれます。 二進体では、特殊縮約（AESで使用）、モンゴメリ縮約（POLYVALで使用）、および再帰縮約（Tower fieldsで使用）が一般的な縮約方法です。Prime Field vs. Binary Field ECCハードウェア実装の設計空間の探索バイナリフィールドでは、加算や乗算において繰り上げが不要であることに注意してください。また、バイナリフィールドにおける2乗は、簡略化ルールにより非常に効率的です。

(𝑋+𝑌)2=𝑋2+𝑌2

.

図1. 二進界の塔

図1に示されているように、128ビットの文字列は、バイナリフィールドのコンテキスト内で複数の方法で解釈できます。それは128ビットのバイナリフィールド内の唯一の要素として表示されるか、2つの64ビットのタワーフィールド要素、4つの32ビットのタワーフィールド要素、16個の8ビットのタワーフィールド要素、または128個の要素に解析されることができます。

𝐹2

。この表現の柔軟性は、ビット文字列の型キャストであるため、計算オーバーヘッドは発生しません。これは非常に興味深く有用な特性であり、より小さなフィールド要素を追加の計算コストなしにより大きなフィールド要素にパックすることができます。Biniusプロトコルは、この特性を活用して計算効率を向上させます。さらに、論文2 の特性のタワーフィールドでの効率的な逆変換について乗算、二乗、および逆数の計算複雑度を探究します。

𝑛

-bit tower binary fields (decomposable into

𝑚

-ビットのサブフィールド)。

2.2 PIOP: 適応されたHyperPlonk製品および置換チェック — 2進フィールドに適していますBiniusプロトコル内のPIOPデザインは、HyperPlonkからのインスピレーションを得ており、多項式と多変量集合の正確性を検証するための一連のコアチェックを組み込んでいます。これらのチェックは、バイナリフィールド上で動作する場合に特に、証明システム内の計算の整合性を確保するために必要です。主要なチェックには、次のものがあります。

• gateCheck: プライベート証人を確認します- 𝜔- および公開入力- 𝑥- 回路の動作関係を満たす- 𝐶(𝑥,𝜔)=0- 、回路の正しい実行を確認します。- PermutationCheck：2つの多変量多項式の評価結果が一致しているかを検証します- 𝑓- そして- 𝑔- ブール超立方体上の順列関係- 𝑓(𝑥)=𝑓(𝜋(𝑥))- 多項式変数間の一貫性を確保すること。- LookupCheck：多項式の評価が指定されたルックアップテーブル内にあるかどうかをチェックします。- 𝑓(𝐵𝜇)⊆𝑇(𝐵𝜇)- 特定の値が指定された範囲内に収まるように確認すること。- MultisetCheck: 2つの多変数集合が等しいかどうかを確認します、つまり、 ${(x*{1,i},x*{2,i})}{i \in H} = {(y{1,i},y*{2,i})}*{i \in H}$、さまざまな集合間の一貫性を確保する。- ProductCheck：合理多項式のブール超立方体上での評価が宣言された値に等しいことを保証します、つまり、- ∏𝑥∈𝐻𝜇𝑓(𝑥)=𝑠- 多項式積の正確性を確認する。- ZeroCheck: 多変量多項式がブール超立方体の任意の点でゼロと評価されるかどうかを検証します。- ∏𝑥∈𝐻𝜇𝑓(𝑥)=0- すべてに対して- 𝑥∈𝐵𝜇- 多項式内のゼロの適切な分布を確保します。- SumCheck: 多変数多項式の評価の和が宣言された値と等しいかどうかを確認します、すなわち、- ∑𝑥∈𝐻𝜇𝑓(𝑥)=𝑠- . 多変数多項式の評価を一変数多項式の評価に削減することで、検証者の計算複雑性を低下させます。 SumCheck はまた、バッチ処理を可能にし、ランダムな数値を使用して線形結合を構築して複数のインスタンスを一括処理します。- BatchCheck: SumCheckの拡張で、複数の多変量多項式評価の正確性を検証し、プロトコルの効率を向上させます。BiniusとHyperPlonkは、プロトコルの設計にいくつかの類似点を共有していますが、Biniusは次の主要な改善点を導入しています。

• ProductCheckの最適化：HyperPlonkでは、ProductCheckには分母が必要です。- 𝑈- ハイパーキューブ全体でゼロでないこと、および製品が特定の値に一致することを確認します。 Biniusは、製品値を1に設定することで、全体的な計算の複雑さを減らすことで、このチェックを簡素化します。- ゼロ除算の処理：HyperPlonkはゼロ除算の問題を効果的に解決しておらず、そのため保証することが困難です。- 𝑈- ハイパーキューブ上で0以外のままです。 Biniusは、ゼロ除算シナリオを適切に処理することで、分母がゼロの場合でもProductCheckが正常に機能し、任意の積の値に拡張することを可能にします。- Cross-Column PermutationCheck: HyperPlonkには、クロスカラムの置換チェックのサポートがありません。Biniusは、複数の列にわたるより複雑な多項式の置換を管理できるようにするために、クロスカラムPermutationCheckのサポートを導入することで、この制限に対処しています。このため、Biniusは、既存のPIOP SumCheckメカニズムを改善することにより、プロトコルの柔軟性と効率を向上させ、特により複雑な多変数多項式の検証に強力な機能を提供することで、HyperPlonkの制約を解消し、バイナリフィールドに基づいた将来の証明システムの基盤を築いています。

2.3 PIOP：新しい多線形シフト議論—ブールハイパーキューブに適用可能Biniusプロトコルでは、仮想多項式の操作と構築が効率的な多項式処理を可能にするために重要な役割を果たしています。これらの操作には、主に2つの主要な技術が使用されています。

• パッキング :パッキング法は、小さな要素を大きなドメインにグループ化することで、それらの処理を最適化します。具体的には、辞書式順序で隣接する要素は、通常はサイズの大きなブロックにパックされます- 2𝜅- . マルチリニア拡張（MLE）を利用することで、パックされた要素は新しい仮想多項式に変換され、効率的に評価および処理することができます。この方法により、ブール超立方体上の操作のパフォーマンスが向上し、関数が再構築されます。- 𝑡- 計算効率の良い形式に- Shift Operator : シフト演算子は、与えられたオフセットに基づいて、ブロック内の要素を循環的にシフトして並べ替えます- 𝑜- . このシフトは、サイズのブロックに適用されます。- 2𝑏- 、事前に定義されたオフセットに従って、ブロック内のすべての要素が均一にシフトされることを保証する演算子です。この演算子は、ブロックサイズと線形に増加するため、高次元空間での仮想多項式を扱う際に特に有用であり、大規模なデータセットや複雑なブール超立方体計算のための理想的な技術です。### 2.4 PIOP：適応されたラッソルックアップ引数- 2進フィールドに適用可能BiniusのLassoプロトコルは、ベクトル内の要素を効率的に証明する方法を提供しています。

𝑎∈𝐹𝑚

は、事前に定義されたテーブル内に含まれています

𝑡∈𝐹𝑛

. この検索引数は、「ルックアップシンギュラリティ」という概念を導入し、多線形多項式コミットメントスキームに適しています。 Lassoの効率は、主要な2つの側面で強調されています。

• Proof Efficiency : 実施時の証明- 𝑚- サイズのテーブル内での検索- 𝑛- 、プルーバーはコミットするだけで十分です- 𝑚+𝑛- 小さなフィールド要素、フィールドサイズはセットから選択される- 0,…,𝑚- 暗号化に依存する暗号化スキームでは、証明者のコストは- 𝑂(𝑚+𝑛)- グループ操作（例：楕円曲線の点の加算）。この効率性は、ブール超立方体で評価された多変数多項式がテーブル要素と一致するかどうかを検証するコストに加えて得られます。- 大きなテーブルへのコミットメントなし: テーブル - 𝑡- Lassoには、テーブルに直接的なコミットメントが必要ないため、非常に大きなテーブルを扱うことができます。- 2128- またはそれ以上）。証明者の実行時間は、テーブルでアクセスされる特定のエントリにのみ依存します。任意の整数パラメータに対して- 𝑐>1- 、主なコストは証明のサイズに関連しており、成長します - 3⋅𝑐⋅𝑚+𝑐⋅𝑛1/𝑐- committed field elements. These elements are also small, drawn from the set - 0、…、max𝑚、𝑛1/𝑐、𝑞−1- 、where - 𝑞- ベクトル内の最大値です- 𝑎- .Lassoプロトコルは、3つの主要なコンポーネントで構成されています:

• 大きなテーブルの仮想多項式抽象化：Lassoプロトコルは、仮想多項式を組み合わせて大きなテーブルのルックアップや操作を効率的に行い、パフォーマンスの低下なしにスケーラビリティを確保します。- Small Table Lookup : Lassoの中心には小さなテーブル検索があり、これはブール超立方体上で評価された仮想多項式が別の仮想多項式の評価の部分集合であるかどうかを検証するものです。このプロセスはオフラインメモリ検出に似ており、多重集合の検出タスクに帰着します。- マルチセットチェック：プロトコルは、2つの要素セットが一致するか、あらかじめ定義された条件を満たすかどうかを確認するための仮想メカニズムも組み込んでいます。Biniusプロトコルは、現在のフィールドが大きな特性(検索される列の長さよりもはるかに長い)の素数フィールドであると仮定して、バイナリフィールド演算にLassoを適応させます。BiniusはLassoプロトコルの乗法バージョンを導入し、証明者と検証者は、単に1を加算するのではなく、バイナリフィールド内の乗算ジェネレータを使用してインクリメントすることによって、プロトコルの「メモリカウンター」操作をインクリメントする必要があります。しかし、この乗法適応はさらなる複雑さをもたらします:加法インクリメントとは異なり、乗法ジェネレータはすべてのケースでインクリメントするわけではなく、代わりに0に単一の軌道を持ち、攻撃ベクトルを提示する可能性があります。この潜在的な攻撃を軽減するために、証明者は、プロトコルのセキュリティを確保するために、どこでもゼロ以外の読み取りカウンタベクトルにコミットする必要があります。

2.5 PCS：小規模フィールドに適応されたブレークダウンPCSBinius PCS（多項式コミットメントスキーム）の構築の核心的なアイデアは、パッキングです。Binius論文では、2つのBrakedown PCSスキームがバイナリフィールドを基にして提案されています。1つは連結符号を使用し、もう1つはブロックレベルエンコーディングを使用しており、Reed-Solomon符号の単独使用もサポートしています。2番目のBrakedown PCSスキームは、証明と検証のプロセスを簡素化しますが、最初のものよりもわずかに大きな証明サイズを生成します。しかし、このトレードオフは、提供される簡素化と実装上の利点によって十分に優れています。

Binius多項式コミットメントは、主に拡張フィールドでの評価を伴う小規模フィールド多項式コミットメント、小規模フィールドユニバーサル構築、およびReed-Solomon符号技術を用いたブロックレベルのエンコーディングを活用しています。

Biniusプロトコルでは、小さなフィールド上で多項式コミットメントを行います。拡張フィールド評価を使用します。

𝐾

、評価は拡張フィールドで行われます

𝐿/𝐾

この技術により、多変数多項式が確実になります。

𝑡(𝑋0,…,𝑋ℓ−1)

belongs to the domain

𝐾[𝑋0,…,𝑋ℓ−1]

評価ポイントは大きなフィールドにあります。

𝐿

. このコミットメント構造により、拡張フィールド内で効率的なクエリが可能となり、セキュリティと計算効率のバランスが取れます。

小規模ユニバーサル構造 この構造はフィールドなどの主要パラメータを定義します

𝐾

、その寸法

ℓ

, および関連する線形ブロックコード

𝐶

、拡張フィールドを確保しながら

𝐿

は安全な評価に十分大きいです。拡張フィールドの特性を活用することにより、Biniusは線形ブロックコードを介して堅牢なコミットメントを実現し、計算効率とセキュリティのバランスを保ちます。

小さなフィールド上で定義された多項式のためのリード・ソロモン符号を用いたブロックレベルのエンコーディング

、ザビニウスプロトコルエンジンリングガバナンスイングリード-ソロモンコード。 This chemical is a special offer by encoding the image of the market field.

\mathbb{F}{2^{16}}$ )、Reed-Solomon符号の効率と最大距離分離特性を利用しています。エンコード後、これらの行はMerkleツリーを使用してコミットされます。これにより、小規模フィールド多項式コミットの操作的複雑さが簡素化されます。このアプローチにより、通常大きなフィールドに関連する計算負荷なしに小規模フィールドの多項式を効率的に処理できます。

3. Biniusの最適化さらなるパフォーマンス向上のために、Biniusは以下の4つの主要な最適化を取り入れています:

• GKRベースのPIOP：GKR（Goldreich-Kalai-Rothblum）プロトコルは、バイナリフィールド乗算のLasso Lookupアルゴリズムを置き換えるために使用され、コミットメントプロセスのオーバーヘッドを大幅に削減します。- ZeroCheck PIOP最適化：この最適化は、プルーバと検証者の計算コストのバランスに対処し、ワークロードを効果的に分散することで、ZeroCheck操作をより効率的にします。- Sumcheck PIOP 最適化 : 小場の Sumcheck プロセスを最適化することで、Binius は小場を操作する際の全体的な計算負荷を軽減します。- PCS 最適化： FRI-Binius（Fast Reed-Solomon Interactive Oracle Proofs of Proximity）最適化を使用することで、Binius は証明のサイズを削減し、プロトコルのパフォーマンスを向上させ、証明生成と検証の両方の全体的な効率を改善します。### 3.1 GKRベースのPIOP: GKRを使用したバイナリフィールド乗算オリジナルのBiniusプロトコルでは、バイナリフィールドの乗算は、ワード内のリンブの数に基づいて線形加算操作に乗算を結び付けるルックアップベースのスキームを通じて処理されます。この方法はバイナリ乗算をある程度最適化していますが、リンブの数に比例して線形に関連付けられた補助的なコミットメントを導入します。GKRベースのアプローチを採用することで、Biniusプロトコルは必要なコミットメントの数を大幅に削減し、バイナリフィールドの乗算操作のさらなる効率化を実現することができます。

GKR (Goldwasser-Kalai-Rothblum) プロトコルの核となる考え方は、有限体上の層状演算回路で証明者 (P) と検証者 (V) の間の一致を達成することです

𝐹

。この回路の各ノードには、必要な関数を計算するための2つの入力があります。検証者の計算量を減らすために、プロトコルはSumCheckプロトコルを使用して、回路の出力ゲートの値に関する主張を下位レイヤーのゲートの値に徐々に簡素化し、最終的には入力に関する主張に単純化します。これにより、検証者は回路の入力の正当性を検証するだけで済みます。

ザGKRベースの整数乗算アルゴリズムBiniusでは、2つの32ビット整数のチェックを変換します

𝐴

そして

𝐵

満足する

𝐴⋅𝐵=?𝐶

into verifying whether

(gA)B=?gC

保有中

F264∗

。 この変換は、GKRプロトコルと組み合わさることで、多項式コミットメントに関連するオーバーヘッドを大幅に削減します。以前のBiniusルックアップベースのスキームと比較して、GKRベースの乗算アプローチでは、補助コミットメントが1つだけ必要であり、SumChecksのコストも削減されるため、アルゴリズムがより効率的になります。特に、SumChecksが追加のコミットメントよりも経済的な場合には、この方法がバイナリフィールド多項式コミットメントのコストを最小化する有望な解決策となっています。Biniusの最適化が進むにつれて、この方法の重要性は高まっています。

3.2 ZeroCheck PIOP 最適化：ProverとVerifierの計算コストのバランス調整論文ゼロチェックのPIOPのいくつかの改善プルーバー（P）と検証者（V）間の計算コストをバランスさせるための戦略を提案し、データの送信と計算の複雑さを減らすことに焦点を当てています。以下は主な最適化技術です:

• プルーバーのデータ送信を削減する検証者に一部の計算負荷を移譲することで、証明者のデータ送信を最小限に抑えることができます。たとえば、

𝑖

、プルーバーは送信します

𝑣𝑖+1(𝑋)

for

𝑋=0、…、𝑑+1

、そして検証者は、

𝑣𝑖=𝑣𝑖+1(0)+𝑣𝑖+1(1)

保有されています。

最適化：Proverは送信を回避できます

𝑣𝑖+1(1)

, バリデータはそれを計算できます

vi+1(1)=vi−vi+1(0)

.

最初のラウンドでは、Prover は

𝑣1(0)=𝑣1(1)=0

、一部の評価計算を省略し、計算および送信コストを削減します。

𝑑2𝑛−1𝐶𝐹+(𝑑+1)2𝑛−1𝐶𝐺

.

• プルーバーの評価ポイントの数を減らすラウンド中

𝑖

、証明者は送信する必要があります

𝑣𝑖+1(𝑋)

, 計算されたものとして

𝑣𝑖+1(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼,(𝑟,𝑋,𝑥))𝐶(𝑟,𝑋,𝑥)

。

最適化: 代わりに、プルーバーは送信することができます

𝑣𝑖+1′（𝑋）=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛（𝛼𝑖+1,…,𝛼𝑛−1、𝑥）𝐶（𝑟、𝑋、𝑥）

ここで、$v_i(X) = v_i'(X) \cdot \hat{\delta}{i+1}((\alpha_0, \dots, \alpha_i), (r, X))

.𝐴𝑠𝑡ℎ𝑒𝑉𝑒𝑟𝑖𝑓𝑖𝑒𝑟ℎ𝑎𝑠𝑎𝑐𝑐𝑒𝑠𝑠𝑡𝑜

\alpha

𝑎𝑛𝑑

r

,𝑡ℑ𝑒𝑑𝑒𝑔𝑟𝑒𝑒𝑜𝑓

v_i’(X)

𝑖𝑠𝑙𝑜𝑤𝑒𝑟𝑡ℎ𝑎𝑛𝑡ℎ𝑎𝑡𝑜𝑓

v_i(X)

,reducingtherequiredevaluationpoints.Theinter−roundcheckcanthenbesimplifiedas

(1 - \ alphai)v{i+1}’(0) + \alpha_i v{i+1}’(1) = v_i’(X),

サービス、および、アルコスティサップロヴェメントス、シンプロヴェメントシー

2^{n-1}(d - 1)C_F + 2^{n-1}dC_G.

𝐹𝑜𝑟

d = 3$、これらの最適化により、コストを5/3倍削減することができます。

• 代数的補間最適化正直な証明者にとって、多項式

𝐶(𝑥0,…,𝑥𝑛−1)

ゼロになります

ハン

そして、以下のように表現することができます。

𝐶(𝑥0,…,𝑥𝑛−1)=∑𝑖=0𝑛−1𝑥𝑖(𝑥𝑖−1)𝑄𝑖(𝑥0,…,𝑥𝑛−1)

. どこ

𝑄𝑖

は、順序付きの多項式除算から計算されます。

𝑅𝑛=𝐶

. 連続的な除算によって

𝑥𝑖(𝑥𝑖−1)

計算する

𝑄𝑖

と

𝑅𝑖

, with

𝑅0

多次元拡張を表す

𝐶

on

𝐻𝑛

、ゼロと見なされます。

解析度の解析

𝑄𝑖

. について

𝑗>𝑖

,

QJの

同じ程度を維持します

𝑥𝑖

as

𝐶

. について

𝑗=𝑖

、度が2減少し、

𝑗- スイッチオーバーラウンドの影響と改善要素 小規模フィールドのSumcheckプロトコルの最適化は、最適なスイッチオーバーラウンドの選択にかかっています𝑡

最適化バージョンから素朴なアルゴリズムに戻るプロトコルがマークするポイントです。実験結果から、改善係数は最適な切り替え点でピークに達し、その後放物線的なトレンドに従います。この点を超えると、効率が低下します。なぜなら、基本フィールドと拡張フィールドの乗算の比率が小さいフィールドでは大きくなるため、素朴なアルゴリズムに適時に戻る必要があるからです。

特定のアプリケーションでは、Cubic Sumcheck (

𝑑=3

)、小フィールドSumcheckプロトコルは、単純なアプローチに比べて桁数の改善を実現します。例えば、基本フィールドでは、桁数が改善されます。

𝐺𝐹[2]2. パフォーマンスへのベースフィールドサイズの影響 ベースフィールドが小さい場合（例えば、

、アルゴリズム4は素朴なアルゴリズムよりも約30倍の性能を発揮します。

𝐺𝐹[2]

)最適化されたアルゴリズムの効率を大幅に向上させることができます。拡張フィールドと基本フィールドの乗算のコストの差が大きいため、最適化されたアルゴリズムの改善要因がより大きくなります。

• カラツバアルゴリズムからの最適化ゲイン カラツバアルゴリズムは、小規模フィールドSumcheckプロトコルのパフォーマンス向上において重要な役割を果たします。ベースフィールドが𝐺𝐹[2]

アルゴリズム4は、アルゴリズム3に対して6倍、アルゴリズム4に対して30倍のピークの改善係数を達成し、アルゴリズム4がアルゴリズム3よりも5倍効率的であることを示しています。カラツバのアルゴリズムはランタイムの効率を向上させ、両方のアルゴリズムの切り替えポイントを最適化し、最適なポイントは、」である。

𝑡=5

アルゴリズム3と

𝑡=8

アルゴリズム4について。

• メモリ効率の改善 小フィールドSumcheckプロトコルはメモリ効率も向上させます。アルゴリズム4には𝑂(𝑑⋅𝑡)

アルゴリズム3はメモリを必要とします

𝑂(2𝑑⋅𝑡)

メモリ。For

𝑡=8

アルゴリズム4は、アルゴリズム3に比べて0.26 MBのメモリしか使用せず、クライアント側の証明など、リソースが制限されているメモリ制約環境に特に適しています（例えば、67 MBが必要です）。

3.4 PCS最適化：FRI-Binius Reducing Binius Proof SizeBiniusプロトコルの主な課題の1つは、証明のサイズが比較的大きいことであり、それは証人のサイズの平方根とスケールします。

O(N)

この平方根スケーリングは、より簡潔な証明を提供するシステムと比較すると、その競争力を制限しています。一方、FRIなどの高度なシステムによって実現されたポリログ証明サイズは、FRIのような技術を介して達成されたものであり、真に「簡潔な」検証者を確保するために不可欠です。FRI-Binius最適化は、Biniusの証明サイズを削減し、より効率的なシステムと比較してその全体的なパフォーマンスを向上させることを目指しています。

The paper バイナリタワー上の多線形に対する多対数証明は、FRI-Biniusと呼ばれ、4つの主要なイノベーションを備えた新しいバイナリフィールドベースのFRI(Fast Reed-Solomon Interactive Oracle Proof of Proof Proximity)フォールディングメカニズムを導入しています。

• フラット化された多項式：初期の多線形多項式を最適化された計算のための低コード高度（LCH）多項式基底に変換します。- Subspace Vanishing Polynomials: これらの多項式を加算型NTT（数論変換）と組み合わせて使用し、係数体上の操作を最適化するFFTのような分解を可能にします。- 代数的基礎パッキング：データの効率的なパッキングを可能にし、埋め込みに関連するプロトコルのオーバーヘッドを最小限に抑えます。- Ring-Switching SumCheck: リングスイッチング技術を使用した新しいSumCheck最適化は、パフォーマンスをさらに向上させるためのものです。FRI-Binius Multilinear Polynomial Commitment Scheme (PCS)のコアプロセス

FRI-Biniusプロトコルは、初期のバイナリフィールド上で定義された初期多変数多項式を変換することにより、バイナリフィールド多変数多項式コミットメントスキーム（PCS）を最適化します。

𝐹2

、大きなフィールド上の多線形多項式に変換します

𝐾

.

• コミットメントフェーズ コミットメントフェーズは、- ℓ- -variable multilinear polynomial (over $\mathbb{F}2- )𝑖𝑛𝑡𝑜𝑎𝑐𝑜𝑚𝑚𝑖𝑡𝑚𝑒𝑛𝑡𝑓𝑜𝑟𝑎𝑝𝑎𝑐𝑘𝑒𝑑- \ell’- −𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑚𝑢𝑙𝑡𝑖𝑙𝑖𝑛𝑒𝑎𝑟𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙(𝑜𝑣𝑒𝑟- \mathbb{F}{2^{128}}$ )。このプロセスにより、係数の数が128分の1に減少し、より効率的な証明生成が可能になります。- 評価フェーズでは、プルーバーと検証者が実行します。- ℓ′- FRIインタラクティブオラクル近接証明（IOPP）と組み合わされたクロスリングスイッチングSumCheckプロトコルのラウンド数。主な詳細は次のとおりです:FRIオープニングプルーフ：これらはプルーフの大部分を占め、大きなフィールド上の標準的なFRIプルーフと同様に処理されます。- ProverのSumCheckコスト：大きなフィールドでSumCheckを実行するコストと同等です。- ProverのFRIコスト：大規模なフィールド実装で見られる標準のFRIコストに一致します。- 検証者の操作：検証者は128の要素を受け取ります - 𝐹2128- さらに128回の乗算を実行し、効率的な検証が可能になります。FRI-Biniusの利点

この方法を適用することで、Biniusは証明のサイズを桁単位で削減し、最先端の暗号システムのパフォーマンスに近づけながら、バイナリフィールドとの互換性を保ちます。バイナリフィールドに最適化されたFRI折りたたみ法と、代数的パッキングとSumCheckの最適化を組み合わせることで、Biniusは検証効率を損なうことなく、より小さな証明を生成することができます。

この変換は、Biniusの証明サイズの改善に向けた重要な一歩であり、特にポリログリスムの証明サイズに焦点を当てた他の最先端システムとの競争力を高めることを保証しています。

表2：Binius vs. FRI-Biniusの証明サイズ比較 テーブル3：Plonky3 FRI vs. FRI-Biniusの比較## 4. 結論Biniusの完全な価値提案は、最小の2のべき乗のフィールドサイズを証人に使用し、必要に応じてフィールドサイズを選択する能力にあります。Biniusは、「ハードウェア、ソフトウェア、およびFPGAアクセラレートされたSumcheckプロトコル」のための共同設計スキームであり、非常に低いメモリ使用量で高速な証明を可能にします。

Halo2やPlonky3のようなプルーフシステムには、証人データを生成する、証人データにコミットする、消滅論証を行う、証明を開くための証明データを生成するという4つの主要な計算集約的なステップがあります。

例えば、Plonky3のKeccakハッシュ関数とBiniusのGrøstlハッシュ関数を使用すると、これら4つの主要なステップの計算分布は図3に示されています。

図3. より小さなコミットコスト

この比較から、Biniusは基本的に検証者のコミットメントのボトルネックを排除しました。新しいボトルネックはSumcheckプロトコルであり、多数の多項式評価や体の乗算などの問題を専用ハードウェアで効率的に対処できます。

FRI-Biniusスキームは、FRIの変種であり、埋め込みオーバーヘッドをフィールド証明レイヤーから取り除き、集約された証明レイヤーでのコスト増加をほとんど引き起こさずに、非常に魅力的なオプションを提供します。

現在、Irreducibleチームは再帰レイヤーを開発中で、GateはPolygonチームとのパートナーシップを発表し、BiniusベースのzkVMを構築することを発表しました; ザ Jolt zkVMは、再帰パフォーマンスを向上させるためにLassoからBiniusに移行しています；そしてIngonyama team は Binius の FPGA バージョンを実装しています.

参考文献- 2024.04 Binius Succinct Arguments over Towers of Binary Fields- 2024.07 Fri-Biniusバイナリタワー上のMultilinearsのためのPolylogarithmic証明- Biniusにおける2024.08の整数乗算：GKRベースのアプローチ- 2024.06 zkStudyClub - FRI-Binius: 2進タワー上の多項式対数証明- 2024.04 ZK11: Binius: a Hardware-Optimized SNARK - Jim Posen- 2023.12エピソード303：UlvetannaとのBiniusへのダイブ- 2024年09月、高性能zkVMの設計- 2024.07 SumcheckとOpen-Binius- 2024.04 Binius: 二進数フィールド上の高効率な証明- 2023.12 二進フィールドのSNARKs：Binius - パート1- 2024.06 バイナリ体上のSNARK: Binius - その2- @espressosys/hyperplonk-a-zk-proof-system-for-zkevms-d45fd077bfba">2022.10 HyperPlonk、ZKEVMのためのzk-proofシステム#### 免責事項：- この記事は[bitlayer]. すべての著作権は元の著者に帰属します [lynndell].この転載に異議がある場合は、[gate学習](https://www.Gate.com/questionnaire/3967チーム、そして彼らはそれを迅速に処理します。- 責任の免責事項：この記事で表現されている意見および見解は、著者個人のものであり、投資アドバイスを構成するものではありません。- 記事の翻訳は、gate Learn チームによって他の言語に行われます。特に言及されていない限り、翻訳された記事の複製、配布、盗用は禁止されています。