Shplonk Verifier. More...

#include <shplonk.hpp>

Public Member Functions
	ShplonkVerifier_ (const std::vector< Commitment > &polynomial_commitments, const Commitment &quotient_commitment, const Fr &nu_challenge, const Fr &partial_evaluation_challenge)

template<typename Transcript >
	ShplonkVerifier_ (const std::vector< Commitment > &polynomial_commitments, std::shared_ptr< Transcript > &transcript, const size_t num_claims)

OpeningClaim< Curve >	finalize (const Commitment &g1_identity)
	Finalize the Shplonk verification and return the KZG opening claim.

BatchOpeningClaim< Curve >	export_batch_opening_claim (const Commitment &g1_identity)
	Export a BatchOpeningClaim instead of performing final batch_mul.

Static Public Member Functions
template<typename Transcript >
static ShplonkVerifier_< Curve >	reduce_verification_no_finalize (std::span< const OpeningClaim< Curve > > claims, std::shared_ptr< Transcript > &transcript)
	Instantiate a Shplonk verifier and update its state with the provided claims.

static OpeningClaim< Curve >	compute_partially_evaluated_quotient_claim (const Commitment &g1_identity, std::span< const OpeningClaim< Curve > > claims, const Commitment &quotient_commitment, const Fr &nu_challenge, const Fr &partial_evaluation_challenge)

template<typename Transcript >
static OpeningClaim< Curve >	reduce_verification (Commitment g1_identity, std::span< const OpeningClaim< Curve > > claims, std::shared_ptr< Transcript > &transcript)
	Recomputes the new claim commitment [G] given the proof and the challenge r. No verification happens so this function always succeeds.

static std::vector< Fr >	compute_inverted_gemini_denominators (const Fr &shplonk_eval_challenge, const std::vector< Fr > &gemini_eval_challenge_powers)
	Computes \( \frac{1}{z - r}, \frac{1}{z + r}, \ldots, \frac{1}{z - r^{2^{d-1}}}, \frac{1}{z + r^{2^{d-1}}} \).

Private Types
using	Fr = typename Curve::ScalarField

using	GroupElement = typename Curve::Element

using	Commitment = typename Curve::AffineElement

using	VK = VerifierCommitmentKey< Curve >

Private Member Functions
void	initialize (const std::vector< Commitment > &polynomial_commitments)

void	accumulate_claims (std::span< const OpeningClaim< Curve > > claims)

Private Attributes
std::vector< Fr >	pows_of_nu

Commitment	quotient

Fr	z_challenge

std::vector< Commitment >	commitments

std::vector< Fr >	scalars

Fr	identity_scalar_coefficient = Fr(0)

Fr	evaluation = Fr(0)

bool	consumed_ = false

Detailed Description

template<typename Curve>
class bb::ShplonkVerifier_< Curve >

Shplonk Verifier.

Given commitments to polynomials \([p_1], \dots, [p_m]\) and couples of challenge/evaluation \((x_i, v_i)\), the Shplonk verifier computes the following commitment:

\[ [G] := [Q] - \sum_{i=1}^m \frac{\nu^{i-1} [p_i]}{(z - x_i)} + \sum_{i=1}^m \frac{\nu^{i-1} v_i}{(z - x_i)} [1] \]

where \(\nu\) is a random batching challenge, \([Q]\) is the commiment to the quotient polymomial

\[ \sum_{i=1}^m \nu^{i-1} \frac{(p_i - v_i)}{(x - x_i)} \]

and \(z\) is the evaluation challenge.

When the polynomials \(p_1, \dots, p_m\) are linearly dependent, and the verifier which calls the Shplonk verifier needs to compute the commitments \([p_1], \dots, [p_m]\) starting from the linearly independent factors, computing the commitments and then executing the Shplonk verifier is not the most efficient way to execute the Shplonk verifier algorithm.

Consider the case \(m = 2\), and take \(p_2 = a p_1\) for some constant \(a \in \mathbb{F}\). Then, the most efficient way to execute the Shplonk verifier algorithm is to compute the following MSM

\[ [Q] - \left( \frac{1}{(z - x_1)} \ + \frac{a \nu}{(z - x_2)} \right) [p_1] \ + \left( \frac{v_1}{(z - x_1)} + \frac{v_2 \nu}{(z - x_2)} \right) [1] \]

The Shplonk verifier api is designed to allow the execution of the Shplonk verifier algorithm in its most efficient form. To achieve this, the Shplonk verifier maintains an internal state depending of the following variables:

\([f_1], \dots, [f_n]\) (commitments in code) the commitments to the linearly independent polynomials such that for each polynomial \(p_i\) we wish to open it holds \(p_i = \sum_{i=1}^n p_{i,j} f_j\) for some \(p_j \in \mathbb{F}\).
\(\nu\) (nu in code) the challenge used to batch the polynomial commitments.
\(\nu^{i}\) (current_nu in code), which is the power of the batching challenge used to batch the \(i\)-th polynomial \( p_i \) in the Shplonk verifier algorithm.
\([Q]\) (quotient in code).
\(z\) (z_challenge in code), the partial evaluation challenge.
\((s_1, \dots, s_n)\) (scalars in code), the coefficient of \([f_i]\) in the Shplonk verifier MSM.
\(\theta\) (identity_scalar_coefficient in code), the coefficient of \([1]\) in the Shplonk verifier MSM.
evaluation, the claimed evaluation at \(z\) of the commitment produced by the Shplonk verifier, always equal to \(0\).

Definition at line 367 of file shplonk.hpp.

Member Typedef Documentation

◆ Commitment

template<typename Curve >

using bb::ShplonkVerifier_< Curve >::Commitment = typename Curve::AffineElement

private

Definition at line 370 of file shplonk.hpp.

◆ Fr

template<typename Curve >

using bb::ShplonkVerifier_< Curve >::Fr = typename Curve::ScalarField

private

Definition at line 368 of file shplonk.hpp.

◆ GroupElement

template<typename Curve >

using bb::ShplonkVerifier_< Curve >::GroupElement = typename Curve::Element

private

Definition at line 369 of file shplonk.hpp.

◆ VK

template<typename Curve >

using bb::ShplonkVerifier_< Curve >::VK = VerifierCommitmentKey<Curve>

private

Definition at line 371 of file shplonk.hpp.

Constructor & Destructor Documentation

◆ ShplonkVerifier_() [1/2]

template<typename Curve >

bb::ShplonkVerifier_< Curve >::ShplonkVerifier_	(	const std::vector< Commitment > &	polynomial_commitments,
		const Commitment &	quotient_commitment,
		const Fr &	nu_challenge,
		const Fr &	partial_evaluation_challenge
	)

inline

Definition at line 395 of file shplonk.hpp.

◆ ShplonkVerifier_() [2/2]

template<typename Curve >

template<typename Transcript >

bb::ShplonkVerifier_< Curve >::ShplonkVerifier_	(	const std::vector< Commitment > &	polynomial_commitments,
		std::shared_ptr< Transcript > &	transcript,
		const size_t	num_claims
	)

inline

Definition at line 409 of file shplonk.hpp.

Member Function Documentation

◆ accumulate_claims()

template<typename Curve >

void bb::ShplonkVerifier_< Curve >::accumulate_claims ( std::span< const OpeningClaim< Curve > > claims )

inlineprivate

Definition at line 446 of file shplonk.hpp.

◆ compute_inverted_gemini_denominators()

template<typename Curve >

static std::vector< Fr > bb::ShplonkVerifier_< Curve >::compute_inverted_gemini_denominators	(	const Fr &	shplonk_eval_challenge,
		const std::vector< Fr > &	gemini_eval_challenge_powers
	)

inlinestatic

Computes \( \frac{1}{z - r}, \frac{1}{z + r}, \ldots, \frac{1}{z - r^{2^{d-1}}}, \frac{1}{z + r^{2^{d-1}}} \).

Parameters

shplonk_eval_challenge	\( z \)
gemini_eval_challenge_powers	\( (r , r^2, \ldots, r^{2^{d-1}}) \)

Returns: \[ \left( \frac{1}{z - r}, \frac{1}{z + r}, \ldots, \frac{1}{z - r^{2^{d-1}}}, \frac{1}{z + r^{2^{d-1}}} \right) \]

Definition at line 592 of file shplonk.hpp.

◆ compute_partially_evaluated_quotient_claim()

template<typename Curve >

static OpeningClaim< Curve > bb::ShplonkVerifier_< Curve >::compute_partially_evaluated_quotient_claim	(	const Commitment &	g1_identity,
		std::span< const OpeningClaim< Curve > >	claims,
		const Commitment &	quotient_commitment,
		const Fr &	nu_challenge,
		const Fr &	partial_evaluation_challenge
	)

inlinestatic

Definition at line 547 of file shplonk.hpp.

◆ export_batch_opening_claim()

template<typename Curve >

BatchOpeningClaim< Curve > bb::ShplonkVerifier_< Curve >::export_batch_opening_claim ( const Commitment & g1_identity )

inline

Export a BatchOpeningClaim instead of performing final batch_mul.

Append g1_identity to commitments, identity_scalar_factor to scalars, and export the resulting vectors. This method is useful when we perform KZG verification of the Shplonk claim right after Shplonk (because we can add the last commitment \([W]\) and scalar factor (0 in this case) to the list and then execute a single batch mul.

Note: This function modifies the commitments and scalars attribute of the class instance on which it is called.

Parameters

g1_identity

Returns: BatchOpeningClaim<Curve>

Definition at line 511 of file shplonk.hpp.

◆ finalize()

template<typename Curve >

OpeningClaim< Curve > bb::ShplonkVerifier_< Curve >::finalize ( const Commitment & g1_identity )

inline

Finalize the Shplonk verification and return the KZG opening claim.

Compute the commitment:

\[ [Q] - \sum_i s_i * [f_i] + \theta * [1] \]

Parameters

g1_identity

Returns: OpeningClaim<Curve>

Definition at line 483 of file shplonk.hpp.

◆ initialize()

template<typename Curve >

void bb::ShplonkVerifier_< Curve >::initialize ( const std::vector< Commitment > & polynomial_commitments )

inlineprivate

Definition at line 423 of file shplonk.hpp.

◆ reduce_verification()

template<typename Curve >

template<typename Transcript >

static OpeningClaim< Curve > bb::ShplonkVerifier_< Curve >::reduce_verification	(	Commitment	g1_identity,
		std::span< const OpeningClaim< Curve > >	claims,
		std::shared_ptr< Transcript > &	transcript
	)

inlinestatic

Recomputes the new claim commitment [G] given the proof and the challenge r. No verification happens so this function always succeeds.

Parameters

g1_identity	the identity element for the Curve
claims	list of opening claims \((C_j, x_j, v_j)\) for a witness polynomial \(f_j(X)\), s.t. \(f_j(x_j) = v_j\).
transcript

Returns: OpeningClaim

Definition at line 575 of file shplonk.hpp.

◆ reduce_verification_no_finalize()

template<typename Curve >

template<typename Transcript >

static ShplonkVerifier_< Curve > bb::ShplonkVerifier_< Curve >::reduce_verification_no_finalize	(	std::span< const OpeningClaim< Curve > >	claims,
		std::shared_ptr< Transcript > &	transcript
	)

inlinestatic

Instantiate a Shplonk verifier and update its state with the provided claims.

Parameters

claims	List of opening claims \((C_j, x_j, v_j)\) for a witness polynomial \(f_j(X)\), s.t. \(f_j(x_j) = v_j\).
transcript

Definition at line 531 of file shplonk.hpp.

Member Data Documentation

◆ commitments

template<typename Curve >

std::vector<Commitment> bb::ShplonkVerifier_< Curve >::commitments

private

Definition at line 381 of file shplonk.hpp.

◆ consumed_

template<typename Curve >

bool bb::ShplonkVerifier_< Curve >::consumed_ = false

private

Definition at line 392 of file shplonk.hpp.

◆ evaluation

template<typename Curve >

Fr bb::ShplonkVerifier_< Curve >::evaluation = Fr(0)

private

Definition at line 389 of file shplonk.hpp.

◆ identity_scalar_coefficient

template<typename Curve >

Fr bb::ShplonkVerifier_< Curve >::identity_scalar_coefficient = Fr(0)

private

Definition at line 387 of file shplonk.hpp.

◆ pows_of_nu

template<typename Curve >

std::vector<Fr> bb::ShplonkVerifier_< Curve >::pows_of_nu

private

Definition at line 374 of file shplonk.hpp.

◆ quotient

template<typename Curve >

Commitment bb::ShplonkVerifier_< Curve >::quotient

private

Definition at line 376 of file shplonk.hpp.

◆ scalars

template<typename Curve >

std::vector<Fr> bb::ShplonkVerifier_< Curve >::scalars

private

Definition at line 385 of file shplonk.hpp.

◆ z_challenge

template<typename Curve >

Fr bb::ShplonkVerifier_< Curve >::z_challenge

private

Definition at line 378 of file shplonk.hpp.

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

src/barretenberg/commitment_schemes/shplonk/shplonk.hpp

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ Commitment

◆ Fr

◆ GroupElement

◆ VK

Constructor & Destructor Documentation

◆ ShplonkVerifier_() [1/2]

◆ ShplonkVerifier_() [2/2]

Member Function Documentation

◆ accumulate_claims()

◆ compute_inverted_gemini_denominators()

◆ compute_partially_evaluated_quotient_claim()

◆ export_batch_opening_claim()

◆ finalize()

◆ initialize()

◆ reduce_verification()

◆ reduce_verification_no_finalize()

Member Data Documentation

◆ commitments

◆ consumed_

◆ evaluation

◆ identity_scalar_coefficient

◆ pows_of_nu

◆ quotient

◆ scalars

◆ z_challenge