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

1. はじめに

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

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

二進数体は、AES(F28)、GMAC(F2128)、QRコード(F28)など、暗号学に広く応用されています。小さな体を使用する場合、拡張体操作はセキュリティを確保するためにますます重要になります。Biniusが使用する二進数体は、安全性と可用性を保証するために完全に拡張体に依存する必要があります。ほとんどのProver計算は基体の下で操作され、効率的です；ランダムポイントのチェックとFRI計算は、セキュリティを確保するためにより大きな拡張体に深入りする必要があります。

Biniusの革新的なソリューション:

1. は、複数の変数 ( 多次元 ) 多項式を使用して単変数多項式の代わりに、"ハイパーキューブ" を用いて計算軌跡を示す。
2. 超立方体を正方形と見なし、正方形に基づいてリード・ソロモン拡張を行う

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

2. 原理分析

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

五つの重要な技術:

1. タワー型バイナリフィールドに基づく算術化 2)適合HyperPlonk製品と順列チェック
2. 新しいマルチリニアシフト証明
3. 改善された投げ縄検索引数
4. スモールドメイン多項式コミットメントスキーム

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

タワー型バイナリドメインの利点:

• 高効率な計算: バイナリフィールドは高効率な算術操作をサポートします
• 効率的な算術化: 二進法領域構造は算術化プロセスの簡素化をサポートします。
• タワー構造を通じて階層的特性を十分に活用する

128ビットの文字列は柔軟に解釈できます:

• 128ビットのバイナリフィールド内のユニークな要素
• 2つの64ビットタワードメイン要素
• 4つの32ビットタワー領域要素
• 16個8ビットタワードメイン要素
• 128個のF2ドメイン要素

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

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

Biniusコアチェックメカニズム:

1. ゲートチェック 2.順列チェック
   3.ルックアップチェック
2. マルチセットチェック
3. プロダクトチェック 6.ゼロチェック 7.サムチェック
4. バッチチェック

Binius の HyperPlonk の改良点:

• ProductCheckの最適化
• ゼロ除算の問題を正しく処理する
• Cross-column PermutationCheckがサポートされています

2.3 PIOP:新しいマルチリニアシフト引数

主な方法:

• パッキング: 隣接する小さな要素をより大きな要素にまとめる
• シフト演算子:ブロック内の要素を再配置する

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

2.4 PIOP: Lasso lookup 引数の適応版

Lassoプロトコルの利点:

• 証明効率が高い:m+n個の領域要素のコミットメント
• 大きなテーブルを約束する必要はありません: 超大きなテーブルを処理できます

Biniusが乗法版Lassoプロトコルを導入しました:

• バイナリドメイン乗算を通じて生成されるメモリカウントの増加
• 証明者は非ゼロの読み取りカウントベクトルを保証して安全性を確保することを約束します。

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

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

コアアイデア:パッキング

二つのプラン:

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

小域多項式コミットメントと拡張域評価:

• 小域Kにおいて約束する
• より大きな拡張ドメインL/Kで評価する

ブロック符号とリード・ソロモン符号:

• 小さな領域(のようにF2)多項式を使用して、大文字のアルファベット(のようにF216) Reed-Solomonコードによる効率的なコミットメントを許可します。

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking

3. 思考の最適化

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

3.1 GKRベースのPIOP: GKRに基づくバイナリフィールド乗算

"チェックA·B =? C"を"チェック(gA)B =? gC"に変換します

• ただ1つの補助的な約束が必要です
• Sumchecksのコストを削減する

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

最適化方法:

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

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

改善すべき主な領域:

• ラウンドtの選択を切り替える
• 基域サイズの影響
• カラツバアルゴリズムの最適化
• メモリ効率の向上

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

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

四つの革新:

1. フラットポリノミアル
2. サブスペース消失多項式
3. アルジェバ基パッケージ 4.リング交換サムチェック

FRI-BiniusはBinius証明のサイズを1桁減少させることができます

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

4. 概要

Biniusの利点:

• witnessが使用する最小のpower-of-two域を提供することができます
• メモリ使用量の少なさを迅速に証明
• Prover commitのボトルネックを基本的に除去する

新しいボトルネック:Sumcheckプロトコル

• 専用ハードウェアを利用して効率的に解決することができます

FRI-ビニウス:

• 域証明層の埋め込みオーバーヘッドを排除する
• 集合証明層のコストの急増を引き起こさない

現在の進捗状況:

• Irreducible チームは再帰的なレイヤーを開発し、Polygon と協力して Binius ベースの zkVM を構築しました。
• JoltzkVM が Lasso から Binius に移動
• IngonyamaがFPGA版Biniusを実装

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking