background We have a computation from [S F] -> P. The first step is to unroll it. We build a table, which we also call the trace, where each column is basically a register and each row is one step of the processor. The first row contains the input and the final row contains the product. So how can the verifier know that this table is correct, and that P is really the product of .*(S F)? First idea- the prover can send the entire table to the verifier and the verifier can check every row. This works but its equivalent to the verifier just running the computation himself. Next idea- the verifier can randomly check rows to see if they are correct. This fails because computation is inherently fragile- the prover could change a single row to be wrong and the final product will be wrong. But the verifier will only catch this if he happens to check that exact row. What we do instead is we encode the trace as polynomials and turn the problem of 'is this computation correct' into a problem of 'is this polynomial zero over a certain set'. Polynomials are rigid and this can be done succinctly. How does this work?

Polynomial composition ideas A major bottleneck in the prover is composing the univariate trace polynomials into the multivariate constraint polynomials to produce one univariate polynomial. Let's think about what it's doing. The multivariate constraints are a bunch of terms which each look like this: $cx_1x_2*...*x_n$ where $c \in \mathbb{F}_p$ and $x_i \in \mathbb{F}_p[X]$ and the $x_n$'s can be repeated.. The max degree of our constraints is 4 so there are at most 4 variables in each term. So for each term we have to multiply max 4 polynomials together and then multiply the result by a single field element.