原文標題：Binius STARKs Analysis and Its Optimization
原文作者：mutourend & lynndell, Bitlayer Labs

1 引言

區別於基於橢圓曲線的SNARKs，可將STARKs 看成是hash-based SNARKs。目前 STARKs 效率低下的一個主要原因是：實際程式中的大多數數值都較小，如 for 迴圈中的索引、真假值、計數器等。然而，為了確保基於 Merkle 樹證明的安全性，使用 Reed-Solomon 編碼對資料進行擴展時，許多額外的冗餘值會佔據整個域，即使原始值本身非常小。為解決此問題，降低網域的大小成為了關鍵策略。

如表1 所示，第1 代STARKs 編碼位寬為252bit，第2 代STARKs 編碼位寬為64bit，第3 代STARKs 編碼位寬為32bit，但32bit 編碼位寬仍存在大量的浪費空間。相較而言，二進位域允許直接對位進行操作，編碼緊湊高效而無任意浪費空間，即第 4 代 STARKs。

表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 tree 承諾時，需做Reed-Solomon 編碼，所用域大小應大於編碼擴充後的大小。

Binius 提出了一個創新的解決方案，分別處理這兩個問題，並透過兩種不同的方式表示相同的資料來實現：首先，使用多變量（具體是多線性）多項式代替單變量多項式，通過其在“超立方體”（hypercubes）上的取值來表示整個計算軌跡；其次，由於超立方體每個維度的長度均為2，因此無法像STARKs 那樣進行標準的Reed-Solomon 擴展，但可以將超立方體視為方形（square），基於該方形進行Reed-Solomon 擴展。這種方法在確保安全性的同時，大幅提升了編碼效率與運算效能。

2 原理解析

目前大多數SNARKs 系統的建置通常包含以下兩部分：

· 資訊理論多項式互動預言機證明（Information-Theoretic Polynomial Interactive Oracle Proof, PIOP）：PIOP 作為證明系統的核心，將輸入的計算關係轉換為可驗證的多項式等式。不同的 PIOP 協議透過與驗證者的交互，允許證明者逐步發送多項式，使得驗證者透過查詢少量多項式的評估結果即可驗證計算是否正確。現有的 PIOP 協定包括：PLONK PIOP、Spartan PIOP 和 HyperPlonk PIOP 等，它們各自對多項式表達式的處理方式有所不同，進而影響整個 SNARK 系統的效能與效率。

· 多項式承諾方案（Polynomial Commitment Scheme, PCS）：多項式承諾方案用於證明PIOP 產生的多項式等式是否成立。 PCS 是一種密碼學工具，透過它，證明者可以承諾某個多項式並在稍後驗證該多項式的評估結果，同時隱藏多項式的其他資訊。常見的多項式承諾方案有 KZG、Bulletproofs、FRI（Fast Reed-Solomon IOPP）和 Brakedown 等。不同的 PCS 具有不同的效能、安全性和適用場景。

根據特定需求，選擇不同的 PIOP 和 PCS，並結合合適的有限域或橢圓曲線，可以建立具有不同屬性的證明系統。例如：

•   Halo2：由 PLONK PIOP 與 Bulletproofs PCS 結合，並基於 Pasta 曲線。 Halo2 設計時，請專注於可擴展性，以及移除 ZCash 協定中的 trusted setup。

•   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 有限域：基於 towers of binary fields 的算術化

塔式二進位域是實現快速可驗證計算的關鍵，主要歸因於兩個面向：高效計算和高效算術化。二進位域本質上支援高度高效的算術操作，使其成為對效能要求敏感的密碼學應用的理想選擇。此外，二元域結構支援簡化的算術化過程，即在二進位域上執行的運算可以以緊湊且易於驗證的代數形式表示。這些特性，加上能夠透過塔結構充分利用其層次化的特性，使得二元域特別適合於諸如 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 Implementations》指出，二進位域在加法和乘法運算中均無需引入進位，且二進位域的平方運算非常高效，因為它遵循(X + Y ) 2 = X2 + Y 2 的簡化規則。

如圖 1 所示，一個 128 位元字串：該字串可以在二進位域的上下文中以多種方式進行解釋。它可以被視為 128 位元二進位域中的一個獨特元素，或被解析為兩個 64 位元塔域元素、四個 32 位元塔域元素、16 個 8 位元塔域元素，或 128 個 F2 域元素。這種表示的靈活性不需要任何計算開銷，只是對位字串的類型轉換（typecast），這是一個非常有趣且有用的屬性。同時，小域元素可以被打包為更大的域元素而不需要額外的計算開銷。 Binius 協定利用了這項特性，以提高運算效率。此外，論文《On Efficient Inversion in Tower Fields of Characteristic Two》探討了在 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：新的multilinear shift argument－適用於boolean hypercube

在Binius協定中，虛擬多項式的建構和處理是關鍵技術之一，能夠有效地產生和操作從輸入句柄或其他虛擬多項式派生出的多項式。以下是兩個關鍵方法：

· Packing：此方法透過將字典序中相鄰位置的較小元素打包成更大的元素來優化操作。 Pack 運算子針對大小為 2κ的區塊操作，並將它們組合成高維域中的單一元素。透過多線性擴展（Multilinear Extension, MLE），這個虛擬多項式可以有效地評估和處理，將函數 t 轉換為另一個多項式，從而提高了計算效能。

· 移位運算子：移位運算子重新排列區塊內的元素，基於給定偏移 o 進行循環移位。此方法適用於大小為 2b 的區塊，每個區塊根據偏移量執行移位。移位運算子透過偵測函數的支援來進行定義，確保在處理虛擬多項式時保持一致性和效率。評估此構造的複雜度隨區塊大小線性增長，特別適用於處理大資料集或布林超立方體中的高維度場景。

2.4 PIOP：改編版Lasso lookup argument－適用於二進位域

Lasso 協議允許證明方承諾一個向量a ∈ Fm，並證明其所有元素均存在於一個預先指定的表t ∈ Fn 中。 Lasso 解鎖了「查找奇點」（lookup singularities）的概念，並能適用於多線性多項式承諾方案。其效率體現在以下兩個方面：

· 證明效率：對於大小為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 協定由以下三個元件構成：

· 大表的虛擬多項式抽象：透過將虛擬多項式組合，實現在大表上的操作，確保在表內進行高效的查找和處理。

· 小表查找：Lasso 的核心是小表查找，作為虛擬多項式協議的核心構建，使用離線內存檢測驗證一個虛擬多項式在布林超立方體上的求值是否為另一個虛擬多項式求值的子集。這個查找過程將歸約為多集合檢測的任務。

· 多集合檢查：Lasso 引入虛擬協定來執行多集合檢查，驗證兩個集合的元素是否相等或滿足特定條件。

Binius 協定將 Lasso 適應於二進位域的操作，假設目前域是一個大特徵的素數域（遠大於被查找列的長度）。 Binius 引入了乘法版本的 Lasso 協議，要求證明方和驗證方聯合遞增協議的「記憶體計數」操作，不是透過簡單的加 1 遞增，而是透過二進位域中的乘法產生元來遞增。然而，這一乘法改編引入了更多的複雜性，與遞增操作不同，乘法生成元並非在所有情況下遞增，在 0 處存在單一軌道，這可能成為攻擊點。為防止這種潛在的攻擊，證明方必須承諾一個處處非零的讀取計數向量，以確保協定的安全性。

2.5 PCS：改編版Brakedown PCS－適用於Small-Field

建置BiniusPCS的核心思想是packing。 Binius 論文中提供了 2 種基於二進位域的 Brakedown 多項式承諾方案：一種是採用 concatenated code 來實例化；另一種採用 block-level encoding 技術，支援單獨使用 Reed-Solomon codes。第二種 Brakedown PCS 方案，簡化了證明和驗證流程，但 proof size 要比第一種略大一點，但所帶來的簡化和實現優勢，做該取捨是值得的。

Binius 多項式承諾主要使用小域多項式承諾與擴展域評估、小域通用構造和區塊級編碼與 Reed-Solomon 碼技術。

小域多項式承諾與擴展域評估：Binius 協議中的承諾是在小域K 上的多項式承諾，並在在更大的擴展域L/K 中進行評估。此方法確保了每個多線性多項式 t(X0,...,Xℓ−1) 屬於域 K[X0,...,Xℓ−1]，而評估點可以位於較大擴展域 L 中。承諾方案專門設計用於小域多項式，並能在擴展域上進行查詢，同時確保承諾的安全性和效率。

小域通用構造：小域通用構造透過定義參數ℓ、域K 及其相關的線性塊碼C，確保擴展域L 足夠大，以支援安全評估。為了在保持運算效率的同時提高安全性，協定透過擴展域的特性，以及採用線性塊碼對多項式進行編碼，保證了承諾的穩健性。

區塊級編碼與 Reed-Solomon 碼：針對欄位比線性區塊碼字母表更小的多項式，Binius 提出了區塊級編碼方案。透過此方案，即使在小域（如 F2）中定義的多項式，也可以使用如 F216 這樣的大字母表的 Reed-Solomon 碼高效承諾。 Reed-Solomon 碼之所以被選中，是因為它具有高效率性和最大距離分離特性。此方案透過將訊息打包並逐行編碼，之後利用 Merkle 樹進行承諾，簡化了操作複雜度。區塊級編碼允許小域多項式的高效承諾，而不會產生通常與大域相關的高計算開銷，從而使得在 F2 等小域中承諾多項式成為可能，並在生成證明與驗證中保持計算效率。

3 最佳化思考

為了進一步提升Binius 協定的效能，本文提出了四個關鍵最佳化點：

1.GKR-based PIOP：針對二進位域乘法運算，借助GKR 協議，來取代Binius 論文中的的Lasso Lookup 演算法，可大幅降低Binius 的承諾開銷；

