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

1. はじめに

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

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

Biniusは以下のコア技術を採用しています:

• タワーバイナリフィールドに基づく算術化
• HyperPlonk製品と順列チェックの改善
• 新しい多線形シフト証明
• Lasso ルックアップ引数の改良版
• 小域多項式コミットメントスキーム

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

2. 原理分析

2.1 バイナリフィールドの塔に基づく算術化

タワー型バイナリドメインは、高度に効率的な算術操作をサポートし、高速で検証可能な計算を実現するための鍵です。その利点には以下が含まれます:

• 効率的な計算
• 効率的な演算
• 簡略化された算術処理をサポート
• タワー構造を通じてその階層的特性を最大限に活用できます

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

HyperPlonk Product と PermutationCheck の 2.2 適応

Binius は、次の領域で HyperPlonk を改善しました。

• ProductCheck最適化:値を1に特化し、チェックプロセスを簡素化する
• ゼロ除算の処理: 分母がゼロであっても処理を続けることができる
• Cross-column PermutationCheck: 複数の列間のPermutationCheckをサポート

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

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

Biniusは二つの重要な方法を導入しました:

• Packing:隣接要素をパッキングして操作を最適化する
• シフト演算子:与えられたオフセットに基づいてブロック内の要素を再配置する

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

2.4 の適応なげなわ検索引数

BiniusはLassoを二進数ドメイン操作に適応させ、Lassoプロトコルの乗算バージョンを導入しました。証明者は、プロトコルの安全性を確保するために、常にゼロでない読み取りカウントベクトルをコミットする必要があります。

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking

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

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

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

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

3. 思考の最適化

3.1 GKR ベースの PIOP

GKRに基づくバイナリフィールドの乗算演算は、1つの補助的なコミットメントだけで済み、Sumchecksのオーバーヘッドを削減することにより効率を向上させます。

3.2 ZeroCheck PIOPの最適化

証明者と検証者の間で作業量の配分を調整することで、さまざまな最適化案が提案された:

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

3.3 Sumcheck PIOPの最適化

Ingonyamaは、小域に基づくSumcheckプロトコルの改良案を提案しました:

• ラウンド切替の選択がパフォーマンスに影響する
• より小さな基盤がより顕著な利点を示しています
• カラツバアルゴリズムはパフォーマンスを向上させました
• メモリ効率が向上しました

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

3.4 PCSの最適化:FRI-Binius

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

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

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking

4. 概要

BiniusはProverのcommit承諾ボトルネックを取り除き、新しいボトルネックはSumcheckプロトコルにあります。FRI-BiniusスキームはFRIの変種であり、領域証明層の埋め込みオーバーヘッドを排除できます。現在、複数のチームがBinius関連のアプリケーションを開発しています。