Non-interactive zero-knowledge proofs for general NP statements are a powerful cryptographic primitive. Recent work has achieved theoretical constructions and working implementations of zero-knowledge proofs that are short and easy to verify.
Alas, all prior implementations suffer from severe scalability limitations: the proving key's size and the prover's space complexity grow with the size of the computation being proved.
The bootstrapping technique of Bitansky et al. (STOC 2013), following Valiant (TCC 2008), offers an approach to scalability, by recursively composing proofs, but it has never been realized in practice, due to enormous computational cost.
In this work, by leveraging new elliptic-curve cryptographic techniques, we achieve the first practical implementation of recursive proof composition, and thereby achieve the first implementation of *scalable zero knowledge*.
Joint work with Eli Ben-Sasson, Eran Tromer, and Madars Virza.