Binius STARKs原理解析及其優化思考

1. 引言

STARKs的演進路徑中,編碼效率逐步提高但仍存在浪費。Binius通過直接對位操作,實現了更緊湊高效的編碼,有望成爲第4代STARK。Binius採用塔式二進制域算術化、改進的HyperPlonk乘積與置換檢查、小域多項式承諾等技術,從多方面提升效率。在二進制域乘法、ZeroCheck、SumCheck、PCS等方面還可進一步優化,以提高證明速度和減小證明大小。

2. 原理解析

Binius結合了HyperPlonk PIOP、Brakedown PCS和二進制域,包含五項關鍵技術:

1. 基於塔式二進制域的算術化
2. 改編版HyperPlonk乘積和置換檢查
3. 新的多線性移位論證
4. 改進版Lasso查找論證
5. 小域多項式承諾方案

2.1 有限域:基於towers of binary fields的算術化

塔式二進制域支持高效計算和簡化的算術化。二進制域元素可靈活表示,無需額外計算開銷即可在不同大小的域之間轉換。

2.2 PIOP:改編版HyperPlonk Product和PermutationCheck

Binius採用改進的HyperPlonk核心檢查機制,包括GateCheck、PermutationCheck、LookupCheck等。主要改進包括:

• ProductCheck優化
• 除零問題處理
• 跨列PermutationCheck支持

2.3 PIOP:新的multilinear shift argument

Binius引入Packing和移位運算符兩種關鍵方法,高效構造和處理虛擬多項式。

2.4 PIOP:改編版Lasso lookup argument

Binius將Lasso適應二進制域操作,引入乘法版本Lasso協議,並處理了潛在的安全問題。

2.5 PCS:改編版Brakedown PCS

Binius提供兩種基於二進制域的Brakedown多項式承諾方案,採用小域多項式承諾與擴展域評估、小域通用構造和塊級編碼技術。

3. 優化思考

3.1 GKR-based PIOP:基於GKR的二進制域乘法

借助GKR協議替換Lasso Lookup算法,可大幅降低承諾開銷。

3.2 ZeroCheck PIOP優化

通過在證明方和驗證方之間調整工作量分配,優化ZeroCheck操作效率。

3.3 Sumcheck PIOP優化

針對小域Sumcheck的優化,進一步減少小域上的計算負擔。

3.4 PCS優化:FRI-Binius

FRI-Binius實現二進制域FRI折疊機制,可顯著降低Binius證明大小。

4. 小結

Binius移除了Prover的commit承諾瓶頸,新瓶頸在於Sumcheck協議。FRI-Binius爲FRI變體,可消除域證明層嵌入開銷。Binius正在開發遞歸層,並與多個團隊合作構建zkVM和FPGA實現。