Welcome back, fellow zk-enjoyer.
In the last post, we used polynomials as a data structure and verified them with a single number (Schwartz-Zippel, remember?). But there’s a question that should be bugging you: “how do we do this efficiently?”
The answer is called “roots of unity.” I promise the idea is simpler than the name suggests, and it’s what makes ZK proofs better (about 50,000 times better, for a typical ZK circuit, terms and conditions may apply [TM]).
(more…)