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

1. はじめに

STARKsの進化の過程では、コーディング効率が徐々に向上していますが、依然として無駄があります。Biniusは、直接ビット操作を通じて、よりコンパクトで効率的なコーディングを実現し、第4世代STARKになることが期待されています。Biniusは、タワー型バイナリフィールドの算術化、改良されたHyperPlonkの積と置換チェック、小域多項式コミットメントなどの技術を採用し、効率を多方面から向上させています。バイナリフィールドの乗算、ZeroCheck、SumCheck、PCSなどの面でもさらなる最適化が可能であり、証明速度を向上させ、証明サイズを削減します。

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

2. 原理分析

Biniusは、HyperPlonk PIOP、Brakedown PCS、およびバイナリドメインを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とシフト演算子を導入しました。

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

2.4 PIOP: Lasso lookup 引数の適応版

BiniusはLassoをバイナリドメイン操作に適応させ、乗法バージョンのLassoプロトコルを導入し、潜在的なセキュリティ問題に対処しました。

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking

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

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

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

3. 思考の最適化

3.1 GKRベースのPIOP: GKRに基づく二進法ドメイン乗算

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

3.2 ZeroCheck PIOPの最適化

証明者と検証者の間で作業負荷の配分を調整することによって、ZeroCheckの操作効率を最適化します。

3.3 Sumcheck PIOPの最適化

小さいフィールドSumcheckの最適化に関して、さらに小さいフィールドでの計算負担を軽減します。

3.4 PCSの最適化:FRI-Binius

FRI-Biniusはバイナリ領域のFRI折りたたみメカニズムを実現し、Biniusの証明サイズを大幅に削減できます。

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

4. 概要

BiniusはProverのcommitのボトルネックを排除し、新しいボトルネックはSumcheckプロトコルにあります。FRI-BiniusはFRIの変種で、フィールド証明層の埋め込みオーバーヘッドを排除できます。Biniusは再帰層を開発しており、複数のチームと協力してzkVMおよびFPGA実装を構築しています。

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking