keccak_rho.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 {
 
template <size_t TABLE_BITS = 0, size_t LANE_INDEX = 0> class Rho {
 
  public:
    static constexpr uint64_t BASE = 11;
 
    // EFFECTIVE_BASE = maximum value each input 'quasi-bit' can reach at this stage in 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 = 3;
 
    // The maximum number of bits of a Rho lookup table (TABLE_BITS <= MAXIMUM_MULTITABLE_BITS).
    // Used in get_rho_output_table
    static constexpr size_t MAXIMUM_MULTITABLE_BITS = 8;
 
    // Rotation offsets, y vertically, x horizontally: r[y * 5 + x]
    static constexpr std::array<size_t, 25> ROTATIONS = {
        0, 1, 62, 28, 27, 36, 44, 6, 55, 20, 3, 10, 43, 25, 39, 41, 45, 15, 21, 8, 18, 2, 61, 56, 14,
    };
 
    static constexpr uint64_t RHO_NORMALIZATION_TABLE[3]{
        0,
        1,
        0,
    };
 
    static std::array<bb::fr, 2> get_rho_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 = TABLE_BITS - 1;
        constexpr uint64_t divisor = numeric::pow64(BASE, divisor_exponent);
        while (input > 0) {
            uint64_t slice = input % BASE;
            uint64_t bit = RHO_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 = numeric::pow64(static_cast<uint64_t>(BASE), TABLE_BITS - 1);
 
        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 += (RHO_NORMALIZATION_TABLE[counts[i]]) * scaled_bases[i];
        }
        return { value, normalized_value, normalized_value / divisor };
    }
 
    static BasicTable generate_rho_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_rho_renormalization_values;
 
        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_rho_output_table(const MultiTableId id = KECCAK_NORMALIZE_AND_ROTATE)
    {
        constexpr size_t left_bits = ROTATIONS[LANE_INDEX];
        constexpr size_t right_bits = 64 - ROTATIONS[LANE_INDEX];
        constexpr size_t num_left_tables =
            left_bits / MAXIMUM_MULTITABLE_BITS + (left_bits % MAXIMUM_MULTITABLE_BITS > 0 ? 1 : 0);
        constexpr size_t num_right_tables =
            right_bits / MAXIMUM_MULTITABLE_BITS + (right_bits % MAXIMUM_MULTITABLE_BITS > 0 ? 1 : 0);
 
        MultiTable table;
        table.id = id;
 
        table.column_1_step_sizes.push_back(1);
        table.column_2_step_sizes.push_back(1);
        table.column_3_step_sizes.push_back(1);
 
        // generate table selector values for the 'right' slice
        bb::constexpr_for<0, num_right_tables, 1>([&]<size_t i> {
            constexpr size_t num_bits_processed = (i * MAXIMUM_MULTITABLE_BITS);
            constexpr size_t bit_slice = (num_bits_processed + MAXIMUM_MULTITABLE_BITS > right_bits)
                                             ? right_bits % MAXIMUM_MULTITABLE_BITS
                                             : MAXIMUM_MULTITABLE_BITS;
 
            constexpr uint64_t scaled_base = numeric::pow64(BASE, bit_slice);
            if (i == num_right_tables - 1) {
                table.column_1_step_sizes.push_back(scaled_base);
                table.column_2_step_sizes.push_back(0);
                table.column_3_step_sizes.push_back(0);
            } else {
                table.column_1_step_sizes.push_back(scaled_base);
                table.column_2_step_sizes.push_back(scaled_base);
                table.column_3_step_sizes.push_back(0);
            }
 
            table.slice_sizes.push_back(scaled_base);
            table.get_table_values.emplace_back(&get_rho_renormalization_values);
            table.basic_table_ids.push_back((BasicTableId)((size_t)KECCAK_RHO_1 + (bit_slice - 1)));
        });
 
        // generate table selector values for the 'left' slice
        bb::constexpr_for<0, num_left_tables, 1>([&]<size_t i> {
            constexpr size_t num_bits_processed = (i * MAXIMUM_MULTITABLE_BITS);
 
            constexpr size_t bit_slice = (num_bits_processed + MAXIMUM_MULTITABLE_BITS > left_bits)
                                             ? left_bits % MAXIMUM_MULTITABLE_BITS
                                             : MAXIMUM_MULTITABLE_BITS;
            constexpr uint64_t scaled_base = numeric::pow64(BASE, bit_slice);
 
            if (i != num_left_tables - 1) {
                table.column_1_step_sizes.push_back(scaled_base);
                table.column_2_step_sizes.push_back(scaled_base);
                table.column_3_step_sizes.push_back(0);
            }
 
            table.slice_sizes.push_back(scaled_base);
            table.get_table_values.emplace_back(&get_rho_renormalization_values);
            table.basic_table_ids.push_back((BasicTableId)((size_t)KECCAK_RHO_1 + (bit_slice - 1)));
        });
 
        return table;
    }
};
 
} // namespace bb::plookup::keccak_tables