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

1. はじめに

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

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

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

Biniusは革新的な解決策を提案しました: まず、単変数多項式の代わりに多変数（具体的には多線形）多項式を使用し、それを「超立方体」での値に基づいて計算の全軌跡を表現します。次に、超立方体を正方形として扱い、その正方形に基づいてReed-Solomon拡張を行います。この方法は安全性を確保しつつ、エンコーディング効率と計算性能を大幅に向上させました。

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

2. 原理分析

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

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

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

タワー型バイナリフィールドは、高度に効率的な算術演算をサポートし、簡素化された算術プロセスをサポートします。バイナリフィールドの要素は、唯一かつ直接的な表現方法を持ち、異なるサイズのフィールド間で柔軟に変換およびパッキングできます。

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

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

Biniusは、GateCheck、PermutationCheck、LookupCheck、MultisetCheck、ProductCheck、ZeroCheck、SumCheck、BatchCheckなど、一連のコア検査メカニズムを採用しています。

HyperPlonkと比較して、Biniusは次の改善を行いました。

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

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

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

Biniusは、仮想多項式を処理するためにPackingとシフト演算子の2つの重要な方法を採用しています。

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

2.4 PIOP: Lasso lookup 引数の適応版

Lassoプロトコルは3つのコンポーネントで構成されています:

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

Biniusは、乗法バージョンのLassoプロトコルを導入し、証明者と検証者が共同で増加プロトコルの「メモリカウント」操作を行うことを要求します。これは単に1を加えるのではなく、バイナリフィールドの乗法生成元を使用して増加します。

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking

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

Binius多項式承諾は主に使用されています:

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

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

3. 思考の最適化

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

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

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

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

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

• ラウンド切替の影響と改善要因
• 基域サイズがパフォーマンスに与える影響
• カラツバ法の最適化による利益
• メモリ効率の向上

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

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

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

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

4. 概要

Biniusは基本的にProverのcommit承諾ボトルネックを完全に排除し、新しいボトルネックはSumcheckプロトコルにあります。FRI-BiniusスキームはFRIの変種であり、ドメイン証明層から埋め込みオーバーヘッドを排除できます。現在、Irreducibleチームはその再帰層を開発しており、Polygonチームと協力してBiniusベースのzkVMを構築しています; JoltzkVMはLassoからBiniusに移行しています; IngonyamaチームはBiniusのFPGAバージョンを実装しています。

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking