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

1 引言

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

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

二進制域已經廣泛應用於密碼學中，典型例子包括:

• 高級加密標準(AES)，基於F28域
• Galois消息認證碼(GMAC)，基於F2128域
• QR碼，使用基於F28的Reed-Solomon編碼
• 原始FRI和zk-STARK協議，以及進入SHA-3決賽的Grøstl哈希函數

當採用較小的域時，擴域操作對於確保安全性愈發重要。Binius所使用的二進制域，需完全依賴擴域來保證其安全性和實際可用性。

Binius提出了一種創新的解決方案:

• 使用多變量（具體是多線性）多項式代替單變量多項式，通過其在"超立方體"上的取值來表示整個計算軌跡
• 將超立方體視爲方形，基於該方形進行Reed-Solomon擴展

2 原理解析

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

Binius包括五項關鍵技術:

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

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

塔式二進制域的優勢:

• 高效計算:二進制域本質上支持高度高效的算術操作
• 高效算術化:二進制域結構支持簡化的算術化過程
• 靈活表示:同一個字符串可以在二進制域的上下文中以多種方式解釋
• 無需歸約:二進制域在加法和乘法運算中均無需引入進位
• 高效平方運算:(X + Y)2 = X2 + Y2

2.2 PIOP:改編版HyperPlonk Product和PermutationCheck

核心檢查機制:

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

相比HyperPlonk的改進:

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

2.3 PIOP:新的multilinear shift argument

關鍵方法:

• Packing:通過將詞典序中相鄰位置的較小元素打包成更大的元素來優化操作
• 移位運算符:重新排列塊內的元素，基於給定偏移量進行循環移位

2.4 PIOP:改編版Lasso lookup argument

Lasso協議的優勢:

• 高效證明:對於大小爲n的表中的m次查找,只需承諾m+n個域元素
• 無需承諾大表:如果表t是結構化的,則無需對其進行承諾,可處理超大表

Lasso協議的組成:

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

Binius對Lasso的改編:

• 引入乘法版本的Lasso協議
• 要求證明方承諾一個處處非零的讀取計數向量

2.5 PCS:改編版Brakedown PCS

核心思想:packing

兩種方案:

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

主要技術:

• 小域多項式承諾與擴展域評估
• 小域通用構造
• 塊級編碼與Reed-Solomon碼

3 優化思考

四個關鍵優化點:

1. GKR-based PIOP:針對二進制域乘法運算
2. ZeroCheck PIOP優化:Prover與Verifier計算開銷權衡
3. Sumcheck PIOP優化:基於小域的Sumcheck協議
4. PCS 優化:FRI-Binius降低Binius proof size

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

核心思想:

將"檢查2個32-bit整數A和B是否滿足 A·B =? C" 轉換爲
"檢查中(gA)B =? gC 是否成立"

優勢:

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

3.2 ZeroCheck PIOP優化

優化方向:

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

3.3 Sumcheck PIOP優化

改進重點:

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

具體成效:

• 在基域爲GF[2]的情況下,算法4的性能比樸素算法高出近30倍
• 算法4僅需0.26MB的內存,而算法3則需67MB

3.4 PCS 優化:FRI-Binius

四個創新點:

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

成效: 將Binius證明大小減少一個數量級

4 小結

Binius的優勢:

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

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

最新進展:

• Irreducible團隊正在開發其遞歸層,並與Polygon團隊合作構建Binius-based zkVM
• JoltzkVM正從Lasso轉向Binius,以改進其遞歸性能
• Ingonyama團隊正在實現FPGA版本的Binius