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

1 引言

STARKs效率低下的一個主要原因是實際程序中的大多數數值較小，但爲了確保基於Merkle樹證明的安全性，使用Reed-Solomon編碼對數據進行擴展時，許多額外的冗餘值會佔據整個域。降低域的大小成爲了關鍵策略。

第1代STARKs編碼位寬爲252bit，第2代爲64bit，第3代爲32bit，但32bit編碼位寬仍存在大量浪費空間。二進制域允許直接對位進行操作，編碼緊湊高效而無任意浪費空間，可能成爲第4代STARKs。

二進制域已廣泛應用於密碼學中，如AES、GMAC、QR碼、原始FRI和zk-STARK協議等。

Binius採用二進制域時，需完全依賴擴域來保證安全性和實際可用性。大多數Prover計算中涉及的多項式無需進入擴域，而只需在基域下操作，從而在小域中實現了高效率。

Binius提出創新解決方案:

1. 使用多變量多項式代替單變量多項式，通過其在"超立方體"上的取值表示整個計算軌跡
2. 將超立方體視爲方形進行Reed-Solomon擴展

2 原理解析

Binius = HyperPlonk PIOP + Brakedown PCS + 二進制域

包括五項關鍵技術:

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

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

塔式二進制域支持高度高效的算術操作和簡化的算術化過程。

128位字符串可被視爲128位二進制域中的一個元素，或被解析爲兩個64位塔域元素、四個32位塔域元素、16個8位塔域元素，或128個F2域元素。這種表示靈活性無需額外計算開銷。

2.2 PIOP：改編版HyperPlonk Product和PermutationCheck

Binius協議中的PIOP設計借鑑了HyperPlonk，採用一系列核心檢查機制:

• GateCheck
• PermutationCheck
• LookupCheck
• MultisetCheck
• ProductCheck
• ZeroCheck
• SumCheck
• BatchCheck

Binius在以下3個方面做出改進:

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

2.3 PIOP：新的multilinear shift argument

Binius協議中虛擬多項式的構造和處理的關鍵方法:

• Packing
• 移位運算符

2.4 PIOP：改編版Lasso lookup argument

Lasso協議由三個組件構成:

• 大表的虛擬多項式抽象
• 小表查找
• 多集合檢查

Binius協議將Lasso適應於二進制域的操作，引入了乘法版本的Lasso協議。

2.5 PCS：改編版Brakedown PCS

Binius論文提供了2種基於二進制域的Brakedown多項式承諾方案:

1. 採用concatenated code來實例化
2. 採用block-level encoding技術,支持單獨使用Reed-Solomon codes

小域多項式承諾與擴展域評估、小域通用構造和塊級編碼與Reed-Solomon碼等技術被用於構建Binius多項式承諾。

3 優化思考

四個關鍵優化點:

1. GKR-based PIOP：針對二進制域乘法運算,借助GKR協議替換Lasso Lookup算法

2. ZeroCheck PIOP優化：在Prover與Verifier之間進行計算開銷權衡

3. Sumcheck PIOP優化：針對小域Sumcheck的優化

4. PCS優化：通過FRI-Binius優化降低證明大小

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

基於GKR的整數乘法運算算法,通過將"檢查2個32-bit整數A和B是否滿足 A·B =? C"，轉換爲"檢查中(gA)B =? gC 是否成立"，借助GKR協議大幅減少承諾開銷。

3.2 ZeroCheck PIOP優化：Prover與Verifier計算開銷權衡

主要優化方向:

• 減少證明方的數據傳輸
• 減少證明方評估點的數量
• 代數插值優化

3.3 Sumcheck PIOP優化：基於小域的Sumcheck協議

主要優化點:

• 切換輪次的影響與改進因子
• 基域大小對性能的影響
• Karatsuba算法的優化收益
• 內存效率的提升

3.4 PCS優化：FRI-Binius降低Binius proof size

FRI-Binius實現了二進制域FRI折疊機制,帶來4個方面的創新:

• 扁平化多項式
• 子空間消失多項式
• 代數基打包
• 環交換SumCheck

4 小結

Binius的價值主張是可爲witnesses使用最小的power-of-two域。Binius中已基本完全移除了Prover的commit承諾瓶頸,新的瓶頸在於Sumcheck協議。

FRI-Binius方案爲FRI變體,可從域證明層中消除嵌入開銷,而不會導致聚合證明層的成本激增。

當前,Irreducible團隊正開發其遞歸層,並與Polygon團隊合作構建Binius-based zkVM；JoltzkVM正從Lasso轉向Binius；Ingonyama團隊正在實現FPGA版本的Binius。