Triton is a virtual machine that comes with Algebraic Execution Tables (AET) and Arithmetic Intermediate Representations (AIR) for use in combination with a STARK proof system.
Here is a potential space and speed improvement: do not store the randomized trace polynomials but store the unrandomized trace polynomials instead.
For starters, this gives faster interpolation. The domain size is half.
To randomize the polynomial in monomial-coefficient form, select a vector of k uniformly random field elements, and add this vector to the vector of coefficients in slices [0:k] and [N:N+k]. This corresponds to adding a multiple of $X^N+1$ where the cofactor consists of k uniformly random coefficients. By construction, this term disappears on the trace domain (whose length is N.)
The next step is to not even bother storing the k randomizer coefficients for every column -- instead, derive them pseudorandomly from a random seed and the column index. You only need the full polynomial when low-degree extending; afterwards the k randomizer coefficients can be thrown away again to save space.
Here is a potential space and speed improvement: do not store the randomized trace polynomials but store the unrandomized trace polynomials instead.
For starters, this gives faster interpolation. The domain size is half.
To randomize the polynomial in monomial-coefficient form, select a vector of
kuniformly random field elements, and add this vector to the vector of coefficients in slices[0:k]and[N:N+k]. This corresponds to adding a multiple of $X^N+1$ where the cofactor consists ofkuniformly random coefficients. By construction, this term disappears on the trace domain (whose length isN.)The next step is to not even bother storing the
krandomizer coefficients for every column -- instead, derive them pseudorandomly from a random seed and the column index. You only need the full polynomial when low-degree extending; afterwards thekrandomizer coefficients can be thrown away again to save space.