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

1. はじめに

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

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

近年研究が進められているGoldilocks、BabyBear、Mersenne31などの有限領域と比較すると、バイナリ領域の研究は前世紀の80年代にまでさかのぼることができ、AES(F28領域)などの暗号技術で広く利用されています。 GMAC(F2128ドメイン)、QRコード、(F28ドメインリード・ソロモン符号化)など

Biniusはバイナリ領域を使用し、安全性と可用性を確保するために完全に拡張領域に依存する必要があります。ほとんどのProver計算は基底領域で効率的に操作され、ランダムポイントチェックとFRI計算は安全性を確保するために拡張領域に深く依存する必要があります。

Biniusは"超立方体"上での計算軌跡を多変数多項式を用いて表現し、超立方体を正方形としてReed-Solomon拡張を行い、安全性を確保しながらエンコーディング効率と計算性能を大幅に向上させます。

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

2. 原理分析

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

五つの重要な技術を含む:

1. 塔型バイナリフィールドに基づく算術的構成計算基盤

2. HyperPlonkの積と置換のチェックを改編し、変数と置換の一貫性チェックを確保する

3. 新しい多線形シフト証明、最適化された小領域における多線形関係の検証効率

4. 改良版Lasso探索証明は、探索メカニズムに柔軟性と安全性を提供します

5. 小域多項式コミットメントスキーム、バイナリーフィールド上での効率的な証明システムを実現する

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

タワー型バイナリーフィールドは、高効率の算術演算と算術化プロセスの簡素化をサポートし、特にBiniusのような拡張可能な証明システムに適しています。

128ビットの文字列は、128ビットのバイナリフィールド内のユニークな要素として見ることができるか、2つの64ビットタワーフィールド要素、4つの32ビットタワーフィールド要素、16の8ビットタワーフィールド要素、または128のF2フィールド要素として解析できます。この柔軟性は計算コストを必要とせず、単にビット文字列の型変換です。

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

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

Binius PIOP は HyperPlonk から借用し、コア チェック メカニズムを使用して、GateCheck、PermutationCheck、LookupCheck、MultisetCheck、ProductCheck、ZeroCheck、SumCheck、BatchCheck などの多項式セットと多変量セットの正確性を検証します。

Biniusは以下の3つの点で改善を行いました:

• ProductCheck最適化: 値を1に特化し、チェックプロセスを簡素化して計算複雑度を低下させる

• ゼロ除算の処理: 分母がゼロの場合を正しく処理し、任意の積の値への拡張を許可します

• Cross-column PermutationCheck: 複数の列間のPermutationCheckは、より複雑な多項式配置を処理するためにサポートされています

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

Biniusでの仮想多項式の構築と処理は、主要な技術です。

• パッキング: 辞書の順序で隣接する小さな要素をより大きな要素にパッキングして操作を最適化する

• シフト演算子:指定されたオフセットに基づいてブロック内の要素を再配置し、循環シフトします。

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

2.4 PIOP: Lasso lookup 引数の適応版

Lassoプロトコルは、証明者がベクトルa ∈ Fmをコミットし、すべての要素が事前に指定された表t ∈ Fnに存在することを証明することを許可します。

BiniusはLassoを二進法領域操作に適応させ、乗算バージョンのLassoプロトコルを導入し、証明者と検証者が共同で増加プロトコル「メモリカウント」操作を要求し、二進法領域の乗算を通じて元の増加を生成します。

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

BiniusPCSの核心思想はpackingです。2つの2進数領域に基づくBrakedown多項式コミットメントスキームを提供します:

1. concatenated codeを使用してインスタンス化する

2. block-levelエンコーディング技術を採用し、Reed-Solomonコードの単独使用をサポートします。

第二の方案は証明と検証のプロセスを簡略化し、証明のサイズはやや大きいですが、簡素化と実装の利点は価値があります。

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

3. 思考の最適化

3.1 GKRベースのPIOP: GKRに基づくバイナリ領域乗算

"チェック2つの32ビット整数AとBがA·B =? Cを満たすかどうか"を"チェック(gA)B =? gCが成立するかどうか"に変換し、GKRプロトコルを利用してコミットメントコストを大幅に削減します。

GKRに基づく乗算は、1つの補助コミットメントだけで済み、Sumchecksのオーバーヘッドを削減することでアルゴリズムをより効率的にします。特に、Sumchecks操作がコミットメント生成よりも安価なシナリオでのことです。

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

証明者のデータ転送を削減: 一部の作業を検証者に移し、証明者が送信するデータ量を減らす。

証明者の評価点の数を減らす: 多項式の送信方法を変更し、評価点の数を減らします。

代数的補間最適化: 多項式長除法は、補間最適化を達成するための順序分解を構築するために使用されます。

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking

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

切り替えラウンドの影響と改善因子:切り替えラウンドtの選択は性能に影響を与え、最適な切り替えポイントの改善因子は最大値に達します。

基域のサイズが性能に与える影響: より小さな基域(のようにGF[2])最適化アルゴリズムの利点がより顕著です。

Karatsubaアルゴリズムの最適化収益: 小域Sumcheck性能の大幅な向上、アルゴリズム4はアルゴリズム3よりも5倍効率的です。

メモリ効率の向上:アルゴリズム4のメモリ要件はO(d·t)で、アルゴリズム3はO(2d·t)で、リソースが限られた環境に適しています。

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

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

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

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

FRI-Biniusを利用することで、Biniusの証明サイズを1桁小さくし、最先端のシステムに近づけることができます。

! 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