WorksComputer Science
Efficient Scalable Oversight via Rewinding
Abstract
Scalable oversight asks how a weak verifier can check the outputs of computations performed by more powerful AI systems. One proposed approach uses relativizing interactive proofs, in which a weak verifier checks the output of a complex oracle-aided computation by interacting with one or more powerful provers. A prominent example is debate, which is highly efficient but assumes that one of two powerful AI models, or provers, is truthful. For certain classes of oracle-aided computations, this assumption can be removed, but at substantially greater computational cost. In this work, we introduce rewindable interactive proofs (RIPs), a new model of relativizing interactive proofs for scalable oversight. In an RIP, the verifier may rewind the prover to an earlier state of the interaction and continue from there. This is possible when the prover is an AI model, since the verifier can save a snapshot of the model's state and later restore it. We construct a relativizing RIP for computations whose outputs are robust to changing a small fraction of oracle answers. Our construction is more efficient than prior relativizing proofs that do not assume a truthful prover, and it uses no cryptography. In our construction the honest prover runs in time linear in that of the original computation, and the verifier, after a one-time preprocessing step, runs in time nearly linear in the input length (which can be much smaller than the computation itself). We implement our protocol, report a preliminary MNIST experiment, and show that an RIP can be faster than a state-of-the-art deployed proof system. RIPs may be of independent interest. Rewinding is possible whenever the verifier controls the prover's machine, for example when the prover runs on trusted hardware or in a virtual machine whose state can be checkpointed.
Introduction
As AI capabilities grow rapidly, a critical problem is: how can we ensure that AI systems remain safe and behave as intended? One major concern is that, as we are training AI models to perform increasingly complex tasks, we may no longer be able to efficiently verify the accuracy of their outputs. As a result, we may not be able to verify that they are behaving in a way that aligns with our intentions. This problem of providing accurate training supervision for increasingly powerful AI models is known as scalable oversight.
Verifiable computation has been studied for decades in cryptography and computational complexity. This research has led to proof systems that allow a powerful but untrusted “prover” (in our setting, a powerful AI model) to convince a weak “verifier” (a weaker AI model or a human) that the output of a hard computation is correct [22, 41, 5, 4, 45, 59 BCS16, 58].
In this work, we observe that scalable oversight has some unique characteristics that make existing approaches either inapplicable or less efficient than they could be. First, the prover is not an external party but rather an AI model whose execution the verifier controls. In particular, the verifier can rewind the model to an earlier state and continue the interaction without the model remembering what happened in previous runs. To capitalize on this, we consider a new proof-system model which we call rewindable interactive proofs (RIPs),1 in which the verifier is allowed to rewind the prover in this way. This model is closely related to previous proof-systems studied in the literature such as MIPs [22] and PCPs [41, 5, 4], but we show that it can have significant efficiency gains over them.
Second, classical results in proof systems do not apply directly to our setting, because the computations we wish to verify may involve functions that we can’t see the inner workings of—such a function can be used to represent human judgment or query access to an external database, for example. We model such “black-box” functions as oracles, and say that a proof system relativizes if its guarantees hold with respect to any oracle. Relativization is believed to be essential for AI safety purposes, because we do not know what sorts of capabilities AI may have in the future. The UK AISI team even writes that “in order to be relevant to AI safety, an interactive proof result must relativize” [52]. The difficulty is that classical results in proof systems, including the celebrated and theorems, do not relativize [29], and moreover results show that efficient verification is impossible for arbitrary oracle-aided computations [44, 43 HCRR92, 42, 35, 14].
For a concrete example of where scalable oversight is needed, consider the scenario of training an LLM to determine which laws a company has violated based on hundreds of pages of records. The LLM outputs one bit for each law (representing yes or no), and now we need to verify whether these bits are correct or not. The straightforward way of doing this would be to have a human expert carefully read through the documents, but this seems unreasonably expensive, especially to produce just one training label. In a scenario like this, we would like to have a more efficient training protocol, especially one that is more efficient in its use of human judgments. As another example, we may consider a scenario where we train an LLM to answer questions using a large public dataset, such as the web; we would like to be able to verify that an output of this LLM is correct efficiently, making few queries to the dataset.
Various approaches to scalable oversight have been proposed in the literature [CS A18; LKEKMM L18; ICA18], including some based on relativizing proof systems. One prominent example of such an approach is debate, which was introduced by Irving, Christiano, and Amodei [51]. In an AI debate, there are two powerful AI models, or provers, who claim different outputs, and the provers debate each other to try to convince a verifier that their output is the correct one. The verifier is extremely efficient, or succinct, meaning that it runs in much less time and makes far fewer oracle queries than it would need to run the computation on its own. The authors show that DEBATE, the class of problems which admit a debate protocol, is powerful: in the language of computational complexity theory, DEBATE = PSPACE (where PSPACE is the class of problems solvable in polynomial space). Moreover, this result relativizes.
However, debate makes the strong assumption that one of the provers is truthful, i.e., one of the AI models is guaranteed to argue for the correct answer. Intuitively, this means that the verifier has one of the powerful AI models on his side. But scalable oversight is especially important precisely when we do not know whether we can trust any AI model. Recently, Chen, Kalai, and Xi [34] sought to remove this assumption by constructing “doubly-efficient” interactive proofs [45]. In an interactive proof [47, 8], a prover interacts with a verifier to convince him of a claim; a doubly-efficient one has an efficient prover as well as an efficient verifier. Since this is impossible for arbitrary oracle computations, [34] instead give protocols for a natural restricted setting where the computation is robust, meaning that the output does not change even if a small fraction of answers to oracle queries are modified. However, these protocols still require substantially more work from the verifier than debate. A natural question, then, is:
Can we obtain a more efficient relativizing interactive proof without assuming any prover is truthful?
Motivated by this question, we give a positive answer for robust oracle computations in the RIP model: by exploiting the verifier’s ability to rewind the prover, we obtain strong efficiency guarantees without assuming that any prover is truthful.
Our results
We introduce and formally define rewindable interactive proofs, and construct a relativizing RIP for robust oracle-aided computations, with a succinct verifier and a linear-time prover. We also implement our protocol and evaluate its performance experimentally.
The model. In an interactive proof, a prover and a verifier exchange messages, after which the verifier accepts or rejects. The proof must be complete, meaning that the honest prover convinces the verifier of a correct output, and sound, meaning that no cheating prover can convince it of an incorrect output, except with small probability. An RIP is an interactive proof in which the verifier has one extra power: at any point, it may rewind the prover to an earlier state of the interaction and continue from there, as one would restore an AI model from a save point (§ 5.1 gives the formal definition). Completeness is as usual: the honest prover must convince the verifier, now across whatever rewinds the verifier performs. Soundness, on the other hand, asks less than it does of a standard proof system. A standard proof system must be sound against every cheating prover, however it behaves; an RIP need only be sound against provers that the verifier can rewind, whose answer after a rewind cannot depend on anything the verifier did after the restored state. This is a weaker guarantee, and it is what makes the model powerful: the verifier can question the prover about one state as many times as it likes, and the prover never learns the other questions. We emphasize that soundness violated if a cheating prover has access to external storage that is not rewound.
A relativizing RIP for robust computations. Following Chen, Kalai, and Xi [34], we model the computation as an oracle Boolean circuit and call it -robust if its output does not change when up to an fraction of the oracle’s answers are modified. Our main result is a relativizing RIP for verifying the output of any robust oracle circuit, with a succinct verifier and a prover that runs in linear time.
Theorem 1.1 (Informal; see Theorem 5.8). Let be an oracle circuit with input bits, output bits, and gates, whose oracle queries have polylogarithmic length. After a one-time preprocessing step taking time, there is a relativizing RIP for verifying the output of on any input with respect to which it is -robust, with the following guarantees:
The honest prover always convinces the verifier of a correct output, while a cheating prover (even a computationally unbounded one) can convince the verifier of an incorrect output with probability at most .
The verifier runs in time and makes oracle queries.
The honest prover runs in time.
The number of rounds is and the total communication is .
Here hides factors polylogarithmic in , and running times count field operations.
In the preprocessing step, the verifier reads the description of the circuit and stores a representation of it, which it reuses in every evaluation of the circuit; the cost is thus amortized over all evaluations, which suits our setting, where a fixed circuit is evaluated on many inputs. Some such step is necessary to achieve online verification time sublinear in the size of a general circuit, and preprocessing is standard in efficient proof systems [CHMMVW20; Set20; CBBZ23]; see Remark 3.22.
Comparison with [34] and debate. Compared with the protocols of [34], after the preprocessing step our verifier’s running time depends only on the lengths of the input and output and on the robustness parameter, instead of on the size or depth of the circuit, and its number of oracle queries depends only on the robustness parameter; compared with their succinct protocol, ours is statistically sound, uses no cryptography, and has a linear-time rather than a polynomial-time prover. Unlike debate, our protocol does not assume that a prover is truthful.
Why not concretely efficient SNARGs? The proof systems deployed in practice, notably in blockchains [27, 63], are SNARGs, succinct non-interactive arguments. Why not take one off the shelf? First, off-the-shelf SNARGs do not handle oracle-aided computations, even robust ones. Second, their soundness rests on unproven cryptographic assumptions, from standard ones such as collision-resistant hash functions to more aggressive ones chosen for concrete efficiency. As AI brings such assumptions under increasing scrutiny (recent AI-discovered results, still under review, claim to refute the Exponential Time Hypothesis [56, 36] and, assuming them, give a subexponential algorithm for the elliptic-curve discrete logarithm problem [1]), it is unclear whether this is a prudent tradeoff for scalable oversight. RIPs address both concerns: they handle robust oracle-aided computations without cryptographic assumptions and are sound even against computationally unbounded provers. Perhaps surprisingly, dispensing with cryptography can also improve prover efficiency: rewinding avoids the cost of cryptographic commitments (Remark 5.9), and our second experiment demonstrates the resulting speedup.
Experiments. We complement our theoretical result by implementing the protocol and running two experiments. The first is a proof-of-concept experiment inspired by the MNIST debate experiment of Irving, Christiano, and Amodei [51]: we run the protocol once, at soundness error , on robust oracle circuits with between and oracle gates, whose oracle is the debate experiment’s judge, a sparse MNIST classifier. Across this range the verifier makes a median of about 76 oracle queries, against up to needed to evaluate the largest circuit directly, and its online running time falls below that of direct evaluation from about seven million oracle gates on, to an eighth of it at the largest size.
For our second experiment, we consider Flock [26], a state-of-the-art SNARG built from an interactive oracle proof (IOP) [BCS16; RRR16] (see § 2) for batch evaluation of the BLAKE3 hash function. To study the efficiency gains of rewinding, we compile Flock’s IOP into an RIP and find that its prover runs 1.8 to 2.1× faster than Flock’s own SNARG prover (§ 6.3).
Related work
Relativizing proof systems. Relativization has been studied extensively as a barrier in computational complexity theory, and notably the classical results on interactive proofs, e.g., the celebrated and theorems, do not relativize [29]. Additionally on the negative side, results show that efficient verification is impossible for arbitrary oracle-aided computations (even when the security guarantee is relaxed to hold only against efficient dishonest provers) [44, 43, 49, 42, 35, 14]. Our work circumvents these barriers by restricting to the setting of robust oracle computation. On the positive side, prior work has shown that and do algebrize, meaning that they relativize if the proof system is also given a low-degree extension of the oracle [6], and there has also been work on constructing relativizing succinct cryptographic proof systems in some structured oracle models [CT10; CCS22; CCGOS23; CGSY24; CKX26].
Interactive proofs for scalable oversight. There has been a recent line of work studying interactive proofs as an approach to scalable oversight, starting with a paper by Irving, Christiano, and Amodei on “AI safety via debate” [51]. Their model assumes that the debating provers are computationally unbounded; later, Brown-Cohen, Irving, and Piliouras introduced doubly-efficient debate, where the provers are guaranteed to be efficient [23]. More recent works on debate have focused on its limitations, e.g., the “obfuscated arguments problem,” where a lying debating prover can make it very hard for the other prover to find the flaw in her argument [9, 24, 25]. Very recently, Chen, Kalai, and Xi initiated the study of relativizing interactive proofs for scalable oversight without a truthful prover, constructing protocols with a succinct verifier and a polynomial-time prover for certain classes of oracle computations [34]. Our work considers the setting of robust computation that they introduce; we leverage rewinding to improve the efficiency of their protocols.
Interactive proofs for trustworthy machine learning. There is also a line of work on applying interactive proofs to problems of trust in machine learning [2 AZWG21, 48, 53, 64]. In particular, Amit, Goldwasser, Paradise, and Rothblum [2] introduce self-proving models, which are trained to provide both an answer and an interactive proof that the answer is correct; their focus is on training models to produce proofs for computations that already admit interactive proofs, whereas we construct new interactive proofs for oracle-aided computation.
Technical Overview
Here, let us briefly outline the key ideas behind our construction.
We model the computation that the verifier wishes to verify as an oracle Boolean circuit , i.e., a Boolean circuit that may contain gates that make calls to an arbitrary oracle . We assume that the oracle circuit is -robust with respect to the verifier’s input, meaning that its output on this input does not change if at most an -fraction of answers to its oracle queries are changed (see Definition 3.14 for a formal definition). Given an oracle circuit , an input for which is -robust, a claimed output , and access to , the prover and the verifier engage in a rewindable interactive proof (RIP, § 5) that . Recall that the verifier may rewind the prover to any earlier state of the interaction and continue from there.
Our goal is to design a protocol that is efficient enough to use in practice. Most practical proof systems are built from an interactive oracle proof (IOP) [BCS16; RRR16], which is an interactive proof where the prover sends long messages but the verifier reads only a few bits of each message, because IOPs admit very efficient provers and verifiers. We first construct a relativizing IOP and then turn it into a relativizing RIP that inherits the IOP’s efficiency.
A relativizing IOP (Section 4). To start, a natural strategy is to try to turn the oracle circuit into a circuit without oracle gates and then use standard IOPs. To “deoraclize” the circuit, suppose that the prover provides a string containing a claimed answer for each oracle gate. We can then define a circuit without oracle gates, which is except with each oracle gate replaced by the corresponding answer in . The basic idea is to have the prover send the string in the first round of the IOP and then prove that . Then the verifier can check that the answers in are correct with respect to .
The verifier cannot check that all the answers in are correct, since this would require making all the oracle calls needed in order to run the computation, which he cannot afford. But the verifier does not actually need to do this, since we assume is -robust: if , then any satisfying must contain more than an -fraction of incorrect oracle answers, so the verifier can catch an incorrect oracle answer with good probability by sampling answers in .
To obtain stronger efficiency guarantees, instead of itself, we have the prover send an encoding of a witness consisting of together with a “transcript” of evaluating on . The prover and verifier then run an IOP to check that this encoding is close to the encoding of a valid witness for . The advantage of using an encoding is that the verifier can later recover a few bits of this same witness, with the prover’s help, without reading the entire witness. In particular, the verifier can sample a few oracle gates, recover the claimed answer in for each oracle gate and the corresponding query using the transcript, and check that the pair is correct using . To achieve this, we construct a variant of an IOP that we call an encoded-witness IOP (Section 3.4).
Relativizing IOP relativizing RIP (Section 5.2). Now we turn our relativizing IOP into a relativizing RIP. The idea is similar to the one behind the standard proof for turning a (non-relativizing) IOP into an MIP [BCS16] (see Section A for MIPs and their relation to RIPs). We have the RIP verifier simulate the IOP verifier and the RIP prover simulate the IOP prover, except that the “IOP” prover computes her long messages but does not send them. If the verifier simply asked the prover for the bits he wants to read, she could answer adaptively, e.g., her answer to the verifier’s second query to some message could depend on his first query. Instead, whenever the verifier wants to read a bit in some message, he rewinds the prover to her state right after she computed that message and asks her for the bit. Her answer then cannot depend on his other queries, so she cannot do better than an IOP prover who fixes each message before the verifier queries it, and the soundness error is that of the IOP. Rewinding thus allows the RIP to be as efficient as the IOP.
Experiments (Section 6). We implement our protocol and run two experiments. The first evaluates it on robust oracle circuits and measures what the verifier saves over evaluating the circuit directly. The second compares it with an existing proof system. Since no relativizing protocol has an implementation, we compare with a state-of-the-art proof system for an oracle-free computation, which is built from an IOP: compiling the same IOP into an RIP instead measures what rewinding saves.
The first experiment is a proof of concept inspired by the MNIST debate experiment of Irving, Christiano, and Amodei [51]. We use a sparse MNIST classifier, which predicts a digit from six revealed nonzero pixels of an MNIST image, to define our oracle. Given a “sparse view” of an MNIST image and a candidate digit, the oracle outputs whether the classifier predicts that digit. Our circuits query this oracle on many random sparse views of an image and output whether a majority of the views vote for the candidate digit.
We run the protocol once, at soundness error , on 50 MNIST test images while increasing the number of oracle gates from to . The robustness parameter remains nearly constant across these circuit sizes, and the median number of oracle queries made by the verifier stays between 74 and 80. At the largest circuit size, the verifier makes 840,000 fewer oracle queries than are needed to evaluate the circuit directly. The verifier’s online running time is also sublinear in the circuit size, growing substantially more slowly than direct evaluation: it falls below direct evaluation at about seven million oracle gates, and at is the time required to evaluate the circuit directly. The prover, which also generates the witness, takes about the time of direct evaluation at the largest sizes.
For the second experiment we use Flock [26], a proof system for batch evaluation of an ordinary Boolean circuit with no oracle gates, namely the BLAKE3 hash function. Flock is built from an IOP, which is not by itself a realistic proof system, since the prover sends long strings; Flock compiles it into a SNARG using cryptography. We compile the same IOP into an RIP instead, which saves the cryptographic compilation: the prover no longer commits to its proof strings, and since a cheating prover gets one attempt per execution rather than unlimited offline retries, the IOP can run at a lower security level and over a smaller field. On instances of size to , our prover runs to faster than Flock’s prover (§ 6.3).
Preliminaries
Here we introduce some definitions and tools that we use.
Definition 3.1 (Language). A language is a set of binary strings. We think of a language as a decision problem: given an instance , we want to determine whether .
Definition 3.2 (Relation). A relation is a set of pairs , where is an instance and is a witness for . The language associated with is .
Definition 3.3 (Oracle and oracle access). An oracle is a fixed function ; in particular, its answer to a query does not depend on earlier queries. We write that an algorithm has oracle access to if it can send a query and receive the answer string in one timestep.
Definition 3.4 (Relativized language). For an oracle , a relativized language is a language whose membership may depend on .
Definition 3.5 (Relativized relation). For an oracle , a relativized relation is a relation whose membership may depend on . Its associated relativized language is .
Definition 3.6 (Equality polynomial). Let be a finite field and an integer. The equality polynomial is
For , is if and otherwise.
Definition 3.7 (Multilinear extension). Let be a finite field and an integer. We interpret every vector as a function . The multilinear extension of is the unique polynomial of degree at most one in each variable satisfying for every . Explicitly,
where is the equality polynomial (Definition 3.6). For a binary string of length , we view its bits as elements of and use the same definition. For a vector or string of any other length, the multilinear extension is that of its zero-padding to the next power-of-two length .
Oracle-aided computation and robustness
Following [34], we model the computation that the verifier verifies as an oracle Boolean circuit. Informally, this is a diagram that shows how to obtain an output string from an input string by applying some sequence of OR (), AND (), and NOT () operations together with calls to an oracle. More formally, we have:
Definition 3.8 (Boolean circuit). An -bit input, -bit output Boolean circuit is a directed acyclic graph with input vertices and an ordered list of output vertices. Input vertices have no incoming edges; every other vertex is a gate labeled or with two incoming edges, or with one. Any vertex may be an output. A circuit is given by its description , a binary string that lists its gates in a fixed order, each with its label and its incoming edges, followed by the list of output vertices; we refer to gates by their position in this list.
On input , the value of the th input vertex is the th bit of , and each gate applies its operation to the values of its children, i.e., the vertices with edges going into the gate. The output of the circuit on consists of the values of the output vertices read in order. The size of a circuit is its number of gates.
Definition 3.9 (Oracle Boolean circuit). For an oracle , an oracle Boolean circuit is a Boolean circuit that may also contain oracle gates. Each oracle gate has an arbitrary number of incoming edges. We view the input to an oracle gate as the string given by the values of its children read in order. The value of an oracle gate is applied to its input string.
Definition 3.10 (Family of circuits). A family of circuits consists of one circuit with an -bit input and an -bit output for each . It computes a function if for every and every .
Definition 3.11. Let be an oracle circuit of size . We define the computation transcript on input to be the string that lists the values of all the gates in when run on input in order (using to evaluate oracle gates), and denote the computation transcript by
Definition 3.12. Suppose has oracle gates, and consider running on an input . We use
for the string of queries and answers that makes to on input , where (resp. ) is the input to (resp. output of) oracle gate . Call a query-answer trace. We write (resp. ) for the string of queries (resp. answers) in .
Definition 3.13 (De-oracularized circuit). Let be an oracle circuit with an input of length and oracle gates. We say that its de-oracularized circuit is the (non-oracle) circuit with input obtained by replacing, for every , oracle gate with an input vertex with value .
We next define robustness. Informally, the output of a robust oracle circuit should not change if at most a small fraction of answers to its oracle queries are incorrect. More formally, we define robustness as follows, adapting the definition that Chen, Kalai, and Xi use [34]:
Definition 3.14 (Robustness). Let be an oracle circuit with an input of length and oracle gates, and let be its de-oracularized circuit (Definition 3.13). For an input , where and , and an index , let denote the input to oracle gate in when we run on except with the value of each oracle gate replaced with the corresponding bit in . For , we say that is -robust with respect to if, for every satisfying
we have that .
Definition 3.15 (Circuit-satisfiability relation). The circuit-satisfiability relation is the relation defined as follows. The instance is a triple , where is the description of a Boolean circuit with input vertices, of which the first form the public input and the remaining the private input, an output of length , and gates, is a public input, and is a claimed output. The witness is a pair of a private input and a transcript. Then
where is the computation transcript of Definition 3.11.
Definition 3.16 (Oracle-circuit-evaluation relation). Fix an oracle . The oracle-circuit-evaluation relation is the relativized relation (Definition 3.5) defined as follows. The instance is a triple , where is the description of an oracle circuit with an input of length , output of length , and gates, is an input, and is a claimed output. The witness is a transcript . Then
where is the computation transcript of Definition 3.11.
Remark 3.17 (Transcript as witness). The witness of Definition 3.15 is a private input together with the entire transcript , and the witness of Definition 3.16 is the entire transcript. The transcript is not needed to define either relation, as it is determined by the instance and in Definition 3.15 and by the instance alone in Definition 3.16. Including it nevertheless allows succinct verification, since the verifier can check an encoding of the witness at a few positions instead of evaluating the circuit (Definition 3.32, Lemma 3.36, and Theorem 4.1).
Interactive oracle proofs
An interactive oracle proof (IOP), introduced in [BCS16; RRR16], lets a powerful prover convince a weak verifier that an instance has a valid witness by sending long proof strings that the verifier checks at a few locations. The parties may interact over several rounds.
Definition 3.18 (Interactive oracle proof). An interactive oracle proof for a relation is an interactive protocol between a probabilistic polynomial-time verifier and a possibly computationally unbounded prover . The parties receive a common input , and the honest prover additionally receives a witness with .
In round , the prover sends a proof string over a finite alphabet , which is a finite field in our constructions. The verifier has oracle access (Definition 3.3) to every proof string sent so far.
The protocol satisfies the completeness and soundness properties defined below.
We write when the verifier accepts after interacting with the prover on common input . Note that we denote the IOP prover and verifier by and , rather than by and as for rewindable interactive proofs (§ 5) and MIPs (Section A), to distinguish between the settings. The probabilities below are over the verifier’s private random bits (we assume without loss of generality that the prover is deterministic).
Definition 3.19 (Completeness). An IOP for has perfect completeness if, for every , the honest prover satisfies
Definition 3.20 (Soundness). An IOP for has soundness error if, for every and every possibly computationally unbounded cheating prover ,
Definition 3.21 (Relativizing IOP). Fix an oracle and a relativizing relation . A relativizing IOP for is an IOP for in which the verifier and prover, including a cheating prover, have black-box access to the same oracle . The protocol relativizes if its completeness, soundness, and efficiency guarantees hold for for every oracle .
Remark 3.22 (Preprocessing). An instance may have the form , where is long and is the same for many instances. In our setting is the description of a circuit and is an input together with a claimed output (Definition 3.16). An IOP with preprocessing has a verifier that is a pair . First receives and outputs a state . Then receives and and interacts with the prover. The verifier reads only in the preprocessing, which is done once and whose state is reused for every . Completeness and soundness are as in Definitions 3.19 and 3.20.
For the verifier’s online time to be sublinear in the size of a general circuit, we need to preprocess the circuit. Intuitively, without preprocessing the verifier must read the entire circuit, since two circuits that differ in one gate can produce different outputs on the same input. Preprocessing is standard in deployed proof systems [CHMMVW20; Set20; CBBZ23]. Since we typically fix a circuit and evaluate it on many inputs, the one-time cost of preprocessing is amortized over all the evaluations. Preprocessing is unnecessary, however, for a circuit with a short description, since the verifier can then work from the description instead of reading the whole circuit [45, 37, 62 XZZPS19]. It is also unnecessary when a circuit is evaluated on a batch of inputs, since the verifier can read the circuit once per batch [26].
We track the following worst-case efficiency parameters of a (relativizing preprocessing) IOP:
Proof length : the total number of alphabet symbols in the proof strings.
Proof query complexity : the total number of verifier queries to the proof strings.
Round complexity : the number of back-and-forth rounds between the verifier and the prover. Queries to proof strings do not count as interaction rounds.
Verifier oracle query complexity : the number of verifier calls to the oracle , when present. These calls are counted separately from proof queries.
Verifier preprocessing time : for an IOP with preprocessing (Remark 3.22), the running time of , which bounds .
Verifier online time : the running time of , with random access to .
Prover running time : the honest prover’s total running time.
Error-correcting codes
An error-correcting code maps a message to a longer string, its codeword, so that any two codewords differ in many positions. A locally decodable code [54] lets a decoder recover any symbol of the message from a few queries to a (possibly corrupted) codeword, and a relaxed locally decodable code [21] also allows the decoder to refuse to answer.
Definition 3.23 (Distance). Let be a finite alphabet and a positive integer. The distance between is the fraction of positions in which they differ. The distance between and a set is
and if is empty. For , we say that is -close to if , and -far from otherwise.
Definition 3.24 (Code). Let be a finite alphabet and a positive integer. A code is a set , whose elements are called codewords. Its relative distance is the minimum distance (Definition 3.23) between two distinct codewords,
For a finite alphabet and an integer , an encoding is an injective map . Its image is a code, and the relative distance of is that of its image.
We write for a list of positions and for the symbols of at these positions.
Definition 3.25 (Relaxed local decoder). Let be an encoding. A relaxed local decoder for with query complexity is a probabilistic algorithm that receives a list of positions, has oracle access to a string , reads at most symbols of , and outputs . We write for its output.
Definition 3.26 (Completeness). A relaxed local decoder for has perfect completeness if, for every and every list of positions,
Definition 3.27 (Decoding error). A relaxed local decoder for has decoding error if, for every proximity parameter , every list of positions, every , and every that is -close to (Definition 3.23),
In this paper we use a more relaxed notion, interactive local decoding, in which a prover helps the decoder. This relaxation is what enables efficient proving and verification: the encoding of Lemma 3.31 has linear length, and decoding a few positions costs the prover linear time and the decoder polylogarithmic time in the message length.
Definition 3.28 (Interactive local decoder). Let be a finite alphabet and let be an encoding (Definition 3.24). An interactive local decoder for is an interactive protocol between a probabilistic polynomial-time decoder and a possibly computationally unbounded prover . The parties receive a common input , a list of positions. The decoder has oracle access to a string , and the honest prover receives with . The prover sends proof strings as in an IOP (Definition 3.18), and at the end the decoder outputs .
We write for the output of the decoder. We track the efficiency parameters of an interactive local decoder as for an IOP (§ 3.2), with the queries to counted as proof queries.
Definition 3.29 (Completeness). An interactive local decoder for has perfect completeness if, for every and every list of positions, the honest prover satisfies
Definition 3.30 (Decoding error). An interactive local decoder for has decoding error if, for every proximity parameter , every list of positions,
every , every that is -close to (Definition 3.23), and every possibly computationally unbounded cheating prover ,
Lemma 3.31 ([19, 61]). Let . There is a prime field of size at least a sufficiently large polynomial in and at most polynomial in , and an injective encoding with , computable in field operations, with relative distance at least a constant , such that for every constant proximity parameter there is an interactive local decoder for that, on a list of positions, has the following parameters, where the constants in the depend on .
Perfect completeness.
Decoding error: .
Round complexity: .
Proof query complexity: .
Proof length: .
Prover time: .
Verifier time: .
The decoder’s verifier has oracle access to a string of length that depends only on and is computable in that time; in Lemma 3.36 the verifier computes it in its preprocessing.
Proof sketch. is the encoding of TensorSwitch [19], a tensor code of two linear-time encodable codes of constant rate and constant relative distance [61], so it has linear length, constant relative distance, and linear encoding time. TensorSwitch binds a string to a message by decoding its columns and then its rows, each within the unique decoding radius of the respective code; a string that is -close to with has few enough undecodable columns for this to recover , and in this regime the hypotheses of TensorSwitch on the codes hold for every linear code. The decoder works as follows. The prover sends the claimed values of the positions in . The decoder picks a random , and the parties run a sumcheck for the claim , where has nonzero entries. This reduces the claim to one evaluation of the multilinear extension of at a random point, which the parties check against by running the remaining rounds of TensorSwitch’s commitment phase and its opening protocol. The decoder outputs if every check passes and otherwise. If some , the combined claim is false except with probability over , and then the sumcheck or the opening rejects except with error polynomially small in plus the error of the opening, which is for queries; gives decoding error below . The prover runs the sumcheck in field operations, since is sparse, and the opening in . The verifier runs in for the sumcheck, to evaluate the multilinear extension of at the random point, and for the opening, which reads a preprocessed string of length that depends only on the code.
Encoded-witness IOPs
Here we define the notion of encoded-witness IOPs, which serve as a building block in our relativizing IOP in § 4. An encoded-witness IOP is an IOP in which the prover’s first message is an encoding of its witness. Soundness is stated in terms of this first message [BCS16; BBHR18]. In addition, the encoding is required to have an interactive local decoder (Definition 3.28).
Definition 3.32 (Encoded-witness IOP). Let be a relation whose witnesses are strings , and let be an encoding (Definition 3.24). An encoded-witness IOP for with encoding is an IOP with preprocessing for (Definition 3.18 and Remark 3.22) in which the prover’s first message is a proof string , and the honest prover sends , where the encoding has an interactive local decoder (Definition 3.28). We write
where denotes the first message of the prover and denotes the decision bit of the verifier. The decoder has the completeness and decoding error of Definitions 3.29 and 3.30; the IOP has the completeness and soundness properties defined below.
Definition 3.33 (Completeness). An encoded-witness IOP has perfect completeness if, for every , the honest prover satisfies
Definition 3.34 (Soundness). For an instance , let be the set of encodings of valid witnesses. An encoded-witness IOP has soundness error if, for every proximity parameter , every instance , and every possibly computationally unbounded cheating prover ,
Remark 3.35 (Holographic proofs). Encoded-witness IOPs are similar to holographic PCPs [18], PCPs of proximity [21], and IOPs of proximity [BCS16; RRR16], in which the verifier has oracle access to an input and certifies that it is close to a language; here the input is the prover’s first message and the language is the set of encodings of valid witnesses. However, these proof systems only guarantee proximity to such an encoding, whereas we also need to recover positions of the witness from the first message, which is what the interactive local decoder provides.
Lemma 3.36 (Encoded-witness IOP for circuits, adapted from [28 CHMMVW20, 20, 19]). Consider instances of (Definition 3.15) whose circuit has a public input of length , a private input of length , output length , and gates. Let , and let be the encoding with an interactive local decoder given by Lemma 3.31 for , applied to the witness padded with zeros to length . Then, for every constant proximity parameter , with as in Lemma 3.31, has an encoded-witness IOP with encoding with the following parameters, where hides factors polylogarithmic in and the constants in the depend on .
Perfect completeness.
Soundness error: .
Round complexity: .
Proof query complexity: .
Proof length: .
Prover time: .
Verifier preprocessing time: .
Verifier online time: .
Proof sketch. The IOP is the standard compilation of a polynomial IOP into an IOP [CHMMVW20; BFS20], applied to the polynomial IOP for circuit satisfiability of HyperPlonk [28], with polynomials
sent as codewords of the encoding Enc of Lemma 3.31 and evaluation claims checked by the proximity test of TensorSwitch [19]. The prover’s first message is , the encoding of the witness. The verifier’s preprocessing encodes the polynomials that describe the circuit and computes the string of Lemma 3.31, which is its cost; its online work is that of the polynomial IOP’s verifier, which reads only the public input and output, plus a polylogarithmic number of queries. Whenever the polynomial IOP’s verifier queries a polynomial at a point, the prover answers with the evaluation, and the two run the proximity test on the encoding and the claimed evaluation. For soundness, since is below the unique decoding radius, every queried string is -close to at most one codeword, and the proximity test ensures, except with its error, that every answer is an evaluation of the polynomial that this codeword encodes. The soundness of the polynomial IOP then applies to the polynomial encoded by the first message, so if the verifier accepts with probability above , the first message is -close to the encoding of a valid witness. The prover runs in field operations, since the prover of HyperPlonk, the encoding, and the prover of the proximity test all do. The constants in the depend on through the proximity test’s query complexity.
Relativizing Interactive Oracle Proofs
In this section we construct a relativizing IOP (Definition 3.21) for the oracle-circuit-evaluation relation of Definition 3.16, that is, for proving that .
Theorem 4.1 (Relativizing IOP for robust oracle circuits). Fix an oracle and . Let be an oracle circuit with an input of length , an output of length , and gates, and let . Suppose that the oracle queries of have length polylogarithmic in . Then , for instances with this circuit such that is -robust with respect to , has a relativizing IOP with preprocessing (Remark 3.22) over a prime field of size polynomial in with the following properties, where hides factors polylogarithmic in , running times count field operations, and proof lengths count field elements.
Perfect completeness.
Soundness error: at most .
Round complexity: .
Proof query complexity: .
Verifier oracle queries: .
Proof length: .
Prover time: .
Verifier preprocessing time: .
Verifier online time: .
Recall that we want a relativizing IOP for , that is, for the claim that , in which the verifier makes only a few queries to . Without oracle gates this would be ordinary circuit satisfiability, which standard IOPs handle; the difficulty is the oracle gates, which the verifier cannot evaluate itself without making oracle queries. Intuitively, we can ask the prover to supply the answer to every oracle query. This turns into its de-oraclized circuit (Definition 3.13), an ordinary circuit whose evaluation an IOP can verify, and leaves the verifier with the task of checking that the supplied answers agree with . Checking all of them would again take oracle queries, but by robustness a wrong output can only be reached by lying about more than an fraction of the answers, so a few random spot checks suffice. Concretely, the construction combines the encoded-witness IOP for circuits of Lemma 3.36 with random sampling of oracle gates. The prover encodes the evaluation of the de-oraclized circuit of (Definition 3.13) on input and the oracle answers in its transcript, and proves that the de-oraclized circuit outputs . The verifier then samples a few oracle gates, decodes the query and the recorded answer at each of them from the encoded witness, and checks that each answer agrees with the oracle. By robustness (Definition 3.14), a wrong output forces more than an fraction of the recorded answers to be wrong, so samples suffice. § 4.1 gives the protocol and § 4.2 proves the theorem.
Construction
We describe the protocol for . Fix , , and a field as in Theorem 4.1, an instance with and , and the witness . Let be the de-oraclized circuit of (Definition 3.13), let be the values of at the oracle gates, and let
be the witness of (Definition 3.15) for the instance . The answer at oracle gate is the bit of , and each bit of its query is a bit of or of , at a position determined by . Let be the encoded-witness IOP of Lemma 3.36 for a constant proximity parameter , let be its encoding, and let be the interactive local decoder of for proximity parameter (Lemma 3.31). The protocol is as follows.
IOP: and run on with witness . This gives the first message and the decision bit .
Decoding: samples a uniformly random set of oracle gates and lets be the positions of their answers and query bits. Then and run on and , which gives . Unless , this yields for each a decoded answer at the -th oracle gate and, together with the bits of , a decoded query .
Decision: accepts if and only if , , and for every .
Proof of Theorem 4.1
Completeness. Suppose that . Then holds the answers of in the evaluation of on , so and is a valid witness. Hence with probability by the completeness of the encoded-witness IOP, and with probability by the completeness of the decoder (Lemma 3.31). The decoded bits are bits of , so is the query at the -th oracle gate and .
Soundness. Consider an instance with , and let be a cheating prover for our IOP. Since and has relative distance at least (Lemma 3.31), the first message of is -close to the encoding of at most one string. Let be this string if it is a valid witness of for , and otherwise; it is determined by . We consider three events:
: and ;
: and ;
: , , and for every .
If accepts, then , , and every oracle check passes, so one of , , occurs. Suppose toward a contradiction that
Then, by the union bound, , , or , and we show that each case is impossible.
Suppose . Let be the cheating prover for the encoded-witness IOP that runs in the IOP step and then stops; the first message and the decision bit in this run are distributed as and in our protocol. When , the first message is -far from , the set of encodings of valid witnesses of for , because it is -close to the encoding of at most one string and that string is not a valid witness. Therefore
contradicting the soundness of Lemma 3.36 (Definition 3.34).
Suppose . By averaging, there is a transcript of the IOP step together with a choice of the sampled gates, which fix , , and , conditioned on which occurs with probability greater than . Let be the cheating prover for the decoder that has this transcript and these gates hardwired and continues to run from the decoding step; the output of in this run is distributed as in our protocol under the same conditioning. Since is -close to , we get
contradicting the decoding error of Lemma 3.31 (Definition 3.30).
Suppose . When , it is a valid witness, so , and by robustness (Definition 3.14) for more than indices , with as in that definition. On the decoded bits are those of , so the -th decoded pair is , and every oracle check passes only if no sampled gate is one of these indices. The sampled set is uniformly random and independent of , which is determined by , sent before the sampling. Hence if , and if , a contradiction.
Hence accepts with probability at most . If , then , so there is no valid witness and only can occur.
Efficiency. The circuit has private input bits and gates, so Lemma 3.36 applies to it with as in the statement of the theorem, and the list has at most positions, where is one plus the maximum fan-in of an oracle gate, which is polylogarithmic by hypothesis. The round complexity, proof query complexity, proof length, and prover time are the sums of those of the IOP in Lemma 3.36 and of the decoder in Lemma 3.31; in particular the prover time is . The the verifier preprocessing time is that of the encoded-witness IOP plus the time to compute and the positions from . The verifier makes oracle queries, and its online time is that of the IOP plus that of the decoder plus to read the positions and form the queries, for a total of .
Relativizing Rewindable Interactive Proofs
In this section we formally define relativizing rewindable interactive proofs (Section 5.1), show how to turn any relativizing IOP into a relativizing RIP (Section 5.2), and define the efficiency that we aim for and prove our main theorem (Section 5.3); in Section A.1 we show that RIPs are as powerful as MIPs.
Definition
As mentioned in § 1, when the prover is an AI model, the verifier can save a snapshot of the model’s state and later restore it. We capture this by letting the verifier query the prover on any history of its choice. Since the prover may be assumed deterministic (Remark 5.6), it is determined by its next-message function, which maps the common input and a sequence of verifier messages to the prover’s reply after receiving these messages in this order; querying it on a history is the same as restoring the snapshot taken after that history and sending the last message.
Definition 5.1 (Rewindable interactive proof). A rewindable interactive proof () for a relation is a pair of a deterministic prover, given by its next-message function , and a probabilistic polynomial-time verifier with oracle access to , which it may query adaptively on any sequence of messages. The parties receive a common input , and the honest prover additionally receives a witness with . At the end, the verifier accepts or rejects.
The protocol satisfies the completeness and soundness properties defined below.
We write when the verifier accepts after interacting with the prover on common input . The probabilities below are over the verifier’s random bits.
Definition 5.2 (Completeness). An for has perfect completeness if, for every , the honest prover satisfies
Definition 5.3 (Soundness). An for has soundness error if, for every and every function from sequences of messages to replies,
Definition 5.4 (Relativizing RIP). Fix an oracle and a relativized relation as in Definition 3.5. A relativizing for is an for in which the verifier and the prover, including a cheating prover, have black-box access to the same oracle . The protocol relativizes if its completeness, soundness, and efficiency guarantees hold for for every oracle .
Remark 5.5 (Preprocessing). As in Remark 3.22, an with preprocessing for instances of the form has a verifier that is a pair . First receives and outputs a state . Then receives and and queries the prover. Completeness and soundness are as in Definitions 5.2 and 5.3.
Remark 5.6 (Deterministic prover). Assuming a deterministic prover loses no generality. For completeness, the honest prover’s random tape can be fixed and included in its state. For soundness, a randomized cheating prover is a distribution over deterministic next-message functions, so its acceptance probability is at most that of the best of them, provided that a snapshot includes the prover’s random tape.
We consider the following efficiency parameters of a (relativizing preprocessing) , where each query to counts as one message from the verifier and one from the prover:
Round complexity : the number of back-and-forth rounds between the verifier and the prover. Queries made in parallel count as one round.
Prover query complexity : the number of verifier queries to .
Communication complexity : the total number of bits in the verifier’s queries and the prover’s answers.
Verifier oracle query complexity : the number of verifier calls to an external oracle , when present.
Verifier preprocessing time : for an RIP with preprocessing (Remark 5.5), the running time of , which bounds .
Verifier online time : the running time of , with random access to .
Prover running time : the honest prover’s total time to answer all queries.
Saving and restoring a snapshot is not charged; the number of restores is at most the prover query complexity.
From IOPs to RIPs
The compilation is inspired by the standard one from an IOP to a two-prover protocol [22, 43], as applied to IOPs in [BCS16, Appendix A], in which one prover answers the verifier’s proof queries and a second, non-communicating prover answers one of them at random to bind the first to fixed proof strings, at the cost of dividing the rejection probability by the query count. With a rewindable prover the verifier binds the prover itself: it obtains each symbol of a proof string by restoring the prover to its state when that string was fixed, so the prover cannot answer adaptively and the compilation loses nothing in soundness.
Lemma 5.7 (IOP-to-RIP transformation). Let be a relativizing IOP (Definition 3.21) for a relativized relation with perfect completeness, soundness error , round complexity , and proof query complexity . Then can be transformed into a relativizing rewindable interactive proof (Definition 5.4) for with the following properties.
Perfect completeness.
Soundness error: at most .
Round complexity: .
Verifier oracle query complexity: the same as that of .
If has preprocessing (Remark 3.22), then so does (Remark 5.5), with the same verifier preprocessing. The verifier runs , and the honest prover runs once, with additional work only to process the query addresses and replies.
Proof. The protocol. The parties receive , and the honest prover also receives . Query addresses are tagged so that a history ending in a query is distinguishable from one ending in a verifier message.
Prover : runs on . On receiving a verifier message , it forwards to , which computes its next proof string, and replies with the empty message. On receiving a query after verifier messages, it replies with the symbol of the -th proof string.
Verifier : runs on and makes ’s oracle queries to itself. Whenever wishes to read position of the -th proof string, queries on the history , where are the messages that sent before the -th proof string, and hands the reply to as that symbol. Queries that makes at the same time are made in parallel, and a message that reads in full is obtained by querying all of its positions. accepts if and only if accepts.
In the snapshot view of Definition 5.1, querying on restores the prover to its state just after it fixed the -th proof string and asks for one symbol of it, which is why the prover cannot answer adaptively.
Completeness. The honest prover’s replies are the symbols of ’s proof strings, so the simulated sees exactly the honest IOP interaction and accepts with probability 1.
Soundness. Consider an instance and a cheating prover , which we may assume to be deterministic (Remark 5.6). Define a cheating IOP prover that, having received the verifier messages , sends the proof string
This is a valid IOP prover strategy, since depends only on messages available when string is sent. Every symbol that obtains from is the corresponding symbol of , so the view of the simulated against is exactly its view against , and accepts with probability at most .
Efficiency. The simulation uses the rounds of the IOP, with the queries of each round made in parallel, plus at most one round per query for queries that makes adaptively, for rounds in total. The verifier’s oracle queries are those of . The verifier’s work beyond ’s is to form the query addresses and copy the message prefixes, and the honest prover’s work beyond ’s is to restore snapshots and read symbols. Preprocessing is preserved since preprocesses exactly as does, and the argument applies verbatim when all parties have access to an oracle .
RIPs with linear-time provers and succinct verifiers
In our setting, the honest prover should take not much more time than evaluating the circuit, and the verifier should do substantially less work than evaluating the circuit itself. To verify the evaluation of an oracle circuit , we use an RIP with preprocessing for the relation of Definition 3.16: the parties receive the instance , where and , the honest prover receives the transcript , and the claim is that . We now prove our main theorem by applying the transformation of § 5.2 to the relativizing IOP of § 4.
Theorem 5.8. Fix and , and let be an oracle circuit with an input of length , an output of length , and gates, and let as in Theorem 4.1. Suppose that the oracle queries of have length polylogarithmic in . For every , , for instances with this circuit such that is -robust with respect to , has a relativizing rewindable interactive proof with preprocessing (Remark 5.5) with the following properties, where hides factors polylogarithmic in and running times count field operations.
Perfect completeness.
Soundness error: at most .
Round complexity: .
Communication complexity: field elements.
Verifier oracle query complexity: .
Verifier preprocessing time: .
Verifier online time: .
Prover time: .
In particular, for constant and , the prover runs in time , linear in the size of the computation, and the verifier’s online time is ; the number of oracle queries, , is sublinear in whenever grows without bound.
The proof applies the transformation of Lemma 5.7 to the IOP of Theorem 4.1 and reduces the soundness error to by sequential repetition, restoring the prover to its initial state before each run. We then remark on computing proof strings on demand (Remark 5.9).
Proof. Apply Lemma 5.7 to the IOP of Theorem 4.1. The result is a relativizing rewindable interactive proof with preprocessing with soundness error at most , rounds, verifier oracle queries, communication , verifier online time , verifier preprocessing time , and prover time . The verifier runs it times sequentially with fresh randomness, restoring the prover to its initial state before each run, and accepts if and only if every run accepts. Perfect completeness is preserved. For soundness, fix a false instance and a deterministic cheating prover . Since each run queries only on histories of that run, the runs are independent executions of the protocol against the same prover, each accepted with probability at most , so all are accepted with probability at most . The round complexity, communication, oracle queries, online time, and prover time are times those of one run, and the preprocessing is done once, which gives the stated parameters. □
Remark 5.9 (Computing proof strings on demand). Bitansky and Chiesa [11] observed that the provers of a multi-prover interactive proof [22] (Section A) need not store a proof: each only ever returns single symbols of proof strings, so it can compute each symbol when it is queried. Holmgren and Rothblum [50] sharpened this to provers with time and space for RAM computations. The same ability to compute symbols on demand is available to a rewindable prover, which also only returns single symbols: its state at the posting of a string already determines the answer at every position, and restoring that state before each query keeps the answer from depending on anything later, so the honest prover can fix a proof string without computing or storing it in full. This is an advantage over hash-based SNARGs: in a Merkle-based compilation of an IOP into a SNARG such as Flock's [26], the prover must compute every proof string in full in order to hash it. Computing on demand can be used to save prover time or prover space:
Prover time. Most known linear-time provers come from tensor and interleaved codes of linear-time encodable codes [13, 57, 16, 15, 65, 46, 12, 19], as does the prover of Theorem 5.8, which specifically uses TensorSwitch [19] (Lemma 3.31). The concretely fastest IOPs, including Flock's, which our implementation builds on (§ 6), encode with Reed–Solomon codes instead, whose encoding relies on the fast Fourier transform (FFT) and makes their provers quasi-linear: the linear-time instantiation is at present a theoretical result. Computing on demand avoids part of the FFT: our compilation of Flock's IOP applies only the first layers of the FFT to every row when it posts a proof string and finishes the remaining layers of a row only when the verifier asks for it. Together with the removal of the hash function and the smaller security parameter, this accounts for the speedup of our prover over Flock's SNARG prover in § 6.3.
Prover space. Theorem 5.8 bounds the prover's time but not its space, and as described the honest prover stores the encoding of its witness, which takes space . Suppose that computes the -step execution of an oracle machine that uses space , so that and the prover can regenerate in space by running the machine again. Then, for the Reed–Solomon instantiation, each message of the prover can be computed in one pass over the regenerated , as in the streaming prover of Cormode, Mitzenmacher, and Thaler [37], so the prover runs in space and in time , at the price of running the machine, and hence querying , once per round. The verifier is unchanged. We do not work out the details here.
Implementation and Experiments
As a proof of concept, we implement our protocol and evaluate it on an MNIST task inspired by the AI debate experiment of Irving, Christiano, and Amodei [51]. Briefly, in their experiment, there are two provers, or agents, and a judge which is trained to classify an MNIST image from a few nonzero pixels. A random MNIST image is shown to the agents but not to the judge. One agent claims the correct label and the other agent claims an incorrect label, e.g., the image contains a 5, and one claims 5 and the other claims 6. They take turns revealing a nonzero pixel in the image to the judge until four or six pixels are revealed. Then the judge chooses which agent wins based on which of their labels has the higher logit. Their experiment studies how often an honest agent wins against a dishonest one; we instead measure the cost of verifying a robust computation that uses their judge as its oracle.
Following their experiment, we train a sparse MNIST classifier using the same architecture; it correctly classifies 59.4% of random six-pixel views. We use its predictions to define an oracle: given a sparse view and a candidate digit , the oracle outputs 1 if the classifier predicts and 0 otherwise. Our circuits query this oracle on many sparse views of an image and output whether a majority of the views vote for the candidate digit. We vary the number of sparse views to study how the cost of verification scales with the size of the circuit. We also compile an existing IOP for a standard, oracle-free computation, Flock’s IOP for BLAKE3 [26], into an RIP and compare it with Flock’s own SNARG (§ 6.3).
Implementation
Our implementation is open source2 and written in Rust. It follows the construction of § 5, building the encoded-witness IOP of § 3.4 from components of Binius [40], Flock [26], and Ligero [3], and compiling it into an RIP as in Lemma 5.7: the prover keeps each proof string it computes instead of sending it, and the verifier reads a symbol of a proof string by restoring the prover to its state at the moment that string was fixed and asking for that symbol, so that no answer can depend on anything the verifier sent later. The proof strings are opened in the layout of Ligero [3]: the encoded witness is arranged in rows of about entries and the verifier reads 64 whole columns, which gives a proximity error below . Together with sampled oracle gates, the smallest number with for the circuit’s robustness parameter , a single execution of the protocol has soundness error at most at every circuit size, against computationally unbounded provers; there are no repetitions.
The majority circuit sums the oracle answers in a tree whose levels consist of identical blocks, so the verifier’s work for a level is that of one block and this circuit family needs no preprocessing; for a general circuit, the preprocessing of Remark 5.5 would take its place. The classifier’s answers are computed in advance, so both the protocol and direct evaluation of the circuit query the oracle by table lookup. All timings are from AWS Graviton4 instances, one single-threaded process per core, with transparent huge pages enabled. Absolute times are specific to that core; every ratio below is between measurements on the same core type.
MNIST experiments
Concretely, call an MNIST image with six nonzero pixels revealed a view. For each circuit, we fix an MNIST image together with randomly sampled views of the image; the image and views are hardwired into the description of the circuit. On input a candidate digit , the circuit queries the oracle on each of its views and outputs 1 if more than half of the views vote for . We can compute the robustness parameters for these circuits exactly: for each digit , we compute the minimum number of oracle answers that would need to be changed in order to flip the output of the circuit on . Let be the minimum of this quantity over all ten digits. Then changing at most oracle answers cannot change the output of the circuit on any input, so the circuit is -robust with respect to every input.
To choose instances to run our circuit on, we scan the MNIST test set in order. For each image, we sample random views and construct the corresponding circuit. We select the first 50 images for which this circuit accepts the correct digit and has robustness parameter at least . We use these same 50 images throughout the experiment, and consider
sampling additional views of each image as increases (one image has fewer than distinct six-pixel views and three have fewer than ; those images are omitted at those sizes). For each image and circuit size, we recompute the robustness parameter and run the complete protocol once, at soundness error . The median robustness parameter remains between 0.30 and 0.32 at every circuit size.
All runs with the honest provers accepted, as expected from perfect completeness. Table 1 reports detailed costs, and Figure 1 shows how the verifier scales relative to direct evaluation. All values are medians over the images.

