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:
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.
The construction of most modern SNARK systems typically consists of the following two components:
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:
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:
These innovations enable Binius to offer a compact, high-performance SNARK system, optimized for binary fields while maintaining robust security and scalability.
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).
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:
While Binius and HyperPlonk share several similarities in their protocol designs, Binius introduces the following key improvements:
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.
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:
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:
The Lasso protocol consists of three core components:
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.
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.
To further improve performance, Binius incorporates four major optimizations:
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.
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:
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𝐶𝐺
.
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.
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.
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.
𝑡
, 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.
𝐺𝐹[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.
𝑂(𝑑⋅𝑡)
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.
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:
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
𝐾
.
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
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.
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:
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.
The construction of most modern SNARK systems typically consists of the following two components:
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:
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:
These innovations enable Binius to offer a compact, high-performance SNARK system, optimized for binary fields while maintaining robust security and scalability.
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).
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:
While Binius and HyperPlonk share several similarities in their protocol designs, Binius introduces the following key improvements:
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.
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:
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:
The Lasso protocol consists of three core components:
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.
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.
To further improve performance, Binius incorporates four major optimizations:
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.
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:
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𝐶𝐺
.
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.
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.
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.
𝑡
, 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.
𝐺𝐹[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.
𝑂(𝑑⋅𝑡)
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.
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:
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
𝐾
.
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
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.