# Prerequisites for STARKS
## Field
For a given prime number p, we can make a finite field that contains p elements; the order of the finite field is equal to p. In our case, we will restrict ourselves to the Goldilocks field, for which $p = 2^{64} - 2^{32} + 1$. For building the Brainstark VM, we will do all the multiplication and addition modulo p.

---
## Multiplicative Group
The order of a group is the number of elements in that group. In our case, we will be using the group scheme of roots of unity, and n should be the power of 2 so that we will be able to use the FRI folding scheme (explained in next [section](https://hackmd.io/@Muskan05/rJb7hejU1x#Divide-and-Conquer-Strategy)) to prove, the maximum multiplicative group order we can make equal to $2^{32}$ as our field is $2^{64}-2^{32}+1$ and for creating the sub-multiplicative group of this group we can square the generator and decrease the order by 2.
For example, for a field equal to 17, a multiplicative group of order 16 and its generator will be 3 which contains element {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16} for creating a group of order 8, generator of that group should be 9 mod 17 which is 9 and have elements {1,3,5,7,9,11,13,15}.

---
## Roots of unity
If n is a positive integer, then ‘x’ is said to be nth root of unity if the equation $x^n$ = 1 is satisfied. As a result, this equation has n roots, commonly known as the nth roots of unity.

---

## Lagrange Interpolation

Given points and evaluations ${(x_i, y_i)}_{i=0}^{d-1}$, we can construct an **interpolation polynomial** $\mathcal{P}(X)$ such that $\mathcal{P}(x_i) = y_i$:

$$
\mathcal{P}(X) := \sum_{i=0}^{d-1} y_i \cdot L_i(X),
$$

where $L_i(X)$ is the **Lagrange basis polynomial** over the evaluation domain ${x_0, \ldots, x_{d-1}}$:

$$
L_i(X) := \prod_{j \neq i} \frac{X - x_j}{x_i - x_j} \quad \text{such that} \quad
L_i(X) =
\begin{cases}
1 & \text{if } X = x_i, \\
0 & \text{otherwise.}
\end{cases}
$$

When the evaluation domain is ${0, \ldots, d-1}$, we get $L_i(X) = 1$ if $X = i$, and $0$ otherwise.
When the evaluation domain is ${\omega^0, \ldots, \omega^{n-1}}$, we get $L_i(X) = 1$ if $X = \omega^i$, and $0$ otherwise.
### Example :-
We can encode a column of values $\vec{v}$ =($v_1,...,v_n$) as its Lagrange interpolation polynomial over the evaluation domain ($w^1,w^2,....,w^n$), where $w$ is an n-th root of unity in a multiplicative subgroup of order n:
$$
V(X) =
\begin{cases}
\vec{v}[i] & \text{when } X = \omega^i, \\
0 & \text{otherwise}.
\end{cases}
$$

This lets us **shift** up and down rows by multiplying by a factor of $\omega$. For instance:

$$
V^{\text{next}}(X) = V(\omega X), \quad V^{\text{prev}}(X) = V(\omega^{-1} X).
$$

## Schwartz-Zippel Lemma

The Schwartz–Zippel lemma is used to check whether two polynomials are identical or not. More specifically, it helps us determine whether a polynomial is a zero polynomial. However, we can also use it to check the equality of two polynomials. For example, if $p(x)$ and $q(x)$ are two polynomials that are identical, then $p(x) - q(x) = 0$ when evaluated at any random value of $x$.
We will explain it further with some examples:
Examples

1. $p(x) = x + 6$ and $q(x) = x + 6$

2. $p(x) = -x + 6$ and $q(x) = x + 6$

4. $p(x) = x + 3$ and $q(x) = x + 6$

When we take two linear polynomials, there are three possibilities:

* They are identical and overlap completely
* They intersect at one point
* They do not intersect at all

Now, let's look at cases involving a line and a curve:

1. $p(x) = x^2$ and $q(x) = x + 6$

3. $8p(x) = (x + 8)^2$ and $q(x) = x + 6$

5. $p(x) = (x + 8)^2$ and $q(x) = x + 6$

When we take a line and a curve, there are three possibilities:

* They intersect at two points
* They intersect at one point (tangentially)
* They do not intersect at all

**Observation**
From these examples, we observe that if two polynomials $p(x)$ and $q(x)$ are not equal, they will intersect at most $d$ points, where $d = \max(\deg(p), \deg(q))$.
Now, let us calculate the probability of two polynomials evaluating to the same value at a random point. Suppose we select a domain $D = 17$ containing the elements ${0, 1, 2, 3, \dots, 16}$, over which these polynomials are defined.
For the polynomials $p(x) = x^2$ and $q(x) = x + 6$, they are equal at exactly two points. Hence, the probability is:
$\Pr[p(x) - q(x)] = \frac{2}{17} \approx 11.7$%
However, if the size of the domain increases significantly (e.g., $D = 2^{64}$), the probability of randomly choosing a root becomes extremely small. This means that for a large domain, if two polynomials evaluate to the same value at a random point, they are highly likely to be equal.

---
## Hashing
Hashing is the process of processing raw information to the extent that it cannot reproduce it back to its original form. It takes a piece of information and passes it through a function that performs mathematical operations on the plaintext. This function is called the hash function, and the output is called the hash value. For now, we are going to use SHA256, which will give a 256-bit hash value when processed through the hash function. 

---

## Merkle Tree
Merkle tree, also known as hash tree, is a data structure used to verify and store large datasets. The leaf node represents the data that we want to store or verify, and all the non-leaf nodes are the hash of their child nodes. The root node will be the hash of the entire tree.

Merkle trees are widely used in distributed systems like blockchain, where secure data verification is needed. They allow for compact proofs of data integrity (Merkle proofs) without needing access to the entire dataset.
For example - for the proof of leaf node $m_3$ we only need to give 3 extra nodes {$H(m_4), H(h_1,h_2), H(h_{54},h_{78})$} after computing the root of merkle tree from these nodes, we will equate the root with the proof root for verification of the proof.

---

## Commitment
A polynomial commitment scheme (PCS) is a cryptographic primitive that allows a prover to commit to a polynomial and later prove the evaluation of that polynomial at a given point. This scheme ensures both integrity and privacy, integrity because the polynomial remains consistent, and privacy is ensured because we are not revealing the polynomial itself.
### Expanded domain
If we have to commit a polynomial first of all we have to evaluate that on the expanded domain, that domain is just expanded by the expansion factor and offset of evaluation domain on which we have interpolated the polynomial.
* **Expansion factor** - The expansion factor is used to increase the error distance. In simpler terms, if two polynomials differ at a certain number of points over a certain domain, then if we expand the evaluation domain, the probabilty of these points with respect to the entire domain decreases, or the probability of the polynomials being equal if they equate at a single random point's evaluation, increases (recall [Schwartz-Zippel Lemma](https://hackmd.io/@Muskan05/rJb7hejU1x#Schwartz-Zippel-Lemma)).
* **Offset** - We don’t want to reveal actual value of polynomial evaluation that’s why we shift the evaluation domain by offset factor.

### Polynomial commitment scheme in the Fri-protocol:
Initially, we compute the polynomial through the Lagrange interpolation of the trace of the input, and then we evaluate that polynomial on the expanded domain, this process of evaluation gives rise to Reed-Solomon codewords of length equal to the length of the expanded domain.
The scheme consists of three algorithms:
1. Commit all the polynomial evaluations on the expanded domain to the Merkle tree.
2. Open, which produces a proof that f(z)=y for some z and for the polynomial f(x) that matches with the given commitment;
3. Verify, which verifies the proof produced by open. 
FRI is a protocol between a prover and a verifier, which establishes that a given codeword belongs to a polynomial of low degree. Without losing generality, the prover knows this codeword explicitly, whereas the verifier knows only its Merkle root and leaves of his choice, assuming the successful validation of the authentication paths that establish the leaf's membership to the Merkle tree.
---
# STARKS

We have introduced all the prerequisites necessary to understand the STARK protocol, as we have to prove the brainfuck ISA using the STARK protocol. Therefore, it is essential to know the STARKS and the FRI protocol. Before explaining the stark engine of ZKVM, we will explain Starks with the help of a simple example and share the corresponding Rust code.
We will be taking a simple example of the Fibonacci Square Sequence as

        $a_{n+1}= a_{n+1}^2+a_{n}^2$
The statement which we need to prove is as follows:
For the FibonnaciSq mod 3221225473 with $a_0$=1 and $a_1$=x we have $a_{1022}$= 2338775057
Prover knows that x= 3141592, we have to prove to the verifier that the $a_{1022}$ is indeed equal to  2338775057, given $a_0$=1 and that the sequence follows the FibonacciSq sequence, without revealing the value of x.
Stark protocol will be divided into 3 parts:-

---

## **Part 1**
### **Low degree extension(LDE)**
1. Generate the trace from the given value of $a_0$ and $a_1$ with the fibonacciSq equation, we choose the g- element from F such that {$1,g,g^{1},g^{2},..g^{1023}$}, that forms a multiplicative group of order 1023, this g must be the 1024th root of unity i.e. $g^{1024}=1$.
2. Interpolate the polynomial using [Lagrange interpolation](https://hackmd.io/@Muskan05/rJb7hejU1x#Lagrange-Interpolation) 
Such that $f(g^{i})=a_i$
3. Now we will evaluate the polynomial f(x) on a larger expanded domain(8k) (intially it have evaluation domain equal to 1024 , now expanded domain have 8192 elements it means expansion factor is 8 and offset factor is w) which have generator h, then collect the Reed-Solomon codewords as:
$f(w)$,$f(w.h)$,$f(w.{h^2})$,$f(w.h^3)$,....
### **Commitment**
We will commit all the Reed-Solomon codewords in the Merkle tree and send the Merkle root to the verifier as


---

## Part 2
### Polynomial constraints on the trace
There are total of three constraints that we need to apply to the polynomial f(x) generated by the trace.
-    $a_0$ = 1
-    $a_{1022}$ = 2338775057
-    $a_{n+2}$ = $a_{n+1}^2$+$a_{n}^2$
That we can show in polynomial form as:
- f(x) =1, for x = $g^{0}$
- f(x)=2338775057, for x = $g^{1022}$
- $f(g^2. x)$ = $f(g.x)^2$ + $f(x)^2$ , for x = $g^i$ , 0 ≤ i ≤ 1020
If f(x) satisfies all 3 constraints that implies that the statement is true.

### **Converting Constraints to the Roots**

The constraints for the polynomial $f(x)$ are:
- $f(x) - 1 = 0$, for $x = g^0$, hence root: $g^0$
- $f(x) - 2338775057 = 0$, for $x = g^{1022}$, hence root: $g^{1022}$
- $f(g^2x)^2 - f(gx)^2 - f(x)^2 = 0$, for $x = g^i$, $0 \leq i \leq 1020$, hence roots: $g^i$ for $0 \leq i \leq 1020$

---

### **Converting Root form to Rational Function**

  **Theorem**: $z$ is a root of $p(x)$ if and only if $(x - z)$ divides $p(x)$.
  **Definition**: $(x - z)$ divides the polynomial $p(x)$ if $p(x)$ divided by $(x - z)$ is also a polynomial.

According to the theorem, we convert our polynomial to the rational function as:

1. $g^0$ is a root of $f(x) - 1$:
$$
\frac{f(x) - 1}{x - g^0}
$$
is a polynomial.

2. $g^{1022}$ is a root of $f(x) - 2338775057$:
$$
\frac{f(x) - 2338775057}{x - g^{1022}}
$$
is a polynomial.

3. $g^i$ ($0 \leq i \leq 1020$) are roots of $f(g^2x)^2 - f(gx)^2 - f(x)^2$:
$$
\frac{f(g^2x)^2 - f(gx)^2 - f(x)^2}{\prod_{i=0}^{1020}(x - g^i)}
$$
is a polynomial.

---

**Nth Root of Decomposition**

- According to the $n$-th root of decomposition:
$$
\prod_{i=0}^{1023}(x - g^i) = x^{1024} - 1
$$

- Fix:
$$
\frac{f(g^2x)^2 - f(gx)^2 - f(x)^2}{(x^{1024} - 1) / [(x - g^{1021})(x - g^{1022})(x - g^{1023})]}
$$

Now, the three rational functions will look like this:
1. $p_0(x)=\frac{f(x) - 1}{x - g^0}$
2. $p_1(x)=\frac{f(x) - 2338775057}{x - g^{1022}}$
3. $p_2(x)=\frac{f(g^2x)^2 - f(gx)^2 - f(x)^2}{(x^{1024} - 1) / [(x - g^{1021})(x - g^{1022})(x - g^{1023})]}$

If we can prove that all 3 rational functions will be a polynomial that implies our statement will be true.
Instead of proving 3 different polynomials separately, we will calculate a composition polynomial as a random linear combination of all three polynomials, that random value will be supplied by the verifier. We will construct composition polynomial as CP:-

Verifier supplies $\alpha_0$,$\alpha_1$, and $\alpha_2$
   **$CP=\alpha_0.p_0(x) + \alpha_1.p_1(x)+\alpha_2.p_2(x)$**
if this composition polynomial is a polynomial that implies all the three polynomial will also be a polynomial.
## Part 3
### **FRI-Commitment**
1. Instead of proving that the composition polynomial is a polynomial we will prove that CP is close to a low-degree polynomial. Distance is defined as
Distance between a function f: D-> F to a polynomial p:

$$D(f, p) := \# \text{ points } x \in D \text{ such that } f(x) \neq p(x)$$

**Proximity**
A function f: D → F is close to a polynomial p if: D(f,p) is small.

We will use **Fast Reed-Solomon Interactive Oracle Proofs of
Proximity** to prove that the CP is close to a low-degree
polynomial.

CP is close to a polynomial of a degree<1024, where domain
size =8192

2. We can explain **FRI-protocol** with a general polynomial defined as :
$$
f(x) = \sum_{i=0}^d c_i X^i
$$
where $d$ is the maximum degree of the polynomial, and $D$ will be the evaluation domain. This is a multiplicative subgroup of order $N$. We will generate this order with $w$ such that it is the $N$th root of unity, i.e., $w^N = 1$, and
$$
D = \{1, w, w^2, \dots, w^{N-1}\}.
$$

The codeword, which we will commit in the Merkle tree, is:
$$
\{f(w^i)\}_{i=0}^{N-1}
$$
for $f(x)$, which corresponds to the evaluation domain $D$.
#### Divide and Conquer Strategy
Following the **divide and conquer strategy** of the [Fast Fourier Transform](https://www.youtube.com/watch?v=h7apO7q16V0&ab_channel=Reducible
), this
polynomial is divided into even and odd terms as:

$$
f(X) = f_E(X^2) + X \cdot f_O(X^2)
$$

where

$$
f(-X) = f(X^2) - X \cdot f_O(X^2).
$$

#### **Requirements for Divide and Conquer**

To apply the divide-and-conquer algorithm:
1. $d$ must be in the form $2^k - 1$ for $k \in \mathbb{N}_+$.
2. The number of possible even or odd terms is given by:

$$
f_E(X^2) = \frac{f(X) + f(-X)}{2} =\sum_{i=0}^{\frac{d+1}{2} - 1} c_{2i} X^{2i} \quad$$
$$
f_O(X^2) = \frac{f(X) - f(-X)}{2X}=\sum_{i=0}^{\frac{d+1}{2} - 1} c_{2i+1} X^{2i} \quad
$$

Here, the degree $d$ is:

$$
\frac{d+1}{2} - 1.
$$

#### Correctness of the Decomposition
The correctness of the decomposition can be observed as follows:

- When computing $f_E(X^2)$, all the odd terms cancel out.
- When computing $f_O(X^2)$, all the even terms cancel out.

The key step in this protocol is to derive a new codeword from the computed odd and even polynomials as:

$$
f^*(X) = f_E(X) + \alpha \cdot f_O(X),
$$

where $\alpha$ is a random scalar supplied by the verifier.

---

#### Example
Consider the polynomial:

$$
P_0(x) = 5x^5 + 3x^4 + 7x^3 + 2x^2 + x + 3.
$$

Using the divide-and-conquer strategy, we divide it into:

1. **Even Terms** ($g(x^2)$):
$$
3x^4, \, 2x^2, \, 3
$$

2. **Odd Terms** ($xh(x^2)$):
$$
5x^5, \, 7x^3, \, x
$$

Repeating this, we get:
$$ g(x^2)->g(y) = 3y^2+ 2y+3,$$

$$ x.h(x^2)->h(y)=5y^2+7y+1$$

$$
P_1(y) = g(y) + \beta h(y)= 3y^2+ 2y+3+\beta (5y^2+7y+1)=(3+5\beta )y^2+(2+7\beta )y+(3+\beta)
$$

where $g(y)$ and $h(y)$ are further simplified.

---

**Effect on Evaluation Domain on decreasing the degree by half**

Let $D^*$ be the evaluation domain of $f^*(x)$. $D^*$ is generated by $w^2$, and it's half the length of $D$. The codewords for $f^*(x)$, corrseponds to $D^*$ are:

$$
\{ f^*(\omega^{2i}) \}_{i=0}^{N/2 - 1}.
$$
Expanding $f^*(X)$ gives:

$$
\{ f^*(\omega^{2i}) \}_{i=0}^{N/2 - 1} = \{ f_E(w^{2i}) + \alpha \cdot f_O(w^{2i}) \}_{i=0}^{N/2 - 1}.
$$

Substituting for $f_E(X^2)$ and $f_O(X^2)$, we get:
$$
\{ f^*(\omega^{2i}) \}_{i=0}^{N/2-1} =
\left\{
\frac{f(\omega^i) + f(-\omega^i)}{2} +
\alpha \cdot \frac{f(\omega^i) - f(-\omega^i)}{2\omega^i}
\right\}_{i=0}^{N/2-1}
$$

$$
= \left\{
2^{-1} \cdot
\left(
(1 + \alpha \cdot \omega^{-i}) \cdot f(\omega^i) +
(1 - \alpha \cdot \omega^{-i}) \cdot f(-\omega^i)
\right)
\right\}_{i=0}^{N/2-1}
$$

Since the order of $\omega$ is $N$, $\omega^{N} = 1$, and therefore

$$
f(-\omega^i) = f(\omega^{N/2 + i}).
$$
This substitution makes it clear that even though the index iterated over half the range (from 0 to N/2-1 ), all points of $\{ f^*(\omega^{i}) \}_{i=0}^{N - 1}$ are involved in the derivation of $\{ f^*(\omega^{2i}) \}_{i=0}^{N/2 - 1}$. It does not matter that the latter codeword has half the length or its polynomial has half the degree.

---
Now we are able to describe the mechanism of FRI-Protocol:

**Applying the FRI Protocol**

1. The prover commits to $f(x)$ by sending the Merkle root of its codewords to the verifier.
2. The verifier sends a random challenge $\alpha$.
3. The prover computes $f^*(x)$ and commits it by sending the Merkle root of $f^*(x)$, evaluated on $D^*$, to the verifier.

This process is repeated iteratively, halving the polynomial degree until it reduces to a constant polynomial.

---
3. We have explained the FRI protocol in detail. Now, we can demonstrate how to apply this FRI protocol to our specific statement.
CP is close to a polynomial of a degree <1024 where domain size=8192
Now we can apply FRI protocol and form a new polynomial by a similar divide and conquer strategy and the verifier supplies the alpha
Now, we need to prove that the new polynomial is close to a polynomial of a degree<512 where domain size=4096 and we will apply this step until we get a constant polynomial and also commit the last term.

---
### Decommitment

1. Untill now, we have seen how we commit all the polynomials, CP and FRI layers. Now, we will see how we decommit on the query of the verifier to convince the verifier.
The list of commitments is as follows:

[Trace root ,$CP$ root, $CP_1$ root, $CP_2$ root,....., $CP_{10}$ root]

Now the verifier sends q random element and the prover gives decommitment for all queries.
Verifier convinces step by step:
**Step 1**:- Prover provides
$$
f(x) + path,$$

$$f(g.x) + path$$

$$ f(g^2.x) + path$$

$$ cp_0(x) + path$$

After getting all these values verifier checks that $cp_0(x)$ is formed according to given constraint or not.
**Step 2**:- Prover provides
$$ cp_0(x) + path$$

$$ cp_0(-x) + path$$

verifier knows the beta supplied at that layer and cp in next layer connected to it’s first layer as $$ cp_{i+1}(x^2)= g(x^2)+\beta h(x^2)$$
And we can obtain the odd and even term as

$$
\begin{aligned}
CP_i(x) &= g(x^2) + xh(x^2) \\
CP_i(-x) &= g(x^2) - xh(x^2) \\
&\Rightarrow
\begin{cases}
g(x^2) = \frac{CP_i(x) + CP_i(-x)}{2}, \\
h(x^2) = \frac{CP_i(x) - CP_i(-x)}{2x}.
\end{cases}
\end{aligned}
$$

We can check the consistency between $cp_1(x)$ and $cp_0(x)$ by the above relation. Similarly, the verifier checks for all 10 layers, the last layer must be constant.
Similarly, the prover provides data for all q queries raised by the verifier.

---

# Fiat Shamir
So far, we have explored how to construct a Stark protocol using a simple example. However, we have observed that the FRI protocol is interactive and requires verifier's constant involvement, we can use Fiat-Shamir algorithm to convert interactive proof system to non-interactive proof system.
We leverage a random deterministic value derived from the trace root—specifically, 64 bits of the trace root—as input to compute $\alpha_0$, $\alpha_1$, and $\alpha_2$ for the CP polynomial. This approach eliminates the need for an interactive verifier while ensuring that the generated value is random and deterministic. As a result, the prover cannot manipulate or cheat the proof since the Merkle root guarantees randomness. In successive steps, we can also use all data that have been collected to produce that random value.

---
We have seen an overview of STARKS and its pre-requisites. The [next blogpost](https://hackmd.io/@Muskan05/r1Q8_I0Uke) will discuss Plonk Arithmetization and Arguments, which will later be used in our zkVM.