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

1. 引言

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

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

相比近幾年研究的Goldilocks、BabyBear、Mersenne31等有限域,二進制域研究可追溯到上世紀80年代,已廣泛應用於密碼學,如AES(F28域)、GMAC(F2128域)、QR碼(F28域Reed-Solomon編碼)等。

Binius使用二進制域,需完全依賴擴域保證安全性和可用性。大多數Prover計算在基域下操作高效,隨機點檢查和FRI計算需深入擴域確保安全性。

Binius通過多變量多項式在"超立方體"上取值表示計算軌跡,將超立方體視爲方形進行Reed-Solomon擴展,在確保安全性同時極大提升編碼效率與計算性能。

2. 原理解析

Binius:HyperPlonk PIOP + Brakedown PCS + 二進制域。

包括五項關鍵技術:

1. 基於塔式二進制域的算術化構成計算基礎

2. 改編HyperPlonk乘積與置換檢查,確保變量及置換一致性檢查

3. 新的多線性移位論證,優化小域上多線性關係驗證效率

4. 改進版Lasso查找論證,爲查找機制提供靈活性和安全性

5. 小域多項式承諾方案,實現二進制域上高效證明系統

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

塔式二進制域支持高效算術操作和簡化算術化過程,特別適合Binius這樣可擴展的證明系統。

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優化:將值特化爲1,簡化檢查過程降低計算復雜度

• 除零問題處理:正確處理分母爲零情況,允許推廣到任意乘積值

• 跨列PermutationCheck:支持多列間PermutationCheck,處理更復雜多項式排列情況

2.3 PIOP:新的multilinear shift argument

Binius中虛擬多項式構造和處理是關鍵技術:

• Packing:將詞典序相鄰位置較小元素打包成更大元素優化操作

• 移位運算符:重新排列塊內元素,基於給定偏移量循環移位

2.4 PIOP:改編版Lasso lookup argument

Lasso協議允許證明方承諾向量a ∈ Fm並證明所有元素存在於預先指定表t ∈ Fn中。

Binius將Lasso適應二進制域操作,引入乘法版本Lasso協議,要求證明方和驗證方聯合遞增協議"內存計數"操作,通過二進制域乘法生成元遞增。

2.5 PCS:改編版Brakedown PCS

構建BiniusPCS核心思想是packing。提供2種基於二進制域的Brakedown多項式承諾方案:

1. 採用concatenated code實例化

2. 採用block-level encoding技術,支持單獨使用Reed-Solomon codes

第二種方案簡化證明和驗證流程,proof size略大但簡化和實現優勢值得。

3. 優化思考

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

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

基於GKR的乘法運算只需一個輔助承諾,通過減少Sumchecks開銷使算法更高效,特別是Sumchecks操作比承諾生成更便宜的場景。

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

減少證明方數據傳輸:將部分工作轉移給驗證方,降低證明方發送數據量。

減少證明方評估點數量:修改多項式發送方式,減少評估點數量。

代數插值優化:通過多項式長除法構造有序分解,實現插值優化。

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

切換輪次的影響與改進因子:切換輪次t選擇影響性能,最佳切換點改進因子達最大值。

基域大小對性能影響:較小基域(如GF[2])優化算法優勢更顯著。

Karatsuba算法優化收益:顯著提升基於小域Sumcheck性能,算法4比算法3高效五倍。

內存效率提升:算法4內存需求O(d·t),算法3爲O(2d·t),適用資源有限環境。

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

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

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

借助FRI-Binius,可將Binius證明大小減少一個數量級,接近最先進系統。

4. 小結

Binius已基本移除Prover commit承諾瓶頸,新瓶頸在於Sumcheck協議。FRI-Binius方案爲FRI變體,可從域證明層消除嵌入開銷。

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