mega_honk.test.cpp

Go to the documentation of this file.

#include <cstddef>
#include <cstdint>
#include <gtest/gtest.h>
 
#include "barretenberg/circuit_checker/circuit_checker.hpp"
#include "barretenberg/common/log.hpp"
#include "barretenberg/goblin/mock_circuits.hpp"
#include "barretenberg/honk/proof_length.hpp"
#include "barretenberg/honk/relation_checker.hpp"
#include "barretenberg/stdlib_circuit_builders/mega_circuit_builder.hpp"
#include "barretenberg/stdlib_circuit_builders/ultra_circuit_builder.hpp"
#include "barretenberg/ultra_honk/oink_prover.hpp"
#include "barretenberg/ultra_honk/ultra_prover.hpp"
#include "barretenberg/ultra_honk/ultra_verifier.hpp"
 
using namespace bb;
 
auto& engine = numeric::get_debug_randomness();
 
using FlavorTypes = ::testing::Types<MegaFlavor, MegaZKFlavor>;
 
template <typename Flavor> class MegaHonkTests : public ::testing::Test {
  public:
    static void SetUpTestSuite() { bb::srs::init_file_crs_factory(bb::srs::bb_crs_path()); }
 
    using Curve = curve::BN254;
    using FF = Curve::ScalarField;
    using Point = Curve::AffineElement;
    using CommitmentKey = bb::CommitmentKey<Curve>;
    using Prover = UltraProver_<Flavor>;
    using Verifier = UltraVerifier_<Flavor, DefaultIO>;
    using VerificationKey = typename Flavor::VerificationKey;
    using ProverInstance = ProverInstance_<Flavor>;
    using VerifierInstance = VerifierInstance_<Flavor>;
 
    bool construct_and_verify_honk_proof(auto& builder)
    {
        auto prover_instance = std::make_shared<ProverInstance>(builder);
        auto verification_key = std::make_shared<VerificationKey>(prover_instance->get_precomputed());
        auto vk_and_hash = std::make_shared<typename Flavor::VKAndHash>(verification_key);
        Prover prover(prover_instance, verification_key);
        Verifier verifier(vk_and_hash);
        auto proof = prover.construct_proof();
        bool verified = verifier.verify_proof(proof).result;
 
        return verified;
    }
};
 
TYPED_TEST_SUITE(MegaHonkTests, FlavorTypes);
 
TYPED_TEST(MegaHonkTests, ProofLengthCheck)
{
    using Flavor = TypeParam;
    using Builder = Flavor::CircuitBuilder;
    using DefaultIO = stdlib::recursion::honk::DefaultIO<Builder>;
 
    auto builder = Builder{};
    DefaultIO::add_default(builder);
 
    // Construct a mega proof and ensure its size matches expectation; if not, the constant may need to be updated
    auto prover_instance = std::make_shared<ProverInstance_<Flavor>>(builder);
    auto verification_key = std::make_shared<typename Flavor::VerificationKey>(prover_instance->get_precomputed());
    UltraProver_<Flavor> prover(prover_instance, verification_key);
    HonkProof mega_proof = prover.construct_proof();
    EXPECT_EQ(mega_proof.size(),
              ProofLength::Honk<Flavor>::LENGTH_WITHOUT_PUB_INPUTS(Flavor::VIRTUAL_LOG_N) +
                  DefaultIO::PUBLIC_INPUTS_SIZE);
}
 
TYPED_TEST(MegaHonkTests, Basic)
{
    using Flavor = TypeParam;
    typename Flavor::CircuitBuilder builder;
 
    GoblinMockCircuits::construct_simple_circuit(builder);
 
    // Construct and verify Honk proof
    bool honk_verified = this->construct_and_verify_honk_proof(builder);
    EXPECT_TRUE(honk_verified);
}
 
TYPED_TEST(MegaHonkTests, DynamicVirtualSizeIncrease)
{
    using Flavor = TypeParam;
 
    // In MegaZKFlavor, we mask witness polynomials by placing random values at the indices `dyadic_circuit_size`-i for
    // i=1,2,3. This mechanism does not work with structured polynomials yet.
    if constexpr (std::is_same_v<Flavor, MegaZKFlavor>) {
        GTEST_SKIP() << "Skipping 'DynamicVirtualSizeIncrease' test for MegaZKFlavor.";
    }
    typename Flavor::CircuitBuilder builder;
    using Prover = UltraProver_<Flavor>;
    using Verifier = UltraVerifier_<Flavor, DefaultIO>;
 
    GoblinMockCircuits::construct_simple_circuit(builder);
 
    auto builder_copy = builder;
 
    // Construct and verify Honk proof using a structured trace
    auto prover_instance = std::make_shared<ProverInstance_<Flavor>>(builder);
    auto prover_instance_copy = std::make_shared<ProverInstance_<Flavor>>(builder_copy);
    auto circuit_size = prover_instance->dyadic_size();
 
    auto doubled_circuit_size = 2 * circuit_size;
    prover_instance_copy->polynomials.increase_polynomials_virtual_size(doubled_circuit_size);
    // TODO(https://github.com/AztecProtocol/barretenberg/issues/1158)
    // prover_instance_copy->dyadic_circuit_size = doubled_circuit_size;
 
    auto verification_key = std::make_shared<typename Flavor::VerificationKey>(prover_instance->get_precomputed());
    Prover prover(prover_instance, verification_key);
 
    auto verification_key_copy = std::make_shared<typename Flavor::VerificationKey>(prover_instance->get_precomputed());
    Prover prover_copy(prover_instance_copy, verification_key_copy);
 
    for (auto [entry, entry_copy] : zip_view(verification_key->get_all(), verification_key_copy->get_all())) {
        EXPECT_EQ(entry, entry_copy);
    }
 
    auto vk_and_hash = std::make_shared<typename Flavor::VKAndHash>(verification_key);
    Verifier verifier(vk_and_hash);
    auto proof = prover.construct_proof();
 
    auto relation_failures =
        RelationChecker<Flavor>::check_all(prover_instance->polynomials, prover_instance->relation_parameters);
    EXPECT_TRUE(relation_failures.empty());
    bool result = verifier.verify_proof(proof).result;
    EXPECT_TRUE(result);
 
    auto vk_and_hash_copy = std::make_shared<typename Flavor::VKAndHash>(verification_key_copy);
    Verifier verifier_copy(vk_and_hash_copy);
    auto proof_copy = prover_copy.construct_proof();
 
    auto relation_failures_copy =
        RelationChecker<Flavor>::check_all(prover_instance->polynomials, prover_instance->relation_parameters);
    EXPECT_TRUE(relation_failures.empty());
    bool result_copy = verifier_copy.verify_proof(proof_copy).result;
    EXPECT_TRUE(result_copy);
}
 
TYPED_TEST(MegaHonkTests, PolySwap)
{
    using Flavor = TypeParam;
    // In MegaZKFlavor, we mask witness polynomials by placing random values at the indices `dyadic_circuit_size`-i, for
    // i=1,2,3. This mechanism does not work with structured polynomials yet.
    if constexpr (std::is_same_v<Flavor, MegaZKFlavor>) {
        GTEST_SKIP() << "Skipping 'PolySwap' test for MegaZKFlavor.";
    }
    using Builder = Flavor::CircuitBuilder;
 
    // Construct a simple circuit and make a copy of it
    Builder builder;
    GoblinMockCircuits::construct_simple_circuit(builder);
    auto builder_copy = builder;
 
    // Construct two identical proving keys
    auto prover_instance_1 = std::make_shared<typename TestFixture::ProverInstance>(builder);
    auto prover_instance_2 = std::make_shared<typename TestFixture::ProverInstance>(builder_copy);
 
    // Tamper with the polys of pkey 1 in such a way that verification should fail
    for (size_t i = 0; i < prover_instance_1->dyadic_size(); ++i) {
        if (prover_instance_1->polynomials.q_arith[i] != 0) {
            prover_instance_1->polynomials.w_l.at(i) += 1;
            break;
        }
    }
 
    // Swap the polys of the two proving keys; result should be pkey 1 is valid and pkey 2 should fail
    std::swap(prover_instance_1->polynomials, prover_instance_2->polynomials);
 
    { // Verification based on pkey 1 should succeed
        auto verification_key =
            std::make_shared<typename TestFixture::VerificationKey>(prover_instance_1->get_precomputed());
        auto vk_and_hash = std::make_shared<typename Flavor::VKAndHash>(verification_key);
        typename TestFixture::Prover prover(prover_instance_1, verification_key);
        typename TestFixture::Verifier verifier(vk_and_hash);
        auto proof = prover.construct_proof();
        bool result = verifier.verify_proof(proof).result;
        EXPECT_TRUE(result);
    }
 
    { // Verification based on pkey 2 should fail
        auto verification_key =
            std::make_shared<typename TestFixture::VerificationKey>(prover_instance_2->get_precomputed());
        auto vk_and_hash = std::make_shared<typename Flavor::VKAndHash>(verification_key);
        typename TestFixture::Prover prover(prover_instance_2, verification_key);
        typename TestFixture::Verifier verifier(vk_and_hash);
        auto proof = prover.construct_proof();
        bool result = verifier.verify_proof(proof).result;
        EXPECT_FALSE(result);
    }
}
 
TYPED_TEST(MegaHonkTests, DyadicSizeJumpsToProtectMaskingArea)
{
    using Flavor = TypeParam;
    if constexpr (!Flavor::HasZK) {
        GTEST_SKIP() << "Masking area only exists for ZK flavors";
    } else {
        using Builder = typename Flavor::CircuitBuilder;
        using ProverInstance = ProverInstance_<Flavor>;
 
        // Determine the baseline dyadic size (with ECC ops + finalization overhead, no extra user gates)
        Builder baseline_builder;
        GoblinMockCircuits::construct_simple_circuit(baseline_builder);
        auto baseline_instance = std::make_shared<ProverInstance>(baseline_builder);
        const size_t baseline_dyadic = baseline_instance->dyadic_size();
 
        // The disabled head region is always present.
        // Verify active trace starts after it and dyadic size doubles when tightly packed.
        size_t prev_dyadic = 0;
        bool found_jump = false;
        for (size_t num_extra_gates = 0; num_extra_gates <= baseline_dyadic; num_extra_gates++) {
            Builder builder;
            GoblinMockCircuits::construct_simple_circuit(builder);
            if (num_extra_gates > 0) {
                MockCircuits::add_arithmetic_gates(builder, num_extra_gates);
            }
            auto prover_instance = std::make_shared<ProverInstance>(builder);
 
            const size_t dyadic_size = prover_instance->dyadic_size();
            const size_t final_active_idx = prover_instance->get_final_active_wire_idx();
 
            // Invariant: active trace doesn't overlap the disabled head region
            ASSERT_GE(final_active_idx, ProverInstance::TRACE_OFFSET)
                << "final_active_idx (" << final_active_idx << ") is within the disabled head region";
 
            if (prev_dyadic != 0 && dyadic_size > prev_dyadic) {
                EXPECT_EQ(dyadic_size, 2 * prev_dyadic);
 
                // Prove and verify at the tightest packing (right before the jump)
                Builder tight_builder;
                GoblinMockCircuits::construct_simple_circuit(tight_builder);
                MockCircuits::add_arithmetic_gates(tight_builder, num_extra_gates - 1);
                bool verified = this->construct_and_verify_honk_proof(tight_builder);
                EXPECT_TRUE(verified);
 
                found_jump = true;
                break;
            }
 
            prev_dyadic = dyadic_size;
        }
 
        EXPECT_TRUE(found_jump) << "should have found a dyadic size jump within " << baseline_dyadic << " extra gates";
    }
}
 
TYPED_TEST(MegaHonkTests, WitnessPolynomialsMasked)
{
    using Flavor = TypeParam;
    if constexpr (!Flavor::HasZK) {
        GTEST_SKIP() << "Masking only applies to ZK flavors";
    } else {
        using Builder = typename Flavor::CircuitBuilder;
 
        Builder builder;
        GoblinMockCircuits::construct_simple_circuit(builder);
        auto prover_instance = std::make_shared<ProverInstance_<Flavor>>(builder);
 
        auto check_masked = [](const auto& poly, const std::string& label) {
            bool has_masking = false;
            for (size_t j = 0; j < NUM_MASKED_ROWS; j++) {
                has_masking |= !poly[NUM_ZERO_ROWS + j].is_zero();
            }
            EXPECT_TRUE(has_masking) << label << " should be masked";
        };
 
        auto check_unmasked = [](const auto& poly, const std::string& label) {
            for (size_t j = 0; j < NUM_MASKED_ROWS; j++) {
                EXPECT_TRUE(poly[NUM_ZERO_ROWS + j].is_zero()) << label << " should not be masked";
            }
        };
 
        auto& polys = prover_instance->polynomials;
        check_masked(polys.w_l, "w_l");
        check_masked(polys.w_r, "w_r");
        check_masked(polys.w_o, "w_o");
        check_masked(polys.w_4, "w_4");
        check_masked(polys.z_perm, "z_perm");
        check_masked(polys.lookup_read_counts, "lookup_read_counts");
        check_masked(polys.lookup_read_tags, "lookup_read_tags");
        check_masked(polys.lookup_inverses, "lookup_inverses");
        check_unmasked(polys.kernel_calldata, "kernel_calldata");
        check_masked(polys.kernel_calldata_read_counts, "kernel_calldata_read_counts");
        check_masked(polys.kernel_calldata_inverses, "kernel_calldata_inverses");
        check_masked(polys.first_app_calldata, "first_app_calldata");
        check_masked(polys.first_app_calldata_read_counts, "first_app_calldata_read_counts");
        check_masked(polys.first_app_calldata_inverses, "first_app_calldata_inverses");
        check_masked(polys.second_app_calldata, "second_app_calldata");
        check_masked(polys.second_app_calldata_read_counts, "second_app_calldata_read_counts");
        check_masked(polys.second_app_calldata_inverses, "second_app_calldata_inverses");
        check_masked(polys.third_app_calldata, "third_app_calldata");
        check_masked(polys.third_app_calldata_read_counts, "third_app_calldata_read_counts");
        check_masked(polys.third_app_calldata_inverses, "third_app_calldata_inverses");
        check_masked(polys.return_data, "return_data");
        check_masked(polys.return_data_read_counts, "return_data_read_counts");
        check_masked(polys.return_data_inverses, "return_data_inverses");
    }
}
 
TYPED_TEST(MegaHonkTests, RepeatedCommitmentsIndicesCorrect)
{
    using Flavor = TypeParam;
    using Builder = typename Flavor::CircuitBuilder;
    using DefaultIO = stdlib::recursion::honk::DefaultIO<Builder>;
    using CommitmentKey = typename Flavor::CommitmentKey;
    using Commitment = typename Flavor::Commitment;
 
    auto builder = Builder{};
    DefaultIO::add_default(builder);
    auto prover_instance = std::make_shared<ProverInstance_<Flavor>>(builder);
    CommitmentKey ck(prover_instance->dyadic_size());
 
    auto unshifted = prover_instance->polynomials.get_unshifted();
    auto to_be_shifted = prover_instance->polynomials.get_to_be_shifted();
 
    constexpr auto repeated = Flavor::REPEATED_COMMITMENTS;
    ASSERT_EQ(to_be_shifted.size(), repeated.first.count);
 
    // Build the commitment vector exactly as Shplemini does: [Q, unshifted..., to_be_shifted...]
    std::vector<Commitment> commitments;
    commitments.push_back(Commitment::one()); // dummy Q
    for (auto& poly : unshifted) {
        commitments.push_back(ck.commit(poly));
    }
    for (auto& poly : to_be_shifted) {
        commitments.push_back(ck.commit(poly));
    }
 
    // Same offset logic as remove_repeated_commitments
    constexpr size_t offset = Flavor::HasZK ? 2 : 1;
    for (size_t i = 0; i < repeated.first.count; i++) {
        EXPECT_EQ(commitments[repeated.first.original_start + offset + i],
                  commitments[repeated.first.duplicate_start + offset + i])
            << "REPEATED_COMMITMENTS commitment mismatch at index " << i;
    }
}