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

1. 引言

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

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

二進制域廣泛應用於密碼學,如AES(F28)、GMAC(F2128)、QR碼(F28)等。當採用較小域時,擴域操作對確保安全性愈發重要。Binius使用的二進制域,需完全依賴擴域來保證安全性和可用性。大多數Prover計算在基域下操作,高效;隨機點檢查和FRI計算需深入更大擴域,確保安全性。

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核心檢查機制:

1. GateCheck
2. PermutationCheck
3. LookupCheck
4. MultisetCheck
5. ProductCheck
6. ZeroCheck
7. SumCheck
8. BatchCheck

Binius對HyperPlonk改進:

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

2.3 PIOP:新的multilinear shift argument

關鍵方法:

• Packing:將相鄰較小元素打包成更大元素
• 移位運算符:重新排列塊內元素

2.4 PIOP:改編版Lasso lookup argument

Lasso協議優勢:

• 證明效率高:m+n個域元素承諾
• 無需承諾大表:可處理超大表

Binius引入乘法版Lasso協議:

• 通過二進制域乘法生成元遞增"內存計數"
• 證明方承諾非零讀取計數向量確保安全

2.5 PCS:改編版Brakedown PCS

核心思想:packing

兩種方案:

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

小域多項式承諾與擴展域評估:

• 承諾在小域K上
• 評估在更大擴展域L/K中

塊級編碼與Reed-Solomon碼:

• 允許小域(如F2)多項式使用大字母表(如F216) Reed-Solomon碼高效承諾

3. 優化思考

四個關鍵優化點:

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

將"檢查A·B =? C"轉換爲"檢查(gA)B =? gC"

• 只需一個輔助承諾
• 減少Sumchecks開銷

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

優化方法:

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

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

改進重點:

• 切換輪次t的選擇
• 基域大小影響
• Karatsuba算法優化
• 內存效率提升

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

四項創新:

1. 扁平化多項式
2. 子空間消失多項式
3. 代數基打包
4. 環交換SumCheck

FRI-Binius可將Binius證明大小減少一個數量級

4. 小結

Binius優勢:

• 可爲witnesses使用最小power-of-two域
• 低內存使用率快速證明
• 基本移除Prover commit承諾瓶頸

新瓶頸:Sumcheck協議

• 可借助專用硬件高效解決

FRI-Binius:

• 消除域證明層嵌入開銷
• 不導致聚合證明層成本激增

當前進展:

• Irreducible團隊開發遞歸層,與Polygon合作構建Binius-based zkVM
• JoltzkVM從Lasso轉向Binius
• Ingonyama實現FPGA版Binius