- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
We implement a Zero-Knowledge Sumcheck protocol for relations of a very general form.
The implementation consists of several components.
Given multilinear polynomials \( P_1,\ldots, P_N \in \mathbb{F}[X_0,\ldots, X_{d-1}] \) and a polynomial \( F \) in \( N \) variables, we run Sumcheck over the polynomial
\begin{align} \tilde{F} (X_0,\ldots, X_{d-1}) = pow_{\beta}(X_0,\ldots, X_{d-1}) \cdot F\left( P_1 (X_0,\ldots, X_{d-1}), \ldots, P_N (X_0,\ldots, X_{d-1}) \right) \end{align}
to establish that \( F(P_1(\vec \ell),\ldots, P_N(\vec \ell) ) = 0 \), i.e. that \( F \) is satisfied at every point \(\vec \ell \{0,1\}^d\).
In the implementation, the relation polynomial \( F \) is specified by the Flavor.
The following constants are used in this exposition.
| Notation | \( \sim \) Upper Bound | |
|---|---|---|
| \( d \) | number of variables in multilinear polynomials \( P_1,\ldots, P_N\) | \( 20 \) |
| \( N \) | number of Prover Polynomials specified by Flavor's parameter NUM_ALL_ENTITIES | \( 60 \) |
| \( N_w \) | number of Witness Polynomials specified by Flavor's parameter NUM_WITNESS_ENTITIES | \( 17 \) |
| \( n \) | size of the hypercube, i.e. \( 2^d\). | \( 2^{20} \) |
| \( D \) | total degree of \(\tilde{F}\) as a polynomial in \(P_1,\ldots, P_N\) incremented by 1 | \( 12 \) |
| \( D_w\) | maximum witness degree of \( F \) | \( 5 \) |
The significance of this parameter becomes apparent in Section Masking Evaluations of Multilinear Witnesses. It is formally defined as follows
\begin{align} D_w = \deg_{P_1, \ldots, P_{N_w}} F(P_1,\ldots, P_{N}) \end{align}
where by \( \deg_{P_1, \ldots, P_{N_w}} \) we mean the total degree of the relation polynomial \( F \) in the witness polynomials \( P_1,\ldots, P_{N_w}\) considered as variables.
For example, given a polynomial \(P_1 + P_{N_w+1} \cdot P_{N_w + 2} \cdot P_{1}^2 \cdot P_{2}\) in prover polynomials, where \(N_w>2\), its witness degree \( D_w \) is \(3\), whereas its total degree \(D\) is equal to \( 6 \).
We remark that prior to running Sumcheck, the prover commits to multilinear polynomials \(P_1,\ldots, P_{N_w}\), and sends the commitments to the verifier and that the total sum and the relation polynomial \( \tilde F \) are public.
The prover algorithm is implemented in the Sumcheck Prover class. See its documentation for a more detailed description of methods described below. The Sumcheck Round routine is abstracted into Sumcheck Prover Round class, which contains most computational steps.
The polynomials \(P_1,\ldots, P_N\) are abstracted in the class ProverPolynomials specific to a Flavor, e.g. Mega Flavor. Sumcheck Prover algorithm takes a reference to an object of this class.
The prover evaluates the round univariate
\begin{align} \tilde{S}^i = \sum_{\vec \ell \in \{0,1\}^{d-1-i}} \tilde{F}\left(P_1(u_0,\ldots, u_{i-1}, X_i,\vec \ell), \ldots, P_N(u_0,\ldots, u_{i-1}, X_i,\vec \ell)\right) \end{align}
over the domain \( 0,\ldots, D \). In fact, it is more efficient to perform this computation sub-relation-wise, because the degrees of individual subrelations as polynomials in \( P_1,\ldots, P_N\) are generally smaller than \(D\) defined in Main Parameters. Taking this into account, for a given subrelation of \(F\), we perform expensive subrelation evaluations at points \((u_0,\ldots, u_{i-1}, k, \vec \ell)\) for \(\ell \in \{0,1\}^{d-1-i} \) and \(k\) from \(0\) only up to the degree of the subrelation as a polynomial in \(P_1,\ldots,P_N\) incremented by \(1\).
At the implementation level, the evaluations of \(\tilde{S}^i\) are obtained using the method compute univariate consisting of the following sub-methods:
After computing Round Univariate and adding its evaluations \(\tilde{S}^i(0),\ldots, \tilde{S}^i(D)\) to the transcript, the prover generates Round Challenge \( u_i \) by hashing the transcript.
To keep prover's work linear in the number of coefficients of \(P_1,\ldots, P_N\), we populate a table of \(\texttt{partially_evaluated_polynomials}\) after getting the first challenge \( u_0 \) with the values \(P_j(u_0,\vec \ell )\), namely
\begin{align} \texttt{partially_evaluated_polynomials}_{\ell,j} \gets P_j(0, \ell) + u_{0} \cdot \left(P_j(1, \vec \ell) - P_j(0, \ell)\right) \end{align}
for \( \vec \ell \in \{0,1\}^{d-1}\) identified with the binary representation of \( 0\leq \ell \leq 2^{d-1}-1\).
In Round \(0< i \leq d-1\), the prover algorithm updates the top \( 2^{d-1 - i}\) values in the book-keeping table
\begin{align} \texttt{partially_evaluated_polynomials}_{\ell,j} \gets \texttt{partially_evaluated_polynomials}_{2 \ell,j} + u_{i} \cdot (\texttt{partially_evaluated_polynomials}_{2\ell+1,j} - \texttt{partially_evaluated_polynomials}_{2\ell,j}) \end{align}
where \(\vec \ell \in \{0,1\}^{d-1-i}\). After the final update, i.e. when \( i = d-1 \), the upper row of the table contains the evaluations of Prover Polynomials at the challenge point \( (u_0,\ldots, u_{d-1}) \).
After computing the last challenge \( u_{d-1} \) in Round \( d-1 \) and updating \( \texttt{partially_evaluated_polynomials} \), the prover looks into the top row of the table containing evaluations \(P_1(u_0,\ldots, u_{d-1}), \ldots, P_N(u_0,\ldots, u_{d-1})\) and concatenates these values with the last challenge to the transcript.
The verifier algorithm is implemented in the Sumcheck Verifier class. See its documentation for a more detailed description of methods described below. The Sumcheck Round verification routine is abstracted into Sumcheck Verifier Round class.
The verifier's work reduces to the following.
For \( i = 0,\ldots, d-1\):
Entering the final round, the verifier has already checked that \(\quad \sigma_{ d-1 } = \tilde{S}^{d-1}(0) + \tilde{S}^{d-1}(1) \) and computed \(\sigma_d = \tilde{S}^{d-1}(u_{d-1})\).
\begin{align}\tilde{F}\left( P_1(u_0,\ldots, u_{d-1}), \ldots, P_N(u_0,\ldots, u_{d-1}) \right)\end{align}
\begin{align}\quad \sigma_{ d } \stackrel{?}{=} \tilde{F}\left(P_1(u_{0}, \ldots, u_{d-1}),\ldots, P_N(u_0,\ldots, u_{d-1})\right)\end{align}
As explained in Section 13.3 of Proofs, Arguments, and Zero-Knowledge, there are two main sources that leak prover's private information:
These issues are resolved by enhancing Sumcheck with a technique that randomizes any given number of evaluations of \(\tilde{S}^{i} \) and a technique that randomizes evaluations of witness polynomials \( P_1,\ldots, P_{N_w} \) at the challenge point \((u_0,\ldots, u_{d-1})\) obtained in Sumcheck.
To prevent the witness information leakage through the Round Univariates determined by their evaluations over the domain \( \{0,\ldots, \tilde{D}\}\), where \(\tilde{D} \geq D\) is specified by the BATCHED_RELATION_PARTIAL_LENGTH of a ZK-Flavor, the Sumcheck Prover masks them using a low-degree multivariate polynomial
\begin{align} G \gets \sum_{i=0}^{d-1} g_{i}(X_i), \end{align}
where \( d \) is the number of Sumcheck rounds, and the Libra univariates are given by the formula
\begin{align} g_{i} = \sum_{j=0}^{\tilde{D}} g_{i,j} \cdot L_{j,\{0,\ldots, \tilde{D}\}}(X_i) \quad \text{for } (g_{i,j}) \gets_{\$} \mathbb{F}^{d\cdot (\tilde{D}+1)} \end{align}
and \(L_{j, \{0,\ldots, \tilde{D}\}}\) is the \(j\)th univariate Lagrange polynomial for the domain \(\{0,\ldots, \tilde{D}\}\). Recall that \(\deg_{X_i} \left(L_{j, \{0,\ldots, \tilde{D}\}} (X_i)\right) = \tilde{D}\).
Set
\begin{align} \texttt{libra_total_sum} \gets \sum_{\vec \ell \in \{0,1\}^{d}} G(\vec \ell) \end{align}
as the value that the honest prover sends to the verifier, and let \(\texttt{libra_challenge}\) be a challenge obtained by hashing the transcript containing the commitments to Libra univariates and the Libra total sum. Then instead of proving that \(\sum \tilde{F}\left(\vec \ell\right) =\sigma\) as in Non-ZK Sumcheck, we run the protocol that establishes that
\begin{align} \sum_{\vec \ell \in\{0,1\}^{d}} \left(\tilde{F}(P_1(\vec \ell), \ldots, P_N(\vec \ell)) + \rho \cdot G(\vec \ell)\right) = \sigma + \texttt{libra_challenge} \cdot \texttt{libra_total_sum}. \end{align}
Observe that \( G \) has several important properties
The first two properties imply that the evaluations of Sumcheck Round Univariates for \(G\) are independent and uniformly distributed. We call them Libra Round Univariates.
Consider Round Univariates for \( \tilde{F} + \texttt{libra_challenge}\cdot G\) which are the sums of the Sumcheck Round Univariates for \( \tilde{F} \) and Libra Round Univariates multiplied by the challenge. The fact that the degrees of Libra Round Univariates are big enough (i.e. \( \tilde{D}\geq D \)) and that their evaluations are random imply that the evaluations \( \tilde{S}^i(0),\ldots,\tilde{S}^i(\tilde D)\) defined in Compute Round Univariates are now masked by the evaluations of Libra Round Univariates. These evaluations are described explicitly below.
If in every round of Sumcheck, the prover aims to hide only \(2\) evaluations the Round Univariate, i.e. if \(\tilde{D} = 1\), the masking polynomial \( G \) has the following form
\begin{align} G = \left( g_{0,0} (1- X_0) + g_{0,1} X_0 \right) + \ldots + \left( g_{d-1,0} (1- X_{d-1}) + g_{d-1,1} X_{d-1} \right). \end{align}
To commit to multivariate polynomial \( G \), the prover commits to the tuple of univariate polynomials \( (g_0,\ldots, g_{d-1})\).
Since \(G\) is a polynomial of a very special form, the computation of \(\texttt{libra_total_sum}\) reduces to the following
\begin{align} \sum_{\vec \ell \in \{0,1\}^{d}} G(\vec \ell) = \sum_{i=0}^{d-1} \sum_{\vec \ell \in \{0,1\}^{d}} g_{i}(\ell_i) = 2^{d-1} \sum_{i = 0}^{d-1} \left( g_i(0) + g_i(1) \right), \end{align}
since the evaluations of \( g_i \) at \(\vec \ell \in \{0,1\}^{d}\) depend only on \( \ell_i \), and therefore, there are \(2^{d-1}\) summands \( g_i(0) \) corresponding to the points \(\vec \ell\) with \(\ell_i=0\) and \(2^{d-1}\) summands \( g_i(1) \) corresponding to \(\vec \ell\) with \(\ell_i=1\).
The prover computes
\begin{align} \texttt{libra_total_sum} \gets 2^{d-1} \sum_{i = 0}^{d-1} \left( g_i(0) + g_i(1) \right). \end{align}
using method compute_libra_total_sum called by the method setup_zk_sumcheck_data, which also adds the Libra sum to the transcript.
As in Sumcheck Book-keeping, we use a table of evaluations of Libra univariates that is being updated in each round. Namely, before entering the first round, the prover updates the vector of Libra univariates in place
\begin{align} \texttt{libra_univariates}_{j}(k) \gets \texttt{libra_challenge} \cdot 2^{d-1} \cdot g_{j}(k) \text{ for } j= i,\ldots, d-1, \text{ and } k=0,\ldots, \tilde{D} \end{align}
and computes the term
\begin{align} \texttt{libra_running_sum} \gets 2^{-1} \left( \texttt{libra_challenge} \cdot \texttt{libra_total_sum} - \left(\texttt{libra_univariates}_{0}(0) + \texttt{libra_univariates}_{0}(1)\right) \right). \end{align}
These entities are created inside setup_zk_sumcheck_data and stored in a ZKSumcheckData structure zk_sumcheck_data. All the modifications between the Sumcheck rounds are performed by the method update Libra data that is called by update_zk_sumcheck_data.
The prover computes the first Libra round univariate
\begin{align} \texttt{libra_round_univariate}_0(X_0) = \texttt{libra_challenge} \cdot \sum_{\vec \ell \in \{0,1\}^{d-1}} G(X_0,\vec \ell) = 2^{d-1} \texttt{libra_challenge}\cdot g_0(X_0) + 2^{d-2} \texttt{libra_challenge} \cdot \sum_{i=1}^{d-1}\left(g_i(0)+g_i(1)\right). \end{align}
By design of the method setup_zk_sumcheck_data, the latter could be expressed as follows
\begin{align} \texttt{libra_round_univariate}_0 (k) \gets \texttt{libra_univariates}_{0}(k) + \texttt{libra_running_sum} \end{align}
for \(k=0,\ldots, \tilde{D}\). It is done by the method compute_libra_round_univariate called inside Sumcheck Round Univariate computation, which also takes care of adding \(\texttt{libra_round_univariate}\) to the \(\texttt{round_unviariate}\).
When the prover receives the challenge \(u_0\), it updates Libra data:
\begin{align} \texttt{libra_running_sum} \gets 2^{d-2} \cdot \texttt{libra_challenge} \cdot g_0(u_0) + 2^{-1} \cdot \left( \texttt{libra_running_sum} - (\texttt{libra_univariates}_{1}(0) + \texttt{libra_univariates}_{1}(1)) \right) \end{align}
In Round \( i \), the prover computes \( i \)-th Libra round univariate
\begin{align} \texttt{libra_univariate}_i(X_i) = \texttt{libra_challenge} \cdot \sum_{\vec \ell \in \{0,1\}^{d-1 - i}} G(u_0,\ldots, u_{i-1}, X_{i}, \vec \ell) = \texttt{libra_challenge} \cdot 2^{d-1 - i} \left( \sum_{j = 0}^{i-1} g_j(u_{j}) + g_{i}(X_i) + \sum_{j=i+1}^{d-1} \left(g_{j,0} + g_{j,1}\right) \right) \end{align}
By design of the method update_zk_sumcheck_data, the latter could be expressed as follows
\begin{align} \texttt{libra_round_univariate}_i (k) \gets \texttt{libra_univariates}_{i}(k) + \texttt{libra_running_sum} \end{align}
for \(k=0,\ldots, \tilde{D}\). This computation is done by the method compute_libra_round_univariate called inside Sumcheck Round Univariate computation, which also adds \(\texttt{libra_round_univariate}\) to the \(\texttt{round_unviariate}\).
When the prover receives new challenge \(u_i\), it updates Libra data. If \( i < d-1\), the prover
\begin{align} \texttt{libra_running_sum} \gets 2^{d-i-2} \cdot \texttt{libra_challenge} \cdot g_0(u_0) + 2^{-1} \cdot \left( \texttt{libra_running_sum} - (\texttt{libra_univariates}_{i+1}(0) + \texttt{libra_univariates}_{i+1}(1)) \right) \end{align}
If \( i = d-1\), the proverLibra claimed evaluations \( g_0(u_0), \ldots, g_{d-1}(u_d-1)\) have to proved using shplonk .
The overhead in prover's field operations is linear in \( d\cdot \tilde D \) with a small constant and therefore, is negligible compared to the number of field operations performed during the main Sumcheck routine.
The main expenses are caused by proving the evaluations of \( g_i (u_i) = v_i\) in the Final Round. Using the PCS introduced in Section 4 of Efficient polynomial commitment schemes for multiple points and polynomials also known as Shplonk, we reduce the costs of opening \( d \) univariate polynomials \( g_i \), each at different \( u_i \) to the following:
| Prover | Verifier | |
|---|---|---|
| Group Operations | \( 2 \cdot \tilde D+1\) | \( d + 3 \) |
| Field Operations | \( O\left(d\cdot (\tilde{D} +1) + \tilde{D} \log(\tilde{D})\right)\) | |
| Pairings | 2 | |
| Proof Size | 2 group elements | |
At the last step of Sumcheck, the Prover adds the evaluations of multilinear polynomials \(P_1,\ldots, P_N \) at the challenge point \(\vec u = (u_0,\ldots, u_{d-1})\) to the transcript.
Let \( N_w\leq N\) and assume that \( P_1,\ldots, P_{N_w}\) are witness polynomials. To mask their evaluations at the challenge point \(\vec u\), the prover samples
\begin{align}\rho_1,\ldots \rho_{N_w} \gets_{\$} \mathbb{F}^{N_w}\end{align}
and sets
\begin{align} \texttt{masked_witness_polynomial}\_j(X_0,\ldots, X_{d-1}) = \widehat{P}_j \gets P_j(X_0,\ldots, X_{d-1}) + \rho_j \cdot \left(\sum_{k=0}^{d-1} X_k(1-X_k) \right). \end{align}
Note that for any relation \(F\), we have
\begin{align} \sum_{\ell \in \{0,1\}^d} pow_{\beta}(X_0,\ldots, X_{d-1}) \cdot F\left(P_1(\ell), \ldots, P_N(\ell)\right) = pow_{\beta}(X_0,\ldots, X_{d-1}) \sum_{\ell \in \{0,1\}^d} F\left(\widehat{P}\_1(\ell), \ldots, \widehat{P}_{N_w}(\ell), P_{N_w+1}(\ell), \ldots, P_{N}(\ell)\right) \end{align}
as \(P_j\) and \(\widehat{P}_j\) agree on the hypercube \(\{0,1\}^d\) for \(j=1,\ldots, N_w\).
The prover commits to \(P_j\) for \(j=1,\ldots, N\) and to \(\rho_j\) for \( j=1, \ldots, N_w\) as multilinear polynomials and sends the commitments to the verifier.
At the end of the Sumcheck, instead of proving the evaluations of witness polynomials \(P_j\) at \(\vec u\) for \(j=1,\ldots, N_w\), the prover opens multilinear polynomials
\begin{align} \widehat{P}_j^{\vec u} \gets P_j(X_0,\ldots, X_{d-1}) + \rho_j \cdot \left(\sum_{k=0}^{d-1} u_k(1-u_k) \right), \end{align}
where \( \rho_j \) is treated as a multilinear polynomial in \( X_0,\ldots, X_{d-1}\).
It is important to notice that the verifier could evaluate public polynomial \(\sum_{k=0}^{d-1} X_k(1-X_k)\) and derive the commitments to \(\widehat{P}_j^{\vec u}\) on its own.
The remaining prover polynomials \(P_{N_w+1}, \ldots, P_{N}\) are evaluated at \( \vec u \) and, if needed, their evaluations are proved without any modifications.
Before proving the evaluations of \(\widehat{P}_j^{\vec u} \), the prover checks that \(\vec u\) does not satisfy the equation \(\sum_{k=0}^{d-1} X_k(1-X_k) = 0\), which generally has many solutions outside of the hypercube \(\{0,1\}^d\).
Since masked witness polynomials \(\widehat{P}_j\) are of degree \(2\) in every variable, the degree of Sumcheck round univariates is also affected. Namely, we set
\begin{align} \tilde{D} = \max_{i\in\{0,\ldots,d-1\}} \left\{\deg_{X_i} F\left(\widehat{P}_1(X_0,\ldots,X_{d-1}),\ldots, \widehat{P}_{N_w}(X_0,\ldots, X_{d-1}),\widehat{P}_{N_w+1}(X_0,\ldots, X_{d-1}), \ldots, \widehat{P}_{N}(X_0,\ldots, X_{d-1}) \right) \right\} \leq D + D_{w} \end{align}
for \(D\) and \( D_w \) defined in Parameters.
In every round of Sumcheck, the Prover sends univariate polynomials \(\tilde{S}^i(X_i)\) represented by their evaluations at \(X_i = 0,\ldots, \tilde{D}\).
Note that \( \tilde{D} \) sets up the corresponding parameter of Libra
The random scalars \( \rho_1,\ldots, \rho_{N_w}\) are created by the method setup_zk_sumcheck_data and are stored as \( \texttt{eval_masking_scalars} \).
To facilitate the computation of Sumcheck Round Univariates, the prover creates the vector of univariates
\begin{align} \texttt{masking_terms_evaluations}_j(k)\gets \texttt{eval_masking_scalars}_j \cdot (1-k) k \end{align}
of the same size as the ExtendedEdges created by the ZK Flavor running Sumcheck.
When the prover receives the challenge \( u_i \), this vector is updated as follows
\begin{align} \texttt{masking_terms_evaluations}_j(k) \gets \texttt{eval_masking_scalars}_j \cdot u_i \cdot (1-u_i) \end{align}
In Round \(i \in \{0,\ldots, d-1\}\), the prover computes univariate polynomials
\begin{align} \widehat{S}^i(X_i) = \sum_{\vec\ell \in \{0,1\}^{d-1-i}} F\left(\widehat{P}_1(u_0,\ldots, u_{i-1}, X_i, \vec \ell),\ldots,\widehat{P}_{N_w}(u_0,\ldots, u_{i-1}, X_i, \vec \ell), P_{N_w+1}(u_0,\ldots, u_{i-1}, X_i, \vec \ell), \ldots, P_{N}(u_0,\ldots, u_{i-1}, X_i, \vec \ell) \right) \end{align}
which reduces to computing at most \( (D+ D_w + 1) \times N \times 2^{d-1 - i}\) values
\begin{align} &\ P_j(u_0,\ldots, u_{i-1}, k, \vec \ell) + \rho_j \cdot \sum_{k=0}^{i-1} u_k(1-u_k) + \rho_j\cdot (1-k) k \quad \text{ for } j=1,\ldots, N_w\\ &\ P_j(u_0,\ldots, u_{i-1}, k, \vec \ell) \quad \text { for } j= N_w+1,\ldots, N \end{align}
By design, we have
\begin{align} \texttt{masking_terms_evaluations}_j(k) = \rho_j \cdot \sum_{k=0}^{i-1} u_k(1-u_k) + \rho_j\cdot (1-k) k. \end{align}
Then the method extend_zk_edges gets the \(j\)-th edge corresponding to the witness polynomial and corrects it with the univariate \( \texttt{masking_terms_evaluations}_j\). The non-witness polynomials are treated as in extend_edges used in non-ZK Flavors.
The prover performs an extra addition per evaluation \(\widehat{P}_j(u_0,\ldots, u_{i-1}, k, \vec \ell)\) for \(k=0,1\) and two extra additions per evaluation for \(k=2,\ldots, D+D_w\) compared to evaluating the original witness polynomials \(P_j\). It results in \(2 (D+D_w) N_w (2^d-1) \) extra additions compared to Non-ZK-Sumcheck.
In contrast to non-ZK-Sumcheck, the prover needs to compute \(\tilde{D} \sim D+D_w \) evaluations of round univariates \(S_i\), which results in
\begin{align} ((D+D_w)\cdot N + C_a \cdot (D+D_w) + 2\cdot N + 2\cdot (D+D_w) N_w ) (2^d - 1) \end{align}
additions and
\begin{align} (C_m\cdot (D+D_w) + N) \cdot (2^d -1) \end{align}
multiplications, where \(C_a\) and \(C_m\) are constants corresponding to the number of additions and multiplications required to evaluate the relation polynomial \(F\).
The overhead is summarized in the following table.
| Prover | Verifier | |
|---|---|---|
| Group Operations | \( + N_w\) MSMs of size \(2^d\) (same group element) | \( + N_w\) MSMs of size 2 |
| Field Operations | \(\times(1+ D_w/D) \) | \(\times(1+D_w/D) \) |
| Communication | \( + N_w\) group elements; \( +D_w\cdot d\) field elements | |
The total costs of ZK Sumcheck are obtained from Libra Costs and Witness Evaluation Masking Costs.
| Prover | Verifier | |
|---|---|---|
| Group Operations |
\(+ d\) MSMs of size \((D+D_w)\) = Libra Commitments \(+ \left(2 \cdot (D+D_w) D+1\right)\) group ops = shplonk \(+ N_w\) MSMs of size \(2^d\) (same group element multiplied by \(\rho_1,\ldots,\rho_{N_w}\)) |
\( + (d + 3) \) group ops \( + N_w\) MSMs of size \(2\) |
| Field Operations | \( \times D_w/D \) | \( \times D_w/D \) |
| Pairings | + 2 | |
| Communication |
\(+ (d+ 2)\) group elements for Libra; \(+N_w\) group elements for witness masking \(+ D_w \cdot d \) field elements | |
The table above sets a reasonable upper bound on the amount of prover's field operations. However, in the implementation, the relation \( F \) is computed as a vector of its subrelations, which allows us to decrease the costs of computing the round univariates. Namely, for a given subrelation \( F_j \), its maximum partial degree \(D_j\) and its witness degree \(D_{w,j} \) are generally less than \( D\) and \( D_w \), respectively. Therefore, we compute \( F_j \)'s contribution to Sumcheck Round Univariates by evaluating the univariate polynomial
\begin{align} \sum_{\vec \ell\in \{0,1\}^{d-1-i}} pow_{\beta}(u_0,\ldots, u_{i-1}, X_i, \vec \ell) \cdot F_j(u_0,\ldots, u_{i-1}, X_i,\vec \ell) \end{align}
at \( X_i = 0,\ldots, D_i + D_{w,i}\) and extend the resulting univariate of degree \(D_j+D_{w,j}\) to the entire domain \(\{ 0,\ldots, D+D_w\}\), which is way cheaper than evaluating the sum above at \( X_i = D_{j}+ D\_{w,j}+1, \ldots, D+ D_w \)
1.9.8