Evaluation Argument

The Evaluation Argument establishes that two lists $A = (a_{0}, \dots, a_{n})$ and $B = (b_{0}, \dots, b_{n})$ are identical. To achieve this, the lists' elements are interpreted as the coefficients of polynomials $f_{A} (X)$ and $f_{B} (X)$ , respectively:

$f_{A} (X) f_{B} (X) = X^{n + 1} + i = 0 \sum n a_{n - i} X^{i} = X^{n + 1} + i = 0 \sum n b_{n - i} X^{i}$

The two lists $A$ and $B$ are identical 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 $α$ establishes the polynomial identity with high probability.¹

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,²
samples a random challenge $α$ through the Fiat-Shamir heuristic,
computes the running evaluation of $f_{A} (α)$ and $f_{B} (α)$ in the respective tables' extension column.

For example, in both Table A and B:

base column	extension column: running evaluation
0	$α^{1} + 0 α^{0}$
1	$α^{2} + 0 α^{1} + 1 α^{0}$
2	$α^{3} + 0 α^{2} + 1 α^{1} + 2 α^{0}$
3	$α^{4} + 0 α^{3} + 1 α^{2} + 2 α^{1} + 3 α^{0}$

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.

Examples for subset Evaluation Arguments can be found between the Hash Table and the Processor Table.

This depends on the length $n$ of the lists $A$ and $B$ as well as the field size. For Triton VM, $n < 2^{32}$ . The polynomials $f_{A} (X)$ and $f_{B} (X)$ are evaluated over the extension field with $p^{3} \approx 2^{192}$ elements. The false positive rate is therefore $n /∣ F_{p^{3}} ∣ ⩽ 2^{- 160}$ .

See “Compressing Multiple Elements.”