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