Shplonk Verifier. More...

#include <shplonk.hpp>

Public Member Functions
template<typename Transcript >
	ShplonkVerifier_ (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.

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 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)

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 343 of file shplonk.hpp.

Member Typedef Documentation

◆ Commitment

template<typename Curve >

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

private

Definition at line 346 of file shplonk.hpp.

◆ Fr

template<typename Curve >

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

private

Definition at line 344 of file shplonk.hpp.

◆ GroupElement

template<typename Curve >

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

private

Definition at line 345 of file shplonk.hpp.

◆ VK

template<typename Curve >

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

private

Definition at line 347 of file shplonk.hpp.

Constructor & Destructor Documentation

◆ ShplonkVerifier_()

template<typename Curve >

template<typename Transcript >

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

inline

Definition at line 367 of file shplonk.hpp.

Member Function Documentation

◆ 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 516 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 432 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 403 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 499 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 448 of file shplonk.hpp.

Member Data Documentation

◆ commitments

template<typename Curve >

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

private

Definition at line 356 of file shplonk.hpp.

◆ evaluation

template<typename Curve >

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

private

Definition at line 363 of file shplonk.hpp.

◆ identity_scalar_coefficient

template<typename Curve >

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

private

Definition at line 361 of file shplonk.hpp.

◆ pows_of_nu

template<typename Curve >

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

private

Definition at line 350 of file shplonk.hpp.

◆ quotient

template<typename Curve >

Commitment bb::ShplonkVerifier_< Curve >::quotient

private

Definition at line 352 of file shplonk.hpp.

◆ scalars

template<typename Curve >

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

private

Definition at line 359 of file shplonk.hpp.

◆ z_challenge

template<typename Curve >

Fr bb::ShplonkVerifier_< Curve >::z_challenge

private

Definition at line 354 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 Attributes

Detailed Description

Member Typedef Documentation

◆ Commitment

◆ Fr

◆ GroupElement

◆ VK

Constructor & Destructor Documentation

◆ ShplonkVerifier_()

Member Function Documentation

◆ compute_inverted_gemini_denominators()

◆ export_batch_opening_claim()

◆ finalize()

◆ reduce_verification()

◆ reduce_verification_no_finalize()

Member Data Documentation

◆ commitments

◆ evaluation

◆ identity_scalar_coefficient

◆ pows_of_nu

◆ quotient

◆ scalars

◆ z_challenge