Analysis of Binius STARKs Principles and Its Optimization Thoughts

1 Introduction

One of the main reasons for the inefficiency of STARKs is that most values in actual programs are relatively small, but to ensure security based on Merkle tree proofs, many additional redundant values occupy the entire field when using Reed-Solomon encoding to expand the data, even though the original values themselves are very small. To address this issue, reducing the size of the field has become a key strategy.

The encoding bit width of the 1st generation STARKs is 252 bits, the 2nd generation STARKs has a bit width of 64 bits, and the 3rd generation STARKs has a bit width of 32 bits, but the 32-bit encoding bit width still has a lot of wasted space. In contrast, the binary field allows for direct bit manipulation, with compact and efficient encoding that has no arbitrary wasted space, which is the 4th generation STARKs.

Compared to recent discoveries in finite fields such as Goldilocks, BabyBear, and Mersenne31, research on binary fields dates back to the 1980s. Currently, binary fields are widely used in cryptography, with typical examples including:

• Advanced Encryption Standard ( AES ), based on F28 field;

• Galois Message Authentication Code ( GMAC ), based on the F2128 field;

• QR code, using Reed-Solomon encoding based on F28;

• The original FRI and zk-STARK protocols, as well as the Grøstl hash function that made it to the finals of SHA-3, which is based on the F28 field and is a very suitable hash algorithm for recursion.

When using smaller fields, the field extension operation becomes increasingly important for ensuring security. The binary field used by Binius relies entirely on field extension to guarantee its security and practical usability. Most polynomials involved in Prover computations do not need to enter the extended field and can operate solely in the base field, achieving high efficiency in small fields. However, random point checks and FRI calculations still need to delve into a larger extended field to ensure the required security.

When constructing proof systems based on binary fields, there are two practical issues: the size of the field used to compute the trace representation in STARKs should be greater than the degree of the polynomial; when committing to a Merkle tree in STARKs, Reed-Solomon encoding is required, and the size of the field should be greater than the size after encoding expansion.

Binius proposed an innovative solution to address these two issues separately and achieves this by representing the same data in two different ways: first, by using multivariate (specifically multilinear) polynomials instead of univariate polynomials, representing the entire computation trajectory through its values on "hypercubes"; secondly, since the length of each dimension of the hypercube is 2, standard Reed-Solomon expansion cannot be performed like in STARKs, but the hypercube can be regarded as a square, allowing for Reed-Solomon expansion based on that square. This approach greatly enhances coding efficiency and computational performance while ensuring security.

2 Principle Analysis

The construction of most SNARKs systems currently usually consists of the following two parts:

• Information-Theoretic Polynomial Interactive Oracle Proof (PIOP): PIOP, as the core of the proof system, transforms the input computational relations into verifiable polynomial equations. Different PIOP protocols allow the prover to send polynomials step by step through interaction with the verifier, enabling the verifier to validate whether the computation is correct by querying a small number of polynomial evaluation results. Existing PIOP protocols include: PLONK PIOP, Spartan PIOP, and HyperPlonk PIOP, each with different approaches to handling polynomial expressions, which in turn affects the performance and efficiency of the entire SNARK system.

• Polynomial Commitment Scheme (PCS): The polynomial commitment scheme is used to prove whether the polynomial equations generated by PIOP hold true. PCS is a cryptographic tool through which the prover can commit to a certain polynomial and later verify the evaluation results of that polynomial while hiding other information about the polynomial. Common polynomial commitment schemes include KZG, Bulletproofs, FRI (Fast Reed-Solomon IOPP), and Brakedown. Different PCS have different performance, security, and applicable scenarios.

Depending on specific requirements, different PIOPs and PCs can be selected, combined with suitable finite fields or elliptic curves, to construct proof systems with different attributes. For example:

• Halo2: combines PLONK PIOP and Bulletproofs PCS, based on the Pasta curve. When designing Halo2, emphasis was placed on scalability and removing the trusted setup in the ZCash protocol.

• Plonky2: Combines PLONK PIOP with FRI PCS and is based on the Goldilocks field. Plonky2 is designed for efficient recursion. When designing these systems, the chosen PIOP and PCS must match the finite field or elliptic curve being used to ensure the system's correctness, performance, and security. The choice of these combinations not only affects the proof size and verification efficiency of the SNARK, but also determines whether the system can achieve transparency without a trusted setup, and whether it can support extended functionalities such as recursive proofs or aggregate proofs.

Binius: HyperPlonk PIOP + Brakedown PCS + binary fields. Specifically, Binius includes five key technologies to achieve its efficiency and security. First, the arithmetic based on towers of binary fields forms the foundation of its computation, enabling simplified operations within the binary fields. Second, Binius adapts the HyperPlonk product and permutation checks in its interactive Oracle proof protocol (PIOP), ensuring secure and efficient consistency checks between variables and their permutations. Third, the protocol introduces a new multilinear shift proof, optimizing the efficiency of verifying multilinear relationships over small fields. Fourth, Binius employs an improved Lasso lookup proof, providing flexibility and strong security for the lookup mechanism. Finally, the protocol uses a Small-Field polynomial commitment scheme (Small-Field PCS), allowing it to implement an efficient proof system over binary fields and reducing the overhead typically associated with large fields.

2.1 Finite Fields: Arithmetic Based on Towers of Binary Fields

