Building Blocks of zk-STARKS

zk-STARK (Zero-Knowledge Scalable Transparent ARguments of Knowledge) is a cryptographic protocol that offers proofs of computational integrity without the need for a trusted setup. Here are its primary building blocks:

1. Polynomial Commitments: Essential for committing to polynomials without revealing their coefficients.

2. Interactive Oracle Proofs: A method where the prover convinces the verifier of the validity of a statement interactively.

3. Fast Fourier Transforms (FFT): Used for efficient polynomial evaluation.

4. Low-degree Extensions: Allows for extending the domain of a polynomial while maintaining low degrees.

The Arithmetization Process

The process of converting computational problems into algebraic language, specifically into polynomial forms, is termed as arithmetization. In zk-STARKS, this is a fundamental step for enabling the rest of the system.

1. Statement Conversion: The initial computational problem or statement is transformed into an algebraic intermediate representation. This involves representing the original computation as a series of steps (or gates) in a circuit.

2. Polynomial Representation: The intermediate representation is then turned into a polynomial. The goal here is to create a polynomial that is zero if and only if the statement is true.

For example, for the equation x + y = z, the polynomial P(X) might be represented as P(X) = x + y - z. The polynomial evaluates to zero if and only if the equation holds true.

The Composition Function

The composition function plays a pivotal role in condensing the various polynomials from the arithmetization step into a single polynomial. This is done to simplify the proof and verification process.

1. Constraint Polynomial: This polynomial captures the constraints of the computational problem. If all constraints are satisfied, the polynomial evaluates to zero.

2. Trace Polynomial: Represents the actual computation's trajectory. It traces the computational steps.

3. Composition: The composition function combines the constraint and trace polynomials into a single polynomial, which is simpler to manage and reason about. This polynomial is zero only if both the trace and constraint polynomials are correctly constructed, ensuring the original statement is true.

The Proof System

The proof system in zk-STARKS is interactive and involves a prover and a verifier.

1. Commitment Phase: The prover commits to a specific polynomial and provides a commitment to the verifier. This is done using polynomial commitment schemes without revealing the polynomial.

2. Challenge Phase: The verifier, after receiving the commitment, sends a challenge to the prover. This challenge is generally a point at which the prover should evaluate their polynomial.

3. Response Phase: The prover responds by providing the evaluation of their polynomial at the challenge point.

4. Verification: The verifier can then verify the correctness of this response using the initial commitment and the properties of the polynomial commitment scheme.