(updated )

WHIR Multilinear Polynomial Commitments.

\gdef\delim#1#2#3{\mathopen{}\mathclose{\left#1 #2 \right#3}} \gdef\p#1{\delim({#1})} \gdef\ps#1{\delim\{{#1}\}} \gdef\F{\mathbb F} \gdef\vec#1{\mathbf{#1}} \gdef\mat#1{\mathrm{#1}} \gdef\eq{\operatorname{eq}} \gdef\∀{\mathop{\huge ∀}\limits}

WHIR combines the ideas from STIR with those from Basefold to achieve a very performant polynomial commitment scheme for multilinear polynomials.

\Sigma-IOPs

Given a multilinear polynomial f ∈ \F[\vec X] commited to by the prover and a weight polynomial w \in \F[Z, \vec X] known to the prover and verifier, WHIR allows the verifier to check the following sum:

\begin{align} \sum_{\vec b \in \ps{0,1}^m} w\p{f(\vec b), \vec b} = σ \end{align}

This includes multivariate evaluation f(\vec r) = h by setting weights w(z, \vec x) = z ⋅ \eq(\vec x, \vec r), which in turn contains univariate evaluation as a special case by evaluating f(\bar x) using the map

\begin{aligned} \bar x : \F &\rightarrow \F^m \\ x &\mapsto (x, x^2, x^4, x^8, …, x^{2^{m - 1}})\text{.} \end{aligned}

If we have multiple such claims w_i, σ_i they can be batched together using a random challenge \gamma as

\begin{aligned} w(z, \vec x) = \sum_i γ^i ⋅ w_i\p{z, \vec x} && σ = \sum_i γ^i ⋅ σ_i\text{.} \end{aligned}

Commitment

To commit f it is Reed-Solomon encoded, i.e. evaluated over a foldable domain \mathcal{L} with rate \rho = \frac{2^m}{|\mathcal{L}|} < 1. These values are commited in a Merkle tree. Denote with \mathcal{L}^{(2^k)} the k-folded domain.

To boost soundness, the verifier can provide random challenges z_i \in \F where the prover responds with f(\bar z_i). These evaluations are then included in the initial weight polynomial in an opening.

Opening

Given a commitment to f, the prover can proof a claim of the form (1) using the protocol:

  1. While m is large:
    1. Prover and verifier run k rounds of sumcheck to reduce (1) to a claim of the form \sum_{\vec b \in \ps{0,1}^{m-k}} w\p{f(\vec r, \vec b), \vec r, \vec b} = h where \vec r \in \F^k is a random vector.
    2. Prover commits to f'(\vec x) = f(\vec r, \vec x) on \mathcal{L}^{(2)}. Note that this reduces the rate by 2^{k-1}.
    3. Verifier send a random challenge z_0 \in \F.
    4. Prover sends the evaluation y_0 = f'(\bar z_0).
    5. For i \in [1,t]
      1. Verifier sends a random challenge z_i \in \mathcal{L}^{(2^k)}.
      2. Verifier and prover evaluate y_i=f'(\bar z_i) by querying f.
    6. Prover and verifier do n bits of proof-of-work.
    7. Prover and verifier repeat with the updated claim with m' = m - k \sum_{\vec b \in \ps{0,1}^{m'}} w'\p{f'(\vec b), \vec b} = h + \sum_{i \in [t]} \gamma^{i+1} ⋅ y_i where the weight polynomial is updated as w'\p{z, \vec x} = w\p{z, \vec r, \vec x} + z ⋅ \sum_{i \in [t]} \gamma^{i + 1} ⋅ \eq(\bar z_i, \vec x)\text{.}
  2. Prover sends f (now small) in full.
  3. Prover and verifier run sumcheck to reduce (1) to a claim of the form w\p{f(\vec r), \vec r} = h for random \vec r \in \F^m.
  4. Verifier checks the claim by evaluating z=f(\vec r) and w(z, \vec r).

For evaluation proofs the final w contains only a small number of \eq terms and can be efficiently computed by the verifier. If w is more complex (as is the case for GR1CS below) the prover can provide a proof of evaluation of w(z, \vec r).

GR1CS

A generalized R1CS relation for a vector \vec z = (\vec z_{\text{public}}, \vec z_{\text{private}}) is a collection of constraints of the form

L_i\p{\mat M_{i0}⋅\vec z, \mat M_{i1}⋅\vec z, …, \mat M_{in}⋅\vec z} = \vec 0

where L_i is a multivariate polynomial evaluated element-wise over the input vectors and \mat M_{ij} are matrices. For example an R1CS instance has a single constraint L(a,b,c) = a ⋅ b - c with three corresponding matrices.

Take f to be the MLE of \vec z such that f(0, ⋯) is the MLE of \vec z_{\text{public}} and f(1, ⋯) is the MLE of \vec z_{\text{private}} and take M(\vec x, \vec y) to be the MLE of \mat M. Define f_{ij} to be

f_{ij}(\vec x) = \sum_{\vec y \in \ps{0,1}^m} M_{ij}(\vec x, \vec y) ⋅ f(\vec y)\text{.}

Observe that f_{ij} is a quadratic polynomial that evaluates to the vector \mat M_{ij}⋅\vec z on \ps{0,1}^m.

  1. Prover sends f(0, ⋯) in full and a commitment to f(1, ⋯).
  2. Verifier sends a random challenge \gamma \in \F.
  3. Prover and verifier run zero-check on the claim \∀_{\vec x \in \ps{0,1}^m} \quad \sum_i \gamma^i ⋅ L_i\p{…, f_{ij}(\vec x), …} = 0 to reduce it to \begin{align} \sum_i \gamma^i ⋅ L_i\p{…,f_{ij}(\vec r_1), …} ⋅\eq(\vec r_1, \vec r_2) = h \end{align}
  4. Prover and verifier use WHIR to provide values for \sum_{\vec b \in \ps{0,1}^{m-1}} M_{ij}(\vec r_1, 1, \vec b) ⋅ f(1, \vec b) by providing values computing the weighted sums w_{ij}(z, \vec x) = z ⋅ M_{ij}(\vec r_1, 1, \vec x)
  5. Verifier computes values f_{ij}(\vec r_1) and checks (2).

References

Remco Bloemen
Math & Engineering
https://2π.com