keccak_chi.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: not started, auditors: [], date: YYYY-MM-DD }
// external_1:  { status: not started, auditors: [], date: YYYY-MM-DD }
// external_2:  { status: not started, auditors: [], date: YYYY-MM-DD }
// =====================
 
#pragma once
 
#include "../types.hpp"
#include "barretenberg/common/constexpr_utils.hpp"
#include "barretenberg/numeric/bitop/pow.hpp"
 
namespace bb::plookup::keccak_tables {
 
class Chi {
  public:
    // 1 + 2a - b + c => a xor (~b & c)
    static constexpr uint64_t CHI_NORMALIZATION_TABLE[5]{
        0, 0, 1, 1, 0,
    };
 
    static constexpr uint64_t BASE = 11;
 
    // effective base = maximum value each input 'quasi-bit' can reach at this stage of the Keccak algo
    // (we use base11 as it's a bit more efficient to use a consistent base across the entire Keccak hash algorithm.
    //  The THETA round requires base-11 in order to most efficiently convert XOR operations into algebraic operations)
    static constexpr uint64_t EFFECTIVE_BASE = 5;
 
    // TABLE_BITS defines table size. More bits = fewer lookups but larger tables!
    static constexpr uint64_t TABLE_BITS = 6;
 
    static std::array<bb::fr, 2> get_chi_renormalization_values(const std::array<uint64_t, 2> key)
    {
        uint64_t accumulator = 0;
        uint64_t input = key[0];
        uint64_t base_shift = 1;
        constexpr uint64_t divisor_exponent = (64 % TABLE_BITS == 0) ? (TABLE_BITS - 1) : (64 % TABLE_BITS) - 1;
        constexpr uint64_t divisor = numeric::pow64(BASE, divisor_exponent);
        while (input > 0) {
            uint64_t slice = input % BASE;
            uint64_t bit = CHI_NORMALIZATION_TABLE[static_cast<size_t>(slice)];
            accumulator += (bit * base_shift);
            input /= BASE;
            base_shift *= BASE;
        }
 
        return { bb::fr(accumulator), bb::fr(accumulator / divisor) };
    }
 
    static constexpr std::array<uint64_t, TABLE_BITS> get_scaled_bases()
    {
        std::array<uint64_t, TABLE_BITS> result;
        uint64_t acc = 1;
        for (size_t i = 0; i < TABLE_BITS; ++i) {
            result[i] = acc;
            acc *= BASE;
        }
        return result;
    }
 
    static std::array<uint64_t, 3> get_column_values_for_next_row(std::array<size_t, TABLE_BITS>& counts)
    {
        static constexpr auto scaled_bases = get_scaled_bases();
 
        // want the most significant bit of the 64-bit integer, when this table is used on the most significant slice
        constexpr uint64_t divisor_exponent = (64 % TABLE_BITS == 0) ? (TABLE_BITS - 1) : (64 % TABLE_BITS) - 1;
        constexpr uint64_t divisor = numeric::pow64(static_cast<uint64_t>(BASE), divisor_exponent);
 
        for (size_t i = 0; i < TABLE_BITS; ++i) {
            if (counts[i] == EFFECTIVE_BASE - 1) {
                counts[i] = 0;
            } else {
                counts[i] += 1;
                break;
            }
        }
 
        uint64_t value = 0;
        uint64_t normalized_value = 0;
        for (size_t i = 0; i < TABLE_BITS; ++i) {
            value += counts[i] * scaled_bases[i];
            normalized_value += (CHI_NORMALIZATION_TABLE[counts[i]]) * scaled_bases[i];
        }
        return { value, normalized_value, normalized_value / divisor };
    }
 
    static BasicTable generate_chi_renormalization_table(BasicTableId id, const size_t table_index)
    {
        BasicTable table;
        table.id = id;
        table.table_index = table_index;
        table.use_twin_keys = false;
        auto table_size = numeric::pow64(static_cast<uint64_t>(EFFECTIVE_BASE), TABLE_BITS);
 
        std::array<size_t, TABLE_BITS> counts{};
        std::array<uint64_t, 3> column_values{ 0, 0, 0 };
        for (size_t i = 0; i < table_size; ++i) {
            table.column_1.emplace_back(column_values[0]);
            table.column_2.emplace_back(column_values[1]);
            table.column_3.emplace_back(column_values[2]);
            column_values = get_column_values_for_next_row(counts);
        }
 
        table.get_values_from_key = &get_chi_renormalization_values;
 
        constexpr uint64_t step_size = numeric::pow64(static_cast<uint64_t>(BASE), TABLE_BITS);
        table.column_1_step_size = bb::fr(step_size);
        table.column_2_step_size = bb::fr(step_size);
        table.column_3_step_size = bb::fr(0);
        return table;
    }
 
    static MultiTable get_chi_output_table(const MultiTableId id = KECCAK_CHI_OUTPUT)
    {
        constexpr size_t num_tables_per_multitable =
            (64 / TABLE_BITS) + (64 % TABLE_BITS == 0 ? 0 : 1); // 64 bits, 8 bits per entry
 
        // column_multiplier is used to define the gap between rows when deriving colunn values via relative differences
        uint64_t column_multiplier = numeric::pow64(BASE, TABLE_BITS);
        MultiTable table(column_multiplier, column_multiplier, 0, num_tables_per_multitable);
 
        table.id = id;
        for (size_t i = 0; i < num_tables_per_multitable; ++i) {
            table.slice_sizes.emplace_back(numeric::pow64(BASE, TABLE_BITS));
            table.basic_table_ids.emplace_back(KECCAK_CHI);
            table.get_table_values.emplace_back(&get_chi_renormalization_values);
        }
        return table;
    }
};
} // namespace bb::plookup::keccak_tables