Allen

Allen

crypto seeker||starknet
HomeArchives

Summary of "Stark Technology Self-Description"

##stark##tech760
AI Translation
This post is translated from Chinese into English through AI.View Original
AI-generated summary
This text discusses how to perform Stark verification using a supermarket receipt as an example. The process involves generating a proof string Π to prove that a program A, given input x, outputs y within a time limit T. The proof is considered valid if y=1. The verification process includes checking a portion of the execution trajectory using error-correcting codes and ensuring the data integrity using polynomial commitments. Transparency and non-interactive verification are achieved using hash functions. The summary also outlines the steps involved in the verification process, such as encoding the initial execution trajectory, encoding program A using AIR, merging the polynomials, performing FRI polynomial commitments, and conducting low-degree tests. The verification involves hashing the proof data, generating random numbers, and checking the consistency between Φ and Π. Finally, the process includes conducting low-degree tests on a sampled portion of the extended execution trajectory to verify the correctness of each point.

Taking a supermarket receipt as an example, how to perform stark verification.

In fact, what needs to be done is to provide 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 possible to recompute the verification. Verification only requires sampling a portion of the execution trace, and to make the sampling effective, error-correcting code functionality needs to be utilized.

Furthermore, it is necessary to ensure the authenticity and integrity of the execution trace data. This requires the use of polynomial commitments. Fast verification can be achieved through low-degree testing, fast exponentiation algorithm, Fermat's theorem, etc.

With the above, effective verification can be guaranteed. Additionally, transparency and non-interactive verification need to be implemented, which requires the use of hash functions.

Summary of the process#

  1. 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 data of the original execution trace is only a subgroup of this field (error-correcting code, the execution trace is considered as an assignment to a polynomial over a certain field and extended on a larger field).

  2. Encode program A by using AIR (Arithmetic Intermediate Representation) and describe the constraints on the given program in the intermediate polynomial.

  3. Merge the above polynomials into one polynomial and prepare for FRI (Fast Reed-Solomon Interactive Oracle) polynomial commitment. Polynomial commitment ensures that the data cannot be modified, or any modifications can be detected. (The size of the polynomial commitment and the time complexity of generating the commitment are log(n), compared to the merged polynomial in AIR).

  4. The verifier sends randomness 𝛔₀, which allows both the prover and the verifier to "bundle" all polynomial constraints into a unified constraint on A.

  5. Hash the proof data and generate some random numbers based on the hash The prover combines the execution trace with the polynomial constraint on A to obtain 𝚵.

  6. The prover sends 𝚵 to the verifier. The verifier ensures the proper correlation between 𝚽 and 𝚵 through local consistency checks.

  7. Perform polynomial commitment. A low-degree test requires computing log(order of 𝚵, n) polynomial evaluations, and the size complexity of the commitment is also log(n). The commitment includes 𝚵 Merkle, split 𝚵 Merkle, branch paths (the selection of branch paths randomly chooses the index or r value of each sample based on the hash of the generated data in the previous proof), and the bottom-level leaf Merkle.

  8. Randomly sample n points (low-degree testing) from the expanded execution trace (long proof) based on the hash. Verify each point's correctness using non-interactive and polynomial commitment combined with the state root (low-degree testing). Obtain the polynomial commitment for each point and generate the proof in combination with the state root.

Loading...
Ownership of this post data is guaranteed by blockchain and smart contracts to the creator alone.