Binius STARKs Analysis and Its Optimization

1. Introduction

Distinguished from elliptic curve-based SNARKs, STARKs can be viewed as hash-based SNARKs. One of the main challenges contributing to the current inefficiency of STARKs is that most values in actual programs are relatively small, such as indices in for loops, boolean values, and counters. However, to ensure the security of Merkle tree-based proofs, Reed-Solomon encoding is used to extend data, resulting in many redundant values occupying the entire field, even when the original values themselves are small. Addressing this inefficiency, reducing the field size has become a key strategy.

As shown in Table 1, the first generation of STARKs had a coding width of 252 bits, the second generation 64 bits, and the third generation 32 bits. Despite the reduced coding width in the third generation, there remains significant wasted space. In contrast, binary fields allow for direct bit-level manipulation, enabling compact and efficient encoding with minimal waste. This efficiency is realized in the fourth generation of STARKs.

Table 1: STARKs Derivation Path

In comparison to finite fields such as Goldilocks, BabyBear, and Mersenne31, which have gained attention recently, binary field research dates back to the 1980s. Today, binary fields are widely used in cryptography, with notable examples including:

• Advanced Encryption Standard (AES), based on the
• 𝐹28
• field;
• Galois Message Authentication Code (GMAC), based on the
• 𝐹2128
• field;
• QR codes, which utilize Reed-Solomon encoding based on the
• 𝐹28
• field;
• The original FRI and zk-STARK protocols, as well as the Grøstl hash function, a finalist in the SHA-3 competition, which is based on the
• 𝐹28
• field and is well-suited for recursive hash algorithms.

When smaller fields are used, field extension operations become increasingly important for ensuring security. The binary field used by Binius relies entirely on field extension to guarantee both security and practical usability. Most of the polynomial computations involved in Prover operations do not need to enter the extended field, as they only need to operate in the base field, thereby achieving high efficiency in the small field. However, random point checks and FRI computations must still be performed in a larger extended field to ensure the necessary level of security.

There are two practical challenges when constructing a proof system based on binary fields: First, the field size used for trace representation in STARKs should be larger than the degree of the polynomial. Second, the field size used for the Merkle tree commitment in STARKs must be greater than the size after Reed-Solomon encoding extension.

Binius is an innovative solution to address these two problems by representing the same data in two different ways: First, by using multivariate (specifically multilinear) polynomials instead of univariate polynomials, representing the entire computation trace through their evaluations over “hypercubes.” Second, since each dimension of the hypercube has a length of 2, it is not possible to perform standard Reed-Solomon extensions like in STARKs, but the hypercube can be treated as a square, and a Reed-Solomon extension can be performed based on this square. This method not only ensures security but also greatly enhances encoding efficiency and computational performance.

2. Binius Principles

The construction of most modern SNARK systems typically consists of the following two components:

• Information-Theoretic Polynomial Interactive Oracle Proof (PIOP): As the core of the proof system, PIOP transforms computational relations from the input into verifiable polynomial equations. Different PIOP protocols allow the prover to send polynomials incrementally through interactions with the verifier. This enables the verifier to confirm the correctness of a computation by querying only a small number of polynomial evaluations. Various PIOP protocols, such as PLONK PIOP, Spartan PIOP, and HyperPlonk PIOP, handle polynomial expressions differently, impacting the performance and efficiency of the overall SNARK system.
• Polynomial Commitment Scheme (PCS): The PCS is a cryptographic tool used to prove that the polynomial equations generated by the PIOP are valid. It allows the prover to commit to a polynomial and verify its evaluations without revealing additional information about the polynomial. Common PCS schemes include KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP), and Brakedown, each offering distinct performance characteristics, security guarantees, and applicable scenarios.

By selecting different PIOPs and PCS schemes, and combining them with suitable finite fields or elliptic curves, one can construct proof systems with distinct properties. For example:

• Halo2: Combines PLONK PIOP with Bulletproofs PCS and operates on the Pasta curve. Halo2 is designed with scalability in mind and eliminates the trusted setup previously used in the ZCash protocol.
• Plonky2: Combines PLONK PIOP with FRI PCS and is based on the Goldilocks field. Plonky2 is optimized for efficient recursion.

When designing these systems, the compatibility between the chosen PIOP, PCS, and finite field or elliptic curve is critical to ensuring correctness, performance, and security. These combinations influence the size of the SNARK proof, the efficiency of verification, and determine whether the system can achieve transparency without a trusted setup, as well as support advanced features like recursive proofs or proof aggregation.

Binius combines HyperPlonk PIOP with Brakedown PCS and operates in a binary field. Specifically, Binius incorporates five key technologies to achieve both efficiency and security:

1. Arithmetic based on towers of binary fields: This forms the computational foundation of Binius, allowing for simplified operations within the binary field.
2. HyperPlonk product and permutation checks: Binius adapts HyperPlonk’s product and permutation checks in its PIOP to ensure secure and efficient consistency between variables and their permutations.
3. New multilinear shift argument: This optimization improves the verification of multilinear relationships within small fields, enhancing overall efficiency.
4. Improved Lasso lookup argument: The protocol incorporates a more flexible and secure lookup mechanism with this advanced argument.
5. Small-Field Polynomial Commitment Scheme (PCS): Binius employs a PCS tailored for small fields, reducing the overhead commonly associated with larger fields and enabling an efficient proof system in the binary field.

