本文分析了Binius STARKs的最佳化方案，強調其與傳統SNARKs的區別，採用基於雜湊的編碼以提升效率。 Binius解決了小域計算中的冗餘，透過多指標方式優化資料表示，同時引入了靈活的查找和驗證演算法。該協定結合了改進的HyperPlonk PIOP和Brakedown PCS，特別適用於二進位域，克服了計算開銷與傳輸資料的瓶頸。最佳化建議包括基於GKR的PIOP以及小域Sumcheck協議，旨在進一步降低證明大小與提升運算效率，從而為高效的零知識證明系統奠定基礎。
原文標題：Binius STARKs 分析及其優化原文作者：mutourend & lyndell, Bitlayer Labs
1 引言
區別於基於橢圓形的SNARKs，可以將STARKs 看成是基於哈希的SNARKs。目前STARKs 效率低下的一個主要原因是：實際程序中的大多數數值都較小，例如對於循環中的索引、真假值然而，為了保證基於Merkle 樹證明的安全性，利用Reed-Solomon 編碼對數據進行擴展時，額外的激勵值會影響整個域，即使原始值本身非常小。為解決該問題，縮小範圍成為關鍵策略。
如表1所示，第1代STARKs編碼位寬為252bit，第2代STARKs編碼位寬為64bit，第3代STARKs編碼位寬為32bit，但32bit編碼位寬仍存在大量的冗餘空間。而言，二進位域允許直接對位進行操作，編碼緊湊而無任何浪費空間，即第4代STARK。
表1: STARKs 衍化路徑
相較於Goldilocks、BabyBear、Mersenne31等近幾年新研究發現的有限域，二元域的研究可追溯至上個世紀80年代。目前，二進位域已經廣泛驗證密碼學中，典型的例子包括：
· 高級加密貨幣標準（AES），基於F28域；
· Galois訊息認證碼（GMAC），基於F2128域；
· QR碼，使用基於F28的Reed-Solomon編碼；
· 原始FRI和zk-STARK協議，以及進入SHA-3的Grøstl雜湊函數，該函數基於F28域，是一種非常適合梯度的雜湊演算法。
當採用較小的域時，擴域操作對於確保安全性癒發重要。而Binius所使用的二進位域，則需要完全依賴擴域來確保其安全性和實際可用性。大多數Prover計算中涉及的示範式消耗進入擴域，而只需在基域下操作，從而在小域中實現了高效率。然而，隨機點檢查和FRI計算仍需深入到更大的擴域中，以確保所需的安全性。
基於二進位域來建構證明系統時，2個實際問題：STARKs中計算trace表示時，所用域大小應大於百分比式的階；STARKs中Merkle樹表示時，需做Reed-Solomon編碼，所用域大小應存在大於編碼擴展後的大小。
Binius提出了一個創新的方案，分別處理這兩個問題，並透過兩種不同的方式表示相同的數據來實現：首先，採用多指標（具體是多線性）替代單指標替代式解決，透過其在「超立方體」（hypercubes）上的取值來表示整個計算統計；其次，由於超立方體每個維度的長度長度為2，因此無法像STARKs那樣進行標準的Reed-Solomon擴展，但可以將超立方體進行標準的Reed-Solomon擴展，但可以將超立方體認為方形（square），基於該方形進行Reed-Solomon擴展。這種方法在確保安全性的同時，極大的提升了編碼效率和計算效能。
2 原理解析
目前大多數SNARK 系統的建置通常包含以下兩個部分：
· 資訊理論論證式同胞機論證（Information-Theoretic Polynomial Interactive Oracle Proof, PIOP）：PIOP作為論證系統的核心，將輸入的計算關係轉化為可以驗證的示範式等式。不同的PIOP協議透過與驗證者的交互，允許論證者逐步導出演示式，使得驗證者透過查詢少量大象式的評估結果即可驗證計算是否正確。現有的PIOP 協定包括：PLONK PIOP、Spartan PIOP 和HyperPlonk PIOP 等，它們分別對應於演示式K線走勢圖的處理方式不同，從而影響整個SNARK系統的性能和效率。
· 大象式承諾方案（Polynomial Commitment Scheme, PCS）：大象式承諾方案用於證明PIOP 產生的大象式等式是否成立。 PCS 是一個密碼學工具，透過它，證明者承諾某個大象式並在近期驗證該示意式的評估結果，同時隱藏了示意式的其他資訊。常見的示意方案有KZG、Bulletproofs、FRI（Fast Reed-Solomon IOPP）和Bakedown等。不同的PCS具有不同的效能、安全性和適用場景。
根據特定需求，選擇不同的PIOP和PCS，並結合適當的有限域或橢圓曲線，可以建構不同屬性的證明系統。例如：
• Halo2：由PLONK PIOP 與Bulletproofs PCS 結合，並基於Pasta 曲線。 Halo2 設計時，請專注於可擴充性，以及刪除ZCash 協定中的可信任設定。
• Plonky2：採用PLONK PIOP 與FRI PCS 結合，並基於Goldilocks 域。 Plonky2 是為了實現高效線性的。在設計這些系統時，所選的PIOP 和PCS 必須與所使用的有限域或橢圓形橢圓形相匹配，以確保系統的正確性、選擇效能和安全性。這些組合的不僅影響SNARK的證明大小和驗證效率，還決定了系統是否能夠在可信任設定的前提下實現透明性，是否可以支援解析證明或聚合證明等擴展功能。
Binius：HyperPlonk PIOP + Brakedown PCS + 二進位域。具體而言，Binius 包括五項關鍵技術，以實現其高效和安全性。首先，基於塔式二進位域（towers of binary fields）的算術化構成了其其次，Binius在其吸入Oracle驅動協議（PIOP）中，改編了HyperPlonk乘積與排列檢查，確保了各變量排列之間的高效安全的一致性檢查。第三，協議引入了一個新的多線性方程，優化了在小域上驗證多線性關係的效率。第四，Binius採用了改良版的Lasso替換演算法，為尋找機制提供了靈活的方法最後，協定使用了小域高效能控制方案（Small-Field PCS），能夠在二進位域上實現高效的證明系統，並減少了通常與大域相關的開銷。
2.1 有限域：基於二元域塔的算術化
塔式二進位域是實現快速可驗證計算的關鍵，主要歸因於高效計算和運算化兩個面向。二進位域本質上支援高效的運算操作，從而成為對效能要求敏感的密碼學應用另外，二進位域結構支援簡化的運算過程，即在二進位域上執行的運算可以以結構緊湊且易於驗證的代數形式表示。這些特性，再加上能夠透過塔結構充分利用其層次化的特性，使得二元域特別適合於諸如Binius 這樣的可擴展的證明系統。
其中「canonical」是指在二進位域中元素的且唯一直接的表示方式。例如，在通訊的二進位域F2中，任意k位的都字串可以直接對應到一個k位的二進位域元素。與質數域不同，質數域無法在給定位數內提供這種規範的表示。雖然32位元的質數域可以包含在32位元中，但並不是每個32位元的字串唯一地對應一個域元素在質數域Fp 中，常見的歸約方法包括Barrett 歸約、Montgomery 歸約，以及針對Mersenne-31 或Goldilocks-64 等特定有限域的特殊歸約方法。在二元域F2k中，常用的歸約方法包括特殊歸約（如AES中使用）、Montgomery歸約（如POLYVAL中使用）和非線性歸約（如Tower）。論文《Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implements》指出，二進位域在加法和乘法侵犯中均消耗引入位，且二進位域的四進位核心非常高效，因為它遵循(X + Y )2 = X2 + Y 2的簡化規則。
如圖1所示，一個128位元字串：該字串可以在二進位域的上下文中以多種方式進行解釋。它可以被視為128位元二進位域中的一個唯一元素，或是被解析為兩個64位元塔域元素、4個32位元塔域元素、16個8位元塔域元素，或128個F2域元素。這種表示的靈活性不需要任何計算頭部，只是對位字串的類型轉換（ typecast），是一個非常有趣且有用的屬性。同時，小元素可以被節省為更大的域元素，而不需要額外的計算開銷。 Binius協定利用了這項特性，以計算效率。另外，論文提高了《論特徵二塔域中的高效反演》探討了在n塔位二進位域中（可分割為m位子域）進行乘法、平方和求式逆運算的計算複雜度。
圖1：塔式二進位域
2.2 PIOP：改編版HyperPlonk Product 和PermutationCheck－適用於二進位域
Binius 協定中的PIOP 設計了HyperPlonk，採用了一系列核心檢查，用於驗證機制和多指標集合的正確性。這些核心檢查包括：
1.GateCheck：驗證保密見證ω和公開輸入x是否滿足電路侵犯關係C(x,ω)=0，以確保電路正確運作。
2.PermutationCheck：驗證兩個多指標指標式f和g在布林超立方體上的求值結果是否為置換關係f(x) = f(π(x))，以確保指標式指標之間的排列一致性。
3.LookupCheck：驗證對照式的求值是否在給定的查找表中，即f(Bμ) ⊆ T(Bμ)，確保某些值在指定範圍內。
4.MultisetCheck：檢查多個多變量集合是否一致性，即{(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H，保證多個集合間的一致性。
5.ProductCheck：檢測有乘積式在布林超立方體上的求值是否等於某個聲明的值∏x∈Hµ f(x) = s，以確保乘積式的正確性。
6.ZeroCheck：一個多指標演示式在布爾超立方體上的任意點是否為零∏x∈Hµ f(x) = 0,∀x ∈ Bµ，以確保驗證式的零點分佈。
7.SumCheck：偵測多指標示範式的求值是否為報表的值Σx∈Hµ f(x) = s。透過將多元指標示範式的求值問題轉換為單指標示範式的求值，降低驗證方的計算複雜度另外，允許SumCheck還批處理，透過引入隨機數，構造線性組合實現對多個和校驗初始化的批次。
8.BatchCheck：基於SumCheck，驗證多個指標示範方式求值的正確性，以提高協定效率。
儘管Binius與HyperPlonk在協議設計上有許多相似之處，但Binius在以下3個方面做出了改進：
· ProductCheck優化：在HyperPlonk中，ProductCheck要求分母U在超立方體上處非零，且乘積必須等於一個特定值；Binius透過將值特化為1，簡化此檢查過程，從而降低計算複雜度。
· 零問題的處理：HyperPlonk 未能充分處理除零情況，導致無法斷言U 在超立方體上的非零問題；Binius 正確地處理了這個問題，即使在除母純淨的情況下，Binius 的ProductCheck也可以繼續處理，允許推廣到任意乘積值。
· 跨列PermutationCheck：HyperPlonk 無此功能；Binius 支援在多個欄位之間進行PermutationCheck，這使得Binius 能夠處理更複雜的陣列式排列情況。
因此，Binius透過對現有PIOPSumCheck的改進，提升了協定的靈活性和效率，尤其是在處理機制更複雜的多指標指示器式驗證時，提供了更強的功能支援。這些改進解決了HyperPlonk中的腋下性，也為未來基於二元域的論證系統奠定了基礎。
2.3 PIOP：新的多線性移位論證－適用於布林超立方體
在Binius協定中，虛擬產出方式的建構和處理是關鍵技術之一，能夠有效地從輸入句柄或其他虛擬產出方式派生的生成方式產生和操作。以下是兩個關鍵方法：
· 打包：此方法透過將排序中順序位置的較小元素縮小成更大的元素來最佳化操作。打包運算子針對大小為2κ的區塊操作，把它們組合成高維域中的單一元素。多線性擴展（Multilinear Extension，MLE），這個虛擬計算公式可以有效率地和評估處理，將函數轉換為另一個計算公式，從而提高了計算效能。
· 升降支架：升降支架重新排列塊內的元件，基於給定偏移量o 進行循環升降。此方法適用於大小為2b 的區塊，每個區塊根據偏移量執行升降。移位運算子透過偵測函數的支援來進行定義，確保在處理虛擬模擬式時保持一致性和效率。評估此構造的複雜度隨區塊大小線性增長，特別適用於處理資料大集或布林超立方體中的高維場景。
2.4 PIOP：改編版Lasso查找參數－適用於二進位域
Lasso 協議允許證明方承諾一個支持a ε Fm，並證明其所有元素均存在於一個預先指定的表t ε Fn 中。 Lasso 解鎖了「查找奇點」（查找奇點）的概念，並能適用於多線性逆變承諾方案。其效率體現在以下兩個：
· 證明效率：對於大小為n 的表中的m 次查找，證明方只需承諾m+n 個域元素。這些域元素的數量，均位於集合{0,…,m} 中。在多次冪冪的承諾方案中，證明方的計算成本為O(m + n)次方冪（如橢圓曲線點加），外加證明多線性算式在布林超立方體上是否為表元素的求成本值。
· 消耗承諾大表：如果表t 是構造的，則其本身進行承諾，可以處理超大表（如2128 或更大因此）。說明方的運行時間僅與訪問的表邊界相關。對於任何整數參數c > 1，證明方的主要成本是證明大小，承諾的域元素為3·cm + c·n1/c 個。這些域元素都是較小的，位於集合{0,…,max{ m,n1/c,q} − 1} 中，其中q 為a 中的頂點。
Lasso 協定由以下三個元件構成：
· 大表的虛擬實例方式抽象化：透過將虛擬實例方式組合，實現在大表上的高效操作，確保在表內進行的查找和處理。
· 小表查找：Lasso 的核心是小表查找，作為虛擬仿真方式協議的核心構建，使用離線內存檢測一個驗證虛擬仿真方式在布爾超立方體上的求值是否是另一個虛擬仿真方式求值的子集。一個發現的過程將關注多集合檢測的任務。
· 多集合檢查：Lasso 引入虛擬協定來執行多集合檢查，驗證兩個集合的元素是否一致或滿足特定條件。
Binius協定將Lasso適應於二進位域的操作，假設目前是一個大特徵的質數域（遠大於被查找列的長度）。 Binius引入了乘法版本的Lasso協議，要求證明方和驗證方聯合遞增協議的「記憶體計數」操作，不是透過簡單的加1遞增，而是透過二進位域中的乘法產生元來遞增。然而，這種乘法改編引入了更多的複雜性，與遞增操作不同，乘法生成元並不是在所有情況下遞增，在0 處存在單一軌道，這可能成為攻擊點。為防止這種潛在的攻擊，證明方必須承諾一個處非零的計數讀數支持，以確保協議的安全性。
2.5 PCS：改編版Brakedown PCS－適用於Small-Field
建構BiniusPCS 的核心思想是打包。 Binius 論文中提供了2 種基於二進位域的Brakedown 逆變式一致性方案：一種是採用級聯代碼來實例化；另一種採用區塊級編碼技術，支援單獨使用Reed-Solomon第二個Brakedown PCS方案，簡化了證明和驗證流程，但證明大小勉強達到了第一個略大一點，但所帶來的簡化和實現優勢，做該取捨是值得的。
Binius 吸煙式計劃主要使用小域吸煙計劃與擴展域評估、小域通用構造和區塊級編碼與Reed-Solomon 碼技術。
小域示範式承諾與擴展域評估：Binius 協議中的承諾是在小域K 上的示範式承諾，並在更大的擴展域L/K 中進行評估。此方法確保了每個多域示範式t( X0,…,Xℓ−1) 屬於域 K[X0,…,Xℓ−1]，而評估點可以位於更大的擴展域L。承諾方案專門設計針對小域的檢索方式，並能在擴展域上進行查詢，同時確保承諾的安全性和效率。
小域通用構造：小域通用構造透過定義參數ℓ、域K 相關的線性塊碼C，其保證擴展域L 足夠大，以支援安全評估。為了在保持計算效率的同時提高安全性，協議透過擴展域的特性，以及採用線性塊碼對灌溉方式進行編碼，保證了承諾的可靠性。
區塊級編碼與Reed-Solomon碼：針對欄位比線性區塊碼字母表更小的ID 式，Binius 提出了區塊級編碼方案。透過此方案，即使在小域（如F2）中定義的ID 式，也可以使用如F216這樣的大字母表的Reed-Solomon碼高效承諾。 Reed-Solomon碼之所以被選中，是因為它具有高效率性和最大距離分離特性。此方案透過將訊息備用並逐行編碼，之後利用Merkle 樹進行承諾，簡化了操作的複雜度。區塊級編碼允許高效小域噴射式的承諾，而不會產生通常與大域相關的高計算開銷，從而使得在F2 等小域中的打擊式成為可能，並在生成證明與驗證中保持計算效率。
3 優化思考
為了進一步提升Binius協定的效能，本文提出了四個關鍵最佳化點：
1.基於GKR的PIOP：針對二進位域乘法侵犯，借助GKR協議，來替換Binius論文中的Lasso Lookup演算法，可大幅降低Binius的承諾開銷；
2.ZeroCheck PIOP最佳化：在Prover與Verifier之間進行計算開銷權衡，使得ZeroCheck操作更有效率；
3.Sumcheck PIOP最佳化：針對小域Sumcheck的最佳化，進一步減少了小域上的運算負擔；
4.PCS優化：透過FRI-Binius優化，降低證明大小，提高協議的整體效能。
3.1 基於GKR的PIOP：基於GKR的二進位域乘法
Binius論文引入了一種基於查找的方案，旨在實現高效的二進位域乘法侵犯。透過Lasso查找參數改造的二元域乘法演算法依賴於查找和加法操作的線性關係，這些操作與單字中的肢體數量成雖然該演算法在一定程度上優化了乘法操作，但仍需要與肢體數量線性相關的輔助承諾。
GKR（Goldwasser-Kalai-Rothblum）協議中的核心思想是，證明方（P）和驗證方（V）針對一個有限域F上的分層算術電路達成協議。此電路的每個節點有兩個輸入，計算所需的函數。為了減少驗證方的計算複雜度，協議採用SumCheck協議，將關於電路輸出閘值的聲明首先簡化為對於高層的閘值聲明，協議最終將聲明簡化到關於輸入的聲明這樣，驗證方只需檢查電路輸入的正確性即可。
基於GKR 的整數乘法侵犯演算法，透過將“檢查2 個32 位元整數A 和B 是否滿足A·B =？ C”，轉換為“檢查中(gA)B =? gC是否成立”，借助GKR協議大幅減少承諾開銷。與先前的Binius查找方案相比，基於GKR的二進位域乘法只需一個輔助承諾，並且透過減少Sumchecks的開銷，使該演算法更加高效，特別是在Sumchecks 操作比承諾生成更便宜的場景下。隨著Binius 優化的推進，基於GKR 的乘法進攻逐漸成為和二進位域架構式承諾開銷的有效路徑。
3.2 ZeroCheck PIOP優化：Prover 與Verifier 計算開支重量衡
論文《Some Improvements for the PIOP for ZeroCheck》在論證方（P）和驗證方（V）之間調整工作量的分配，提出了多種最佳化方案，以權衡開銷。該工作探索了不同的k值配置，使得在證明方和驗證方之間達成了成本的權衡，特別是在減少資料傳輸和降低計算複雜度方面。
減少證明方的資料傳輸：透過將部分工作轉移給驗證方V，從而減少證明方P發送的資料量。在第i輪中，證明方P需要向驗證方V發送vi+1(X)，其中X=0,…,d + 1。驗證方V檢查以下等式與驗證資料的正確性
vi = vi+1(0) + vi+1(1)。
最佳化方法：驗證方P 可以選擇不傳送vi+1(1)，而是讓驗證方V 自行透過以下方式計算出該值
vi+1(1) = vi − vi+1(0)。
另外，在第0 輪，誠實的證明方P 始終發送v1(0) = v1(1) = 0，這意味著消耗進行評估計算，從而顯著減少了計算和傳輸成本，降低至d2n−1CF + (d + 1)2n−1CG。
減少證明方評估點的數量：在協議的第i 輪中，驗證者在先前的i 輪中已經發送了一個值序列r =(r0,…,ri−1)。目前協定要求證明者( P) 發送演示式
vi+1(X) = Σ δˆn(α,(r,X,x))C(r,X,x).x∈H −−1
最佳化方法：證明方P 發送以下灌溉式這兩個函數之間的關係是：
vi(X) = vi′(X)·δi+1((α0,…,αi),(r,X))
其中δˆi+1因為驗證者擁有α和r，所以是完全已知的。這個修改的好處是vi′(X)的次數比vi(X)少1，這意味著證明者需要評估的點更少因此，主要的協議變化發生在輪次之間的檢查階段。
另外，將具體的約束vi = vi+1(0)+vi+1(1) 最佳化為(1−αi)vi′+1(0)+αivi′+1(1) = vi′(X)。則證明者需要更少評估和發送的數據，進一步減少傳輸的數據量。計算δˆn−i−1也比計算δˆn更有效率。透過這兩項改進，成本降低為大約：2n−1(d− 1) )CF + 2n−1dCG。在常見的d=3 情況下，這些最佳化使成本降低了5/3 倍。
代數插值最佳化：對於誠實的證明者，C(x0,…,xn−1) 在Hn 上零，可表示為：C(x0,…,xn-1)= Σxi(xi- 1)Qi(x0, …,xn-1)。雖然Qi不是唯一的，但可以透過刪除式長除法構造一個小區的分割：從Rn=C開始，逐次除以xi(xi−1)來計算Qi 和Ri，其中R0 是C 在Hn 上的多線性擴展，且假設其為零。分析Qi 的次數，可以得到： 對於j> i，Qj 在xi 上的次數與C 相同；對於j = i，次數減少2；對於 j
C(r,X,x) − Qi(r,X,x) = X(X − 1)Qi+1(r,X,x)
因此，在協議的每一輪中，只需引入一個新的Q，其評估值可以從C和先前的Q計算得出，實現插值優化。
3.3 Sumcheck PIOP最佳化：基於小域的Sumcheck協議
Binius所實現的STARKs 方案，其承諾開銷很低，使得證明者瓶頸不再是PCS，而是採用sum-check 協議。 Ingonyama 在2024 年提出了基於小域的Sumcheck 協定的改進方案（對應圖2 中的） Algo3 和Algo4 演算法），並開源了實作程式碼。演算法4 專注於將Karatsub 演算法合併到演算法3 中，以額外的基域乘法為代價來最小化擴域乘法次數，當擴域乘法比基域乘法昂貴的手術時，演算法4的表現會更好。
· 切換輪次的影響與改善因子
基於小域的Sumcheck 協定的改進中心化於切換輪次t 的選擇。切換輪次是指從優化演算法切換回樸素演算法的時間點，論文的實驗表明，在最佳切換點時，改進因子達到頂點如果這個切換點，優化演算法的性能優勢，效率下跌。這是由於小域上的基域乘法與擴域乘法相比有更高的時間，因此在適當的時機切換回樸素演算法至關重要。
圖2：切換輪次與改善因子關係
對於具體應用，如涉及Cubic Sumcheck（d = 3）的情況，基於小域的Sumcheck 協定進而於樸素演算法的改進達到了一個數量級。例如，在基域為GF[2] 的情況下，演算法4 的效能比樸素演算法高出近30 倍。
· 基域大小對效能的影響
論文的實驗結果表明，較小的基域（如GF[2]）能夠使最佳化演算法顯示出更顯著的優勢。這是因為擴展與基域乘法的時間範圍在較小的基域上更高，從而優化演算法在此條件下表現出更高的改進因子。
· Karatsuba 演算法的最佳化效益
Karatsuba 演算法在提升基於小域的Sumcheck 效能方面表現出了顯著的效果。對於基域GF[2]，演算法3 和演算法4 的提升因子分別為6 和30，演算法4 比演算法3 高效五倍。 Karatsuba 最佳化不僅提升了運作效率，也優化了演算法的切換點，分別在演算法3 的t=5和演算法4 的t=8 達到最佳。
· 記憶體效率的提升
基於小域的Sumcheck 協定除了提升運行時間，在記憶體效率方面也展現了顯著的優勢。演算法4 的記憶體需求為O(d·t)，而演算法3 的記憶體需求為O(2d·t)。當t=8 時，演算法4 外圍0.26MB 的內存，而演算法3 則需要67MB 來儲存基域的乘積。這使得演算法4 在記憶體設定裝置上表現出更強的最佳化，尤其適用於資源有限的客戶端論證環境。
3.4 PCS最佳化：FRI-Binius 降低Binius證明尺寸
Binius 協議的一個主要缺陷在於其相對增大的證明大小，隨著見證大小的平方根按O(√N) 縮放。與更有效率的系統相比，這種平方根大小的證明是一種限制。 ，對數級（多對數）證明大小對於實現真正“簡潔”的驗證器至關重要，這在像Plonky3這樣的先進系統中得到了驗證，晚上通過FRI等先進技術實現了對數級證明。
論文《Polylogarithmic Proofs for Multilinears over Binary Towers》，簡稱FRI-Binius，實現了二元域FRI折疊機構，帶來了4個方面的創新：
· 梵紙化大象式：最初的多線性大象式被轉換為LCH（低碼高度）全新大象式基礎。
· 子空間消除示意式：用於在係數域上執行FRI，並透過加性NTT（數論轉換）實現類似FFT的分層。
· 代數基礎儲備：支援協議中資訊的儲備，可取消嵌入開銷高效率。
· 環交易所SumCheck：一種新穎的SumCheck方法，利用環交易所技術優化性能。
基於二元域FRI-Binius 的多線性灌溉式控制方案（PCS）的核心思想為：FRI-Binius 協定透過將初始的二元域多線性灌溉式（定義於F2 上）備份為定義在更大域K 上的多線性演示式來操作。
在基於二進位域的FRI-BiniusPCS中，流程如下：
· 承諾階段：對一個ℓ指標的多線性調節式（定義於F2上）的承諾轉化為對一個備用後ℓ’變量的多線性調節式（定義於F2128上）的承諾，係數個數因此減少了128倍。
· 評估階段：證明方和驗證方進行ℓ′輪交叉環切換SumCheck 和FRI 交互證明（IOPP）：
–FRI 開放論證討論了論證的大小。
– 證明方的SumCheck 成本類似於大範圍上的SumCheck 成本。
– 證明方的FRI 成本與常規大範圍上的FRI 成本相同。
–驗證方接收128個來自F2128的元素，並執行128個額外的乘法侵犯。
借助FRI-Binius，可將Binius的證明大小減少一個數量級。這使得Binius的證明大小更加接近最先進的系統，同時保持與二進位域的兼容性。專為二進制域定制的FRI折疊技術，加上代數節省和SumCheck 的優化，使得Binius 能夠在保持高效驗證的同時，產生更簡潔的證明。
表2：Binius 與FRI-Binius 證明大小
表3：Plonky3 FRI 與FRI-Binius
4 小結
Binius 的整個架構價值是，可以見證使用最小的二冪域，只需根據所需選擇來域大小。 Binius 是「使用硬體、軟體、與FPGA 中加速的Sumcheck 協定」的精心設計方案，可以以非常低的記憶體使用率來快速證明。 Halo2 和Plonky3 等證明系統有4 個佔用大部分計算量的關鍵步驟：產生見證資料、對見證資料進行承諾、vanishingargument、openingproof。以Plonky3 中的Keccak 與Binius 中的Grøstl 雜湊函數為例，兩者對應的以上4 大關鍵步驟計算量情況如圖3 所示：
圖3：較小的提交成本
由此可知，Binius中已基本移除了Prover的提交高效承諾瓶頸，新的完全的瓶頸面臨Sumcheck協議，而Sumcheck協議中大規模種植方式評估和域乘法等問題，可藉助專用硬體解決。 FRI-Binius方案，對於FRI 變體，可以提供一個非常緊張的選擇——從證明層中去除嵌入頭域，而不會導致聚合證明層的成本大幅上漲。目前，Irreducible 正在開發其地下水層，並與Polygon 宣布團隊合作構建基於Binius的zkVM；JoltzkVM正從Lasso轉向Binius，以改進其分段性能；Ingonyama團隊正在實現FPGA版本的Binius。
參考文獻：
2024.04 Binius 關於二元域塔的簡潔論證
2024.07 Fri-Binius 二元塔上多重線性的多對數證明
2024.08 Binius 中的整數乘法：基於GKR 的方法
2024.06 zkStudyClub – FRI-Binius：二元塔上多重線性的多對數證明
2024.04 ZK11：Binius：硬體優化的SNARK – Jim Posen
2023.12 第303集與烏爾維塔娜一起潛入比尼烏斯
2024.09 設計高性能zkVM
2024.07 Sumcheck與Open-Binius
2024.04 Binius：二進位域的高效率證明
2023.12 二進位字段上的SNARK：Binius – 第1 部分
2024.06 二進位字段上的SNARK：Binius – 第2 部分
2022.10 HyperPlonk，ZKEVM 的防zk 系統
原文連結
歡迎加入律動BlockBeats官方社群：
Telegram 訂閱群：https://t.me/theblockbeats
Telegram交易所群：https://t.me/BlockBeats_App
Twitter 官方帳號：https://twitter.com/BlockBeatsAsia
資訊來源：0x資訊編譯自網際網路。版權所有，未經許可，不得轉載