Binius STARKsの原理とその最適化思考の解析

1 はじめに

STARKsの効率が低下する主な理由の一つは、実際のプログラムでの数値の多くが小さいことですが、Merkleツリー証明の安全性を確保するために、Reed-Solomon符号化を使用してデータを拡張する際に、多くの追加の冗長値が全体の領域を占めます。領域のサイズを減少させることが重要な戦略となりました。

第1世代STARKsのエンコーディングビット幅は252ビット、第2世代は64ビット、第3世代は32ビットですが、32ビットのエンコーディングビット幅には依然として大量の無駄なスペースがあります。バイナリ領域はビットに直接操作を行うことを許可し、エンコーディングはコンパクトで効率的であり、無駄なスペースがありません。これが第4世代STARKsになる可能性があります。

バイナリドメインは、AES、GMAC、QRコード、原始FRI、zk-STARKプロトコルなど、暗号学に広く適用されています。

Biniusは二進数領域を使用する際、セキュリティと実際の可用性を保証するために拡張領域に完全に依存する必要があります。ほとんどのProver計算に関与する多項式は拡張領域に入る必要がなく、基底領域で操作するだけで、小さな領域内で高効率を実現します。

Biniusは革新的なソリューションを提案しました:

1. は、多変数多項式を単変数多項式の代わりに使用し、その値を "超立方体" 上で表現することによって、全体の計算軌跡を示します。
2. 超立方体を正方形として扱うことによるリード・ソロモン拡張

! Bitlayer研究:Binius STARKsの原理分析と最適化思考

2 原理分析

Binius = HyperPlonk PIOP + ブレーキダウン PCS + バイナリ ドメイン

五つの主要技術を含む:

1. 塔型バイナリ領域に基づく算術化
2. ハイパープロンクの積と置換のチェックを改編
3. 新しい多線形シフト証明
4. 改善された投げ縄検索引数
5. 小域多項式コミットメントスキーム

2.1 有限体:二値体の塔に基づく算術

タワー型バイナリドメインは、高度に効率的な算術操作と簡略化された算術プロセスをサポートします。

128ビットの文字列は、128ビットのバイナリフィールド内の要素として見なすことができるか、2つの64ビットのタワーフィールド要素、4つの32ビットのタワーフィールド要素、16の8ビットのタワーフィールド要素、または128のF2フィールド要素として解析することができます。この表現の柔軟性は、追加の計算コストを必要としません。

! Bitlayer研究:Binius STARKsの原理分析と最適化思考

2.2 PIOP:適応されたHyperPlonk製品と順列チェック

BiniusプロトコルのPIOP設計はHyperPlonkを参考にしており、一連のコアチェックメカニズムを採用しています。

• ゲートチェック
• 順列チェック
• ルックアップチェック
• マルチセットチェック
• プロダクトチェック
• ゼロチェック
• サムチェック
• バッチチェック

Biniusは以下の3つの点で改善を行いました:

• ProductCheckの最適化
• ゼロ除算の処理
• クロスカラム順列チェック

2.3 PIOP：新しいマルチラインシフト引数

Biniusプロトコルにおける仮想多項式の構築と処理の重要な方法:

• パッキング
• シフト演算子

2.4 PIOP: Lasso lookup 引数の適応版

Lassoプロトコルは三つのコンポーネントで構成されています:

• 大きなテーブルの仮想多項式抽象化
• 小さなテーブル検索
• 多集合チェック

Biniusプロトコルは、バイナリ領域でのLassoの操作を適応させ、Lassoプロトコルの乗法バージョンを導入しました。

2.5 PCS:ブレーキダウンPCSの適応版

Binius論文は、2つのバイナリ領域に基づくBrakedown多項式コミットメントスキームを提供しています:

1. は連結コードを使用してインスタンス化されます
2. はブロックレベルエンコーディング技術を採用し、リード・ソロモン符号を単独で使用することをサポートしています。

小域多項式コミットメントと拡張域評価、小域一般構成、ブロックレベルエンコーディングとReed-Solomon符号などの技術がBinius多項式コミットメントの構築に使用されます。

! Bitlayer研究:Binius STARKsの原理分析と最適化思考

3 思考の最適化

四つの重要な最適化ポイント:

1. GKRベースのPIOP：バイナリドメインの乗算演算に対して、GKRプロトコルを利用してLasso Lookupアルゴリズムを置き換えます。

2. ZeroCheck PIOP 最適化: Prover と Verifier 間の計算コストのトレードオフ

3. Sumcheck PIOP Optimization:スモールドメインのSumcheckの最適化

4. PCSの最適化:FRI-Biniusの最適化によりプルーフサイズを縮小します

3.1 GKRベースのPIOP：GKRに基づくバイナリドメイン乗算

GKRに基づく整数乗算アルゴリズムでは、"2つの32ビット整数AとBがA·B =? Cを満たすかどうかを確認"することを、"中(gA)B =? gCが成立するかどうかを確認"に変換し、GKRプロトコルを利用してコミットメントコストを大幅に削減します。

! Bitlayer研究:Binius STARKsの原理分析と最適化思考

3.2 ZeroCheck PIOP 最適化: Prover と Verifier 間の計算コストのトレードオフ

主な最適化方向:

• 証明者のデータ伝送を減らす
• 評価ポイントを減らす
• 代数的補間最適化

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking

3.3 Sumcheck PIOP 最適化: 小さなドメインに基づく Sumcheck プロトコル

主要最適化ポイント:

• 切り替えラウンドの影響と改善要因
• 基域のサイズが性能に与える影響
• カラツバ法の最適化利益
• メモリ効率の向上

! Bitlayer研究:Binius STARKsの原理分析と最適化思考

3.4 PCSの最適化:FRI-BiniusはBiniusプルーフサイズを縮小します

FRI-Biniusは、バイナリーフィールドFRI折りたたみメカニズムを実現し、4つの側面での革新をもたらしました:

• フラット多項式
• サブスペース消失多項式
• アルジェブラ基のパッケージ
• リングスワップサムチェック

! Bitlayer研究:Binius STARKsの原理分析と最適化思考

4 まとめ

Biniusの価値提案は、witnessesが最小のpower-of-twoフィールドを使用できることです。Biniusでは、Proverのcommitコミットメントボトルネックが基本的に完全に排除されており、新しいボトルネックはSumcheckプロトコルにあります。

FRI-Binius方式はFRIの変種であり、ドメイン証明層から埋め込みコストを排除でき、集約証明層のコストの急増を引き起こすことはありません。

現在、Irreducibleチームはその再帰層を開発しており、Polygonチームと協力してBiniusベースのzkVMを構築しています；JoltzkVMはLassoからBiniusに移行しています；IngonyamaチームはBiniusのFPGAバージョンを実装しています。

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking