Shockwave+

Motivation

Field-agnostic proof systems provide efficient proving by allowing native-field arithmetic. This property is significant for client-side programmable signatures, zkEVMs, and various other scenarios where proof of statements about primitives traditionally considered "zk-unfriendly" is required.

We aim to build a zero-knowledge proof system that is field-agnostic, efficient, and effortlessly composable with a SNARK with $O (1)$ proof size (e.g. Groth16, PLONK) to achieve minimal verification complexity.

Overview

Shockwave is a variant of Brakedown that uses Reed-Solomon code instead of a linear-time encodable code. Brakedown has a linear-time prover and is field-agnostic (i.e. works over all finite fields), but its proofs are concretely larger than Shockwave’s. Shockwave provides shorter proofs and lower verification time but requires an FFT-friendly field to achieve $O (n\log{n})$ proving time.

Shockwave+ is an extension of Shockwave that works over all finite fields by using ECFFT instead of FFT for low-degree extension of polynomial evaluations. It inherits the smaller proofs of Shockwave and is also field-agnostic. It uses the EXTEND operation from ECFFT to run Reed-Solomon encoding in $O (n\log{n})$ time.

Crates

shockwave_plus contains the prover/verifier for a zero-knowledge proof of R1CS satisfiability. It’s based on the PIOP from Spartan, and uses the multilinear polynomial commitment scheme implemented in tensor_pcs.

The EXTEND operation is implemented in a separate crate ecfft and is used in tensor_pcs.

Zero-Knowledge

We use the zero-knowledge sum-check protocol from Libra to transform the Spartan PIOP into a zero-knowledge PIOP. And use a technique from BCG+17 to make the polynomial commitment scheme zero-knowledge.

Benchmarks

R1CS constraints	Proof gen	Proving key gen
2^12	60ms	83ms
2^15	477ms	85ms
2^18	4s	169ms

• On the secp256k1 base field
• Measured on a M1 MacBook Pro

Future work

• Employ self-recursion techniques from Vortex/Orion to make the proofs smaller.
• Support richer frontends (CCS, PLONKish).

Run tests

cargo test

Run benchmarks

cargo bench