Prover class for the Goblin ECC op queue transcript merge protocol. More...

#include <merge_prover.hpp>

Public Types
using	MergeProof = std::vector< FF >

Public Member Functions
	MergeProver (const std::shared_ptr< ECCOpQueue > &op_queue, const MergeSettings settings=MergeSettings::PREPEND, const CommitmentKey &commitment_key=CommitmentKey(), const std::shared_ptr< Transcript > &transcript=std::make_shared< Transcript >())
	Create MergeProver.

BB_PROFILE MergeProof	construct_proof ()
	Prove proper construction of the aggregate Goblin ECC op queue polynomials T_j.

Public Attributes
std::shared_ptr< ECCOpQueue >	op_queue

CommitmentKey	pcs_commitment_key

std::shared_ptr< Transcript >	transcript

MergeSettings	settings

Static Public Attributes
static constexpr size_t	NUM_WIRES = MegaExecutionTraceBlocks::NUM_WIRES

Private Types
using	Curve = curve::BN254

using	FF = Curve::ScalarField

using	Commitment = Curve::AffineElement

using	Polynomial = bb::Polynomial< FF >

using	CommitmentKey = bb::CommitmentKey< Curve >

using	PCS = KZG< Curve >

using	OpeningClaim = ProverOpeningClaim< Curve >

using	OpeningPair = bb::OpeningPair< Curve >

using	Transcript = NativeTranscript

Static Private Member Functions
static Polynomial	compute_degree_check_polynomial (const std::array< Polynomial, NUM_WIRES > &left_table, const std::vector< FF > &degree_check_challenges)
	Compute the batched polynomial for the degree check.

static Polynomial	compute_shplonk_batched_quotient (const std::array< Polynomial, NUM_WIRES > &left_table, const std::array< Polynomial, NUM_WIRES > &right_table, const std::array< Polynomial, NUM_WIRES > &merged_table, const std::vector< FF > &shplonk_batching_challenges, const FF &kappa, const FF &kappa_inv, const Polynomial &reversed_batched_left_tables, const std::vector< FF > &evals)
	Compute the batched Shplonk quotient polynomial.

static OpeningClaim	compute_shplonk_opening_claim (Polynomial &shplonk_batched_quotient, const FF &shplonk_opening_challenge, const std::array< Polynomial, NUM_WIRES > &left_table, const std::array< Polynomial, NUM_WIRES > &right_table, const std::array< Polynomial, NUM_WIRES > &merged_table, const std::vector< FF > &shplonk_batching_challenges, const FF &kappa, const FF &kappa_inv, Polynomial &reversed_batched_left_tables, const std::vector< FF > &evals)
	Compute the partially evaluated Shplonk batched quotient and the resulting opening claim.

Private Attributes
std::vector< std::string >	labels_degree_check

std::vector< std::string >	labels_shplonk_batching_challenges

Detailed Description

Prover class for the Goblin ECC op queue transcript merge protocol.

Definition at line 22 of file merge_prover.hpp.

Member Typedef Documentation

◆ Commitment

using bb::MergeProver::Commitment = Curve::AffineElement

private

Definition at line 25 of file merge_prover.hpp.

◆ CommitmentKey

using bb::MergeProver::CommitmentKey = bb::CommitmentKey<Curve>

private

Definition at line 27 of file merge_prover.hpp.

◆ Curve

using bb::MergeProver::Curve = curve::BN254

private

Definition at line 23 of file merge_prover.hpp.

◆ FF

using bb::MergeProver::FF = Curve::ScalarField

private

Definition at line 24 of file merge_prover.hpp.

◆ MergeProof

using bb::MergeProver::MergeProof = std::vector<FF>

Definition at line 34 of file merge_prover.hpp.

◆ OpeningClaim

using bb::MergeProver::OpeningClaim = ProverOpeningClaim<Curve>

private

Definition at line 29 of file merge_prover.hpp.

◆ OpeningPair

using bb::MergeProver::OpeningPair = bb::OpeningPair<Curve>

private

Definition at line 30 of file merge_prover.hpp.

◆ PCS

using bb::MergeProver::PCS = KZG<Curve>

private

Definition at line 28 of file merge_prover.hpp.

◆ Polynomial

using bb::MergeProver::Polynomial = bb::Polynomial<FF>

private

Definition at line 26 of file merge_prover.hpp.

◆ Transcript

using bb::MergeProver::Transcript = NativeTranscript

private

Definition at line 31 of file merge_prover.hpp.

Constructor & Destructor Documentation

◆ MergeProver()

bb::MergeProver::MergeProver	(	const std::shared_ptr< ECCOpQueue > &	op_queue,
		const MergeSettings	settings = `MergeSettings::PREPEND`,
		const CommitmentKey &	commitment_key = `CommitmentKey()`,
		const std::shared_ptr< Transcript > &	transcript = `std::make_shared<Transcript>()`
	)

explicit

Create MergeProver.

We require an SRS at least as large as the current ultra ecc ops table TODO(https://github.com/AztecProtocol/barretenberg/issues/1267): consider possible efficiency improvements

Definition at line 18 of file merge_prover.cpp.

Member Function Documentation

◆ compute_degree_check_polynomial()

MergeProver::Polynomial bb::MergeProver::compute_degree_check_polynomial	(	const std::array< Polynomial, NUM_WIRES > &	left_table,
		const std::vector< FF > &	degree_check_challenges
	)

staticprivate

Compute the batched polynomial for the degree check.

To show that \(\deg(L_j) < k\), the prover batches the \(L_i\)'s as \(\sum_i \alpha_i L_i\) and computes \(G(X) = (\sum_i \alpha_i L_i(X)) X^{k-1}\). The prover commits to \(G\) and later opens \(L_i\) at \(\kappa\) and \(G\) at \(\kappa^{-1}\), so to show that \(G(\kappa^{-1}) = (\sum_i \alpha_i L_i(\kappa)) * \kappa^{-(k-1)}\).

Parameters

left_table
degree_check_challenges

Returns: Polynomial

Definition at line 40 of file merge_prover.cpp.

◆ compute_shplonk_batched_quotient()

MergeProver::Polynomial bb::MergeProver::compute_shplonk_batched_quotient	(	const std::array< Polynomial, NUM_WIRES > &	left_table,
		const std::array< Polynomial, NUM_WIRES > &	right_table,
		const std::array< Polynomial, NUM_WIRES > &	merged_table,
		const std::vector< FF > &	shplonk_batching_challenges,
		const FF &	kappa,
		const FF &	kappa_inv,
		const Polynomial &	reversed_batched_left_tables,
		const std::vector< FF > &	evals
	)

staticprivate

Compute the batched Shplonk quotient polynomial.

This function computes the polynomial \(Q(X)\) such that \(Q(X) * (X - \kappa) * (X - \kappa^{-1}) = F(X)\), where \(F(X)\) is defined as

\[ (X - \kappa^{-1}) * (\sum_i \beta_i (L_i - l_i) + \sum_i \beta_i (R_i - r_i) + \sum_i \beta_i (M_i - m_i)) + (X - \kappa) * \beta_i (G - g) \]

Definition at line 50 of file merge_prover.cpp.

◆ compute_shplonk_opening_claim()

MergeProver::OpeningClaim bb::MergeProver::compute_shplonk_opening_claim	(	Polynomial &	shplonk_batched_quotient,
		const FF &	shplonk_opening_challenge,
		const std::array< Polynomial, NUM_WIRES > &	left_table,
		const std::array< Polynomial, NUM_WIRES > &	right_table,
		const std::array< Polynomial, NUM_WIRES > &	merged_table,
		const std::vector< FF > &	shplonk_batching_challenges,
		const FF &	kappa,
		const FF &	kappa_inv,
		Polynomial &	reversed_batched_left_tables,
		const std::vector< FF > &	evals
	)

staticprivate

Compute the partially evaluated Shplonk batched quotient and the resulting opening claim.

Compute the partially evaluated batched quotient \(Q'(X)\) defined as:

\[ -Q * (z - \kappa) + + (\sum_i \beta_i (L_i - l_i) + \sum_i \beta_i (R_i - r_i) + \sum_i \beta_i (M_i - m_i)) + (z - \kappa) / (z - \kappa^{-1}) * \beta_i (G - g) \]

and return the opening claim \(\{ Q', (z, 0) \}\).

Definition at line 95 of file merge_prover.cpp.

◆ construct_proof()

MergeProver::MergeProof bb::MergeProver::construct_proof ( )

Prove proper construction of the aggregate Goblin ECC op queue polynomials T_j.

Proves that M_j(X) = L_j(X) + X^k * R_j(X) and deg(L_j) < k for j = 1,2,3,4. Uses degree-check polynomial G(X) and Shplonk for batched openings.

For PREPEND: L = subtable (t), R = previous table (T_prev) For APPEND: L = previous table (T_prev), R = subtable (t)

See also: MERGE_PROTOCOL.md for complete protocol specification.

Returns: MergeProver::MergeProof

Definition at line 156 of file merge_prover.cpp.

Member Data Documentation

◆ labels_degree_check

std::vector<std::string> bb::MergeProver::labels_degree_check

private

Initial value:

= { "LEFT_TABLE_DEGREE_CHECK_0",
                                                     "LEFT_TABLE_DEGREE_CHECK_1",
                                                     "LEFT_TABLE_DEGREE_CHECK_2",
                                                     "LEFT_TABLE_DEGREE_CHECK_3" }

Definition at line 53 of file merge_prover.hpp.

◆ labels_shplonk_batching_challenges

std::vector<std::string> bb::MergeProver::labels_shplonk_batching_challenges

private

Initial value:

= {
        "SHPLONK_MERGE_BATCHING_CHALLENGE_0",  "SHPLONK_MERGE_BATCHING_CHALLENGE_1",
        "SHPLONK_MERGE_BATCHING_CHALLENGE_2",  "SHPLONK_MERGE_BATCHING_CHALLENGE_3",
        "SHPLONK_MERGE_BATCHING_CHALLENGE_4",  "SHPLONK_MERGE_BATCHING_CHALLENGE_5",
        "SHPLONK_MERGE_BATCHING_CHALLENGE_6",  "SHPLONK_MERGE_BATCHING_CHALLENGE_7",
        "SHPLONK_MERGE_BATCHING_CHALLENGE_8",  "SHPLONK_MERGE_BATCHING_CHALLENGE_9",
        "SHPLONK_MERGE_BATCHING_CHALLENGE_10", "SHPLONK_MERGE_BATCHING_CHALLENGE_11",
        "SHPLONK_MERGE_BATCHING_CHALLENGE_12"
    }

Definition at line 58 of file merge_prover.hpp.

◆ NUM_WIRES

constexpr size_t bb::MergeProver::NUM_WIRES = MegaExecutionTraceBlocks::NUM_WIRES

staticconstexpr

Definition at line 50 of file merge_prover.hpp.

◆ op_queue

std::shared_ptr<ECCOpQueue> bb::MergeProver::op_queue

Definition at line 43 of file merge_prover.hpp.

◆ pcs_commitment_key

CommitmentKey bb::MergeProver::pcs_commitment_key

Definition at line 44 of file merge_prover.hpp.

◆ settings

MergeSettings bb::MergeProver::settings

Definition at line 46 of file merge_prover.hpp.

◆ transcript

std::shared_ptr<Transcript> bb::MergeProver::transcript

Definition at line 45 of file merge_prover.hpp.

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

src/barretenberg/goblin/merge_prover.hpp
src/barretenberg/goblin/merge_prover.cpp

Public Types

Public Member Functions

Public Attributes

Static Public Attributes

Private Types

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Commitment

◆ CommitmentKey

◆ Curve

◆ FF

◆ MergeProof

◆ OpeningClaim

◆ OpeningPair

◆ PCS

◆ Polynomial

◆ Transcript

Constructor & Destructor Documentation

◆ MergeProver()

Member Function Documentation

◆ compute_degree_check_polynomial()

◆ compute_shplonk_batched_quotient()

◆ compute_shplonk_opening_claim()

◆ construct_proof()

Member Data Documentation

◆ labels_degree_check

◆ labels_shplonk_batching_challenges

◆ NUM_WIRES

◆ op_queue

◆ pcs_commitment_key

◆ settings

◆ transcript