Analysis of the Principles of Binius STARKs and Optimization Thoughts

1 Introduction

STARKs are a hash-based proof system, unlike SNARKs which are based on elliptic curves. A major reason for the current inefficiency of STARKs is that most values in practical programs are quite small, such as indices in for loops, boolean values, counters, etc. However, to ensure the security of proofs based on Merkle trees, using Reed-Solomon encoding to expand the data introduces many additional redundant values that occupy the entire field, even though the original values themselves are very small. To address this issue, reducing the size of the field has become a key strategy.

As shown in Table 1, the encoding bit width of the first generation STARKs is 252 bits, the second generation STARKs is 64 bits, and the third generation STARKs is 32 bits; however, the 32-bit encoding 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 fourth generation STARKs.

Table 1: STARKs Derivation Path

| Generation | Bit Width | Features | |------|------|------| | 1st Generation | 252bit | Global, large space waste | | 2nd Generation | 64bit | Medium domain, larger space waste | | 3rd Generation | 32bit | Small Domain, Still Has Wasted Space | | 4th Generation | 1bit | Binary Domain, no wasted space |

Compared to finite fields discovered in recent years such as Goldilocks, BabyBear, and Mersenne31, the study of binary fields can be traced 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 reached the finals of SHA-3, which is based on the F28 field, are very suitable recursive hash algorithms.

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

When constructing proof systems based on binary fields, there are two practical issues: the size of the field used for calculating 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 must be performed, and the size of the field used should be greater than the size after encoding expansion.

Binius has proposed an innovative solution that addresses both problems separately and achieves this by representing the same data in two different ways: first, using multivariable ( specifically multivariate ) polynomials instead of univariate polynomials, representing the entire computational trajectory through its values on "hypercubes" (; secondly, since each dimension of the hypercube has a length of 2, it cannot perform standard Reed-Solomon extensions like STARKs, but the hypercube can be viewed as a square ), and Reed-Solomon extensions can be based on that square. This method greatly improves coding efficiency and computational performance while ensuring security.

2 Principle Analysis

The construction of most SNARKs systems currently typically includes 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 gradually send polynomials through interaction with the verifier, enabling the verifier to validate the correctness of the computation by querying a small number of polynomial evaluation results. Existing PIOP protocols include: PLONK PIOP, Spartan PIOP, and HyperPlonk PIOP, each with different methods of handling polynomial expressions, thereby affecting the performance and efficiency of the entire SNARK system.

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

According to specific requirements, different PIOP and PCS can be selected, and combined with suitable finite fields or elliptic curves, to construct proof systems with different attributes. For example:

• Halo2: Combined from PLONK PIOP and Bulletproofs PCS, based on the Pasta curve. Halo2 is designed with a focus on scalability and the removal of 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 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 SNARKs 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 tower binary fields )towers of binary fields( forms the foundation of its computation, enabling simplified operations within binary fields. Second, Binius adapts 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 version of the Lasso lookup proof, providing flexibility and robust security for the lookup mechanism. Finally, the protocol utilizes a small-field polynomial commitment scheme )Small-Field PCS(, allowing it to achieve an efficient proof system over binary fields while reducing the overhead typically associated with large fields.

) 2.1 Finite Fields: Arithmetic based on towers of binary fields

Tower binary fields are key to achieving fast verifiable computation, primarily 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. Furthermore, 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 nature through tower structures, make binary fields particularly suitable for scalable proof systems such as Binius.

The term "canonical" refers to the unique and direct representation of an element in a binary field. For example, in the simplest 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 specified 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 binary fields have the convenience of this one-to-one mapping. In the prime field Fp, common reduction methods include Barrett reduction, Montgomery reduction, and special reduction methods for specific finite fields like Mersenne-31 or Goldilocks-64. In the binary field F2k, commonly used reduction methods include special reduction ( as used in AES ), Montgomery reduction ### as used in POLYVAL (, and recursive reduction ) as in Tower (. The paper "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" points out that binary fields do not require carry in addition and multiplication operations, 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 considered a unique element in the 128-bit binary field, or parsed as two 64-bit tower field elements, four 32-bit tower field elements, 16 8-bit tower field elements, or 128 F2 field elements. This flexibility in representation does not require any computational overhead, just a typecast of the bit string )typecast(, which is a very interesting and useful property. At the same time, small field elements can be packed into larger field elements without additional computational overhead. The Binius protocol takes advantage of this feature to improve computational efficiency. Furthermore, the paper "On Efficient Inversion in Tower Fields of Characteristic Two" explores the computational complexity of performing multiplication, squaring, and inversion operations in an n-bit tower binary field ) decomposed into m-bit subfields (.

![Bitlayer Research: Analysis of Binius STARKs Principles and Its Optimization Thoughts])https://img-cdn.gateio.im/webp-social/moments-5775a629f494c4e01e2b74d864fa4100.webp(

) 2.2 PIOP: Adapted HyperPlonk Product and Permutation Check ------ Applicable to Binary Field

The PIOP design in the Binius protocol draws inspiration from HyperPlonk and employs a series of core checking mechanisms to verify the correctness of polynomials and sets of multiple variables. 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 multivariable polynomials f and g on the Boolean hypercube are a permutation relationship 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: Checks whether two multiset collections are equal, i.e., {)x1,i,x2,(}i∈H={)y1,i,y2,(}i∈H, ensuring consistency among multiple collections.

5. ProductCheck: Check whether the evaluation of the 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 an arbitrary point of a multivariable polynomial on the Boolean hypercube is zero ∏x∈Hµ f)x( = 0, ∀x ∈ Bµ, to ensure the distribution of the polynomial's zeros.

7. SumCheck: Detecting whether the sum of a multivariate polynomial is equal to the declared value ∑x∈Hµ f)x( = s. By transforming the evaluation problem of multivariate polynomials into that of univariate polynomial evaluation, it reduces the computational complexity for the verifier. Additionally, SumCheck allows for batching by introducing random numbers to construct linear combinations for the batching of multiple sum check instances.

8. BatchCheck: Based on SumCheck, verifies the correctness of multiple multivariable 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, ProductCheck requires that the denominator U is non-zero everywhere on the hypercube, and the product must equal a specific value; Binius simplifies this check process by specializing that value to 1, thereby reducing computational complexity.

• Handling of Division by Zero: HyperPlonk fails to adequately address the division by zero situation, leading to an inability to assert the non-zero problem of U on the hypercube; Binius handles this issue correctly, such that even in cases where the denominator is zero, Binius' ProductCheck can continue processing, allowing for generalization to any product value.

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

Therefore, Binius has improved the existing PIOPSumCheck mechanism, enhancing the protocol's flexibility and efficiency, especially in handling more complex multivariable polynomial verifications, providing stronger functional support. These improvements not only address the limitations in HyperPlonk but also for the unmet.