Binius STARKs原理解析及優化思考

1. 引言

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

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

Binius所使用的二進制域，需完全依賴擴域來保證其安全性和實際可用性。大多數Prover計算中涉及的多項式無需進入擴域，而只需在基域下操作，從而在小域中實現了高效率。然而，隨機點檢查和FRI計算仍需深入到更大的擴域中，以確保所需的安全性。

Binius提出了一種創新的解決方案:首先，使用多變量（具體是多線性）多項式代替單變量多項式，通過其在"超立方體"（hypercubes）上的取值來表示整個計算軌跡；其次，由於超立方體每個維度的長度均爲2，因此無法像STARKs那樣進行標準的Reed-Solomon擴展，但可以將超立方體視爲方形（square），基於該方形進行Reed-Solomon擴展。

2. 原理解析

Binius包括五項關鍵技術:

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

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

塔式二進制域的優勢:

• 高效計算:二進制域本質上支持高度高效的算術操作
• 高效算術化:二進制域結構支持簡化的算術化過程
• 規範表示:二進制域中元素有唯一且直接的表示方式

二進制域優勢:

• 加法和乘法運算無需引入進位
• 平方運算非常高效,遵循(X + Y)^2 = X^2 + Y^2 的簡化規則
• 表示靈活性:128位字符串可視爲128位二進制域中的獨特元素,或解析爲多種塔域元素組合

2.2 PIOP:改編版HyperPlonk Product和PermutationCheck

Binius PIOP核心檢查機制:

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

Binius對HyperPlonk的改進:

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

2.3 PIOP:新的multilinear shift argument

關鍵方法:

• Packing:通過打包相鄰元素優化操作
• 移位運算符:重新排列塊內元素

2.4 PIOP:改編版Lasso lookup argument

Lasso協議組成:

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

Binius對Lasso的改編:

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

2.5 PCS:改編版Brakedown PCS

核心思想:packing

兩種基於二進制域的Brakedown多項式承諾方案:

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

主要技術:

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

3. 優化思考

四個關鍵優化點:

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

相比Binius lookup方案的優勢:

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

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

優化方法:

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

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

關鍵點:

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

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

FRI-Binius四個創新:

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

FRI-Binius PCS過程:

• 承諾階段
• 評估階段

4. 小結

Binius的價值主張:

• 可爲witnesses使用最小的power-of-two域
• 協同設計方案,低內存使用率快速證明
• 基本移除Prover的commit承諾瓶頸
• 新瓶頸在於Sumcheck協議,可借助專用硬件高效解決

FRI-Binius方案:

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

當前進展:

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