poseidon2_permutation.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Sergei], commit: dd03c4a23ab067274b4964cacb36d1545f73fb14}
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
 
#include "poseidon2_params.hpp"
 
#include <array>
#include <cstddef>
#include <cstdint>
 
namespace bb::crypto {
 
template <typename Params> class Poseidon2Permutation {
  public:
    // t = sponge permutation size (in field elements)
    // t = rate + capacity
    // capacity = 1 field element (256 bits)
    // rate = number of field elements that can be compressed per permutation
    static constexpr size_t t = Params::t;
    // number of full sbox rounds
    static constexpr size_t rounds_f = Params::rounds_f;
    // number of partial sbox rounds
    static constexpr size_t rounds_p = Params::rounds_p;
    static constexpr size_t NUM_ROUNDS = Params::rounds_f + Params::rounds_p;
 
    using FF = typename Params::FF;
    using State = std::array<FF, t>;
    using RoundConstants = std::array<FF, t>;
    using MatrixDiagonal = std::array<FF, t>;
    using RoundConstantsContainer = std::array<RoundConstants, NUM_ROUNDS>;
 
    static constexpr MatrixDiagonal internal_matrix_diagonal_minus_one = Params::internal_matrix_diagonal_minus_one;
    static constexpr RoundConstantsContainer round_constants = Params::round_constants;
 
    static constexpr void matrix_multiplication_4x4(State& input)
    {
        auto t0 = input[0] + input[1]; // A + B
        auto t1 = input[2] + input[3]; // C + D
        auto t2 = input[1] + input[1]; // 2B
        t2 += t1;                      // 2B + C + D
        auto t3 = input[3] + input[3]; // 2D
        t3 += t0;                      // 2D + A + B
        auto t4 = t1 + t1;
        t4 += t4;
        t4 += t3; // A + B + 4C + 6D
        auto t5 = t0 + t0;
        t5 += t5;
        t5 += t2;          // 4A + 6B + C + D
        auto t6 = t3 + t5; // 5A + 7B + C + 3D
        auto t7 = t2 + t4; // A + 3B + 5C + 7D
        input[0] = t6;
        input[1] = t5;
        input[2] = t7;
        input[3] = t4;
    }
 
    static constexpr void add_round_constants(State& input, const RoundConstants& rc)
    {
        for (size_t i = 0; i < t; ++i) {
            input[i] += rc[i];
        }
    }
 
    static constexpr void matrix_multiplication_internal(State& input)
    {
        // for t = 4
        // Computes: result[i] = (D_i - 1) * input[i] + sum = D_i * input[i] + (sum of other elements)
        // where D_i are the actual diagonal values and internal_matrix_diagonal_minus_one[i] = D_i - 1
        auto sum = input[0];
        for (size_t i = 1; i < t; ++i) {
            sum += input[i];
        }
        for (size_t i = 0; i < t; ++i) {
            input[i] *= internal_matrix_diagonal_minus_one[i];
            input[i] += sum;
        }
    }
 
    static constexpr void matrix_multiplication_external(State& input)
    {
        static_assert(t == 4, "Only t=4 is supported");
        matrix_multiplication_4x4(input);
    }
 
    static constexpr void apply_single_sbox(FF& input)
    {
        auto x2 = input.sqr();
        x2.self_sqr(); // x2 -> x4
        input *= x2;
    }
 
    static constexpr void apply_sbox(State& input)
    {
        for (auto& in : input) {
            apply_single_sbox(in);
        }
    }
 
    static constexpr void permutation_inplace(State& state)
    {
        // Apply 1st linear layer
        matrix_multiplication_external(state);
 
        // First set of external rounds
        constexpr size_t rounds_f_beginning = rounds_f / 2;
        for (size_t i = 0; i < rounds_f_beginning; ++i) {
            add_round_constants(state, round_constants[i]);
            apply_sbox(state);
            matrix_multiplication_external(state);
        }
 
        // Internal rounds
        constexpr size_t p_end = rounds_f_beginning + rounds_p;
        for (size_t i = rounds_f_beginning; i < p_end; ++i) {
            state[0] += round_constants[i][0];
            apply_single_sbox(state[0]);
            matrix_multiplication_internal(state);
        }
 
        // Remaining external rounds
        for (size_t i = p_end; i < NUM_ROUNDS; ++i) {
            add_round_constants(state, round_constants[i]);
            apply_sbox(state);
            matrix_multiplication_external(state);
        }
    }
 
    static constexpr State permutation(const State& input)
    {
        State result(input);
        permutation_inplace(result);
        return result;
    }
};
} // namespace bb::crypto