Zero-Knowledge with Constant Computational Overhead

For many zero-knowledge proofs and arguments, the burden of proof is on the prover. Computing proofs for large statements is a bottleneck, despite the fact that we know how to produce amazingly succinct proofs with incredibly fast verification times.

This talk will explain a 2017 work on zero-knowledge which was the first to achieve optimal proving time, up to a constant factor. The cost of computing a proof of arithmetic circuit satisfiability is a constant times the cost of evaluating the circuit.