#include <protogalaxy_recursive_verifier.hpp>

Public Types
using	Flavor = typename VerifierInstance::Flavor

using	FF = typename Flavor::FF

using	Commitment = typename Flavor::Commitment

using	BaseField = typename Commitment::BaseField

using	VKAndHash = typename Flavor::VKAndHash

using	VerifierInstances = std::array< std::shared_ptr< VerifierInstance >, NUM_INSTANCES >

using	Builder = typename Flavor::CircuitBuilder

using	Transcript = StdlibTranscript< Builder >

Public Member Functions
	ProtogalaxyRecursiveVerifier_ (Builder *builder, const std::shared_ptr< VerifierInstance > &accumulator, const std::shared_ptr< VKAndHash > &vk_and_hash, const std::shared_ptr< Transcript > &transcript)

	ProtogalaxyRecursiveVerifier_ (Builder *builder, const std::shared_ptr< VerifierInstance > &accumulator, const std::shared_ptr< VerifierInstance > &incoming_instance, const std::shared_ptr< Transcript > &transcript)

void	run_oink_verifier_on_each_incomplete_instance (const std::vector< FF > &)
	Process the public data \(\phi\) for the verification keys to be folded.

std::shared_ptr< VerifierInstance >	verify_folding_proof (const stdlib::Proof< Builder > &)
	Run the folding protocol on the verifier side to establish whether the public data \(\phi\) of the new accumulator received from the prover is the same as that produced by the verifier.

Public Attributes
Builder *	builder

VerifierInstances	insts_to_fold

std::shared_ptr< Transcript >	transcript = std::make_shared<Transcript>()

Static Public Attributes
static constexpr size_t	EXTENDED_LENGTH = computed_extended_length<Flavor>()

static constexpr size_t	BATCHED_EXTENDED_LENGTH = computed_batched_extended_length<Flavor>()

static constexpr size_t	NUM_SUBRELATIONS = Flavor::NUM_SUBRELATIONS

Private Types
enum class	FOLDING_DATA : std::uint8_t { PRECOMPUTED_COMMITMENTS , WITNESS_COMMITMENTS , ALPHAS , RELATION_PARAMETERS }

Private Member Functions
template<FOLDING_DATA FoldingData>
auto	get_data_to_fold () const
	Get data to be folded grouped by commitment index. Here the "commitment index" is the index of the row in the matrix whose columns are given be the instance components to be folded.

Detailed Description

template<class VerifierInstance>
class bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >

Definition at line 16 of file protogalaxy_recursive_verifier.hpp.

Member Typedef Documentation

◆ BaseField

template<class VerifierInstance >

using bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::BaseField = typename Commitment::BaseField

Definition at line 21 of file protogalaxy_recursive_verifier.hpp.

◆ Builder

template<class VerifierInstance >

using bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::Builder = typename Flavor::CircuitBuilder

Definition at line 25 of file protogalaxy_recursive_verifier.hpp.

◆ Commitment

template<class VerifierInstance >

using bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::Commitment = typename Flavor::Commitment

Definition at line 20 of file protogalaxy_recursive_verifier.hpp.

◆ FF

template<class VerifierInstance >

using bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::FF = typename Flavor::FF

Definition at line 19 of file protogalaxy_recursive_verifier.hpp.

◆ Flavor

template<class VerifierInstance >

using bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::Flavor = typename VerifierInstance::Flavor

Definition at line 18 of file protogalaxy_recursive_verifier.hpp.

◆ Transcript

template<class VerifierInstance >

using bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::Transcript = StdlibTranscript<Builder>

Definition at line 26 of file protogalaxy_recursive_verifier.hpp.

◆ VerifierInstances

template<class VerifierInstance >

using bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::VerifierInstances = std::array<std::shared_ptr<VerifierInstance>, NUM_INSTANCES>

Definition at line 23 of file protogalaxy_recursive_verifier.hpp.

◆ VKAndHash

template<class VerifierInstance >

using bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::VKAndHash = typename Flavor::VKAndHash

Definition at line 22 of file protogalaxy_recursive_verifier.hpp.

Member Enumeration Documentation

◆ FOLDING_DATA

template<class VerifierInstance >

enum class bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_::FOLDING_DATA : std::uint8_t

strongprivate

Enumerator
PRECOMPUTED_COMMITMENTS
WITNESS_COMMITMENTS
ALPHAS
RELATION_PARAMETERS

Definition at line 84 of file protogalaxy_recursive_verifier.hpp.

Constructor & Destructor Documentation

◆ ProtogalaxyRecursiveVerifier_() [1/2]

template<class VerifierInstance >

bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::ProtogalaxyRecursiveVerifier_	(	Builder *	builder,
		const std::shared_ptr< VerifierInstance > &	accumulator,
		const std::shared_ptr< VKAndHash > &	vk_and_hash,
		const std::shared_ptr< Transcript > &	transcript
	)

inline

Definition at line 38 of file protogalaxy_recursive_verifier.hpp.

◆ ProtogalaxyRecursiveVerifier_() [2/2]

template<class VerifierInstance >

bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::ProtogalaxyRecursiveVerifier_	(	Builder *	builder,
		const std::shared_ptr< VerifierInstance > &	accumulator,
		const std::shared_ptr< VerifierInstance > &	incoming_instance,
		const std::shared_ptr< Transcript > &	transcript
	)

inline

Definition at line 49 of file protogalaxy_recursive_verifier.hpp.

Member Function Documentation

◆ get_data_to_fold()

template<class VerifierInstance >

template<FOLDING_DATA FoldingData>

auto bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::get_data_to_fold ( ) const

inlineprivate

Get data to be folded grouped by commitment index. Here the "commitment index" is the index of the row in the matrix whose columns are given be the instance components to be folded.

Template Parameters

FoldingData The type of the parameter to be folded

Definition at line 97 of file protogalaxy_recursive_verifier.hpp.

◆ run_oink_verifier_on_each_incomplete_instance()

template<class VerifierInstance >

void bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::run_oink_verifier_on_each_incomplete_instance ( const std::vector< FF > & proof )

Process the public data \(\phi\) for the verification keys to be folded.

Definition at line 16 of file protogalaxy_recursive_verifier.cpp.

◆ verify_folding_proof()

template<class VerifierInstance >

std::shared_ptr< VerifierInstance > bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::verify_folding_proof ( const stdlib::Proof< Builder > & proof )

Run the folding protocol on the verifier side to establish whether the public data \(\phi\) of the new accumulator received from the prover is the same as that produced by the verifier.

Note: We update the first instance with which the verifier was constructed in-place. That is, the result of the folding verification is stored in insts_to_fold[0] after the execution of this function.; In the recursive setting this function doesn't return anything because the equality checks performed by the recursive verifier, ensuring the folded \(\phi^{\ast}\), \(e^{\ast}\) and \(\beta^{\ast}\) on the verifier side correspond to what has been sent by the prover, are expressed as constraints.

We run the Protogalaxy verifier with parameters k = 1 (we fold one instance/accumulator with an instance) , n = 2^CONST_PG_LOG_N, and d = (Flavor::MAX_TOTAL_RELATION_LENGTH - 1) + 1 (the first term is the maximum of the degrees of the subrelations considering relation parameters as variables, while the second term comes from the batching challenges).

The verifier must compute \phi^{\ast} = L0(\gamma) \phi_0 + L_1(\gamma) \phi_1 = \phi_0 + \gamma * (\phi_1 - \phi_0). This amounts to compute, for each commitment contained in \phi_i, a scalar mul of size 1 and an addition.

The ECCVM handles a size k MSM with scalars of size at most 128 bits in 33 * roundup(k / 4) + 31 rows. Hence, if N is the number of commitments contained in a committed instance \phi_i, performing all the scalar multiplications requires N * (33 + 31) = 64 * N rows.

To optimize the calculation, we make the circuit prover (do not confuse it with the Protogalaxy prover) supply the purported folded commitment, and make the verifier validate those commitments. Write [P_{i,j}] for the commitments contained in \phi_i, and [Q_j] for the commitments supplied by the circuit prover. Then, the Protogalaxy verifier samples random challenges c_1, .., c_N, computes: [A] = \sum_j c_j [P_{0,j}] [B] = \sum_j c_j [P_{1,j}] [C] = \sum_j c_j [Q_j] and then verifies: [C] = (1 - gamma) * [A] + gamma * [B]

The cost of this verification is 3 size N MSMs with short scalars and 1 size 2 MSM with full scalars, amounting to 3 * (33 * roundup(N/4) + 31) + 64 = 99 * roundup(N/4) + 157 ~ 25 * N + 157 rows (here we use that an MSM of size k with full scalars accounts for 33 * roundup(N/2) + 31 rows, which for k = 2 equals 64 rows)

Note: there are more efficient ways to evaluate this relationship if one solely wants to reduce number of scalar muls, however we must also consider the number of ECCVM operations being executed, as each operation incurs a cost in the translator circuit.

Definition at line 41 of file protogalaxy_recursive_verifier.cpp.

Member Data Documentation

◆ BATCHED_EXTENDED_LENGTH

template<class VerifierInstance >

constexpr size_t bb::stdlib::recursion::honk::ProtogalaxyRecursiveVerifier_< VerifierInstance >::BATCHED_EXTENDED_LENGTH = computed_batched_extended_length<Flavor>()

staticconstexpr

Definition at line 29 of file protogalaxy_recursive_verifier.hpp.