These innovations enable Binius to offer a compact, high-performance SNARK system, optimized for binary fields while maintaining robust security and scalability.

2.1 Finite Fields: Arithmetic Based on Towers of Binary Fields

Towers of binary fields play a critical role in achieving fast, verifiable computations due to two primary factors: efficient computation and efficient arithmetization. Binary fields inherently support highly efficient arithmetic operations, making them ideal for cryptographic applications sensitive to performance. Moreover, their structure enables a simplified arithmetization process, where operations performed in binary fields can be represented in compact and easily verifiable algebraic forms. These characteristics, combined with the hierarchical structure of towers of binary fields, make them particularly suitable for scalable proof systems like Binius.

The term “canonical” refers to the unique and direct representation of elements in a binary field. For example, in the most basic binary field $\mathbb{F}2

,𝑎𝑛𝑦𝑘−𝑏𝑖𝑡𝑠𝑡𝑟𝑖𝑛𝑔𝑐𝑎𝑛𝑏𝑒𝑑𝑖𝑟𝑒𝑐𝑡𝑙𝑦𝑚𝑎𝑝𝑝𝑒𝑑𝑡𝑜𝑎𝑘−𝑏𝑖𝑡𝑏𝑖𝑛𝑎𝑟𝑦𝑓𝑖𝑒𝑙𝑑𝑒𝑙𝑒𝑚𝑒𝑛𝑡.𝑇ℎ𝑖𝑠𝑑𝑖𝑓𝑓𝑒𝑟𝑠𝑓𝑟𝑜𝑚𝑝𝑟𝑖𝑚𝑒𝑓𝑖𝑒𝑙𝑑𝑠,𝑤ℎ𝑖𝑐ℎ𝑑𝑜𝑛𝑜𝑡𝑜𝑓𝑓𝑒𝑟𝑠𝑢𝑐ℎ𝑎𝑐𝑎𝑛𝑜𝑛𝑖𝑐𝑎𝑙𝑟𝑒𝑝𝑟𝑒𝑠𝑒𝑛𝑡𝑎𝑡𝑖𝑜𝑛𝑤𝑖𝑡ℎ𝑖𝑛𝑎𝑔𝑖𝑣𝑒𝑛𝑛𝑢𝑚𝑏𝑒𝑟𝑜𝑓𝑏𝑖𝑡𝑠.𝐴𝑙𝑡ℎ𝑜𝑢𝑔ℎ𝑎32−𝑏𝑖𝑡𝑝𝑟𝑖𝑚𝑒𝑓𝑖𝑒𝑙𝑑𝑐𝑎𝑛𝑓𝑖𝑡𝑤𝑖𝑡ℎ𝑖𝑛32𝑏𝑖𝑡𝑠,𝑛𝑜𝑡𝑒𝑣𝑒𝑟𝑦32−𝑏𝑖𝑡𝑠𝑡𝑟𝑖𝑛𝑔𝑐𝑎𝑛𝑢𝑛𝑖𝑞𝑢𝑒𝑙𝑦𝑐𝑜𝑟𝑟𝑒𝑠𝑝𝑜𝑛𝑑𝑡𝑜𝑎𝑓𝑖𝑒𝑙𝑑𝑒𝑙𝑒𝑚𝑒𝑛𝑡,𝑤ℎ𝑒𝑟𝑒𝑎𝑠𝑏𝑖𝑛𝑎𝑟𝑦𝑓𝑖𝑒𝑙𝑑𝑠𝑝𝑟𝑜𝑣𝑖𝑑𝑒𝑡ℎ𝑖𝑠𝑜𝑛𝑒−𝑡𝑜−𝑜𝑛𝑒𝑚𝑎𝑝𝑝𝑖𝑛𝑔.𝐼𝑛𝑝𝑟𝑖𝑚𝑒𝑓𝑖𝑒𝑙𝑑𝑠

\mathbb{F}_p$ , common reduction methods include Barrett reduction , Montgomery reduction , as well as specialized reduction methods for certain finite fields like Mersenne-31 or Goldilocks-64 . In binary fields $\mathbb{F}{2^k}$ , common reduction methods include special reduction (as used in AES), Montgomery reduction (as used in POLYVAL), and recursive reduction (as used in Tower fields). The paper Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations notes that binary fields do not require carry propagation in addition or multiplication, and squaring in binary fields is highly efficient due to the simplification rule

(𝑋+𝑌)2=𝑋2+𝑌2

.

Figure 1. Towers of Binary Field

As shown in Figure 1, a 128-bit string can be interpreted in multiple ways within the context of a binary field. It can be viewed as a unique element in the 128-bit binary field, or it can be parsed as two 64-bit tower field elements, four 32-bit tower field elements, sixteen 8-bit tower field elements, or 128 elements of

