Analysis and Optimization Thoughts on the Principles of Binius STARKs

1. Introduction

One of the main reasons for the inefficiency of STARKs is that most of the numerical values in actual programs are relatively small. However, to ensure the security of proofs based on Merkle trees, many additional redundant values occupy the entire field when data is expanded using Reed-Solomon coding. To address this issue, reducing the size of the field has become 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. However, the 32-bit code width still has a lot of wasted space. In contrast, the binary field allows for direct bit manipulation, making the encoding compact and efficient without any wasted space, namely the fourth generation of STARKs.

The binary field used by Binius relies entirely on the extension field to ensure its security and practical usability. Most polynomials involved in Prover computations do not need to enter the extension field and can operate solely in the base field, achieving high efficiency in the small field. However, random point checks and FRI computations still need to delve into a larger extension field to ensure the required security.

Binius proposed an innovative solution: first, using multivariable (specifically multilinear) polynomials instead of univariate polynomials to represent the entire computation trajectory by its values on "hypercubes"; second, 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 viewed as a square, and Reed-Solomon expansion can be based on that square.

2. Principle Analysis

Binius includes five key technologies:

1. Arithmetic based on tower binary fields
2. Adapted version of HyperPlonk product and permutation check
3. New Multilinear Shift Argument
4. Improved Lasso Search Argument
5. Small Domain Polynomial Commitment Scheme

2.1 Finite Fields: Arithmetic based on towers of binary fields

Advantages of tower binary domain:

• Efficient computation: The binary field essentially supports highly efficient arithmetic operations.
• Efficient Arithmetic: The binary field structure supports simplified arithmetic processes.
• Standard representation: The elements in the binary field have a unique and direct representation.

Advantages of binary domain:

• Addition and multiplication operations do not require carry.
• Square operations are very efficient, following the simplification rule of (X + Y)^2 = X^2 + Y^2.
• Indicates flexibility: a 128-bit string can be regarded as a unique element in a 128-bit binary field, or parsed as a combination of multiple tower field elements.

2.2 PIOP: Adapted HyperPlonk Product and Permutation Check

Binius PIOP Core Inspection Mechanism:

• GateCheck
• PermutationCheck
• LookupCheck
• MultisetCheck
• ProductCheck
• ZeroCheck
• SumCheck
• BatchCheck

Binius' improvements to HyperPlonk:

• ProductCheck Optimization
• Handling of Division by Zero Issue
• Cross-column Permutation Check support

2.3 PIOP: New multilinear shift argument

Key Method:

• Packing: Optimize operations by packing adjacent elements.
• Bitwise operator: rearrange elements within the block

2.4 PIOP: Adapted Lasso lookup argument

Components of the Lasso Protocol:

• Virtual Polynomial Abstraction of Large Tables
• Small table lookup
• Multi-collection check

Binius's adaptation of Lasso:

• Introduce the multiplication version of the Lasso protocol
• Requires the proving party to commit to a non-zero reading count vector.

2.5 PCS: Adapted Version Brakedown PCS

Core idea: packing

Two types of Brakedown polynomial commitment schemes based on binary fields:

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

Main technology:

• Small Domain Polynomial Commitment and Extension Field Evaluation
• Small Domain Universal Construction
• Block coding and Reed-Solomon codes

3. Optimizing Thinking

Four key optimization points:

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

Advantages compared to the Binius lookup solution:

• Just one auxiliary commitment is required.
• Reduce Sumchecks overhead

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

Optimization methods:

• Reduce the data transmission of the proving 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 point:

• The impact and improvement factors of switching rounds
• The impact of the domain size on performance
• The optimization benefits of the Karatsuba algorithm
• Improvement in memory efficiency

3.4 PCS optimization: FRI-Binius reduces Binius proof size

FRI-Binius' four innovations:

• Flattened polynomial
• Subspace Disappearance Polynomial
• Algebra Base Packaging
• Ring exchange SumCheck

FRI-Binius PCS process:

• Commitment Stage
• Evaluation Phase

4. Summary

Binius's value proposition:

• Can use the minimum power-of-two field for witnesses.
• Collaborative design scheme, low memory usage for quick proof.
• Fundamentally remove the commitment bottleneck of Prover.
• The new bottleneck lies in the Sumcheck protocol, which can be efficiently resolved using dedicated hardware.

FRI-Binius Plan:

• Eliminate embedding overhead from the domain proof layer
• Will not lead to a surge in costs for the aggregated proof layer.

Current Progress:

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