keccakf1600.cpp

Go to the documentation of this file.

#include "barretenberg/vm2/simulation/gadgets/keccakf1600.hpp"
 
#include <cstddef>
 
#include "barretenberg/aztec/aztec_constants.hpp"
#include "barretenberg/common/assert.hpp"
#include "barretenberg/common/log.hpp"
 
namespace bb::avm2::simulation {
 
namespace {
 
MemoryValue unconstrained_rotate_left(MemoryValue x, uint8_t len)
{
    // We avoid an undefined behavior in the shift below: "x_uint64_t >> (64 - len)"
    // if it were evaluated with len = 0. (cpp standard on bitwise shifts requires rhs
    // to be less than the number of bits in lhs).
    if (len == 0) {
        return x;
    }
 
    const auto x_uint64_t = x.as<uint64_t>();
    BB_ASSERT_LT(len, 64, "Length out of bounds");
    const auto out_uint64_t = (x_uint64_t << len) | x_uint64_t >> (64 - len);
    return MemoryValue::from(out_uint64_t);
}
 
template <size_t N, size_t M>
std::array<std::array<uint64_t, M>, N> two_dim_array_to_uint64(const std::array<std::array<MemoryValue, M>, N>& input)
{
    std::array<std::array<uint64_t, M>, N> output;
    for (size_t i = 0; i < N; i++) {
        for (size_t j = 0; j < M; j++) {
            output[i][j] = input[i][j].template as<uint64_t>();
        }
    }
    return output;
}
 
template <size_t N> std::array<uint64_t, N> array_to_uint64(const std::array<MemoryValue, N>& input)
{
    std::array<uint64_t, N> output;
    for (size_t i = 0; i < N; i++) {
        output[i] = input[i].template as<uint64_t>();
    }
    return output;
}
 
} // namespace
 
void KeccakF1600::permutation(MemoryInterface& memory, MemoryAddress dst_addr, MemoryAddress src_addr)
{
    KeccakF1600Event keccakf1600_event;
    keccakf1600_event.execution_clk = execution_id_manager.get_execution_id();
    keccakf1600_event.dst_addr = dst_addr;
    keccakf1600_event.src_addr = src_addr;
 
    try {
        // We need to perform two bound checks to determine whether dst_addr and src_addr correspond to
        // a memory slice which is out-of-range.
        constexpr MemoryAddress HIGHEST_SLICE_ADDRESS = AVM_HIGHEST_MEM_ADDRESS - AVM_KECCAKF1600_STATE_SIZE + 1;
 
        // We group both possible out-of-range errors in the same temporality group.
        // Therefore, we perform both bound checks no matter what.
        bool src_out_of_range = gt.gt(static_cast<uint128_t>(src_addr), static_cast<uint128_t>(HIGHEST_SLICE_ADDRESS));
        bool dst_out_of_range = gt.gt(static_cast<uint128_t>(dst_addr), static_cast<uint128_t>(HIGHEST_SLICE_ADDRESS));
 
        keccakf1600_event.src_out_of_range = src_out_of_range;
        keccakf1600_event.dst_out_of_range = dst_out_of_range;
        keccakf1600_event.space_id = memory.get_space_id();
 
        if (src_out_of_range) {
            throw KeccakF1600Exception(format("Read slice out of range: ", src_addr));
        }
        if (dst_out_of_range) {
            throw KeccakF1600Exception(format("Write slice out of range: ", dst_addr));
        }
 
        // We work with MemoryValue as this type is required for bitwise operations handled
        // by the bitwise sub-trace simulator. We continue by operating over Memory values and convert
        // them back only at the end (event emission).
        std::array<MemoryValue, AVM_KECCAKF1600_STATE_SIZE> src_mem_values{ MemoryValue::from<uint64_t>(0) };
 
        // Slice read and tag check
        for (size_t k = 0; k < AVM_KECCAKF1600_STATE_SIZE; k++) {
            const auto addr = src_addr + static_cast<MemoryAddress>(k);
            const MemoryValue& mem_val = memory.get(addr);
            const MemoryTag tag = mem_val.get_tag();
            src_mem_values[k] = mem_val;
 
            if (tag != MemoryTag::U64) {
                keccakf1600_event.tag_error = true;
                keccakf1600_event.src_mem_values = src_mem_values;
 
                throw KeccakF1600Exception(
                    format("Read slice tag invalid - addr: ", addr, " tag: ", static_cast<uint32_t>(tag)));
            }
        }
 
        keccakf1600_event.src_mem_values = src_mem_values;
 
        // Initialize state input values with values read from memory.
        // Standard Keccak layout: memory[(y * 5) + x] = A[x][y], so linear index k maps to (x=k%5, y=k/5)
        KeccakF1600StateMemValues state_input_values;
        for (size_t k = 0; k < AVM_KECCAKF1600_STATE_SIZE; k++) {
            state_input_values[k % 5][k / 5] = src_mem_values[k];
        }
 
        std::array<KeccakF1600RoundData, AVM_KECCAKF1600_NUM_ROUNDS> rounds_data;
 
        for (uint8_t round_idx = 0; round_idx < AVM_KECCAKF1600_NUM_ROUNDS; round_idx++) {
            std::array<std::array<MemoryValue, 4>, 5> theta_xor_values;
 
            // Theta xor computations. Each sheet's 4 steps form a dependency chain, so we walk
            // step-major and SIMD-64 pair the same step across sheets ((0,1) and (2,3)); sheet 4 is
            // scalar. (Must match keccakf1600.pil.)
            // The running accumulator for sheet i at a given step is the previous step's xor result,
            // or the sheet's first lane for step 0.
            const auto theta_acc = [&](size_t i, size_t step) -> const MemoryValue& {
                return step == 0 ? state_input_values[i][0] : theta_xor_values[i][step - 1];
            };
            for (size_t step = 0; step < 4; ++step) {
                for (size_t s = 0; s + 1 < 4; s += 2) { // sheet pairs (0,1) and (2,3)
                    auto [c0, c1] = bitwise.simd_xor_op_64(theta_acc(s, step),
                                                           state_input_values[s][step + 1],
                                                           theta_acc(s + 1, step),
                                                           state_input_values[s + 1][step + 1]);
                    theta_xor_values[s][step] = c0;
                    theta_xor_values[s + 1][step] = c1;
                }
                theta_xor_values[4][step] = bitwise.xor_op(theta_acc(4, step), state_input_values[4][step + 1]);
            }
 
            // Theta xor values left rotated by 1
            std::array<MemoryValue, 5> theta_xor_row_rotl1_values;
            for (size_t i = 0; i < 5; ++i) {
                theta_xor_row_rotl1_values[i] = unconstrained_rotate_left(theta_xor_values[i][3], 1);
            }
 
            // Theta combined xor computation. For sheet j the inputs are theta_xor[(j+4)%5][3] and
            // rotl1(theta_xor_row[(j+1)%5]). SIMD-64 pairs sheets (0,1),(2,3); sheet 4 is scalar
            // (must match keccakf1600.pil).
            std::array<MemoryValue, 5> theta_combined_xor_values;
            for (size_t i = 0; i + 1 < 5; i += 2) {
                auto [c0, c1] = bitwise.simd_xor_op_64(theta_xor_values[(i + 4) % 5][3],
                                                       theta_xor_row_rotl1_values[(i + 1) % 5],
                                                       theta_xor_values[i % 5][3],
                                                       theta_xor_row_rotl1_values[(i + 1 + 1) % 5]);
                theta_combined_xor_values[i] = c0;
                theta_combined_xor_values[i + 1] = c1;
            }
            theta_combined_xor_values[4] = bitwise.xor_op(theta_xor_values[3][3], theta_xor_row_rotl1_values[0]);
 
            // State theta values: state_theta[i][j] = state_in[i][j] XOR theta_combined_xor[i].
            // SIMD-64: pair lanes in flat order idx = 5*i + j (must match keccakf1600.pil); the odd
            // lane 24 (state index 44) is computed with a scalar XOR.
            std::array<std::array<MemoryValue, 5>, 5> state_theta_values;
            for (size_t idx = 0; idx + 1 < 25; idx += 2) {
                const size_t i0 = idx / 5;
                const size_t j0 = idx % 5;
                const size_t i1 = (idx + 1) / 5;
                const size_t j1 = (idx + 1) % 5;
                auto [c0, c1] = bitwise.simd_xor_op_64(state_input_values[i0][j0],
                                                       theta_combined_xor_values[i0],
                                                       state_input_values[i1][j1],
                                                       theta_combined_xor_values[i1]);
                state_theta_values[i0][j0] = c0;
                state_theta_values[i1][j1] = c1;
            }
            state_theta_values[4][4] = bitwise.xor_op(state_input_values[4][4], theta_combined_xor_values[4]);
 
            // State rho values
            KeccakF1600StateMemValues state_rho_values;
 
            // Handle range checks related to Rho round function.
            // For i,j, such that 0 < rotation_len[i][j] <= 32, we range check
            // the highest rotation_len[i][j] number of bits of state_theta_values[i][j].
            // Otherwise, we range check the lowest 64 - rotation_len[i][j] bits.
            for (size_t i = 0; i < 5; ++i) {
                for (size_t j = 0; j < 5; ++j) {
                    const uint8_t& len = keccak_rotation_len[i][j];
                    // Compute state values after Rho function.
                    state_rho_values[i][j] = unconstrained_rotate_left(state_theta_values[i][j], len);
                    if (len > 0 && len <= 32) {
                        range_check.assert_range(state_theta_values[i][j].as<uint64_t>() >> (64 - len), len);
                    } else if (len > 32) {
                        range_check.assert_range(state_theta_values[i][j].as<uint64_t>() & ((1ULL << (64 - len)) - 1),
                                                 64 - len);
                    }
                }
            }
 
            // state pi values
            // state "not pi" values
            KeccakF1600StateMemValues state_pi_values;
            KeccakF1600StateMemValues state_pi_not_values;
            for (size_t i = 0; i < 5; ++i) {
                for (size_t j = 0; j < 5; ++j) {
                    state_pi_values[i][j] = state_rho_values[keccak_pi_rho_x_coords[i][j]][i];
                    state_pi_not_values[i][j] = ~state_pi_values[i][j];
                }
            }
 
            // state "pi and" values: pi_and[i][j] = NOT(pi[(i+1)%5][j]) AND pi[(i+2)%5][j].
            // SIMD-64 pairs lanes in flat order idx = 5*i + j; lane 24 (state index 44) is scalar.
            // (Pairing must match keccakf1600.pil.) pi_and and chi are computed in separate passes so
            // each phase can be paired independently.
            KeccakF1600StateMemValues state_pi_and_values;
            for (size_t idx = 0; idx + 1 < 25; idx += 2) {
                const size_t i0 = idx / 5;
                const size_t j0 = idx % 5;
                const size_t i1 = (idx + 1) / 5;
                const size_t j1 = (idx + 1) % 5;
                auto [c0, c1] = bitwise.simd_and_op_64(state_pi_not_values[(i0 + 1) % 5][j0],
                                                       state_pi_values[(i0 + 2) % 5][j0],
                                                       state_pi_not_values[(i1 + 1) % 5][j1],
                                                       state_pi_values[(i1 + 2) % 5][j1]);
                state_pi_and_values[i0][j0] = c0;
                state_pi_and_values[i1][j1] = c1;
            }
            state_pi_and_values[4][4] =
                bitwise.and_op(state_pi_not_values[(4 + 1) % 5][4], state_pi_values[(4 + 2) % 5][4]);
 
            // state chi values: chi[i][j] = pi[i][j] XOR pi_and[i][j]. Same SIMD-64 pairing.
            KeccakF1600StateMemValues state_chi_values;
            for (size_t idx = 0; idx + 1 < 25; idx += 2) {
                const size_t i0 = idx / 5;
                const size_t j0 = idx % 5;
                const size_t i1 = (idx + 1) / 5;
                const size_t j1 = (idx + 1) % 5;
                auto [c0, c1] = bitwise.simd_xor_op_64(state_pi_values[i0][j0],
                                                       state_pi_and_values[i0][j0],
                                                       state_pi_values[i1][j1],
                                                       state_pi_and_values[i1][j1]);
                state_chi_values[i0][j0] = c0;
                state_chi_values[i1][j1] = c1;
            }
            state_chi_values[4][4] = bitwise.xor_op(state_pi_values[4][4], state_pi_and_values[4][4]);
 
            // state iota_00 value
            // Recall that round starts with 1
            MemoryValue iota_00_value =
                bitwise.xor_op(state_chi_values[0][0], MemoryValue::from(keccak_round_constants[round_idx]));
 
            rounds_data[round_idx] = {
                .state = two_dim_array_to_uint64(state_input_values),
                .theta_xor = two_dim_array_to_uint64(theta_xor_values),
                .theta_xor_row_rotl1 = array_to_uint64(theta_xor_row_rotl1_values),
                .theta_combined_xor = array_to_uint64(theta_combined_xor_values),
                .state_theta = two_dim_array_to_uint64(state_theta_values),
                .state_rho = two_dim_array_to_uint64(state_rho_values),
                .state_pi_not = two_dim_array_to_uint64(state_pi_not_values),
                .state_pi_and = two_dim_array_to_uint64(state_pi_and_values),
                .state_chi = two_dim_array_to_uint64(state_chi_values),
                .state_iota_00 = iota_00_value.as<uint64_t>(),
            };
 
            state_input_values = state_chi_values;
            state_input_values[0][0] = iota_00_value;
        }
 
        // Slice write
        for (size_t i = 0; i < 5; i++) {
            for (size_t j = 0; j < 5; j++) {
                memory.set(dst_addr + static_cast<MemoryAddress>((j * 5) + i), state_input_values[i][j]);
            }
        }
 
        keccakf1600_event.rounds = rounds_data;
        perm_events.emit(KeccakF1600Event(keccakf1600_event));
    } catch (const KeccakF1600Exception& e) {
        perm_events.emit(KeccakF1600Event(keccakf1600_event));
        throw;
    }
}
 
} // namespace bb::avm2::simulation