The PIOP and IOP Models

A PCS (polynomial commitment scheme) is a protocol between the prover and the verifier by the aid of which the prover might commit to a multilinear polynomial and the verifier might later evaluate it at arbitrary points. The pithy way of saying this is:

Of course, "perfectly honest oracle machines" don't exist in real life. But that's the point: the point of (secure) PCSs is to allow us to act as if they did. Indeed, when it comes down to defining the security of multilinear PCSs, the natural way to proceed is to essentially prove that the protocol is as good as an oracle machine of the above form, so that in practice, we may simply "pretend" that we had the oracle machine and move on accordingly. We refer to [DP23, § 3.2] for a rigorous treatment of this security definition.

This is the basic idea of PIOP–PCS separation. Once we've gone through the work of defining the PCS, we may progress to the PIOP. A PIOP (polynomial interactive oracle proof) is, by definition, a protocol between the prover and verifier which takes place in the enriched computational model in which the abstract polynomial oracle machine above is simply assumed to exist. That is, the prover and verifier may freely send each other messages, proceeding over multiple rounds of interaction; moreover, they may freely make use of the polynomial oracle throughout the protocol's various phases.

This model is extremely useful for us, since it allows us to run interactive protocols—like the sumcheck—which reduce directly to multilinear evaluation claims. We can, one the one hand, describe and build interactive protocols like this one, getting as much mileage as we can out of the abstract oracle machine. On the other hand, we ultimately have to implement and build that abstract machine in the first place. Separating these tasks makes things conceptually easier to deal with.

The reductions section of this site takes place above the PIOP–PCS boundary (on the PIOP side). The cryptography section of this site takes place below it (on the PCS side).

The IOP Model

Above, we sketched a boundary line, hinging on whether or not we assume the existence of the polynomial oracle machine. Above the boundary, we get the PIOP model, in which an abstract polynomial oracle machine is assumed to exist. Beneath the boundary, the polynomial oracle doesn't exist (and our job is to make it!).

In the lower of these two regions, do the parties get nothing at all? As we argue now, it will be convenient—and justified—to postulate, in the lower region, a different, and much-weaker, sort of oracle, which we'll call the string oracle. While the polynomial oracle was capable of receiving multilinear polynomials, and later evaluating them anywhere, the string oracle is much weaker: it's only capable of receiving lists of field elements, and later returning specific elements of the list to the verifier.

Merkle Commitments

Why is it justified to postulate the existence of the string oracle in the region beneath the boundary? As should be clear by now, whenever we postulate an abstract computational model in which some idealized oracle is assumed to exist, it becomes incumbent on us to actually instantiate that oracle. Our payoff, of course, is getting to work in that idealized model, in which many logistical tasks get abstracted away. The one-time cost is instantiating that oracle. An entire section of this site area is devoted to instantiating the polynomial oracle. Why do we get to assume the string oracle for free, while we go about doing so?

The answer is: we don't. Indeed, we need to instantiate the string oracle too, in the even-weaker model in which even it doesn't exist (i.e., the "plain" random oracle model, in which we just get an idealized random function—basically, a hash function). Thankfully, the string oracle is fairly straightforward to instantiate. The basic idea is due to Ben-Sasson, Chiesa and Spooner [BCS16], and uses Merkle trees.

We review the details here. When the prover wants to ship off a list of elements to the string oracle, instead, it computes a Merkle tree on top of these elements—that is, a balanced, binary tree whose leaves are the elements of its list, and in which each intermediate node is the hash of its children—and then sends just the root of this tree to the verifier. This root serves as the prover's "commitment" to the tree's leaves, and is kept by the verifier.

Later, when the verifier wants to ask the string oracle for some specific element of a committed list, it instead asks the prover for that element. The prover sends the element, together with a Merkle path attesting to the validity of that element (vis-à-vis the Merkle root it already forked over to the verifier). The verifier finally checks this path before accepting the prover's element.

It can be shown rigorously that this technique is secure: only by finding a collision in the random oracle might the prover successfully manage to trick the verifier (i.e., to pawn off onto the verifier a claimed list element that it didn't already have when it made its original list). This fact justifies our decision to work in the IOP model while we instantiate our polynomial commitment scheme.

A Hierarchy of Models

Stepping back from the above, we really see a hierarchy consisting of three successively richer models. We initially described a dividing line, above which resides the PIOP model (in which the full-featured polynomial oracle exists). As far as the region beneath that, we are working in the IOP model (containing just the string oracle). Finally, at the very bottom, there is a third model: the plain model (in which we only have the random oracle, and nothing else).

The general pattern is this: whenever we have one of these dividing lines, we split our task into two. First, we can describe a protocol in the higher region, which exploits that region's abstract machine. Then, we need to step downwards, and implement that higher region's abstract machine using only the abstract machine of this region. In each step, we "peel away" one abstract machine, and implement that thing using the more rudimentary stuff within.

In light of the above, we abstract away from this point forward the instantiation of the string oracle, and assume that we have access to it. That is, we conduct our entire cryptography section in the IOP model.