Efficient Scalable Oversight via Rewinding

What it claims

Ziyi Guan, Yael Tauman Kalai, Ron Rothblum and Zoe Xi (MIT and Succinct, October 2026) give a relativizing rewindable interactive proof (RIP) for any ε-robust oracle Boolean circuit. The circuit has n input bits, m output bits, S gates and oracle queries of polylogarithmic length. After a one-time preprocessing step of Õ(n+m+S), the bounds are:

• Verifier: runs in Õ(n+m+1/ε) and makes O(1/ε) oracle queries. Neither figure depends on circuit size or depth.
• Honest prover: runs in O(n+m+S)+Õ(1/ε).
• Interaction: O(log(n+m+S)) rounds and Õ(1/ε) communication.
• Soundness: error is at most 1/3 per run, even against a computationally unbounded prover.

Running times count field operations. Õ hides factors polylogarithmic in n+m+S.

The prior protocols of Chen, Kalai and Xi (2026) needed a polynomial-time prover and cryptography for succinctness. This construction is statistically sound, uses no cryptography and has a linear-time prover. Debate (Irving, Christiano, Amodei) needs one truthful prover. This protocol does not.

How it works

The verifier snapshots the prover's state and can restore it at any point. It can then question one state many times, and the prover never sees the other questions.

Soundness is required only against provers that can be rewound in this way. This is weaker than standard soundness, and it is what replaces cryptographic commitments. The authors identify those commitments as the main source of prover cost in SNARGs.

Preprocessing reads the circuit once and stores a representation of it. That cost is spread over many evaluations of the same circuit on different inputs. The construction compiles an interactive oracle proof (IOP), built with error-correcting codes and "encoded-witness IOPs", into an RIP.

Evidence

MNIST experiment. The protocol was run once at soundness error 2⁻⁴⁰. The robust oracle circuits had 2⁸ to 2²⁶ oracle gates. The oracle was the sparse MNIST classifier used as the judge in the original debate experiment.

• The verifier made a median of about 76 oracle queries. Evaluating the largest circuit directly needs up to 2²⁶ queries.
• The verifier's online time drops below direct evaluation from about seven million oracle gates.
• At the largest size, the verifier's online time is one eighth of direct evaluation.

Flock comparison. Flock is a SNARG for batch BLAKE3 hashing. Its IOP, compiled into an RIP, has a prover 1.8 to 2.1× faster than Flock's own SNARG prover.

Limits

• External storage: soundness fails if a cheating prover can reach storage that is not rewound. The verifier must fully control the prover's machine, for example through a checkpointed VM or trusted hardware.
• Robustness required: the guarantee covers only computations whose output is ε-robust on the given input. The authors note that efficient verification of arbitrary oracle computations is known to be impossible.
• Preprocessing: the Õ(n+m+S) one-time cost is only worthwhile when a fixed circuit is evaluated many times.
• Preliminary results: the authors call the MNIST experiment preliminary.
• Missing text: the fetched text stops in the technical overview. The paper's Limitations section (6.4) and the experimental setup details were not available.