Binius STARKs: 深入剖析新一代高效零知識證明技術

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擴展。

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

2. 原理解析

Binius包括五項關鍵技術:

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

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

塔式二進制域的優勢:

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

二進制域優勢:

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

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

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:通過打包相鄰元素優化操作
  • 移位運算符:重新排列塊內元素

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

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碼

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

3. 優化思考

四個關鍵優化點:

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

相比Binius lookup方案的優勢:

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

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

優化方法:

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

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

關鍵點:

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

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

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

FRI-Binius四個創新:

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

FRI-Binius PCS過程:

  • 承諾階段
  • 評估階段

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

4. 小結

Binius的價值主張:

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

FRI-Binius方案:

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

當前進展:

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

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

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

查看原文
此页面可能包含第三方内容,仅供参考(非陈述/保证),不应被视为 Gate 认可其观点表述,也不得被视为财务或专业建议。详见声明
  • 讚賞
  • 5
  • 分享
留言
0/400
分叉自由主义者vip
· 4小時前
性能优化有突破了
回復0
不明所以鲸vip
· 4小時前
需降低域值冗余
回復0
AlphaLeakervip
· 4小時前
扩域安全性需考虑
回復0
元宇宙的包租婆vip
· 4小時前
比起前代有进步了
回復0
空投自助餐vip
· 5小時前
效率才是硬道理
回復0
交易,隨時隨地
qrCode
掃碼下載 Gate APP
社群列表
繁體中文
  • 简体中文
  • English
  • Tiếng Việt
  • 繁體中文
  • Español
  • Русский
  • Français (Afrique)
  • Português (Portugal)
  • Bahasa Indonesia
  • 日本語
  • بالعربية
  • Українська
  • Português (Brasil)