non_native_group_generator.cpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Suyash], commit: 553c5eb82901955c638b943065acd3e47fc918c0}
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#include "non_native_group_generator.hpp"
 
namespace bb::plookup::ecc_generator_tables {
 
template <typename G1> void ecc_generator_table<G1>::init_generator_tables()
{
    std::call_once(init_flag, []() {
        element base_point = G1::one;
 
        auto d2 = base_point.dbl();
        std::array<element, TABLE_SIZE> point_table;
        point_table[TABLE_SIZE / 2] = base_point;
        for (size_t i = 1; i < TABLE_SIZE / 2; ++i) {
            point_table[i + TABLE_SIZE / 2] = point_table[i + TABLE_SIZE / 2 - 1] + d2;
        }
        for (size_t i = 0; i < TABLE_SIZE / 2; ++i) {
            point_table[TABLE_SIZE / 2 - 1 - i] = -point_table[TABLE_SIZE / 2 + i];
        }
        element::batch_normalize(&point_table[0], TABLE_SIZE);
 
        auto beta = G1::Fq::cube_root_of_unity();
        for (size_t i = 0; i < TABLE_SIZE; ++i) {
            uint256_t endo_x = static_cast<uint256_t>(point_table[i].x * beta);
            uint256_t x = static_cast<uint256_t>(point_table[i].x);
            uint256_t y = static_cast<uint256_t>(point_table[i].y);
 
            // Store the values in prime-basis lookup tables
            ecc_generator_table<G1>::generator_xyprime_table[i] = std::make_pair(bb::fr(x), bb::fr(y));
            ecc_generator_table<G1>::generator_endo_xyprime_table[i] = std::make_pair(bb::fr(endo_x), bb::fr(y));
 
            // Compute x limbs
            constexpr size_t num_limb_bits = stdlib::NUM_LIMB_BITS_IN_FIELD_SIMULATION;
            const uint256_t SHIFT = uint256_t(1) << num_limb_bits;
            const uint256_t MASK = SHIFT - 1;
            uint256_t x0 = x & MASK;
            x = x >> num_limb_bits;
            uint256_t x1 = x & MASK;
            x = x >> num_limb_bits;
            uint256_t x2 = x & MASK;
            x = x >> num_limb_bits;
            uint256_t x3 = x & MASK;
 
            // Compute endo x limbs
            uint256_t endox0 = endo_x & MASK;
            endo_x = endo_x >> num_limb_bits;
            uint256_t endox1 = endo_x & MASK;
            endo_x = endo_x >> num_limb_bits;
            uint256_t endox2 = endo_x & MASK;
            endo_x = endo_x >> num_limb_bits;
            uint256_t endox3 = endo_x & MASK;
 
            // Compute y limbs
            uint256_t y0 = y & MASK;
            y = y >> num_limb_bits;
            uint256_t y1 = y & MASK;
            y = y >> num_limb_bits;
            uint256_t y2 = y & MASK;
            y = y >> num_limb_bits;
            uint256_t y3 = y & MASK;
 
            // Store the limb values in the respective lookup tables
            ecc_generator_table<G1>::generator_xlo_table[i] = std::make_pair(x0, x1);
            ecc_generator_table<G1>::generator_xhi_table[i] = std::make_pair(x2, x3);
            ecc_generator_table<G1>::generator_endo_xlo_table[i] = std::make_pair(endox0, endox1);
            ecc_generator_table<G1>::generator_endo_xhi_table[i] = std::make_pair(endox2, endox3);
            ecc_generator_table<G1>::generator_ylo_table[i] = std::make_pair(y0, y1);
            ecc_generator_table<G1>::generator_yhi_table[i] = std::make_pair(y2, y3);
        }
    });
}
 
template <typename G1> std::array<bb::fr, 2> ecc_generator_table<G1>::get_xlo_values(const std::array<uint64_t, 2> key)
{
    init_generator_tables();
    const size_t index = static_cast<size_t>(key[0]);
    BB_ASSERT(index < TABLE_SIZE, "xlo table key out of range");
    return { ecc_generator_table<G1>::generator_xlo_table[index].first,
             ecc_generator_table<G1>::generator_xlo_table[index].second };
}
 
template <typename G1> std::array<bb::fr, 2> ecc_generator_table<G1>::get_xhi_values(const std::array<uint64_t, 2> key)
{
    init_generator_tables();
    const size_t index = static_cast<size_t>(key[0]);
    BB_ASSERT(index < TABLE_SIZE, "xhi table key out of range");
    return { ecc_generator_table<G1>::generator_xhi_table[index].first,
             ecc_generator_table<G1>::generator_xhi_table[index].second };
}
 
template <typename G1>
std::array<bb::fr, 2> ecc_generator_table<G1>::get_xlo_endo_values(const std::array<uint64_t, 2> key)
{
    init_generator_tables();
    const size_t index = static_cast<size_t>(key[0]);
    BB_ASSERT(index < TABLE_SIZE, "xlo_endo table key out of range");
    return { ecc_generator_table<G1>::generator_endo_xlo_table[index].first,
             ecc_generator_table<G1>::generator_endo_xlo_table[index].second };
}
 
template <typename G1>
std::array<bb::fr, 2> ecc_generator_table<G1>::get_xhi_endo_values(const std::array<uint64_t, 2> key)
{
    init_generator_tables();
    const size_t index = static_cast<size_t>(key[0]);
    BB_ASSERT(index < TABLE_SIZE, "xhi_endo table key out of range");
    return { ecc_generator_table<G1>::generator_endo_xhi_table[index].first,
             ecc_generator_table<G1>::generator_endo_xhi_table[index].second };
}
 
template <typename G1> std::array<bb::fr, 2> ecc_generator_table<G1>::get_ylo_values(const std::array<uint64_t, 2> key)
{
    init_generator_tables();
    const size_t index = static_cast<size_t>(key[0]);
    BB_ASSERT(index < TABLE_SIZE, "ylo table key out of range");
    return { ecc_generator_table<G1>::generator_ylo_table[index].first,
             ecc_generator_table<G1>::generator_ylo_table[index].second };
}
 
template <typename G1> std::array<bb::fr, 2> ecc_generator_table<G1>::get_yhi_values(const std::array<uint64_t, 2> key)
{
    init_generator_tables();
    const size_t index = static_cast<size_t>(key[0]);
    BB_ASSERT(index < TABLE_SIZE, "yhi table key out of range");
    return { ecc_generator_table<G1>::generator_yhi_table[index].first,
             ecc_generator_table<G1>::generator_yhi_table[index].second };
}
 
template <typename G1>
std::array<bb::fr, 2> ecc_generator_table<G1>::get_xyprime_values(const std::array<uint64_t, 2> key)
{
    init_generator_tables();
    const size_t index = static_cast<size_t>(key[0]);
    BB_ASSERT(index < TABLE_SIZE, "xyprime table key out of range");
    return { ecc_generator_table<G1>::generator_xyprime_table[index].first,
             ecc_generator_table<G1>::generator_xyprime_table[index].second };
}
 
template <typename G1>
std::array<bb::fr, 2> ecc_generator_table<G1>::get_xyprime_endo_values(const std::array<uint64_t, 2> key)
{
    init_generator_tables();
    const size_t index = static_cast<size_t>(key[0]);
    BB_ASSERT(index < TABLE_SIZE, "xyprime_endo table key out of range");
    return { ecc_generator_table<G1>::generator_endo_xyprime_table[index].first,
             ecc_generator_table<G1>::generator_endo_xyprime_table[index].second };
}
 
template <typename G1> BasicTable ecc_generator_table<G1>::generate_xlo_table(BasicTableId id, const size_t table_index)
{
    BasicTable table;
    table.id = id;
    table.table_index = table_index;
    size_t table_size = TABLE_SIZE;
    table.use_twin_keys = false;
 
    for (size_t i = 0; i < table_size; ++i) {
        table.column_1.emplace_back((i));
        table.column_2.emplace_back(ecc_generator_table<G1>::generator_xlo_table[i].first);
        table.column_3.emplace_back(ecc_generator_table<G1>::generator_xlo_table[i].second);
    }
 
    table.get_values_from_key = &get_xlo_values;
 
    table.column_1_step_size = 0;
    table.column_2_step_size = 0;
    table.column_3_step_size = 0;
 
    return table;
}
 
template <typename G1> BasicTable ecc_generator_table<G1>::generate_xhi_table(BasicTableId id, const size_t table_index)
{
    BasicTable table;
    table.id = id;
    table.table_index = table_index;
    size_t table_size = TABLE_SIZE;
    table.use_twin_keys = false;
 
    for (size_t i = 0; i < table_size; ++i) {
        table.column_1.emplace_back((i));
        table.column_2.emplace_back(ecc_generator_table<G1>::generator_xhi_table[i].first);
        table.column_3.emplace_back(ecc_generator_table<G1>::generator_xhi_table[i].second);
    }
 
    table.get_values_from_key = &get_xhi_values;
 
    table.column_1_step_size = 0;
    table.column_2_step_size = 0;
    table.column_3_step_size = 0;
 
    return table;
}
 
template <typename G1>
BasicTable ecc_generator_table<G1>::generate_xlo_endo_table(BasicTableId id, const size_t table_index)
{
    BasicTable table;
    table.id = id;
    table.table_index = table_index;
    size_t table_size = TABLE_SIZE;
    table.use_twin_keys = false;
 
    for (size_t i = 0; i < table_size; ++i) {
        table.column_1.emplace_back((i));
        table.column_2.emplace_back(ecc_generator_table<G1>::generator_endo_xlo_table[i].first);
        table.column_3.emplace_back(ecc_generator_table<G1>::generator_endo_xlo_table[i].second);
    }
 
    table.get_values_from_key = &get_xlo_endo_values;
 
    table.column_1_step_size = 0;
    table.column_2_step_size = 0;
    table.column_3_step_size = 0;
 
    return table;
}
 
template <typename G1>
BasicTable ecc_generator_table<G1>::generate_xhi_endo_table(BasicTableId id, const size_t table_index)
{
    BasicTable table;
    table.id = id;
    table.table_index = table_index;
    size_t table_size = TABLE_SIZE;
    table.use_twin_keys = false;
 
    for (size_t i = 0; i < table_size; ++i) {
        table.column_1.emplace_back((i));
        table.column_2.emplace_back(ecc_generator_table<G1>::generator_endo_xhi_table[i].first);
        table.column_3.emplace_back(ecc_generator_table<G1>::generator_endo_xhi_table[i].second);
    }
 
    table.get_values_from_key = &get_xhi_endo_values;
 
    table.column_1_step_size = 0;
    table.column_2_step_size = 0;
    table.column_3_step_size = 0;
 
    return table;
}
 
template <typename G1> BasicTable ecc_generator_table<G1>::generate_ylo_table(BasicTableId id, const size_t table_index)
{
    BasicTable table;
    table.id = id;
    table.table_index = table_index;
    size_t table_size = TABLE_SIZE;
    table.use_twin_keys = false;
 
    for (size_t i = 0; i < table_size; ++i) {
        table.column_1.emplace_back((i));
        table.column_2.emplace_back(ecc_generator_table<G1>::generator_ylo_table[i].first);
        table.column_3.emplace_back(ecc_generator_table<G1>::generator_ylo_table[i].second);
    }
 
    table.get_values_from_key = &get_ylo_values;
 
    table.column_1_step_size = 0;
    table.column_2_step_size = 0;
    table.column_3_step_size = 0;
 
    return table;
}
 
template <typename G1> BasicTable ecc_generator_table<G1>::generate_yhi_table(BasicTableId id, const size_t table_index)
{
    BasicTable table;
    table.id = id;
    table.table_index = table_index;
    size_t table_size = TABLE_SIZE;
    table.use_twin_keys = false;
 
    for (size_t i = 0; i < table_size; ++i) {
        table.column_1.emplace_back((i));
        table.column_2.emplace_back(ecc_generator_table<G1>::generator_yhi_table[i].first);
        table.column_3.emplace_back(ecc_generator_table<G1>::generator_yhi_table[i].second);
    }
 
    table.get_values_from_key = &get_yhi_values;
 
    table.column_1_step_size = 0;
    table.column_2_step_size = 0;
    table.column_3_step_size = 0;
 
    return table;
}
 
template <typename G1>
BasicTable ecc_generator_table<G1>::generate_xyprime_table(BasicTableId id, const size_t table_index)
{
    BasicTable table;
    table.id = id;
    table.table_index = table_index;
    size_t table_size = TABLE_SIZE;
    table.use_twin_keys = false;
 
    for (size_t i = 0; i < table_size; ++i) {
        table.column_1.emplace_back((i));
        table.column_2.emplace_back(ecc_generator_table<G1>::generator_xyprime_table[i].first);
        table.column_3.emplace_back(ecc_generator_table<G1>::generator_xyprime_table[i].second);
    }
 
    table.get_values_from_key = &get_xyprime_values;
 
    table.column_1_step_size = 0;
    table.column_2_step_size = 0;
    table.column_3_step_size = 0;
 
    return table;
}
 
template <typename G1>
BasicTable ecc_generator_table<G1>::generate_xyprime_endo_table(BasicTableId id, const size_t table_index)
{
    BasicTable table;
    table.id = id;
    table.table_index = table_index;
    size_t table_size = TABLE_SIZE;
    table.use_twin_keys = false;
 
    for (size_t i = 0; i < table_size; ++i) {
        table.column_1.emplace_back((i));
        table.column_2.emplace_back(ecc_generator_table<G1>::generator_endo_xyprime_table[i].first);
        table.column_3.emplace_back(ecc_generator_table<G1>::generator_endo_xyprime_table[i].second);
    }
 
    table.get_values_from_key = &get_xyprime_endo_values;
 
    table.column_1_step_size = 0;
    table.column_2_step_size = 0;
    table.column_3_step_size = 0;
 
    return table;
}
 
template <typename G1>
MultiTable ecc_generator_table<G1>::get_xlo_table(const MultiTableId id, const BasicTableId basic_id)
{
    const size_t num_entries = 1;
    MultiTable table(TABLE_SIZE, 0, 0, 1);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(TABLE_SIZE);
        table.basic_table_ids.emplace_back(basic_id);
        table.get_table_values.emplace_back(&get_xlo_values);
    }
    return table;
}
 
template <typename G1>
MultiTable ecc_generator_table<G1>::get_xhi_table(const MultiTableId id, const BasicTableId basic_id)
{
    const size_t num_entries = 1;
    MultiTable table(TABLE_SIZE, 0, 0, 1);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(TABLE_SIZE);
        table.basic_table_ids.emplace_back(basic_id);
        table.get_table_values.emplace_back(&get_xhi_values);
    }
    return table;
}
 
template <typename G1>
MultiTable ecc_generator_table<G1>::get_xlo_endo_table(const MultiTableId id, const BasicTableId basic_id)
{
    const size_t num_entries = 1;
    MultiTable table(TABLE_SIZE, 0, 0, 1);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(TABLE_SIZE);
        table.basic_table_ids.emplace_back(basic_id);
        table.get_table_values.emplace_back(&get_xlo_endo_values);
    }
    return table;
}
 
template <typename G1>
MultiTable ecc_generator_table<G1>::get_xhi_endo_table(const MultiTableId id, const BasicTableId basic_id)
{
    const size_t num_entries = 1;
    MultiTable table(TABLE_SIZE, 0, 0, 1);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(TABLE_SIZE);
        table.basic_table_ids.emplace_back(basic_id);
        table.get_table_values.emplace_back(&get_xhi_endo_values);
    }
    return table;
}
 
template <typename G1>
MultiTable ecc_generator_table<G1>::get_ylo_table(const MultiTableId id, const BasicTableId basic_id)
{
    const size_t num_entries = 1;
    MultiTable table(TABLE_SIZE, 0, 0, 1);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(TABLE_SIZE);
        table.basic_table_ids.emplace_back(basic_id);
        table.get_table_values.emplace_back(&get_ylo_values);
    }
    return table;
}
 
template <typename G1>
MultiTable ecc_generator_table<G1>::get_yhi_table(const MultiTableId id, const BasicTableId basic_id)
{
    const size_t num_entries = 1;
    MultiTable table(TABLE_SIZE, 0, 0, 1);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(TABLE_SIZE);
        table.basic_table_ids.emplace_back(basic_id);
        table.get_table_values.emplace_back(&get_yhi_values);
    }
    return table;
}
 
template <typename G1>
MultiTable ecc_generator_table<G1>::get_xyprime_table(const MultiTableId id, const BasicTableId basic_id)
{
    const size_t num_entries = 1;
    MultiTable table(TABLE_SIZE, 0, 0, 1);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(TABLE_SIZE);
        table.basic_table_ids.emplace_back(basic_id);
        table.get_table_values.emplace_back(&get_xyprime_values);
    }
    return table;
}
 
template <typename G1>
MultiTable ecc_generator_table<G1>::get_xyprime_endo_table(const MultiTableId id, const BasicTableId basic_id)
{
    const size_t num_entries = 1;
    MultiTable table(TABLE_SIZE, 0, 0, 1);
 
    table.id = id;
    for (size_t i = 0; i < num_entries; ++i) {
        table.slice_sizes.emplace_back(TABLE_SIZE);
        table.basic_table_ids.emplace_back(basic_id);
        table.get_table_values.emplace_back(&get_xyprime_endo_values);
    }
    return table;
}
template class ecc_generator_table<secp256k1::g1>;
 
} // namespace bb::plookup::ecc_generator_tables