resource
https://starkware.co/stark-101
low degree polynomials extension
interpolate the trace points into a polynomial in a small domain, then extend the domain, evaluate the interpolated polynomial into the bigger domain
Prime Field: a field created by module a prime number, remove 0 from it, then it is a cyclic group, a multiplicative group
the order of the group is p-1
any subgroup has an order that divides p-1
The trace polynomial needs to be evaluated on a larger domain to create a reed-solomon code
How to generate a group of order k in a prime field of order p-1?
Key: when \(k\) divides \(|\mathbb{F}^\times|\), \(g^k\) generates a group of size \(\frac{\mathbb{F}^\times|}{k}\)
If I want to generate a group of order \(k\)
– find a group generator \(g\)
– \(g^{\frac{\mathbb{F}^\times|}{k}}\) will generate the group we want
How to extend the group to be of order \(8k\), for example?
-find a group \(H\) with generator \(g^{\frac{\mathbb{F}^\times|}{8k}}\)
-Multiply each of the the elements in \(H\) with the generator of \(\mathbb{F}^\times\)
Correction of your illumination
polynomial evaluated in a small domain at the beginning
polynomial evaluated in the extended domain, it is more like interpolating more points between, instead of evaluating the polynomials in more points afterwards
note: polynomial in the pictures are lines for illumination purpose, in real they are not because the polynomial will modular \(p\)
send merkle tree root, the leaves are evaluations of the polynomial in this large domain
Polynomial Constrains
- Start by specifying the constraints we care about (the FibonacciSq constraints).
- Translate the FibonacciSq constraints into polynomial constraints.
- Translate those into rational functions that represent polynomials if and only if the original constraints hold.
Rational functions:
Rational functions are functions that can be expressed as the ratio of two polynomial functions. In other words, a rational function
f(x)=a(x)/b(x)
commit to the composition polynomial
The composition polynomial is already a combination of the quotients polynomials
FRI Commitment
The proof
what are committed:
decommitment
collection of your illumination
some resources talk about repeat the FRI protocol many rounds to get the desirable security level, some resources talk about get enough query points to get enough security level
