Data Representation in a Hypercube:
- The data to be proven is initially represented as a multilinear polynomial in a hypercube $P(x_0,x_1,…,x_k)$. Each point in the hypercube corresponds to a bit value (0 or 1).
Hypercube to Grid Transformation:
- The bits in the hypercube are converted into a grid format. This involves "flattening" the hypercube, which essentially means representing the data in a more linear structure suitable for subsequent operations.
Extension Using Reed-Solomon Codes:
- The protocol extends the bits into larger values by grouping them into columns. These columns are temporarily treated as larger field elements for the purpose of Reed-Solomon encoding.
- For instance, bits might be packed together in groups (e.g., 16 bits at a time) and then extended using Reed-Solomon codes. This extension process is critical for ensuring that the proof has sufficient redundancy for security.
Row Combination:
- After the initial extension, the protocol performs a row combination. This involves taking linear combinations of rows to check if they satisfy certain polynomial relations. The row combination is done over the extended field elements.
Bit Decomposition:
- After the row combination, the extended values are decomposed back into bits. This ensures that the data remains in the binary field (0s and 1s).
Evaluation at Random Points:
- To ensure cryptographic security, evaluations are performed at random points that are sampled from a larger space than the original hypercube. This step helps in proving the correctness of the polynomial representation and the computations performed on it.
Commitments and Proofs:
- The protocol then commits to the multilinear polynomial using Merkle trees or other commitment schemes. It provides proofs of evaluations at random points, ensuring that these commitments are consistent with the original data and polynomial operations.
Verifier Checks:
- The verifier performs a series of checks to validate the proof. This includes verifying the row and column combinations and ensuring that the evaluations match the committed values.
- Specifically, the verifier checks the consistency of the polynomial evaluations and the Merkle branches corresponding to the randomly selected points.
Prover Time:
- The time complexity for the prover in the Binius protocol is $O(N\log N)$. This is due to the efficient encoding and bitwise operations that significantly reduce the computational overhead compared to traditional zero-knowledge proof systems.
Verifier Time:
- The time complexity for the verifier is $O(\sqrt{N})$. The verifier needs to perform checks on the proof data, which involves verifying polynomial evaluations and consistency of Merkle branches. The use of efficient data structures and algorithms helps to keep this time complexity low.
Proof Size:
- The size of the proof is $O(\sqrt{N})$. By leveraging compact encoding techniques and optimizing the representation of data, the proof size is kept small, making the protocol more efficient in terms of storage and transmission.
Even if $O(N \log N)$ seems less efficient wrt to $O(N)$ which is the prover complexity of Groth16 or Plonk, Binius operates directly over binary fields making $N$closely related to the bit-length of the data while the others use large prime fields (typically 256-bit primes), where
$N$ corresponds to the number of operations performed over these fields. In other words;
Binius is more efficient for circuits with many small values (bits), leveraging binary operations.
Plonk is optimized for general arithmetic circuits over large prime fields, making it less efficient for small, bit-level operations.
Circle STARK
Circle STARKs build on the concept of Elliptic Curve FFT (ECFFT) to improve the efficiency of STARKs for certain finite fields. The key innovation is the use of a circle curve $𝑥^2+𝑦^2=1$ for arithmetization, which allows for efficient interpolation using the FFT algorithm. This approach is particularly efficient when $p+1$ is divisible by a large power of 2, such as the Mersenne prime $p=2^{31}-1$.
Circle STARK Protocol Steps
Initialization and Preprocessing
- Utilize the Mersenne prime $p=2^{31}−1$, which allows for highly efficient arithmetic operations.
- Define the circle curve $x^2+y^2=1$ over the prime field. This curve is used to construct the algebraic framework needed for the protocol.
Polynomial Representation
- Define the space of polynomials $L_N(F)$ over the circle curve. These polynomials have total degrees bounded by $N/2$, where $N$ is the size of the evaluation domain.
- Canonical Form: Polynomials in $L_N(F)$ can be expressed in the form $p(x,y)=p_0(x)+y⋅p_1(x)$, where $p_0$ and $p_1$ are polynomials in $x$ with degrees $≤N/2−1$.
FFT and Inverse FFT
- Construct the FFT basis $B_n$ using the vanishing polynomials $v_n(x)$ of the standard position cosets.
- The algorithm decomposes a function over the twin-coset domain $D$ into its even and odd parts using the involution $J$ and recursively computes the coefficients with respect to the FFT basis. This process involves the following steps:
- Decomposition: Split the function $f$ into even $f_0$ and odd $f_1$ parts using the reference functions $t_0(x,y)=y$ and $t_1(x,y)=x$.
- Recursive Reduction: Reduce the problem size step by step by mapping the domains through squaring and projection operations.
- Coefficient Computation: The final output is the set of coefficients $c_k$ corresponding to the FFT basis polynomials $b_k$.
Proving and Verification
(Same idea in STARK applied)
- Prover: The prover generates a proof by encoding the witness data into polynomials over the circle curve and applying the IOP system. This involves:
- Constraint Encoding: Encode the constraints as low-degree polynomials over the evaluation domain.
- Proof Composition: Use the FFT to transform and verify the polynomial evaluations efficiently.
- Verifier: The verifier checks the proof by validating the polynomial evaluations and ensuring they satisfy the encoded constraints. The low-degree test over the circle curve ensures the soundness of the proof.