Commit To Multilinear Polynomials Using A Univariate Commitment Scheme As A Black Box
Pre-requisites: We assume the reader is familiar with the basics of polynomial commitment schemes, or at least knows how the KZG algorithm works.
How To Commit
We are given a multilinear polynomial \(f \in \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}[X_1, \ldots, X_\ell]\). To commit to \(f\), we encode \(f\) as a univariate polynomial \(p^{(0)}\) using \(2^\ell\) evaluations of \(f\) over the boolean hypercube \(\{ 0, 1\}^\ell\) as coefficients. Then we commit to the univariate polynomial encoding of \(f\) using any univariate polynomial commitment scheme (such as KZG).
The univariate encoding \(p^{(0)}\) of \(f\) is given by \[ \begin{align} p^{(0)}(X) &= p_0^{(0)} + p_1^{(0)}X + \ldots, + p_{2^\ell-1}^{(0)}X^{2^\ell-1}\\ &= f(\langle 0 \rangle_{2}) + \ldots + f(\langle 2^\ell-1 \rangle_{2})X^{2^\ell-1} \end{align} \]
where for any \(x\in \{0, \ldots, 2^\ell-1\}\), let \(\langle x \rangle_{2}\) be the representation of \(x\) in binary.
Example
Supposed we are given the following multi-linear polynomial \[ \begin{align} f(x_1, x_2) &= a(1-x_1)(1-x_2) + bx_1(1-x_2) \\&\qquad+ c(1-x_1)x_2 + d x_1 x_2 \end{align} \]
The univariate encoding of \(f\) \[ \begin{align} p^{(0)}(x) &= f(0, 0) + f(1,0)x + f(0, 1)x^2 + f(1,1)x^3\\ &=a + bx + cx^2 + dx^3 \end{align} \]
Let \(C_{p^{(0)}}\) denote the commitment to \(p^{(0)}\).
Prover \(\rightarrow\) Verifier: Prover sends commitment \(C_{p}\)
Attention: That we use the KZG commitment is NOT so important. The idea was introduced using KZG commitments in Section 6 of (Zhao et al., 2024). they use the KZG commitment scheme., but we will soon see, that there’s nothing special about KZG for this procedure. We can use any univariate commitment scheme, and things will work out. The optimisations really come from homomorphism, which KZG of course satisfies.
How To Open
Prover \(\leftarrow\) Verifier: Verifier wants to open at \(\vec{z}\)
Now the verifier wants to open at some point \(\vec{z} = (z_1, \ldots, z_\ell) \in \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}^{\ell}\). The prover claims that \(f(\vec{z}) = y\) and constructs the following proof:
Let \(p^{(0)}\) denote the univariate encoding of \(f\). Now for all \(j \in \{1, \ell \}\) we define \(\ell\) univariate polynomials: \[ \begin{align} p^{(\textcolor{blue}{j})}(X) = \sum_{\textcolor{seagreen}{i}=0}^{2^{(\ell-\textcolor{blue}{j})}-1} \Big((1-z_{\textcolor{blue}{j}})p_{2\textcolor{seagreen}{i}}^{(\textcolor{blue}{j}-1)} + z_{\textcolor{blue}{j}}p_{2\textcolor{seagreen}{i}+1}^{(\textcolor{blue}{j}-1)}\Big)X^{\textcolor{seagreen}{i}} \end{align} \]
As a proof the prover commits to all the above polynomials as \(\pi = \left(C_{p}, C_{p^{(1)}}, C_{p^{(2)}}\ldots, C_{p^{(\ell)}}\right)\) as the proof.
What Are These Polynomials?
Notice that each \(p^{(j)}\) corresponds to partially evaluating \(f\) at location \((z_1, \ldots z_j, x_{j+1}, \ldots, x_\ell)\), and encoding it as a univariate polynomial.
This is best illustrated with a toy example:
Suppose \[\begin{align} f(x_1, x_2) &= a (1 - x_1)(1 - x_2) \\[5pt] &\quad + b x_1 (1 - x_2) \\[5pt] &\quad + c (1 - x_1) x_2 \\[5pt] &\quad + d x_1 x_2 \end{align}\] Using the above formula, we have
\[
\begin{align}
p^{(1)}(X) &= ((1-z_1)p^{(0)}_0 + z_1p^{(0)}_1)
\\[10pt]&\qquad\qquad+ ((1-z_1)p^{(0)}_2 + z_1p^{(0)}_3)X\\[10pt]
&= (1-z_1)f(0,0) + z_1f(0,1) +
\\[10pt]&\qquad\qquad(1-z_1)f(1,0)X + z_1f(1,1)X \\[10pt]
&= (1-z_1)a + z_1b + X\Big(z_1c + (1-z_1)d\Big) \\[10pt]
&= p_0^{(1)} + p^{(1)}_1X
\end{align}
\]
We claim that \(p^{(1)}(X)\) is a
univariate encoding of \(f(z_1, x_2, \ldots,
x_\ell)\). So expressing \(f(z_1,
X_2)\) in standard multi-linear form with \(X_1 = z_1\) and \(X_2\) free we get
\[ f(z_1, X_2) = p_0^{(1)}(1-X_2) + p_1^{(1)}X_2 \] which is exactly the partial evaluation of \(f\) at \(z_1\) is given by \[ \begin{align} f(z_1, X_1) &= a(1-z_1)(1-X_2) + bz_1(1-X_2) \\&\quad+ c(1-z_1)X_2 + d z_1 X_2 \end{align} \] Continuing this with one more level of folding to pin \(X_2 = z_2\).
\[ \begin{align} p^{(2)}(X) &= (1 - z_2) p_0^{(1)} + z_2 p_1^{(1)} \\ &= a (1 - z_1)(1 - z_2) \\ &\quad + b z_1 (1 - z_2) \\ &\quad + c (1 - z_1) z_2 \\ &\quad + d z_1 z_2 \\ &= f(z_1, z_2) \end{align} \]
Prover \(\rightarrow\) Verifier: Prover sends evaluation \(y\) and proof \(\pi\)
On receiving these commitments the verifier sends the prover a challenge \(r \xleftarrow[]{\$}\mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\)
Prover \(\leftarrow\) Verifier: \(r \xleftarrow[]{\$}\mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\)
The prover computes for all \(i \in \{1 \ldots, \ell\}\) 3 univariate polynomial evaluations.
\[ \begin{align} y^{(i)} = p^{(i)}(r^2) \\ y^{(i-1)}_{\text{neg}} = p^{(i-1)}(-r) \\ y^{(i-1)}_{\text{pos}} = p^{(i-1)}(r) \\ \end{align} \]
Prover \(\rightarrow\) Verifier: \(\left\{y^{(i)}\right\}_{i=1}^{\ell}, \left\{y^{(i)}_{\text{neg}}, y^{(i)}_{\text{pos}}\right\}_{i=0}^{\ell-1},\)
Communication is \(3\ell\) \(\mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\) elements.
Verifier Test 1
For all \(i \in \{ 1, \ldots, \ell\}\), the verifier checks
\[ \begin{align} y^{(i)} &\textcolor{red}{\overset{?}{=}}(1-z_i)\frac{y^{i-1}_{\text{pos}}+y^{i-1}_{\text{neg}}}{2} + z_i\frac{y^{i-1}_{\text{pos}}-y^{i-1}_{\text{neg}}}{2r} \end{align} \] Finally the verifier checks \(y^{(\ell)} \textcolor{red}{\overset{?}{=}}y\)
Where did we get these equations
What the verifier really wants to do is confirm that the prover started with some multi-variate polynomial \(f^*\), and then constructed the encodings consistently as specified. If it does so, then the last evaluation will be the evaluation of \(f^*\) at \(\vec{z}\).
Define univariate polynomial \(q\)
\[ \begin{align} q(X) = p^{(j-1)}(X) = \sum_{i=0}^{2^{l-j+1}-1} q_ix^{i} \end{align} \]
Observe that
\[ \begin{align} q(x) &= q_{\text{even}}(X^2) + Xq_{\text{odd}}(X^2) \end{align} \]
where \[ \begin{align} q_{\text{even}}(X) &= \sum_{i=0}^{2^{\ell-j}-1}q_{2i}X^{i} \\ q_{\text{odd}}(X) &= \sum_{i=0}^{2^{\ell-j}-1}q_{2i+1}X^{i} \\ \end{align} \]
Now \[ \begin{align} q(r) &= q_{\text{even}}(r^2) + rq_{\text{even}}(r^2) \\ q(-r) &= q_{\text{even}}(r^2) - rq_{\text{even}}(r^2) \\ \end{align} \]
Solving the above system of equations
\[q_{\text{even}}(r^2) = \frac{q(r) + q(-r)}{2}\]
\[q_{\text{odd}}(r^2) = \frac{q(r) - q(-r)}{2r}\]
Now from how we defined \(p^{(j)}\) we have
\[ \begin{align}&p^{(j)}(r^2) \\[10pt] &= (1-z_j)\sum_{i=0}^{2^{\ell-j}-1} p_{2i}^{(j-1)}(r^2)^i +\quad z_j\sum_{i=0}^{2^{\ell-j}-1}p_{2i+1}^{(j-1)}(r^2)^i \\[10pt] &= (1-z_j)q_{\text{even}}(r^2) + \quad z_jq_{\text{odd}}(r^2) \\[10pt] &= (1-z_j)\left(\frac{q(r) + q(-r)}{2}\right) + \quad z_j\left(\frac{q(r) - q(-r)}{2r}\right)\\[10pt] &= (1-z_j)\left(\frac{y^{(j-1)}_{\text{pos}} + y^{(j-1)}_{\text{neg}}}{2}\right) + \quad z_j\left(\frac{y^{(j-1)}_{\text{pos}} - y^{(j-1)}_{\text{neg}}}{2r}\right) \end{align} \]
This is exactly the test the verifier checks.
So what the above test really does, is ensure that the prover constructed the univariate polynomials as instructed. If they did, then the univariate polynomials would end up being encodings to partial openings.
Finally, this ensures that \(f'(z_1, \ldots, z_l) = y^{\ell}\)
NOTE: This check does not use the commitments at all. Thus, all we get from there is some multi-linear polynomial and the provers evaluations are consistent with the folding evaluation described above. Whether these evaluations are consistent with the commitments comes from step 2.
Verifier Test 2
We have \(\ell + 1\) commitments \(C_{p^{0}}, \ldots, C_{p^{(\ell)}}\) and for each polynomial we have \(3\ell\) evaluations
\(p^{(1)}(r^2), \ldots, p^{(\ell)}(r^2)\)
\(p^{(0)}(r), \ldots, p^{(\ell-1)}(r)\)
\(p^{(0)}(-r), \ldots, p^{(\ell-1)}(-r)\)
If the commitment scheme is homomorphic, we can do construct a single commitment from these. The verifier samples \(q \xleftarrow[]{\$}\mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\), and sends this to the prover.
The verifier then calculates \(C_{B} = \sum_{i=0}^{\ell} \left(C_{p^{(i)}}\right)^{q^{i}}\), Then the verifier hands over \(q\) to the prover.
Verifier \(\rightarrow\) Prover: \(q \xleftarrow[]{\$}\mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\)
The prover computes
\[B(X) = \sum_{i=0}^{\ell} q^{i}\cdot p^{(i)}(X)\]
So now we have 1 polynomial \(B\), it’s commitment \(C_{B}\) and 3 evaluation points \(r, -r, r^2\). We get 3 evaluations proofs for each evaluation.
NOTE: So far we have used the univariate polynomial commitment scheme as a blackbox. Below we mention some advantages of using KZG.
KZG Specific Optimisations
We could have used KZG’s batching to make this a single proof, but the original authors choose not to. As the number is only 3, it’s not a big computational advantage.
KZG Specific Optimisations
A second optimisation is that although we get 3 proofs, each KZG proof consists of a check of the form \(e(L, R)= e(L', R')\). We can batch them together and do one single equality check.