Unified batch verifier for the batch Goblin ECC op queue merge protocol. More...

#include <batch_merge_verifier.hpp>

Classes
struct	ReductionResult
	Result of batch merge verification. More...

Public Types
using	FF = typename Curve::ScalarField

using	Commitment = typename Curve::AffineElement

using	PCS = bb::KZG< Curve >

using	PairingPoints = std::conditional_t< Curve::is_stdlib_type, stdlib::recursion::PairingPoints< Curve >, bb::PairingPoints< Curve > >

using	Proof = std::vector< FF >

using	Transcript = TranscriptFor_t< Curve >

using	ShplonkVerifier = ShplonkVerifier_< Curve >

using	TableCommitments = std::array< Commitment, NUM_WIRES >

Public Member Functions
	BatchMergeVerifier_ ()

ReductionResult	reduce_to_pairing_check (const Proof &proof, const FF hash)
	Reduce the batch merge proof to a pairing check.

Static Public Member Functions
static FF	ecc_op_hash_step (const std::vector< Commitment > &col_commitments, const std::optional< FF > &prev_hash=std::nullopt)
	Compute one step of the ECC op running hash.

Public Attributes
std::shared_ptr< Transcript >	transcript

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

static constexpr size_t	MAX_MERGE_SIZE = MaxMergeSize

static constexpr size_t	LOG_MAX_MERGE_SIZE = static_cast<size_t>(numeric::get_msb(MAX_MERGE_SIZE))

static constexpr bool	IsRecursive = Curve::is_stdlib_type

static constexpr size_t	NUM_COLUMN_TABLES = MAX_MERGE_SIZE + 1

static constexpr size_t	NUM_EVALS_FROM_COLUMNS = NUM_COLUMN_TABLES * NUM_WIRES

static constexpr size_t	NUM_EVALS

static constexpr size_t	NUM_OPENING_CLAIMS = NUM_EVALS

static constexpr size_t	MERGE_BATCHED_CLAIM_SIZE = NUM_OPENING_CLAIMS + 2

Private Member Functions
std::vector< FF >	compute_indicator_array (const FF &N) const
	Compute array of length M := MaxMergeSize s.t. indicator_array[i] = (i < N).

std::vector< FF >	compute_dirac_array (const std::vector< FF > &indicator_array) const
	Compute array of length M := MaxMergeSize s.t. dirac_array[i] = (i == N - 1)

bool	check_concatenation_identity (std::vector< FF > &evals, const std::vector< FF > &pow_kappa_subtable_size) const
	Verify the concatenation identity T(κ) = Σ_i C_i(κ) · κ^{offset_i} for every column.

bool	check_degree_identity (std::vector< FF > &evals, const std::vector< FF > &powers_of_kappa_inv, const FF &kappa, const std::vector< FF > &degree_check_challenges) const
	Verify the degree identity G(κ⁻¹) = Σ_{i,col} α_{i,col} · C_i_col(κ) · κ^{1 − shift_sizes[j]}.

bool	check_hash_consistency (const FF &hash, const std::vector< FF > &calculated_hashes, const std::vector< FF > &indicator_array) const
	Verify that the column commitments in the proof match the running hash from accumulation.

Detailed Description

template<typename Curve, size_t MaxMergeSize>
class bb::BatchMergeVerifier_< Curve, MaxMergeSize >

Unified batch verifier for the batch Goblin ECC op queue merge protocol.

Works for both native verification and recursive (in-circuit) verification.

Template Parameters

Curve	The curve type (native curve::BN254 or stdlib bn254<Builder>)
MaxMergeSize	The maximum number of subtables that can be merged

Definition at line 26 of file batch_merge_verifier.hpp.

Member Typedef Documentation

◆ Commitment

template<typename Curve , size_t MaxMergeSize>

using bb::BatchMergeVerifier_< Curve, MaxMergeSize >::Commitment = typename Curve::AffineElement

Definition at line 29 of file batch_merge_verifier.hpp.

◆ FF

template<typename Curve , size_t MaxMergeSize>

using bb::BatchMergeVerifier_< Curve, MaxMergeSize >::FF = typename Curve::ScalarField

Definition at line 28 of file batch_merge_verifier.hpp.

◆ PairingPoints

template<typename Curve , size_t MaxMergeSize>

using bb::BatchMergeVerifier_< Curve, MaxMergeSize >::PairingPoints = std::conditional_t<Curve::is_stdlib_type, stdlib::recursion::PairingPoints<Curve>, bb::PairingPoints<Curve> >

Definition at line 31 of file batch_merge_verifier.hpp.

◆ PCS

template<typename Curve , size_t MaxMergeSize>

using bb::BatchMergeVerifier_< Curve, MaxMergeSize >::PCS = bb::KZG<Curve>

Definition at line 30 of file batch_merge_verifier.hpp.

◆ Proof

template<typename Curve , size_t MaxMergeSize>

using bb::BatchMergeVerifier_< Curve, MaxMergeSize >::Proof = std::vector<FF>

Definition at line 33 of file batch_merge_verifier.hpp.

◆ ShplonkVerifier

template<typename Curve , size_t MaxMergeSize>

using bb::BatchMergeVerifier_< Curve, MaxMergeSize >::ShplonkVerifier = ShplonkVerifier_<Curve>

Definition at line 35 of file batch_merge_verifier.hpp.

◆ TableCommitments

template<typename Curve , size_t MaxMergeSize>

using bb::BatchMergeVerifier_< Curve, MaxMergeSize >::TableCommitments = std::array<Commitment, NUM_WIRES>

Definition at line 48 of file batch_merge_verifier.hpp.

◆ Transcript

template<typename Curve , size_t MaxMergeSize>

using bb::BatchMergeVerifier_< Curve, MaxMergeSize >::Transcript = TranscriptFor_t<Curve>

Definition at line 34 of file batch_merge_verifier.hpp.

Constructor & Destructor Documentation

◆ BatchMergeVerifier_()

template<typename Curve , size_t MaxMergeSize>

bb::BatchMergeVerifier_< Curve, MaxMergeSize >::BatchMergeVerifier_ ( )

inlineexplicit

Definition at line 62 of file batch_merge_verifier.hpp.

Member Function Documentation

◆ check_concatenation_identity()

template<typename Curve , size_t MaxMergeSize>

bool bb::BatchMergeVerifier_< Curve, MaxMergeSize >::check_concatenation_identity	(	std::vector< FF > &	evals,
		const std::vector< FF > &	pow_kappa_subtable_size
	)		const

private

Verify the concatenation identity T(κ) = Σ_i C_i(κ) · κ^{offset_i} for every column.

offset_i = Σ_{j<i} shift_sizes[j]

Parameters

evals	Evaluations of C_i(κ) and T(κ) received from the proof
pow_kappa_subtable_size	Precomputed κ^{shift_sizes[i]} for each subtable i

Definition at line 289 of file batch_merge_verifier.cpp.

◆ check_degree_identity()

template<typename Curve , size_t MaxMergeSize>

bool bb::BatchMergeVerifier_< Curve, MaxMergeSize >::check_degree_identity	(	std::vector< FF > &	evals,
		const std::vector< FF > &	powers_of_kappa_inv,
		const FF &	kappa,
		const std::vector< FF > &	degree_check_challenges
	)		const

private

Verify the degree identity G(κ⁻¹) = Σ_{i,col} α_{i,col} · C_i_col(κ) · κ^{1 − shift_sizes[j]}.

This is a single combined check across all subtables and columns.

Definition at line 315 of file batch_merge_verifier.cpp.

◆ check_hash_consistency()

template<typename Curve , size_t MaxMergeSize>

bool bb::BatchMergeVerifier_< Curve, MaxMergeSize >::check_hash_consistency	(	const FF &	hash,
		const std::vector< FF > &	calculated_hashes,
		const std::vector< FF > &	indicator_array
	)		const

private

Verify that the column commitments in the proof match the running hash from accumulation.

This ensures that the commitments provided in the proof are consistent with the expected running hash computed during the accumulation process.

Definition at line 376 of file batch_merge_verifier.cpp.

◆ compute_dirac_array()

template<typename Curve , size_t MaxMergeSize>

std::vector< typename BatchMergeVerifier_< Curve, MaxMergeSize >::FF > bb::BatchMergeVerifier_< Curve, MaxMergeSize >::compute_dirac_array ( const std::vector< FF > & indicator_array ) const

private

Compute array of length M := MaxMergeSize s.t. dirac_array[i] = (i == N - 1)

Parameters

indicator_array

Returns: std::vector<FF>

Definition at line 267 of file batch_merge_verifier.cpp.

◆ compute_indicator_array()

template<typename Curve , size_t MaxMergeSize>

std::vector< typename BatchMergeVerifier_< Curve, MaxMergeSize >::FF > bb::BatchMergeVerifier_< Curve, MaxMergeSize >::compute_indicator_array ( const FF & N ) const

private

Compute array of length M := MaxMergeSize s.t. indicator_array[i] = (i < N).

Parameters

N

Returns: std::vector<FF>

Definition at line 242 of file batch_merge_verifier.cpp.

◆ ecc_op_hash_step()

template<typename Curve , size_t MaxMergeSize>

BatchMergeVerifier_< Curve, MaxMergeSize >::FF bb::BatchMergeVerifier_< Curve, MaxMergeSize >::ecc_op_hash_step	(	const std::vector< Commitment > &	col_commitments,
		const std::optional< FF > &	prev_hash = `std::nullopt`
	)

static

Compute one step of the ECC op running hash.

Returns Poseidon2([prev_hash, serialize_to_fields(col_commitments)]).

Definition at line 343 of file batch_merge_verifier.cpp.

◆ reduce_to_pairing_check()

template<typename Curve , size_t MaxMergeSize>

BatchMergeVerifier_< Curve, MaxMergeSize >::ReductionResult bb::BatchMergeVerifier_< Curve, MaxMergeSize >::reduce_to_pairing_check	(	const Proof &	proof,
		const FF	hash
	)

Reduce the batch merge proof to a pairing check.

Parameters

proof	Batch merge proof.
hash	Running hash of the column commitments [C_0]..[C_{M-1}]

Returns: ReductionResult with pairing points and merged table commitments.

Definition at line 15 of file batch_merge_verifier.cpp.

Member Data Documentation

◆ IsRecursive

template<typename Curve , size_t MaxMergeSize>

constexpr bool bb::BatchMergeVerifier_< Curve, MaxMergeSize >::IsRecursive = Curve::is_stdlib_type

staticconstexpr

Definition at line 40 of file batch_merge_verifier.hpp.

◆ LOG_MAX_MERGE_SIZE

template<typename Curve , size_t MaxMergeSize>

constexpr size_t bb::BatchMergeVerifier_< Curve, MaxMergeSize >::LOG_MAX_MERGE_SIZE = static_cast<size_t>(numeric::get_msb(MAX_MERGE_SIZE))

staticconstexpr

Definition at line 39 of file batch_merge_verifier.hpp.

◆ MAX_MERGE_SIZE

template<typename Curve , size_t MaxMergeSize>

constexpr size_t bb::BatchMergeVerifier_< Curve, MaxMergeSize >::MAX_MERGE_SIZE = MaxMergeSize

staticconstexpr

Definition at line 38 of file batch_merge_verifier.hpp.

◆ MERGE_BATCHED_CLAIM_SIZE

template<typename Curve , size_t MaxMergeSize>

constexpr size_t bb::BatchMergeVerifier_< Curve, MaxMergeSize >::MERGE_BATCHED_CLAIM_SIZE = NUM_OPENING_CLAIMS + 2

staticconstexpr

Definition at line 46 of file batch_merge_verifier.hpp.

◆ NUM_COLUMN_TABLES

template<typename Curve , size_t MaxMergeSize>

constexpr size_t bb::BatchMergeVerifier_< Curve, MaxMergeSize >::NUM_COLUMN_TABLES = MAX_MERGE_SIZE + 1

staticconstexpr

Definition at line 41 of file batch_merge_verifier.hpp.

◆ NUM_EVALS

template<typename Curve , size_t MaxMergeSize>

constexpr size_t bb::BatchMergeVerifier_< Curve, MaxMergeSize >::NUM_EVALS

staticconstexpr

Initial value:

=

((MAX_MERGE_SIZE + 2) * NUM_WIRES) + 1

bb::BatchMergeVerifier_::NUM_WIRES

static constexpr size_t NUM_WIRES

Definition batch_merge_verifier.hpp:37

bb::BatchMergeVerifier_::MAX_MERGE_SIZE

static constexpr size_t MAX_MERGE_SIZE

Definition batch_merge_verifier.hpp:38

Definition at line 43 of file batch_merge_verifier.hpp.

◆ NUM_EVALS_FROM_COLUMNS

template<typename Curve , size_t MaxMergeSize>

constexpr size_t bb::BatchMergeVerifier_< Curve, MaxMergeSize >::NUM_EVALS_FROM_COLUMNS = NUM_COLUMN_TABLES * NUM_WIRES

staticconstexpr

Definition at line 42 of file batch_merge_verifier.hpp.

◆ NUM_OPENING_CLAIMS

template<typename Curve , size_t MaxMergeSize>

constexpr size_t bb::BatchMergeVerifier_< Curve, MaxMergeSize >::NUM_OPENING_CLAIMS = NUM_EVALS

staticconstexpr

Definition at line 45 of file batch_merge_verifier.hpp.

◆ NUM_WIRES

template<typename Curve , size_t MaxMergeSize>

constexpr size_t bb::BatchMergeVerifier_< Curve, MaxMergeSize >::NUM_WIRES = MegaExecutionTraceBlocks::NUM_WIRES

staticconstexpr

Definition at line 37 of file batch_merge_verifier.hpp.

◆ transcript

template<typename Curve , size_t MaxMergeSize>

std::shared_ptr<Transcript> bb::BatchMergeVerifier_< Curve, MaxMergeSize >::transcript

Definition at line 60 of file batch_merge_verifier.hpp.

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

src/barretenberg/goblin/batch_merge_verifier.hpp
src/barretenberg/goblin/batch_merge_verifier.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Private Member Functions

Detailed Description

Member Typedef Documentation

◆ Commitment

◆ FF

◆ PairingPoints

◆ PCS

◆ Proof

◆ ShplonkVerifier

◆ TableCommitments

◆ Transcript

Constructor & Destructor Documentation

◆ BatchMergeVerifier_()

Member Function Documentation

◆ check_concatenation_identity()

◆ check_degree_identity()

◆ check_hash_consistency()

◆ compute_dirac_array()

◆ compute_indicator_array()

◆ ecc_op_hash_step()

◆ reduce_to_pairing_check()

Member Data Documentation

◆ IsRecursive

◆ LOG_MAX_MERGE_SIZE

◆ MAX_MERGE_SIZE

◆ MERGE_BATCHED_CLAIM_SIZE

◆ NUM_COLUMN_TABLES

◆ NUM_EVALS

◆ NUM_EVALS_FROM_COLUMNS

◆ NUM_OPENING_CLAIMS

◆ NUM_WIRES

◆ transcript