compute quotient codewords more efficiently

[jan-ferdinand]

Proving correct execution of Triton VM involves computing quotient codewords, whose low-degreeness is then proved using FRI. In order to compute the quotient codewords, we first need the so-called FRI codewords. There are several ways to compute them, all of which are equivalent conceptually, but not computationally. For example, following the red path in the picture below, the AIR constraints can be evaluated on the (symbolic) trace polynomials, resulting in {initial, consistency, transition, terminal} polynomials, which can then be low-degree extended. This is generally very slow.

In Triton VM, we currently follow the gray-into-orange path, i.e., we perform low-degree extension first, and then evaluate the AIR constraints on the FRI trace codewords¹.

The fastest way is indicated by the green path. Here, we introduce a new domain, the arithmetic domain, which is smaller than the FRI domain by a factor of expansion_factor, i.e., 4. After having evaluated the AIR constraints on the trace codewords (over the arithmetic domain), low-degree extension is performed on the {initial, consistency, transition, terminal} codewords, resulting in the sought-after FRI codewords. Following the green path instead of the orange path is (projected to be) a speedup with factor 4.

As far as I know, all credit for the idea goes to @aszepieniec.

Footnotes

1. This name is not used anywhere yet – up until now, we did not need to distinguish between trace codewords over the arithmetic domain and over the FRI domain. ↩