poseidon2_external_relation.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Luke, Raju], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#pragma once
#include "barretenberg/relations/relation_types.hpp"
namespace bb {
 
template <typename FF_> class Poseidon2ExternalRelationImpl {
  public:
    using FF = FF_;
 
    static constexpr std::array<size_t, 4> SUBRELATION_PARTIAL_LENGTHS{
        7, // external poseidon2 round sub-relation for first value
        7, // external poseidon2 round sub-relation for second value
        7, // external poseidon2 round sub-relation for third value
        7, // external poseidon2 round sub-relation for fourth value
    };
 
    template <typename AllEntities> inline static bool skip(const AllEntities& in)
    {
        return in[AllEntities::EntityId::q_poseidon2_external].is_zero();
    }
 
    template <typename ContainerOverSubrelations, typename AllEntities, typename Parameters>
    void static accumulate(ContainerOverSubrelations& evals,
                           const AllEntities& in,
                           const Parameters&,
                           const FF& scaling_factor)
    {
        // Univariates of degree 6 represented in Lagrange basis
        using Accumulator = std::tuple_element_t<0, ContainerOverSubrelations>;
        // Low-degree univariates represented in monomial basis
        using CoefficientAccumulator = typename Accumulator::CoefficientAccumulator;
 
        // Current state
        const auto w_1 = CoefficientAccumulator(in[AllEntities::EntityId::w_l]);
        const auto w_2 = CoefficientAccumulator(in[AllEntities::EntityId::w_r]);
        const auto w_3 = CoefficientAccumulator(in[AllEntities::EntityId::w_o]);
        const auto w_4 = CoefficientAccumulator(in[AllEntities::EntityId::w_4]);
        // Expected state, contained in the next row
        const auto w_1_shift = CoefficientAccumulator(in[AllEntities::EntityId::w_l_shift]);
        const auto w_2_shift = CoefficientAccumulator(in[AllEntities::EntityId::w_r_shift]);
        const auto w_3_shift = CoefficientAccumulator(in[AllEntities::EntityId::w_o_shift]);
        const auto w_4_shift = CoefficientAccumulator(in[AllEntities::EntityId::w_4_shift]);
        // i-th external round constants
        const auto c_1 = CoefficientAccumulator(in[AllEntities::EntityId::q_l]);
        const auto c_2 = CoefficientAccumulator(in[AllEntities::EntityId::q_r]);
        const auto c_3 = CoefficientAccumulator(in[AllEntities::EntityId::q_o]);
        const auto c_4 = CoefficientAccumulator(in[AllEntities::EntityId::q_4]);
        // Poseidon2 external relation selector
        const auto q_poseidon2_external = CoefficientAccumulator(in[AllEntities::EntityId::q_poseidon2_external]);
 
        // add round constants which are loaded in selectors
 
        // Square the degree-1 sbox input in the coefficient basis before promoting -- see
        // UnivariateCoefficientBasis::sqr.
        auto sbox = [](const auto& x_m) {
            const Accumulator x(x_m);
            const Accumulator t2(x_m.sqr()); // x^2
            return t2.sqr() * x;             // x^4 * x = x^5
        };
        // apply s-box round
        auto u1 = sbox(w_1 + c_1);
        auto u2 = sbox(w_2 + c_2);
        auto u3 = sbox(w_3 + c_3);
        auto u4 = sbox(w_4 + c_4);
        // Matrix mul v = M_E * u with 14 additions.
        // Precompute common summands.
        auto t0 = u1 + u2; // u_1 + u_2
        auto t1 = u3 + u4; // u_3 + u_4
        auto t2 = u2 + u2; // 2u_2
        t2 += t1;          // 2u_2 + u_3 + u_4
        auto t3 = u4 + u4; // 2u_4
        t3 += t0;          // u_1 + u_2 + 2u_4
 
        // Row 4: u_1 + u_2 + 4u_3 + 6u_4
        auto v4 = t1 + t1;
        v4 += v4;
        v4 += t3;
 
        // Row 2: 4u_1 + 6u_2 + u_3 + u_4
        auto v2 = t0 + t0;
        v2 += v2;
        v2 += t2;
        // Row 1: 5u_1 + 7u_2 + u_3 + 3u_4
        auto v1 = t3 + v2;
 
        // Row 3: u_1 + 3u_2 + 5u_3 + 7u_4
        auto v3 = t2 + v4;
 
        auto q_pos_by_scaling = Accumulator(q_poseidon2_external * scaling_factor);
        std::get<0>(evals) += q_pos_by_scaling * (v1 - Accumulator(w_1_shift));
 
        std::get<1>(evals) += q_pos_by_scaling * (v2 - Accumulator(w_2_shift));
 
        std::get<2>(evals) += q_pos_by_scaling * (v3 - Accumulator(w_3_shift));
 
        std::get<3>(evals) += q_pos_by_scaling * (v4 - Accumulator(w_4_shift));
    };
};
 
template <typename FF> using Poseidon2ExternalRelation = Relation<Poseidon2ExternalRelationImpl<FF>>;
} // namespace bb