2.ZeroCheck PIOP 最佳化：在Prover 與Verifier 之間進行計算開銷權衡，使得ZeroCheck 操作更有效率；

3.Sumcheck PIOP 最佳化：針對小域Sumcheck 的最佳化，進一步減少了小域上的計算負擔；

4.PCS 優化：透過FRI-Binius 優化，降低證明大小，提高協議的整體性能。

3.1 GKR-based PIOP：基於GKR 的二進位域乘法

Binius 論文引入一種基於lookup 的方案，旨在實現高效的二進位域乘法運算。透過 Lasso lookup argument 改編的二進位域乘法演算法依賴 lookups 和加法操作的線性關係，這些操作與單一 word 中的 limbs 數量成比例。雖然這項演算法在某種程度上優化了乘法操作，但仍需要與 limbs 數量線性相關的輔助承諾。

GKR（Goldwasser-Kalai-Rothblum）協議中的核心思想是，證明方（P）和驗證方（V）針對一個有限域F 上的layered 算術電路達成一致。此電路的每個節點有兩個輸入，用於計算所需的函數。為了減少驗證方的計算複雜度，協議使用 SumCheck 協議，將關於電路輸出閘值的聲明逐步簡化為更低層的閘值聲明，直至最終將聲明簡化到關於輸入的陳述。這樣，驗證方只需檢查電路輸入的正確性即可。

基於GKR 的整數乘法運算演算法，透過將“檢查2 個32-bit 整數A 和B 是否滿足A·B =? C”，轉換為“檢查中(gA)B =? gC 是否成立”，借助GKR 協議大幅減少承諾開銷。與先前的 Binius lookup 方案相比，基於 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 < 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)

因此，在協議的每一輪中，僅引入一個新的Q，其評估值可以從C 和先前的Q 計算得出，實現插值優化。

3.3 Sumcheck PIOP 最佳化：基於小域的Sumcheck 協定

Binius 所實現的STARKs方案，其承諾開銷很低，使得prover 瓶頸不再是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 proof size

Binius 協定的一個主要缺陷在於其相對較大的證明大小，隨著見證大小的平方根以O(√N) 縮放。與更有效率的系統相比，這種平方根大小的證明是一種限制。相反，對數級（polylogarithmic）證明大小對於實現真正「簡潔」的驗證器至關重要，這在像 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 vs. FRI-Binius Proof Size

表3: Plonky3 FRI vs. FRI-Binius

4 小結

Binius 的整個價值主張是，可為witnesses 使用最小的power-of-two 域，因此只需根據所需來選擇域大小。 Binius 是「使用硬體、軟體、與 FPGA 中加速的 Sumcheck 協定」的協同設計方案，可以以非常低的記憶體使用率來快速證明。 Halo2 和 Plonky3 等證明系統有 4 個佔用大部分計算量的關鍵步驟：產生 witness 資料、對 witness 資料進行承諾、vanishingargument、openingproof。以Plonky3 中的Keccak 與Binius 中的Grøstl 雜湊函數為例，二者對應的以上4 大關鍵步驟計算量佔比情況如圖3 所示：

圖3: Smaller commit cost

由此可知，Binius 中已基本完全移除了Prover 的commit 承諾瓶頸，新的瓶頸在於Sumcheck 協議，而Sumcheck 協議中大量多項式evaluations 和域乘法等問題，可藉助專用硬體高效解決。 FRI-Binius 方案，為 FRI 變體，可提供一個非常有吸引力的選擇——從域證明層中消除嵌入開銷，而不會導致聚合證明層的成本激增。目前，Irreducible 團隊正在開發其遞歸層，並宣布與 Polygon 團隊合作建立 Binius-based zkVM；JoltzkVM 正從 Lasso 轉向 Binius，以改善其遞歸效能；Ingonyama 團隊正在實現 FPGA 版本的 Binius。

參考文獻：

2024.04 Binius Succinct Arguments over Towers of Binary Fields

2024.07 Fri-Binius Polylogarithmic Proofs for Polylogarithmic Proofs for Multilinears over Binary Towers

2024.08 Integer Multiplication in Binius: GKR-based approach

2024.06 zkStudyClub - FRI-Binius: Polylogarithmic Proofs forsferlin - FRI-Binius: Polylogarithmic 4block: 454 ZK11: Binius: a Hardware-Optimized SNARK - Jim Posen

2023.12 Episode 303: A Dive into Binius with Ulvetanna

2024.09 Designing high-performance zblockquote>

2024.09 Designing high-performance zkVMs 。 : Binius - Part 2

2022.10 HyperPlonk, a zk-proof system for ZKEVMs

原文連結

欢迎加入律动 BlockBeats 官方社群：

Telegram 订阅群：https://t.me/theblockbeats

Telegram 交流群：https://t.me/BlockBeats_App

Twitter 官方账号：https://twitter.com/BlockBeatsAsia