# STARK

The process involves two main steps:
1. Transforming a Constraint Integrity (CI) statement into certain polynomials.

2. Proving that these polynomials are close to low-degree polynomials.

Our primary focus is on step 1, while step 2 is handled a the low-degree test (such as [FRI](https://hackmd.io/@YaoGalteland/SJhTGtsZ1x)).

## Computational Integrity (CI) Statement

A CI statement asserts that for a given program $A$, input $x$, output $y$, and time bound $T$, one can produce a proof string $𝛑$ attesting to the following claim:
> $A(x)$ outputs $y$ within $T$ computation steps

In STARKs, the process of arithmetization relies on **Arithmetic Intermediate Representation (AIR)**, which describes computations using **transition constraints** and **boundary constraints** defined over an **execution trace**.

**Compared to SNARKs.** Larger proof sizes. But optimized for iterative and high-throughput computations.

:::warning
In contrast, SNARKs (e.g., Groth16, Marlin) use **Rank-1 Constraint Systems (R1CS)** for arithmetization. PLONK uses **arithmetic constraint systems**.

:::

**Example: Fibonacci Sequence Problem**
Given two inputs $x_0,x_1$, compute the 5-th term of the Fibonacci sequence modulo 97, where:
- $a_0=x_0$
- $a_1=x_1$
- Output: $a_5=28$

## From CI statement to [Polynomial Constraints and Execution Trace](https://medium.com/starkware/arithmetization-i-15c046390862)

### Execution Trace

The **execution trace**, denoted as $A_{i,j}$, records the internal state of the computation at each step. It includes data columns (holding intermediate values) and selector/control columns (enforcing specific rules).

For example:

### Polynomial Constraints
**Boundary constraints** enforce rules for initialization and termination:

- Initialization Rule
- $(A_{i,1} - 24)\cdot A_{i,3}=0$
- $(A_{i,2} - 30)\cdot A_{i,3}=0$

- Termination Rule:
- $(A_{i,2} - 28)\cdot A_{i,6}=0$

**Transition constraints** ensure the correct relationship between consecutive states:
- Transition Rule (enforce Fibonacci-like progression):
- $(A_{i,2}-A_{i-1,1}-A_{i-1,2})\cdot A_{i,4}=0$
- $(A_{i,1}-A_{i-1,2})\cdot A_{i,4}=0$

**Enabling Zero-Knowledge Properties (Part I).** For zero-knowledge proofs, **random padding** is added to the execution trace, and rule checks are **disabled** by setting the relevant control columns to 0.


## Error Correction Codes

We have transformed the task of proving a CI (Computational Integrity) statement into proving the validity of an execution trace that satisfies the specified polynomial constraints.

**Challenge.** A malicious prover could construct an execution trace that is mostly correct but introduces errors at a single or few specific points, potentially leading to a vastly incorrect result. The difficulty lies in detecting these rare faults with a small number of queries.

**Solution: Error Correction Codes** Polynomials can be used to generate error correction code, e.g. Reed-Solomon codes. Over a sufficiently large domain, two polynomials of degree $d$ differ at nearly all evaluation points. This property is leveraged in STARK to ensure the integrity of the execution trace.

### Why Do Reed-Solomon Codes Work in STARK?

1. **Error Amplification (Soundness):**
Errors in the original execution trace are amplified when the trace is extended to a larger domain. This ensures that invalid traces are caught with high probability.

2. **Low-Degree Testing (Completeness):**
A valid CI statement corresponds to a valid execution trace, which can be encoded as certain low-degree polynomials. If a prover submits an invalid trace or fails to satisfy the constraints, the resulting polynomial will either exceed the expected degree or deviate from the expected structure.

## Encode the Trace into a Quotient Polynomial

### Step 1. From Trace to Trace Polynomials

Assume the trace has $d$ rows. For the $j$-th column of the trace, we define the corresponding trace polynomial $f_j$ satisfies:
$$f_{j}(\omega^i)=A_{i,j}, i \in\{0,1,2,...,d-1\}$$
where $\omega$ is $d$-th root of unity.
The polynomial can be computed using the iNTT:
$$f_{j}=iNTT(evaluation, modulus, domain)$$
where:
- $evaluation=\{A_{i,j}\}_{i \in\{0,1,2,...,d-1\}}$,
- $domain=(1, \omega^1, \omega^2,...\omega^{d-1})$.

Since $f_{j}(x)$ is derived from $d$ points, its degree is at most $d-1$.

:::warning
- We extend the trace by evaluating the trace polynomial $f_j(x)$ over a larger domain $D$. The expension rate directly influences the soundness error.
- **For a Zero-Knowledge Protocol (Part II)**, the domain $D$ is shifted to $s\cdot D$ for a constant shift $s$, effectively blinding all trace data.
:::

### Step 2: From Trace Polynomials to Constraint Polynomials

Polynomial constraints ensure the validity of the trace. For example, consider the transition constraint:
$$(A_{i,2}-A_{i-1,1}-A_{i-1,2})\cdot A_{i,4}=0, i \in\{1,2,...,d-1\}.$$
This translates into the transition polynomial:
$$c(x)=(f_{2}(x)-f_{1}(\omega^{-1}x)-f_{2}(\omega^{-1}x))\cdot f_4(x)$$
The roots of $c(x)$ are:
$$\omega^i, \text{for }i\in\{1,2,...,d-1\}.$$

The degree of $c(x)$ is twice the degree of the trace polynomials, so it is at most $2(d-1)$.

### Step 3: From Constraint Polynomials to a Quotient Polynomial

**Mixing Constraint Polynomials:**
Suppose we have $l+1$ constraint polynomials $c_0,c_1,...,c_l$. We combine them into a single polynomial:
$$C(x)=\alpha^0\cdot c_0(x) +\alpha^1\cdot c_1(x)+... +\alpha^l\cdot c_l(x),$$
where $\alpha$ is a verifier selected random challenge. If each $c_i(x)$ has a root $r$, then $C(x)$ also vanishes at this root.

The degree of $C(x)$ is equal to the maximum degree of the constraint polynomials, so it is at most $2(d-1)$.

**Constructing the Quotient Polynomial:**
The prover divide $C(x)$ by the vanishing polynomial $Z(x)$, defined as:
$$Z(x)=\prod_{i=1}^{d-1} (x-\omega^i)$$
This yield the quotient polynomial:
$$Q(x)=\frac{C(x)}{Z(x)}.$$

The degree of $Q(x)$ is equal to $deg(C(x))-deg(Z(x))$, so it is at most $d-1$.

**Key Properties:**
$Q(x)$ is a low degree polynomial **if and only if**:
- The trace satisfies all polynomial constraints, i.e. each constraint polynomial vanishes at some $d$-th roots of unity ($\omega^i, \text{for }i\in\{1,2,...,d-1\}.$)
- The original CI statement is correct.

### Succinctness

The verifier can efficiently compute the following expression:
$$Q(x)=\frac{C(x)\cdot (x-1)}{\prod_{i=0}^{d-1} (x-\omega^i)}=\frac{C(x)\cdot (x-1)}{x^d-1}$$

## References
- [STARKs whitepaper](https://eprint.iacr.org/2018/046)
- [RISC0's STARK tutorial](https://dev.risczero.com/proof-system/stark-by-hand)
- [Anatomy of a STARK](https://aszepieniec.github.io/stark-anatomy/)

- StarkWare's blogs: [1](https://medium.com/starkware/stark-math-the-journey-begins-51bd2b063c71), [2](https://medium.com/starkware/arithmetization-i-15c046390862), [3](https://medium.com/starkware/arithmetization-ii-403c3b3f4355), [4](https://medium.com/starkware/low-degree-testing-f7614f5172db), [5](https://medium.com/starkware/a-framework-for-efficient-starks-19608ba06fbe)

- [STARK 101](https://starkware.co/stark-101/)