generic_permutation_relation.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 <array>
#include <tuple>
 
#include "barretenberg/common/constexpr_utils.hpp"
#include "barretenberg/honk/proof_system/logderivative_library.hpp"
#include "barretenberg/polynomials/univariate.hpp"
#include "barretenberg/relations/relation_types.hpp"
 
namespace bb {
enum GenericPermutationSettingIndices {
    INVERSE_POLYNOMIAL_INDEX,                       /* The index of the inverse polynomial*/
    FIRST_PERMUTATION_SET_ENABLE_POLYNOMIAL_INDEX,  /* The index of the polynomial that adds an element from the first
                                                       set to the sum*/
    SECOND_PERMUTATION_SET_ENABLE_POLYNOMIAL_INDEX, /* The index of the polynomial that adds an element from the second
                                                       set to the sum*/
 
    PERMUTATION_SETS_START_POLYNOMIAL_INDEX, /* The starting index of the polynomials that are used in the permutation
                                                sets*/
};
 
template <typename Settings, typename FF_> class GenericPermutationRelationImpl {
  public:
    using FF = FF_;
    // Read and write terms counts should stay set to 1 unless we want to permute several columns at once as accumulated
    // sets (not as tuples).
    static constexpr size_t READ_TERMS = 1;
    static constexpr size_t WRITE_TERMS = 1;
    // 1 + polynomial degree of this relation
    static constexpr size_t LENGTH = READ_TERMS + WRITE_TERMS + 3; // 5
 
    static constexpr std::array<size_t, 2> SUBRELATION_PARTIAL_LENGTHS{
        LENGTH, // inverse polynomial correctness sub-relation
        LENGTH  // log-derived terms subrelation
    };
 
    static constexpr std::array<bool, 2> SUBRELATION_LINEARLY_INDEPENDENT = { true, false };
 
    template <typename AllValues> static bool operation_exists_at_row(const AllValues& row)
 
    {
        return Settings::inverse_polynomial_is_computed_at_row(row);
    }
 
    template <typename AllEntities> static auto& get_inverse_polynomial(AllEntities& in)
    {
        // WIRE containing the inverse of the product of terms at this row. Used to reconstruct individual inversed
        // terms
        return std::get<INVERSE_POLYNOMIAL_INDEX>(Settings::get_nonconst_entities(in));
    }
 
    template <typename Accumulator, typename AllEntities>
    static Accumulator compute_inverse_exists(const AllEntities& in)
    {
        using View = typename Accumulator::View;
 
        // WIRE/SELECTOR enabling the permutation used in the sumcheck computation. This affects the first
        // subrelation
        Accumulator const& first_set_enabled = Accumulator(
            View(std::get<FIRST_PERMUTATION_SET_ENABLE_POLYNOMIAL_INDEX>(Settings::get_const_entities(in))));
 
        Accumulator const& second_set_enabled = Accumulator(
            View(std::get<SECOND_PERMUTATION_SET_ENABLE_POLYNOMIAL_INDEX>(Settings::get_const_entities(in))));
 
        // This has the truth table of a logical OR
        return (first_set_enabled + second_set_enabled - (first_set_enabled * second_set_enabled));
    }
 
    template <typename Accumulator, size_t read_index, typename AllEntities>
    static Accumulator compute_read_term_predicate(const AllEntities& in)
 
    {
        static_assert(read_index < READ_TERMS);
        using View = typename Accumulator::View;
 
        // The selector/wire value that determines that an element from the first set needs to be included. Can be
        // different from the wire used in the write part.
        return Accumulator(
            View(std::get<FIRST_PERMUTATION_SET_ENABLE_POLYNOMIAL_INDEX>(Settings::get_const_entities(in))));
    }
 
    template <typename Accumulator, size_t write_index, typename AllEntities>
    static Accumulator compute_write_term_predicate(const AllEntities& in)
    {
        static_assert(write_index < WRITE_TERMS);
        using View = typename Accumulator::View;
 
        // The selector/wire value that determines that an element from the second set needs to be included. Can be
        // different from the wire used in the read part.
        return Accumulator(
            View(std::get<SECOND_PERMUTATION_SET_ENABLE_POLYNOMIAL_INDEX>(Settings::get_const_entities(in))));
    }
 
    template <typename Accumulator, size_t read_index, typename AllEntities, typename Parameters>
    static Accumulator compute_read_term(const AllEntities& in, const Parameters& params)
    {
        using View = typename Accumulator::View;
 
        static_assert(read_index < READ_TERMS);
 
        // Retrieve all polynomials used
        const auto all_polynomials = Settings::get_const_entities(in);
 
        auto result = Accumulator(0);
 
        // Iterate over tuple and sum as a polynomial over beta
        bb::constexpr_for<PERMUTATION_SETS_START_POLYNOMIAL_INDEX,
                          PERMUTATION_SETS_START_POLYNOMIAL_INDEX + Settings::COLUMNS_PER_SET,
                          1>([&]<size_t i>() { result = result * params.beta + View(std::get<i>(all_polynomials)); });
 
        const auto& gamma = params.gamma;
        return result + gamma;
    }
 
    template <typename Accumulator, size_t write_index, typename AllEntities, typename Parameters>
    static Accumulator compute_write_term(const AllEntities& in, const Parameters& params)
    {
        using View = typename Accumulator::View;
 
        static_assert(write_index < WRITE_TERMS);
 
        // Get all used entities
        const auto& used_entities = Settings::get_const_entities(in);
 
        auto result = Accumulator(0);
        // Iterate over tuple and sum as a polynomial over beta
        bb::constexpr_for<PERMUTATION_SETS_START_POLYNOMIAL_INDEX + Settings::COLUMNS_PER_SET,
                          PERMUTATION_SETS_START_POLYNOMIAL_INDEX + 2 * Settings::COLUMNS_PER_SET,
                          1>([&]<size_t i>() { result = result * params.beta + View(std::get<i>(used_entities)); });
 
        const auto& gamma = params.gamma;
        return result + gamma;
    }
 
    template <typename ContainerOverSubrelations, typename AllEntities, typename Parameters>
    static void accumulate(ContainerOverSubrelations& accumulator,
                           const AllEntities& in,
                           const Parameters& params,
                           const FF& scaling_factor)
    {
        accumulate_logderivative_permutation_subrelation_contributions<FF,
                                                                       GenericPermutationRelationImpl<Settings, FF>>(
            accumulator, in, params, scaling_factor);
    }
};
 
template <typename Settings, typename FF>
using GenericPermutationRelation = Relation<GenericPermutationRelationImpl<Settings, FF>>;
 
template <typename Settings, typename FF> using GenericPermutation = GenericPermutationRelationImpl<Settings, FF>;
 
} // namespace bb