𝐹2

. This flexibility in representation incurs no computational overhead, as it is merely a typecast of the bit string. This is a very interesting and useful property, as smaller field elements can be packed into larger field elements without additional computational cost. The Binius protocol leverages this property to enhance computational efficiency. Furthermore, the paper On Efficient Inversion in Tower Fields of Characteristic Two explores the computational complexity of multiplication, squaring, and inversion in

𝑛

-bit tower binary fields (decomposable into

𝑚

-bit subfields).

2.2 PIOP: Adapted HyperPlonk Product and Permutation Check — Suitable for Binary Fields

The PIOP design in the Binius protocol draws inspiration from HyperPlonk and incorporates a series of core checks to verify the correctness of polynomials and multivariate sets. These checks are essential for ensuring the integrity of computations within the proof system, especially when operating over binary fields. The key checks include:

1. GateCheck: Ensures that the private witness
2. 𝜔
3. and public input
4. 𝑥
5. satisfy the circuit operation relation
6. 𝐶(𝑥,𝜔)=0
7. , verifying the correct execution of the circuit.
8. PermutationCheck: Verifies that the evaluation results of two multivariate polynomials
9. 𝑓
10. and
11. 𝑔
12. on the Boolean hypercube form a permutation relation
13. 𝑓(𝑥)=𝑓(𝜋(𝑥))
14. , ensuring consistency between polynomial variables.
15. LookupCheck: Checks if the evaluation of a polynomial is within a given lookup table, i.e.,
16. 𝑓(𝐵𝜇)⊆𝑇(𝐵𝜇)
17. , ensuring that certain values fall within a specified range.
18. MultisetCheck: Confirms whether two multivariate sets are equal, i.e., ${(x{1,i},x{2,i})}{i \in H} = {(y{1,i},y{2,i})}{i \in H}$, ensuring consistency between different sets.
19. ProductCheck: Ensures that the evaluation of a rational polynomial on the Boolean hypercube equals a declared value, i.e.,
20. ∏𝑥∈𝐻𝜇𝑓(𝑥)=𝑠
21. , confirming the correctness of the polynomial product.
22. ZeroCheck: Verifies whether a multivariate polynomial evaluates to zero at any point on the Boolean hypercube, i.e.,
23. ∏𝑥∈𝐻𝜇𝑓(𝑥)=0
24. for all
25. 𝑥∈𝐵𝜇
26. , ensuring proper distribution of zeros in the polynomial.
27. SumCheck: Confirms whether the sum of the evaluations of a multivariate polynomial equals the declared value, i.e.,
28. ∑𝑥∈𝐻𝜇𝑓(𝑥)=𝑠
29. . By reducing the evaluation of multivariate polynomials to univariate polynomial evaluation, it lowers the verifier’s computational complexity. SumCheck also allows for batching, which constructs linear combinations using random numbers to batch-process multiple instances.
30. BatchCheck: An extension of SumCheck, it verifies the correctness of multiple multivariate polynomial evaluations, increasing protocol efficiency.

While Binius and HyperPlonk share several similarities in their protocol designs, Binius introduces the following key improvements:

1. ProductCheck Optimization: In HyperPlonk, ProductCheck requires the denominator
2. 𝑈
3. to be non-zero across the entire hypercube, and that the product matches a specific value. Binius simplifies this check by setting the product value to 1, reducing the overall computational complexity.
4. Handling of Zero-Division Issues: HyperPlonk does not effectively address zero-division problems, making it challenging to guarantee that
5. 𝑈
6. remains non-zero over the hypercube. Binius resolves this by handling zero-division scenarios appropriately, enabling ProductCheck to function even when the denominator is zero, allowing for extensions to arbitrary product values.
7. Cross-Column PermutationCheck: HyperPlonk lacks support for cross-column permutation checks. Binius addresses this limitation by introducing support for cross-column PermutationCheck, enabling the protocol to manage more complex polynomial permutations across multiple columns.

Thus, Binius enhances the flexibility and efficiency of the protocol by improving the existing PIOP SumCheck mechanism, particularly by providing stronger functionality for verifying more complex multivariate polynomials. These improvements not only address the limitations of HyperPlonk but also lay the foundation for future proof systems based on binary fields.

2.3 PIOP: A New Multilinear Shift Argument—Applicable to Boolean Hypercube

In the Binius protocol, the manipulation and construction of virtual polynomials play a crucial role in enabling efficient polynomial handling. Two main techniques are employed for these operations:

• Packing :The packing method optimizes the handling of smaller elements by grouping them together in a larger domain. Specifically, elements adjacent in lexicographic order are packed into larger blocks, typically of size
• 2𝜅
• . By leveraging Multilinear Extension (MLE), the packed elements are transformed into a new virtual polynomial, which can then be evaluated and processed efficiently. This method enhances the performance of operations on the Boolean hypercube by restructuring the function
• 𝑡
• into a computationally efficient form.
• Shift Operator : The shift operator rearranges elements within a block by cyclically shifting them based on a given offset
• 𝑜
• . This shift applies to blocks of size
• 2𝑏
• , ensuring that all elements in a block are shifted uniformly according to the predefined offset. This operator is particularly useful when dealing with virtual polynomials in high-dimensional spaces, as its complexity increases linearly with the block size, making it an ideal technique for large datasets or complex Boolean hypercube computations.

