Zero knowledge proofs
ZKP for scaling in StarkWare FB post: The Cambrian explosion of Zero-Knowledge proof systems for verifying computation. AFAIK the first time ZKPs are used for scaling txns per second. Allowing nodes to verify proofs instead of re-executing the computation.
https://github.com/starkware-industries/stark101
- prove that 1023rd element of the fibonacci sequence is X
- Low degree extension, evaluate poly at 8k points, commit to it with merkle tree
- f(x) is the trace of computing the 1023rd element
- constraints on f(x) are satisfied, iff the constraints are rational polys
- combine them by taking a linear combination, this is the composite poly (CP), commit to it
- show that CP is a polynomial, instead prove that it is close to a poly of low degree using FRI
- receive random beta, apply FRI operator, commit, repeatedly, then send result to verifier
- prove that f is close to a poly degree < D -> apply FRI -> prove that f’ (half the domain) is close to poly degree < D/2
- FRI splits the poly into even and odd powers, then use random vector to add then together
- apply FRI until we get to a poly bounded by degree 1, a constant
- verifier sends x (do this q times)
- prove that CP is computed from trace, prover sends f(x), f(gx), f(g^2x), and cp_0(x), verifier recompute cp_0(x)
- prove that each FRI poly computed correctly, prover sends cp_0(x), cp_0(-x), cp_1(x^2), verifier recompute cp_1(x^2)
- prover sends cp_1(-x^2), verifier compute cp_2(x^4) and so on
Vitalik explains STARKS