Towered binary fields are key to achieving fast verifiable computation, mainly due to two aspects: efficient computation and efficient arithmetic. Binary fields inherently support highly efficient arithmetic operations, making them an ideal choice for performance-sensitive cryptographic applications. Additionally, the structure of binary fields supports a simplified arithmetic process, meaning that operations performed over binary fields can be represented in a compact and easily verifiable algebraic form. These features, combined with the ability to fully leverage their hierarchical characteristics through the tower structure, make binary fields particularly suitable for scalable proof systems such as Binius.

The term "canonical" refers to the unique and direct representation of elements in the binary field. For example, in the most basic binary field F2, any k-bit string can be directly mapped to a k-bit binary field element. This is different from prime fields, which cannot provide such a canonical representation within a given bit length. Although a 32-bit prime field can be contained within 32 bits, not every 32-bit string can uniquely correspond to a field element; whereas, the binary field has the convenience of such a one-to-one mapping. In prime fields Fp, common reduction methods include Barrett reduction, Montgomery reduction, and special reduction methods for specific finite fields such as Mersenne-31 or Goldilocks-64. In the binary field F2k, commonly used reduction methods include special reductions (as used in AES), Montgomery reductions (as used in POLYVAL), and recursive reductions (such as Tower). The paper "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" points out that in binary fields, both addition and multiplication operations do not require carry, and the squaring operation in binary fields is very efficient because it follows the simplified rule (X + Y )2 = X2 + Y2.

As shown in Figure 1, a 128-bit string: this string can be interpreted in various ways in the context of binary fields. It can be viewed as a unique element in a 128-bit binary field, or parsed into two 64-bit tower field elements, four 32-bit tower field elements, sixteen 8-bit tower field elements, or 128 F2 field elements. This flexibility of representation does not require any computational overhead; it is merely a typecast of the bit string, which is a very interesting and useful property. Meanwhile, small field elements can be packed into larger field elements without additional computational overhead. The Binius protocol leverages this feature to improve computational efficiency. Additionally, the paper "On Efficient Inversion in Tower Fields of Characteristic Two" discusses the computational complexity of multiplication, squaring, and inversion operations in an n-bit tower binary field (which can decompose into m-bit subfields).

2.2 PIOP: Adapted HyperPlonk Product and Permutation Check------Applicable to binary fields

The PIOP design in the Binius protocol is inspired by HyperPlonk and employs a series of core verification mechanisms to validate the correctness of polynomials and multivariate sets. These core checks include:

1. GateCheck: Verify whether the confidential witness ω and public input x satisfy the circuit operation relationship C(x, ω)=0, to ensure the correct operation of the circuit.

2. PermutationCheck: Verify whether the evaluation results of two multivariate polynomials f and g on the Boolean hypercube form a permutation relation f(x) = f(π(x)), to ensure the consistency of the arrangement between polynomial variables.

3. LookupCheck: Verify whether the evaluation of the polynomial is within the given lookup table, i.e., f(Bµ) ⊆ T(Bµ), ensuring that certain values are within the specified range.

4. MultisetCheck: Check whether two multivariate sets are equal, that is, {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H, ensuring the consistency between multiple sets.

5. ProductCheck: Check whether the evaluation of a rational polynomial on the Boolean hypercube equals a declared value ∏x∈Hµ f(x) = s, to ensure the correctness of the polynomial product.

6. ZeroCheck: Verify whether a multivariable polynomial at any point on the Boolean hypercube is zero ∏x∈Hµ f(x) = 0, ∀x ∈ Bµ, to ensure the distribution of the polynomial's zeros.

7. SumCheck: Verifying whether the sum of a multivariate polynomial equals the declared value ∑x∈Hµ f(x) = s. It reduces the computational complexity for the verifier by transforming the multivariate polynomial evaluation problem into a univariate polynomial evaluation problem. In addition, SumCheck also allows for batching, constructing linear combinations to achieve batching for multiple sum verification instances by introducing randomness.

8. BatchCheck: Based on SumCheck, it verifies the correctness of multiple multivariate polynomial evaluations to improve protocol efficiency.

Although Binius and HyperPlonk have many similarities in protocol design, Binius has made improvements in the following three areas:

• ProductCheck Optimization: In HyperPlonk, the ProductCheck requires that the denominator U is non-zero everywhere on the hypercube, and the product must equal a specific value; Binius simplifies this checking process by specializing that value to 1, thus reducing computational complexity.

• Handling of the divide-by-zero problem: HyperPlonk fails to adequately handle divide-by-zero situations, leading to an inability to assert the non-zero problem of U on the hypercube; Binius correctly addresses this issue, allowing Binius's ProductCheck to continue processing even when the denominator is zero, enabling extension to any product value.

• Cross-column Permutation Check: HyperPlonk does not have this feature; Binius supports Permutation Check across multiple columns, allowing Binius to handle more complex polynomial arrangement scenarios.

Therefore, Binius has improved the existing PIOPSumCheck mechanism, enhancing the flexibility and efficiency of the protocol, especially in providing stronger functional support when dealing with more complex multivariable polynomial verifications. These improvements not only address the limitations in HyperPlonk but also lay the groundwork for future proof systems based on binary fields.

2.3 PIOP: New multilinear shift argument------Applicable to boolean hypercube

In the Binius protocol, the construction and handling of virtual polynomials is one of the key technologies, which can effectively generate and operate polynomials derived from input handles or other virtual polynomials. Here are two key methods:

• Packing: This method involves taking the smaller elements from adjacent positions in the dictionary order.