hypernova_recursion_constraint.test.cpp

Go to the documentation of this file.

#include "barretenberg/dsl/acir_format/hypernova_recursion_constraint.hpp"
#include "acir_format.hpp"
#include "barretenberg/bbapi/bbapi_shared.hpp"
#include "barretenberg/chonk/chonk.hpp"
#include "barretenberg/chonk/chonk_verifier.hpp"
#include "barretenberg/dsl/acir_format/gate_count_constants.hpp"
#include "barretenberg/dsl/acir_format/mock_verifier_inputs.hpp"
#include "barretenberg/dsl/acir_format/utils.hpp"
#include "barretenberg/goblin/mock_circuits.hpp"
#include "barretenberg/ultra_honk/prover_instance.hpp"
#include "barretenberg/ultra_honk/ultra_prover.hpp"
#include "barretenberg/ultra_honk/ultra_verifier.hpp"
#include "honk_recursion_constraint.hpp"
 
#include <gtest/gtest.h>
#include <vector>
 
using namespace acir_format;
using namespace bb;
 
class HypernovaRecursionConstraintTest : public ::testing::Test {
 
  public:
    using Builder = MegaCircuitBuilder;
    using Flavor = MegaFlavor;
    using VerificationKey = MegaFlavor::VerificationKey;
    using FF = Flavor::FF;
    using VerifierInputs = Chonk::VerifierInputs;
    using QUEUE_TYPE = Chonk::QUEUE_TYPE;
    using VerificationQueue = Chonk::VerificationQueue;
    using PairingPoints = Chonk::PairingPoints;
 
    static constexpr size_t NUM_TRAILING_KERNELS = 3; // reset, tail, hiding
 
    static Builder construct_mock_app_circuit(const std::shared_ptr<Chonk>& ivc)
    {
        Builder circuit{ ivc->goblin.op_queue };
        GoblinMockCircuits::add_some_ecc_op_gates(circuit);
        MockCircuits::add_arithmetic_gates(circuit);
        stdlib::recursion::honk::AppIO::add_default(circuit);
        return circuit;
    }
 
    static std::shared_ptr<VerificationKey> get_verification_key(Builder& builder_in, bool is_hiding_kernel = false)
    {
        // This is a workaround to ensure that the circuit is finalized before we create the verification key
        // In practice, this should not be needed as the circuit will be finalized when it is accumulated into the IVC
        // but this is a workaround for the test setup.
        // Create a copy of the input circuit
        MegaCircuitBuilder_<bb::fr> builder{ builder_in };
 
        // Deepcopy the opqueue to avoid modifying the original one
        builder.op_queue = std::make_shared<ECCOpQueue>(*builder.op_queue);
        if (is_hiding_kernel) {
            auto prover_instance = std::make_shared<Chonk::HidingKernelProverInstance>(builder);
            return std::make_shared<VerificationKey>(prover_instance->get_precomputed());
        }
        std::shared_ptr<Chonk::ProverInstance> prover_instance = std::make_shared<Chonk::ProverInstance>(builder);
        std::shared_ptr<VerificationKey> vk = std::make_shared<VerificationKey>(prover_instance->get_precomputed());
        return vk;
    }
 
    static void construct_and_accumulate_trailing_kernels(const std::shared_ptr<Chonk>& ivc)
    {
 
        // Reset kernel
        EXPECT_EQ(ivc->verification_queue.size(), 1);
        EXPECT_EQ(ivc->verification_queue[0].type, QUEUE_TYPE::HN);
        construct_and_accumulate_mock_kernel(ivc);
 
        // Tail kernel
        EXPECT_EQ(ivc->verification_queue.size(), 1);
        EXPECT_EQ(ivc->verification_queue[0].type, QUEUE_TYPE::HN_TAIL);
        construct_and_accumulate_mock_kernel(ivc);
 
        // Hiding kernel
        EXPECT_EQ(ivc->verification_queue.size(), 1);
        EXPECT_EQ(ivc->verification_queue[0].type, QUEUE_TYPE::HN_FINAL);
        construct_and_accumulate_mock_kernel(ivc);
    }
 
