Analysis of Binius STARKs Principles and Optimization Thoughts

1. Introduction

One of the main reasons for the inefficiency of STARKs is that most values in actual programs are relatively small. However, to ensure the security of proofs based on Merkle trees, when using Reed-Solomon encoding to expand the data, many additional redundant values occupy the entire field, even if the original values are small. Reducing the size of the field becomes a key strategy.

The first generation of STARKs has a code width of 252 bits, the second generation has 64 bits, and the third generation has 32 bits, but there is still a lot of wasted space in 32 bits. The binary field allows for direct bit manipulation, and the encoding is compact, efficient, and waste-free, which may be the fourth generation of STARKs.

Binary fields are widely used in cryptography, such as AES(F28), GMAC(F2128), QR code(F28), etc. When using smaller fields, the operation of field extension becomes increasingly important to ensure security. The binary fields used by Binius must rely entirely on field extension to guarantee security and usability. Most Prover computations operate efficiently under the base field; however, random point checks and FRI calculations require delving into larger extended fields to ensure security.

Binius Innovative Solutions:

1. use multivariable ( multilinear ) polynomial to replace univariate polynomial, representing the calculation trajectory through "hypercube" value extraction.
2. views the hypercube as a square and performs Reed-Solomon expansion based on the square.

2. Principle Analysis

Binius = HyperPlonk PIOP + Brakedown PCS + Binary Field

Five key technologies:

1. Arithmetic based on tower binary field
2. Adaptation of HyperPlonk Product and Permutation Check
3. New Multilinear Shift Argument
4. Improved Lasso Search Argument
5. Local Polynomial Commitment Scheme

2.1 Finite fields: Arithmetic based on towers of binary fields

Tower Binary Domain Advantages:

• Efficient computation: The binary field supports efficient arithmetic operations.
• Efficient arithmetic: The binary field structure supports a simplified arithmetic process.
• Fully utilize the hierarchical characteristics through the tower structure

128-bit string can be flexibly interpreted:

• A unique element in a 128-bit binary field
• Two 64-bit tower field elements
• Four 32-bit tower domain elements
• 16 8-bit tower domain elements
• 128 F2 field elements

2.2 PIOP: Adapted HyperPlonk Product and Permutation Check

Binius Core Check Mechanism:

1. GateCheck
2. PermutationCheck
3. LookupCheck
4. MultisetCheck
5. ProductCheck
6. ZeroCheck
7. SumCheck
8. BatchCheck

Binius's improvement on HyperPlonk:

• ProductCheck Optimization
• Correctly handle division by zero issues
• Support cross-column PermutationCheck

2.3 PIOP: new multilinear shift argument

Key Methods:

• Packing: Pack adjacent smaller elements into larger elements.
• Shift operator: Rearranging elements within the block

2.4 PIOP: Adapted version Lasso lookup argument

Advantages of Lasso Protocol:

• High proof efficiency: m+n field elements commitment
• No need to commit to large tables: can handle super large tables

Binius introduces the multiplicative version of the Lasso protocol:

• Generate a "memory count" incrementally through binary field multiplication.
• The proving party commits to a non-zero read count vector to ensure security.

2.5 PCS: Adapted Version Brakedown PCS

Core idea: packing

Two solutions:

1. Instantiate using concatenated code
2. Adopting block-level encoding, supporting the use of Reed-Solomon codes independently.

Small Field Polynomial Commitment and Extended Field Evaluation:

• Committed to the small domain K
• Evaluate in a larger expansion domain L/K

Block-level encoding and Reed-Solomon codes:

• Allow small domain ( such as F2) polynomial to use uppercase alphabet ( such as F216) Reed-Solomon code for efficient commitment.

3. Optimizing Thinking

Four key optimization points:

3.1 GKR-based PIOP: GKR-based binary field multiplication

Convert "Check A·B =? C" to "Check (gA)B =? gC"

• Just one auxiliary commitment
• Reduce Sumchecks overhead

3.2 ZeroCheck PIOP Optimization: Trade-off between Prover and Verifier computational overhead

Optimization method:

• Reduce the data transmission of the proof party
• Reduce the number of evaluation points for the proving party
• Algebraic Interpolation Optimization

3.3 Sumcheck PIOP Optimization: Sumcheck Protocol Based on Small Fields

Key Improvements:

• Switch selection for round t
• The influence of the domain size
• Karatsuba Algorithm Optimization
• Memory efficiency improvement

3.4 PCS optimization: FRI-Binius reduces proof size

Four innovations:

1. Flattened polynomial
2. Subspace Disappearance Polynomial
3. Algebraic Basis Packaging
4. Ring Exchange SumCheck

FRI-Binius can reduce the size of the Binius proof by one order of magnitude.

4. Summary

Binius Advantages:

• Can use the minimum power-of-two field for witnesses
• Low memory usage rapid verification
• Basic removal of Prover commit bottleneck

New Bottleneck: Sumcheck Protocol

• Efficiently solved with dedicated hardware

FRI-Binius:

• Eliminate the overhead of embedding proof layers
• Does not cause a surge in the cost of the proof of aggregation layer

Current progress:

• The Irreducible team is developing a recursive layer in collaboration with Polygon to build a Binius-based zkVM.
• JoltzkVM switches from Lasso to Binius
• Ingonyama implements FPGA version of Binius