gate_separator.hpp File Reference

#include "barretenberg/common/compiler_hints.hpp"
#include "barretenberg/common/op_count.hpp"
#include "barretenberg/common/thread.hpp"
#include "barretenberg/stdlib/primitives/bool/bool.hpp"
#include <cstddef>
#include <vector>

Go to the source code of this file.

Classes
struct	bb::GateSeparatorPolynomial< FF >
	Implementation of the methods for the \(pow_{\ell}\)-polynomials used in Protogalaxy and \(pow_{\beta}\)-polynomials used in Sumcheck. More...

Namespaces
namespace	bb
	Entry point for Barretenberg command-line interface.

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 \).

Variables
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) \).

Function Documentation

current_element()

FF GateSeparatorPolynomial::current_element

(

)

const

Computes the component at index current_element_idx in betas.

Returns

FF

Definition at line 96 of file gate_separator.hpp.

GateSeparatorPolynomial() [1/3]

GateSeparatorPolynomial::GateSeparatorPolynomial

(

const std::vector< FF > &

betas

)

Construct a new GateSeparatorPolynomial object without expanding to a vector of monomials.

The sumcheck verifier does not use beta_products

Parameters

betas

Definition at line 67 of file gate_separator.hpp.

GateSeparatorPolynomial() [2/3]

GateSeparatorPolynomial::GateSeparatorPolynomial	(	const std::vector< FF > &	betas,
		const size_t	log_num_monomials
	)

Construct a new GateSeparatorPolynomial.

Parameters

betas
log_num_monomials

Definition at line 56 of file gate_separator.hpp.

GateSeparatorPolynomial() [3/3]

GateSeparatorPolynomial::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}).

Definition at line 76 of file gate_separator.hpp.

operator[]()

FF const & GateSeparatorPolynomial::operator[]

(

size_t

idx

)

const

Retruns the element in beta_products at place #idx.

Parameters

idx

Returns

FF const&

Definition at line 90 of file gate_separator.hpp.

partially_evaluate() [1/2]

void GateSeparatorPolynomial::partially_evaluate	(	const FF &	challenge,
		const FF &	indicator
	)

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.

Parameters

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.

partially_evaluate() [2/2]

void GateSeparatorPolynomial::partially_evaluate

(

FF

challenge

)

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.

Parameters

challenge

\( i \)-th verifier challenge \( u_{i}\)

Definition at line 109 of file gate_separator.hpp.

univariate_eval()

FF GateSeparatorPolynomial::univariate_eval

(

FF

challenge

)

const

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.

Variable Documentation

beta_products

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\).

Definition at line 29 of file gate_separator.hpp.

betas

std::vector<FF> betas

The challenges \((\beta_0,\ldots, \beta_{d-1}) \).

Definition at line 22 of file gate_separator.hpp.

current_element_idx

size_t 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.

partial_evaluation_result

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.

periodicity

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.

Definition at line 40 of file gate_separator.hpp.