Hyper BMMTV Costs

Notation

Throughout this post we assume that use \(m \in \mathbb{N}\) is a power of 2. As the main content of this post is from (Bünz et al., 2019), when describing group operations, we stick with their conventions and use multiplicative notation.

Index Notation: Usually we index the \(i\)’th location of a vector \(\vec{a}\) with \(a_i\). Often, however, owing to the need for multi-indexing or other reasons, we will index vectors with script notation \(a^{(j)}\) instead. We understand this can be confusing, so to ease cognitive load, the reader is asked to remember that

• When there are parentheses around \((i)\) then \(a^{(i)}\) is the \(i\)’th index of a vector \(\vec{a}\).

• When there are NO parentheses around \(i\) then \(a^{i}\) is \(a\) raised to the power of \(i\).

The original manuscript by (Bünz et al., 2019) introduces a lot of non-standard notation. We feel that most of that notation is not needed to accurately describe the protocols. Therefore, in this post, we describe everything using standard notation accepted by the wider mathematics/TCS community, outside of crypto and snarks (at the cost of sometimes being a little bit more verbose). As we do not go into security proofs, we also abandon most of the formalism introduced in the preliminary sections of the original manuscript. We believe this approach simplifies the exposition significantly without compromising rigour or correctness.

Background

To fully make sense of the commitment scheme, we need to understand 4 sub-components

1. The KZG commitment scheme: You can ignore the section on batching, as that’s not critical for understanding inner product arguments.
2. We introduce the “inner product” or “multi-exponentiation” argument, which is the main contribution of (Bünz et al., 2019). Using KZG and the inner product argument, we show how to commit to a bivariate polynomial. This is the new stuff!.
3. Finally, we show how to commit to a univariate polynomial using bi-variate commitment scheme
4. Now that we have a univariate commitment scheme, we can commit to multi-linear polynomials using univariate commitments using the black box reduction of knowledge scheme from (Zhao et al., 2024).

Bi-variate Polynomials

We are given a bi-variate polynomial \(f \in \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}[X, Y]\)

\[ \begin{align} f(X, Y) &= \sum_{i=0}^{m-1} f_i(Y)X^{i} \tag{i} \end{align} \] where for all \(i \in \{0, \ldots, m-1\}\), \(f_i \in \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}[Y]\) is a univariate polynomial with degree at most \(\ell -1\) i.e \(f_i(Y) = f_{(i, 0)}Y^0 + \ldots + f_{(i, \ell-1)}Y^{\ell-1}\) where \(f_{i,j} \in \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\) for all \(j \in \{0, \ldots, \ell-1\}\)

Trusted Setup

Let \(g \in \mathbb{G}_1\) and \(h \in \mathbb{G}_2\) be group generators.

Things that the prover is given

• \(\vec{w} = [w_j]_{j=0}^{\ell-1} = \left[ g^{\alpha^i} \right]_{i=0}^{\ell - 1} \in \mathbb{G}_1^m\), where \(\alpha \xleftarrow[]{\$}\mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\) is toxic waste of the trusted setup.

• \(\vec{u} = \left[u_i\right]^{2m-2}_{i=0} = \left[h^{\beta^{i}}\right]^{2m-2}_{i=0} \in \mathbb{G}_2^{2m-2}\) where \(\beta \xleftarrow[]{\$}\mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\) is also toxic waste of the trusted setup.

Things that the verifier is given: Just the two group elements that will be needed to open KZG proofs using keys in \(\mathbb{G}_1\) and \(\mathbb{G}_2\)

• \(w_1 = g^{\alpha}\)
• \(u_1 = h^{\beta}\)

How To Commit

How To Open

The verifier asks the prover to open \(f\) at points \((z_x, z_y) \in \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\times \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\). As a response the prover

Inner Product Proof

The provers witness is \(\vec{A} = A_0, \ldots, A_{m-1} \in \mathbb{G}_1^m\).

Define \(\vec{b} = (b_0, \ldots, b_{m-1}) = (z_x^0, \ldots, z_x^{m-1})\in \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}^m\). This is common knowledge to the prover and the verifier, as the verifier picks \(z_x \in \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\).

See below for details about \(q\). The cost of this is 1 KZG opening over \(\mathbb{G}_2\) – and the degree of the \(q\) is at most \(2m-2\),

How To Verify An Inner Product Proof

The verifier performs a sequence of checks:

1. Check commitment collapsing: Define \(T^{(0)}, U^{(0)} = (T, U)\) where \(T\) and \(U\) are the original pairing commitment to \(f\) and the KZG commitment to \(f(z_x, Y)\) respectively.

\[ \begin{align} \forall j \in 1, \ldots \ell \qquad & T^{(j)} = C_{L^{j}}^{r_j}T^{(j-1)}C_{R^{j}}^{r_j^{-1}} \\[10pt] & U^{(j)} = C_{L^{j}_1}^{r_j}\cdot U^{(j-1)}\cdot C_{R^{j}_1}^{r_j^{-1}} \end{align} \]

2. Compute the foldings of \(\vec{b}\): If the prover folds all the \(b_i\)’s correctly, then the final check boils down to \[b' = \prod_{i=1}^{\log m}(1 + r_i {b}^{j})\]

3. Check folding for commitment keys

   To check that all commitment keys \(\vec{v}^{(1)}, \ldots, \vec{v}^{(\log m -1)}\) were folded correctly, given \(\vec{v}^{(\log m)}\) the prover asks for a KZG opening proof to evaluate \(q\) at \(z \xleftarrow[]{\$}\mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\), where \(q(x) = \prod_{i=1}^{\log m}(1 + r^{-1}_{(\log m-i+1)}x^{2i})\)

4. Finally check \[T^{(j)} \quad \textcolor{red}{\overset{?}{=}}\quad e(\pi_1.A^{(\log m)}, \pi_1.v^{\log m})\]

and

\[U^{(j)} \quad \textcolor{red}{\overset{?}{=}}\quad \left(\pi_1.A^{(\log m)}\right)^{b^{' }}\]

where \(b'\) was computed in step 2.

How To Commit To A Univariate Polynomial

Now we are given \(f \in \mathbb{F}_{\textcolor{blue}{\mathtt{q}}}[X]\) with degree \(d\). We select \(\ell, m\) of roughly equal size such that \(\ell m =d\).

Just make sure \(m\) is a power of 2.

Let \(f(X) = f_0 + f_1X + \ldots + f_{d}x^d\). Now we chunk the coefficients of \(f\) into a \(m\) sets of size \(\ell\), that is

\(f_i(Y) = \sum_{j=0}^{\ell -1} f_{i\ell + j}Y^j\), and \(p(X,Y) = \sum_{i=0}^{m} f_i(Y)X^{i}\).

This implies that \(p(X^\ell, X) = f(X)\).

See worked out example below

To commit to \(f\) we commit to bivariate polynomial \(p\). To evaluate \(f\) at \(z\) we evaluate \(p\) at \((z^\ell, z)\).

Full Accounting For Prover Costs For Multi-variate Polynomial

To fully understand this accounting please make sure you’ve read this article.

We want to commit to a \(\log d\) variable multi-linear polynomial \(f\). To commit we compute the univariate encoding of \(f\) and we pick \(m\) which is a power of 2 and \(\ell \in \mathbb{N}\) such that \(\ell m = d\). Then we represent \(f\) with the bivariate polynomial \(p^{(0)}\) as described above. Typically \(\ell, m \in O\left(\sqrt{d}\right)\).

Next we discuss the cost of opening a polynomial

The cost of opening \(f\) at \((z_1, \ldots, z_{\log d})\) leads to the prover constructing \(\log d\) univariate polynomials \(p^{(1)}, \ldots, p^{(\log d)}\) with number of coefficients \(d/2, d/4, \ldots, 1\) and committing to these polynomials \(\{C_{p^{(i)}}\}_{i=1}^{\log d}\)

Next the prover will have open the above \(p^{(1)}, \ldots, p^{(\log d)}\) at \(r\) and \(-r\) and open \(p^{(0)}, \ldots, p^{(\log d -1)}\) at \(r^2\).

As the above commitment scheme is also homomorphic, the prover constructs a single polynomial \(B\) using the verifiers challenge \(z_r \xleftarrow[]{\$}\mathbb{F}_{\textcolor{blue}{\mathtt{q}}}\).

\[B(X) = p^{(0)}(X) + z_r p^{(1)}(X) + z_r^2 p^{(2)}(X) + \ldots + (z_r)^{\log d} p^{(\log d)}(X)\]

This is not an issue for the verifier as it can construct a commitment for \(B\) from \(\{C_{p^{(i)}}\}_{i=0}^{\log d}\) (using homomorphism)

\(B\) has \(d\) coefficients, and setting \(m\ell = d\) we once again get \(m, \ell \in O\left(\sqrt{d}\right)\)

So we have to open at 3 locations – where the cost of evaluating one is given by