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

1 はじめに

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

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

二進数領域は暗号学に広く応用されており、典型的な例としては:

• 高度暗号化標準(AES)、F28フィールドに基づく
• Galoisメッセージ認証コード(GMAC)、F2128フィールドに基づいて
• QRコード、F28ベースのリード・ソロモン符号を使用
• 原始FRIとzk-STARKプロトコル、およびSHA-3ファイナルに進出したGrøstlハッシュ関数

小さなフィールドを使用する場合、拡張フィールド操作はセキュリティを確保するためにますます重要になります。Biniusが使用する二項フィールドは、そのセキュリティと実用性を保証するために完全に拡張フィールドに依存しています。

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

• 単変数多項式の代わりに多変数（具体的には多項式）を使用し、その値を「ハイパーキューブ」で表現して全体の計算軌跡を示します。
• ハイパーキューブを正方形と考え、その正方形に基づいてリード・ソロモン拡張を作成します

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

2 原理分析

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

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

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

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

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

• 高効率計算: バイナリフィールドは本質的に非常に効率的な算術演算をサポートしています
• 高効率な算術化: 二進法フィールド構造は簡略化された算術プロセスをサポートします
• 柔軟な表現: 同じ文字列はバイナリ領域の文脈で多様な方法で解釈できる
• 繰り上げ不要: 2進数の域では、加算と乗算の演算において繰り上げを導入する必要がない
• 効率的な二乗:(X + Y)2 = X2 + Y2

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

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

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

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

HyperPlonkの改善点:

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

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

主な方法:

• Packing:隣接する位置の小さい要素をより大きな要素にパッキングすることによって操作を最適化する
• シフト演算子:指定されたオフセットに基づいて、ブロック内の要素を再配置し、循環シフトを行います

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

2.4 PIOP: Lasso lookup 引数の適応版

Lassoプロトコルの利点:

• 高効率な証明: サイズnのテーブルに対してm回の検索を行うには、m+n個のフィールド要素を約束するだけで済みます
• 大きなテーブルにコミットする必要はありません: テーブルtが構造化されている場合、コミットする必要はなく、超大きなテーブルを処理できます。

Lassoプロトコルの構成:

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

BiniusによるLassoのアレンジ:

• Lassoプロトコルの乗法バージョンを導入
• 要求証明者が常にゼロでない読み取りカウントベクトルを約束すること

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

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

二つの提案:

1. 連結コードを使用する 2.ブロックレベルのエンコーディング技術を採用し、リードソロモンコードのみの使用をサポートします

主な技術:

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

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

3 思考の最適化

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

1. GKRベースのPIOP:バイナリドメインの乗算演算
2. ZeroCheck PIOP 最適化: Prover と Verifier 間の計算コストのトレードオフ
3. Sumcheck PIOPの最適化:小さなドメインに基づくSumcheckプロトコル
4. PCSの最適化:FRI-BiniusはBiniusプルーフサイズを下げます

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

コアアイデア:

"2つの32ビット整数AとBが A·B =? C を満たすかどうかを確認する" 変換する "チェック中(gA)B =? gC が成立しているか"

利：

• ただの補助的な約束が必要です
• Sumchecksのオーバーヘッドを削減する

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking

3.2 ZeroCheck PIOPの最適化

最適化の方向:

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

3.3 Sumcheck PIOPの最適化

改善のポイント:

• ラウンドの切り替え選択
• 基域のサイズがパフォーマンスに与える影響
• Karatsubaアルゴリズムの最適化の利得
• メモリ効率の向上

具体的な結果:

• 基域がGF[2]の場合、アルゴリズム4の性能は素朴なアルゴリズムよりも約30倍高いです。
• アルゴリズム4はわずか0.26MBのメモリを必要とし、アルゴリズム3は67MBを必要とします。

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

3.4 PCSの最適化:FRI-Binius

4つのイノベーション:

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

影響： Biniusの証明のサイズを1桁減らす

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

4 まとめ

Biniusの利点:

• witnessに最小のpower-of-two域を使用することができます
• メモリ使用量が少なく、高速プルーフ
• Proverのcommit承諾ボトルネックをほぼ完全に排除しました

FRI-Biniusソリューション: 埋め込みオーバーヘッドを削除して、集合証明層のコストの急増を引き起こさない。

最新の動向:

• Irreducibleチームはその再帰層を開発しており、Polygonチームと協力してBiniusベースのzkVMを構築しています。
• JoltzkVMは、再帰的なパフォーマンスを向上させるため、LassoからBiniusに移行しています。
• IngonyamaチームはBiniusのFPGAバージョンを実現しています

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking