The Evaluation Argument establishes that two lists and are identical. To achieve this, the lists' elements are interpreted as the coefficients of polynomials and , respectively:
The two lists and are identical 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 Evaluation Argument is generally used to show that (parts of) some row appear in two tables in the same order. 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 evaluation of and in the respective tables' extension column.
For example, in both Table A and B:
|base column||extension column: running evaluation|
It is possible to establish a subset relation by skipping over certain elements when computing the running evaluation. The running evaluation must incorporate the same elements in both tables. Otherwise, the Evaluation 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 .