2.4 PIOP: An Adapted Lasso Lookup Argument—Applicable to Binary Fields

The Lasso protocol in Binius offers a highly efficient method for proving that elements in a vector

𝑎∈𝐹𝑚

are contained within a predefined table

𝑡∈𝐹𝑛

. This lookup argument introduces the concept of “Lookup Singularity” and is well-suited for multilinear polynomial commitment schemes. The efficiency of Lasso is highlighted in two major aspects:

• Proof Efficiency : When conducting
• 𝑚
• lookups in a table of size
• 𝑛
• , the prover only needs to commit to
• 𝑚+𝑛
• small field elements, with the field size drawn from the set
• 0,…,𝑚
• . In cryptographic schemes that rely on exponentiation, the prover’s cost is
• 𝑂(𝑚+𝑛)
• group operations (e.g., elliptic curve point additions). This efficiency comes in addition to the cost of verifying whether a multilinear polynomial evaluated on the Boolean hypercube matches a table element.
• No Commitment to Large Tables : If the table
• 𝑡
• is structured, Lasso does not require a direct commitment to the table, making it possible to handle very large tables (e.g.,
• 2128
• or more). The prover’s runtime depends solely on the specific entries accessed in the table. For any integer parameter
• 𝑐>1
• , the main cost involves proof size, which grows as
• 3⋅𝑐⋅𝑚+𝑐⋅𝑛1/𝑐
• committed field elements. These elements are also small, drawn from the set
• 0,…,max𝑚,𝑛1/𝑐,𝑞−1
• , where
• 𝑞
• is the largest value in the vector
• 𝑎
• .

The Lasso protocol consists of three core components:

1. Virtual Polynomial Abstraction of Large Tables : The Lasso protocol combines virtual polynomials to enable efficient lookups and operations on large tables, ensuring scalability without performance degradation.
2. Small Table Lookup : At the heart of Lasso lies the small table lookup, which verifies whether a virtual polynomial evaluated on a Boolean hypercube is a subset of another virtual polynomial’s evaluations. This process is akin to offline memory detection and boils down to a multiset detection task.
3. Multiset Check : The protocol also incorporates a virtual mechanism to perform multiset checks, ensuring that two sets of elements either match or fulfill predefined conditions.

The Binius protocol adapts Lasso for binary field operations, assuming the current field is a prime field of large characteristic (much larger than the length of the column being looked up). Binius introduces a multiplicative version of the Lasso protocol, requiring the prover and verifier to increment the protocol’s “memory counter” operation not simply by adding 1 but by incrementing using a multiplicative generator within the binary field. However, this multiplicative adaptation introduces additional complexity: unlike an additive increment, the multiplicative generator does not increment in all cases, instead having a single orbit at 0, which may present an attack vector. To mitigate this potential attack, the prover must commit to a read counter vector that is non-zero everywhere to ensure protocol security.

2.5 PCS: Adapted Brakedown PCS—Applicable to Small Fields

The core idea behind constructing the Binius PCS (Polynomial Commitment Scheme) is packing. The Binius paper presents two Brakedown PCS schemes based on binary fields: one instantiated using concatenated codes, and another using block-level encoding, which supports the standalone use of Reed-Solomon codes. The second Brakedown PCS scheme simplifies the proof and verification process, though it produces a slightly larger proof size than the first one; however, this trade-off is worthwhile due to the simplification and implementation benefits it offers.

The Binius polynomial commitment primarily utilizes small-field polynomial commitment with evaluations in an extended field, small-field universal construction, and block-level encoding with Reed-Solomon code techniques.

Small-Field Polynomial Commitment with Extended Field Evaluation In the Binius protocol, polynomial commitments are performed over a small field

𝐾

, with evaluations taking place in an extended field

𝐿/𝐾

. This technique ensures that a multilinear polynomial

𝑡(𝑋0,…,𝑋ℓ−1)

belongs to the domain

𝐾[𝑋0,…,𝑋ℓ−1]

, while the evaluation points are in the larger field

𝐿

. This commitment structure enables efficient queries within the extended field, balancing security and computational efficiency.

Small-Field Universal Construction This construction defines key parameters like the field

𝐾

, its dimension

ℓ

, and the associated linear block code

𝐶

, while ensuring that the extended field

𝐿

is large enough for secure evaluations. By leveraging properties of the extended field, Binius achieves robust commitments through linear block codes, maintaining a balance between computational efficiency and security.

Block-Level Encoding with Reed-Solomon Codes For polynomials defined over small fields like $\mathbb{F}2

