Binius STARKsの分析と最適化

1. はじめに

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

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

Biniusは、タワー型バイナリドメインに基づく算術化された改良版HyperPlonkの積と置換チェック、有限体多項式コミットメントなどの技術を使用して、さまざまな観点から効率を向上させています。

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

2. 原理分析

Biniusは5つの主要な技術で構成されています:

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

2.1 タワー型バイナリ領域に基づく算術化

タワー型二進法体は、高効率の算術演算と簡略化された算術化プロセスをサポートします。二進法体の要素は、kビットの文字列に直接マッピングでき、1対1のマッピングの便利さを持っています。

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

2.2 適合 HyperPlonk 製品と順列チェック

Biniusは、GateCheck、PermutationCheck、LookupCheckなど、HyperPlonkのコアチェックメカニズムを借用し、次の側面で改善を行っています。

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

2.3 新しい多重線形シフト証明

Biniusは、仮想多項式を構築および処理するための2つの重要なメソッド、Packingとシフト演算子を導入しました。

2.4 適応されたなげなわルックアップ引数

BiniusはLassoを二進数領域の操作に適応させ、Lassoプロトコルの乗法版を導入しました。

2.5 小域多項式コミットメント

Biniusは、主に小域多項式コミットメントと拡張域評価、小域一般構造、ブロックレベルエンコーディングとReed-Solomon符号技術を使用して、2つのバイナリドメインに基づくBrakedown多項式コミットメントスキームを提供しています。

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

3. 思考の最適化

3.1 GKR ベースの PIOP

GKRに基づくバイナリ領域乗算アルゴリズムは、「2つの32ビット整数AとBがA·B =? Cを満たすかどうかを確認する」という式を「中(gA)B =? gCが成り立つかどうかを確認する」に変換し、GKRプロトコルを利用してコミットメントのオーバーヘッドを大幅に削減します。

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

3.2 ZeroCheck PIOPの最適化

証明者と検証者の間で作業量の配分を調整することにより、いくつかの最適化案が提案されました:

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

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking

3.3 Sumcheck PIOPの最適化

Ingonyamaは、小領域に基づくSumcheckプロトコルの改善案を提案し、ラウンドtの選択に焦点を当てています。

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

3.4 PCSの最適化:FRI-Binius

FRI-Biniusは、二進数領域FRI折りたたみメカニズムを実現し、4つの側面での革新をもたらしました:

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

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

4. 概要

Biniusは「ハードウェア、ソフトウェア、FPGAを使用した加速されたSumcheckプロトコル」の協調設計ソリューションであり、非常に低いメモリ使用率で迅速に証明できます。BiniusではProverのコミットメントボトルネックが基本的に完全に排除されており、新しいボトルネックはSumcheckプロトコルにありますが、これを専用ハードウェアで効率的に解決できます。

FRI-BiniusプランはFRIの変種であり、ドメイン証明層から埋め込みコストを排除することができ、集約証明層のコストの急増を引き起こすことはありません。現在、複数のチームがBinius関連技術を開発しており、再帰層やzkVMなどが含まれています。

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking