Prover for the single-step Goblin ECC op queue merge protocol. More...

#include <merge_prover.hpp>

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

using	Table = std::array< Polynomial, NUM_WIRES >

Public Member Functions
	MergeProver (const std::shared_ptr< ECCOpQueue > &op_queue, std::shared_ptr< Transcript > transcript)
	Create MergeProver.

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

Public Attributes
CommitmentKey	pcs_commitment_key

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

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

Static Private Member Functions
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::shared_ptr< Transcript >	transcript

std::shared_ptr< ECCOpQueue >	op_queue

size_t	fixed_append_shift_size = 0

std::vector< std::string >	labels_degree_check

std::vector< std::string >	labels_shplonk_batching_challenges

Detailed Description

Prover for the single-step Goblin ECC op queue merge protocol.

Proves that the most recently merged subtable concatenates correctly with the prior aggregate table to form the new aggregate table. Used in the Chonk flow only for the final merge of the hiding kernel's subtable (placed at a fixed offset). For the multi-subtable batched merge proven once at the end of an IVC, see BatchMergeProver.

Definition at line 26 of file merge_prover.hpp.

Member Typedef Documentation

◆ Commitment

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

private

Definition at line 29 of file merge_prover.hpp.

◆ CommitmentKey

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

private

Definition at line 31 of file merge_prover.hpp.

◆ Curve

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

private

Definition at line 27 of file merge_prover.hpp.

◆ FF

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

private

Definition at line 28 of file merge_prover.hpp.

◆ MergeProof

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

Definition at line 38 of file merge_prover.hpp.

◆ OpeningClaim

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

private

Definition at line 33 of file merge_prover.hpp.

◆ OpeningPair

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

private

Definition at line 34 of file merge_prover.hpp.

◆ PCS

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

private

Definition at line 32 of file merge_prover.hpp.

◆ Polynomial

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

private

Definition at line 30 of file merge_prover.hpp.

◆ Table

using bb::MergeProver::Table = std::array<Polynomial, NUM_WIRES>

Definition at line 45 of file merge_prover.hpp.

◆ Transcript

using bb::MergeProver::Transcript = NativeTranscript

private

Definition at line 35 of file merge_prover.hpp.

Constructor & Destructor Documentation

◆ MergeProver()

bb::MergeProver::MergeProver	(	const std::shared_ptr< ECCOpQueue > &	op_queue,
		std::shared_ptr< Transcript >	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 19 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
	)		const

private

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 31 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 42 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 91 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.

L = aggregate table up to and including the tail subtable (T_tail), R = the hiding kernel's subtable (t, appended at a fixed offset and carrying APPEND_TRACE_OFFSET leading zeros), M = the resulting full table (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

◆ fixed_append_shift_size

size_t bb::MergeProver::fixed_append_shift_size = 0

private

Definition at line 52 of file merge_prover.hpp.

◆ 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 54 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 59 of file merge_prover.hpp.

◆ NUM_WIRES

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

staticconstexpr

Definition at line 39 of file merge_prover.hpp.

◆ op_queue

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

private

Definition at line 51 of file merge_prover.hpp.

◆ pcs_commitment_key

CommitmentKey bb::MergeProver::pcs_commitment_key

Definition at line 47 of file merge_prover.hpp.

◆ transcript

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

private

Definition at line 50 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

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Commitment

◆ CommitmentKey

◆ Curve

◆ FF

◆ MergeProof

◆ OpeningClaim

◆ OpeningPair

◆ PCS

◆ Polynomial

◆ Table

◆ 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

◆ fixed_append_shift_size

◆ labels_degree_check

◆ labels_shplonk_batching_challenges

◆ NUM_WIRES

◆ op_queue

◆ pcs_commitment_key

◆ transcript