pg_recursion_constraint.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 "pg_recursion_constraint.hpp"
#include "barretenberg/common/assert.hpp"
#include "barretenberg/common/throw_or_abort.hpp"
#include "barretenberg/dsl/acir_format/mock_verifier_inputs.hpp"
#include "barretenberg/flavor/flavor.hpp"
#include "barretenberg/flavor/ultra_recursive_flavor.hpp"
#include "barretenberg/flavor/ultra_rollup_recursive_flavor.hpp"
#include "barretenberg/stdlib/honk_verifier/ultra_recursive_verifier.hpp"
#include "barretenberg/stdlib/primitives/bigfield/constants.hpp"
#include "barretenberg/stdlib/primitives/curves/bn254.hpp"
#include "barretenberg/stdlib/primitives/pairing_points.hpp"
#include "proof_surgeon.hpp"
#include "recursion_constraint.hpp"
 
namespace acir_format {
 
using namespace bb;
 
std::shared_ptr<ClientIVC> create_mock_ivc_from_constraints(const std::vector<RecursionConstraint>& constraints,
                                                            const TraceSettings& trace_settings)
{
    auto ivc = std::make_shared<ClientIVC>(constraints.size(), trace_settings);
 
    uint32_t oink_type = static_cast<uint32_t>(PROOF_TYPE::OINK);
    uint32_t pg_type = static_cast<uint32_t>(PROOF_TYPE::PG);
    uint32_t pg_final_type = static_cast<uint32_t>(PROOF_TYPE::PG_FINAL);
    uint32_t pg_tail_type = static_cast<uint32_t>(PROOF_TYPE::PG_TAIL);
 
    // There is a fixed set of valid combinations of IVC recursion constraints for Aztec kernel circuits:
 
    // Case: INIT kernel; single Oink recursive verification of an app
    if (constraints.size() == 1 && constraints[0].proof_type == oink_type) {
        mock_ivc_accumulation(ivc, ClientIVC::QUEUE_TYPE::OINK, /*is_kernel=*/false);
        return ivc;
    }
 
    // Case: RESET kernel; single PG recursive verification of a kernel
    if (constraints.size() == 1 && constraints[0].proof_type == pg_type) {
        ivc->recursive_verifier_native_accum = create_mock_verifier_instance<ClientIVC::Flavor>();
        mock_ivc_accumulation(ivc, ClientIVC::QUEUE_TYPE::PG, /*is_kernel=*/true);
        return ivc;
    }
 
    // Case: TAIL kernel; single PG recursive verification of a kernel
    if (constraints.size() == 1 && constraints[0].proof_type == pg_tail_type) {
        ivc->recursive_verifier_native_accum = create_mock_verifier_instance<ClientIVC::Flavor>();
        mock_ivc_accumulation(ivc, ClientIVC::QUEUE_TYPE::PG_TAIL, /*is_kernel=*/true);
        return ivc;
    }
 
    // Case: INNER kernel; two PG recursive verifications, kernel and app in that order
    if (constraints.size() == 2) {
        BB_ASSERT_EQ(constraints[0].proof_type, pg_type);
        BB_ASSERT_EQ(constraints[1].proof_type, pg_type);
        ivc->recursive_verifier_native_accum = create_mock_verifier_instance<ClientIVC::Flavor>();
        mock_ivc_accumulation(ivc, ClientIVC::QUEUE_TYPE::PG, /*is_kernel=*/true);
        mock_ivc_accumulation(ivc, ClientIVC::QUEUE_TYPE::PG, /*is_kernel=*/false);
        return ivc;
    }
 
    // Case: HIDING kernel; single PG_FINAL recursive verification of a kernel
    if (constraints.size() == 1 && constraints[0].proof_type == pg_final_type) {
        ivc->recursive_verifier_native_accum = create_mock_verifier_instance<ClientIVC::Flavor>();
        mock_ivc_accumulation(ivc, ClientIVC::QUEUE_TYPE::PG_FINAL, /*is_kernel=*/true);
        return ivc;
    }
 
    throw_or_abort("Invalid set of IVC recursion constraints!");
    return ivc;
}
 
std::shared_ptr<SumcheckClientIVC> create_mock_sumcheck_ivc_from_constraints(
    const std::vector<RecursionConstraint>& constraints)
{
    auto ivc = std::make_shared<SumcheckClientIVC>(constraints.size());
 
    uint32_t oink_type = static_cast<uint32_t>(PROOF_TYPE::OINK);
    uint32_t pg_type = static_cast<uint32_t>(PROOF_TYPE::PG);
    uint32_t pg_final_type = static_cast<uint32_t>(PROOF_TYPE::PG_FINAL);
    uint32_t pg_tail_type = static_cast<uint32_t>(PROOF_TYPE::PG_TAIL);
 
    // There is a fixed set of valid combinations of IVC recursion constraints for Aztec kernel circuits:
 
    // Case: INIT kernel; single Oink recursive verification of an app
    if (constraints.size() == 1 && constraints[0].proof_type == oink_type) {
        mock_sumcheck_ivc_accumulation(ivc, SumcheckClientIVC::QUEUE_TYPE::OINK, /*is_kernel=*/false);
        return ivc;
    }
 
    // Case: RESET kernel; single PG recursive verification of a kernel
    if (constraints.size() == 1 && constraints[0].proof_type == pg_type) {
        mock_sumcheck_ivc_accumulation(ivc, SumcheckClientIVC::QUEUE_TYPE::PG, /*is_kernel=*/true);
        return ivc;
    }
 
    // Case: TAIL kernel; single PG recursive verification of a kernel
    if (constraints.size() == 1 && constraints[0].proof_type == pg_tail_type) {
        mock_sumcheck_ivc_accumulation(ivc, SumcheckClientIVC::QUEUE_TYPE::PG_TAIL, /*is_kernel=*/true);
        return ivc;
    }
 
    // Case: INNER kernel; two PG recursive verifications, kernel and app in that order
    if (constraints.size() == 2) {
        BB_ASSERT_EQ(constraints[0].proof_type, pg_type);
        BB_ASSERT_EQ(constraints[1].proof_type, pg_type);
        mock_sumcheck_ivc_accumulation(ivc, SumcheckClientIVC::QUEUE_TYPE::PG, /*is_kernel=*/true);
        mock_sumcheck_ivc_accumulation(ivc, SumcheckClientIVC::QUEUE_TYPE::PG, /*is_kernel=*/false);
        return ivc;
    }
 
    // Case: HIDING kernel; single PG_FINAL recursive verification of a kernel
    if (constraints.size() == 1 && constraints[0].proof_type == pg_final_type) {
        mock_sumcheck_ivc_accumulation(ivc, SumcheckClientIVC::QUEUE_TYPE::PG_FINAL, /*is_kernel=*/true);
        return ivc;
    }
 
    throw_or_abort("Invalid set of IVC recursion constraints!");
    return ivc;
}
 
ClientIVC::VerifierInputs create_mock_verification_queue_entry(const ClientIVC::QUEUE_TYPE verification_type,
                                                               const TraceSettings& trace_settings,
                                                               const bool is_kernel)
{
    using FF = ClientIVC::FF;
    using MegaVerificationKey = ClientIVC::MegaVerificationKey;
    using Flavor = ClientIVC::Flavor;
 
    // Use the trace settings to determine the correct dyadic size and the public inputs offset
    MegaExecutionTraceBlocks blocks;
    blocks.set_fixed_block_sizes(trace_settings);
    blocks.compute_offsets(/*is_structured=*/true);
    size_t dyadic_size = blocks.get_structured_dyadic_size();
    size_t pub_inputs_offset = blocks.pub_inputs.trace_offset();
 
    // Construct a mock Oink or PG proof and a mock MegaHonk verification key
    std::vector<FF> proof;
    std::shared_ptr<MegaVerificationKey> verification_key;
 
    if (is_kernel) {
        using KernelIO = stdlib::recursion::honk::KernelIO;
        switch (verification_type) {
        case ClientIVC::QUEUE_TYPE::OINK:
            proof = create_mock_oink_proof<Flavor, KernelIO>();
            break;
        case ClientIVC::QUEUE_TYPE::PG:
        case ClientIVC::QUEUE_TYPE::PG_FINAL:
        case ClientIVC::QUEUE_TYPE::PG_TAIL:
            proof = create_mock_pg_proof<Flavor, KernelIO>();
            break;
        default:
            throw_or_abort("Invalid verification type! Only OINK, PG and PG_FINAL are supported");
        }
        verification_key = create_mock_honk_vk<Flavor, KernelIO>(dyadic_size, pub_inputs_offset);
    } else {
        using AppIO = stdlib::recursion::honk::AppIO;
        switch (verification_type) {
        case ClientIVC::QUEUE_TYPE::OINK:
            proof = create_mock_oink_proof<Flavor, AppIO>();
            break;
        case ClientIVC::QUEUE_TYPE::PG:
            proof = create_mock_pg_proof<Flavor, AppIO>();
            break;
        default:
            throw_or_abort("Invalid verification type! Only OINK, PG and PG_FINAL are supported");
        }
        verification_key = create_mock_honk_vk<Flavor, AppIO>(dyadic_size, pub_inputs_offset);
    }
 
    return ClientIVC::VerifierInputs{ proof, verification_key, verification_type, is_kernel };
}
 
SumcheckClientIVC::VerifierInputs create_mock_verification_queue_entry_nova(
    const SumcheckClientIVC::QUEUE_TYPE verification_type, const bool is_kernel)
{
    using IvcType = SumcheckClientIVC;
    using FF = IvcType::FF;
    using MegaVerificationKey = IvcType::MegaVerificationKey;
    using Flavor = IvcType::Flavor;
 
    size_t dyadic_size = 1 << Flavor::VIRTUAL_LOG_N;         // maybe doesnt need to be correct
    size_t pub_inputs_offset = Flavor::has_zero_row ? 1 : 0; // always 1
 
    // Construct a mock Oink or PG proof and a mock MegaHonk verification key
    std::vector<FF> proof;
    std::shared_ptr<MegaVerificationKey> verification_key;
 
    if (is_kernel) {
        using KernelIO = stdlib::recursion::honk::KernelIO;
        BB_ASSERT_EQ(verification_type == SumcheckClientIVC::QUEUE_TYPE::PG ||
                         verification_type == SumcheckClientIVC::QUEUE_TYPE::PG_TAIL ||
                         verification_type == SumcheckClientIVC::QUEUE_TYPE::PG_FINAL,
                     true);
 
        // kernel circuits are always folded, thus the proof always includes the nova fold proof
        bool include_fold = true;
        proof = create_mock_hyper_nova_proof<Flavor, KernelIO>(include_fold);
 
        verification_key = create_mock_honk_vk<Flavor, KernelIO>(dyadic_size, pub_inputs_offset);
    } else {
        using AppIO = stdlib::recursion::honk::AppIO;
        BB_ASSERT_EQ(verification_type == SumcheckClientIVC::QUEUE_TYPE::OINK ||
                         verification_type == SumcheckClientIVC::QUEUE_TYPE::PG,
                     true);
 
        // The first app is not folded thus the proof does not include the nova fold proof
        bool include_fold = !(verification_type == SumcheckClientIVC::QUEUE_TYPE::OINK);
        proof = create_mock_hyper_nova_proof<Flavor, AppIO>(include_fold);
 
        verification_key = create_mock_honk_vk<Flavor, AppIO>(dyadic_size, pub_inputs_offset);
    }
 
    return SumcheckClientIVC::VerifierInputs{ proof, verification_key, verification_type, is_kernel };
}
 
void mock_ivc_accumulation(const std::shared_ptr<ClientIVC>& ivc, ClientIVC::QUEUE_TYPE type, const bool is_kernel)
{
    ClientIVC::VerifierInputs entry =
        acir_format::create_mock_verification_queue_entry(type, ivc->trace_settings, is_kernel);
    ivc->verification_queue.emplace_back(entry);
    ivc->goblin.merge_verification_queue.emplace_back(acir_format::create_mock_merge_proof());
    // If the type is PG_FINAL, we also need to populate the ivc instance with a mock decider proof
    if (type == ClientIVC::QUEUE_TYPE::PG_FINAL) {
        ivc->decider_proof = acir_format::create_mock_decider_proof<ClientIVC::Flavor>();
    }
    ivc->num_circuits_accumulated++;
}
 
void mock_sumcheck_ivc_accumulation(const std::shared_ptr<SumcheckClientIVC>& ivc,
                                    SumcheckClientIVC::QUEUE_TYPE type,
                                    const bool is_kernel)
{
    using FF = SumcheckClientIVC::FF;
    using Commitment = SumcheckClientIVC::Commitment;
 
    // Initialize verifier accumulator with proper structure
    ivc->recursive_verifier_native_accum.challenge =
        std::vector<FF>(SumcheckClientIVC::Flavor::VIRTUAL_LOG_N, FF::zero());
    ivc->recursive_verifier_native_accum.batched_evaluations = { FF::zero(), FF::zero() };
    ivc->recursive_verifier_native_accum.batched_commitments = { Commitment::one(), Commitment::one() };
 
    SumcheckClientIVC::VerifierInputs entry = acir_format::create_mock_verification_queue_entry_nova(type, is_kernel);
    ivc->verification_queue.emplace_back(entry);
    ivc->goblin.merge_verification_queue.emplace_back(acir_format::create_mock_merge_proof());
    if (type == SumcheckClientIVC::QUEUE_TYPE::PG_FINAL) {
        ivc->pcs_proof = acir_format::create_mock_pcs_proof<SumcheckClientIVC::Flavor>();
    }
    ivc->num_circuits_accumulated++;
}
 
void populate_dummy_vk_in_constraint(MegaCircuitBuilder& builder,
                                     const std::shared_ptr<MegaFlavor::VerificationKey>& mock_verification_key,
                                     std::vector<uint32_t>& key_witness_indices)
{
    using FF = ClientIVC::FF;
 
    // Convert the VerificationKey to fields
    std::vector<FF> mock_vk_fields = mock_verification_key->to_field_elements();
    BB_ASSERT_EQ(mock_vk_fields.size(), key_witness_indices.size());
 
    // Add the fields to the witness and set the key witness indices accordingly
    for (auto [witness_idx, value] : zip_view(key_witness_indices, mock_vk_fields)) {
        builder.set_variable(witness_idx, value);
    }
}
 
} // namespace acir_format