Skip to main content

​
From Spreadsheet to Trace Polynomials

Figure 1: Prover workflow: Trace polynomials In the previous section, we created a table (aka spreadsheet). In this section, we will convert the table into something called trace polynomials. Figure 2: From spreadsheet to trace polynomials In STARKs, the computation trace is represented as evaluations of a polynomial over some domain. Typically this domain is a coset of a multiplicative subgroup. But since the multiplicative subgroup of M31 is not smooth, S-two works over the circle group which is the subgroup of degree-2 extension of M31 (as explained in the Mersenne Primes and Circle Group sections). Thus the domain in S-two is formed of points (xi,yi)(x_i, y_i) on the circle curve. Note that when we interpolate a polynomial over the points on the circle curve, we get a bivariate trace polynomial fj(x,y)f_j(x, y). We will explain why using a polynomial representation is useful in the next section, but for now, let’s see how we can create trace polynomials for our code. Note that we are building upon the code from the previous section, so there’s not much new code here. 
fn main() {
    // --snip--

    // Convert table to trace polynomials
    let domain = CanonicCoset::new(log_num_rows).circle_domain();
    let _trace: ColumnVec<CircleEvaluation<SimdBackend, M31, BitReversedOrder>> =
        vec![col_1, col_2]
            .into_iter()
            .map(|col| CircleEvaluation::new(domain, col))
            .collect();
}
Here, domain refers to the (xi,yi)(x_i, y_i) values used to interpolate the trace polynomials. For example, (x1,y1),(x2,y2)(x_1, y_1), (x_2, y_2) in Figure 2 are the domain values for our example. Note that when creating the domain, we set the log_num_rows to the log of the actual number of rows that are used in the table. In our example, we set it to 4 since S-two requires that we use at least 16 rows. For a background on what CanonicCoset and .circle_domain() mean, you can refer to the Circle Group section. Now that we have created 2 trace polynomials for our 2 columns, let’s move on to the next section where we commit to those polynomials!