Stark can be described in 5 steps in a high level:
- Computation program
- generate an execution trace and a set of polynomial constraints, AIR (Algebraic Intermediate Representation) (no circuit)
- Transfer the execution trace to be a polynomial, extend it to a larger domain
- compute the composition polynomial, which is the quotient polynomial \(q(x)=\frac{constrain \ systems}{vanishing \ polynomial}\)
- if prover is honest, \(q(x)\) should be a low degree polynomial. Using FRI protocol, to test \(q(x)\)
The steps in
https://papers.ssrn.com/sol3/papers.cfm?abstract_id=4308637
- computation statement, define the field
- Arithmetication
- Evaluating Trace as a polynomial, the degree \(d\) is the same with the number of trace points.
- evaluate the polynomial in a large domain \(L\), to create a Reed soloman error correction code
- apply constraint to polynomial
- create the composition polynomial
- commitment round: prover commits to the composition polynomial, commit to the folded polynomial (has \(\alpha\))
- Query round: verifier query the evaluation of the original polynomial on the original group \(z, -z\), use it to calculate the evaluation of the folded polynomial on \(z^2\). query this value for the merkle tree of folded polynomial, compare if the value are the same