Analysis of Binius STARKs Principles and Its Optimization Thoughts

1 Introduction

Unlike elliptic curve-based SNARKs, STARKs can be thought of as hash-based SNARKs. One of the main reasons for the current inefficiency of STARKs is that most of the values in the actual program are small, such as indexes in for loops, true and false values, counters, etc. However, to ensure the security of Merkle tree-based proofs, when the data is extended with Reed-Solomon encoding, many additional redundant values occupy the entire domain, even though the original values themselves are very small. To solve this problem, reducing the size of the domain becomes a key strategy.

As shown in Table 1, the first-generation STARKs are 252 bits, the second-generation STARKs are 64 bits, and the third-generation STARKs are 32 bits. In contrast, the binary domain allows direct bit-alignment operations and is compact and efficient in encoding without wasting space, i.e., 4th generation STARKs.

Table 1: STARKs Evolution Pathways

| Feature | 1st generation STARKs | 2nd generation STARKs | 3rd generation STARKs | The 4th generation STARKs(Binius) | |------|-------------|-------------|-------------|---------------------| | Code bit width | 252bit | 64bit | 32bit | 1bit | | Representative System | StarkWare | Plonky2 | BabyBear | Binius |

Compared with the finite domains discovered in recent years, such as Goldilocks, BabyBear, and Mersenne31, the study of binary domains can be traced back to the 80s of the last century. At present, binary domains have been widely used in cryptography, typical examples include:

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

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

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

• The original FRI and zk-STARK protocols, as well as the Grøstl hash function that made it to the SHA-3 finalist, which is based on the F28 domain and is a well-suited hashing algorithm for recursion.

When using smaller domains, expanding domain operations becomes increasingly important to ensure security. The binary domain used by Binius, on the other hand, needs to rely entirely on domain expansion to ensure its security and actual availability. Most of the polynomials involved in Prover calculations do not need to enter the expanded domain, but only need to operate under the base domain, thus achieving high efficiency in small domains. However, random point checks and FRI calculations still need to be drilled into a larger expansion area to ensure the required security.

When constructing a proof system based on binary domains, there are two practical problems: when calculating the trace representation in STARKs, the domain size used should be larger than the order of the polynomial; When the Merkle tree is promised in STARKs, it needs to be encoded in Reed-Solomon, and the size of the domain used should be larger than the size of the encoding extension.

Binius proposes an innovative solution that deals with these two problems separately and does so by representing the same data in two different ways: first, using multivariate (specifically, multilinear) polynomials instead of univariate polynomials, and representing the entire computational trajectory by its value on the "hypercubes"; Secondly, since the length of each dimension of the hypercube is 2, it is not possible to do the standard Reed-Solomon extension like STARKs, but the hypercube can be treated as a square based on the Reed-Solomon extension. This method greatly improves encoding efficiency and computing performance while ensuring security.

2 Principle Analysis

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

• Information-Theoretic Polynomial Interactive Oracle Proof (PIOP) :P IOP as the core of the proof system, transforming the computational relationships of inputs into verifiable polynomial equations. Different PIOP protocols allow the prover to send polynomials step by step by interacting with the validator, allowing the validator to verify that the calculation is correct by querying the evaluation results of a small number of polynomials. Existing PIOP protocols include PLONK PIOP, Spartan PIOP, and HyperPlonk PIOP, all of which handle polynomial expressions differently, which 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 equation generated by PIOP is true. PCS is a cryptographic tool through which a 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 PCSs have different performance, security, and application scenarios.

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

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

• Plonky2: Combines PLONK PIOP with FRI PCS and is based on the Goldilocks domain. Plonky2 is for efficient recursion. When designing these systems, the PIOP and PCS selected must match the finite domain or elliptic curve used to ensure the correctness, performance, and safety of the system. 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 the need for trusted settings, and whether it can support extended functions such as recursive proofs or aggregate proofs.

Binius: HyperPlonk PIOP + Brakedown PCS + Binary Domain. Specifically, Binius includes five key technologies to achieve its efficiency and safety. First of all, the arithmetic based on the towers of binary fields forms the basis of its calculations, which can realize simplified operations in the binary fields. Secondly, in its interactive Oracle Proof Protocol (PIOP), Binius adapted the HyperPlonk product and permutation check to ensure a safe and efficient consistency check between the variables and their permutations. Thirdly, the protocol introduces a new multilinear shift argument to optimize the efficiency of verifying the multilinear relationship on a small domain. Fourth, Binius adopts an improved version of the Lasso lookup argument, which provides flexibility and strong security for the lookup mechanism. Finally, the protocol uses a small-field polynomial commitment scheme (Small-Field PCS), which enables it to implement an efficient proof system on the binary domain and reduce the overhead typically associated with large domains.

2.1 Finite Fields: Arithmetic based on Towers of Binary Fields

The tower binary domain is the key to fast verifiable computation, which is mainly attributed to two aspects: efficient computation and efficient arithmeticization. Binary domains inherently support highly efficient arithmetic operations, making them ideal for cryptography applications that are sensitive to performance requirements. In addition, the binary domain structure supports a simplified arithmetic process, i.e., operations performed on the binary domain can be represented in a compact and easily verifiable algebraic form. These features, combined with the ability to take full advantage of its hierarchical nature through tower structures, make the binary domain particularly suitable for scalable proof systems such as Binius

where "canonical" refers to a unique and direct representation of an element in the binary domain. For example, in the most basic binary domain F2, any k-bit string can be mapped directly to a k-bit binary domain element. This is in contrast to the prime number field, which cannot provide such a canonical representation within the given position. Although a 32-bit prime number field can be contained in a 32-bit system, not every 32-bit string uniquely corresponds to a domain element, and binary fields have the convenience of this one-to-one mapping. In the prime domain 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 domain F2k, commonly used reduction methods include special reduction (e.g., used in AES), Montgomery reduction (e.g., used in POLYVAL), and recursive reduction (e.g., Tower). The paper "Exploring the Design Space of Prime Field vs. Binary Field ECC-Hardware Implementations" points out that the binary domain does not need to introduce carry in both addition and multiplication, and that the squared operation of the binary domain is very efficient because it follows (X + Y )2 = X2 + Y 2.

! Bitlayer Research: Binius STARKs Principle Analysis and Optimization Thinking

As shown in Figure 1, a 128-bit string: this string can be interpreted in a variety of ways in the context of the binary domain. It can be seen as a unique element in a 128-bit binary domain, or it can be resolved as two 64-bit tower elements, four 32-bit tower elements, 16 8-bit tower elements, or 128 F2 domain elements. The flexibility of this representation doesn't require any computational overhead, just a typecast of bitwise strings, which is a very interesting and useful property. At the same time, small domain elements can be packaged into larger domain elements without additional computational overhead. The Binius protocol takes advantage of this feature to improve computational efficiency. In addition, the paper "On Efficient Inversion in Tower Fields of Characteristic Two" explores the computational complexity of multiplication, squarering, and inversion operations in an n-bit tower binary domain that can be decomposed into m-bit subdomains.

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

The PIOP design in the Binius protocol borrows from HyperPlonk and employs a series of core checking mechanisms to verify the correctness of polynomials and multivariate sets. These core tests include:

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

2. PermutationCheck: Verify that the evaluation results of the two multivariate polynomials f and g on the Boolean hypercube are permutation relations f(x) = f(π(x)) to ensure consistency in the arrangement between polynomial variables.

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

4. MultisetCheck: Check whether the two multivariate sets are equal, i.e., {(x1,i,x2,)}i∈H={(y1,i,y2,)}i∈H to ensure consistency among multiple sets.

5. ProductCheck: Checks whether the evaluation of a rational polynomial on a Boolean hypercube is equal to a declared value ∏x∈Hμ f(x) = s to ensure the correctness of the polynomial product.

6. ZeroCheck: Verify that a multivariate polynomial is zero at any point on the Boolean hypercube∏x∈Hμ f(x) = 0,∀x ∈ Bμ to ensure the zero distribution of the polynomial.

7. SumCheck: Checks if the sum value of the multivariate polynomial is the declared value ∑x∈Hμ f(x) = s. By transforming the evaluation problem of multivariate polynomials into univariate polynomial evaluation, the computational complexity of the verifier is reduced. In addition, SumCheck also allows batch processing, by introducing random numbers, constructing linear combinations to achieve batch processing of multiple sum check instances.

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

Although there are many similarities between Binius and HyperPlonk in terms of protocol design, Binius has made improvements in the following three aspects:

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

• Handling of the divide-zero problem: HyperPlonk fails to adequately handle the divide-zero case, resulting in the inability to assert the non-zero problem of U on the hypercube; Binius handles this correctly, and Binius' ProductCheck continues to process even when the denominator is zero, allowing generalizations to arbitrary product values.

• PermutationCheck: This feature is not available in HyperPlonk; Binius supports PermutationCheck between multiple columns, which allows Binius to handle more complex polynomial permutations.

Therefore, through the improvement of the existing PIOPSumCheck mechanism, Binius improves the flexibility and efficiency of the protocol, especially when dealing with more complex multivariate polynomial verification, and provides stronger functional support. These improvements not only address the limitations in HyperPlonk, but also provide a binary-based foundation for the future