GKR protocol

A public-coin interactive proof for any language computable by a log-space-uniform boolean circuit of depth $d$ on inputs of length $n$, with a polynomial-time prover, a verifier running in time $n\cdot \mathrm{poly}(d,\log n)$, and $\mathrm{poly}(d,\log n)$ communication.

TODO: syntax and security definition.

Participates in

Barriers

• No reduction from Fiat-Shamir + GKR to SNARK