sumcheck evaluation point set

[kunxian-xia]

We currently use the point set P = {0, 1, 2, ..., d} for proving sumcheck with max degree d.

• tower sumcheck for logup spec
  The sumcheck expression is \sum_b eq(r,b) * (n[b,0] * d[b, 1] + n[b,1]*d[b,0]). The max degree is 3.

  We can borrow an optimization idea in sp1 hypercube to interpolate the univariate polynomials via another point set P' = {0, 1, 1/2, s}.

• tower sumcheck for product spec: the sumcheck expression is \sum_b eq(r,b) * p[b,0] * p[b,1].

[kunxian-xia]

To evaluate virtual polynomial f = eq * (n0 * d1 + n1 * d0) at 1/2, we just need to do 6 additions and 3 multiplications. That is, f(1/2) = 1/8 * \sum_b (eq[b,0] + eq[b,1]) * ((n0[b,0] + n0[b,1]) * (d1[b,0] + d1[b,1]) + (n1[b,0] + n1[b,1]) * (d0[b,0] + d1[b,1])).

As a comparison, to get f(2), the prover needs to compute eq[b,2], n0[b,2], n1[b,2], d0[b,2], d1[b,2] and each one requires 1 multiplication (by 2) and 1 addition. This gives us 6 additions and 8 multiplications.