proof_system::honk::sumcheck::SumcheckProver< Flavor > Class Template Reference

Public Types
using	FF = typename Flavor::FF
using	ProverPolynomials = typename Flavor::ProverPolynomials
using	PartiallyEvaluatedMultivariates = typename Flavor::PartiallyEvaluatedMultivariates
using	ClaimedEvaluations = typename Flavor::AllValues
using	Transcript = typename Flavor::Transcript
using	Instance = ProverInstance_< Flavor >

Public Member Functions
	SumcheckProver (size_t multivariate_n, const std::shared_ptr< Transcript > &transcript)
SumcheckOutput< Flavor >	prove (ProverPolynomials &full_polynomials, const proof_system::RelationParameters< FF > &relation_parameters, FF alpha)
	Compute univariate restriction place in transcript, generate challenge, partially evaluate,... repeat until final round, then compute multivariate evaluations and place in transcript.
SumcheckOutput< Flavor >	prove (std::shared_ptr< Instance > instance)
	Compute univariate restriction place in transcript, generate challenge, partially evaluate,... repeat until final round, then compute multivariate evaluations and place in transcript.
void	partially_evaluate (auto &polynomials, size_t round_size, FF round_challenge)
	Evaluate at the round challenge and prepare class for next round. Illustration of layout in example of first round when d==3 (showing just one Honk polynomial, i.e., what happens in just one column of our two-dimensional array):
template<typename PolynomialT , std::size_t N>
void	partially_evaluate (std::array< PolynomialT, N > &polynomials, size_t round_size, FF round_challenge)
	Evaluate at the round challenge and prepare class for next round. Specialization for array, see generic version above.

Public Attributes
std::shared_ptr< Transcript >	transcript
const size_t	multivariate_n
const size_t	multivariate_d
SumcheckProverRound< Flavor >	round
PartiallyEvaluatedMultivariates	partially_evaluated_polynomials
	(partially_evaluated_polynomials) Suppose the Honk polynomials (multilinear in d variables) are called P_1, ..., P_N. At initialization, we think of these as lying in a two-dimensional array, where each column records the value of one P_i on H^d. After the first round, the array will be updated (partially evaluated), so that the first n/2 rows will represent the evaluations P_i(u0, X1, ..., X_{d-1}) as a low-degree extension on H^{d-1}. In reality, we elude copying all of the polynomial-defining data by only populating partially_evaluated_polynomials after the first round. I.e.:

Member Function Documentation

partially_evaluate()

template<typename Flavor >

void proof_system::honk::sumcheck::SumcheckProver< Flavor >::partially_evaluate ( auto &  polynomials, size_t  round_size, FF  round_challenge  )

inline

Evaluate at the round challenge and prepare class for next round. Illustration of layout in example of first round when d==3 (showing just one Honk polynomial, i.e., what happens in just one column of our two-dimensional array):

groups vertex terms collected vertex terms groups after partial evaluation g0 – v0 (1-X0)(1-X1)(1-X2) — (v0(1-X0) + v1 X0) (1-X1)(1-X2) -— (v0(1-u0) + v1 u0) (1-X1)(1-X2) - v1 X0 (1-X1)(1-X2) –/ — (v2(1-u0) + v3 u0) X1 (1-X2) g1 – v2 (1-X0) X1 (1-X2) — (v2(1-X0) + v3 X0) X1 (1-X2)-/ – (v4(1-u0) + v5 u0) (1-X1) X2 - v3 X0 X1 (1-X2) –/ / - (v6(1-u0) + v7 u0) X1 X2 g2 – v4 (1-X0)(1-X1) X2 — (v4(1-X0) + v5 X0) (1-X1) X2 -/ / - v5 X0 (1-X1) X2 –/ / g3 – v6 (1-X0) X1 X2 — (v6(1-X0) + v7 X0) X1 X2 -/ - v7 X0 X1 X2 –/

prove()

template<typename Flavor >

SumcheckOutput< Flavor > proof_system::honk::sumcheck::SumcheckProver< Flavor >::prove ( ProverPolynomials &  full_polynomials, const proof_system::RelationParameters< FF > &  relation_parameters, FF  alpha  )

inline

Compute univariate restriction place in transcript, generate challenge, partially evaluate,... repeat until final round, then compute multivariate evaluations and place in transcript.

Member Data Documentation

partially_evaluated_polynomials

template<typename Flavor >

PartiallyEvaluatedMultivariates proof_system::honk::sumcheck::SumcheckProver< Flavor >::partially_evaluated_polynomials

(partially_evaluated_polynomials) Suppose the Honk polynomials (multilinear in d variables) are called P_1, ..., P_N. At initialization, we think of these as lying in a two-dimensional array, where each column records the value of one P_i on H^d. After the first round, the array will be updated (partially evaluated), so that the first n/2 rows will represent the evaluations P_i(u0, X1, ..., X_{d-1}) as a low-degree extension on H^{d-1}. In reality, we elude copying all of the polynomial-defining data by only populating partially_evaluated_polynomials after the first round. I.e.:

We imagine all of the defining polynomial data in a matrix like this: | P_1 | P_2 | P_3 | P_4 | ... | P_N | N = number of multivariatesk |--------------------------------—| group 0 –| * | * | * | * | ... | * | vertex 0 -| * | * | * | * | ... | * | vertex 1 group 1 –| * | * | * | * | ... | * | vertex 2 -| * | * | * | * | ... | * | vertex 3 | * | * | * | * | ... | * | group m-1 –| * | * | * | * | ... | * | vertex n-2 -| * | * | * | * | ... | * | vertex n-1 m = n/2

Each group consists of N edges |, and our construction of univariates and partial evaluation

operations naturally operate on these groups of edges

NOTE: With ~40 columns, prob only want to allocate 256 EdgeGroup's at once to keep stack under 1MB? TODO(#224)(Cody): might want to just do C-style multidimensional array? for guaranteed adjacency?

---

The documentation for this class was generated from the following file:

• src/barretenberg/sumcheck/sumcheck.hpp