Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
Classes | Public Types | Public Member Functions | Public Attributes | Static Public Attributes | List of all members
bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder > Class Template Reference

#include <merge_recursive_verifier.hpp>

Classes

struct  InputCommitments
 

Public Types

using Curve = bn254< CircuitBuilder >
 
using FF = typename Curve::ScalarField
 
using Commitment = typename Curve::Element
 
using GroupElement = typename Curve::Element
 
using KZG = ::bb::KZG< Curve >
 
using Transcript = bb::BaseTranscript< bb::stdlib::recursion::honk::StdlibTranscriptParams< CircuitBuilder > >
 
using PairingPoints = stdlib::recursion::PairingPoints< CircuitBuilder >
 
using TableCommitments = std::array< Commitment, NUM_WIRES >
 

Public Member Functions

 MergeRecursiveVerifier_ (CircuitBuilder *builder, const MergeSettings settings=MergeSettings::PREPEND, const std::shared_ptr< Transcript > &transcript=std::make_shared< Transcript >())
 
std::pair< PairingPoints, TableCommitments > verify_proof (const stdlib::Proof< CircuitBuilder > &proof, const InputCommitments &input_commitments)
 Computes inputs to a pairing check that, if verified, establishes proper construction of the aggregate Goblin ECC op queue polynomials T_j, j = 1,2,3,4.
 

Public Attributes

CircuitBuilder * builder
 
std::shared_ptr< Transcript > transcript
 
MergeSettings settings
 

Static Public Attributes

static constexpr size_t NUM_WIRES = MegaExecutionTraceBlocks::NUM_WIRES
 

Detailed Description

template<typename CircuitBuilder>
class bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >

Definition at line 16 of file merge_recursive_verifier.hpp.

Member Typedef Documentation

◆ Commitment

template<typename CircuitBuilder >
using bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::Commitment = typename Curve::Element

Definition at line 20 of file merge_recursive_verifier.hpp.

◆ Curve

template<typename CircuitBuilder >
using bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::Curve = bn254<CircuitBuilder>

Definition at line 18 of file merge_recursive_verifier.hpp.

◆ FF

template<typename CircuitBuilder >
using bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::FF = typename Curve::ScalarField

Definition at line 19 of file merge_recursive_verifier.hpp.

◆ GroupElement

template<typename CircuitBuilder >
using bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::GroupElement = typename Curve::Element

Definition at line 21 of file merge_recursive_verifier.hpp.

◆ KZG

template<typename CircuitBuilder >
using bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::KZG = ::bb::KZG<Curve>

Definition at line 22 of file merge_recursive_verifier.hpp.

◆ PairingPoints

template<typename CircuitBuilder >
using bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::PairingPoints = stdlib::recursion::PairingPoints<CircuitBuilder>

Definition at line 24 of file merge_recursive_verifier.hpp.

◆ TableCommitments

template<typename CircuitBuilder >
using bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::TableCommitments = std::array<Commitment, NUM_WIRES>

Definition at line 33 of file merge_recursive_verifier.hpp.

◆ Transcript

template<typename CircuitBuilder >
using bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::Transcript = bb::BaseTranscript<bb::stdlib::recursion::honk::StdlibTranscriptParams<CircuitBuilder> >

Definition at line 23 of file merge_recursive_verifier.hpp.

Constructor & Destructor Documentation

◆ MergeRecursiveVerifier_()

template<typename CircuitBuilder >
bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::MergeRecursiveVerifier_ ( CircuitBuilder *  builder,
const MergeSettings  settings = MergeSettings::PREPEND,
const std::shared_ptr< Transcript > &  transcript = std::make_shared<Transcript>() 
)
explicit

Definition at line 13 of file merge_recursive_verifier.cpp.

Member Function Documentation

◆ verify_proof()

template<typename CircuitBuilder >
std::pair< typename MergeRecursiveVerifier_< CircuitBuilder >::PairingPoints, typename MergeRecursiveVerifier_< CircuitBuilder >::TableCommitments > bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::verify_proof ( const stdlib::Proof< CircuitBuilder > &  proof,
const InputCommitments &  input_commitments 
)

Computes inputs to a pairing check that, if verified, establishes proper construction of the aggregate Goblin ECC op queue polynomials T_j, j = 1,2,3,4.

Let \(l_j\), \(r_j\), \(m_j\) be three vectors. The Merge wants to convince the verifier that the polynomials l_j, r_j, m_j for which they have sent commitments [l_j], [r_j], [m_j] satisfy

  • m_j(X) = l_j(X) + X^l r_j(X) (1)
  • deg(l_j(X)) < k (2) where k = shift_size.

To check condition (1), the verifier samples a challenge kappa and request from the prover a proof that the polynomial p_j(X) = l_j(kappa) + kappa^k r_j(kappa) - m_j(kappa) opens to 0 at kappa.

To check condition (2), the verifier requests from the prover the commitment to a polynomial g_j, and then requests proofs that l_j(1/kappa) = c g_j(kappa) = d Then, they verify c * kappa^{k-1} = d, which implies, up to negligible probability, that g_j(X) = X^{l-1} l_j(1/X), which means that deg(l_j(X)) < l.

The verifier must therefore check 12 opening claims: p_j(kappa) = 0, l_j(1/kappa), g_j(kappa) We use Shplonk to verify the claims with a single MSM (instead of computing [p_j] from [l_j], [r_j], [m_j] and then open it). We initialize the Shplonk verifier with the following commitments: [l_1], [r_1], [m_1], [g_1], ..., [l_4], [r_4], [m_4], [g_4] Then, we verify the various claims:

  • p_j(kappa) = 0: The commitment to p_j is constructed from the commitments to l_j, r_j, m_j, so the claim passed to the Shplonk verifier specifies the indices of these commitments in the above vector: {4 * (j-1), 4 * (j-1) + 1, 4 * (j-1) + 2}, the coefficients reconstructing p_j from l_j, r_j, m_j: {1, kappa^k, -1}, and the claimed evaluation: 0.
  • l_j(1/kappa) = v_j: The index in this case is {4 * (j-1)}, the coefficient is { 1 }, and the evaluation is v_j.
  • g_j(kappa) = w_j: The index is {3 + 4 * (j-1)}, the coefficient is { 1 }, and the evaluation is w_j. The claims are passed in the following order: {kappa, 0}, {kappa, 0}, {kappa, 0}, {kappa, 0}, {1/kappa, v_1}, {kappa, w_1}, .., {1/kappa, v_4}, {kappa, w_4}

In the Goblin scenario, we have:

  • \(l_j = t_j, r_j = T_{prev,j}, m_j = T_j\) if we are prepending the subtable
  • \(l_j = T_{prev,j}, r_j = t_j, m_j = T_j\) if we are appending the subtable
Template Parameters
CircuitBuilder
Parameters
proof
inputs_commitmentsThe commitments used by the Merge verifier
Returns
std::pair<PairingPoints, TableCommitments> Pair of the pairing inputs for final verification and the commitments to the merged tables as read from the proof

Definition at line 70 of file merge_recursive_verifier.cpp.

Member Data Documentation

◆ builder

template<typename CircuitBuilder >
CircuitBuilder* bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::builder

Definition at line 26 of file merge_recursive_verifier.hpp.

◆ NUM_WIRES

template<typename CircuitBuilder >
constexpr size_t bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::NUM_WIRES = MegaExecutionTraceBlocks::NUM_WIRES
staticconstexpr

Definition at line 32 of file merge_recursive_verifier.hpp.

◆ settings

template<typename CircuitBuilder >
MergeSettings bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::settings

Definition at line 28 of file merge_recursive_verifier.hpp.

◆ transcript

template<typename CircuitBuilder >
std::shared_ptr<Transcript> bb::stdlib::recursion::goblin::MergeRecursiveVerifier_< CircuitBuilder >::transcript

Definition at line 27 of file merge_recursive_verifier.hpp.

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