bc_hashing.test.cpp

Go to the documentation of this file.

#include <gmock/gmock.h>
#include <gtest/gtest.h>
 
#include <cstdint>
#include <memory>
#include <vector>
 
#include "barretenberg/vm2/constraining/flavor_settings.hpp"
#include "barretenberg/vm2/constraining/testing/check_relation.hpp"
#include "barretenberg/vm2/generated/columns.hpp"
#include "barretenberg/vm2/generated/relations/bc_hashing.hpp"
#include "barretenberg/vm2/generated/relations/lookups_bc_hashing.hpp"
#include "barretenberg/vm2/generated/relations/poseidon2_hash.hpp"
#include "barretenberg/vm2/simulation/gadgets/poseidon2.hpp"
#include "barretenberg/vm2/simulation/lib/contract_crypto.hpp"
#include "barretenberg/vm2/simulation/testing/mock_execution_id_manager.hpp"
#include "barretenberg/vm2/simulation/testing/mock_gt.hpp"
#include "barretenberg/vm2/testing/fixtures.hpp"
#include "barretenberg/vm2/testing/macros.hpp"
#include "barretenberg/vm2/tracegen/bytecode_trace.hpp"
#include "barretenberg/vm2/tracegen/lib/lookup_builder.hpp"
#include "barretenberg/vm2/tracegen/poseidon2_trace.hpp"
#include "barretenberg/vm2/tracegen/precomputed_trace.hpp"
#include "barretenberg/vm2/tracegen/test_trace_container.hpp"
 
namespace bb::avm2::constraining {
namespace {
 
using ::testing::StrictMock;
 
using testing::random_bytes;
using testing::random_fields;
 
using simulation::compute_public_bytecode_first_field;
using simulation::EventEmitter;
using simulation::MockExecutionIdManager;
using simulation::MockGreaterThan;
using simulation::Poseidon2;
using simulation::Poseidon2HashEvent;
using simulation::Poseidon2PermutationEvent;
using simulation::Poseidon2PermutationMemoryEvent;
using tracegen::BytecodeTraceBuilder;
using tracegen::Poseidon2TraceBuilder;
using tracegen::PrecomputedTraceBuilder;
using tracegen::TestTraceContainer;
 
using FF = AvmFlavorSettings::FF;
using C = Column;
using bc_hashing = bb::avm2::bc_hashing<FF>;
using bc_decomposition = bb::avm2::bc_decomposition<FF>;
using RawPoseidon2 = crypto::Poseidon2<crypto::Poseidon2Bn254ScalarFieldParams>;
 
class BytecodeHashingConstrainingTest : public ::testing::Test {
  public:
    EventEmitter<Poseidon2HashEvent> hash_event_emitter;
    EventEmitter<Poseidon2PermutationEvent> perm_event_emitter;
    EventEmitter<Poseidon2PermutationMemoryEvent> perm_mem_event_emitter;
 
    StrictMock<MockGreaterThan> mock_gt;
    StrictMock<MockExecutionIdManager> mock_execution_id_manager;
 
    Poseidon2TraceBuilder poseidon2_builder;
    PrecomputedTraceBuilder precomputed_builder;
    BytecodeTraceBuilder builder;
};
 
class BytecodeHashingConstrainingTestTraceHelper : public BytecodeHashingConstrainingTest {
  public:
    TestTraceContainer process_bc_hashing_trace(std::vector<std::vector<FF>> all_bytecode_fields,
                                                std::vector<FF> bytecode_ids,
                                                std::vector<size_t> bytecode_size_in_bytes)
    {
        // Note: this helper expects bytecode fields without the prepended separator and does not complete decomposition
        Poseidon2 poseidon2 = Poseidon2(
            mock_execution_id_manager, mock_gt, hash_event_emitter, perm_event_emitter, perm_mem_event_emitter);
        TestTraceContainer trace({
            { { C::precomputed_first_row, 1 } },
        });
        uint32_t row = 1;
        for (uint32_t j = 0; j < all_bytecode_fields.size(); j++) {
            uint32_t pc_index = 0;
            auto bytecode_fields = all_bytecode_fields[j];
            auto bytecode_id = bytecode_ids[j];
            bytecode_fields.insert(bytecode_fields.begin(),
                                   compute_public_bytecode_first_field(bytecode_size_in_bytes[j]));
            poseidon2.hash(bytecode_fields); // Required to populate Poseidon2 hash events
            auto bytecode_field_at = [&bytecode_fields](size_t i) -> FF {
                return i < bytecode_fields.size() ? bytecode_fields[i] : 0;
            };
            auto padding_amount = (3 - (bytecode_fields.size() % 3)) % 3;
            auto num_rounds = (bytecode_fields.size() + padding_amount) / 3;
            for (uint32_t i = 0; i < bytecode_fields.size(); i += 3) {
                bool start = i == 0;
                bool end = i + 3 >= bytecode_fields.size();
                auto pc_index_1 = start ? 0 : pc_index + 31;
                trace.set(row,
                          { {
                              { C::bc_hashing_bytecode_id, bytecode_id },
                              { C::bc_hashing_end, end },
                              { C::bc_hashing_size_in_bytes, bytecode_size_in_bytes[j] },
                              { C::bc_hashing_input_len, bytecode_fields.size() },
                              { C::bc_hashing_rounds_rem, num_rounds },
                              { C::bc_hashing_packed_fields_0, bytecode_field_at(i) },
                              { C::bc_hashing_packed_fields_1, bytecode_field_at(i + 1) },
                              { C::bc_hashing_packed_fields_2, bytecode_field_at(i + 2) },
                              { C::bc_hashing_pc_index, pc_index },
                              { C::bc_hashing_pc_index_1, pc_index_1 },
                              { C::bc_hashing_pc_index_2, pc_index_1 + 31 },
                              { C::bc_hashing_sel, 1 },
                              { C::bc_hashing_sel_not_padding_1, end && padding_amount == 2 ? 0 : 1 },
                              { C::bc_hashing_sel_not_padding_2, end && padding_amount > 0 ? 0 : 1 },
                              { C::bc_hashing_padding, padding_amount },
                              { C::bc_hashing_sel_not_start, !start },
                              { C::bc_hashing_start, start },
                          } });
                row++;
                num_rounds--;
                pc_index = pc_index_1 + 62;
            }
        }
        precomputed_builder.process_misc(trace, 256);
        poseidon2_builder.process_hash(hash_event_emitter.dump_events(), trace);
        return trace;
    }
};
 
TEST_F(BytecodeHashingConstrainingTest, EmptyRow)
{
    check_relation<bc_hashing>(testing::empty_trace());
}
 
TEST_F(BytecodeHashingConstrainingTest, SingleBytecodeHashOneRow)
{
    Poseidon2 poseidon2 =
        Poseidon2(mock_execution_id_manager, mock_gt, hash_event_emitter, perm_event_emitter, perm_mem_event_emitter);
    std::vector<FF> bytecode_fields = { 1, 2 };
    std::vector<uint8_t> bytecode = {};
 
    for (auto bytecode_field : bytecode_fields) {
        auto bytes = to_buffer(bytecode_field);
        // Each field elt of encoded bytecode represents 31 bytes, hence start at +1:
        bytecode.insert(bytecode.end(), bytes.begin() + 1, bytes.end());
    }
    auto sep = compute_public_bytecode_first_field(bytecode.size());
    auto hash = poseidon2.hash({ sep, 1, 2 });
 
    auto trace = TestTraceContainer({
        { { C::precomputed_first_row, 1 } },
        {
            { C::bc_hashing_size_in_bytes, bytecode.size() },
            { C::bc_hashing_input_len, 3 },
            { C::bc_hashing_end, 1 },
            { C::bc_hashing_packed_fields_0, sep },
            { C::bc_hashing_packed_fields_1, 1 },
            { C::bc_hashing_packed_fields_2, 2 },
            { C::bc_hashing_pc_index_1, 0 },
            { C::bc_hashing_pc_index_2, 31 },
            { C::bc_hashing_sel_not_padding_1, 1 },
            { C::bc_hashing_sel_not_padding_2, 1 },
            { C::bc_hashing_bytecode_id, hash },
            { C::bc_hashing_pc_index, 0 },
            { C::bc_hashing_rounds_rem, 1 },
            { C::bc_hashing_sel, 1 },
            { C::bc_hashing_start, 1 },
        },
    });
 
    precomputed_builder.process_misc(trace, 3);
    builder.process_decomposition(
        { { .bytecode_id = hash, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
    poseidon2_builder.process_hash(hash_event_emitter.dump_events(), trace);
 
    check_relation<bc_hashing>(trace);
    check_all_interactions<BytecodeTraceBuilder>(trace);
}
 
TEST_F(BytecodeHashingConstrainingTestTraceHelper, SingleBytecodeHash100Fields)
{
    // The hardcoded value is taken from noir-projects/labs/aztec-nr/aztec/src/hash.nr:
    FF hash = FF("0x09348974e76c3602893d7a4b4bb52c2ec746f1ade5004ac471d0fbb4587a81a6");
 
    std::vector<FF> bytecode_fields = {};
    for (uint32_t i = 1; i < 100; i++) {
        bytecode_fields.push_back(FF(i));
    }
    std::vector<uint8_t> bytecode = {};
    for (auto bytecode_field : bytecode_fields) {
        auto bytes = to_buffer(bytecode_field);
        // Each field elt of encoded bytecode represents 31 bytes, but to_buffer returns 32, hence start at +1:
        bytecode.insert(bytecode.end(), bytes.begin() + 1, bytes.end());
    }
    TestTraceContainer trace = process_bc_hashing_trace({ bytecode_fields }, { hash }, { bytecode.size() });
 
    builder.process_decomposition(
        { { .bytecode_id = hash, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
 
    check_relation<bc_hashing>(trace);
    check_all_interactions<BytecodeTraceBuilder>(trace);
}
 
TEST_F(BytecodeHashingConstrainingTestTraceHelper, SingleBytecodeHashMax)
{
    std::vector<uint8_t> bytecode = random_bytes(static_cast<size_t>(31 * MAX_PACKED_PUBLIC_BYTECODE_SIZE_IN_FIELDS));
    std::vector<FF> bytecode_fields = simulation::encode_bytecode(bytecode);
    std::vector<FF> prepended_fields = { compute_public_bytecode_first_field(bytecode.size()) };
    prepended_fields.insert(prepended_fields.end(), bytecode_fields.begin(), bytecode_fields.end());
    FF hash = RawPoseidon2::hash(prepended_fields);
 
    TestTraceContainer trace = process_bc_hashing_trace({ bytecode_fields }, { hash }, { bytecode.size() });
    builder.process_decomposition(
        { { .bytecode_id = hash, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
 
    check_relation<bc_hashing>(trace);
    check_all_interactions<BytecodeTraceBuilder>(trace);
}
 
TEST_F(BytecodeHashingConstrainingTestTraceHelper, MultipleBytecodeHash)
{
    // 40 bytes => hash 3 fields, no padding
    // 20 bytes => hash 2 fields, one padding field
    // 80 bytes => hash 4 fields, two padding fields
    std::vector<std::vector<uint8_t>> all_bytecode = { random_bytes(40), random_bytes(20), random_bytes(80) };
    std::vector<std::vector<FF>> all_bytecode_fields;
    std::vector<FF> hashes;
    std::vector<size_t> byte_sizes;
    for (uint32_t i = 0; i < all_bytecode.size(); i++) {
        all_bytecode_fields.push_back(simulation::encode_bytecode(all_bytecode[i]));
        std::vector<FF> prepended_fields = { compute_public_bytecode_first_field(all_bytecode[i].size()) };
        prepended_fields.insert(prepended_fields.end(), all_bytecode_fields[i].begin(), all_bytecode_fields[i].end());
        hashes.push_back(RawPoseidon2::hash(prepended_fields));
        byte_sizes.push_back(all_bytecode[i].size());
    }
 
    TestTraceContainer trace = process_bc_hashing_trace(all_bytecode_fields, hashes, byte_sizes);
    std::vector<simulation::BytecodeDecompositionEvent> decomp_events = {};
 
    for (uint32_t j = 0; j < all_bytecode.size(); j++) {
        const auto& bytecode = all_bytecode[j];
        decomp_events.push_back(simulation::BytecodeDecompositionEvent{
            .bytecode_id = hashes[j], .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) });
    }
    builder.process_decomposition({ decomp_events }, trace);
 
    check_relation<bc_hashing>(trace);
    check_all_interactions<BytecodeTraceBuilder>(trace);
}
 
TEST_F(BytecodeHashingConstrainingTest, BytecodeInteractions)
{
    TestTraceContainer trace({
        { { C::precomputed_first_row, 1 } },
    });
 
    std::vector<uint8_t> bytecode = random_bytes(123);
    std::vector<FF> fields = simulation::encode_bytecode(bytecode);
    std::vector<FF> prepended_fields = { compute_public_bytecode_first_field(bytecode.size()) };
    prepended_fields.insert(prepended_fields.end(), fields.begin(), fields.end());
    FF hash = RawPoseidon2::hash(prepended_fields);
 
    builder.process_hashing({ { .bytecode_id = hash,
                                .bytecode_length_in_bytes = static_cast<uint32_t>(bytecode.size()),
                                .bytecode_fields = fields } },
                            trace);
    builder.process_decomposition(
        { { .bytecode_id = hash, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
 
    tracegen::MultiPermutationBuilder<perm_bc_hashing_get_packed_field_0_settings,
                                      perm_bc_hashing_get_packed_field_1_settings,
                                      perm_bc_hashing_get_packed_field_2_settings>
        perm_builder(C::bc_decomposition_sel_packed);
    perm_builder.process(trace);
 
    check_multipermutation_interaction<BytecodeTraceBuilder,
                                       perm_bc_hashing_get_packed_field_0_settings,
                                       perm_bc_hashing_get_packed_field_1_settings,
                                       perm_bc_hashing_get_packed_field_2_settings>(trace);
    check_relation<bc_hashing>(trace);
    check_relation<bb::avm2::bc_decomposition<FF>>(trace);
}
 
// Negative test where latch == 1 and sel == 0
TEST_F(BytecodeHashingConstrainingTest, NegativeLatchNotSel)
{
    TestTraceContainer trace;
    trace.set(0,
              { {
                  { C::bc_hashing_end, 1 },
                  { C::bc_hashing_sel, 1 },
              } });
 
    check_relation<bc_hashing>(trace, bc_hashing::SR_SEL_ON_START_OR_END);
    trace.set(C::bc_hashing_sel, 0, 0); // Mutate to wrong value
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_SEL_ON_START_OR_END),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_SEL_ON_START_OR_END));
}
 
TEST_F(BytecodeHashingConstrainingTest, NegativeInvalidStartAfterLatch)
{
    TestTraceContainer trace({
        { { C::precomputed_first_row, 1 } },
    });
    builder.process_hashing(
        { { .bytecode_id = 1, .bytecode_length_in_bytes = 62, .bytecode_fields = random_fields(2) },
          { .bytecode_id = 2, .bytecode_length_in_bytes = 93, .bytecode_fields = random_fields(3) } },
        trace);
    check_relation<bc_hashing>(trace, bc_hashing::SR_START_AFTER_LATCH);
 
    // Row = 2 is the start of the hashing for bytecode id = 2
    trace.set(Column::bc_hashing_start, 2, 0);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_START_AFTER_LATCH),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_START_AFTER_LATCH));
}
 
TEST_F(BytecodeHashingConstrainingTest, NegativeInvalidPCIncrement)
{
    TestTraceContainer trace({
        { { C::precomputed_first_row, 1 } },
    });
    builder.process_hashing(
        {
            { .bytecode_id = 1, .bytecode_length_in_bytes = 124, .bytecode_fields = random_fields(4) },
        },
        trace);
    check_relation<bc_hashing>(trace, bc_hashing::SR_PC_INCREMENTS);
    check_relation<bc_hashing>(trace, bc_hashing::SR_PC_INCREMENTS_1);
    check_relation<bc_hashing>(trace, bc_hashing::SR_PC_INCREMENTS_2);
 
    // This is the last row of the bytecode hashing, pc_index should be 62
    trace.set(Column::bc_hashing_pc_index, 2, 10);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_PC_INCREMENTS),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_PC_INCREMENTS));
    trace.set(Column::bc_hashing_pc_index, 2, 62);
    trace.set(Column::bc_hashing_pc_index_1, 2, 97);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_PC_INCREMENTS_1),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_PC_INCREMENTS_1));
    trace.set(Column::bc_hashing_pc_index_1, 2, 93);
    // The next pc_index should be 124 = pc_index_1 + 31
    check_relation<bc_hashing>(trace, bc_hashing::SR_PC_INCREMENTS_2);
    trace.set(Column::bc_hashing_pc_index_2, 2, 10);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_PC_INCREMENTS_2),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_PC_INCREMENTS_2));
}
 
TEST_F(BytecodeHashingConstrainingTest, NegativeStartIsSeparator)
{
    TestTraceContainer trace({
        { { C::precomputed_first_row, 1 } },
    });
    builder.process_hashing({ { .bytecode_id = 1, .bytecode_length_in_bytes = 62, .bytecode_fields = { 1, 2 } } },
                            trace);
    check_relation<bc_hashing>(trace, bc_hashing::SR_START_IS_FIRST_FIELD);
 
    // Row = 1 is the start of the hashing for bytecode id = 1
    trace.set(Column::bc_hashing_packed_fields_0, 1, 1);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_START_IS_FIRST_FIELD),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_START_IS_FIRST_FIELD));
}
 
TEST_F(BytecodeHashingConstrainingTest, NegativeBytecodeInteraction)
{
    TestTraceContainer trace({
        { { C::precomputed_first_row, 1 } },
    });
 
    std::vector<uint8_t> bytecode = random_bytes(150);
    std::vector<FF> fields = simulation::encode_bytecode(bytecode);
    std::vector<FF> prepended_fields = { compute_public_bytecode_first_field(bytecode.size()) };
    prepended_fields.insert(prepended_fields.end(), fields.begin(), fields.end());
    FF hash = RawPoseidon2::hash(prepended_fields);
 
    builder.process_hashing({ { .bytecode_id = hash, .bytecode_length_in_bytes = 150, .bytecode_fields = fields } },
                            trace);
    builder.process_decomposition(
        { { .bytecode_id = hash, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
    tracegen::MultiPermutationBuilder<perm_bc_hashing_get_packed_field_0_settings,
                                      perm_bc_hashing_get_packed_field_1_settings,
                                      perm_bc_hashing_get_packed_field_2_settings>
        perm_builder(C::bc_decomposition_sel_packed);
    perm_builder.process(trace);
 
    // Row = 2 constrains the hashing for the last 3 fields of the bytecode (no padding)
    // Modify the pc index for the permutation of the first packed field of row 2 (= prepended_fields[3])
    trace.set(Column::bc_hashing_pc_index, 2, 0);
    EXPECT_THROW_WITH_MESSAGE((check_multipermutation_interaction<BytecodeTraceBuilder,
                                                                  perm_bc_hashing_get_packed_field_0_settings,
                                                                  perm_bc_hashing_get_packed_field_1_settings,
                                                                  perm_bc_hashing_get_packed_field_2_settings>(trace)),
                              "Failed.*GET_PACKED_FIELD_0. Could not find tuple in destination.");
    trace.set(Column::bc_hashing_pc_index, 2, 62);
    // Modify the field value for the permutation of the second packed field of row 2 (= prepended_fields[4])
    trace.set(Column::bc_hashing_packed_fields_1, 2, 0);
    EXPECT_THROW_WITH_MESSAGE((check_multipermutation_interaction<BytecodeTraceBuilder,
                                                                  perm_bc_hashing_get_packed_field_0_settings,
                                                                  perm_bc_hashing_get_packed_field_1_settings,
                                                                  perm_bc_hashing_get_packed_field_2_settings>(trace)),
                              "Failed.*GET_PACKED_FIELD_1. Could not find tuple in destination.");
    trace.set(Column::bc_hashing_packed_fields_1, 2, prepended_fields[4]);
 
    // Modify the pc index for the permutation of the third packed field of row 2 (= fields[5])
    trace.set(Column::bc_hashing_pc_index_2, 2, 0);
    EXPECT_THROW_WITH_MESSAGE((check_multipermutation_interaction<BytecodeTraceBuilder,
                                                                  perm_bc_hashing_get_packed_field_0_settings,
                                                                  perm_bc_hashing_get_packed_field_1_settings,
                                                                  perm_bc_hashing_get_packed_field_2_settings>(trace)),
                              "Failed.*GET_PACKED_FIELD_2. Could not find tuple in destination.");
 
    // Reset for next test:
    trace.set(Column::bc_hashing_pc_index_2, 2, 124);
    check_multipermutation_interaction<BytecodeTraceBuilder,
                                       perm_bc_hashing_get_packed_field_0_settings,
                                       perm_bc_hashing_get_packed_field_1_settings,
                                       perm_bc_hashing_get_packed_field_2_settings>(trace);
 
    // Modify the bytecode id for the permutation:
    trace.set(Column::bc_hashing_bytecode_id, 2, 0);
    EXPECT_THROW_WITH_MESSAGE((check_multipermutation_interaction<BytecodeTraceBuilder,
                                                                  perm_bc_hashing_get_packed_field_0_settings,
                                                                  perm_bc_hashing_get_packed_field_1_settings,
                                                                  perm_bc_hashing_get_packed_field_2_settings>(trace)),
                              "Failed.*GET_PACKED_FIELD_.*. Could not find tuple in destination.");
}
 
TEST_F(BytecodeHashingConstrainingTestTraceHelper, NegativePaddingSelectors)
{
    // 80 bytes => hash 4 fields, two padding fields
    std::vector<uint8_t> bytecode = random_bytes(80);
    std::vector<FF> fields = simulation::encode_bytecode(bytecode);
 
    TestTraceContainer trace = process_bc_hashing_trace({ fields }, { 1 }, { bytecode.size() });
    builder.process_decomposition(
        { { .bytecode_id = 1, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
 
    // Row = 2 constrains the hashing for the last field of the bytecode, plus 2 padding fields
    // We cannot have padding anywhere but the last hashing row (= latch):
    trace.set(Column::bc_hashing_end, 2, 0);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_PADDING_END),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_PADDING_END));
    trace.set(Column::bc_hashing_end, 2, 1);
 
    // We cannot have packed_fields_1 is padding, but packed_fields_2 is not:
    trace.set(Column::bc_hashing_sel_not_padding_2, 2, 1);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_PADDING_CONSISTENCY),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_PADDING_CONSISTENCY));
    trace.set(Column::bc_hashing_sel_not_padding_2, 2, 0);
 
    // We cannot have any padding with non-zero values:
    trace.set(Column::bc_hashing_packed_fields_1, 2, 1);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_PADDED_BY_ZERO_1),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_PADDED_BY_ZERO_1));
    trace.set(Column::bc_hashing_packed_fields_2, 2, 1);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_PADDED_BY_ZERO_2),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_PADDED_BY_ZERO_2));
}
 
TEST_F(BytecodeHashingConstrainingTestTraceHelper, NegativePaddingUnder)
{
    // 80 bytes => hash 4 fields, two padding fields
    std::vector<uint8_t> bytecode = random_bytes(80);
    std::vector<FF> fields = simulation::encode_bytecode(bytecode);
    std::vector<FF> prepended_fields = { compute_public_bytecode_first_field(bytecode.size()) };
    prepended_fields.insert(prepended_fields.end(), fields.begin(), fields.end());
    FF hash = RawPoseidon2::hash(prepended_fields);
 
    TestTraceContainer trace = process_bc_hashing_trace({ fields }, { hash }, { bytecode.size() });
    builder.process_decomposition(
        { { .bytecode_id = hash, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
 
    // Row = 2 constrains the hashing for the last field of the bytecode, plus 2 padding fields
    // We cannot claim there is only one padding field:
    trace.set(Column::bc_hashing_sel_not_padding_1, 2, 1);
    // This will initially fail, because pc_at_final_field does not correspond to the pc at field 1...
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_PADDING_COMPUTATION),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_PADDING_COMPUTATION));
    // ...setting it to that padding = 1 and input_len = 5 will make all relations to pass...
    trace.set(Column::bc_hashing_padding, 2, 1);
    trace.set(Column::bc_hashing_padding, 1, 1);
    trace.set(Column::bc_hashing_input_len, 1, 5);
    check_relation<bc_hashing>(trace);
    // ...but the lookup to find field 1 will fail...
    EXPECT_THROW_WITH_MESSAGE((check_multipermutation_interaction<BytecodeTraceBuilder,
                                                                  perm_bc_hashing_get_packed_field_0_settings,
                                                                  perm_bc_hashing_get_packed_field_1_settings,
                                                                  perm_bc_hashing_get_packed_field_2_settings>(trace)),
                              "Failed.*GET_PACKED_FIELD_1. Could not find tuple in destination.");
}
 
TEST_F(BytecodeHashingConstrainingTestTraceHelper, NegativePaddingOver)
{
    // 100 bytes => hash 5 fields, one padding field
    std::vector<uint8_t> bytecode = random_bytes(100);
    std::vector<FF> fields = simulation::encode_bytecode(bytecode);
    std::vector<FF> prepended_fields = { compute_public_bytecode_first_field(bytecode.size()) };
    prepended_fields.insert(prepended_fields.end(), fields.begin(), fields.end());
    FF hash = RawPoseidon2::hash(prepended_fields);
 
    TestTraceContainer trace = process_bc_hashing_trace({ fields }, { hash }, { bytecode.size() });
    builder.process_decomposition(
        { { .bytecode_id = hash, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
 
    // Row = 2 constrains the hashing for the last fields of the bytecode, plus 1 padding field
    // We cannot claim there are two padding fields (to attempt to skip processing the last bytecode field):
    trace.set(Column::bc_hashing_sel_not_padding_1, 2, 0);
    // Padding computation will fail:
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_PADDING_COMPUTATION),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_PADDING_COMPUTATION));
    // If we set padding = 2, fields_1 = 0, and input_len = 4, all relations will pass.
    trace.set(Column::bc_hashing_padding, 2, 2);
    trace.set(Column::bc_hashing_padding, 1, 2);
    trace.set(Column::bc_hashing_packed_fields_1, 2, 0);
    trace.set(Column::bc_hashing_input_len, 1, 4);
    check_relation<bc_hashing>(trace);
 
    // The multipermutation interaction will pass but a multipermutation selector `sel_packed_read[1]` will be
    // untoggled, which will fail the #[PACKED_ROW_NEEDS_PERM_SELECTOR] (in bc_decomposition.pil) constraint.
    check_multipermutation_interaction<BytecodeTraceBuilder,
                                       perm_bc_hashing_get_packed_field_0_settings,
                                       perm_bc_hashing_get_packed_field_1_settings,
                                       perm_bc_hashing_get_packed_field_2_settings>(trace);
 
    EXPECT_THROW_WITH_MESSAGE(
        check_relation<bc_decomposition>(trace, bc_decomposition::SR_PACKED_ROW_NEEDS_PERM_SELECTOR),
        bc_decomposition::get_subrelation_label(bc_decomposition::SR_PACKED_ROW_NEEDS_PERM_SELECTOR));
}
 
TEST_F(BytecodeHashingConstrainingTestTraceHelper, NegativeInputLen)
{
    // 80 bytes => hash 4 fields, two padding fields
    std::vector<uint8_t> bytecode = random_bytes(80);
    std::vector<FF> fields = simulation::encode_bytecode(bytecode);
 
    TestTraceContainer trace = process_bc_hashing_trace({ fields }, { 1 }, { bytecode.size() });
    builder.process_decomposition(
        { { .bytecode_id = 1, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
 
    // Set the incorrect input_len at the first row, and the lookup into (an honest) poseidon will fail:
    trace.set(Column::bc_hashing_input_len, 1, 0);
    EXPECT_THROW_WITH_MESSAGE(
        (check_interaction<BytecodeTraceBuilder, lookup_bc_hashing_poseidon2_hash_settings>(trace)),
        "LOOKUP_BC_HASHING_POSEIDON2_HASH");
 
    trace.set(Column::bc_hashing_input_len, 1, 4);
 
    // Set the incorrect input_len at the start row, and the constraining length check will fail:
    trace.set(Column::bc_hashing_input_len, 1, 0);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_BYTECODE_LENGTH_FIELDS),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_BYTECODE_LENGTH_FIELDS));
}
 
TEST_F(BytecodeHashingConstrainingTestTraceHelper, NegativeRounds)
{
    // 80 bytes => hash 4 fields, two padding fields
    std::vector<uint8_t> bytecode = random_bytes(80);
    std::vector<FF> fields = simulation::encode_bytecode(bytecode);
 
    TestTraceContainer trace = process_bc_hashing_trace({ fields }, { 1 }, { bytecode.size() });
    builder.process_decomposition(
        { { .bytecode_id = 1, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
 
    // Setting the incorrect number of rounds remaining will fail relative to the next row...
    trace.set(Column::bc_hashing_rounds_rem, 1, 3);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_ROUNDS_DECREMENT),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_ROUNDS_DECREMENT));
 
    // ...and even if decremented correctly, will fail at latch if rounds_rem != 1:
    trace.set(Column::bc_hashing_rounds_rem, 2, 2);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_ROUNDS_DECREMENT),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_ROUNDS_DECREMENT));
}
 
TEST_F(BytecodeHashingConstrainingTestTraceHelper, NegativeOutputHash)
{
    std::vector<FF> bytecode_fields = random_fields(10);
    std::vector<FF> prepended_fields = { compute_public_bytecode_first_field(bytecode_fields.size() * 31) };
    prepended_fields.insert(prepended_fields.end(), bytecode_fields.begin(), bytecode_fields.end());
    FF hash = RawPoseidon2::hash(prepended_fields);
    TestTraceContainer trace = process_bc_hashing_trace({ bytecode_fields }, { hash }, { bytecode_fields.size() * 31 });
 
    check_relation<bc_hashing>(trace);
    check_interaction<BytecodeTraceBuilder, lookup_bc_hashing_poseidon2_hash_settings>(trace);
 
    // Change any of the output_hash values
    trace.set(Column::bc_hashing_bytecode_id, 2, 123);
    EXPECT_THROW_WITH_MESSAGE(
        (check_interaction<BytecodeTraceBuilder, lookup_bc_hashing_poseidon2_hash_settings>(trace)),
        "LOOKUP_BC_HASHING_POSEIDON2_HASH");
}
 
TEST_F(BytecodeHashingConstrainingTest, NegativeSingleBytecodeHashIncrements)
{
    Poseidon2 poseidon2 =
        Poseidon2(mock_execution_id_manager, mock_gt, hash_event_emitter, perm_event_emitter, perm_mem_event_emitter);
    // Attempt to skip some init fields:
    // decomp: 3 fields 1, 2, 3 => real hash [ sep, 1, 2, 3 ] => try and claim hash [ sep, 2, 3 ] => start = 1,
    // pc_index = 31. Note that this is protected by the addition of precomputed.first_row in #[PC_INCREMENTS]
    std::vector<uint8_t> bytecode = random_bytes(static_cast<size_t>(31 * 3));
    std::vector<FF> bytecode_fields = simulation::encode_bytecode(bytecode);
 
    auto sep = compute_public_bytecode_first_field(bytecode.size());
 
    auto bad_hash = poseidon2.hash({ sep, bytecode_fields[1], bytecode_fields[2] });
 
    auto trace = TestTraceContainer({
        { { C::precomputed_first_row, 1 } },
        {
            { C::bc_hashing_end, 1 },
            { C::bc_hashing_packed_fields_0, sep },
            { C::bc_hashing_packed_fields_1, bytecode_fields[1] },
            { C::bc_hashing_packed_fields_2, bytecode_fields[2] },
            { C::bc_hashing_pc_index_1, 31 },
            { C::bc_hashing_pc_index_2, 62 },
            { C::bc_hashing_sel_not_padding_1, 1 },
            { C::bc_hashing_sel_not_padding_2, 1 },
            { C::bc_hashing_bytecode_id, bad_hash },
            { C::bc_hashing_pc_index, 31 },
            { C::bc_hashing_sel, 1 },
            { C::bc_hashing_sel_not_start, 0 },
            { C::bc_hashing_start, 1 },
        },
    });
 
    precomputed_builder.process_misc(trace, 256);
    poseidon2_builder.process_hash(hash_event_emitter.dump_events(), trace);
    builder.process_decomposition(
        { { .bytecode_id = bad_hash, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
 
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_PC_INCREMENTS),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_PC_INCREMENTS));
}
 
TEST_F(BytecodeHashingConstrainingTest, NegativeSingleBytecodeHashLength)
{
    Poseidon2 poseidon2 =
        Poseidon2(mock_execution_id_manager, mock_gt, hash_event_emitter, perm_event_emitter, perm_mem_event_emitter);
    // Attempt to prepend fields to the hash
    // decomp: 3 fields 1, 2, 3 => real hash [ sep, 1, 2, 3 ] => try and claim hash [ a, b, c, sep, 1, 2, 3 ]
    std::vector<uint8_t> bytecode = random_bytes(static_cast<size_t>(31 * 3));
    std::vector<FF> bytecode_fields = simulation::encode_bytecode(bytecode);
 
    auto sep = compute_public_bytecode_first_field(bytecode.size());
 
    auto bad_hash = poseidon2.hash({ 0xa, 0xb, 0xc, sep, bytecode_fields[0], bytecode_fields[1], bytecode_fields[2] });
 
    auto trace = TestTraceContainer({
        { { C::precomputed_first_row, 1 } },
        {
            { C::bc_hashing_input_len, 7 },
            { C::bc_hashing_packed_fields_0, sep },
            { C::bc_hashing_packed_fields_1, bytecode_fields[0] },
            { C::bc_hashing_packed_fields_2, bytecode_fields[1] },
            { C::bc_hashing_pc_index_1, 0 },
            { C::bc_hashing_pc_index_2, 31 },
            { C::bc_hashing_sel_not_padding_1, 1 },
            { C::bc_hashing_sel_not_padding_2, 1 },
            { C::bc_hashing_bytecode_id, bad_hash },
            { C::bc_hashing_pc_index, 0 },
            { C::bc_hashing_rounds_rem, 2 },
            { C::bc_hashing_sel, 1 },
            { C::bc_hashing_start, 1 },
        },
        {
            { C::bc_hashing_input_len, 7 },
            { C::bc_hashing_end, 1 },
            { C::bc_hashing_packed_fields_0, bytecode_fields[2] },
            { C::bc_hashing_packed_fields_1, 0 },
            { C::bc_hashing_packed_fields_2, 0 },
            { C::bc_hashing_pc_index_1, 93 },
            { C::bc_hashing_pc_index_2, 124 },
            { C::bc_hashing_bytecode_id, bad_hash },
            { C::bc_hashing_pc_index, 62 },
            { C::bc_hashing_rounds_rem, 1 },
            { C::bc_hashing_sel, 1 },
            { C::bc_hashing_sel_not_start, 1 },
        },
    });
 
    precomputed_builder.process_misc(trace, 256);
    poseidon2_builder.process_hash(hash_event_emitter.dump_events(), trace);
    builder.process_decomposition(
        { { .bytecode_id = 1, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
 
    // The correct rows (for input chunks [sep, 1, 2] and [3, 0, 0]) will exist in the poseidon trace, but the start
    // rows do not line up:
    EXPECT_THROW_WITH_MESSAGE(
        (check_interaction<BytecodeTraceBuilder, lookup_bc_hashing_poseidon2_hash_settings>(trace)),
        "LOOKUP_BC_HASHING_POSEIDON2_HASH");
    // At the final row, the length check will fail:
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_BYTECODE_LENGTH_FIELDS),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_BYTECODE_LENGTH_FIELDS));
}
 
TEST_F(BytecodeHashingConstrainingTest, NegativeSingleBytecodeHashLengthBytes)
{
    Poseidon2 poseidon2 =
        Poseidon2(mock_execution_id_manager, mock_gt, hash_event_emitter, perm_event_emitter, perm_mem_event_emitter);
    // Attempt to extend the bytecode by zero value bytes (without requiring a new field)
    // bc: 0xa...f of size 90 => real hash [ (90|sep), 0xa.., .., 0xf000000 ] => try and claim bc = 0xa...f0000 of
    // size 92 with hash [ (92|sep), 0xa.., .., 0xf000000 ]
    std::vector<uint8_t> bytecode = random_bytes(static_cast<size_t>(90));
    std::vector<FF> bytecode_fields = simulation::encode_bytecode(bytecode);
 
    auto sep = compute_public_bytecode_first_field(92);
 
    auto bad_hash = poseidon2.hash({ sep, bytecode_fields[0], bytecode_fields[1], bytecode_fields[2] });
 
    auto trace = TestTraceContainer({
        { { C::precomputed_first_row, 1 } },
        {
            { C::bc_hashing_size_in_bytes, 92 },
            { C::bc_hashing_input_len, 4 },
            { C::bc_hashing_packed_fields_0, sep },
            { C::bc_hashing_packed_fields_1, bytecode_fields[0] },
            { C::bc_hashing_packed_fields_2, bytecode_fields[1] },
            { C::bc_hashing_pc_index_1, 0 },
            { C::bc_hashing_pc_index_2, 31 },
            { C::bc_hashing_sel_not_padding_1, 1 },
            { C::bc_hashing_sel_not_padding_2, 1 },
            { C::bc_hashing_bytecode_id, bad_hash },
            { C::bc_hashing_pc_index, 0 },
            { C::bc_hashing_rounds_rem, 2 },
            { C::bc_hashing_padding, 2 },
            { C::bc_hashing_sel, 1 },
            { C::bc_hashing_start, 1 },
        },
        {
            { C::bc_hashing_input_len, 4 },
            { C::bc_hashing_end, 1 },
            { C::bc_hashing_packed_fields_0, bytecode_fields[2] },
            { C::bc_hashing_packed_fields_1, 0 },
            { C::bc_hashing_packed_fields_2, 0 },
            { C::bc_hashing_pc_index_1, 93 },
            { C::bc_hashing_pc_index_2, 124 },
            { C::bc_hashing_bytecode_id, bad_hash },
            { C::bc_hashing_pc_index, 62 },
            { C::bc_hashing_rounds_rem, 1 },
            { C::bc_hashing_sel, 1 },
            { C::bc_hashing_sel_not_start, 1 },
        },
    });
 
    precomputed_builder.process_misc(trace, 256);
    poseidon2_builder.process_hash(hash_event_emitter.dump_events(), trace);
    builder.process_decomposition(
        { { .bytecode_id = 1, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
 
    // The field length is correct (90 and 92 bytes both require 3 fields, total 4 for sep):
    check_relation<bc_hashing>(trace, bc_hashing::SR_BYTECODE_LENGTH_FIELDS);
 
    // The claimed byte length is incorrect:
    EXPECT_THROW_WITH_MESSAGE(
        (check_interaction<BytecodeTraceBuilder, perm_bc_hashing_bytecode_length_bytes_settings>(trace)),
        "PERM_BC_HASHING_BYTECODE_LENGTH_BYTES");
}
 
// =====================================================================
// Ghost Row Injection Vulnerability Tests
// =====================================================================
// These tests verify that ghost rows (sel=0) cannot fire permutations.
// The fix: sel_not_padding_1 * (1 - sel) = 0 and sel_not_padding_2 * (1 - sel) = 0
// ensure these selectors are forced to 0 when sel=0.
 
TEST_F(BytecodeHashingConstrainingTest, NegativeGhostRowInjectionBlocked)
{
    // Try to create a ghost row (sel=0) with sel_not_padding_1=1 or sel_not_padding_2=1
    // which would fire the #[GET_PACKED_FIELD_1] or #[GET_PACKED_FIELD_2] permutations
    TestTraceContainer trace({
        { { C::precomputed_first_row, 1 } },
        {
            { C::bc_hashing_sel, 0 },               // Ghost row: gadget not active
            { C::bc_hashing_sel_not_padding_1, 1 }, // Try to fire permutation anyway
            { C::bc_hashing_sel_not_padding_2, 0 },
        },
    });
 
    // The fix: sel_not_padding_1 * (1 - sel) = 0
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_SEL_NOT_PADDING_REQUIRES_SEL));
 
    // Reset and try with sel_not_padding_2
    trace.set(C::bc_hashing_sel_not_padding_1, 1, 0);
    trace.set(C::bc_hashing_sel_not_padding_2, 1, 1);
 
    // The fix: sel_not_padding_2 * (1 - sel) = 0
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_SEL_NOT_PADDING_REQUIRES_SEL));
}
 
TEST_F(BytecodeHashingConstrainingTestTraceHelper, NegativePaddingPropagationMultiRow)
{
    // 248 bytes => 8 fields + 1 sep = 9 fields => padding = 0, 3 rounds
    // Verify PADDING_PROPAGATION across a longer computation block.
    std::vector<uint8_t> bytecode = random_bytes(248);
    std::vector<FF> fields = simulation::encode_bytecode(bytecode);
 
    TestTraceContainer trace = process_bc_hashing_trace({ fields }, { 1 }, { bytecode.size() });
    builder.process_decomposition(
        { { .bytecode_id = 1, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
 
    check_relation<bc_hashing>(trace, bc_hashing::SR_PADDING_PROPAGATION);
 
    // Rows 1, 2, 3 are the three rounds. Changing padding on the middle row should break propagation.
    trace.set(C::bc_hashing_padding, 2, 1);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_PADDING_PROPAGATION),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_PADDING_PROPAGATION));
}
 
TEST_F(BytecodeHashingConstrainingTestTraceHelper, NegativeBytecodeFieldLengthViaPadding)
{
    // Verify that #[BYTECODE_LENGTH_FIELDS] catches a mismatch between padding and input_len at start.
    // Constraint: start * (3 * rounds_rem - padding - input_len) = 0
    // 93 bytes => 3 fields + 1 sep = 4 fields => padding = 2, rounds_rem = 2, input_len = 4
    // Check: 3 * 2 - 2 - 4 = 0 ✓
    std::vector<uint8_t> bytecode = random_bytes(93);
    std::vector<FF> fields = simulation::encode_bytecode(bytecode);
 
    TestTraceContainer trace = process_bc_hashing_trace({ fields }, { 1 }, { bytecode.size() });
    builder.process_decomposition(
        { { .bytecode_id = 1, .bytecode = std::make_shared<std::vector<uint8_t>>(bytecode) } }, trace);
 
    check_relation<bc_hashing>(trace, bc_hashing::SR_BYTECODE_LENGTH_FIELDS);
 
    // Corrupt padding at the start row to break the link between rounds_rem, padding, and input_len.
    // Set padding to 0 at start (should be 2). Now 3 * 2 - 0 - 4 = 2 ≠ 0
    trace.set(C::bc_hashing_padding, 1, 0);
    EXPECT_THROW_WITH_MESSAGE(check_relation<bc_hashing>(trace, bc_hashing::SR_BYTECODE_LENGTH_FIELDS),
                              bc_hashing::get_subrelation_label(bc_hashing::SR_BYTECODE_LENGTH_FIELDS));
}
 
} // namespace
} // namespace bb::avm2::constraining