Taking a supermarket receipt as an example, how to perform stark verification.
The goal is to provide a program A, input x, output y, and time limit T, and generate a proof string Π to prove that "A(x) outputs y within T computation steps", where y=1 is a valid proof.
Firstly, it is not feasible to recompute the entire process. Verification only requires sampling a portion of the execution trace, which can be achieved by utilizing error-correcting codes.
Furthermore, it is necessary to ensure the authenticity and integrity of the execution trace data. This can be achieved by utilizing polynomial commitments. Fast verification can be achieved using low-degree testing, fast exponentiation algorithms, and Fermat's theorem.
With the above techniques, effective verification can be ensured. Additionally, transparency and non-interactive verification can be achieved by utilizing hash functions.
Summary of the process:
-
Obtain the initial execution trace (supermarket receipt) by encoding (A, x, y, T). Encode the execution trace to form a T-step execution trace and encode it using polynomials to obtain Φ. Expand the execution trace, for example, by 10 times, and choose a larger field. The original execution trace data is only a subgroup of this field (error-correcting codes, treating the execution trace as an assignment to a polynomial over a certain field and extending the execution trace by assigning the polynomial over a larger field).
-
Encode program A by using AIR (Arithmetic Intermediate Representation) and intermediate polynomials to describe the constraints on the given program.
-
Merge the above polynomials into one polynomial and prepare for FRI (Fast Reed-Solomon Interactive) polynomial commitment. Polynomial commitment ensures that the data cannot be modified, and any modifications can be detected. The size and time complexity of the commitment are logarithmic in n, compared to the merged polynomial from AIR.
-
The verifier sends randomness 𝛔₀, which allows both the prover and verifier to "bundle" all polynomial constraints into a unified constraint on A.
-
The prover constructs 𝚵 based on the execution trace and the polynomial constraint on A.
-
The prover sends 𝚵 to the verifier. The verifier performs local consistency checks to ensure that Φ and 𝚵 are appropriately related.
-
Perform polynomial commitment. A low-degree test requires computing logarithmically many polynomial evaluations, and the size complexity of the commitment is also logarithmic in n. The commitment includes 𝚵 Merkle tree, split 𝚵 Merkle trees, branch paths (the selection of branch paths is based on the previously generated data's hash, randomly selecting the index or r value for each sample), and the bottom-level leaf Merkle tree.
-
Randomly sample n points from the expanded execution trace (long proof) based on the hash. Verify each point's correctness using non-interactive and polynomial commitment-based verification (low-degree testing). Obtain polynomial commitments for each point and combine them with the state root to generate the proof.