- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
Implementation of the methods for the \(pow_{\ell}\)-polynomials used in Protogalaxy and \(pow_{\beta}\)-polynomials used 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 std::vector< FF > | compute_beta_products (const std::vector< FF > &betas, const size_t log_num_monomials) |
| 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}) \). | |
| std::vector< 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_{\ell}\)-polynomials used in Protogalaxy and \(pow_{\beta}\)-polynomials used in Sumcheck.
For \(0\leq \ell \leq 2^d-1 \), the \(pow_{\ell} \)-polynomials used in Protogalaxy is a multilinear polynomial defined by the formula
\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 \).
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 17 of file gate_separator.hpp.
|
inline |
Construct a new GateSeparatorPolynomial.
| betas | |
| log_num_monomials |
Definition at line 56 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 67 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 76 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 143 of file gate_separator.hpp.
|
inline |
Computes the component at index current_element_idx in betas.
Definition at line 96 of file gate_separator.hpp.
|
inline |
Retruns the element in beta_products at place #idx.
| idx |
Definition at line 90 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 125 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 109 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 101 of file gate_separator.hpp.
| std::vector<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 29 of file gate_separator.hpp.
| std::vector<FF> bb::GateSeparatorPolynomial< FF >::betas |
The challenges \((\beta_0,\ldots, \beta_{d-1}) \).
Definition at line 22 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 34 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 48 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 40 of file gate_separator.hpp.
1.9.8