1. WHIR lets us commit to a polynomial $f$ and then verify a claim of the form

$$ \sum_{b \in \{0, 1\}^n}w(f(b), b) = 0 $$

For this to work, the verifier has to be able to efficiently evaluate $w$ at a random point.

NB: This is not implemented in the WHIR codebase, Remco has some draft that he’d happily throw over the fence.

1. R1CS: take any matrices A, B and C, and a witness vector w. The instance is accepted if

$$ Aw \odot Bw - Cw = 0 $$

Where $\odot$ is the pointwise product.

1. GR1CS: a single constraint is any set of matrices $A_1, \ldots , A_n$, plus a polynomial $L \in F[X_1,\ldots,X_n]$ and it is satisfied by $w$ iff $L(A_1w, \ldots,A_nw) = 0$ in the $(\odot, +)$ algebra. GR1CS allows multiple such constraints, but:

   1. we are mostly interested in just using R1CS, where $L(A, B, C) = AB - C$ is the only constraint
   2. multiple constraints are dealt with by taking a random linear combination, so they disappear quite early in the protocol.

   so from now on we’re just assuming a single constraint to save on some index-fu.

2. The protocol is:

   1. Set up the following ML polys: $f_w$ interpolates the private witness, $f_v$ interpolates the public inputs, $f$ such that $f(0, X) = f_v(X)$ and $f(1,X)=f_w(X)$, $\alpha_i (X,Y)$ interpolates $A_i$ and a

      $$ g(X) = L(\sum_b \alpha_1(X, b)f(b), \ldots, \sum_b\alpha_n(X,b)f(b)) $$

      i.e. $g(X)$ interpolates the value of the constraint on row $X$. Note that $g$ is not multilinear, but instead its degree in each variable is bounded by the total degree of $L$ (two in the case of R1CS).

   2. The prover WHIR-commits to $f_w$

   3. We now run a standard zerocheck on $g$, that is the verifier chooses some $r$ and we run sumcheck on $\sum_b g(b)eq(b, r)$

   4. In the final step of that sumcheck we have to evaluate $g(r')eq(r', r)$ which is the same as

   $$ L(\sum_b\alpha_1(r',b)f(b),\ldots,\sum\alpha_n(r',b)f(b)) $$

   Each of the argument sums can be rewritten as

   $$ \sum_b \alpha_i(r',b)f(b) = \sum_b \alpha_i(r',0,b)f_v(b) + \sum_b\alpha_i(r',1,b)f_w(b) $$

   The first term can be computed directly by the verifier and the second is exactly the right shape for a WHIR opening proof. So we do a WHIR opening for each of these and then compute the value of $L$.

   1. Can we get rid of the additional variable introduced in the private/public split? This would halve the size of $f$ and the constraint matrices. Idea:

      1. Redefine $f$ as the interpolation of the entire witness concatenated naively and redefine $f_w$ as $f -f_v$
      2. The protocol proceeds normally until the last step when we have to evaluate $\sum_b \alpha_i(r',b)f_v(b) + \sum_b\alpha_i(r',b)f_w(b)$ (note the lack of the additional 0/1 indices). Now in the second term we have to somehow ensure that $f_w$ is zero on public inputs to get rid of public input maleability. Verifier could sample some randomness $\beta_i$ for each public input and make the prover evaluate

      $$ \sum_b(\alpha_i(r', b) + \sum_{i\in pub}\beta_ieq(b, i))f_w(b) $$

      This way, if $f_w$ is zero on public inputs, the sum is unchanged. Otherwise it will drift away by an unpredictable factor and break the final verification.