The zk-STARK is a proof zero-knowledge proof system that, in contrast to the zk-SNARK, no longer relies on a trusted setup where the "toxic waste" parameters are initialized.
What are, in layman's terms, the basic building blocks of the zk-STARK, and how do they work?
The STARK is a Zero-Knowlege proof system that is transparent. In other words, the prover and verifier didn't need to use a third generated parameters to produce the proof and check the validity of the claim, respectively. Conversely, it would be a lack of security in zk-SNARK systems (these schemes are based on Common Reference Strings (CRSs)).
Let there is a data center to answer the users' queries. For instance, in the CODIS system which is addressed by the STARK whitepaper, verifiers want to know whether a specific DNA profile exists in the FBI data center or not (to prevent further crimes by quickly identifying recidivists). In this term, it is so important for this data center to not only decrease the complexity of executing the protocol for each query but also be secure under the attack of a third trusted party (revealing the information and compromising the privacy by using the Master Key).
Suppose there are 1 million DNA profiles and the data center as a prover wants to produce just a proof for all profiles to convince the verifier. A crazy solution would seem to be the data center produce a proof for each profile but it is not efficient (i.e. doubly efficient). Regarding the Reed-Solomon (RS) error-correcting codes, the prover is able to obtain the encoded function corresponding to all DNA profiles. For each RS code, $RS[F, S, \rho]$ is the family of functions $f: S\to F$ which these functions are evaluations of polynomials of degree less than $\rho|S|$. Precisely, the output of encoding is a polynomial which the prover claims if the verifier put each DNA profile in this polynomial as input the output is equal to zero (i.e. is a root of a low-degree polynomial). The significant point is that the verifier never knows any information about the rest of the profiles.
But as you know, this is not enough for the verifier to check whether the claimed function is good or bad! I mean regarding the Schwartz-Zipple lemma two distinct polynomials with degree $d$ have at most d intersections so the function $f$ is not unique for 999.999 DNA profile. Moreover, the verifier needs to check all profiles to become sure about the validity of function (i.e is a low-degree polynomial). The way that is addressed by the authors of the STARK whitepaper is the FRI (Fast Fourier Transform Reed Solomon Interactive Proximity of Testing) scheme. It is a solution for solving the low-degree proximity testing problem. This scheme tried to reduce the number of elements in the set of S step by step to convince the verifier just by checking the low degree polynomial for a smaller polynomial instead of the original structure. (The degree of polynomial chooses less than the number of profiles to provide better soundness, for instance, a polynomial with degree 10.000 for 1 million DNA profiles)
The FRI scheme is based on Interactive Oracle Proof (IOP) systems which the verifier selects some random numbers and the prover provides corresponding oracle access for him/her. Finally, after some rounds, the verifier can decide about the correctness of the prover claim. It is possible to provide non-interactive IOP, also.
The critical point is about the arithmetization in which the prover wants to produce a proximity testing problem corresponding to a circuit satisfiability problem. In other words, the prover and verifier agree for a circuit to prove and check the validity of the execution of it, respectively. This term is based on some techniques to make to solve the problem in logarithmic complexity instead of NP-complete (3SAT is an NP problem). I just mention these techniques here and if you need to know more send a comment.
The circuit satisfiability $\to$ algebraic constraint satisfaction problem (CSP) $\to$ 3SAT $\to$ 3-Coloring problem $\to$ de-Bruijn Graphs to solve 3 coloring problem and so on.
For more information: https://www.starkware.co/ https://vitalik.ca/
zkSTARK in an argument of knowledge system for an NP-complete computational integrity relation which satisfies the following properties:
While the details of the exact construction are complicated, the overarching idea is to construct an interactive argument system where the verifier is granted the freedom to probabilistically query the prover's messages rather than reading them in their entirety. This type of protocol is called an interactive oracle proof (IOP). If all the verifier's queries are generated from a uniform distribution, then an IOP can be made non-interactive using the Fiat-Shamir heuristic. The main innovation of zkSTARK is (1) the reduction of computational integrity to certain statements about Reed-Solomon codes, and (2) the construction of a very efficient IOP for the formerly mentioned statements.
