Rewinding lets verifiers check robust computations efficiently
Efficient Scalable Oversight via Rewinding · arXiv:2610.40535
In plain words
The paper introduces rewindable interactive proofs, a method for a weaker checker to verify a powerful system’s answer. The checker saves the prover’s state, restores it, and asks for parts of a proof already fixed, so answers cannot change to fit later questions.
The authors prove guarantees for calculations whose answers survive a small fraction of incorrect source answers. In a limited MNIST example, verifier queries stayed nearly flat as circuit size grew.
The research
When a computation is too costly for a weaker checker to repeat, how can it verify the answer without trusting a powerful prover? Debate can reduce the checker’s work but assumes one prover is truthful; prior robust-computation protocols remove that assumption at higher verifier cost.
The paper introduces rewindable interactive proofs, letting a verifier check fixed proof answers by restoring a prover’s state.
Rewindable interactive proofs let a verifier restore the prover to when a proof message was fixed and request selected symbols. The protocol encodes the computation and claimed oracle answers, checks that encoded work, then samples oracle gates.
Because robustness means a small share of changed answers cannot change the result, a false result requires many incorrect answers and can be caught by sampling.
The theorem guarantees honest proofs are accepted and bounds a cheater’s acceptance chance by 2^-σ. With preprocessing and short queries, verifier online time is nearly linear in input and output size; under stated conditions, prover time is linear in computation size.
The theorem applies to robust oracle computations under stated query-length and preprocessing assumptions. The MNIST circuits were selected, simple majority calculations over hardwired random views, and the experiments treat saving and restoring the prover’s state as free.
What the evidence shows
- The trust and cost problem
The paper introduces rewindable interactive proofs (RIPs), a proof-system model that lets a verifier restore a prover to an earlier state. This addresses a tension in scalable oversight: debate can make checking efficient but assumes one prover is truthful, while earlier protocols for robust computations remove that assumption at greater verifier cost. The question is whether a verifier can avoid that trust assumption without paying as much to check.
- Rewinding fixes proof answers
A verifier can rewind the prover to the moment a proof message was fixed, then ask for selected parts of it. Since the prover returns to that earlier state, its answers cannot depend on questions asked afterward.
This works only when the prover’s relevant state is restored; information stored elsewhere and left intact can invalidate the guarantee.
- Why spot checks can work
The protocol encodes the computation and its claimed answers from an oracle, an external function that returns answers to queries. It checks the encoded computation, then samples oracle gates and checks their recorded answers against that function.
Robustness means the output cannot change when only a small fraction of oracle answers change. Thus, a false output claim requires many incorrect recorded answers, making random spot checks useful.
- Formal guarantees and scope
For robust oracle circuits with polylogarithmic-length queries, the theorem gives perfect completeness and bounds the chance that a cheating prover gets a false claim accepted. With preprocessing, verifier online time is nearly linear in input and output length under the stated parameters; prover time is linear in computation size when the soundness setting is constant and 1/ε is polylogarithmic. The result has explicit query and robustness conditions.
- Two implementation results
In selected MNIST majority circuits, median verifier queries stayed between 74 and 80 as circuit size grew from 2^8 to 2^26 views; at the largest size, that was 840,000 times fewer queries than direct evaluation. A separate BLAKE3 test found a faster RIP prover than Flock’s default proof system under the tested configurations. These implementations demonstrate bounded cases, not arbitrary robust computations.
Deep
- Original paper authors
- Ziyi Guan, Yael Tauman Kalai, Ron Rothblum, Zoe Xi
- Submitted to arXiv
- License
- CC BY 4.0