precomputed_trace.cpp

Go to the documentation of this file.

#include "barretenberg/vm2/tracegen/precomputed_trace.hpp"
 
#include <array>
#include <cstddef>
#include <cstdint>
#include <vector>
 
#include "barretenberg/vm2/common/aztec_constants.hpp"
#include "barretenberg/vm2/common/aztec_types.hpp"
#include "barretenberg/vm2/common/gas.hpp"
#include "barretenberg/vm2/common/instruction_spec.hpp"
#include "barretenberg/vm2/common/memory_types.hpp"
#include "barretenberg/vm2/common/tagged_value.hpp"
#include "barretenberg/vm2/common/to_radix.hpp"
#include "barretenberg/vm2/simulation/gadgets/keccakf1600.hpp"
#include "barretenberg/vm2/tracegen/lib/get_contract_instance_spec.hpp"
#include "barretenberg/vm2/tracegen/lib/get_env_var_spec.hpp"
#include "barretenberg/vm2/tracegen/lib/instruction_spec.hpp"
#include "barretenberg/vm2/tracegen/lib/phase_spec.hpp"
 
namespace bb::avm2::tracegen {
 
using C = Column;
 
void PrecomputedTraceBuilder::process_misc(TraceContainer& trace, const uint32_t num_rows)
{
    // First row.
    trace.set(C::precomputed_first_row, 0, 1);
 
    // Clk
    // TODO: What a waste of 64MB. Can we elegantly have a flag for this?
    trace.reserve_column(C::precomputed_clk, num_rows);
    for (uint32_t i = 0; i < num_rows; i++) {
        trace.set(C::precomputed_clk, i, i);
    }
}
 
void PrecomputedTraceBuilder::process_bitwise(TraceContainer& trace)
{
    // 256 per input (a and b), and 3 different bitwise ops
    constexpr auto num_rows = 256 * 256 * 3;
    trace.reserve_column(C::precomputed_sel_bitwise, num_rows);
    trace.reserve_column(C::precomputed_bitwise_input_a, num_rows);
    trace.reserve_column(C::precomputed_bitwise_input_b, num_rows);
    trace.reserve_column(C::precomputed_bitwise_output, num_rows);
 
    // row # is derived as:
    //     - input_b: bits 0...7 (0 being LSB)
    //     - input_a: bits 8...15
    //     - op_id: bits 16...
    // In other words, the first 256*256 rows are for op_id 0. Next are for op_id 1, followed by op_id 2.
    auto row_from_inputs = [](BitwiseOperation op_id, uint32_t input_a, uint32_t input_b) -> uint32_t {
        return (static_cast<uint32_t>(op_id) << 16) | (input_a << 8) | input_b;
    };
    auto compute_operation = [](BitwiseOperation op_id, uint32_t a, uint32_t b) -> uint32_t {
        switch (op_id) {
        case BitwiseOperation::AND:
            return a & b;
        case BitwiseOperation::OR:
            return a | b;
        case BitwiseOperation::XOR:
            return a ^ b;
        }
 
        BB_ASSERT(false, "This should not happen");
        __builtin_unreachable();
    };
 
    for (const auto op_id : { BitwiseOperation::AND, BitwiseOperation::OR, BitwiseOperation::XOR }) {
        for (uint32_t a = 0; a < 256; a++) {
            for (uint32_t b = 0; b < 256; b++) {
                trace.set(row_from_inputs(op_id, a, b),
                          { {
                              { C::precomputed_sel_bitwise, 1 },
                              { C::precomputed_bitwise_op_id, static_cast<uint8_t>(op_id) },
                              { C::precomputed_bitwise_input_a, FF(a) },
                              { C::precomputed_bitwise_input_b, FF(b) },
                              { C::precomputed_bitwise_output, FF(compute_operation(op_id, a, b)) },
                          } });
            }
        }
    }
}
 
void PrecomputedTraceBuilder::process_sel_range_8(TraceContainer& trace)
{
    constexpr auto num_rows = 1 << 8; // 256
    // Set this selector high for the first 2^8 rows
    // For these rows, clk will be 0...255
    trace.reserve_column(C::precomputed_sel_range_8, num_rows);
    for (uint32_t i = 0; i < num_rows; i++) {
        trace.set(C::precomputed_sel_range_8, i, 1);
    }
}
 
void PrecomputedTraceBuilder::process_sel_range_16(TraceContainer& trace)
{
    constexpr auto num_rows = 1 << 16; // 2^16
    // Set this selector high for the first 2^16 rows
    // For these rows, clk will be 0...2^16-1
    trace.reserve_column(C::precomputed_sel_range_16, num_rows);
    for (uint32_t i = 0; i < num_rows; i++) {
        trace.set(C::precomputed_sel_range_16, i, 1);
    }
}
 
void PrecomputedTraceBuilder::process_power_of_2(TraceContainer& trace)
{
    constexpr auto num_rows = 1 << 8; // 2^8 = 256
    trace.reserve_column(C::precomputed_power_of_2, num_rows);
    for (uint32_t i = 0; i < num_rows; i++) {
        trace.set(C::precomputed_power_of_2, i, uint256_t(1) << uint256_t(i));
    }
}
 
void PrecomputedTraceBuilder::process_sha256_round_constants(TraceContainer& trace)
{
    constexpr std::array<uint32_t, 64> round_constants{
        0x428a2f98, 0x71374491, 0xb5c0fbcf, 0xe9b5dba5, 0x3956c25b, 0x59f111f1, 0x923f82a4, 0xab1c5ed5,
        0xd807aa98, 0x12835b01, 0x243185be, 0x550c7dc3, 0x72be5d74, 0x80deb1fe, 0x9bdc06a7, 0xc19bf174,
        0xe49b69c1, 0xefbe4786, 0x0fc19dc6, 0x240ca1cc, 0x2de92c6f, 0x4a7484aa, 0x5cb0a9dc, 0x76f988da,
        0x983e5152, 0xa831c66d, 0xb00327c8, 0xbf597fc7, 0xc6e00bf3, 0xd5a79147, 0x06ca6351, 0x14292967,
        0x27b70a85, 0x2e1b2138, 0x4d2c6dfc, 0x53380d13, 0x650a7354, 0x766a0abb, 0x81c2c92e, 0x92722c85,
        0xa2bfe8a1, 0xa81a664b, 0xc24b8b70, 0xc76c51a3, 0xd192e819, 0xd6990624, 0xf40e3585, 0x106aa070,
        0x19a4c116, 0x1e376c08, 0x2748774c, 0x34b0bcb5, 0x391c0cb3, 0x4ed8aa4a, 0x5b9cca4f, 0x682e6ff3,
        0x748f82ee, 0x78a5636f, 0x84c87814, 0x8cc70208, 0x90befffa, 0xa4506ceb, 0xbef9a3f7, 0xc67178f2
    };
    constexpr auto num_rows = round_constants.size();
    trace.reserve_column(C::precomputed_sha256_compression_round_constant, num_rows);
    trace.reserve_column(C::precomputed_sel_sha256_compression, num_rows);
    for (uint32_t i = 0; i < num_rows; i++) {
        trace.set(i,
                  { { { C::precomputed_sel_sha256_compression, 1 },
                      { C::precomputed_sha256_compression_round_constant, round_constants[i] } } });
    }
}
 
void PrecomputedTraceBuilder::process_tag_parameters(TraceContainer& trace)
{
    using bb::avm2::MemoryTag;
 
    constexpr uint32_t NUM_TAGS = static_cast<uint32_t>(MemoryTag::MAX) + 1;
    for (uint32_t i = 0; i < NUM_TAGS; i++) {
        const auto tag = static_cast<MemoryTag>(i);
        trace.set(i, // Column number corresponds to MemoryTag enum value.
                  { {
                      { C::precomputed_sel_tag_parameters, 1 },
                      { C::precomputed_tag_byte_length, get_tag_bytes(tag) },
                      { C::precomputed_tag_max_bits, get_tag_bits(tag) },
                      { C::precomputed_tag_max_value, get_tag_max_value(tag) },
                  } });
    }
}
 
void PrecomputedTraceBuilder::process_wire_instruction_spec(TraceContainer& trace)
{
    const std::array<Column, NUM_OP_DC_SELECTORS> sel_op_dc_columns = {
        C::precomputed_sel_op_dc_0,  C::precomputed_sel_op_dc_1,  C::precomputed_sel_op_dc_2,
        C::precomputed_sel_op_dc_3,  C::precomputed_sel_op_dc_4,  C::precomputed_sel_op_dc_5,
        C::precomputed_sel_op_dc_6,  C::precomputed_sel_op_dc_7,  C::precomputed_sel_op_dc_8,
        C::precomputed_sel_op_dc_9,  C::precomputed_sel_op_dc_10, C::precomputed_sel_op_dc_11,
        C::precomputed_sel_op_dc_12, C::precomputed_sel_op_dc_13, C::precomputed_sel_op_dc_14,
        C::precomputed_sel_op_dc_15, C::precomputed_sel_op_dc_16, C::precomputed_sel_op_dc_17,
    };
 
    // First set the selector for this table lookup.
    constexpr uint32_t num_rows = 1 << 8; // 256
    constexpr uint32_t num_opcodes = static_cast<uint32_t>(WireOpCode::LAST_OPCODE_SENTINEL);
    trace.reserve_column(C::precomputed_opcode_out_of_range, num_rows - num_opcodes);
    for (uint32_t i = num_opcodes; i < num_rows; i++) {
        trace.set(C::precomputed_opcode_out_of_range, i, 1);
    }
 
    for (size_t i = 0; i < NUM_OP_DC_SELECTORS; i++) {
        trace.reserve_column(sel_op_dc_columns.at(i), num_opcodes);
    }
    trace.reserve_column(C::precomputed_exec_opcode, num_opcodes);
    trace.reserve_column(C::precomputed_instr_size, num_opcodes);
 
    // Fill the lookup tables with the operand decomposition selectors.
    for (const auto& [wire_opcode, wire_instruction_spec] : get_wire_instruction_spec()) {
        for (size_t i = 0; i < NUM_OP_DC_SELECTORS; i++) {
            trace.set(sel_op_dc_columns.at(i),
                      static_cast<uint32_t>(wire_opcode),
                      wire_instruction_spec.op_dc_selectors.at(i));
        }
        trace.set(C::precomputed_exec_opcode,
                  static_cast<uint32_t>(wire_opcode),
                  static_cast<uint32_t>(wire_instruction_spec.exec_opcode));
        trace.set(C::precomputed_instr_size, static_cast<uint32_t>(wire_opcode), wire_instruction_spec.size_in_bytes);
 
        if (wire_instruction_spec.tag_operand_idx.has_value()) {
            trace.set(C::precomputed_sel_has_tag, static_cast<uint32_t>(wire_opcode), 1);
 
            if (wire_instruction_spec.tag_operand_idx.value() == 2) {
                trace.set(C::precomputed_sel_tag_is_op2, static_cast<uint32_t>(wire_opcode), 1);
            }
        }
    }
}
 
void PrecomputedTraceBuilder::process_exec_instruction_spec(TraceContainer& trace)
{
    constexpr std::array<Column, AVM_MAX_REGISTERS> MEM_OP_REG_COLUMNS = {
        Column::precomputed_sel_mem_op_reg_0_, Column::precomputed_sel_mem_op_reg_1_,
        Column::precomputed_sel_mem_op_reg_2_, Column::precomputed_sel_mem_op_reg_3_,
        Column::precomputed_sel_mem_op_reg_4_, Column::precomputed_sel_mem_op_reg_5_,
    };
    constexpr std::array<Column, AVM_MAX_REGISTERS> RW_COLUMNS = {
        Column::precomputed_rw_reg_0_, Column::precomputed_rw_reg_1_, Column::precomputed_rw_reg_2_,
        Column::precomputed_rw_reg_3_, Column::precomputed_rw_reg_4_, Column::precomputed_rw_reg_5_,
    };
    constexpr std::array<Column, AVM_MAX_REGISTERS> DO_TAG_CHECK_COLUMNS = {
        Column::precomputed_sel_tag_check_reg_0_, Column::precomputed_sel_tag_check_reg_1_,
        Column::precomputed_sel_tag_check_reg_2_, Column::precomputed_sel_tag_check_reg_3_,
        Column::precomputed_sel_tag_check_reg_4_, Column::precomputed_sel_tag_check_reg_5_,
    };
    constexpr std::array<Column, AVM_MAX_REGISTERS> EXPECTED_TAG_COLUMNS = {
        Column::precomputed_expected_tag_reg_0_, Column::precomputed_expected_tag_reg_1_,
        Column::precomputed_expected_tag_reg_2_, Column::precomputed_expected_tag_reg_3_,
        Column::precomputed_expected_tag_reg_4_, Column::precomputed_expected_tag_reg_5_,
    };
 
    constexpr std::array<Column, AVM_MAX_OPERANDS> SEL_OP_IS_ADDRESS_COLUMNS = {
        Column::precomputed_sel_op_is_address_0_, Column::precomputed_sel_op_is_address_1_,
        Column::precomputed_sel_op_is_address_2_, Column::precomputed_sel_op_is_address_3_,
        Column::precomputed_sel_op_is_address_4_, Column::precomputed_sel_op_is_address_5_,
        Column::precomputed_sel_op_is_address_6_,
    };
 
    for (const auto& [exec_opcode, exec_instruction_spec] : get_exec_instruction_spec()) {
        // Basic information.
        trace.set(static_cast<uint32_t>(exec_opcode),
                  { {
                      { C::precomputed_sel_exec_spec, 1 },
                      { C::precomputed_exec_opcode_opcode_gas, exec_instruction_spec.gas_cost.opcode_gas },
                      { C::precomputed_exec_opcode_base_da_gas, exec_instruction_spec.gas_cost.base_da },
                      { C::precomputed_exec_opcode_dynamic_l2_gas, exec_instruction_spec.gas_cost.dyn_l2 },
                      { C::precomputed_exec_opcode_dynamic_da_gas, exec_instruction_spec.gas_cost.dyn_da },
                  } });
 
        // Register information.
        const auto& register_info = get_exec_instruction_spec().at(exec_opcode).register_info;
        for (size_t i = 0; i < AVM_MAX_REGISTERS; i++) {
            trace.set(MEM_OP_REG_COLUMNS.at(i), static_cast<uint32_t>(exec_opcode), register_info.is_active(i) ? 1 : 0);
            trace.set(RW_COLUMNS.at(i), static_cast<uint32_t>(exec_opcode), register_info.is_write(i) ? 1 : 0);
            trace.set(DO_TAG_CHECK_COLUMNS.at(i),
                      static_cast<uint32_t>(exec_opcode),
                      register_info.need_tag_check(i) ? 1 : 0);
            trace.set(EXPECTED_TAG_COLUMNS.at(i),
                      static_cast<uint32_t>(exec_opcode),
                      static_cast<uint32_t>(register_info.expected_tag(i).value_or(static_cast<ValueTag>(0))));
        }
 
        // Whether an operand is an address
        for (size_t i = 0; i < AVM_MAX_OPERANDS; i++) {
            trace.set(SEL_OP_IS_ADDRESS_COLUMNS.at(i),
                      static_cast<uint32_t>(exec_opcode),
                      i < exec_instruction_spec.num_addresses ? 1 : 0);
        }
 
        // Gadget / Subtrace Selectors / Decomposable selectors
        auto dispatch_to_subtrace = get_subtrace_info_map().at(exec_opcode);
        trace.set(static_cast<uint32_t>(exec_opcode),
                  { { { C::precomputed_subtrace_id, get_subtrace_id(dispatch_to_subtrace.subtrace_selector) },
                      { C::precomputed_subtrace_operation_id, dispatch_to_subtrace.subtrace_operation_id },
                      { C::precomputed_dyn_gas_id, exec_instruction_spec.dyn_gas_id } } });
    }
}
 
void PrecomputedTraceBuilder::process_to_radix_safe_limbs(TraceContainer& trace)
{
    const auto& p_limbs_per_radix = get_p_limbs_per_radix();
 
    trace.reserve_column(C::precomputed_sel_to_radix_p_limb_counts, p_limbs_per_radix.size());
    trace.reserve_column(C::precomputed_to_radix_safe_limbs, p_limbs_per_radix.size());
 
    for (size_t i = 0; i < p_limbs_per_radix.size(); ++i) {
        size_t decomposition_len = p_limbs_per_radix[i].size();
        trace.set(C::precomputed_sel_to_radix_p_limb_counts, static_cast<uint32_t>(i), 1);
        // Use 0 as fallback when decomposition_len == 0 (i.e. p_limbs_per_radix[0] and p_limbs_per_radix[1])
        trace.set(C::precomputed_to_radix_safe_limbs,
                  static_cast<uint32_t>(i),
                  decomposition_len > 0 ? decomposition_len - 1 : 0);
        trace.set(C::precomputed_to_radix_num_limbs_for_p, static_cast<uint32_t>(i), decomposition_len);
    }
}
 
void PrecomputedTraceBuilder::process_to_radix_p_decompositions(TraceContainer& trace)
{
    const auto& p_limbs_per_radix = get_p_limbs_per_radix();
 
    uint32_t row = 0;
    for (size_t i = 0; i < p_limbs_per_radix.size(); ++i) {
        size_t decomposition_len = p_limbs_per_radix[i].size();
        for (size_t j = 0; j < decomposition_len; ++j) {
            trace.set(C::precomputed_sel_p_decomposition, row, 1);
            trace.set(C::precomputed_p_decomposition_radix, row, i);
            trace.set(C::precomputed_p_decomposition_limb_index, row, j);
            trace.set(C::precomputed_p_decomposition_limb, row, p_limbs_per_radix[i][j]);
            row++;
        }
    }
}
 
void PrecomputedTraceBuilder::process_memory_tag_range(TraceContainer& trace)
{
    constexpr uint32_t num_rows = 1 << 8; // 256
 
    for (uint32_t i = static_cast<uint32_t>(MemoryTag::MAX) + 1; i < num_rows; i++) {
        trace.set(C::precomputed_sel_mem_tag_out_of_range, i, 1);
    }
}
 
void PrecomputedTraceBuilder::process_addressing_gas(TraceContainer& trace)
{
    constexpr uint32_t num_rows = 1 << 16; // 65536
    trace.reserve_column(C::precomputed_sel_addressing_gas, num_rows);
    trace.reserve_column(C::precomputed_addressing_gas, num_rows);
 
    for (uint32_t i = 0; i < num_rows; i++) {
        trace.set(C::precomputed_sel_addressing_gas, i, 1);
        trace.set(C::precomputed_addressing_gas, i, compute_addressing_gas(static_cast<uint16_t>(i)));
    }
}
 
void PrecomputedTraceBuilder::process_phase_table(TraceContainer& trace)
{
    using C = Column;
 
    for (const auto& [phase_value, spec] : get_tx_phase_spec_map()) {
 
        const uint32_t row = static_cast<uint32_t>(phase_value);
        // Populate all columns that are part of the #[READ_PHASE_SPEC] lookup in tx.pil.
        std::vector<std::pair<Column, FF>> row_data = {
            { C::precomputed_sel_phase, 1 },
            { C::precomputed_is_public_call_request, spec.is_public_call_request ? 1 : 0 },
            { C::precomputed_is_teardown, spec.is_teardown ? 1 : 0 },
            { C::precomputed_is_collect_fee, spec.is_collect_fee ? 1 : 0 },
            { C::precomputed_is_tree_padding, spec.is_tree_padding ? 1 : 0 },
            { C::precomputed_is_cleanup, spec.is_cleanup ? 1 : 0 },
            { C::precomputed_is_revertible, spec.is_revertible ? 1 : 0 },
            { C::precomputed_read_pi_start_offset, spec.read_pi_start_offset },
            { C::precomputed_read_pi_length_offset, spec.read_pi_length_offset },
            { C::precomputed_sel_non_revertible_append_note_hash, spec.non_revertible_append_note_hash ? 1 : 0 },
            { C::precomputed_sel_non_revertible_append_nullifier, spec.non_revertible_append_nullifier ? 1 : 0 },
            { C::precomputed_sel_non_revertible_append_l2_l1_msg, spec.non_revertible_append_l2_l1_msg ? 1 : 0 },
            { C::precomputed_sel_revertible_append_note_hash, spec.revertible_append_note_hash ? 1 : 0 },
            { C::precomputed_sel_revertible_append_nullifier, spec.revertible_append_nullifier ? 1 : 0 },
            { C::precomputed_sel_revertible_append_l2_l1_msg, spec.revertible_append_l2_l1_msg ? 1 : 0 },
            { C::precomputed_next_phase_on_revert, spec.next_phase_on_revert },
        };
 
        trace.set(row, row_data);
    }
}
 
void PrecomputedTraceBuilder::process_keccak_round_constants(TraceContainer& trace)
{
    uint32_t row = 1;
    for (const auto& round_constant : simulation::keccak_round_constants) {
        trace.set(row,
                  { {
                      { C::precomputed_sel_keccak, 1 },
                      { C::precomputed_keccak_round_constant, round_constant },
                  } });
        row++;
    }
}
 
void PrecomputedTraceBuilder::process_get_env_var_table(TraceContainer& trace)
{
    constexpr uint32_t NUM_ROWS = 1 << 8;
 
    // Start by flagging `invalid_envvar_enum` as 1 for all rows.
    // "valid" rows will be reset manually to 0 below.
    for (uint32_t i = 0; i < NUM_ROWS; i++) {
        trace.set(C::precomputed_invalid_envvar_enum, i, 1);
    }
 
    for (uint8_t enum_value = 0; enum_value <= static_cast<uint8_t>(EnvironmentVariable::MAX); enum_value++) {
        const auto& envvar_spec = GetEnvVarSpec::get_table(enum_value);
        trace.set(static_cast<uint32_t>(enum_value),
                  { {
                      { C::precomputed_invalid_envvar_enum, 0 }, // Reset the invalid enum flag for valid rows
                      { C::precomputed_sel_envvar_pi_lookup_col0, envvar_spec.envvar_pi_lookup_col0 },
                      { C::precomputed_sel_envvar_pi_lookup_col1, envvar_spec.envvar_pi_lookup_col1 },
                      { C::precomputed_envvar_pi_row_idx, envvar_spec.envvar_pi_row_idx },
                      { C::precomputed_is_address, envvar_spec.is_address ? 1 : 0 },
                      { C::precomputed_is_sender, envvar_spec.is_sender ? 1 : 0 },
                      { C::precomputed_is_transactionfee, envvar_spec.is_transactionfee ? 1 : 0 },
                      { C::precomputed_is_isstaticcall, envvar_spec.is_isstaticcall ? 1 : 0 },
                      { C::precomputed_is_l2gasleft, envvar_spec.is_l2gasleft ? 1 : 0 },
                      { C::precomputed_is_dagasleft, envvar_spec.is_dagasleft ? 1 : 0 },
                      { C::precomputed_out_tag, envvar_spec.out_tag },
                  } });
    }
}
 
void PrecomputedTraceBuilder::process_get_contract_instance_table(TraceContainer& trace)
{
    // Set valid rows based on the precomputed table
    for (uint8_t enum_value = 0; enum_value <= static_cast<uint8_t>(ContractInstanceMember::MAX); enum_value++) {
        const auto& spec = GetContractInstanceSpec::get_table(enum_value);
 
        trace.set(static_cast<uint32_t>(enum_value),
                  { {
                      { C::precomputed_is_valid_member_enum, spec.is_valid_member_enum ? 1 : 0 },
                      { C::precomputed_is_deployer, spec.is_deployer ? 1 : 0 },
                      { C::precomputed_is_class_id, spec.is_class_id ? 1 : 0 },
                      { C::precomputed_is_init_hash, spec.is_init_hash ? 1 : 0 },
                  } });
    }
}
 
} // namespace bb::avm2::tracegen