Binius STARKs:基於二進制域的高效率零知識證明創新

Binius STARKs原理解析及優化思考

1. 引言

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

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

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

Binius提出了一種創新的解決方案:首先,使用多變量(具體是多線性)多項式代替單變量多項式,通過其在"超立方體"上的取值來表示整個計算軌跡;其次,將超立方體視爲方形,基於該方形進行Reed-Solomon擴展。這種方法在確保安全性的同時,極大提升了編碼效率與計算性能。

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

2. 原理解析

Binius包括五項關鍵技術:

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

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

塔式二進制域支持高度高效的算術操作,支持簡化的算術化過程。二進制域的元素具有唯一且直接的表示方式,可以靈活地在不同大小的域之間轉換和打包。

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

2.2 PIOP:改編版HyperPlonk Product和PermutationCheck

Binius採用了一系列核心檢查機制,包括GateCheck、PermutationCheck、LookupCheck、MultisetCheck、ProductCheck、ZeroCheck、SumCheck和BatchCheck。

相比HyperPlonk,Binius在以下方面做出改進:

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

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

2.3 PIOP:新的multilinear shift argument

Binius採用Packing和移位運算符兩個關鍵方法來處理虛擬多項式。

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

2.4 PIOP:改編版Lasso lookup argument

Lasso協議由三個組件構成:

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

Binius引入了乘法版本的Lasso協議,要求證明方和驗證方聯合遞增協議的"內存計數"操作,不是通過簡單的加1遞增,而是通過二進制域中的乘法生成元來遞增。

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

2.5 PCS:改編版Brakedown PCS

Binius多項式承諾主要使用:

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

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

3. 優化思考

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

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

4. 小結

Binius基本完全移除了Prover的commit承諾瓶頸,新的瓶頸在於Sumcheck協議。FRI-Binius方案爲FRI變體,可從域證明層中消除嵌入開銷。目前,Irreducible團隊正在開發其遞歸層,並與Polygon團隊合作構建Binius-based zkVM;JoltzkVM正從Lasso轉向Binius;Ingonyama團隊正在實現FPGA版本的Binius。

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

查看原文
此頁面可能包含第三方內容,僅供參考(非陳述或保證),不應被視為 Gate 認可其觀點表述,也不得被視為財務或專業建議。詳見聲明
  • 讚賞
  • 5
  • 分享
留言
0/400
WalletDivorcervip
· 07-27 05:08
只聊安全性你就输了...sigh
回復0
Anon4461vip
· 07-24 16:08
这论文标题唬谁呢 v几
回復0
ProofOfNothingvip
· 07-24 16:06
位宽从252到32,还不够低啊
回復0
跑路预警Botvip
· 07-24 16:00
听说零知识又烧钱了
回復0
StakeOrRegretvip
· 07-24 15:55
论文看了三遍,啥都没看懂
回復0
交易,隨時隨地
qrCode
掃碼下載 Gate APP
社群列表
繁體中文
  • 简体中文
  • English
  • Tiếng Việt
  • 繁體中文
  • Español
  • Русский
  • Français (Afrique)
  • Português (Portugal)
  • Bahasa Indonesia
  • 日本語
  • بالعربية
  • Українська
  • Português (Brasil)