mega_transcript.test.cpp

Go to the documentation of this file.

#include "barretenberg/ecc/curves/bn254/g1.hpp"
#include "barretenberg/flavor/flavor.hpp"
#include "barretenberg/numeric/bitop/get_msb.hpp"
#include "barretenberg/polynomials/univariate.hpp"
#include "barretenberg/stdlib/special_public_inputs/special_public_inputs.hpp"
#include "barretenberg/stdlib/test_utils/tamper_proof.hpp"
#include "barretenberg/transcript/transcript.hpp"
#include "barretenberg/ultra_honk/prover_instance.hpp"
#include "barretenberg/ultra_honk/ultra_prover.hpp"
#include "barretenberg/ultra_honk/ultra_verifier.hpp"
 
#include <gtest/gtest.h>
 
using namespace bb;
 
using FlavorTypes = ::testing::Types<MegaFlavor, MegaZKFlavor>;
 
template <typename Flavor> class MegaTranscriptTests : public ::testing::Test {
  public:
    static void SetUpTestSuite() { bb::srs::init_file_crs_factory(bb::srs::bb_crs_path()); }
 
    using ProverInstance = ProverInstance_<Flavor>;
    using Prover = UltraProver_<Flavor>;
    using Proof = typename Flavor::Transcript::Proof;
    using FF = Flavor::FF;
 
    static Proof export_serialized_proof(Prover& prover, const size_t num_public_inputs)
    {
        // reset internal variables needed for exporting the proof
        // Note: compute_proof_length_for_export excludes IPA proof length since export_proof appends it separately
        size_t proof_length = compute_proof_length_for_export<Flavor>(num_public_inputs);
        prover.transcript->test_set_proof_parsing_state(0, proof_length);
        return prover.export_proof();
    }
    static TranscriptManifest construct_mega_honk_manifest()
    {
        using Commitment = typename Flavor::Commitment;
        TranscriptManifest manifest_expected;
 
        const size_t virtual_log_n = Flavor::VIRTUAL_LOG_N;
 
        size_t NUM_PUBLIC_INPUTS =
            stdlib::recursion::honk::DefaultIO<typename Flavor::CircuitBuilder>::PUBLIC_INPUTS_SIZE;
        size_t MAX_PARTIAL_RELATION_LENGTH = Flavor::BATCHED_RELATION_PARTIAL_LENGTH;
 
        size_t frs_per_Fr = FrCodec::calc_num_fields<FF>();
        size_t frs_per_G = FrCodec::calc_num_fields<Commitment>();
        size_t frs_per_uni = MAX_PARTIAL_RELATION_LENGTH * frs_per_Fr;
        size_t frs_per_evals = (Flavor::NUM_ALL_ENTITIES)*frs_per_Fr;
 
        size_t round = 0;
        manifest_expected.add_entry(round, "vk_hash", frs_per_Fr);
        manifest_expected.add_entry(round, "public_input_0", frs_per_Fr);
        for (size_t i = 0; i < NUM_PUBLIC_INPUTS; i++) {
            manifest_expected.add_entry(round, "public_input_" + std::to_string(1 + i), frs_per_Fr);
        }
        if constexpr (Flavor::HasZK) {
            manifest_expected.add_entry(round, "Gemini:masking_poly_comm", frs_per_G);
        }
        manifest_expected.add_entry(round, "W_L", frs_per_G);
        manifest_expected.add_entry(round, "W_R", frs_per_G);
        manifest_expected.add_entry(round, "W_O", frs_per_G);
        manifest_expected.add_entry(round, "ECC_OP_WIRE_1", frs_per_G);
        manifest_expected.add_entry(round, "ECC_OP_WIRE_2", frs_per_G);
        manifest_expected.add_entry(round, "ECC_OP_WIRE_3", frs_per_G);
        manifest_expected.add_entry(round, "ECC_OP_WIRE_4", frs_per_G);
        manifest_expected.add_entry(round, "CALLDATA", frs_per_G);
        manifest_expected.add_entry(round, "CALLDATA_READ_COUNTS", frs_per_G);
        manifest_expected.add_entry(round, "CALLDATA_READ_TAGS", frs_per_G);
        manifest_expected.add_entry(round, "SECONDARY_CALLDATA", frs_per_G);
        manifest_expected.add_entry(round, "SECONDARY_CALLDATA_READ_COUNTS", frs_per_G);
        manifest_expected.add_entry(round, "SECONDARY_CALLDATA_READ_TAGS", frs_per_G);
        manifest_expected.add_entry(round, "RETURN_DATA", frs_per_G);
        manifest_expected.add_entry(round, "RETURN_DATA_READ_COUNTS", frs_per_G);
        manifest_expected.add_entry(round, "RETURN_DATA_READ_TAGS", frs_per_G);
        manifest_expected.add_challenge(round, std::array{ "eta", "eta_two", "eta_three" });
 
        round++;
        manifest_expected.add_entry(round, "LOOKUP_READ_COUNTS", frs_per_G);
        manifest_expected.add_entry(round, "LOOKUP_READ_TAGS", frs_per_G);
        manifest_expected.add_entry(round, "W_4", frs_per_G);
        manifest_expected.add_challenge(round, std::array{ "beta", "gamma" });
 
        round++;
        manifest_expected.add_entry(round, "LOOKUP_INVERSES", frs_per_G);
        manifest_expected.add_entry(round, "CALLDATA_INVERSES", frs_per_G);
        manifest_expected.add_entry(round, "SECONDARY_CALLDATA_INVERSES", frs_per_G);
        manifest_expected.add_entry(round, "RETURN_DATA_INVERSES", frs_per_G);
        manifest_expected.add_entry(round, "Z_PERM", frs_per_G);
 
        manifest_expected.add_challenge(round, "alpha");
        round++;
 
        manifest_expected.add_challenge(round, "Sumcheck:gate_challenge");
        round++;
 
        if constexpr (Flavor::HasZK) {
            manifest_expected.add_entry(round, "Libra:concatenation_commitment", frs_per_G);
            manifest_expected.add_entry(round, "Libra:Sum", frs_per_Fr);
            manifest_expected.add_challenge(round, "Libra:Challenge");
            round++;
        }
 
        for (size_t i = 0; i < virtual_log_n; ++i) {
            std::string idx = std::to_string(i);
            manifest_expected.add_entry(round, "Sumcheck:univariate_" + idx, frs_per_uni);
            std::string label = "Sumcheck:u_" + idx;
            manifest_expected.add_challenge(round, label);
            round++;
        }
 
        manifest_expected.add_entry(round, "Sumcheck:evaluations", frs_per_evals);
 
        if constexpr (Flavor::HasZK) {
            manifest_expected.add_entry(round, "Libra:claimed_evaluation", frs_per_Fr);
            manifest_expected.add_entry(round, "Libra:grand_sum_commitment", frs_per_G);
            manifest_expected.add_entry(round, "Libra:quotient_commitment", frs_per_G);
        }
 
        manifest_expected.add_challenge(round, "rho");
 
        round++;
        for (size_t i = 1; i < virtual_log_n; ++i) {
            std::string idx = std::to_string(i);
            manifest_expected.add_entry(round, "Gemini:FOLD_" + idx, frs_per_G);
        }
        manifest_expected.add_challenge(round, "Gemini:r");
        round++;
        for (size_t i = 1; i <= virtual_log_n; ++i) {
            std::string idx = std::to_string(i);
            manifest_expected.add_entry(round, "Gemini:a_" + idx, frs_per_Fr);
        }
        if constexpr (Flavor::HasZK) {
            manifest_expected.add_entry(round, "Libra:concatenation_eval", frs_per_Fr);
            manifest_expected.add_entry(round, "Libra:shifted_grand_sum_eval", frs_per_Fr);
            manifest_expected.add_entry(round, "Libra:grand_sum_eval", frs_per_Fr);
            manifest_expected.add_entry(round, "Libra:quotient_eval", frs_per_Fr);
        }
 
        manifest_expected.add_challenge(round, "Shplonk:nu");
        round++;
        manifest_expected.add_entry(round, "Shplonk:Q", frs_per_G);
        manifest_expected.add_challenge(round, "Shplonk:z");
 
        round++;
        manifest_expected.add_entry(round, "KZG:W", frs_per_G);
        manifest_expected.add_challenge(round, "KZG:masking_challenge");
 
        return manifest_expected;
    }
 
    void generate_test_circuit(auto& builder)
    {
        // Add some ecc op gates
        for (size_t i = 0; i < 3; ++i) {
            auto point = Flavor::Curve::AffineElement::one() * FF::random_element();
            auto scalar = FF::random_element();
            builder.queue_ecc_mul_accum(point, scalar);
        }
        builder.queue_ecc_eq();
 
        // Add one conventional gates that utilize public inputs
        FF a = FF::random_element();
        FF b = FF::random_element();
        FF c = FF::random_element();
        FF d = a + b + c;
        uint32_t a_idx = builder.add_public_variable(a);
        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, FF(1), FF(1), FF(1), FF(-1), FF(0) });
        stdlib::recursion::honk::DefaultIO<typename Flavor::CircuitBuilder>::add_default(builder);
    }
};
TYPED_TEST_SUITE(MegaTranscriptTests, FlavorTypes);
TYPED_TEST(MegaTranscriptTests, ProverManifestConsistency)
{
    using Flavor = TypeParam;
    using ProverInstance = ProverInstance_<Flavor>;
 
    using Prover = UltraProver_<Flavor>;
    // Construct a simple circuit of size n = 8 (i.e. the minimum circuit size)
    auto builder = typename Flavor::CircuitBuilder();
    TestFixture::generate_test_circuit(builder);
 
    // Automatically generate a transcript manifest by constructing a proof
    auto prover_instance = std::make_shared<ProverInstance>(builder);
    auto verification_key = std::make_shared<typename Flavor::VerificationKey>(prover_instance->get_precomputed());
    Prover prover(prover_instance, verification_key);
    prover.transcript->enable_manifest();
    auto proof = prover.construct_proof();
 
    // Check that the prover generated manifest agrees with the manifest hard coded in this suite
    auto manifest_expected = TestFixture::construct_mega_honk_manifest();
    auto prover_manifest = prover.transcript->get_manifest();
    // Note: a manifest can be printed using manifest.print()
    ASSERT_GT(manifest_expected.size(), 0);
    for (size_t round = 0; round < manifest_expected.size(); ++round) {
        if (prover_manifest[round] != manifest_expected[round]) {
            info("Prover manifest discrepency in round ", round);
            info("Prover manifest:");
            prover_manifest[round].print();
            info("Expected manifest:");
            manifest_expected[round].print();
            FAIL();
        }
    }
}
 
TYPED_TEST(MegaTranscriptTests, VerifierManifestConsistency)
{
    using Flavor = TypeParam;
    using ProverInstance = ProverInstance_<Flavor>;
    using VerificationKey = Flavor::VerificationKey;
    using Prover = UltraProver_<Flavor>;
    using Verifier = UltraVerifier_<Flavor, DefaultIO>;
 
    // Construct a simple circuit of size n = 8 (i.e. the minimum circuit size)
    auto builder = typename Flavor::CircuitBuilder();
    TestFixture::generate_test_circuit(builder);
 
    // Automatically generate a transcript manifest in the prover by constructing a proof
    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);
    prover.transcript->enable_manifest();
    auto proof = prover.construct_proof();
 
    // Automatically generate a transcript manifest in the verifier by verifying a proof
    auto verifier_transcript = std::make_shared<typename Flavor::Transcript>();
    verifier_transcript->enable_manifest();
    Verifier verifier(vk_and_hash, verifier_transcript);
    [[maybe_unused]] auto verifier_output = verifier.verify_proof(proof);
 
    // Check consistency between the manifests generated by the prover and verifier
    auto prover_manifest = prover.transcript->get_manifest();
 
    auto verifier_manifest = verifier.get_transcript()->get_manifest();
 
    // Note: a manifest can be printed using manifest.print()
    ASSERT_GT(prover_manifest.size(), 0);
    for (size_t round = 0; round < prover_manifest.size(); ++round) {
        if (prover_manifest[round] != verifier_manifest[round]) {
            info("Prover/Verifier manifest discrepency in round ", round);
            prover_manifest[round].print();
            verifier_manifest[round].print();
            FAIL();
        }
    }
}
 
TYPED_TEST(MegaTranscriptTests, ChallengeGenerationTest)
{
    using Flavor = TypeParam;
    using FF = Flavor::FF;
    // initialized with random value sent to verifier
    auto transcript = Flavor::Transcript::prover_init_empty();
    // test a bunch of challenges
    std::vector<std::string> challenge_labels{ "a", "b", "c", "d", "e", "f" };
    auto challenges = transcript->template get_challenges<FF>(challenge_labels);
    // check they are not 0
    for (size_t i = 0; i < challenges.size(); ++i) {
        ASSERT_NE(challenges[i], 0) << "Challenge " << i << " is 0";
    }
    constexpr uint32_t random_val{ 17 }; // arbitrary
    transcript->send_to_verifier("random val", random_val);
    // test more challenges
    challenge_labels = { "a", "b", "c" };
    challenges = transcript->template get_challenges<FF>(challenge_labels);
    ASSERT_NE(challenges[0], 0) << "Challenge a is 0";
    ASSERT_NE(challenges[1], 0) << "Challenge b is 0";
    ASSERT_NE(challenges[2], 0) << "Challenge c is 0";
}
 
TYPED_TEST(MegaTranscriptTests, StructureTest)
{
    using Flavor = TypeParam;
    using ProverInstance = ProverInstance_<Flavor>;
    using VerificationKey = Flavor::VerificationKey;
    using FF = Flavor::FF;
    using Commitment = typename Flavor::Commitment;
    using Prover = UltraProver_<Flavor>;
    using Verifier = UltraVerifier_<Flavor, DefaultIO>;
 
    // Construct a simple circuit of size n = 8 (i.e. the minimum circuit size)
    typename Flavor::CircuitBuilder builder;
    this->generate_test_circuit(builder);
 
    // Automatically generate a transcript manifest by constructing a proof
    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);
    auto proof = prover.construct_proof();
    Verifier verifier(vk_and_hash);
    EXPECT_TRUE(verifier.verify_proof(proof).result);
 
    const size_t virtual_log_n = Flavor::VIRTUAL_LOG_N;
 
    // Use StructuredProof test utility to deserialize/serialize proof data
    StructuredProof<Flavor> proof_structure;
 
    // try deserializing and serializing with no changes and check proof is still valid
    proof_structure.deserialize(
        prover.transcript->test_get_proof_data(), verification_key->num_public_inputs, virtual_log_n);
    proof_structure.serialize(prover.transcript->test_get_proof_data(), virtual_log_n);
 
    proof = TestFixture::export_serialized_proof(prover, prover_instance->num_public_inputs());
    // we have changed nothing so proof is still valid
    Verifier verifier2(vk_and_hash);
    EXPECT_TRUE(verifier2.verify_proof(proof).result);
 
    Commitment one_group_val = Commitment::one();
    FF rand_val = FF::random_element();
    proof_structure.z_perm_comm = one_group_val * rand_val; // choose random object to modify
    proof = TestFixture::export_serialized_proof(prover, prover_instance->num_public_inputs());
    // we have not serialized it back to the proof so it should still be fine
    Verifier verifier3(vk_and_hash);
    EXPECT_TRUE(verifier3.verify_proof(proof).result);
 
    proof_structure.serialize(prover.transcript->test_get_proof_data(), virtual_log_n);
    proof = TestFixture::export_serialized_proof(prover, prover_instance->num_public_inputs());
    // the proof is now wrong after serializing it
    Verifier verifier4(vk_and_hash);
    EXPECT_FALSE(verifier4.verify_proof(proof).result);
 
    proof_structure.deserialize(
        prover.transcript->test_get_proof_data(), verification_key->num_public_inputs, virtual_log_n);
    EXPECT_EQ(static_cast<Commitment>(proof_structure.z_perm_comm), one_group_val * rand_val);
}