Asymptotically linear-time provers are the subject of one very promising thread at the forefront of zero-knowledge and verifiable computing research. These zk-SNARK systems can prove correctness of an execution, producing a succinctly verifiable certificate, with only a constant factor overhead over the work required to check the execution directly. Several exciting works, beginning with Spartan, achieve linear-time proving by combining multilinear polynomial IOPs with a multilinear polynomial commitment schemes. The work of Brakedown notably instantiates a multilinear polynomial commitment using only hash functions and some remarkable properties of linear error-correcting codes. These codes, widely used to ensure data integrity, are now, fascinatingly, a key ingredient of many modern zk-SNARK systems offering computational integrity.
The Brakedown SNARK isn't just asymptotically linear, it’s also concretely very fast. On the other hand, Brakedown’s verifier is relatively slow, and its proofs relatively large. This has naturally led to protocols like Orion and Orion+ which recursively verify Brakedown-style proofs to reduce the overall verification time and proof size. In this setting of proof composition, the verification complexity of the inner proof translates directly to the time to generate the outer, recursive proof.
Brakedown’s security stems from a mathematical result, first published in the paper Ligero, concerning a procedure which tests whether a set of vectors are all in close proximity to codewords by testing a random linear combination. In our new research paper, Proximity Testing with Logarithmic Randomness, we establish the security of a new proximity test which consumes exponentially less randomness than the standard test, at the cost of just a small increase in the probability of a false positive. Applying our theorem to the Brakedown polynomial commitment scheme, we immediately reduce that scheme’s proving time and verification time by approximately half, and proof size by up to a factor of \(\sqrt{2}\), for large polynomials. We furthermore improve the verification complexity of recursive proofs like Orion.
The full article, Proximity Testing with Logarithmic Randomness, is available on ePrint.
