第1,2,3代STARK證明系統(tǒng)位寬分別為252,64和32bit，編碼效率雖有提高，但仍有浪費空間；Binius直接對位操作，編碼緊湊高效，很可能是未來的第4代STARK。Binius使用基于塔式二進制域的算術化、改進版的HyperPlonk乘積與置換檢查、小域多項式承諾等技術，從各個角度提升效率。在二進制域乘法、ZeroCheck、SumCheck、PCS等方面可進一步優(yōu)化，以進一步提高證明速度和降低proof size。
1 引言
區(qū)別于基于橢圓曲線的SNARKs，可將STARKs看成是hash-based SNARKs。當前STARKs效率低下的一個主要原因是：實際程序中的大多數數值都較小，如for循環(huán)中的索引、真假值、計數器等。然而，為了確保基于Merkle樹證明的安全性，使用Reed-Solomon編碼對數據進行擴展時，許多額外的冗余值會占據整個域，即使原始值本身非常小。為解決該問題，降低域的大小成為了關鍵策略。
如表1所示，第1代STARKs編碼位寬為252bit，第2代STARKs編碼位寬為64bit，第3代STARKs編碼位寬為32bit，但32bit編碼位寬仍然存在大量的浪費空間。相較而言，二進制域允許直接對位進行操作，編碼緊湊高效而無任意浪費空間，即第4代STARKs。
表1:STARKs衍化路徑
相比于Goldilocks、BabyBear、Mersenne31等近幾年新研究發(fā)現(xiàn)的有限域，二進制域的研究可追溯到上個世紀80年代。當前，二進制域已經廣泛應用于密碼學中，典型例子包括：
高級加密標準(AES)，基于F28域；
Galois消息認證碼(GMAC)，基于F2128域；
QR碼，使用基于F28的Reed-Solomon編碼；
原始FRI和zk-STARK協(xié)議，以及進入SHA-3決賽的Gr?stl哈希函數，該函數基于F28域，是一種非常適合遞歸的哈希算法。
當采用較小的域時，擴域操作對于確保安全性愈發(fā)重要。而Binius所使用的二進制域，需完全依賴擴域來保證其安全性和實際可用性。大多數Prover計算中涉及的多項式無需進入擴域，而只需在基域下操作，從而在小域中實現(xiàn)了高效率。然而，隨機點檢查和FRI計算仍需深入到更大的擴域中，以確保所需的安全性。
基于二進制域來構建證明系統(tǒng)時，存在2個實際問題：STARKs中計算trace表示時，所用域大小應大于多項式的階；STARKs中Merkle tree承諾時，需做Reed-Solomon編碼，所用域大小應大于編碼擴展后的大小。
Binius提出了一種創(chuàng)新的解決方案，分別處理這兩個問題，并通過兩種不同的方式表示相同的數據來實現(xiàn)：首先，使用多變量（具體是多線性）多項式代替單變量多項式，通過其在“超立方體”（hypercubes）上的取值來表示整個計算軌跡；其次，由于超立方體每個維度的長度均為2，因此無法像STARKs那樣進行標準的Reed-Solomon擴展，但可以將超立方體視為方形（square），基于該方形進行Reed-Solomon擴展。這種方法在確保安全性的同時，極大提升了編碼效率與計算性能。
2 原理解析
當前大多數SNARKs系統(tǒng)的構建通常包含以下兩部分：
信息理論多項式交互預言機證明（Information-Theoretic Polynomial Interactive Oracle Proof, PIOP）：PIOP作為證明系統(tǒng)的核心，將輸入的計算關系轉化為可以驗證的多項式等式。不同的PIOP協(xié)議通過與驗證者的交互，允許證明者逐步發(fā)送多項式，使得驗證者通過查詢少量多項式的評估結果即可驗證計算是否正確?，F(xiàn)有的PIOP協(xié)議包括：PLONK PIOP、Spartan PIOP 和 HyperPlonk PIOP 等，它們各自對多項式表達式的處理方式有所不同，從而影響整個 SNARK 系統(tǒng)的性能與效率。
多項式承諾方案（Polynomial Commitment Scheme, PCS）：多項式承諾方案用于證明PIOP生成的多項式等式是否成立。PCS是一種密碼學工具，通過它，證明者可以承諾某個多項式并在稍后驗證該多項式的評估結果，同時隱藏多項式的其他信息。常見的多項式承諾方案有KZG、Bulletproofs、FRI（Fast Reed-Solomon IOPP）和Brakedown等。不同的PCS具有不同的性能、安全性和適用場景。
根據具體需求，選擇不同的PIOP和PCS，并結合合適的有限域或橢圓曲線，可以構建具有不同屬性的證明系統(tǒng)。例如：
? Halo2：由 PLONK PIOP 與 Bulletproofs PCS 結合，并基于Pasta曲線。Halo2設計時，注重于可擴展性，以及移除ZCash協(xié)議中的trusted setup。
? Plonky2：采用PLONK PIOP與FRI PCS結合，并基于Goldilocks域。Plonky2是為了實現(xiàn)高效遞歸的。在設計這些系統(tǒng)時，選擇的PIOP和PCS必須與所使用的有限域或橢圓曲線相匹配，以確保系統(tǒng)的正確性、性能和安全性。這些組合的選擇不僅影響SNARK的證明大小和驗證效率，還決定了系統(tǒng)是否能夠在無需可信設置的前提下實現(xiàn)透明性，是否可以支持遞歸證明或聚合證明等擴展功能。
Binius：HyperPlonk PIOP Brakedown PCS 二進制域。具體而言，Binius包括五項關鍵技術，以實現(xiàn)其高效性和安全性。首先，基于塔式二進制域（towers of binary fields）的算術化構成了其計算的基礎，能夠在二進制域內實現(xiàn)簡化的運算。其次，Binius在其交互式Oracle證明協(xié)議（PIOP）中，改編了HyperPlonk乘積與置換檢查，確保了變量及其置換之間的安全高效的一致性檢查。第三，協(xié)議引入了一個新的多線性移位論證，優(yōu)化了在小域上驗證多線性關系的效率。第四，Binius采用了改進版的Lasso查找論證，為查找機制提供了靈活性和強大的安全性。最后，協(xié)議使用了小域多項式承諾方案（Small-Field PCS），使其能夠在二進制域上實現(xiàn)高效的證明系統(tǒng)，并減少了通常與大域相關的開銷。
2.1 有限域：基于towers of binary fields的算術化
塔式二進制域是實現(xiàn)快速可驗證計算的關鍵，主要歸因于兩個方面：高效計算和高效算術化。二進制域本質上支持高度高效的算術操作，使其成為對性能要求敏感的密碼學應用的理想選擇。此外，二進制域結構支持簡化的算術化過程，即在二進制域上執(zhí)行的運算可以以緊湊且易于驗證的代數形式表示。這些特性，加上能夠通過塔結構充分利用其層次化的特性，使得二進制域特別適合于諸如Binius這樣可擴展的證明系統(tǒng)
其中“canonical”是指在二進制域中元素的唯一且直接的表示方式。例如，在最基本的二進制域F2中，任意k位的字符串都可以直接映射到一個k位的二進制域元素。這與素數域不同，素數域無法在給定位數內提供這種規(guī)范的表示。盡管32位的素數域可以包含在32位中，但并非每個32位的字符串都能唯一地對應一個域元素，而二進制域則具備這種一對一映射的便利性。在素數域Fp中，常見的歸約方法包括Barrett歸約、Montgomery歸約，以及針對Mersenne-31或Goldilocks-64等特定有限域的特殊歸約方法。在二進制域F2k中，常用的歸約方法包括特殊歸約（如AES中使用）、Montgomery歸約（如POLYVAL中使用）和遞歸歸約（如Tower）。論文《》指出，二進制域在加法和乘法運算中均無需引入進位，且二進制域的平方運算非常高效，因為它遵循(X Y )2 = X2 Y 2 的簡化規(guī)則。
如圖1所示，一個128位字符串：該字符串可以在二進制域的上下文中以多種方式進行解釋。它可以被視為128位二進制域中的一個獨特元素，或者被解析為兩個64位塔域元素、四個32位塔域元素、16個8位塔域元素，或128個F2域元素。這種表示的靈活性不需要任何計算開銷，只是對位字符串的類型轉換（typecast），是一個非常有趣且有用的屬性。同時，小域元素可以被打包為更大的域元素而不需要額外的計算開銷。Binius協(xié)議利用了這一特性，以提高計算效率。此外，論文《》探討了在n位塔式二進制域中（可分解為m位子域）進行乘法、平方和求逆運算的計算復雜度。
圖1:塔式二進制域
2.2 PIOP：改編版HyperPlonk Product和PermutationCheck——適用于二進制域
Binius協(xié)議中的PIOP設計借鑒了HyperPlonk，采用了一系列核心檢查機制，用于驗證多項式和多變量集合的正確性。這些核心檢查包括：
GateCheck：驗證保密見證ω和公開輸入x是否滿足電路運算關系C(x,ω)=0，以確保電路正確運行。
PermutationCheck：驗證兩個多變量多項式f和g在布爾超立方體上的求值結果是否為置換關系f(x) = f(π(x))，以確保多項式變量之間的排列一致性。
LookupCheck：驗證多項式的求值是否在給定的查找表中，即f(Bμ) ? T(Bμ)，確保某些值在指定范圍內。
MultisetCheck：檢查兩個多變量集合是否相等，即{(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H，保證多個集合間的一致性。
ProductCheck：檢測有理多項式在布爾超立方體上的求值是否等于某個聲明的值∏x∈Hμ f(x) = s，以確保多項式乘積的正確性。
ZeroCheck：驗證一個多變量多項式在布爾超立方體上的任意點是否為零∏x∈Hμ f(x) = 0,?x ∈ Bμ，以確保多項式的零點分布。
SumCheck：檢測多變量多項式的求和值是否為聲明的值∑x∈Hμ f(x) = s。通過將多元多項式的求值問題轉化為單變量多項式求值，降低驗證方的計算復雜度。此外，SumCheck還允許批處理，通過引入隨機數，構造線性組合實現(xiàn)對多個和校驗實例的批處理。
BatchCheck：基于SumCheck，驗證多個多變量多項式求值的正確性，以提高協(xié)議效率。
盡管Binius與HyperPlonk在協(xié)議設計上有許多相似之處，但Binius在以下3個方面做出改進：
ProductCheck優(yōu)化：在HyperPlonk中，ProductCheck要求分母U在超立方體上處處非零，且乘積必須等于一個特定值；Binius通過將該值特化為1，簡化這一檢查過程，從而降低計算復雜度。
除零問題的處理：HyperPlonk未能充分處理除零情況，導致無法斷言U在超立方體上的非零問題；Binius正確地處理了這一問題，即使在分母為零的情況下，Binius的ProductCheck也能繼續(xù)處理，允許推廣到任意乘積值。
跨列PermutationCheck：HyperPlonk無此功能；Binius支持在多個列之間進行PermutationCheck，這使得Binius能夠處理更復雜的多項式排列情況。
因此，Binius通過對現(xiàn)有PIOPSumCheck機制的改進，提升了協(xié)議的靈活性和效率，尤其在處理更復雜的多變量多項式驗證時，提供了更強的功能支持。這些改進不僅解決了HyperPlonk中的局限性，還為未來基于二進制域的證明系統(tǒng)奠定了基礎。
2.3 PIOP：新的 multilinear shift argument——適用于 boolean hypercube
在Binius協(xié)議中，虛擬多項式的構造和處理是關鍵技術之一，能夠有效地生成和操作從輸入句柄或其他虛擬多項式派生出的多項式。以下是兩個關鍵方法：
Packing：該方法通過將詞典序中相鄰位置的較小元素打包成更大的元素來優(yōu)化操作。Pack運算符針對大小為2κ的塊操作，并將它們組合成高維域中的單個元素。通過多線性擴展（Multilinear Extension, MLE），這個虛擬多項式可以高效地評估和處理，將函數t轉換為另一個多項式，從而提高了計算性能。
移位運算符：移位運算符重新排列塊內的元素，基于給定偏移量o進行循環(huán)移位。該方法適用于大小為2b的塊，每個塊根據偏移量執(zhí)行移位。移位運算符通過檢測函數的支持來進行定義，確保在處理虛擬多項式時保持一致性和效率。評估該構造的復雜度隨塊大小線性增長，特別適用于處理大數據集或布爾超立方體中的高維場景。
2.4 PIOP：改編版Lasso lookup argument——適用于二進制域
Lasso協(xié)議允許證明方承諾一個向量a ∈ Fm，并證明其所有元素均存在于一個預先指定的表t ∈ Fn 中。Lasso解鎖了“查找奇點”（lookup singularities）的概念，并能適用于多線性多項式承諾方案。其效率體現(xiàn)在以下兩個方面：
證明效率：對于大小為n的表中的m次查找，證明方只需承諾m n個域元素。這些域元素很小，均位于集合{0,...,m}中。在基于多次冪運算的承諾方案中，證明方的計算成本為O(m n)次群運算（如橢圓曲線點加），外加證明多線性多項式在布爾超立方體上是否為表元素的求值成本。
無需承諾大表：如果表t是結構化的，則無需對其進行承諾，因此可以處理超大表（如2128或更大）。證明方的運行時間僅與訪問的表條目相關。對于任意整數參數c > 1，證明方的主要成本是證明大小，承諾的域元素為 3·c m c·n1/c 個。這些域元素都是較小的，位于集合{0,...,max{m,n1/c,q} ? 1} 中，其中q為a中的最大值。
Lasso協(xié)議由以下三個組件構成：
大表的虛擬多項式抽象：通過將虛擬多項式組合，實現(xiàn)在大表上的操作，確保在表內進行高效的查找和處理。
小表查找：Lasso的核心是小表查找，作為虛擬多項式協(xié)議的核心構建，使用離線內存檢測驗證一個虛擬多項式在布爾超立方體上的求值是否是另一個虛擬多項式求值的子集。這一查找過程將歸約為多集合檢測的任務。
多集合檢查：Lasso引入虛擬協(xié)議來執(zhí)行多集合檢查，驗證兩個集合的元素是否相等或滿足特定條件。
Binius協(xié)議將Lasso適應于二進制域的操作，假設當前域是一個大特征的素數域（遠大于被查找列的長度）。Binius引入了乘法版本的Lasso協(xié)議，要求證明方和驗證方聯(lián)合遞增協(xié)議的“內存計數”操作，不是通過簡單的加1遞增，而是通過二進制域中的乘法生成元來遞增。然而，這一乘法改編引入了更多的復雜性，與遞增操作不同，乘法生成元并非在所有情況下遞增，在0處存在單一軌道，這可能成為攻擊點。為防止這種潛在的攻擊，證明方必須承諾一個處處非零的讀取計數向量，以確保協(xié)議的安全性。
2.5 PCS：改編版Brakedown PCS——適用于Small-Field
構建BiniusPCS的核心思想是packing。Binius論文中提供了2種基于二進制域的Brakedown多項式承諾方案：一種是采用concatenated code來實例化；另一種采用block-level encoding技術，支持單獨使用Reed-Solomon codes。第二種Brakedown PCS方案，簡化了證明和驗證流程，但proof size要比第一種略大一點，但所帶來的簡化和實現(xiàn)優(yōu)勢，做該取舍是值得的。
Binius多項式承諾主要使用小域多項式承諾與擴展域評估、小域通用構造和塊級編碼與Reed-Solomon碼技術。
小域多項式承諾與擴展域評估：Binius協(xié)議中的承諾是在小域K上的多項式承諾，并在更大的擴展域L/K中進行評估。這種方法確保了每個多線性多項式t(X0,...,X??1)屬于域K[X0,...,X??1]，而評估點可以位于更大擴展域L中。承諾方案專門設計用于小域多項式，并能在擴展域上進行查詢，同時保證承諾的安全性和效率。
小域通用構造：小域通用構造通過定義參數?、域K及其相關的線性塊碼C，確保擴展域L足夠大，以支持安全評估。為了在保持計算效率的同時提高安全性，協(xié)議通過擴展域的特性，以及采用線性塊碼對多項式進行編碼，保證了承諾的穩(wěn)健性。
塊級編碼與Reed-Solomon碼：針對字段比線性塊碼字母表更小的多項式，Binius提出了塊級編碼方案。通過這一方案，即使在小域（如F2）中定義的多項式，也可以使用如F216這樣的大字母表的Reed-Solomon碼高效承諾。Reed-Solomon碼之所以被選中，是因為它具有高效性和最大距離分離特性。該方案通過將消息打包并逐行編碼，之后利用Merkle樹進行承諾，簡化了操作復雜度。塊級編碼允許小域多項式的高效承諾，而不會產生通常與大域相關的高計算開銷，從而使得在F2等小域中承諾多項式成為可能，并在生成證明與驗證中保持計算效率。
3 優(yōu)化思考
為了進一步提升Binius協(xié)議的性能，本文提出了四個關鍵優(yōu)化點：
GKR-based PIOP：針對二進制域乘法運算，借助GKR協(xié)議，來替換Binius論文中的的Lasso Lookup算法，可大幅降低Binius的承諾開銷；
ZeroCheck PIOP優(yōu)化：在Prover與Verifier之間進行計算開銷權衡，使得ZeroCheck操作更加高效；
Sumcheck PIOP優(yōu)化：針對小域Sumcheck的優(yōu)化，進一步減少了小域上的計算負擔；
PCS 優(yōu)化：通過FRI-Binius優(yōu)化，降低證明大小，提高協(xié)議的整體性能。
3.1 GKR-based PIOP：基于GKR的二進制域乘法
Binius論文引入一種基于lookup的方案，旨在實現(xiàn)高效的二進制域乘法運算。通過Lasso lookup argument 改編的二進制域乘法算法依賴于lookups和加法操作的線性關系，這些操作與單個word中的limbs數量成比例。雖然這一算法在某種程度上優(yōu)化了乘法操作，但仍需要與limbs數量線性相關的輔助承諾。
GKR（Goldwasser-Kalai-Rothblum）協(xié)議中的核心思想是，證明方（P）和驗證方（V）針對一個有限域F上的layered算術電路達成一致。該電路的每個節(jié)點有兩個輸入，用于計算所需的函數。為了減少驗證方的計算復雜度，協(xié)議使用SumCheck協(xié)議，將關于電路輸出門值的聲明逐步簡化為更低層的門值聲明，直至最終將聲明簡化到關于輸入的陳述。這樣，驗證方只需檢查電路輸入的正確性即可。
算法，通過將“檢查2個32-bit整數A和B是否滿足 A·B =? C”，轉換為“檢查中(gA)B =? gC 是否成立”，借助GKR協(xié)議大幅減少承諾開銷。與之前的Binius lookup方案相比，基于GKR的二進制域乘法運算只需一個輔助承諾，并且通過減少Sumchecks的開銷，使該算法更加高效，特別是在Sumchecks操作比承諾生成更便宜的場景下。隨著Binius優(yōu)化的推進，基于GKR的乘法運算逐漸成為減少二進制域多項式承諾開銷的有效途徑。
3.2 ZeroCheck PIOP優(yōu)化：Prover與Verifier計算開銷權衡
論文《》在證明方（P）和驗證方（V）之間調整工作量的分配，提出了多種優(yōu)化方案，以權衡開銷。該工作探索了不同的k值配置，使得在證明方和驗證方之間達成了成本的權衡，特別是在減少傳輸數據和降低計算復雜性方面。
減少證明方的數據傳輸：通過將一部分工作轉移給驗證方V，從而降低證明方P發(fā)送的數據量。在第i輪中，證明方P需要向驗證方V發(fā)送vi 1(X)，其中X=0,...,d 1。驗證方V檢查以下等式以驗證數據的正確性
vi = vi 1(0) vi 1(1).
優(yōu)化方法：證明方P可以選擇不發(fā)送vi 1(1)，而是讓驗證方V自行通過以下方式計算出該值
vi 1(1) = vi ? vi 1(0).
此外，在第0輪，誠實的證明方P始終發(fā)送v1(0) = v1(1) = 0，這意味著無需進行任何評估計算，從而顯著減少了計算和傳輸成本，降低至d2n?1CF (d 1)2n?1CG。
減少證明方評估點的數量：在協(xié)議的第i輪中，驗證者在之前的i輪中已經發(fā)送了一個值序列r =(r0,...,ri?1)。當前協(xié)議要求證明者 (P) 發(fā)送多項式
vi 1(X) = ∑ δ?n(α,(r,X,x))C(r,X,x).x∈H ??1
優(yōu)化方法：證明方P發(fā)送以下多項式這兩個函數之間的關系是：
vi(X) = vi′(X)·δi 1((α0,...,αi),(r,X))
其中δ?i 1因為驗證者擁有α和r，所以是完全已知的。這個修改的好處在于vi′(X)的次數比vi(X)少1，這意味著證明者需要評估的點更少。因此，主要的協(xié)議變化發(fā)生在輪次之間的檢查環(huán)節(jié)。
此外，將原本的約束vi = vi 1(0) vi 1(1) 優(yōu)化為 (1?αi)vi′ 1(0) αivi′ 1(1) = vi′(X)。則證明者需要評估和發(fā)送的數據更少，進一步減少傳輸的數據量。計算δ?n?i?1也比計算δ?n更高效。通過這兩項改進，成本降低為大約：2n?1(d? 1)CF 2n?1dCG。在常見的d=3情況下，這些優(yōu)化使成本降低了5/3倍。
代數插值優(yōu)化：對于誠實的證明者，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 < i，次數至多為 1。給定向量 r = (r0,...,ri)，Qj(r,X) 對于所有 j ≤ i 都是多線性的。此外1)Qj(r,X) 是與 C(r,X) 在 Hn?i 上相等的唯一多線性多項式。對于任何 X 和 x ∈ Hn?i?1，可以表示為：
C(r,X,x) ? Qi(r,X,x) = X(X ? 1)Qi 1(r,X,x)
因此，在協(xié)議的每一輪中，僅引入一個新的Q，其評估值可以從C和先前的Q計算得出，實現(xiàn)插值優(yōu)化。
3.3 Sumcheck PIOP優(yōu)化：基于小域的Sumcheck協(xié)議
Binius所實現(xiàn)的STARKs方案，其承諾開銷很低，使得prover瓶頸不再是PCS，而在于sum-check協(xié)議。Ingonyama在2024年提出了針對基于小域的Sumcheck協(xié)議的對應圖2中的Algo3和Algo4算法），并開源了。算法4專注于將Karatsub算法合并到算法3中，以額外的基域乘法為代價來最小化擴域乘法次數，因此當擴域乘法比基域乘法昂貴得多時，算法4的性能會更好。
切換輪次的影響與改進因子
基于小域的Sumcheck協(xié)議的改進集中于切換輪次t的選擇。切換輪次是指從優(yōu)化算法切換回樸素算法的時間點，論文的實驗表明，在最佳切換點時，改進因子達到最大值，隨后呈現(xiàn)拋物線趨勢。如果超過這一切換點，優(yōu)化算法的性能優(yōu)勢減弱，效率下降。這是由于小域上的基域乘法與擴域乘法相比有更高的時間比率，因此在適當時機切換回樸素算法至關重要。
圖2:切換輪次與改進因子關系
對于具體應用，如涉及Cubic Sumcheck（d = 3）的情況，基于小域的Sumcheck協(xié)議相較于樸素算法的改進達到了一個數量級。例如，在基域為GF[2]的情況下，算法4的性能比樸素算法高出近30倍。
基域大小對性能的影響
論文的實驗結果表明，較小的基域（如GF[2]）能夠使優(yōu)化算法顯示出更顯著的優(yōu)勢。這是因為擴展域與基域乘法的時間比率在較小基域上更高，從而優(yōu)化算法在此條件下表現(xiàn)出更高的改進因子。
Karatsuba算法的優(yōu)化收益
Karatsuba算法在提升基于小域的Sumcheck性能方面表現(xiàn)出顯著的效果。對于基域GF[2]，算法3和算法4的峰值改進因子分別為6和30，表明算法4比算法3高效五倍。Karatsuba優(yōu)化不僅提升了運行效率，也優(yōu)化了算法的切換點，分別在算法3的t=5和算法4的t=8達到最佳。
內存效率的提升
基于小域的Sumcheck協(xié)議除了提升運行時間，還在內存效率方面表現(xiàn)出顯著的優(yōu)勢。算法4的內存需求為O(d·t)，而算法3的內存需求為O(2d·t)。當t=8時，算法4僅需0.26MB的內存，而算法3則需67MB來存儲基域的乘積。這使得算法4在內存受限設備上表現(xiàn)出更強的適應性，尤其適用于資源有限的客戶端證明環(huán)境。
3.4 PCS 優(yōu)化：FRI-Binius降低Binius proof size
Binius協(xié)議的一個主要缺陷在于其相對較大的證明大小，隨著見證大小的平方根按O(√N)縮放。與更高效的系統(tǒng)相比，這種平方根大小的證明是一種局限性。相反，對數級（polylogarithmic）證明大小對于實現(xiàn)真正“簡潔”的驗證器至關重要，這在像Plonky3這樣的先進系統(tǒng)中得到了驗證，后者通過FRI等先進技術實現(xiàn)了對數級證明。
論文《》，簡稱為FRI-Binius，實現(xiàn)了二進制域FRI折疊機制，帶來4個方面的創(chuàng)新：
扁平化多項式：初始的多線性多項式被轉換為LCH（低碼高度）新穎多項式基。
子空間消失多項式：用于在系數域上執(zhí)行FRI，并通過加性NTT（數論變換）實現(xiàn)類似FFT的分解。
代數基打包：支持協(xié)議中信息的高效打包，可移除嵌入開銷。
環(huán)交換SumCheck：一種新穎的SumCheck方法，利用環(huán)交換技術優(yōu)化性能。
基于二進制域FRI-Binius的多線性多項式承諾方案（PCS）的核心思想為：FRI-Binius協(xié)議通過將初始的二進制域多線性多項式（定義于F2上）打包為定義在更大域K上的多線性多項式來操作。
在基于二進制域的FRI-BiniusPCS中，過程如下：
承諾階段：對一個?變量的多線性多項式（定義于F2上）的承諾被轉化為對一個打包后的?′變量的多線性多項式（定義于F2128上）的承諾，系數個數因此減少了128倍。
評估階段：證明方和驗證方進行?′輪交叉環(huán)切換SumCheck和FRI交互證明（IOPP）：
–FRI開放證明占據了證明大小的大部分。
–證明方的SumCheck成本類似于常規(guī)大域上的SumCheck成本。
–證明方的FRI成本與常規(guī)大域上的FRI成本相同。
–驗證方接收128個來自F2128的元素，并執(zhí)行128個額外的乘法運算。
借助FRI-Binius，可將Binius證明大小減少一個數量級。這使得Binius的證明大小更加接近最先進的系統(tǒng)，同時保持與二進制域的兼容性。專為二進制域定制的FRI折疊技術，加上代數打包和SumCheck的優(yōu)化，使得Binius能夠在保持高效驗證的同時，生成更加簡潔的證明。
表2:Biniusvs.FRI-BiniusProofSize
表3:Plonky3FRIvs.FRI-Binius
4 小結
Binius的整個價值主張是，可為witnesses使用最小的power-of-two域，因此只需根據所需來選擇域大小。Binius是“使用硬件、軟件、與FPGA中加速的Sumcheck協(xié)議”的協(xié)同設計方案，可以以非常低的內存使用率來快速證明。Halo2和Plonky3等證明系統(tǒng)有4個占用大部分計算量的關鍵步驟：生成witness數據、對witness數據進行承諾、vanishingargument、openingproof。以Plonky3中的Keccak和Binius中的Gr?stl哈希函數為例，二者對應的以上4大關鍵步驟計算量占比情況如圖3所示：
圖3:Smallercommitcost
由此可知，Binius中已基本完全移除了Prover的commit承諾瓶頸，新的瓶頸在于Sumcheck協(xié)議，而Sumcheck協(xié)議中大量多項式evaluations和域乘法等問題，可借助專用硬件高效解決。FRI-Binius方案，為FRI變體，可提供一個非常有吸引力的選擇——從域證明層中消除嵌入開銷，而不會導致聚合證明層的成本激增。當前，Irreducible團隊正在開發(fā)其遞歸層，并宣布與Polygon團隊合作構建Binius-based zkVM;JoltzkVM正從Lasso轉向Binius，以改進其遞歸性能;Ingonyama團隊正在實現(xiàn)FPGA版本的Binius。
鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯(lián)系我們修改或刪除，多謝。
