merge_recursive_verifier.cpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: not started, auditors: [], date: YYYY-MM-DD }
// external_1:  { status: not started, auditors: [], date: YYYY-MM-DD }
// external_2:  { status: not started, auditors: [], date: YYYY-MM-DD }
// =====================
 
#include "barretenberg/stdlib/merge_verifier/merge_recursive_verifier.hpp"
#include "barretenberg/commitment_schemes/shplonk/shplonk.hpp"
 
namespace bb::stdlib::recursion::goblin {
 
template <typename CircuitBuilder>
MergeRecursiveVerifier_<CircuitBuilder>::MergeRecursiveVerifier_(CircuitBuilder* builder,
                                                                 const MergeSettings settings,
                                                                 const std::shared_ptr<Transcript>& transcript)
    : builder(builder)
    , transcript(transcript)
    , settings(settings)
{}
 
template <typename CircuitBuilder>
std::pair<typename MergeRecursiveVerifier_<CircuitBuilder>::PairingPoints,
          typename MergeRecursiveVerifier_<CircuitBuilder>::TableCommitments>
MergeRecursiveVerifier_<CircuitBuilder>::verify_proof(const stdlib::Proof<CircuitBuilder>& proof,
                                                      const InputCommitments& input_commitments)
{
    using Claims = typename ShplonkVerifier_<Curve>::LinearCombinationOfClaims;
 
    transcript->load_proof(proof);
 
    FF shift_size = transcript->template receive_from_prover<FF>("shift_size");
    BB_ASSERT_GT(shift_size.get_value(), 0U, "Shift size should always be bigger than 0");
 
    // Vector of commitments to be passed to the Shplonk verifier
    // The vector is composed of: [l_1], [r_1], [m_1], [g_1], ..., [l_4], [r_4], [m_4], [g_4]
    std::vector<Commitment> table_commitments;
    for (size_t idx = 0; idx < NUM_WIRES; ++idx) {
        auto left_table = settings == MergeSettings::PREPEND ? input_commitments.t_commitments[idx]
                                                             : input_commitments.T_prev_commitments[idx];
        auto right_table = settings == MergeSettings::PREPEND ? input_commitments.T_prev_commitments[idx]
                                                              : input_commitments.t_commitments[idx];
 
        table_commitments.emplace_back(left_table);
        table_commitments.emplace_back(right_table);
        table_commitments.emplace_back(
            transcript->template receive_from_prover<Commitment>("MERGED_TABLE_" + std::to_string(idx)));
        table_commitments.emplace_back(
            transcript->template receive_from_prover<Commitment>("LEFT_TABLE_REVERSED_" + std::to_string(idx)));
    }
 
    // Store T_commitments of the verifier
    TableCommitments merged_table_commitments;
    size_t commitment_idx = 2; // Index of [m_j = T_j] in the vector of commitments
    for (auto& commitment : merged_table_commitments) {
        commitment = table_commitments[commitment_idx];
        commitment_idx += NUM_WIRES;
    }
 
    // Evaluation challenge
    const FF kappa = transcript->template get_challenge<FF>("kappa");
    const FF kappa_inv = kappa.invert();
    const FF pow_kappa = kappa.pow(shift_size);
    const FF pow_kappa_minus_one = pow_kappa * kappa_inv;
 
    // Opening claims to be passed to the Shplonk verifier
    std::vector<Claims> opening_claims;
 
    // Add opening claim for p_j(X) = l_j(X) + X^k r_j(X) - m_j(X)
    commitment_idx = 0;
    for (size_t idx = 0; idx < NUM_WIRES; ++idx) {
        opening_claims.emplace_back(Claims{ { /*index of [l_j]*/ commitment_idx,
                                              /*index of [r_j]*/ commitment_idx + 1,
                                              /*index of [m_j]*/ commitment_idx + 2 },
                                            { FF(1), pow_kappa, FF(-1) },
                                            { kappa, FF(0) } });
 
        // Move commitment_idx to the index of [l_{j+1}]
        commitment_idx += NUM_WIRES;
    }
 
    // Add opening claim for l_j(1/kappa), g_j(kappa) and check g_j(kappa) = l_j(1/kappa) * kappa^{k-1}
    commitment_idx = 0;
    for (size_t idx = 0; idx < NUM_WIRES; ++idx) {
        // Opening claim for l_j(1/kappa)
        FF left_table_eval_kappa_inv =
            transcript->template receive_from_prover<FF>("left_table_eval_kappa_inv_" + std::to_string(idx));
        opening_claims.emplace_back(
            Claims{ { /*index of [l_j]*/ commitment_idx }, { FF(1) }, { kappa_inv, left_table_eval_kappa_inv } });
 
        // Opening claim for g_j(kappa)
        FF left_table_reversed_eval =
            transcript->template receive_from_prover<FF>("left_table_reversed_eval_" + std::to_string(idx));
        opening_claims.emplace_back(
            Claims{ { /*index of [g_j]*/ commitment_idx + 3 }, { FF(1) }, { kappa, left_table_reversed_eval } });
 
        // Move commitment_idx to index of left_table_{j+1}
        commitment_idx += NUM_WIRES;
 
        // Degree identity
        left_table_reversed_eval.assert_equal(left_table_eval_kappa_inv * pow_kappa_minus_one);
    }
 
    // Initialize Shplonk verifier
    ShplonkVerifier_<Curve> verifier(table_commitments, transcript, opening_claims.size());
    verifier.reduce_verification_vector_claims_no_finalize(opening_claims);
 
    // Export batched claim
    auto batch_opening_claim = verifier.export_batch_opening_claim(Commitment::one(kappa.get_context()));
 
    // KZG verifier
    auto pairing_points = KZG::reduce_verify_batch_opening_claim(batch_opening_claim, transcript);
 
    return { pairing_points, merged_table_commitments };
}
 
template class MergeRecursiveVerifier_<MegaCircuitBuilder>;
template class MergeRecursiveVerifier_<UltraCircuitBuilder>;
 
} // namespace bb::stdlib::recursion::goblin