Figure 1. Verifier cost compared with direct circuit evaluation as the number of oracle gates increases, for one execution of the protocol at soundness error . Curves are medians over the selected MNIST images (50, or 49 and 47 at the two largest sizes). Left: verifier online time compared with one direct circuit evaluation. Right: verifier oracle queries compared with the queries made by direct evaluation. Both axes are logarithmic.
| V oracle queries | direct eval. | V online | P | |
| 76 | 0.064 s | 6,976× | 4,809× | |
| 74 | 0.238 s | 2,081× | 1,635× | |
| 75 | 0.936 s | 558× | 567× | |
| 75 | 3.73 s | 172× | 237× | |
| 76 | 14.9 s | 46.2× | 117× | |
| 76 | 59.6 s | 13.4× | 79.5× | |
| 76 | 238.3 s | 3.97× | 64.8× | |
| 76 | 953.1 s | 1.17× | 60.9× | |
| 78 | 3.83 ms | 0.39× | 59.2× | |
| 80 | 15.51 ms | 0.12× | 58.8× |
Table 1. Cost of the protocol on the MNIST circuits, one execution at soundness error (Graviton 4, one core): medians over the 50 images, or over those with enough distinct views at the two largest sizes. “Direct eval.” is the time to evaluate the circuit directly, one table lookup per view and the majority. Verifier online time and prover time are reported as multiples of it; there is no preprocessing. P includes witness generation.
Since the robustness parameter remains nearly constant, the median number of oracle queries made by the verifier stays between 74 and 80 as grows from to . At views, the verifier makes 840,000 fewer oracle queries than the circuit. The verifier’s online time also grows much more slowly than direct evaluation: it grows from 0.45 ms to 1.9 ms, while direct evaluation grows from 0.06 s to 16 ms. Because direct evaluation costs only about 0.23 ns per view, the two cross between and views, and at the verifier takes 0.12 as long as direct evaluation. This baseline is pessimistic for the protocol: both direct evaluation and the protocol answer oracle queries by table lookup, whereas in the intended setting each query is a model evaluation and dominates everything else. With a costly oracle, direct evaluation pays evaluations while the verifier pays his 74 to 80, so the crossing would come at a far smaller circuit, and the prover’s overhead over direct evaluation would shrink toward the cost of its field arithmetic alone; the oracle-query counts in Table 1 are the measure that transfers.
At small , the verifier is slower than direct evaluation because protocol overhead dominates: the verifier performs the IOP interaction and opening checks, whereas direct evaluation requires only table lookups. As grows, direct evaluation grows linearly, while the verifier’s time grows by a factor of 1.1 to 1.3 per fourfold increase in , so their ratio falls by a factor of 3.0 to 3.7 per step. The verifier time grows because our implementation uses the Ligero layout [3], whose openings have size about , rather than the polylogarithmic cost in Theorem 5.8.
The prover cost settles at a constant multiple of direct evaluation from on: the prover, which generates the witness and makes all oracle lookups, takes about 60× direct evaluation (0.9 s at views); at the small sizes it is dominated by fixed costs.
Comparison with a SNARG
In Section 1 we argued that rewinding brings efficiency gains over a SNARG. The relativizing protocols of Chen, Kalai, and Xi [34] offer no comparison, since they have no implementation and their prover is only polynomial-time, so we compare prover time against the best known concretely efficient proof system for ordinary, oracle-free computations, Flock [26], whose IOP proves batches of BLAKE3 compressions and whose SNARG, a succinct non-interactive argument, compiles it with Merkle commitments. A SNARG is how an IOP is made practical in the applications of proof systems to date, where the verifier has no control over the prover’s machine and so cannot rewind it: the IOP’s proof strings are committed to with a hash function and the interaction is removed. Rewinding is another way to make the same IOP practical, so comparing our compilation with Flock’s SNARG measures what each way costs. We compiled Flock’s IOP into an RIP, keeping its proof strings, queries, and checks: the prover runs Flock’s prover with the Merkle commitments removed, and the verifier rewinds it to its state at each proof string’s posting before every row query, as in the compilation of Lemma 5.7, so that its answers depend on the posting alone; the verifier runs Flock’s verifier on those rows. A false statement is then accepted with at most the IOP’s own error (Lemma 5.7).
The RIP gains in three ways over the SNARG. It needs no hash function, since rewinding replaces the Merkle commitment. Nor does it need to encode every proof string in full, since nothing is hashed: the prover applies only the first layers of the FFT when it posts a string and finishes a row only when it is queried (Remark 5.9). And it needs far fewer bits of security: a SNARG prover can retry offline until the hash-derived challenges are favorable, so Flock’s default configuration targets a 128-bit per-round work factor, whereas a cheating prover in the RIP gets one attempt per execution, which the verifier observes, so 40 bits suffice. We therefore run Flock’s IOP at its 40-bit interactive parameter setting and, since a smaller field suffices as well, over a 64-bit base field with a 128-bit extension for the challenges, which Flock’s release does not offer and which halves the field arithmetic. The error is to at these sizes, assuming that the IOP’s query and algebraic error terms compose statistically, as Flock’s parameter code assumes.
Table 2 reports prover times at to witness bits ( to compressions) on one Graviton 4 core, medians of three executions. Our prover is 1.8 to faster than Flock’s SNARG prover at every size.
| witness bits | Flock’s SNARG prover | our prover | speedup |
| 89.9 ms | 46.7 ms | ||
| 101.6 ms | 54.7 ms | ||
| 153.9 ms | 86.9 ms | ||
| 480.1 ms | 223.7 ms | ||
| 1.23 s | 694.2 ms | ||
| 4.81 s | 2.66 s | ||
| 19.8 s | 10.6 s |
Table 2. Prover time for Flock’s IOP for BLAKE3 compiled as Flock’s SNARG (default configuration, Merkle commitments, sound against bounded provers) and as our protocol over a 64-bit base field at the 40-bit interactive parameters, with the prover rewound before each query (sound against unbounded provers with the IOP’s own error, to ). The speedup is Flock’s SNARG prover’s time divided by ours. Medians of three executions on one Graviton 4 core, including witness generation.
Limitations
Our experiments are intended as a proof of concept rather than as a realistic scalable-oversight benchmark. The circuits are simple majority circuits over random sparse views, and the 50 images are selected so that their circuits have robustness parameter at least 1/8; thus, the experiments do not show that arbitrary MNIST instances or more complex oracle computations satisfy our robustness assumption. Moreover, unlike in the MNIST debate experiment, the sparse views are sampled randomly instead of chosen adversarially (by debating agents). The majority is also a statistical quantity: for a majority over hardwired views, the verifier could estimate the output himself by sampling about as many views as he queries in the protocol, with no prover at all. The protocol is needed for circuits that process the oracle answers further or choose later queries from earlier answers; our circuits do neither.
Because the image and views are hardwired into the circuit, each image and circuit size is its own instance; the verifier needs no preprocessing here only because the majority circuit’s levels consist of identical blocks, and a general circuit would need the preprocessing of Remark 5.5, with its own amortization question. The verifier’s time grows with the square root of the trace, from the Libero layout of the opening, rather than polylogarithmically as in Theorem 5.8. Even though the verifier becomes cheaper than direct evaluation on the largest circuits, the prover cost remains a constant factor over direct evaluation, about 60× at the largest sizes, where direct evaluation is table lookups and the prover performs field arithmetic over the entire encoded witness; on the BLAKE3 instances, where there is no such gap to begin with, our prover is cheaper than the SNARG’s. The protocol also treats saving and restoring the prover’s state as free; for a real model each restore copies its state, and in both compilations the prover is restored before every query.
AI Disclosure
We used generative AI tools to write large portions of the code for our implementation and experiments, draft and edit sections of this paper, proofread the paper to catch potential bugs and suggest writing improvements, do a literature review, and help with numerical calculations. All AI-generated text and code was manually reviewed and verified by the authors. For example, we tested AI-generated code and checked consistency against the theoretical protocol, and we did a manual literature survey. The theoretical model and construction were developed solely by the authors. We take full responsibility for the content of this work.
Acknowledgments
The authors would like to acknowledge support provided by the UK AISI alignment project. Ziyi Guan thanks Benedikt Bünz, Alessandro Chiesa, Giacomo Fenzi, Christian Knabenhans, William Wang, and Andrew Zitek for helpful discussions on the implementations of the protocols.
References
Multi-prover interactive proofs
Rewindable interactive proofs are closely related to multi-prover interactive proofs (MIPs) [22]: a restored snapshot gives the verifier an interaction that the prover cannot connect to any other, much as a second non-communicating prover would. MIPs are in turn equivalent in power to probabilistically checkable proofs (PCPs) [41, 5, 4], since two non-communicating provers can simulate a proof string, at a loss in soundness, and a proof string can hold the provers’ strategies [43]; we therefore present only the equivalence of MIPs and RIPs. This appendix recalls the definition of MIPs and shows that the two models have the same power (Section A.1): every MIP is an RIP with the same soundness error, and every RIP whose verifier makes queries to the prover is a two-prover MIP with soundness error .
A multi-prover interactive proof lets several powerful provers try to convince a weak verifier that an instance has a valid witness.
Definition A.1 (Multi-prover interactive proof system). A -prover interactive proof for a relation is an interactive protocol between a probabilistic polynomial-time verifier and computationally unbounded provers . The parties receive a common input , and the honest provers additionally receive a witness with .
The provers may agree on a strategy beforehand but cannot communicate during the protocol: each prover’s messages depend only on , its agreed strategy, and its own interaction with the verifier. At the end of the interaction, the verifier accepts or rejects.
The protocol satisfies the completeness and soundness properties defined below.
We write when the verifier accepts after interacting with the provers on common input . The probabilities below are over the verifier’s private random bits (we assume without loss of generality that the provers are deterministic).
Definition A.2 (Completeness). An MIP for has perfect completeness if, for every , the honest provers satisfy
Definition A.3 (Soundness). An MIP for has soundness error if, for every and every tuple of possibly computationally unbounded cheating provers ,
Definition A.4 (Relativizing MIP). Fix an oracle and a relativized relation as in Definition 3.5. A relativizing MIP for is an MIP for in which the verifier and all provers, including cheating provers, have black-box access to the same oracle . The protocol relativizes if its completeness, soundness, and efficiency guarantees hold for for every oracle .
Remark A.5 (Preprocessing). As in Remark 3.22, an MIP with preprocessing for instances of the form has a verifier that is a pair . First receives and outputs a state . Then receives and and interacts with the provers. Completeness and soundness are as in Definitions A.2 and A.3.
Efficiency parameters are as for RIPs (§ 5.1), with parallel exchanges with different provers counting as one round and the prover running time taken as the sum over the honest provers.
Relation to RIPs
Rewindable interactive proofs are as powerful as MIPs: every MIP is a rewindable interactive proof with the same soundness error, and two provers can simulate a rewindable prover at a loss in the soundness error.
Lemma A.6 (MIP to RIP). Every -prover interactive proof for with perfect completeness and soundness error yields a rewindable interactive proof for with perfect completeness and soundness error , the same verifier complexity up to tagging each message with a prover index, and the same prover running time. If the MIP has preprocessing (Remark A.5), so does the RIP (Remark 5.5), with the same verifier preprocessing. The same holds for relativizing protocols.
Proof. Let be the MIP. The new verifier runs , and whenever has sent messages to prover , it obtains that prover’s reply by querying the rewindable prover on the history . The honest rewindable prover answers a history tagged with as would, so completeness is preserved. For soundness, given any function , define cheating MIP provers by . Each depends only on its own history, so these are valid non-communicating MIP provers, and the new verifier’s view against is exactly that of against . Hence the acceptance probability is at most , so . The new verifier preprocesses exactly as does, and the same argument applies verbatim when all parties have access to an oracle .
Lemma A.7 (RIP to MIP). Every rewindable interactive proof for with perfect completeness and soundness error in which the verifier makes at most queries to the prover yields a two-prover interactive proof for with perfect completeness and soundness error , with one additional round, in which the first prover answers the verifier’s queries and the second prover answers one query. The same holds for relativizing protocols and for protocols with preprocessing.
Proof. The verifier runs the RIP, sending each query to the first prover, and at the end sends one of the queries, chosen uniformly at random, to the second prover and rejects if the two answers differ. With honest provers the answers always agree. For soundness, the second prover’s answers define a single next-message function, hence a cheating RIP prover . Let be the event that the first prover’s answers agree with on every queried history. On the simulated RIP verifier’s view is its view against , so . Otherwise some answer disagrees, and the second prover’s query, chosen independently of the transcript, lands on it with probability at least , so . Writing , the acceptance probability is at most , with the maximum at .
References
- [1]Akshima, Renas Bacho, Yu-Hsuan Huang, Eike Kiltz, Aysan Nishaburi, Samin Nooripoor, Noah Tittelbach, and Emiel Wiedijk. A Subexponential Time Algorithm for Elliptic Curve Discrete Logarithm. Preprint, 28 October 2026. 2026. URL: https://github.com/bochum-crypto/subexponential-ecdl.
- [2]Noga Amit, Shafi Goldwasser, Orr Paradise, and Guy Rothblum. “Models that prove their own correctness”. In: arXiv preprint arXiv:2405.15722 (2024).arxiv.org/abs/2405.15722
- [3]Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. “Ligero: Lightweight Sublinear Arguments Without a Trusted Setup”. In: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 2017, pp. 2087–2104. DOI: 10.1145/3133956.3134104. URL: https://doi.org/10.1145/3133956.3134104.
- [4]Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. “Proof verification and the hardness of approximation problems”. In: Journal of the ACM (JACM) 45.3 (1998), pp. 501–555.
- [5]Sanjeev Arora and Shmuel Safra. “Probabilistic checking of proofs: A new characterization of NP”. In: Journal of the ACM (JACM) 45.1 (1998), pp. 70–122.
- [6]Scott Aaronson and Avi Wigderson. “Algebrization: A New Barrier in Complexity Theory”. In: ACM Transactions on Computation Theory 1.1 (2009), 2:1–2:54. DOI: 10.1145/1490270.1490272. URL: https://www.scottaaronson.com/papers/alg.pdf.DOI
- [8]László Babai. “Trading group theory for randomness”. In: Proceedings of the seventeenth annual ACM symposium on Theory of computing. 1985, pp. 421–429.DOI
- [9]Beth Barnes. Debate update: Obfuscated arguments problem. AI Alignment Forum post. 2020. URL: https://www.alignmentforum.org/posts/PJLABqQ962hZEqhdB/debate-update-obfuscated-arguments-problem (visited on 06/26/2025).
- [11]Nir Bitansky and Alessandro Chiesa. “Succinct Arguments from Multi-prover Interactive Proofs and Their Efficiency Benefits”. In: Advances in Cryptology – CRYPTO 2012. Vol. 7417. Lecture Notes in Computer Science. Springer, 2012, pp. 255–272. DOI: 10.1007/978-3-642-32009-5_16. URL: https://www.iacr.org/archive/crypto2012/74170253/74170253.pdf.DOI
- [12]Martijn Brehm, Binyi Chen, Ben Fisch, Nicolas Resch, Ron D. Rothblum, and Hadas Zeilberger. “Blaze: Fast SNARKs from Interleaved RAA Codes”. In: Advances in Cryptology – EUROCRYPT 2025. Vol. 15604. Lecture Notes in Computer Science. Springer, 2025, pp. 123–152. DOI: 10.1007/978-3-031-91134-7_5. URL: https://link.springer.com/chapter/10.1007/978-3-031-91134-7_5.DOI
- [13]Jonathan Bootle, Alessandro Chiesa, and Jens Groth. “Linear-Time Arguments with Sublinear Verification from Tensor Codes”. In: Theory of Cryptography – TCC 2020. Vol. 12551. Lecture Notes in Computer Science. Springer, 2020, pp. 19–46. DOI: 10.1007/978-3-030-64378-2_2. URL: https://link.springer.com/chapter/10.1007/978-3-030-64378-2_2.DOI
- [14]Annalisa Barbara, Alessandro Chiesa, and Ziyi Guan. “Relativized Succinct Arguments in the ROM do not Exist”. In: TCC (1). Vol. 16268. Lecture Notes in Computer Science. Springer, 2025, pp. 400–416. DOI: 10.1007/978-3-032-12287-2_14. URL: https://eprint.iacr.org/2024/728.DOI
- [15]Jonathan Bootle, Alessandro Chiesa, Ziyi Guan, and Siqi Liu. Linear-Time Probabilistic Proofs with Sublinear Verification for Algebraic Automata over Every Field. Cryptology ePrint Archive, Paper 2022/1056. 2022. URL: https://eprint.iacr.org/2022/1056.
- [16]Jonathan Bootle, Alessandro Chiesa, and Siqi Liu. “Zero-Knowledge IOPs with Linear-Time Prover and Polylogarithmic-Time Verifier”. In: Advances in Cryptology – EUROCRYPT 2022. Vol. 13276. Lecture Notes in Computer Science. Springer, 2022, pp. 275–304.DOI
- [18]László Babai, Lance Fortnow, Leonid A. Levin, and Mario Szegedy. “Checking computations in polylogarithmic time”. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing. STOC ’91. 1991, pp. 21–31.DOI
- [19]Benedikt Bünz, Giacomo Fenzi, Ron D. Rothblum, and William Wang. “Tensor-Switch: Nearly Optimal Polynomial Commitments from Tensor Codes”. In: Advances in Cryptology – CRYPTO 2026. Vol. 16808. Lecture Notes in Computer Science. Springer, 2026, pp. 297–329. DOI: 10.1007/978-3-032-35424-2_11. URL: https://eprint.iacr.org/2025/2065.DOI
- [20]Benedikt Bünz, Ben Fisch, and Alan Szepieniec. “Transparent SNARKs from DARK Compilers”. In: Advances in Cryptology – EUROCRYPT 2020. Vol. 12105. Lecture Notes in Computer Science. Springer, 2020, pp. 677–706. DOI: 10.1007/978-3-030-45721-1_24. URL: https://link.springer.com/chapter/10.1007/978-3-030-45721-1_24.DOI
- [21]Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, and Salil Vadhan. “Robust PCPs of proximity, shorter PCPs and applications to coding”. In: Proceedings of the thirty-sixth annual ACM symposium on Theory of computing. 2004, pp. 1–10.
- [22]Michael Ben-Or, Shafi Goldwasser, Joe Kilian, and Avi Wigderson. “Multi-prover interactive proofs: how to remove intractability assumptions”. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing. Association for Computing Machinery, 1988, pp. 113–131.
- [23]Jonah Brown-Cohen, Geoffrey Irving, and Georgios Piliouras. “Scalable AI safety via doubly-efficient debate”. In: Proceedings of the 41st International Conference on Machine Learning. 2024, pp. 4585–4602.
- [24]Jonah Brown-Cohen, Geoffrey Irving, and Georgios Piliouras. “Avoiding Obfuscation with Prover-Estimator Debate”. In: arXiv preprint arXiv:2506.13609 (2025).
- [25]Marie Davidsen Buhl, Jacob Pfau, Benjamin Hilton, and Geoffrey Irving. “An alignment safety case sketch based on debate”. In: arXiv preprint arXiv:2505.03989 (2025).arxiv.org/abs/2505.03989
- [26]Benedikt Bünz, Ron D. Rothblum, and William Wang. Flock: Fast Proving for Batch Boolean Computations. Cryptology ePrint Archive, Paper 2026/1329. 2026. URL: https://eprint.iacr.org/2026/1329.arxiv.org/abs/2607.27491
- [27]Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. “Zerocash: Decentralized Anonymous Payments from Bitcoin”. In: IEEE Symposium on Security and Privacy. 2014, pp. 459–474. DOI: 10.1109/SP.2014.36.
- [28]Binyi Chen, Benedikt Bünz, Dan Boneh, and Zhenfei Zhang. “HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates”. In: Advances in Cryptology – EUROCRYPT 2023. Vol. 14005. Lecture Notes in Computer Science. Springer, 2023, pp. 499–530. DOI: 10.1007/978-3-031-30617-4_17. URL: https://link.springer.com/chapter/10.1007/978-3-031-30617-4_17.DOI
- [29]Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Håstad, Desh Ranjan, and Pankaj Rohatgi. “The Random Oracle Hypothesis Is False”. In: Journal of Computer and System Sciences 49.1 (1994), pp. 24–39. DOI: 10.1016/S0022-0000(05)80084-4. URL: https://userpages.cs.umbc.edu/chang/papers/roh/.DOI
- [34]Liyan Chen, Yael Tauman Kalai, and Zoe Xi. “How to Avoid Debate: Scalable AI Safety via Doubly-Efficient Interactive Proofs”. In: arXiv preprint arXiv:2607.03561 (2026).
- [35]Alessandro Chiesa and Siqi Liu. “On the Impossibility of Probabilistic Proofs in Relativized Worlds”. In: 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Vol. 151. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020, 57:1–57:30. DOI: 10.4230/LIPIcs.ITCS.2020.57. URL: https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.57.
- [36]Claude (Anthropic). A 2^{o(n)} Time Algorithm for 3-SAT. Preprint, October 2026. 2026. URL: https://github.com/anthropics/formal-math/tree/main/eth.
- [37]Graham Cormode, Michael Mitzenmacher, and Justin Thaler. “Practical Verified Computation with Streaming Interactive Proofs”. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. 2012, pp. 90–112. DOI: 10.1145/2090236.2090245. URL: https://arxiv.org/abs/1105.2003.
- [40]Benjamin E. Diamond and Jim Posen. “Succinct Arguments over Towers of Binary Fields”. In: Advances in Cryptology – EUROCRYPT 2025. Vol. 15604. Lecture Notes in Computer Science. Springer, 2025, pp. 93–122. DOI: 10.1007/978–3–031–91134–7_4. URL: https://link.springer.com/chapter/10.1007/978–3–031–91134–7_4.DOI
- [41]Uriel Feige and Joe Kilian. “Making games short”. In: Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. 1997, pp. 506–516.DOI
- [42]Lance Fortnow. “The Role of Relativization in Complexity Theory”. In: Bulletin of the EATCS 52 (1994), pp. 229–243.
- [43]Lance Fortnow, John Rompel, and Michael Sipser. “On the Power of Multi-Prover Interactive Protocols”. In: Theoretical Computer Science 134.2 (1994), pp. 545–557.DOI
- [44]Lance Fortnow and Michael Sipser. “Are There Interactive Protocols for co-NP Languages?” In: Information Processing Letters 28.5 (1988), pp. 249–251.DOI
- [45]Shafi Goldwasser, Yael Tauman Kalai, and Guy N. Rothblum. “Delegating computation: interactive proofs for muggles”. In: Journal of the ACM (JACM) 62.4 (2015), 27:1–27:64.
- [46]Alexander Golovnev, Jonathan Lee, Srinath Setty, Justin Thaler, and Riad S. Wahby. “Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS”. In: Advances in Cryptology – CRYPTO 2023. Vol. 14082. Lecture Notes in Computer Science. Springer, 2023, pp. 193–226. DOI: 10.1007/978–3–031–38545–2_7. URL: https://link.springer.com/chapter/10.1007/978–3–031–38545–2_7.DOI
- [47]Shafi Goldwasser, Silvio Micali, and Charles Rackoff. “The knowledge complexity of interactive proof-systems”. In: Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali. ACM, 2019, pp. 203–225.
- [48]Lewis Hammond and Sam Adam-Day. “Neural interactive proofs”. In: arXiv preprint arXiv:2412.08897 (2024).arxiv.org/abs/2412.08897
- [49]Juris Hartmanis, Richard Chang, Suresh Chari, Desh Ranjan, and Pankaj Rohatgi. “Relativization: A Revisionistic Retrospective”. In: Bulletin of the EATCS 47 (1992), pp. 144–153.DOI
- [50]Justin Holmgren and Ron D. Rothblum. “Delegating Computations with (Almost) Minimal Time and Space Overhead”. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2018, pp. 124–135. DOI: 10.1109/FOCS.2018.00021. URL: https://eprint.iacr.org/2018/861.DOI
- [51]Geoffrey Irving, Paul Christiano, and Dario Amodei. “AI safety via debate”. In: arXiv preprint arXiv:1805.00899 (2018).arxiv.org/abs/1805.00899
- [52]Geoffrey Irving and Simon Marshall. The need to relativise in debate. AI Alignment Forum post. June 2025. URL: https://www.alignmentforum.org/posts/xycoFucvXAPhcgJQa/the-need-to-relativise-in-debate-1 (visited on 06/26/2025).
- [53]Jan Hendrik Kirchner, Yining Chen, Harri Edwards, Jan Leike, Nat McAleese, and Yuri Burda. “Prover-verifier games improve legibility of llm outputs”. In: arXiv preprint arXiv:2407.13692 (2024).arxiv.org/abs/2407.13692
- [54]Jonathan Katz and Luca Trevisan. “On the efficiency of local decoding procedures for error-correcting codes”. In: Proceedings of the thirty-second annual ACM symposium on Theory of computing. 2000, pp. 80–86.DOI
- [56]OpenAI. The Exponential Time Hypothesis is False. Preprint, 17 October 2026, revised 25 October 2026. 2026. URL: https://github.com/openai/math.
- [57]Noga Ron-Zewi and Ron D. Rothblum. “Proving as Fast as Computing: Succinct Arguments with Constant Prover Overhead”. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing. Association for Computing Machinery, 2022, pp. 1353–1363. DOI: 10.1145/3519935.3519956. URL: https://doi.org/10.1145/3519935.3519956.
- [58]Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. “Constant-round interactive proofs for delegating computation”. In: Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. 2016, pp. 49–62.
- [59]Guy N. Rothblum, Salil Vadhan, and Avi Wigderson. “Interactive proofs of proximity: delegating computation in sublinear time”. In: Proceedings of the forty-fifth annual ACM symposium on Theory of computing. 2013, pp. 793–802.
- [61]Daniel A. Spielman. “Linear-time encodable and decodable error-correcting codes”. In: IEEE Transactions on Information Theory 42.6 (1996), pp. 1723–1731.
- [62]Justin Thaler. “Time-Optimal Interactive Proofs for Circuit Evaluation”. In: Advances in Cryptology – CRYPTO 2013, Part II. Vol. 8043. Lecture Notes in Computer Science. Springer, 2013, pp. 71–89. DOI: 10.1007/978–3–642–40084–1_5. URL: https://link.springer.com/chapter/10.1007/978–3–642–40084–1_5.arxiv.org/abs/1304.3812
- [63]Justin Thaler. “Proofs, Arguments, and Zero-Knowledge”. In: Found. Trends Priv. Secur. 4.2-4 (2022), pp. 117–660. DOI: 10.1561/3300000030. URL: https://doi.org/10.1561/3300000030.
- [64]Stephan Wä_ldchen, Kartikey Sharma, Berkant Turan, Max Zimmer, and Sebastian Pokutta. Interpretability Guarantees with Merlin-Arthur Classifiers. 2024. arXiv: 2206.00759 [cs.LG]. URL: https://arxiv.org/abs/2206.00759.
- [65]Tiancheng Xie, Yupeng Zhang, and Dawn Song. “Orion: Zero Knowledge Proof with Linear Prover Time”. In: Advances in Cryptology – CRYPTO 2022. Vol. 13510. Lecture Notes in Computer Science. Springer, 2022, pp. 299–328. DOI: 10.1007/978–3–031–15985–5_11. URL: https://link.springer.com/chapter/10.1007/978–3–031–15985–5_11.