    static UltraCircuitBuilder create_inner_circuit(size_t log_num_gates = 10)
    {
        UltraCircuitBuilder builder;
 
        // Create 2^log_n many add gates based on input log num gates
        const size_t num_gates = (1 << log_num_gates);
        for (size_t i = 0; i < num_gates; ++i) {
            fr a = fr::random_element();
            uint32_t a_idx = builder.add_variable(a);
 
            fr b = fr::random_element();
            fr c = fr::random_element();
            fr d = a + b + c;
            uint32_t b_idx = builder.add_variable(b);
            uint32_t c_idx = builder.add_variable(c);
            uint32_t d_idx = builder.add_variable(d);
 
            builder.create_big_add_gate({ a_idx, b_idx, c_idx, d_idx, fr(1), fr(1), fr(1), fr(-1), fr(0) });
        }
 
        stdlib::recursion::honk::DefaultIO<UltraCircuitBuilder>::add_default(builder);
        return builder;
    }
 
    static Builder construct_mock_UH_recursion_app_circuit(const std::shared_ptr<Chonk>& ivc, const bool tamper_vk)
    {
        AcirProgram program;
        std::vector<RecursionConstraint> recursion_constraints;
 
        Builder circuit{ ivc->goblin.op_queue };
        GoblinMockCircuits::add_some_ecc_op_gates(circuit);
        MockCircuits::add_arithmetic_gates(circuit);
 
        {
            using RecursiveFlavor = UltraRecursiveFlavor_<Builder>;
            using VerifierOutput = bb::stdlib::recursion::honk::UltraRecursiveVerifierOutput<Builder>;
            using StdlibProof = bb::stdlib::Proof<Builder>;
            using StdlibIO = bb::stdlib::recursion::honk::DefaultIO<Builder>;
 
            // Create an arbitrary inner circuit
            auto inner_circuit = create_inner_circuit();
 
            // Compute native verification key
            auto prover_instance = std::make_shared<ProverInstance_<UltraFlavor>>(inner_circuit);
            auto honk_vk = std::make_shared<UltraFlavor::VerificationKey>(prover_instance->get_precomputed());
            UltraProver prover(prover_instance, honk_vk); // A prerequisite for computing VK
            auto inner_proof = prover.construct_proof();
 
            if (tamper_vk) {
                honk_vk->q_l = g1::one;
                auto honk_vk_and_hash = std::make_shared<UltraFlavor::VKAndHash>(honk_vk);
                UltraVerifier_<UltraFlavor, DefaultIO> verifier(honk_vk_and_hash);
                EXPECT_FALSE(verifier.verify_proof(inner_proof).result);
            }
            // Instantiate the recursive verifier using the native verification key
            auto stdlib_vk_and_hash = std::make_shared<RecursiveFlavor::VKAndHash>(circuit, honk_vk);
            bb::UltraVerifier_<RecursiveFlavor, StdlibIO> verifier(stdlib_vk_and_hash);
 
            StdlibProof stdlib_inner_proof(circuit, inner_proof);
            VerifierOutput output = verifier.verify_proof(stdlib_inner_proof);
 
            // IO
            StdlibIO inputs;
            inputs.pairing_inputs = output.points_accumulator;
            inputs.set_public(); // propagate resulting pairing points on the public inputs
        }
 
        return circuit;
    }
 
    static RecursionConstraint create_recursion_constraint(const VerifierInputs& input, std::vector<FF>& witness)
    {
        // Use centralized conversion from QUEUE_TYPE to PROOF_TYPE
        PROOF_TYPE proof_type = queue_type_to_proof_type(input.type);
 
        RecursionConstraint constraint =
            recursion_data_to_recursion_constraint(witness,
                                                   input.proof, // proof contains the public inputs at this stage
                                                   input.honk_vk->to_field_elements(),
                                                   input.honk_vk->hash(),
                                                   bb::fr::zero(),
                                                   /*num_public_inputs_to_extract=*/0,
                                                   proof_type);
 
        constraint.proof = {}; // the proof witness indices are not needed in an ivc recursion constraint
 
        return constraint;
    }
 
    static AcirProgram construct_mock_kernel_program(const VerificationQueue& verification_queue)
    {
        AcirProgram program;
 
        // Construct recursion constraints based on the ivc verification queue; populate the witness along the way
        std::vector<RecursionConstraint> hn_recursion_constraints;
        hn_recursion_constraints.reserve(verification_queue.size());
        for (const auto& queue_entry : verification_queue) {
            hn_recursion_constraints.push_back(create_recursion_constraint(queue_entry, program.witness));
        }
 
        // Construct a constraint system containing the business logic and ivc recursion constraints
        program.constraints.max_witness_index = static_cast<uint32_t>(program.witness.size() - 1);
        program.constraints.num_acir_opcodes = static_cast<uint32_t>(hn_recursion_constraints.size());
        program.constraints.hn_recursion_constraints = hn_recursion_constraints;
        for (size_t idx = 0; idx < hn_recursion_constraints.size(); ++idx) {
            program.constraints.original_opcode_indices.hn_recursion_constraints.push_back(static_cast<uint32_t>(idx));
        }
 
        return program;
    }
 
    static void construct_and_accumulate_mock_kernel(std::shared_ptr<Chonk> ivc)
    {
        // construct a mock kernel program (acir) from the ivc verification queue
        const ProgramMetadata metadata{ ivc };
        AcirProgram mock_kernel_program = construct_mock_kernel_program(ivc->verification_queue);
        auto kernel = acir_format::create_circuit<Builder>(mock_kernel_program, metadata);
        const bool is_hiding_kernel = ivc->num_circuits_accumulated == ivc->get_num_circuits() - 1;
        auto kernel_vk = get_kernel_vk_from_circuit(kernel, is_hiding_kernel);
        ivc->accumulate(kernel, kernel_vk);
    }
 
    static void construct_and_accumulate_mock_app(std::shared_ptr<Chonk> ivc)
    {
        // construct a mock kernel program (acir) from the ivc verification queue
        auto app_circuit = construct_mock_app_circuit(ivc);
        ivc->accumulate(app_circuit, get_verification_key(app_circuit));
    }
 
    static std::shared_ptr<Chonk::MegaVerificationKey> construct_kernel_vk_from_acir_program(
        AcirProgram& program, bool is_hiding_kernel = false)
    {
        // Create kernel circuit from the kernel program
        auto kernel = acir_format::create_circuit<Builder>(program);
        if (is_hiding_kernel) {
            auto prover_instance = std::make_shared<Chonk::HidingKernelProverInstance>(kernel);
            return std::make_shared<Chonk::MegaVerificationKey>(prover_instance->get_precomputed());
        }
        auto prover_instance = std::make_shared<Chonk::ProverInstance>(kernel);
        return std::make_shared<Chonk::MegaVerificationKey>(prover_instance->get_precomputed());
    }
 
    static std::shared_ptr<Chonk::MegaVerificationKey> get_kernel_vk_from_circuit(Builder& kernel,
                                                                                  bool is_hiding_kernel = false)
    {
        if (is_hiding_kernel) {
            auto prover_instance = std::make_shared<Chonk::HidingKernelProverInstance>(kernel);
            return std::make_shared<Chonk::MegaVerificationKey>(prover_instance->get_precomputed());
        }
        auto prover_instance = std::make_shared<Chonk::ProverInstance>(kernel);
        return std::make_shared<Chonk::MegaVerificationKey>(prover_instance->get_precomputed());
    }
 
  protected:
    void SetUp() override { bb::srs::init_file_crs_factory(bb::srs::bb_crs_path()); }
};
 
TEST_F(HypernovaRecursionConstraintTest, MockMergeProofSize)
{
    Goblin::MergeProof merge_proof = create_mock_merge_proof();
    EXPECT_EQ(merge_proof.size(), MERGE_PROOF_SIZE);
}
 
TEST_F(HypernovaRecursionConstraintTest, AccumulateSingleApp)
{
    auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5 /* app, kernel, reset, tail, hiding */);
 
    // construct a mock app_circuit
    construct_and_accumulate_mock_app(ivc);
 
    // Construct kernel consisting only of the kernel completion logic
    construct_and_accumulate_mock_kernel(ivc);
 
    // add the trailing kernels
    construct_and_accumulate_trailing_kernels(ivc);
 
    auto proof = ivc->prove();
    {
        auto vk_and_hash = ivc->get_hiding_kernel_vk_and_hash();
        ChonkNativeVerifier verifier(vk_and_hash);
        EXPECT_TRUE(verifier.verify(proof));
    }
}
 
TEST_F(HypernovaRecursionConstraintTest, AccumulateTwoApps)
{
    // 4 ciruits and the tail kernel
    auto ivc = std::make_shared<Chonk>(/*num_circuits=*/7);
 
    // construct a mock app_circuit
    construct_and_accumulate_mock_app(ivc);
 
    const ProgramMetadata metadata{ ivc };
 
    // Construct kernel_0; consists of a single oink recursive verification for app (plus databus/merge logic)
    construct_and_accumulate_mock_kernel(ivc);
 
    // construct a mock app_circuit
    construct_and_accumulate_mock_app(ivc);
 
    // Construct and accumulate another Kernel circuit
    construct_and_accumulate_mock_kernel(ivc);
 
    // Accumulate the trailing kernels
    construct_and_accumulate_trailing_kernels(ivc);
 
    auto proof = ivc->prove();
    {
        ChonkNativeVerifier verifier(ivc->get_hiding_kernel_vk_and_hash());
        EXPECT_TRUE(verifier.verify(proof));
    }
}
 
// Test generation of "init" kernel VK via dummy IVC data
TEST_F(HypernovaRecursionConstraintTest, GenerateInitKernelVKFromConstraints)
{
    BB_DISABLE_ASSERTS();
    // First, construct the kernel VK by running the full IVC (accumulate one app and one kernel)
    std::shared_ptr<MegaFlavor::VerificationKey> expected_kernel_vk;
    {
        auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
 
        // Construct and accumulate mock app_circuit
        construct_and_accumulate_mock_app(ivc);
 
        // Construct and accumulate kernel consisting only of the kernel completion logic
        construct_and_accumulate_mock_kernel(ivc);
        expected_kernel_vk = ivc->verification_queue.back().honk_vk;
    }
 
    // Now, construct the kernel VK by mocking the post app accumulation state of the IVC
    std::shared_ptr<MegaFlavor::VerificationKey> kernel_vk;
    {
        auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
 
        // Construct kernel consisting only of the kernel completion logic
        acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::OINK, /*is_kernel=*/false);
        AcirProgram program = construct_mock_kernel_program(ivc->verification_queue);
        program.witness = {}; // remove the witness to mimick VK construction context
 
        kernel_vk = construct_kernel_vk_from_acir_program(program);
    }
 
    // Compare the VK constructed via running the IVc with the one constructed via mocking
    EXPECT_EQ(*kernel_vk.get(), *expected_kernel_vk.get());
}
 
// Test generation of "reset" kernel VK via dummy IVC data
TEST_F(HypernovaRecursionConstraintTest, GenerateResetKernelVKFromConstraints)
{
    BB_DISABLE_ASSERTS();
    // First, construct the kernel VK by running the full IVC (accumulate one app and one kernel)
    std::shared_ptr<MegaFlavor::VerificationKey> expected_kernel_vk;
    {
        auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
 
        const ProgramMetadata metadata{ ivc };
 
        // Construct and accumulate mock app_circuit
        construct_and_accumulate_mock_app(ivc);
 
        // Construct and accumulate a mock INIT kernel (oink recursion for app accumulation)
        construct_and_accumulate_mock_kernel(ivc);
        EXPECT_TRUE(ivc->verification_queue.size() == 1);
        EXPECT_TRUE(ivc->verification_queue[0].type == bb::Chonk::QUEUE_TYPE::HN);
 
        // Construct and accumulate a mock RESET kernel (HN recursion for kernel accumulation)
        construct_and_accumulate_mock_kernel(ivc);
        expected_kernel_vk = ivc->verification_queue.back().honk_vk;
    }
 
    // Now, construct the kernel VK by mocking the IVC state prior to kernel construction
    std::shared_ptr<MegaFlavor::VerificationKey> kernel_vk;
    {
        auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
 
        // Construct kernel consisting only of the kernel completion logic
        acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::HN, /*is_kernel=*/true);
        AcirProgram program = construct_mock_kernel_program(ivc->verification_queue);
        program.witness = {}; // remove the witness to mimick VK construction context
        kernel_vk = construct_kernel_vk_from_acir_program(program);
    }
 
    // Compare the VK constructed via running the IVc with the one constructed via mocking
    EXPECT_EQ(*kernel_vk.get(), *expected_kernel_vk.get());
}
 
// Test generation of "tail" kernel VK via dummy IVC data
TEST_F(HypernovaRecursionConstraintTest, GenerateTailKernelVKFromConstraints)
{
    BB_DISABLE_ASSERTS();
    // First, construct the kernel VK by running the full IVC (accumulate one app and one kernel)
    std::shared_ptr<MegaFlavor::VerificationKey> expected_kernel_vk;
    {
        auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
 
        const ProgramMetadata metadata{ ivc };
 
        // Construct and accumulate mock app_circuit
        construct_and_accumulate_mock_app(ivc);
 
        // Construct and accumulate a mock INIT kernel (oink recursion for app accumulation)
        construct_and_accumulate_mock_kernel(ivc);
 
        // Construct and accumulate a mock RESET kernel (HN recursion for kernel accumulation)
        construct_and_accumulate_mock_kernel(ivc);
 
        // Construct and accumulate a mock TAIL kernel (HN recursion for kernel accumulation)
        EXPECT_TRUE(ivc->verification_queue.size() == 1);
        EXPECT_TRUE(ivc->verification_queue[0].type == bb::Chonk::QUEUE_TYPE::HN_TAIL);
        construct_and_accumulate_mock_kernel(ivc);
 
        expected_kernel_vk = ivc->verification_queue.back().honk_vk;
    }
 
    // Now, construct the kernel VK by mocking the IVC state prior to kernel construction
    std::shared_ptr<MegaFlavor::VerificationKey> kernel_vk;
    {
        auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
 
        // Construct kernel consisting only of the kernel completion logic
        acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::HN_TAIL, /*is_kernel=*/true);
        AcirProgram program = construct_mock_kernel_program(ivc->verification_queue);
        program.witness = {}; // remove the witness to mimick VK construction context
 
        kernel_vk = construct_kernel_vk_from_acir_program(program);
    }
 
    // Compare the VK constructed via running the IVc with the one constructed via mocking
    EXPECT_EQ(*kernel_vk.get(), *expected_kernel_vk.get());
}
 
// Test generation of "inner" kernel VK via dummy IVC data
TEST_F(HypernovaRecursionConstraintTest, GenerateInnerKernelVKFromConstraints)
{
    BB_DISABLE_ASSERTS();
    // First, construct the kernel VK by running the full IVC (accumulate one app and one kernel)
    std::shared_ptr<MegaFlavor::VerificationKey> expected_kernel_vk;
    {
        // we have to set the number of circuits one more than the number of circuits we're accumulating as otherwise
        // the last circuit will be seen as a tail
        auto ivc = std::make_shared<Chonk>(/*num_circuits=*/6);
 
        const ProgramMetadata metadata{ ivc };
 
        { // Construct and accumulate mock app_circuit
            construct_and_accumulate_mock_app(ivc);
        }
 
        // Construct and accumulate a mock INIT kernel (oink recursion for app accumulation)
        construct_and_accumulate_mock_kernel(ivc);
 
        { // Construct and accumulate a second mock app_circuit
            construct_and_accumulate_mock_app(ivc);
        }
 
        { // Construct and accumulate a mock INNER kernel (HN recursion for kernel accumulation)
            EXPECT_TRUE(ivc->verification_queue.size() == 2);
            EXPECT_TRUE(ivc->verification_queue[1].type == bb::Chonk::QUEUE_TYPE::HN);
            construct_and_accumulate_mock_kernel(ivc);
        }
 
        expected_kernel_vk = ivc->verification_queue.back().honk_vk;
    }
 
    // Now, construct the kernel VK by mocking the IVC state prior to kernel construction
    std::shared_ptr<MegaFlavor::VerificationKey> kernel_vk;
    {
        auto ivc = std::make_shared<Chonk>(/*num_circuits=*/4);
 
        // Construct kernel consisting only of the kernel completion logic
        acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::HN, /*is_kernel=*/true);
        acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::HN, /*is_kernel=*/false);
        AcirProgram program = construct_mock_kernel_program(ivc->verification_queue);
        program.witness = {}; // remove the witness to mimick VK construction context
 
        kernel_vk = construct_kernel_vk_from_acir_program(program);
    }
 
    // Compare the VK constructed via running the IVc with the one constructed via mocking
    EXPECT_EQ(*kernel_vk.get(), *expected_kernel_vk.get());
}
 
// Test generation of "hiding" kernel VK via dummy IVC data
TEST_F(HypernovaRecursionConstraintTest, GenerateMegaVerificationKeyFromConstraints)
{
    BB_DISABLE_ASSERTS();
    // First, construct the kernel VK by running the full IVC
    std::shared_ptr<MegaFlavor::VerificationKey> expected_hiding_kernel_vk;
    {
        auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
        const ProgramMetadata metadata{ ivc };
 
        {
            // Construct and accumulate mock app_circuit
            construct_and_accumulate_mock_app(ivc);
        }
 
        {
            // Construct and accumulate a mock INIT kernel (oink recursion for app accumulation)
            construct_and_accumulate_mock_kernel(ivc);
        }
 
        construct_and_accumulate_trailing_kernels(ivc);
 
        // The single entry in the verification queue corresponds to the hiding kernel
        expected_hiding_kernel_vk = ivc->verification_queue[0].honk_vk;
    }
 
    // Now, construct the kernel VK by mocking the IVC state prior to kernel construction
    std::shared_ptr<MegaFlavor::VerificationKey> kernel_vk;
    {
        // mock IVC accumulation increases the num_circuits_accumualted, hence we need to assume the tail kernel has
        // been accumulated
        auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
        // construct a mock tail kernel
        acir_format::mock_chonk_accumulation(ivc,
                                             Chonk::QUEUE_TYPE::HN_FINAL,
                                             /*is_kernel=*/true);
        AcirProgram program = construct_mock_kernel_program(ivc->verification_queue);
        program.witness = {}; // remove the witness to mimick VK construction context
        kernel_vk = construct_kernel_vk_from_acir_program(program, /*is_hiding_kernel=*/true);
    }
 
    // Compare the VK constructed via running the IVc with the one constructed via mocking
    EXPECT_EQ(*kernel_vk.get(), *expected_hiding_kernel_vk.get());
}
 
TEST_F(HypernovaRecursionConstraintTest, RecursiveVerifierAppCircuit)
{
    auto ivc = std::make_shared<Chonk>(/*num_circuits*/ 5);
 
    // construct a mock app_circuit with an UH recursion call
    Builder app_circuit = construct_mock_UH_recursion_app_circuit(ivc, /*tamper_vk=*/false);
 
    // Complete instance and generate an oink proof
    ivc->accumulate(app_circuit, get_verification_key(app_circuit));
 
    // Construct kernel consisting only of the kernel completion logic
    construct_and_accumulate_mock_kernel(ivc);
 
    construct_and_accumulate_trailing_kernels(ivc);
 
    auto proof = ivc->prove();
    {
        ChonkNativeVerifier verifier(ivc->get_hiding_kernel_vk_and_hash());
        EXPECT_TRUE(verifier.verify(proof));
    }
}
 
TEST_F(HypernovaRecursionConstraintTest, RecursiveVerifierAppCircuitFailure)
{
    BB_DISABLE_ASSERTS(); // Disable assert in HN prover
 
    auto ivc = std::make_shared<Chonk>(/*num_circuits*/ 5);
 
    // construct and accumulate mock app_circuit that has bad pairing point object
    Builder app_circuit = construct_mock_UH_recursion_app_circuit(ivc, /*tamper_vk=*/true);
    ivc->accumulate(app_circuit, get_verification_key(app_circuit));
 
    // Construct kernel consisting only of the kernel completion logic
    construct_and_accumulate_mock_kernel(ivc);
 
    // add the trailing kernels
    construct_and_accumulate_trailing_kernels(ivc);
 
    // We expect the Chonk proof to fail due to the app with a failed UH recursive verification
    auto proof = ivc->prove();
    {
        ChonkNativeVerifier verifier(ivc->get_hiding_kernel_vk_and_hash());
        EXPECT_FALSE(verifier.verify(proof));
    }
}
 
TEST_F(HypernovaRecursionConstraintTest, InitKernelGateCount)
{
    BB_DISABLE_ASSERTS();
    auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
 
    // Mock the post-app accumulation state (OINK proof ready to be verified)
    acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::OINK, /*is_kernel=*/false);
 
    // Construct kernel program with gate counting enabled
    AcirProgram program = construct_mock_kernel_program(ivc->verification_queue);
    ProgramMetadata metadata{ .ivc = ivc, .collect_gates_per_opcode = true };
 
    auto kernel = acir_format::create_circuit<Builder>(program, metadata);
 
    // Verify the gate count was recorded
    EXPECT_EQ(program.constraints.gates_per_opcode.size(), 1);
 
    // Assert gate count
    EXPECT_EQ(program.constraints.gates_per_opcode[0], INIT_KERNEL_GATE_COUNT);
 
    // Assert ECC row count
    size_t actual_ecc_rows = kernel.op_queue->get_num_rows();
    EXPECT_EQ(actual_ecc_rows, INIT_KERNEL_ECC_ROWS);
 
    // Assert ultra ops count
    size_t actual_ultra_ops = kernel.op_queue->get_current_subtable_size();
    EXPECT_EQ(actual_ultra_ops, INIT_KERNEL_ULTRA_OPS);
}
 
TEST_F(HypernovaRecursionConstraintTest, InnerKernelGateCount)
{
    BB_DISABLE_ASSERTS();
    auto ivc = std::make_shared<Chonk>(/*num_circuits=*/4);
 
    // Mock the state where we need to verify a previous kernel (HN) and a new app (HN)
    acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::HN, /*is_kernel=*/true);
    acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::HN, /*is_kernel=*/false);
 
    // Construct kernel program with gate counting enabled
    AcirProgram program = construct_mock_kernel_program(ivc->verification_queue);
    ProgramMetadata metadata{ .ivc = ivc, .collect_gates_per_opcode = true };
 
    auto kernel = acir_format::create_circuit<Builder>(program, metadata);
 
    // Verify the gate count was recorded
    EXPECT_EQ(program.constraints.gates_per_opcode.size(), 2);
 
    // Assert gate counts (HN verification + OINK verification)
    EXPECT_EQ(program.constraints.gates_per_opcode[0], INNER_KERNEL_GATE_COUNT_HN);
 
    // Assert ECC row count
    size_t actual_ecc_rows = kernel.op_queue->get_num_rows();
    EXPECT_EQ(actual_ecc_rows, INNER_KERNEL_ECC_ROWS);
 
    // Assert ultra ops count
    size_t actual_ultra_ops = kernel.op_queue->get_current_subtable_size();
    EXPECT_EQ(actual_ultra_ops, INNER_KERNEL_ULTRA_OPS);
}
 
TEST_F(HypernovaRecursionConstraintTest, TailKernelGateCount)
{
    BB_DISABLE_ASSERTS();
    auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
 
    // Mock the state where we need to verify a tail kernel proof
    acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::HN_TAIL, /*is_kernel=*/true);
 
    // Construct kernel program with gate counting enabled
    AcirProgram program = construct_mock_kernel_program(ivc->verification_queue);
    ProgramMetadata metadata{ .ivc = ivc, .collect_gates_per_opcode = true };
 
    auto kernel = acir_format::create_circuit<Builder>(program, metadata);
 
    // Verify the gate count was recorded
    EXPECT_EQ(program.constraints.gates_per_opcode.size(), 1);
 
    // Assert gate count
    EXPECT_EQ(program.constraints.gates_per_opcode[0], TAIL_KERNEL_GATE_COUNT);
 
    // Assert ECC row count
    size_t actual_ecc_rows = kernel.op_queue->get_num_rows();
    EXPECT_EQ(actual_ecc_rows, TAIL_KERNEL_ECC_ROWS);
 
    // Assert ultra ops count
    size_t actual_ultra_ops = kernel.op_queue->get_current_subtable_size();
    EXPECT_EQ(actual_ultra_ops, TAIL_KERNEL_ULTRA_OPS);
}
 
TEST_F(HypernovaRecursionConstraintTest, HidingKernelGateCount)
{
    BB_DISABLE_ASSERTS();
    auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
 
    // Mock the state where we need to verify a hiding kernel proof
    acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::HN_FINAL, /*is_kernel=*/true);
 
    // Construct kernel program with gate counting enabled
    AcirProgram program = construct_mock_kernel_program(ivc->verification_queue);
    ProgramMetadata metadata{ .ivc = ivc, .collect_gates_per_opcode = true };
 
    auto kernel = acir_format::create_circuit<Builder>(program, metadata);
 
    // Verify the gate count was recorded
    EXPECT_EQ(program.constraints.gates_per_opcode.size(), 1);
 
    // Assert gate count
    EXPECT_EQ(program.constraints.gates_per_opcode[0], HIDING_KERNEL_GATE_COUNT);
 
    // Assert ECC row count
    size_t actual_ecc_rows = kernel.op_queue->get_num_rows();
    EXPECT_EQ(actual_ecc_rows, HIDING_KERNEL_ECC_ROWS);
 
    // Assert ultra ops count
    size_t actual_ultra_ops = kernel.op_queue->get_current_subtable_size();
    EXPECT_EQ(actual_ultra_ops, HIDING_KERNEL_ULTRA_OPS);
}
 
// =====================================================================================
// Boundary check failure tests - verify that invalid inputs are rejected
// =====================================================================================
 
TEST_F(HypernovaRecursionConstraintTest, FailsOnConstraintIndicesSizeMismatch)
{
    auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
    acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::OINK, /*is_kernel=*/false);
 
    AcirProgram program = construct_mock_kernel_program(ivc->verification_queue);
 
    // Corrupt the opcode indices to have wrong size
    program.constraints.original_opcode_indices.hn_recursion_constraints.push_back(999);
 
    ProgramMetadata metadata{ .ivc = ivc };
 
    EXPECT_THROW_WITH_MESSAGE(acir_format::create_circuit<Builder>(program, metadata),
                              "hn_recursion_data constraints/indices size mismatch");
}
 
TEST_F(HypernovaRecursionConstraintTest, FailsOnAcirQueueSizeMismatch)
{
    auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
    acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::OINK, /*is_kernel=*/false);
 
    AcirProgram program = construct_mock_kernel_program(ivc->verification_queue);
 
    // Add an extra constraint that doesn't exist in the IVC queue
    program.constraints.hn_recursion_constraints.push_back(program.constraints.hn_recursion_constraints[0]);
    program.constraints.original_opcode_indices.hn_recursion_constraints.push_back(1);
 
    ProgramMetadata metadata{ .ivc = ivc };
 
    EXPECT_THROW_WITH_MESSAGE(acir_format::create_circuit<Builder>(program, metadata),
                              "mismatch in number of recursive verifications");
}
 
TEST_F(HypernovaRecursionConstraintTest, FailsOnNonEmptyPublicInputs)
{
    auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
    acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::OINK, /*is_kernel=*/false);
 
    AcirProgram program = construct_mock_kernel_program(ivc->verification_queue);
 
    // Add public inputs to the constraint (which should be empty for HN)
    program.constraints.hn_recursion_constraints[0].public_inputs = { 0, 1, 2 };
 
    ProgramMetadata metadata{ .ivc = ivc };
 
    EXPECT_THROW_WITH_MESSAGE(acir_format::create_circuit<Builder>(program, metadata),
                              "unexpected non-empty public_inputs in HN constraint");
}
 
TEST_F(HypernovaRecursionConstraintTest, FailsOnProofTypeMismatch)
{
    auto ivc = std::make_shared<Chonk>(/*num_circuits=*/5);
    acir_format::mock_chonk_accumulation(ivc, Chonk::QUEUE_TYPE::OINK, /*is_kernel=*/false);
 
    AcirProgram program = construct_mock_kernel_program(ivc->verification_queue);
 
    // Change the proof type to something that doesn't match the queue entry
    // OINK queue entry expects PROOF_TYPE::OINK, change to HN
    program.constraints.hn_recursion_constraints[0].proof_type = PROOF_TYPE::HN;
 
    ProgramMetadata metadata{ .ivc = ivc };
 
    EXPECT_THROW_WITH_MESSAGE(acir_format::create_circuit<Builder>(program, metadata),
                              "ACIR constraint proof_type does not match IVC queue type");
}