The Permutation Argument establishes that two lists and are permutations of each other. To achieve this, the lists' elements are interpreted as the roots of polynomials and , respectively:
The two lists and are a permutation of each other if and only if the two polynomials and are identical. By the Schwartz–Zippel lemma, probing the polynomials in a single point establishes the polynomial identity with high probability.1
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,2
- samples a random challenge through the Fiat-Shamir heuristic,
- computes the running product of and in the respective tables' extension column.
For example, in Table A:
|base column A||extension column A: running product|
And in Table B:
|base column B||extension column B: running product|
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.
This depends on the length of the lists and as well as the field size. For Triton VM, . The polynomials and are evaluated over the extension field with elements. The false positive rate is therefore .