Permutation Argument

The Permutation Argument establishes that two lists $A=(a_0,\dots ,a_n)$ and $B=(b_0,\dots ,b_n)$ are permutations of each other. To achieve this, the lists' elements are interpreted as the roots of polynomials $f_A(X)$ and $f_B(X)$, respectively:

$$\begin{array}{rl}{f}_A(X)& =\prod _{i=0}^{n}X-a_i\\ f_B(X)& =\prod _{i=0}^{n}X-b_i\end{array}$$

The two lists $A$ and $B$ are a permutation of each other if and only if the two polynomials $f_A(X)$ and $f_B(X)$ are identical. By the Schwartz–Zippel lemma, probing the polynomials in a single point $\alpha$ establishes the polynomial identity with high probability.¹

In Triton VM, the Permutation Argument is generally applied to show that the rows of one table appear in some other table without enforcing the rows' order in relation to each other. To establish this, the prover

• commits to the base column in question,²
• samples a random challenge $\alpha$ through the Fiat-Shamir heuristic,
• computes the running product of $f_A(\alpha )$ and $f_B(\alpha )$ in the respective tables' extension column.

For example, in Table A:

And in Table B:

It is possible to establish a subset relation by skipping over certain elements when computing the running product. The running product must incorporate the same elements in both tables. Otherwise, the Permutation Argument will fail.

An example of a subset Permutation Argument can be found between the U32 Table and the Processor Table.