- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
Implementation of the methods for the \(pow_{\beta}\)-polynomials used in in Sumcheck. More...
#include <gate_separator.hpp>
Public Member Functions | |
| GateSeparatorPolynomial (const std::vector< FF > &betas, const size_t log_num_monomials) | |
| Construct a new GateSeparatorPolynomial. | |
| GateSeparatorPolynomial (const std::vector< FF > &betas) | |
| Construct a new GateSeparatorPolynomial object without expanding to a vector of monomials. | |
| GateSeparatorPolynomial (const std::vector< FF > &betas, const std::vector< FF > &challenge) | |
| Constructs a virtual GateSeparator used by the prover in rounds k > d - 1, and computes its partial evaluation at (u_0, ..., u_{d-1}). | |
| FF const & | operator[] (size_t idx) const |
| Retruns the element in beta_products at place #idx. | |
| FF | current_element () const |
| Computes the component at index current_element_idx in betas. | |
| FF | univariate_eval (FF challenge) const |
| Evaluate \( ((1−X_{i}) + X_{i}\cdot \beta_{i})\) at the challenge point \( X_{i}=u_{i} \). | |
| void | partially_evaluate (FF challenge) |
| Partially evaluate the \(pow_{\beta} \)-polynomial at the new challenge and update \( c_i \). | |
| void | partially_evaluate (const FF &challenge, const FF &indicator) |
| Partially evaluate the \(pow_{\beta} \)-polynomial at the new challenge and update \( c_i \). | |
Static Public Member Functions | |
| static BB_PROFILE Polynomial< FF > | compute_beta_products (const std::vector< FF > &betas, const size_t log_num_monomials, const FF &scaling_factor=FF(1)) |
| Given \( \vec\beta = (\beta_0,...,\beta_{d-1})\) compute \( pow_{\ell}(\vec \beta) = pow_{\beta}(\vec
\ell)\) for \( \ell =0,\ldots,2^{d}-1\). | |
Public Attributes | |
| std::vector< FF > | betas |
| The challenges \((\beta_0,\ldots, \beta_{d-1}) \). | |
| Polynomial< FF > | beta_products |
| The consecutive evaluations \( pow_{\ell}(\beta) = pow_{\beta}(\vec \ell) \) for \(\vec \ell\) identified with the integers \(\ell = 0,\ldots, 2^d-1\). | |
| size_t | current_element_idx = 0 |
| In Round \( i\) of Sumcheck, it points to the \( i \)-th element in \( \vec \beta \). | |
| size_t | periodicity = 2 |
| In Round \( i\) of Sumcheck, the periodicity equals to \( 2^{i+1}\) and represents the fixed interval at which elements not containing either of \( (\beta_0,\ldots ,β_i)\) appear in beta_products. | |
| FF | partial_evaluation_result = FF(1) |
| The value \(c_i\) obtained by partially evaluating one variable in the power polynomial at each round. At the end of Round \( i \) in the sumcheck protocol, variable \(X_i\) is replaced by the challenge \(u_i
\). The partial evaluation result is updated to represent \( pow_{\beta}(u_0,.., u_{i}) = \prod_{k=0}^{i} (
(1-u_k) + u_k\cdot \beta_k) \). | |
Implementation of the methods for the \(pow_{\beta}\)-polynomials used in in Sumcheck.
For \(0\leq \ell \leq 2^d-1 \), the \(pow_{\ell} \)-polynomials are multilinear polynomials defined by
\begin{align} pow_{\ell}(X_0,\ldots, X_{d-1}) = \prod_{k=0}^{d-1} ( ( 1-\ell_k ) + \ell_k \cdot X_k ) = \prod_{k=0}^{d-1} X_{k}^{ \ell_k } \end{align}
where \((\ell_0,\ldots, \ell_{d-1})\) is the binary representation of \(\ell \).
When betas is empty, the GateSeparatorPolynomial represents the constant polynomial equal to 1, meaning no gate separation is applied. This is useful for flavors where all subrelations are linearly dependent (not linearly independent), meaning they do not need to be scaled by the \( pow_{\beta} \)-polynomial.
Behavior when betas is empty:
This optimization avoids unnecessary multiplications by 1 in MultilinearBatchingFlavor, where gate separation is not needed.
For a fixed \( \vec \beta \in \mathbb{F}^d\), the map \( \ell \mapsto pow_{\ell} (\vec \beta)\) defines a polynomial
\begin{align} pow_{\beta} (X_0,\ldots, X_{d-1}) = \prod_{k=0}^{d-1} (1- X_k + X_k \cdot \beta_k) \end{align}
such that \( pow_{\beta} (\vec \ell) = pow_{\ell} (\vec \beta) \) for any \(0\leq \ell \leq 2^d-1 \) and any vector \((\beta_0,\ldots, \beta_{d-1}) \in \mathbb{F} ^d\).
Let \( i \) be the current Sumcheck round, \( i \in \{0, …, d-1\}\) and \( u_{0}, ..., u_{i-1} \) be the challenges generated in Rounds \( 0 \) to \( i-1\).
In Round \( i \), we iterate over the points \( (\ell_{i+1}, \ldots, \ell_{d-1}) \in \{0,1\}^{d-1-i}\). Define a univariate polynomial \(pow_{\beta}^i(X_i, \vec \ell) \) as follows
\begin{align} pow_{\beta}^i(X_i, \vec \ell) = pow_{\beta} ( u_{0}, ..., u_{i-1}, X_i, \ell_{i+1}, \ldots, \ell_{d-1}) = c_i \cdot ( (1−X_i) + X_i \cdot \beta_i ) \cdot \beta_{i+1}^{\ell_{i+1}}\cdot \cdots \cdot \beta_{d-1}^{\ell_{d-1}}, \end{align}
where \( c_i = \prod_{k=0}^{i-1} (1- u_k + u_k \cdot \beta_k) \). It will be used below to simplify the computation of Sumcheck round univariates.
We identify \( \vec \ell = (\ell_{i+1}, \ldots, \ell_{d-1}) \in \{0,1\}^{d-1 - i}\) with the binary representation of the integer \( \ell \in \{0,\ldots, 2^{d-1-i}-1 \}\).
Set
\begin{align}S^i_{\ell}( X_i ) = F( u_{0}, ..., u_{i-1}, X_{i}, \vec \ell ), \end{align}
i.e. \( S^{i}_{\ell}( X_i ) \) is the univariate of the full relation \( F \) defined by its partial evaluation at \((u_0,\ldots,u_{i-1}, \ell_{i+1},\ldots, \ell_{d-1}) \) which is an alpha-linear-combination of the subrelations evaluated at this point.
In Round \(i\), the prover computes the univariate polynomial for the relation defined by \( \tilde{F} (X_0,\ldots, X_{d-1}) = pow_{\beta}(X_0,\ldots, X_{d-1}) \cdot F\), namely
\begin{align} \tilde{S}^{i}(X_i) = \sum_{ \ell = 0} ^{2^{d-i-1}-1} pow^i_\beta ( X_i, \ell_{i+1}, \ldots, \ell_{d-1} ) S^i_{\ell}( X_i ) = c_i \cdot ( (1−X_i) + X_i\cdot \beta_i ) \cdot \sum_{ \ell = 0} ^{2^{d-i-1}-1} \beta_{i+1}^{\ell_{i+1}} \cdot \ldots \cdot \beta_{d-1}^{\ell_{d-1}} \cdot S^i_{\ell}( X_i ) \end{align}
Define
\begin{align} T^{i}( X_i ) = \sum_{\ell = 0}^{2^{d-i-1}-1} \beta_{i+1}^{\ell_{i+1}} \cdot \ldots \cdot \beta_{d-1}^{\ell_{d-1}} \cdot S^{i}_{\ell}( X_i ) \end{align}
then \( \deg_{X_i} (T^i) \leq \deg_{X_i} S^i \).
Definition at line 18 of file gate_separator.hpp.
|
inline |
Construct a new GateSeparatorPolynomial.
| betas | |
| log_num_monomials |
Definition at line 57 of file gate_separator.hpp.
|
inline |
Construct a new GateSeparatorPolynomial object without expanding to a vector of monomials.
The sumcheck verifier does not use beta_products
| betas |
Definition at line 68 of file gate_separator.hpp.
|
inline |
Constructs a virtual GateSeparator used by the prover in rounds k > d - 1, and computes its partial evaluation at (u_0, ..., u_{d-1}).
Definition at line 77 of file gate_separator.hpp.
|
inlinestatic |
Given \( \vec\beta = (\beta_0,...,\beta_{d-1})\) compute \( pow_{\ell}(\vec \beta) = pow_{\beta}(\vec \ell)\) for \( \ell =0,\ldots,2^{d}-1\).
| log_num_monomials | Determines the number of beta challenges used to compute beta_products (required because when we generate CONST_SIZE_PROOF_LOG_N, currently 28, challenges but the real circuit size is less than 1 << CONST_SIZE_PROOF_LOG_N, we should compute unnecessarily a vector of beta_products of length 1 << 28 ) |
Definition at line 161 of file gate_separator.hpp.
|
inline |
Computes the component at index current_element_idx in betas.
Definition at line 104 of file gate_separator.hpp.
|
inline |
Retruns the element in beta_products at place #idx.
| idx |
Definition at line 93 of file gate_separator.hpp.
|
inline |
Partially evaluate the \(pow_{\beta} \)-polynomial at the new challenge and update \( c_i \).
Update the constant \(c_{i} \to c_{i+1} \) multiplying it by \(pow_{\beta}\)'s factor \(\left( (1-X_i) + X_i\cdot \beta_i\right)\vert_{X_i = u_i}\) computed by univariate_eval.
| challenge | \( i \)-th verifier challenge \( u_{i}\) |
| indicator | An entry of padding_indicator_array, which is equal to 1 when round_idx < log_circuit_size and is 0 otherwise. |
Definition at line 141 of file gate_separator.hpp.
|
inline |
Partially evaluate the \(pow_{\beta} \)-polynomial at the new challenge and update \( c_i \).
Update the constant \(c_{i} \to c_{i+1} \) multiplying it by \(pow_{\beta}\)'s factor \(\left( (1-X_i) + X_i\cdot \beta_i\right)\vert_{X_i = u_i}\) computed by univariate_eval.
| challenge | \( i \)-th verifier challenge \( u_{i}\) |
Definition at line 123 of file gate_separator.hpp.
|
inline |
Evaluate \( ((1−X_{i}) + X_{i}\cdot \beta_{i})\) at the challenge point \( X_{i}=u_{i} \).
Definition at line 115 of file gate_separator.hpp.
| Polynomial<FF> bb::GateSeparatorPolynomial< FF >::beta_products |
The consecutive evaluations \( pow_{\ell}(\beta) = pow_{\beta}(\vec \ell) \) for \(\vec \ell\) identified with the integers \(\ell = 0,\ldots, 2^d-1\).
Definition at line 30 of file gate_separator.hpp.
| std::vector<FF> bb::GateSeparatorPolynomial< FF >::betas |
The challenges \((\beta_0,\ldots, \beta_{d-1}) \).
Definition at line 23 of file gate_separator.hpp.
| size_t bb::GateSeparatorPolynomial< FF >::current_element_idx = 0 |
In Round \( i\) of Sumcheck, it points to the \( i \)-th element in \( \vec \beta \).
Definition at line 35 of file gate_separator.hpp.
| FF bb::GateSeparatorPolynomial< FF >::partial_evaluation_result = FF(1) |
The value \(c_i\) obtained by partially evaluating one variable in the power polynomial at each round. At the end of Round \( i \) in the sumcheck protocol, variable \(X_i\) is replaced by the challenge \(u_i \). The partial evaluation result is updated to represent \( pow_{\beta}(u_0,.., u_{i}) = \prod_{k=0}^{i} ( (1-u_k) + u_k\cdot \beta_k) \).
Definition at line 49 of file gate_separator.hpp.
| size_t bb::GateSeparatorPolynomial< FF >::periodicity = 2 |
In Round \( i\) of Sumcheck, the periodicity equals to \( 2^{i+1}\) and represents the fixed interval at which elements not containing either of \( (\beta_0,\ldots ,β_i)\) appear in beta_products.
Definition at line 41 of file gate_separator.hpp.
1.9.8