Melvin's digital garden

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.

  • 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

Links to this note