There have been rumors recently that Stark is going to issue coins! It is a very wise choice to issue coins when the market is doing well.
Here, I want to review the basic technical principles of Stark. I have been recording them intermittently before, and now I will organize them here (although it is still a bit messy).
Computational Integrity#
Computational Integrity ensures that the output of a calculation is correct.
Step 1: Arithmeticization#
Generating Execution Traces#
The execution trace is actually a list, where each row represents a computational step.
Express the execution trace as a polynomial.
Expand the polynomial to a larger field.
Polynomial Constraints#
Polynomial constraints ensure that all polynomial constraints are satisfied only when the execution trace represents a valid computation.
Use polynomial constraints to transform it into another polynomial, such that it is a low-degree polynomial only when the execution trace of the new polynomial is valid.
The work of the Verifier mainly includes two tasks:
- Querying the synthesized polynomial at a random position.
- Based on these queries, checking if the polynomial is low-degree.
Succinctness#
There is still one work that has not been completed, which is the "S" in STARK, succinctness. Succinctness consists of the following two parts:
- Using a small number of queries.
- Completing very few calculations for each query.
During the query, the calculation amount can be reduced by using the method shown in the figure below. By utilizing the characteristics of this group, we treat the execution trace as the evaluation of a polynomial on a subgroup of the field, and the polynomial constraints for evaluation are about this subgroup. This reduces the verification time of the Verifier to logarithmic order. With this feature, we can construct more complex execution traces, but the constraints must be consistent with a subgroup of the field.
Mathematical Background:
Integer Modulo n Multiplicative Group#
Multiplicative inverse
Modular arithmetic
Fermat's Little Theorem
Extended Euclidean Algorithm
Montgomery Algorithm
Fast Fourier Transform
Low-degree testing - FRI algorithm
zk-STARK proof approach
- Each step of the program corresponds to a value, and all the steps together form a computation trace, which corresponds to a polynomial P(n).
- Each step of the computation trace generates a constraint C(p) = 0.
- Combine the trace polynomial and the constraint polynomial to obtain D(x) = C(p(x), p(x-1), ...).
- The combined polynomial D(x) is zero at each step of the computation trace, which means it has roots Z(x) = (x-x1)(x-x2)...(x-xn).
- Use the FRI algorithm to perform low-degree testing on the polynomial T(x) = D(x)/Z(x).