Ben Diamond and Jim Posen
May 4, 2023

Proximity Testing with Logarithmic Randomness

Our new result in error-correcting codes yields a 2x zk-SNARK speedup

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.

RELATED POSTS

Ulvetanna Team

|

November 20, 2023

Ulvetanna Team
November 20, 2023

Binius: a Hardware-Optimized SNARK

In a new research paper, we demonstrate a performance-optimized approach to SNARK construction based on towers of binary fields.

READ ARTICLE

Ulvetanna Team

|

August 8, 2023

Ulvetanna Team
August 1, 2022

Caulk+: Table-independent Lookup Arguments

New work on lookup arguments with reduced complexity

READ ARTICLE

Ulvetanna Team

|

May 24, 2023

Ulvetanna Team
May 24, 2023

Poseidon Merkle Trees in Hardware

We report the first fully-pipelined FPGA architecture for ZKP-friendly Merkle trees using the Poseidon hash

READ ARTICLE