This is the fifth week of the zkEVM Bootcamp by Encode.
Reed Solomon Codes
It is a set of length n vectors (codewords), where the elements of the vector (symbols) consist of m binary digits. The only restriction is that n must be no larger than 2m. We can tolerate errors in our codeword and be able to reconstruct the information from the received vector.
Our message is encoded as coefficients in a polynomial of degree d: A = a0, a1, …ad-1 over a finite field and we add redundancy by producing the evaluations of that polynomial at certain points. With Fast Fourier Transforms we can compute evaluations of polynomials.
Computational Integrity
Prove that some computation has been done correctly. Succinctness is important: the time to verify to be substantially less than the time to execute the computation.
In Starknet, computational intergity is more important than zero knowledge, all data on Starknet is public.
STARK Arithmetisation
STARKS are transparent, so there’s no hidden information, no toxic waste and don’t require an MPC ceremony. The underlying cryptographic assumption is that we can use a collision resistant hash function. This means that STARKS are quantum secure. Process:
- Computation
- Arithmetisation
- Polynomial IOP
- Cryptographic proof system
We need to go from the trace of our program, to the proof. The first part involves taking our trace and turning it into a set of polynomials (arithmetisation). Then the prover attempts to convince the verifier that the polynomial is of low degree (=only true if the original computation is correct).
Arithmetisation in 2 steps
- Generating an execution trace (for each step of the computation) and polynomial constraints (how we described what a correctly running program will look like). The constraints are decided as part of the initial setup and both prover and verifier agree upon.
- Transforming these 2 objects into a single low-degree polynomial
The Arithmetic Intermediate Representation (AIR)
FRI Background
Fast Reed-Solomon IOP of Proximity, is a protocol that establishes that a committed polynomial has a bounded degree.
- Commitment: the prover, wants to show that their pointr come from a low-degree polynomial, sends a commitment to verifier. This is a Merkle root of the polynomial’s evaluation
- Decomposition: even-odd, left-right etc.
- Proof Generation:
- Verification: checks the Merkle proofs and uses the to ensure that the decomposed polynomials are consistent with the original polynomial.
Built on Split and Fold Technique
We take a polynomial and split it out, to get polys of lower degree. Then both claims are merged into one using random weights. After many steps we end up with a constant. This is going to have quickly because the polynomials are from lower degree.
STARKNET
Provable code is the next iteration of distributed computing.
Cairo – CPU Air: one verifier, universal and turing complete.