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

1 はじめに

従来のSTARKsシステムと比較して、Biniusはバイナリフィールドを直接操作することで、よりコンパクトで効率的なエンコーディングを実現しました。Biniusはタワー型バイナリフィールドの算術化、改良版HyperPlonkの積と置換チェック、小域多項式コミットメントなどの技術を使用して、多方面から効率を向上させています。本稿では、Biniusの核心原理を深く分析し、バイナリフィールドの乗法、ZeroCheck、SumCheck、PCSなどのさらなる最適化の可能性について探ります。

! 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など、HyperPlonkのコアチェックメカニズムを借用し、次の側面で改善を行っています。

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

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

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

Biniusは、効率的に仮想多項式を生成および操作するための2つの重要な方法、Packingとシフト演算子を導入しました。

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

BiniusはLassoプロトコルをバイナリドメイン操作に適応させ、乗法バージョンのLassoプロトコルを導入し、潜在的な攻撃を防ぐための措置を講じました。

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

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

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

3 思考の最適化

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

GKRプロトコルを利用してLasso Lookupアルゴリズムを置き換えることで、Biniusのコミットメントコストを大幅に削減できます。

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking

3.2 ZeroCheck PIOPの最適化

証明者と検証者の間で作業量の配分を調整することにより、ZeroCheck操作の効率を最適化できます。

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

3.3 Sumcheck PIOPの最適化

小領域Sumcheckの改良案は、小領域での計算負担をさらに軽減することができます。

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

3.4 PCSの最適化:FRI-Binius

FRI-Biniusは、バイナリドメインFRI折りたたみメカニズムを実現し、Binius証明のサイズを1桁小さくすることができます。

4 まとめ

Biniusは最小のpower-of-twoフィールドを使用することで、witnessesの効率的な処理を実現しました。その価値提案は、ニーズに応じてフィールドサイズを柔軟に選択でき、ハードウェア、ソフトウェア、およびFPGAの協調設計により、高速かつ低メモリの証明生成を実現することにあります。現在、Biniusは基本的にProverのcommitのボトルネックを取り除き、新しいボトルネックはSumcheckプロトコルに集中しています。今後、専用ハードウェアの助けを借りて、Sumcheckの効率をさらに向上させることが期待されます。

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking