generic_permutation_relation.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Completed, auditors: [Federico], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#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 {
 
template <typename Settings> class PermutationPolynomialStructure {
  private:
    static constexpr size_t NUM_LOOKUP_TERMS = 1;
    static constexpr size_t NUM_TABLE_TERMS = 1;
 
    static constexpr size_t INVERSE_POLYNOMIAL_INDEX = 0;
    static constexpr size_t LOOKUP_TERM_PREDICATE_START_POLYNOMIAL_INDEX = INVERSE_POLYNOMIAL_INDEX + NUM_TABLE_TERMS;
    static constexpr size_t TABLE_TERM_PREDICATE_START_POLYNOMIAL_INDEX =
        LOOKUP_TERM_PREDICATE_START_POLYNOMIAL_INDEX + NUM_LOOKUP_TERMS;
    static constexpr size_t LOOKUP_TERM_START_POLYNOMIAL_INDEX =
        TABLE_TERM_PREDICATE_START_POLYNOMIAL_INDEX + NUM_TABLE_TERMS;
    static constexpr size_t TABLE_TERM_START_POLYNOMIAL_INDEX =
        LOOKUP_TERM_START_POLYNOMIAL_INDEX + Settings::COLUMNS_PER_SET;
 
  public:
    static constexpr size_t get_inverse_polynomial_index() { return INVERSE_POLYNOMIAL_INDEX; }
 
    static constexpr size_t get_lookup_term_predicate_index() { return LOOKUP_TERM_PREDICATE_START_POLYNOMIAL_INDEX; }
    static constexpr size_t get_table_term_predicate_index() { return TABLE_TERM_PREDICATE_START_POLYNOMIAL_INDEX; }
 
    static constexpr size_t compute_lookup_term_polynomial_offset() { return LOOKUP_TERM_START_POLYNOMIAL_INDEX; }
 
    static constexpr size_t compute_table_term_polynomial_offset() { return TABLE_TERM_START_POLYNOMIAL_INDEX; }
};
 
template <typename Settings, typename FF_> class GenericPermutationRelationImpl {
  public:
    using FF = FF_;
    using PolynomialStructure = PermutationPolynomialStructure<Settings>;
 
    // The term 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 NUM_LOOKUP_TERMS = 1;
    static constexpr size_t NUM_TABLE_TERMS = 1;
 
    // Specialization of the calculation of the length for the generic lookup relation to the permutation relation; note
    // that the second subrelation degree is one lower than the one in the lookup argument because there is not read
    // count polynomial
    static constexpr size_t FIRST_RELATION_PARTIAL_LENGTH = std::max(NUM_LOOKUP_TERMS + NUM_TABLE_TERMS + 1,
                                                                     Settings::INVERSE_EXISTS_POLYNOMIAL_DEGREE) +
                                                            1; // inverse polynomial correctness sub-relation
    static constexpr size_t SECOND_RELATION_PARTIAL_LENGTH =
        NUM_LOOKUP_TERMS + NUM_TABLE_TERMS + 2; // log-derived terms sub-relation
    static constexpr size_t LENGTH = std::max(FIRST_RELATION_PARTIAL_LENGTH, SECOND_RELATION_PARTIAL_LENGTH);
 
    // We use the max of the subrelation lengths because the inverses of lookup/table terms must be used in both
    // subrelations
    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)
    {
        return std::get<PolynomialStructure::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;
 
        Accumulator const& first_set_enabled = Accumulator(
            View(std::get<PolynomialStructure::get_lookup_term_predicate_index()>(Settings::get_const_entities(in))));
 
        Accumulator const& second_set_enabled = Accumulator(
            View(std::get<PolynomialStructure::get_table_term_predicate_index()>(Settings::get_const_entities(in))));
 
        // The following expression (assuming the values are boolean) is the algebraic representation of a logical OR
        return (first_set_enabled + second_set_enabled - (first_set_enabled * second_set_enabled));
    }
 
    template <typename Accumulator, size_t lookup_index, typename AllEntities>
    static Accumulator get_lookup_term_predicate(const AllEntities& in)
 
    {
        static_assert(lookup_index < NUM_LOOKUP_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<PolynomialStructure::get_lookup_term_predicate_index()>(Settings::get_const_entities(in))));
    }
 
    template <typename Accumulator, size_t table_index, typename AllEntities>
    static Accumulator get_table_term_predicate(const AllEntities& in)
    {
        static_assert(table_index < NUM_TABLE_TERMS);
        using View = typename Accumulator::View;
 
        return Accumulator(
            View(std::get<PolynomialStructure::get_table_term_predicate_index()>(Settings::get_const_entities(in))));
    }
 
    template <typename Accumulator, size_t lookup_index, typename AllEntities, typename Parameters>
    static Accumulator compute_lookup_term(const AllEntities& in, const Parameters& params)
    {
        using View = typename Accumulator::View;
 
        static_assert(lookup_index < NUM_LOOKUP_TERMS);
        constexpr size_t start_polynomial_index = PolynomialStructure::compute_lookup_term_polynomial_offset();
        const FF beta = params.beta;
        const FF gamma = params.gamma;
 
        auto result = Accumulator(0);
 
        // Retrieve all polynomials used
        const auto all_polynomials = Settings::get_const_entities(in);
 
        // Iterate over tuple and sum as a polynomial over beta
        bb::constexpr_for<start_polynomial_index, start_polynomial_index + Settings::COLUMNS_PER_SET, 1>(
            [&]<size_t i>() { result = result * beta + View(std::get<i>(all_polynomials)); });
 
        return result + gamma;
    }
 
    template <typename Accumulator, size_t table_index, typename AllEntities, typename Parameters>
    static Accumulator compute_table_term(const AllEntities& in, const Parameters& params)
    {
        using View = typename Accumulator::View;
 
        static_assert(table_index < NUM_TABLE_TERMS);
        constexpr size_t start_polynomial_index = PolynomialStructure::compute_table_term_polynomial_offset();
        const FF beta = params.beta;
        const FF gamma = params.gamma;
 
        auto result = Accumulator(0);
 
        // Retrieve all polynomials used
        const auto all_polynomials = Settings::get_const_entities(in);
 
        // Iterate over tuple and sum as a polynomial over beta
        bb::constexpr_for<start_polynomial_index, start_polynomial_index + Settings::COLUMNS_PER_SET, 1>(
            [&]<size_t i>() { result = result * beta + View(std::get<i>(all_polynomials)); });
 
        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_subrelation_contributions<FF,
                                                            GenericPermutationRelationImpl<Settings, FF>,
                                                            ContainerOverSubrelations,
                                                            AllEntities,
                                                            Parameters,
                                                            true>(accumulator, in, params, scaling_factor);
    }
};
 
template <typename Settings, typename FF>
using GenericPermutationRelation = Relation<GenericPermutationRelationImpl<Settings, FF>>;
 
} // namespace bb