🎉【Gate 3000萬紀念】曬出我的Gate時刻,解鎖限量好禮!
Gate用戶突破3000萬!這不僅是數字,更是我們共同的故事。
還記得第一次開通帳號的激動,搶購成功的喜悅,或陪伴你的Gate週邊嗎?
📸 參與 #我的Gate时刻# ,在Gate廣場曬出你的故事,一起見證下一個3000萬!
✅ 參與方式:
1️⃣ 帶話題 #我的Gate时刻# ,發布包含Gate元素的照片或視頻
2️⃣ 搭配你的Gate故事、祝福或感言更佳
3️⃣ 分享至Twitter(X)可參與瀏覽量前10額外獎勵
推特回鏈請填表單:https://www.gate.com/questionnaire/6872
🎁 獨家獎勵:
🏆 創意大獎(3名):Gate × F1紅牛聯名賽車模型一輛
👕 共創紀念獎(10名): 國際米蘭同款球員衛衣
🥇 參與獎(50名):Gate 品牌抱枕
📣 分享獎(10名):Twitter前10瀏覽量,送Gate × 國米小夜燈!
*海外用戶紅牛聯名賽車折合爲 $200 合約體驗券,國米同款球衣折合爲 $50 合約體驗券,國米小夜燈折合爲 $30 合約體驗券,品牌抱枕折合爲 $20 合約體驗券發放
🧠 創意提示:不限元素內容風格,曬圖帶有如Gate logo、Gate色彩、週邊產品、GT圖案、活動紀念品、活動現場圖等均可參與!
活動截止於7月25日 24:00 UTC+8
3
Binius: STARKs原理及二進制域優化探索
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 + 二進制域。
包括五項關鍵技術:
基於塔式二進制域的算術化構成計算基礎
改編HyperPlonk乘積與置換檢查,確保變量及置換一致性檢查
新的多線性移位論證,優化小域上多線性關係驗證效率
改進版Lasso查找論證,爲查找機制提供靈活性和安全性
小域多項式承諾方案,實現二進制域上高效證明系統
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多項式承諾方案:
採用concatenated code實例化
採用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方面創新:
借助FRI-Binius,可將Binius證明大小減少一個數量級,接近最先進系統。
4. 小結
Binius已基本移除Prover commit承諾瓶頸,新瓶頸在於Sumcheck協議。FRI-Binius方案爲FRI變體,可從域證明層消除嵌入開銷。
Irreducible團隊開發遞歸層,與Polygon合作構建Binius-based zkVM。JoltzkVM從Lasso轉向Binius改進遞歸性能。Ingonyama實現FPGA版Binius。