,𝑡ℎ𝑒𝐵𝑖𝑛𝑖𝑢𝑠𝑝𝑟𝑜𝑡𝑜𝑐𝑜𝑙𝑒𝑚𝑝𝑙𝑜𝑦𝑠𝑏𝑙𝑜𝑐𝑘−𝑙𝑒𝑣𝑒𝑙𝑒𝑛𝑐𝑜𝑑𝑖𝑛𝑔𝑢𝑠𝑖𝑛𝑔𝑅𝑒𝑒𝑑−𝑆𝑜𝑙𝑜𝑚𝑜𝑛𝑐𝑜𝑑𝑒𝑠.𝑇ℎ𝑖𝑠𝑠𝑐ℎ𝑒𝑚𝑒𝑎𝑙𝑙𝑜𝑤𝑠𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑡𝑐𝑜𝑚𝑚𝑖𝑡𝑚𝑒𝑛𝑡𝑜𝑓𝑠𝑚𝑎𝑙𝑙−𝑓𝑖𝑒𝑙𝑑𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙𝑠𝑏𝑦𝑒𝑛𝑐𝑜𝑑𝑖𝑛𝑔𝑡ℎ𝑒𝑚𝑟𝑜𝑤−𝑏𝑦−𝑟𝑜𝑤𝑖𝑛𝑡𝑜𝑙𝑎𝑟𝑔𝑒𝑟𝑓𝑖𝑒𝑙𝑑𝑠(𝑠𝑢𝑐ℎ𝑎𝑠

\mathbb{F}{2^{16}}$ ), utilizing the efficiency and maximum distance separable properties of Reed-Solomon codes. After encoding, these rows are committed using a Merkle tree, which simplifies the operational complexity of small-field polynomial commitments. This approach allows for the efficient handling of polynomials in small fields without the computational burden usually associated with larger fields.

3. Binius Optimizations

To further improve performance, Binius incorporates four major optimizations:

1. GKR-based PIOP : The GKR (Goldreich-Kalai-Rothblum) protocol is used to replace the Lasso Lookup algorithm in binary field multiplication, significantly reducing the overhead in the commitment process.
2. ZeroCheck PIOP Optimization : This optimization addresses the balance between the Prover and Verifier’s computational costs, making the ZeroCheck operation more efficient by distributing workload more effectively.
3. Sumcheck PIOP Optimization : By optimizing the small-field Sumcheck process, Binius reduces the overall computational burden when operating over small fields.
4. PCS Optimization : Using FRI-Binius (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) optimization, Binius reduces proof size and enhances protocol performance, improving overall efficiency in both proof generation and verification.

3.1 GKR-based PIOP: Binary Field Multiplication Using GKR

In the original Binius protocol, binary field multiplication is handled through a lookup-based scheme, which ties multiplication to linear addition operations based on the number of limbs in a word. While this method optimizes binary multiplication to an extent, it still introduces auxiliary commitments linearly related to the number of limbs. By adopting a GKR-based approach, the Binius protocol can significantly reduce the number of required commitments, leading to further efficiency in binary field multiplication operations.

The core idea of the GKR (Goldwasser-Kalai-Rothblum) protocol is to achieve agreement between the Prover (P) and Verifier (V) over a layered arithmetic circuit on a finite field

𝐹

. Each node in this circuit has two inputs for computing the required function. To reduce the Verifier’s computational complexity, the protocol employs the SumCheck protocol, which progressively reduces claims about the circuit’s output gate values to lower-layer gate values, eventually simplifying the claims to statements about the inputs. This way, the Verifier only needs to verify the correctness of the circuit inputs.

The GKR-based integer multiplication algorithm in Binius transforms the check of whether two 32-bit integers

𝐴

and

𝐵

satisfy

𝐴⋅𝐵=?𝐶

into verifying whether

(𝑔𝐴)𝐵=?𝑔𝐶

holds in

𝐹264∗

. This transformation, combined with the GKR protocol, significantly reduces the overhead associated with polynomial commitments. Compared to the previous Binius lookup-based scheme, the GKR-based multiplication approach requires only one auxiliary commitment and reduces the cost of SumChecks, making the algorithm more efficient, especially in cases where SumChecks are more economical than additional commitments. This method is becoming a promising solution for minimizing binary field polynomial commitment costs as Binius optimizations progress.

3.2 ZeroCheck PIOP Optimization: Balancing Computational Costs between Prover and Verifier

The paper Some Improvements for the PIOP for ZeroCheck proposes strategies to balance computational costs between the Prover (P) and Verifier (V), focusing on reducing data transmission and computational complexity. Below are key optimization techniques:

• Reducing Prover’s Data Transmission

By transferring some of the computational burden to the Verifier, the Prover’s data transmission can be minimized. For instance, in round

𝑖

, the Prover sends

𝑣𝑖+1(𝑋)

for

𝑋=0,…,𝑑+1

, and the Verifier checks whether

𝑣𝑖=𝑣𝑖+1(0)+𝑣𝑖+1(1)

holds.

Optimization: The Prover can avoid sending

𝑣𝑖+1(1)

, as the Verifier can compute it as

𝑣𝑖+1(1)=𝑣𝑖−𝑣𝑖+1(0)

.

In the initial round, the Prover sends

𝑣1(0)=𝑣1(1)=0

, eliminating some evaluation calculations, which reduces both computational and transmission costs to

𝑑2𝑛−1𝐶𝐹+(𝑑+1)2𝑛−1𝐶𝐺

.

• Reducing the Number of Evaluation Points for the Prover

During round

𝑖

, the Prover must send

𝑣𝑖+1(𝑋)

, calculated as

𝑣𝑖+1(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼,(𝑟,𝑋,𝑥))𝐶(𝑟,𝑋,𝑥)

.

Optimization: Instead, the Prover can send

𝑣𝑖+1′(𝑋)=∑𝑥∈𝐻𝑛−𝑖−1𝛿^𝑛(𝛼𝑖+1,…,𝛼𝑛−1,𝑥)𝐶(𝑟,𝑋,𝑥),

where $v_i(X) = v_i’(X) \cdot \hat{\delta}{i+1}((\alpha_0, \dots, \alpha_i), (r, X))

.𝐴𝑠𝑡ℎ𝑒𝑉𝑒𝑟𝑖𝑓𝑖𝑒𝑟ℎ𝑎𝑠𝑎𝑐𝑐𝑒𝑠𝑠𝑡𝑜

\alpha

𝑎𝑛𝑑

r

,𝑡ℎ𝑒𝑑𝑒𝑔𝑟𝑒𝑒𝑜𝑓

v_i’(X)

𝑖𝑠𝑙𝑜𝑤𝑒𝑟𝑡ℎ𝑎𝑛𝑡ℎ𝑎𝑡𝑜𝑓

v_i(X)

,𝑟𝑒𝑑𝑢𝑐𝑖𝑛𝑔𝑡ℎ𝑒𝑟𝑒𝑞𝑢𝑖𝑟𝑒𝑑𝑒𝑣𝑎𝑙𝑢𝑎𝑡𝑖𝑜𝑛𝑝𝑜𝑖𝑛𝑡𝑠.𝑇ℎ𝑒𝑖𝑛𝑡𝑒𝑟−𝑟𝑜𝑢𝑛𝑑𝑐ℎ𝑒𝑐𝑘𝑐𝑎𝑛𝑡ℎ𝑒𝑛𝑏𝑒𝑠𝑖𝑚𝑝𝑙𝑖𝑓𝑖𝑒𝑑𝑎𝑠

(1 - \alphai)v{i+1}’(0) + \alpha_i v{i+1}’(1) = v_i’(X),

𝑡ℎ𝑒𝑟𝑒𝑏𝑦𝑙𝑜𝑤𝑒𝑟𝑖𝑛𝑔𝑑𝑎𝑡𝑎𝑡𝑟𝑎𝑛𝑠𝑚𝑖𝑠𝑠𝑖𝑜𝑛𝑛𝑒𝑒𝑑𝑠𝑎𝑛𝑑𝑒𝑛ℎ𝑎𝑛𝑐𝑖𝑛𝑔𝑒𝑓𝑓𝑖𝑐𝑖𝑒𝑛𝑐𝑦.𝑊𝑖𝑡ℎ𝑡ℎ𝑒𝑠𝑒𝑖𝑚𝑝𝑟𝑜𝑣𝑒𝑚𝑒𝑛𝑡𝑠,𝑡ℎ𝑒𝑜𝑣𝑒𝑟𝑎𝑙𝑙𝑐𝑜𝑠𝑡𝑖𝑠𝑎𝑝𝑝𝑟𝑜𝑥𝑖𝑚𝑎𝑡𝑒𝑙𝑦

2^{n-1}(d - 1)C_F + 2^{n-1}dC_G.

𝐹𝑜𝑟

d = 3$ , these optimizations yield a cost reduction by a factor of 5/3.

• Algebraic Interpolation Optimization

For an honest Prover, the polynomial

𝐶(𝑥0,…,𝑥𝑛−1)

is zero on

𝐻𝑛

and can be expressed as

𝐶(𝑥0,…,𝑥𝑛−1)=∑𝑖=0𝑛−1𝑥𝑖(𝑥𝑖−1)𝑄𝑖(𝑥0,…,𝑥𝑛−1)

. Where

𝑄𝑖

is computed through ordered polynomial division, starting from

𝑅𝑛=𝐶

. Sequential division by

𝑥𝑖(𝑥𝑖−1)

computes

𝑄𝑖

and

𝑅𝑖

, with

𝑅0

representing the multilinear extension of

𝐶

on

𝐻𝑛

, assumed to be zero.

Analyzing the Degrees of

𝑄𝑖

. For

𝑗>𝑖

,

𝑄𝑗

retains the same degree in

𝑥𝑖

as

𝐶

. For

𝑗=𝑖

, the degree is reduced by 2, and for

𝑗<𝑖

, the degree is at most 1. Given a vector

𝑟=(𝑟0,…,𝑟𝑖)

,

𝑄𝑗(𝑟,𝑋)

is multilinear for all

𝑗≤𝑖

. Moreover,

𝑄𝑖(𝑟,𝑋)=∑𝑗=0𝑖𝑟𝑗(𝑟𝑗−1)𝑄𝑗(𝑟,𝑋)

is the unique multilinear polynomial matching

𝐶(𝑟,𝑋)

on

𝐻𝑛−𝑖

. For any

𝑋

and

𝑥∈𝐻𝑛−𝑖−1

, it can be represented as

𝐶(𝑟,𝑋,𝑥)−𝑄𝑖(𝑟,𝑋,𝑥)=𝑋(𝑋−1)𝑄𝑖+1(𝑟,𝑋,𝑥).

Thus, during each round of the protocol, a new

𝑄

is introduced, and its evaluation can be derived from

𝐶

and the previous

𝑄

, allowing for interpolation optimization.

3.3 Sumcheck PIOP Optimization: Small-Field Sumcheck Protocol

In the STARKs protocol implemented by Binius, the primary bottleneck for the prover is often the sum-check protocol rather than the Polynomial Commitment Scheme (PCS), due to the low commitment cost.

Figure 2. Relationship between Switchover round and Factor improvement

In 2024, Ingonyama proposed improvements for small-field-based Sumcheck protocols, focusing on Algorithms 3 and 4. These improvements were implemented and made publicly available here. Algorithm 4 incorporates the Karatsuba algorithm into Algorithm 3, reducing the number of extension field multiplications in exchange for more base field multiplications. This approach is more efficient when extension field multiplications are more expensive than base field ones.

1. Impact of Switchover Rounds and Improvement Factors The small-field Sumcheck protocol’s optimization hinges on selecting the optimal switchover round

𝑡

, which marks when the protocol reverts from the optimized version to the naive algorithm. Experiments indicate that the improvement factor peaks at the optimal switchover point and then follows a parabolic trend. When this point is exceeded, efficiency diminishes because the ratio between base field and extension field multiplications is greater in smaller fields, necessitating a timely reversion to the naive algorithm.

For certain applications, like the Cubic Sumcheck (

𝑑=3

), the small-field Sumcheck protocol delivers an order-of-magnitude improvement over the naive approach. For instance, in the base field

𝐺𝐹[2]2. Impact of Base Field Size on Performance Smaller base fields (e.g.,

, Algorithm 4 outperforms the naive algorithm by nearly 30 times.

𝐺𝐹[2]

) significantly enhance the efficiency of the optimized algorithm due to the larger disparity between the costs of extension field and base field multiplications. This leads to a more substantial improvement factor for the optimized algorithm.

1. Optimization Gains from the Karatsuba Algorithm The Karatsuba algorithm plays a crucial role in improving the performance of the small-field Sumcheck protocol. For a base field of

𝐺𝐹[2]

, Algorithm 4 achieves peak improvement factors of 6 for Algorithm 3 and 30 for Algorithm 4, indicating that Algorithm 4 is five times more efficient than Algorithm 3. The Karatsuba algorithm enhances runtime efficiency and optimizes the switchover point for both algorithms, with optimal points at

𝑡=5

for Algorithm 3 and

𝑡=8

for Algorithm 4.

1. Memory Efficiency Improvements The small-field Sumcheck protocol also boosts memory efficiency. Algorithm 4 requires

𝑂(𝑑⋅𝑡)

memory, while Algorithm 3 needs

𝑂(2𝑑⋅𝑡)

memory. For

𝑡=8

, Algorithm 4 uses just 0.26 MB of memory, compared to the 67 MB required by Algorithm 3. This makes Algorithm 4 particularly suitable for memory-constrained environments, such as client-side proving with limited resources.

3.4 PCS Optimization: FRI-Binius Reducing Binius Proof Size

One of the main challenges of the Binius protocol is its relatively large proof size, which scales with the square root of the witness size at

𝑂(𝑁)

. This square-root scaling limits its competitiveness when compared to systems offering more succinct proofs. In contrast, polylogarithmic proof sizes, as achieved by advanced systems like Plonky3 through techniques such as FRI, are essential for ensuring truly “succinct” verifiers. The FRI-Binius optimization aims to reduce Binius’ proof size and improve its overall performance in comparison to more efficient systems.

The paper Polylogarithmic Proofs for Multilinears over Binary Towers, referred to as FRI-Binius, introduces a novel binary-field-based FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) folding mechanism with four key innovations:

• Flattened Polynomials: Transforms the initial multilinear polynomial into a Low Code Height (LCH) polynomial basis for optimized computation.
• Subspace Vanishing Polynomials: Utilizes these polynomials in conjunction with an additive NTT (Number Theoretic Transform) to enable FFT-like decomposition, optimizing operations over the coefficient field.
• Algebraic Basis Packing: Facilitates efficient data packing, minimizing the protocol’s overhead related to embedding.
• Ring-Switching SumCheck: A new SumCheck optimization using ring-switching techniques to further enhance performance.

Core Process of FRI-Binius Multilinear Polynomial Commitment Scheme (PCS)

The FRI-Binius protocol optimizes binary-field multilinear polynomial commitment schemes (PCS) by transforming the initial multilinear polynomial, defined over the binary field

𝐹2

, into a multilinear polynomial over a larger field

