Rewindable interactive proofs let weak verifier check AI outputs faster than prior proofs
The claim
RIP protocols provide efficient scalable oversight without assuming a truthful prover
Published as: “Efficient Scalable Oversight via Rewinding”
So what
RIPs provide a practical way to verify robust AI-driven computations more efficiently than existing SNARGs, potentially lowering the cost of scalable oversight for AI systems.
The five-minute version
The paper builds a rewindable interactive proof (RIP) for robust oracle-aided computations that achieves a linear-time prover and a verifier running in near-linear time without cryptography, and demonstrates experimentally that the verifier can be faster than direct circuit evaluation and that the prover can be 1.8-2.1× faster than a SNARG. The evidence includes a formal theorem with concrete time bounds and two experiments on MNIST-based circuits and on the Flock SNARG.
What they found 4
- Verifier runtime and query complexity are independent of circuit size, depending only on input length and robustness parameter.
“The verifier runs in e O(n + m + 1/ε) time and makes O(1/ε) oracle queries.”
- Honest prover runs in linear time plus a term depending on the robustness parameter.
“The honest prover runs in O(n + m + S) + e O(1/ε) time.”
- On the largest MNIST circuit (226 oracle gates) the verifier takes only 0.12× the time of direct evaluation.
“at 226 the verifier takes 0.12× as long as direct evaluation.”
- When compiling Flock’s IOP into an RIP, the prover is 1.8 to 2.1× faster than Flock’s SNARG prover.
“Our prover is 1.8 to 2.1× faster than Flock’s SNARG prover at every size.”
What undercuts it the paper’s own results
- The verifier’s time grows with the square root of the trace, from the Ligero layout of the opening, rather than polylogarithmically as in Theorem 5.8.
- the prover cost remains a constant factor over direct evaluation, about 60× at the largest sizes.
- Our experiments are intended as a proof of concept rather than as a realistic scalable-oversight benchmark.
Stated limits 3
- Our experiments are intended as a proof of concept rather than as a realistic scalable-oversight benchmark.
- The verifier’s time grows with the square root of the trace, from the Ligero layout of the opening, rather than polylogarithmically as in Theorem 5.8.
- the prover cost remains a constant factor over direct evaluation, about 60× at the largest sizes.
What’s new here 4
- Introduces the rewindable interactive proof (RIP) model allowing a verifier to rewind a prover’s state.
- Constructs a relativizing RIP for ε-robust oracle circuits with a linear-time prover and a succinct verifier, without cryptographic assumptions.
- Implements the protocol and shows the verifier can be cheaper than direct evaluation on large robust circuits.
- Shows that compiling an existing IOP into an RIP yields a prover 1.8-2.1× faster than the corresponding SNARG.
Artifacts & methods 4
- rewindable interactive proofs (RIP)primitive
- encoded-witness IOPsystem
- MNIST majority circuitsdataset
- Flock SNARGevaluation