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

1 引言

相比常規STARKs系統，Binius採用二進制域直接對位操作，實現了更緊湊高效的編碼。Binius使用塔式二進制域算術化、改進版HyperPlonk乘積與置換檢查、小域多項式承諾等技術，從多方面提升了效率。本文將深入分析Binius的核心原理,並探討其在二進制域乘法、ZeroCheck、SumCheck、PCS等方面的進一步優化空間。

2 原理解析

Binius由五項關鍵技術構成:

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

2.1 有限域:基於塔式二進制域的算術化

塔式二進制域支持高效的算術操作和簡化的算術化過程,特別適合構建可擴展的證明系統。二進制域元素可靈活表示爲不同維度的塔域元素,無需額外計算開銷即可打包爲更大的域元素。

2.2 PIOP:改編版HyperPlonk乘積和置換檢查

Binius借鑑了HyperPlonk的核心檢查機制,包括GateCheck、PermutationCheck、LookupCheck等,並在以下方面做出改進:

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

2.3 PIOP:新的多線性移位論證

Binius引入了兩種關鍵方法:Packing和移位運算符,用於高效生成和操作虛擬多項式。

2.4 PIOP:改編版Lasso查找論證

Binius將Lasso協議適應於二進制域操作,引入乘法版本的Lasso協議,並採取措施防止潛在攻擊。

2.5 PCS:改編版Brakedown PCS

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

3 優化思考

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

利用GKR協議替代Lasso Lookup算法,可大幅降低Binius的承諾開銷。

3.2 ZeroCheck PIOP優化

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

3.3 Sumcheck PIOP優化

針對小域Sumcheck的改進方案,可進一步減少小域上的計算負擔。

3.4 PCS優化:FRI-Binius

FRI-Binius實現了二進制域FRI折疊機制,可將Binius證明大小減少一個數量級。

4 小結

Binius通過使用最小power-of-two域,實現了對witnesses的高效處理。其價值主張在於可根據需求靈活選擇域大小,並通過硬件、軟件與FPGA協同設計,實現快速低內存的證明生成。目前,Binius已基本移除了Prover的commit承諾瓶頸,新的瓶頸集中在Sumcheck協議。未來,借助專用硬件可望進一步提升Sumcheck效率。