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/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();
 
        // Add gates one at a time until the dyadic size doubles
        size_t prev_dyadic = 0;
        size_t prev_final_active_idx = 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();
            const size_t first_masked_row = dyadic_size - NUM_MASKED_ROWS;
 
            // Invariant: lagrange_last must be strictly before the masking area
            ASSERT_LT(final_active_idx, first_masked_row)
                << "lagrange_last (at " << final_active_idx << ") overlaps masking area (starting at "
                << first_masked_row << ") with num_extra_gates=" << num_extra_gates;
 
            // Sufficient headroom for disabled rows
            ASSERT_GE(dyadic_size - final_active_idx - 1, static_cast<size_t>(NUM_DISABLED_ROWS_IN_SUMCHECK));
 
            if (prev_dyadic != 0 && dyadic_size > prev_dyadic) {
                EXPECT_EQ(dyadic_size, 2 * prev_dyadic);
                EXPECT_LE(prev_dyadic - prev_final_active_idx - 1,
                          2 * static_cast<size_t>(NUM_DISABLED_ROWS_IN_SUMCHECK));
 
                // 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);
                auto tight_instance = std::make_shared<ProverInstance>(tight_builder);
                bool verified = this->construct_and_verify_honk_proof(tight_builder);
                EXPECT_TRUE(verified);
 
                found_jump = true;
                break;
            }
 
            prev_dyadic = dyadic_size;
            prev_final_active_idx = final_active_idx;
        }
 
        EXPECT_TRUE(found_jump) << "should have found a dyadic size jump within " << baseline_dyadic << " extra gates";
    }
}