permutation_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 UltraPermutationRelationImpl {
  public:
    using FF = FF_;
 
    static constexpr std::array<size_t, 3> SUBRELATION_PARTIAL_LENGTHS{
        6, // grand product construction sub-relation
        3, // left-shiftable polynomial sub-relation
        3  // z_perm initialization sub-relation
    };
 
    template <typename AllEntities> inline static bool skip(const AllEntities& in)
    {
        // If z_perm == z_perm_shift, this implies that none of the wire values for the present input are involved in
        // non-trivial copy constraints.
        return (in[AllEntities::EntityId::z_perm] - in[AllEntities::EntityId::z_perm_shift]).is_zero();
    }
 
    template <typename AllEntities> inline static auto& get_grand_product_polynomial(AllEntities& in)
    {
        return in[AllEntities::EntityId::z_perm];
    }
    template <typename AllEntities> inline static auto& get_shifted_grand_product_polynomial(AllEntities& in)
    {
        return in[AllEntities::EntityId::z_perm_shift];
    }
 
    template <typename Accumulator, typename AllEntities, typename Parameters>
    inline static Accumulator compute_grand_product_numerator(const AllEntities& in, const Parameters& params)
    {
        using View = typename Accumulator::View;
        using ParameterView = Parameters::DataType;
 
        auto w_1 = View(in[AllEntities::EntityId::w_l]);
        auto w_2 = View(in[AllEntities::EntityId::w_r]);
        auto w_3 = View(in[AllEntities::EntityId::w_o]);
        auto w_4 = View(in[AllEntities::EntityId::w_4]);
        auto id_1 = View(in[AllEntities::EntityId::id_1]);
        auto id_2 = View(in[AllEntities::EntityId::id_2]);
        auto id_3 = View(in[AllEntities::EntityId::id_3]);
        auto id_4 = View(in[AllEntities::EntityId::id_4]);
 
        const auto& beta = ParameterView(params.beta);
        const auto& gamma = ParameterView(params.gamma);
 
        // witness degree 4
        return (w_1 + id_1 * beta + gamma) * (w_2 + id_2 * beta + gamma) * (w_3 + id_3 * beta + gamma) *
               (w_4 + id_4 * beta + gamma);
    }
 
    template <typename Accumulator, typename AllEntities, typename Parameters>
    inline static Accumulator compute_grand_product_denominator(const AllEntities& in, const Parameters& params)
    {
        using View = typename Accumulator::View;
        using ParameterView = Parameters::DataType;
 
        auto w_1 = View(in[AllEntities::EntityId::w_l]);
        auto w_2 = View(in[AllEntities::EntityId::w_r]);
        auto w_3 = View(in[AllEntities::EntityId::w_o]);
        auto w_4 = View(in[AllEntities::EntityId::w_4]);
 
        auto sigma_1 = View(in[AllEntities::EntityId::sigma_1]);
        auto sigma_2 = View(in[AllEntities::EntityId::sigma_2]);
        auto sigma_3 = View(in[AllEntities::EntityId::sigma_3]);
        auto sigma_4 = View(in[AllEntities::EntityId::sigma_4]);
 
        const auto& beta = ParameterView(params.beta);
        const auto& gamma = ParameterView(params.gamma);
 
        // witness degree 4
        return (w_1 + sigma_1 * beta + gamma) * (w_2 + sigma_2 * beta + gamma) * (w_3 + sigma_3 * beta + gamma) *
               (w_4 + sigma_4 * beta + gamma);
    }
 
    template <typename Accumulator, typename GateCoefficientAccumulator>
    static bool subrelation_is_active(const GateCoefficientAccumulator& gate)
    {
        if constexpr (IsProverAccumulator<Accumulator>) {
            return !gate.is_zero();
        } else {
            return true;
        }
    }
 
    template <typename ContainerOverSubrelations, typename AllEntities, typename Parameters>
    inline static void accumulate(ContainerOverSubrelations& accumulators,
                                  const AllEntities& in,
                                  const Parameters& params,
                                  const FF& scaling_factor)
    {
        // Contribution (1)
        using Accumulator = std::tuple_element_t<0, ContainerOverSubrelations>;
        using CoefficientAccumulator = typename Accumulator::CoefficientAccumulator;
        using ParameterView = Parameters::DataType;
        using ParameterCoefficientAccumulator = typename ParameterView::CoefficientAccumulator;
 
        const CoefficientAccumulator w_1_m(in[AllEntities::EntityId::w_l]);
        const CoefficientAccumulator w_2_m(in[AllEntities::EntityId::w_r]);
        const CoefficientAccumulator w_3_m(in[AllEntities::EntityId::w_o]);
        const CoefficientAccumulator w_4_m(in[AllEntities::EntityId::w_4]);
        const CoefficientAccumulator id_1_m(in[AllEntities::EntityId::id_1]);
        const CoefficientAccumulator id_2_m(in[AllEntities::EntityId::id_2]);
        const CoefficientAccumulator id_3_m(in[AllEntities::EntityId::id_3]);
        const CoefficientAccumulator id_4_m(in[AllEntities::EntityId::id_4]);
        const CoefficientAccumulator sigma_1_m(in[AllEntities::EntityId::sigma_1]);
        const CoefficientAccumulator sigma_2_m(in[AllEntities::EntityId::sigma_2]);
        const CoefficientAccumulator sigma_3_m(in[AllEntities::EntityId::sigma_3]);
        const CoefficientAccumulator sigma_4_m(in[AllEntities::EntityId::sigma_4]);
 
        const ParameterCoefficientAccumulator gamma_m(params.gamma);
        const ParameterCoefficientAccumulator beta_m(params.beta);
 
        const auto w_1_plus_gamma = w_1_m + gamma_m;
        const auto w_2_plus_gamma = w_2_m + gamma_m;
        const auto w_3_plus_gamma = w_3_m + gamma_m;
        const auto w_4_plus_gamma = w_4_m + gamma_m;
 
        auto t1 = (id_1_m * beta_m);
        t1 += w_1_plus_gamma;
        t1 *= scaling_factor;
        auto t2 = id_2_m * beta_m;
        t2 += w_2_plus_gamma;
        auto t3 = id_3_m * beta_m;
        t3 += w_3_plus_gamma;
        auto t4 = id_4_m * beta_m;
        t4 += w_4_plus_gamma;
 
        auto t5 = sigma_1_m * beta_m;
        t5 += w_1_plus_gamma;
        t5 *= scaling_factor;
        auto t6 = sigma_2_m * beta_m;
        t6 += w_2_plus_gamma;
        auto t7 = sigma_3_m * beta_m;
        t7 += w_3_plus_gamma;
        auto t8 = sigma_4_m * beta_m;
        t8 += w_4_plus_gamma;
 
        // t1..t8 are degree-1 coefficient-basis monomials. The prover pairs them as (t1*t2)(t3*t4): Karatsuba
        // on the degree-1 pairs reduces the naive 36 muls (chaining 6 pointwise length-6 products) to 24.
        Accumulator numerator;
        Accumulator denominator;
        if constexpr (IsProverAccumulator<Accumulator>) {
            numerator = Accumulator(t1 * t2);
            numerator *= Accumulator(t3 * t4);
            denominator = Accumulator(t5 * t6);
            denominator *= Accumulator(t7 * t8);
        } else {
            numerator = Accumulator(t1);
            numerator *= Accumulator(t2);
            numerator *= Accumulator(t3);
            numerator *= Accumulator(t4);
 
            denominator = Accumulator(t5);
            denominator *= Accumulator(t6);
            denominator *= Accumulator(t7);
            denominator *= Accumulator(t8);
        }
 
        const ParameterCoefficientAccumulator public_input_delta_m(params.public_input_delta);
        const auto z_perm_m = CoefficientAccumulator(in[AllEntities::EntityId::z_perm]);
        const auto z_perm_shift_m = CoefficientAccumulator(in[AllEntities::EntityId::z_perm_shift]);
        const auto lagrange_first_m = CoefficientAccumulator(in[AllEntities::EntityId::lagrange_first]);
        const auto lagrange_last_m = CoefficientAccumulator(in[AllEntities::EntityId::lagrange_last]);
 
        // Prover fast path (guarded on ::LENGTH so it never enters the verifiers, which must not branch on witness
        // values). lagrange_first/last are one-hot and vanish on almost every edge pair under folding; when both are
        // zero the public-input term collapses to z_perm_shift and the (z_perm + L_first) factor to z_perm, and
        // subrelations (2),(3) vanish -- the same accumulator value as the general path below, skipping ~12 muls.
        if constexpr (IsProverAccumulator<Accumulator>) {
            if (lagrange_first_m.is_zero() && lagrange_last_m.is_zero()) {
                const Accumulator public_input_term(z_perm_shift_m);
                std::get<0>(accumulators) += ((Accumulator(z_perm_m) * numerator) - (public_input_term * denominator));
                return;
            }
        }
 
        auto public_input_term_m = lagrange_last_m * public_input_delta_m;
        public_input_term_m += z_perm_shift_m;
        const Accumulator public_input_term(public_input_term_m);
        // witness degree: deg 5 - deg 5 = deg 5
        std::get<0>(accumulators) +=
            ((Accumulator(z_perm_m + lagrange_first_m) * numerator) - (public_input_term * denominator));
 
        // Contribution (2): gated by lagrange_last (zero on all but the last row).
        using ShortAccumulator = std::tuple_element_t<1, ContainerOverSubrelations>;
        if (subrelation_is_active<Accumulator>(lagrange_last_m)) {
            std::get<1>(accumulators) += ShortAccumulator((lagrange_last_m * z_perm_shift_m) * scaling_factor);
        }
 
        // Contribution (3): Enforce z_perm starts at 0. The grand product initialization relies on
        // z_perm[0] = 0 so that (z_perm + L_first) evaluates to 1 at the first row.
        // Without this constraint, a cheating prover could set z_perm[0] to a non-zero value.
        // Gated by lagrange_first (zero on all but the first row).
        using InitAccumulator = std::tuple_element_t<2, ContainerOverSubrelations>;
        if (subrelation_is_active<Accumulator>(lagrange_first_m)) {
            std::get<2>(accumulators) += InitAccumulator((lagrange_first_m * z_perm_m) * scaling_factor);
        }
    };
};
 
template <typename FF> using UltraPermutationRelation = Relation<UltraPermutationRelationImpl<FF>>;
 
} // namespace bb