merge_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 "merge_verifier.hpp"
#include "barretenberg/commitment_schemes/shplonk/shplonk.hpp"
#include "barretenberg/flavor/mega_zk_flavor.hpp"
#include "barretenberg/flavor/ultra_flavor.hpp"
 
namespace bb {
 
MergeVerifier::MergeVerifier(const MergeSettings settings, const std::shared_ptr<Transcript>& transcript)
    : transcript(transcript)
    , settings(settings) {};
 
std::pair<bool, typename MergeVerifier::TableCommitments> MergeVerifier::verify_proof(
    const HonkProof& proof, const InputCommitments& input_commitments)
{
    using Claims = typename ShplonkVerifier_<Curve>::LinearCombinationOfClaims;
 
    transcript->load_proof(proof);
 
    const uint32_t shift_size = transcript->template receive_from_prover<uint32_t>("shift_size");
    BB_ASSERT_GT(shift_size, 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);
 
    // 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) {
        Claims claim{ { /*index of [l_j]*/ commitment_idx,
                        /*index of [r_j]*/ commitment_idx + 1,
                        /*index of [m_j]*/ commitment_idx + 2 },
                      { FF::one(), pow_kappa, FF::neg_one() },
                      { kappa, FF::zero() } };
        opening_claims.emplace_back(claim);
 
        // Move commitment_idx to the index of [l_{j+1}]
        commitment_idx += NUM_WIRES;
    }
 
    // Boolean keeping track of the degree identities
    bool degree_check_verified = true;
 
    // 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) {
        Claims claim;
 
        // 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));
        claim = { { commitment_idx }, { FF::one() }, { kappa_inv, left_table_eval_kappa_inv } };
        opening_claims.emplace_back(claim);
 
        // Move commitment_idx to index of g_j
        commitment_idx += 3;
 
        // 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));
        claim = { { commitment_idx }, { FF::one() }, { kappa, left_table_reversed_eval } };
        opening_claims.emplace_back(claim);
 
        // Move commitment_idx to index of left_table_{j+1}
        commitment_idx += 1;
 
        // Degree identity
        degree_check_verified &= (left_table_eval_kappa_inv * kappa.pow(shift_size - 1) == left_table_reversed_eval);
    }
 
    // 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());
 
    // KZG verifier
    auto pairing_points = PCS::reduce_verify_batch_opening_claim(batch_opening_claim, transcript);
    VerifierCommitmentKey pcs_vkey{};
    bool claims_verified = pcs_vkey.pairing_check(pairing_points[0], pairing_points[1]);
 
    return { degree_check_verified && claims_verified, merged_table_commitments };
}
} // namespace bb