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

1. はじめに

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

第1世代STARKsのエンコーディングビット幅は252ビット、第2世代は64ビット、第3世代は32ビットですが、32ビットのエンコーディングビット幅には依然として大量の無駄なスペースが存在します。それに対して、バイナリーフィールドはビットを直接操作できるため、エンコーディングがコンパクトで効率的であり、無駄なスペースはありません。つまり、第4世代STARKsです。

Biniusが使用する二進数領域は、その安全性と実際の使用可能性を保証するために、完全に拡張領域に依存する必要があります。ほとんどのProver計算に関与する多項式は、拡張領域に入る必要はなく、基本領域で操作するだけで、小領域内で高効率を実現しています。しかし、ランダムポイントチェックとFRI計算は、必要な安全性を確保するために、より大きな拡張領域に深く入る必要があります。

Biniusは革新的な解決策を提案しました。まず、単変数多項式の代わりに多変数（具体的には多線形）多項式を使用し、その値を「超立方体」（hypercubes）上で取ることで、全体の計算軌跡を表現します。次に、超立方体の各次元の長さが2であるため、STARKsのように標準的なReed-Solomon拡張を行うことはできませんが、超立方体を正方形（square）と見なし、その正方形に基づいてReed-Solomon拡張を行うことができます。

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

2. 原理分析

Biniusには5つの重要な技術が含まれています:

1. タワー型バイナリフィールドに基づく算術化
2. 適応HyperPlonk製品と順列チェック
3. 新しい多次元シフト証明 4.なげなわルックアップ引数の改善
4. 小域多項式コミットメントスキーム

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

タワー型バイナリ領域の利点:

• 高効率な計算: バイナリフィールドは本質的に非常に効率的な算術演算をサポートします
• 高効率な算術化: バイナリフィールド構造は簡易な算術化プロセスをサポートします。
• 規範表現: バイナリ領域の要素には唯一かつ直接的な表現方法がある

バイナリドメインの利点:

• 加算と乗算は繰り上がりを導入する必要がない
• 平方運算は非常に効率的で、(X + Y)^2 = X^2 + Y^2 の簡略化ルールに従います。
• 表示の柔軟性: 128ビットの文字列は128ビットのバイナリフィールド内のユニークな要素として見なされるか、または複数のタワーフィールド要素の組み合わせとして解析されることができます。

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

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

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

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

Binius の HyperPlonk の改良点:

• ProductCheckの最適化
• ゼロ除算の処理
• Cross-column PermutationCheckのサポート

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

主な方法:

• パッキング: 隣接する要素をパッキングして操作を最適化
• シフト演算子:ブロック内の要素を再配置する

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

2.4 PIOP: Lasso lookup 引数の適応版

Lassoプロトコルの構成:

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

ビニウスのラッソの適応:

• マルチプライヤーバージョンのLassoプロトコルを導入する
• 要求証明者は常に非ゼロの読み取りカウントベクトルを約束すること

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

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

2つのバイナリーフィールドに基づくBrakedown多項式コミットメントスキーム:

1. concatenated codeを用いてインスタンス化する 2.ブロックレベルのエンコーディング技術を採用し、リードソロモンコードのみの使用をサポートします

主な技術:

• 小域多項式コミットメントと拡張域評価
• スモールドメインジェネリック構造
• ブロック符号とリード・ソロモン符号

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

3. 思考の最適化

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

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

Biniusルックアップに対する利点:

• たった1つのサポートコミットメント
• Sumchecksのコストを削減する

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

最適化方法:

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

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

重要なポイント:

• 切り替えラウンドの影響と改善ファクター
• 基域サイズが性能に与える影響
• カラツバのアルゴリズムの最適化の利得
• メモリ効率の向上

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking

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

FRI-Biniusには4つのイノベーションがあります。

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

FRI-Binius PCSプロセス:

• コミットメント段階
• 評価フェーズ

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

4. 概要

Biniusのバリュープロポジション:

• 最小の 2 のべき乗ドメインをウィットネスに使用できます
• コラボレーティブな設計ソリューションにより、メモリ使用量の少なさを迅速に証明
• Proverのcommitコミットメントボトルネックを基本的に除去する
• 新しいボトルネックはSumcheckプロトコルにあり、専用ハードウェアを利用して効率的に解決できます。

FRI-Biniusソリューション:

• 埋め込みオーバーヘッドを領域証明層から排除する
• 集約証明層のコストが急増することはない

現在の進捗状況:

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

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

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking