plookup_tables.cpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Luke, Raju], commit: dd03c4a23ab067274b4964cacb36d1545f73fb14}
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
//
// === CODE ROLE: Builder-agnostic native computation ===
// This file performs pure computation without modifying any circuit builder. All functions here
// operate on native field elements (bb::fr) and return computed values. No witnesses or gates are created.
//
// Key functions:
//   - get_lookup_accumulators(): Slices inputs, computes table values, builds accumulator arrays.
//     This is the core native lookup logic. Returns ReadData<bb::fr> with computed values.
//   - get_multitable(): Returns a MultiTable by ID (lazy initialization of all tables)
//   - create_basic_table(): Factory function for BasicTable creation by ID
//
// The output of get_lookup_accumulators() is passed to ultra_circuit_builder::create_gates_from_plookup_accumulators()
// which actually creates the lookup gates in the circuit.
// =====================
 
#include "plookup_tables.hpp"
#include "barretenberg/common/constexpr_utils.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/aes128.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/blake2s.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/dummy.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/fixed_base/fixed_base.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/non_native_group_generator.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/sha256.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/uint.hpp"
 
#include "barretenberg/stdlib_circuit_builders/plookup_tables/keccak/keccak_chi.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/keccak/keccak_input.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/keccak/keccak_output.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/keccak/keccak_rho.hpp"
#include "barretenberg/stdlib_circuit_builders/plookup_tables/keccak/keccak_theta.hpp"
namespace bb::plookup {
 
using namespace bb;
 
namespace {
std::array<MultiTable, MultiTableId::NUM_MULTI_TABLES>& get_multi_tables()
{
    // C++11 guarantees thread-safe initialization of static local variables
    static std::array<MultiTable, MultiTableId::NUM_MULTI_TABLES> MULTI_TABLES = []() {
        std::array<MultiTable, MultiTableId::NUM_MULTI_TABLES> tables;
        tables[MultiTableId::SHA256_CH_INPUT] = sha256_tables::get_choose_input_table(MultiTableId::SHA256_CH_INPUT);
        tables[MultiTableId::SHA256_MAJ_INPUT] =
            sha256_tables::get_majority_input_table(MultiTableId::SHA256_MAJ_INPUT);
        tables[MultiTableId::SHA256_WITNESS_INPUT] =
            sha256_tables::get_witness_extension_input_table(MultiTableId::SHA256_WITNESS_INPUT);
        tables[MultiTableId::SHA256_CH_OUTPUT] = sha256_tables::get_choose_output_table(MultiTableId::SHA256_CH_OUTPUT);
        tables[MultiTableId::SHA256_MAJ_OUTPUT] =
            sha256_tables::get_majority_output_table(MultiTableId::SHA256_MAJ_OUTPUT);
        tables[MultiTableId::SHA256_WITNESS_OUTPUT] =
            sha256_tables::get_witness_extension_output_table(MultiTableId::SHA256_WITNESS_OUTPUT);
        tables[MultiTableId::AES_NORMALIZE] = aes128_tables::get_aes_normalization_table(MultiTableId::AES_NORMALIZE);
        tables[MultiTableId::AES_INPUT] = aes128_tables::get_aes_input_table(MultiTableId::AES_INPUT);
        tables[MultiTableId::AES_SBOX] = aes128_tables::get_aes_sbox_table(MultiTableId::AES_SBOX);
        tables[MultiTableId::UINT8_XOR] = uint_tables::get_uint_xor_table<8>(MultiTableId::UINT8_XOR);
        tables[MultiTableId::UINT16_XOR] = uint_tables::get_uint_xor_table<16>(MultiTableId::UINT16_XOR);
        tables[MultiTableId::UINT32_XOR] = uint_tables::get_uint_xor_table<32>(MultiTableId::UINT32_XOR);
        tables[MultiTableId::UINT64_XOR] = uint_tables::get_uint_xor_table<64>(MultiTableId::UINT64_XOR);
        tables[MultiTableId::UINT8_AND] = uint_tables::get_uint_and_table<8>(MultiTableId::UINT8_AND);
        tables[MultiTableId::UINT16_AND] = uint_tables::get_uint_and_table<16>(MultiTableId::UINT16_AND);
        tables[MultiTableId::UINT32_AND] = uint_tables::get_uint_and_table<32>(MultiTableId::UINT32_AND);
        tables[MultiTableId::UINT64_AND] = uint_tables::get_uint_and_table<64>(MultiTableId::UINT64_AND);
        tables[MultiTableId::SECP256K1_XLO] = ecc_generator_tables::ecc_generator_table<secp256k1::g1>::get_xlo_table(
            MultiTableId::SECP256K1_XLO, BasicTableId::SECP256K1_XLO_BASIC);
        tables[MultiTableId::SECP256K1_XHI] = ecc_generator_tables::ecc_generator_table<secp256k1::g1>::get_xhi_table(
            MultiTableId::SECP256K1_XHI, BasicTableId::SECP256K1_XHI_BASIC);
        tables[MultiTableId::SECP256K1_YLO] = ecc_generator_tables::ecc_generator_table<secp256k1::g1>::get_ylo_table(
            MultiTableId::SECP256K1_YLO, BasicTableId::SECP256K1_YLO_BASIC);
        tables[MultiTableId::SECP256K1_YHI] = ecc_generator_tables::ecc_generator_table<secp256k1::g1>::get_yhi_table(
            MultiTableId::SECP256K1_YHI, BasicTableId::SECP256K1_YHI_BASIC);
        tables[MultiTableId::SECP256K1_XYPRIME] =
            ecc_generator_tables::ecc_generator_table<secp256k1::g1>::get_xyprime_table(
                MultiTableId::SECP256K1_XYPRIME, BasicTableId::SECP256K1_XYPRIME_BASIC);
        tables[MultiTableId::SECP256K1_XLO_ENDO] =
            ecc_generator_tables::ecc_generator_table<secp256k1::g1>::get_xlo_endo_table(
                MultiTableId::SECP256K1_XLO_ENDO, BasicTableId::SECP256K1_XLO_ENDO_BASIC);
        tables[MultiTableId::SECP256K1_XHI_ENDO] =
            ecc_generator_tables::ecc_generator_table<secp256k1::g1>::get_xhi_endo_table(
                MultiTableId::SECP256K1_XHI_ENDO, BasicTableId::SECP256K1_XHI_ENDO_BASIC);
        tables[MultiTableId::SECP256K1_XYPRIME_ENDO] =
            ecc_generator_tables::ecc_generator_table<secp256k1::g1>::get_xyprime_endo_table(
                MultiTableId::SECP256K1_XYPRIME_ENDO, BasicTableId::SECP256K1_XYPRIME_ENDO_BASIC);
        tables[MultiTableId::BLAKE_XOR] = blake2s_tables::get_blake2s_xor_table(MultiTableId::BLAKE_XOR);
        tables[MultiTableId::BLAKE_XOR_ROTATE_16] =
            blake2s_tables::get_blake2s_xor_rotate_16_table(MultiTableId::BLAKE_XOR_ROTATE_16);
        tables[MultiTableId::BLAKE_XOR_ROTATE_8] =
            blake2s_tables::get_blake2s_xor_rotate_8_table(MultiTableId::BLAKE_XOR_ROTATE_8);
        tables[MultiTableId::BLAKE_XOR_ROTATE_7] =
            blake2s_tables::get_blake2s_xor_rotate_7_table(MultiTableId::BLAKE_XOR_ROTATE_7);
        tables[MultiTableId::KECCAK_FORMAT_INPUT] =
            keccak_tables::KeccakInput::get_keccak_input_table(MultiTableId::KECCAK_FORMAT_INPUT);
        tables[MultiTableId::KECCAK_THETA_OUTPUT] =
            keccak_tables::Theta::get_theta_output_table(MultiTableId::KECCAK_THETA_OUTPUT);
        tables[MultiTableId::KECCAK_CHI_OUTPUT] =
            keccak_tables::Chi::get_chi_output_table(MultiTableId::KECCAK_CHI_OUTPUT);
        tables[MultiTableId::KECCAK_FORMAT_OUTPUT] =
            keccak_tables::KeccakOutput::get_keccak_output_table(MultiTableId::KECCAK_FORMAT_OUTPUT);
        tables[MultiTableId::FIXED_BASE_LEFT_LO] =
            fixed_base::table::get_fixed_base_table<0, 128>(MultiTableId::FIXED_BASE_LEFT_LO);
        tables[MultiTableId::FIXED_BASE_LEFT_HI] =
            fixed_base::table::get_fixed_base_table<1, 126>(MultiTableId::FIXED_BASE_LEFT_HI);
        tables[MultiTableId::FIXED_BASE_RIGHT_LO] =
            fixed_base::table::get_fixed_base_table<2, 128>(MultiTableId::FIXED_BASE_RIGHT_LO);
        tables[MultiTableId::FIXED_BASE_RIGHT_HI] =
            fixed_base::table::get_fixed_base_table<3, 126>(MultiTableId::FIXED_BASE_RIGHT_HI);
 
        bb::constexpr_for<0, 25, 1>([&]<size_t i>() {
            tables[static_cast<size_t>(MultiTableId::KECCAK_NORMALIZE_AND_ROTATE) + i] =
                keccak_tables::Rho<8, i>::get_rho_output_table(MultiTableId::KECCAK_NORMALIZE_AND_ROTATE);
        });
        tables[MultiTableId::HONK_DUMMY_MULTI] = dummy_tables::get_honk_dummy_multitable();
        return tables;
    }();
    return MULTI_TABLES;
}
} // namespace
const MultiTable& get_multitable(const MultiTableId id)
{
    return get_multi_tables()[id];
}
 
ReadData<bb::fr> get_lookup_accumulators(const MultiTableId id,
                                         const fr& key_a,
                                         const fr& key_b,
                                         const bool is_2_to_1_lookup)
{
    // return multi-table, populating global array of all multi-tables if need be
    const auto& multi_table = get_multitable(id);
    const size_t num_lookups = multi_table.basic_table_ids.size();
 
    // All MultiTable vectors must be consistently sized
    BB_ASSERT_EQ(multi_table.column_1_coefficients.size(), num_lookups, "MultiTable coefficient/table count mismatch");
    BB_ASSERT_EQ(multi_table.get_table_values.size(), num_lookups, "MultiTable get_table_values/table count mismatch");
    BB_ASSERT_EQ(multi_table.slice_sizes.size(), num_lookups, "MultiTable slice_sizes/table count mismatch");
 
    ReadData<bb::fr> lookup;
    const auto key_a_slices = numeric::slice_input_using_variable_bases(key_a, multi_table.slice_sizes);
    const auto key_b_slices = numeric::slice_input_using_variable_bases(key_b, multi_table.slice_sizes);
 
    std::vector<fr> column_1_raw_values;
    std::vector<fr> column_2_raw_values;
    std::vector<fr> column_3_raw_values;
 
    for (size_t i = 0; i < num_lookups; ++i) {
        // compute the value(s) corresponding to the key(s) using the i-th basic table query function
        const auto values = multi_table.get_table_values[i]({ key_a_slices[i], key_b_slices[i] });
        // store all query data in raw columns and key entry
        column_1_raw_values.emplace_back(key_a_slices[i]);
        column_2_raw_values.emplace_back(is_2_to_1_lookup ? key_b_slices[i] : values[0]);
        column_3_raw_values.emplace_back(is_2_to_1_lookup ? values[0] : values[1]);
 
        // Store the lookup entries for use in constructing the sorted table/lookup polynomials later on
        const BasicTable::LookupEntry lookup_entry{ { key_a_slices[i], key_b_slices[i] }, values };
        lookup.lookup_entries.emplace_back(lookup_entry);
    }
 
    lookup[C1].resize(num_lookups);
    lookup[C2].resize(num_lookups);
    lookup[C3].resize(num_lookups);
 
    lookup[C1][num_lookups - 1] = column_1_raw_values[num_lookups - 1];
    lookup[C2][num_lookups - 1] = column_2_raw_values[num_lookups - 1];
    lookup[C3][num_lookups - 1] = column_3_raw_values[num_lookups - 1];
 
    for (size_t i = num_lookups - 1; i > 0; --i) {
        lookup[C1][i - 1] = column_1_raw_values[i - 1] + lookup[C1][i] * multi_table.column_1_step_sizes[i];
        lookup[C2][i - 1] = column_2_raw_values[i - 1] + lookup[C2][i] * multi_table.column_2_step_sizes[i];
        lookup[C3][i - 1] = column_3_raw_values[i - 1] + lookup[C3][i] * multi_table.column_3_step_sizes[i];
    }
    return lookup;
}
 
BasicTable create_basic_table(const BasicTableId id, const size_t index)
{
    // we have >50 basic fixed base tables so we match with some logic instead of a switch statement
    auto id_var = static_cast<size_t>(id);
    if (id_var >= static_cast<size_t>(FIXED_BASE_0_0) && id_var < static_cast<size_t>(FIXED_BASE_1_0)) {
        return fixed_base::table::generate_basic_fixed_base_table<0>(
            id, index, id_var - static_cast<size_t>(FIXED_BASE_0_0));
    }
    if (id_var >= static_cast<size_t>(FIXED_BASE_1_0) && id_var < static_cast<size_t>(FIXED_BASE_2_0)) {
        return fixed_base::table::generate_basic_fixed_base_table<1>(
            id, index, id_var - static_cast<size_t>(FIXED_BASE_1_0));
    }
    if (id_var >= static_cast<size_t>(FIXED_BASE_2_0) && id_var < static_cast<size_t>(FIXED_BASE_3_0)) {
        return fixed_base::table::generate_basic_fixed_base_table<2>(
            id, index, id_var - static_cast<size_t>(FIXED_BASE_2_0));
    }
    if (id_var >= static_cast<size_t>(FIXED_BASE_3_0) && id_var < static_cast<size_t>(HONK_DUMMY_BASIC1)) {
        return fixed_base::table::generate_basic_fixed_base_table<3>(
            id, index, id_var - static_cast<size_t>(FIXED_BASE_3_0));
    }
    switch (id) {
    case AES_SPARSE_MAP: {
        return sparse_tables::generate_sparse_table_with_rotation<9, 8, 0>(AES_SPARSE_MAP, index);
    }
    case AES_SBOX_MAP: {
        return aes128_tables::generate_aes_sbox_table(AES_SBOX_MAP, index);
    }
    case AES_SPARSE_NORMALIZE: {
        return aes128_tables::generate_aes_sparse_normalization_table(AES_SPARSE_NORMALIZE, index);
    }
    case SHA256_WITNESS_NORMALIZE: {
        return sha256_tables::generate_witness_extension_normalization_table(SHA256_WITNESS_NORMALIZE, index);
    }
    case SHA256_WITNESS_SLICE_3: {
        return sparse_tables::generate_sparse_table_with_rotation<16, 3, 0>(SHA256_WITNESS_SLICE_3, index);
    }
    case SHA256_WITNESS_SLICE_7_ROTATE_4: {
        return sparse_tables::generate_sparse_table_with_rotation<16, 7, 4>(SHA256_WITNESS_SLICE_7_ROTATE_4, index);
    }
    case SHA256_WITNESS_SLICE_8_ROTATE_7: {
        return sparse_tables::generate_sparse_table_with_rotation<16, 8, 7>(SHA256_WITNESS_SLICE_8_ROTATE_7, index);
    }
    case SHA256_WITNESS_SLICE_14_ROTATE_1: {
        return sparse_tables::generate_sparse_table_with_rotation<16, 14, 1>(SHA256_WITNESS_SLICE_14_ROTATE_1, index);
    }
    case SHA256_CH_NORMALIZE: {
        return sha256_tables::generate_choose_normalization_table(SHA256_CH_NORMALIZE, index);
    }
    case SHA256_MAJ_NORMALIZE: {
        return sha256_tables::generate_majority_normalization_table(SHA256_MAJ_NORMALIZE, index);
    }
    case SHA256_BASE28: {
        return sparse_tables::generate_sparse_table_with_rotation<28, 11, 0>(SHA256_BASE28, index);
    }
    case SHA256_BASE28_ROTATE6: {
        return sparse_tables::generate_sparse_table_with_rotation<28, 11, 6>(SHA256_BASE28_ROTATE6, index);
    }
    case SHA256_BASE28_ROTATE3: {
        return sparse_tables::generate_sparse_table_with_rotation<28, 11, 3>(SHA256_BASE28_ROTATE3, index);
    }
    case SHA256_BASE16: {
        return sparse_tables::generate_sparse_table_with_rotation<16, 11, 0>(SHA256_BASE16, index);
    }
    case SHA256_BASE16_ROTATE2: {
        return sparse_tables::generate_sparse_table_with_rotation<16, 11, 2>(SHA256_BASE16_ROTATE2, index);
    }
    case UINT_XOR_SLICE_6_ROTATE_0: {
        return uint_tables::generate_xor_rotate_table</*bits_per_slice=*/6, /*num_rotated_output_bits=*/0>(
            UINT_XOR_SLICE_6_ROTATE_0, index);
    }
    case UINT_XOR_SLICE_4_ROTATE_0: {
        return uint_tables::generate_xor_rotate_table</*bits_per_slice=*/4, /*num_rotated_output_bits=*/0>(
            UINT_XOR_SLICE_4_ROTATE_0, index);
    }
    case UINT_XOR_SLICE_2_ROTATE_0: {
        return uint_tables::generate_xor_rotate_table</*bits_per_slice=*/2, /*num_rotated_output_bits=*/0>(
            UINT_XOR_SLICE_2_ROTATE_0, index);
    }
    case UINT_AND_SLICE_6_ROTATE_0: {
        return uint_tables::generate_and_rotate_table</*bits_per_slice=*/6, /*num_rotated_output_bits=*/0>(
            UINT_AND_SLICE_6_ROTATE_0, index);
    }
    case UINT_AND_SLICE_4_ROTATE_0: {
        return uint_tables::generate_and_rotate_table</*bits_per_slice=*/4, /*num_rotated_output_bits=*/0>(
            UINT_AND_SLICE_4_ROTATE_0, index);
    }
    case UINT_AND_SLICE_2_ROTATE_0: {
        return uint_tables::generate_and_rotate_table</*bits_per_slice=*/2, /*num_rotated_output_bits=*/0>(
            UINT_AND_SLICE_2_ROTATE_0, index);
    }
    case SECP256K1_XLO_BASIC: {
        return ecc_generator_tables::ecc_generator_table<secp256k1::g1>::generate_xlo_table(SECP256K1_XLO_BASIC, index);
    }
    case SECP256K1_XHI_BASIC: {
        return ecc_generator_tables::ecc_generator_table<secp256k1::g1>::generate_xhi_table(SECP256K1_XHI_BASIC, index);
    }
    case SECP256K1_YLO_BASIC: {
        return ecc_generator_tables::ecc_generator_table<secp256k1::g1>::generate_ylo_table(SECP256K1_YLO_BASIC, index);
    }
    case SECP256K1_YHI_BASIC: {
        return ecc_generator_tables::ecc_generator_table<secp256k1::g1>::generate_yhi_table(SECP256K1_YHI_BASIC, index);
    }
    case SECP256K1_XYPRIME_BASIC: {
        return ecc_generator_tables::ecc_generator_table<secp256k1::g1>::generate_xyprime_table(SECP256K1_XYPRIME_BASIC,
                                                                                                index);
    }
    case SECP256K1_XLO_ENDO_BASIC: {
        return ecc_generator_tables::ecc_generator_table<secp256k1::g1>::generate_xlo_endo_table(
            SECP256K1_XLO_ENDO_BASIC, index);
    }
    case SECP256K1_XHI_ENDO_BASIC: {
        return ecc_generator_tables::ecc_generator_table<secp256k1::g1>::generate_xhi_endo_table(
            SECP256K1_XHI_ENDO_BASIC, index);
    }
    case SECP256K1_XYPRIME_ENDO_BASIC: {
        return ecc_generator_tables::ecc_generator_table<secp256k1::g1>::generate_xyprime_endo_table(
            SECP256K1_XYPRIME_ENDO_BASIC, index);
    }
    case BLAKE_XOR_ROTATE0: {
        return blake2s_tables::generate_xor_rotate_table<6, 0>(BLAKE_XOR_ROTATE0, index);
    }
    case BLAKE_XOR_ROTATE0_SLICE5_MOD4: {
        return blake2s_tables::generate_xor_rotate_table<5, 0, true>(BLAKE_XOR_ROTATE0_SLICE5_MOD4, index);
    }
    case BLAKE_XOR_ROTATE2: {
        return blake2s_tables::generate_xor_rotate_table<6, 2>(BLAKE_XOR_ROTATE2, index);
    }
    case BLAKE_XOR_ROTATE1: {
        return blake2s_tables::generate_xor_rotate_table<6, 1>(BLAKE_XOR_ROTATE1, index);
    }
    case BLAKE_XOR_ROTATE4: {
        return blake2s_tables::generate_xor_rotate_table<6, 4>(BLAKE_XOR_ROTATE4, index);
    }
    case HONK_DUMMY_BASIC1: {
        return dummy_tables::generate_honk_dummy_table<HONK_DUMMY_BASIC1>(HONK_DUMMY_BASIC1, index);
    }
    case HONK_DUMMY_BASIC2: {
        return dummy_tables::generate_honk_dummy_table<HONK_DUMMY_BASIC2>(HONK_DUMMY_BASIC2, index);
    }
    case KECCAK_INPUT: {
        return keccak_tables::KeccakInput::generate_keccak_input_table(KECCAK_INPUT, index);
    }
    case KECCAK_THETA: {
        return keccak_tables::Theta::generate_theta_renormalization_table(KECCAK_THETA, index);
    }
    case KECCAK_CHI: {
        return keccak_tables::Chi::generate_chi_renormalization_table(KECCAK_CHI, index);
    }
    case KECCAK_OUTPUT: {
        return keccak_tables::KeccakOutput::generate_keccak_output_table(KECCAK_OUTPUT, index);
    }
    case KECCAK_RHO_1: {
        return keccak_tables::Rho<1>::generate_rho_renormalization_table(KECCAK_RHO_1, index);
    }
    case KECCAK_RHO_2: {
        return keccak_tables::Rho<2>::generate_rho_renormalization_table(KECCAK_RHO_2, index);
    }
    case KECCAK_RHO_3: {
        return keccak_tables::Rho<3>::generate_rho_renormalization_table(KECCAK_RHO_3, index);
    }
    case KECCAK_RHO_4: {
        return keccak_tables::Rho<4>::generate_rho_renormalization_table(KECCAK_RHO_4, index);
    }
    case KECCAK_RHO_5: {
        return keccak_tables::Rho<5>::generate_rho_renormalization_table(KECCAK_RHO_5, index);
    }
    case KECCAK_RHO_6: {
        return keccak_tables::Rho<6>::generate_rho_renormalization_table(KECCAK_RHO_6, index);
    }
    case KECCAK_RHO_7: {
        return keccak_tables::Rho<7>::generate_rho_renormalization_table(KECCAK_RHO_7, index);
    }
    case KECCAK_RHO_8: {
        return keccak_tables::Rho<8>::generate_rho_renormalization_table(KECCAK_RHO_8, index);
    }
    default: {
        throw_or_abort("table id does not exist");
        return sparse_tables::generate_sparse_table_with_rotation<9, 8, 0>(AES_SPARSE_MAP, index);
    }
    }
}
} // namespace bb::plookup