such that

a list of boundary conditions

points

There is a minor issue the above description does not capture: how does the verifier query a committed polynomial f(X) in a point z that does not belong to the domain? In principle, there is an obvious and straightforward solution: the verifier sends z to the prover, and the prover responds by sending y=f(z). The polynomial f(X)−y has a zero in X=z and so must be divisible by X−z. So both prover and verifier have access to a new low degree polynomial, f(X)−yX−z. If the prover was lying about f(z)=y, then he is incapable of proving the low degree of f(X)−yX−z, and so his fraud will be exposed in the course of the FRI protocol. This is in fact the exact mechanism that enforces the boundary constraints; a slightly more involved but similar construction enforces the transition constraints. The new polynomials are the result of dividing out known factors, so they will be called quotients and denoted qi(X).

In other words, the interpolation step reduces the satisfiability of an arithmetic constraint system to a claim about the low degree of certain polynomials

Interpolation in the usual sense means finding a polynomial that passes through a set of data points.

At any point in time, the state of the computation is contained in a tuple of w registers that take values from the finite field F. The machine defines a state transition function f:Fw→Fw that updates the state every cycle. The algebraic execution trace (AET) is the list of all state tuples in chronological order.

In this procedure, the sequence of elementary logical and arithmetical operations on strings of bits is transformed into a sequence of native finite field operations on finite field elements, such that the two represent the same computation.

Especially in the context of zero-knowledge proof systems, the computational integrity claim may need a subtle amendment. In some contexts it is not enough to prove the correctness of a claim, but the prover must additionally prove that he knows the secret additional input, and could as well have outputted the secret directly instead of producing the proof.3 Proof systems that achieve this stronger notion of soundness called knowledge-soundness are called proofs (or arguments) of knowledge.

When the verifier has no access to secret information that is available to the prover, and when the proof system protects the confidentiality of this secret, the proof system satisfies zero-knowledge.

nverse is the correct inverse of the memory value

For the extension columns, InstructionPermutation and MemoryPermutation both start with a random initial value selected by the prover, but since this value needs to remain secret it is enforced instead through a difference constraint across tables.

4 extension columns

That observation is entirely correct.

The verifier, who has cleartext access to the program, evaluates this terminal locally

On the other hand, an evaluation argument (for a sublist relation) establishes that all rows of this Instruction Table correspond to an instruction and its successor at the given location in the program.

clk

to make a permutation argument work for establishing correct memory accesses, it is necessary to keep track of jumps in a cycle counter in the table where the rows are sorted for memory address. To this end, introduce a register clk whose only purpose is to count the number of cycles have passed.

To this end, introduce mv (memory value) and ci (current instruction). If the current instruction is a potential jump, then we also need to know where to jump to. This address is contained in the next instruction, and so a register is needed for that purpose: ni. Also, a potential jump requires some constraints be enforced if mv is nonzero and other constraints be enforced if mv is zero. The only way to enforce constraints conditioned on the zero-ness of some variable, is with an expression that evaluates to the inverse of this variable if it exists and 0 otherwise. Let inv be this register, and so in particular we have that mv * inv is always 0 or 1.

Using two registers ip and mp for instruction pointer and memory pointer like the VM defines makes sense. However, this selection is too limited on its own. The constraints need to depend not just on the index contained in ip and mp, but also on the values these registers point to.

when one table’s list of rows appears in order as a sublist of another table’s list of rows.

The relation that is proved by a permutation argument is actually multiset equality rather than set equality – multiplicity matters.

how does the verifier verify that these tables pertain to the same execution trace? A permutation argument is what establishes that the sets of rows of the two tables are identical

When the memory pointer register mp is reset to a previous value, the memory value register mv changes. Its new value now must be consistent with the value it had the last time the memory pointer pointed to it. This constraint pertains to two rows, but the problem is that these two rows are generally not consecutive and not even spaced apart by a static amount. Transition constraints can only apply to consecutive pairs of rows

in w