𝐾

.

1. Commitment Phase The commitment phase transforms an
2. ℓ
3. -variable multilinear polynomial (over $\mathbb{F}2
4. )𝑖𝑛𝑡𝑜𝑎𝑐𝑜𝑚𝑚𝑖𝑡𝑚𝑒𝑛𝑡𝑓𝑜𝑟𝑎𝑝𝑎𝑐𝑘𝑒𝑑
5. \ell’
6. −𝑣𝑎𝑟𝑖𝑎𝑏𝑙𝑒𝑚𝑢𝑙𝑡𝑖𝑙𝑖𝑛𝑒𝑎𝑟𝑝𝑜𝑙𝑦𝑛𝑜𝑚𝑖𝑎𝑙(𝑜𝑣𝑒𝑟
7. \mathbb{F}{2^{128}}$ ). This process reduces the number of coefficients by a factor of 128, allowing for more efficient proof generation.
8. Evaluation Phase In this phase, the prover and verifier execute
9. ℓ′
10. rounds of a cross-ring switching SumCheck protocol combined with FRI interactive oracle proofs of proximity (IOPP). Key details include:
    • FRI Opening Proofs: These make up the majority of the proof size and are handled similarly to standard FRI proofs over large fields.
    • Prover’s SumCheck Cost: Comparable to the cost of executing SumCheck in a large field.
    • Prover’s FRI Cost: Matches the standard FRI costs seen in large-field implementations.
    • Verifier’s Operations: The verifier receives 128 elements from
    • 𝐹2128
    • and performs 128 additional multiplications, allowing for efficient verification.

Benefits of FRI-Binius

By applying this method, Binius is able to reduce its proof size by an order of magnitude, bringing it closer to the performance of state-of-the-art cryptographic systems, while remaining compatible with binary fields. The FRI folding method, optimized for binary fields, combined with algebraic packing and SumCheck optimizations, helps Binius generate smaller proofs without compromising verification efficiency.

This transformation marks a significant step toward improving proof size in Binius, ensuring that it becomes more competitive with other cutting-edge systems, particularly those focused on polylogarithmic proof sizes.

Table 2: Binius vs. FRI-Binius Proof Size Comparison

Table 3: Plonky3 FRI vs. FRI-Binius Comparison

4. Conclusion

The entire value proposition of Binius lies in its ability to use the smallest power-of-two field size for witnesses, selecting the field size as needed. Binius is a co-design scheme for “hardware, software, and FPGA-accelerated Sumcheck protocols,” enabling fast proofs with very low memory usage.

Proof systems like Halo2 and Plonky3 involve four key computationally intensive steps: generating witness data, committing to the witness data, performing a vanishing argument, and generating the opening proof.

For example, with the Keccak hash function in Plonky3 and the Grøstl hash function in Binius, the computational distribution for these four key steps is illustrated in Figure 3.

Figure 3. Smaller Commit Cost

This comparison shows that Binius has essentially eliminated the prover’s commitment bottleneck. The new bottleneck is the Sumcheck protocol, where issues such as numerous polynomial evaluations and field multiplications can be efficiently addressed with specialized hardware.

The FRI-Binius scheme, a variant of FRI, offers a highly attractive option by removing embedding overhead from the field proof layer without causing a significant cost increase in the aggregated proof layer.

Currently, the Irreducible team is developing its recursive layer and has announced a partnership with the Polygon team to build a Binius-based zkVM; the Jolt zkVM is transitioning from Lasso to Binius to enhance its recursive performance; and the Ingonyama team is implementing an FPGA version of Binius.

References

1. 2024.04 Binius Succinct Arguments over Towers of Binary Fields
2. 2024.07 Fri-Binius Polylogarithmic Proofs for Multilinears over Binary Towers
3. 2024.08 Integer Multiplication in Binius: GKR-based approach
4. 2024.06 zkStudyClub - FRI-Binius: Polylogarithmic Proofs for Multilinears over Binary Towers
5. 2024.04 ZK11: Binius: a Hardware-Optimized SNARK - Jim Posen
6. 2023.12 Episode 303: A Dive into Binius with Ulvetanna
7. 2024.09 Designing high-performance zkVMs
8. 2024.07 Sumcheck and Open-Binius
9. 2024.04 Binius: highly efficient proofs over binary fields
10. 2023.12 SNARKs on binary fields: Binius - Part 1
11. 2024.06 SNARKs on binary fields: Binius - Part 2
12. @espressosys/hyperplonk-a-zk-proof-system-for-zkevms-d45fd077bfba">2022.10 HyperPlonk, a zk-proof system for ZKEVMs

Disclaimer：

1. This article is reprinted from [bitlayer]. All copyrights belong to the original author [lynndell]. If there are objections to this reprint, please contact the Gate Learn team, and they will handle it promptly.
2. Liability Disclaimer: The views and opinions expressed in this article are solely those of the author and do not constitute any investment advice.
3. Translations of the article into other languages are done by the Gate Learn team. Unless mentioned, copying, distributing, or plagiarizing the translated articles is prohibited.