generic_lookup_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 {
 
enum LOOKUP_TYPE : uint8_t { BASIC_LOOKUP, CUSTOMIZED_LOOKUP };
enum TABLE_TYPE : uint8_t { BASIC_TABLE, CUSTOMIZED_TABLE };
 
template <typename Settings_> class LookupPolynomialStructure {
  private:
    static constexpr size_t NUM_LOOKUP_TERMS = Settings_::NUM_LOOKUP_TERMS;
    static constexpr size_t NUM_TABLE_TERMS = Settings_::NUM_TABLE_TERMS;
 
    static constexpr size_t INVERSE_POLYNOMIAL_INDEX = 0;
    static constexpr size_t LOOKUP_READ_COUNT_START_POLYNOMIAL_INDEX = 1;
    static constexpr size_t LOOKUP_TERM_PREDICATE_START_POLYNOMIAL_INDEX =
        LOOKUP_READ_COUNT_START_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;
 
  public:
    static constexpr size_t get_inverse_polynomial_index() { return INVERSE_POLYNOMIAL_INDEX; }
 
    static constexpr size_t get_read_count_polynomial_index(const size_t index)
    {
        return LOOKUP_READ_COUNT_START_POLYNOMIAL_INDEX + index;
    }
 
    static constexpr size_t get_lookup_term_predicate_index(const size_t lookup_index)
    {
        return LOOKUP_TERM_PREDICATE_START_POLYNOMIAL_INDEX + lookup_index;
    }
 
    static constexpr size_t get_table_term_predicate_index(const size_t table_index)
    {
        return TABLE_TERM_PREDICATE_START_POLYNOMIAL_INDEX + table_index;
    }
 
    static constexpr size_t compute_lookup_term_polynomial_offset(size_t lookup_index)
    {
        // If it's the starting index, then there is nothing to compute, just get the starting index
        if (lookup_index == 0) {
            return LOOKUP_TERM_START_POLYNOMIAL_INDEX;
        }
 
        switch (Settings_::LOOKUP_TYPES[lookup_index - 1]) {
        case BASIC_LOOKUP:
            // If the previous lookup was a basic lookup, add lookup tuple size (it was using just a linear combination
            // of polynomials)
            return compute_lookup_term_polynomial_offset(lookup_index - 1) + Settings_::LOOKUP_TUPLE_SIZE;
        case CUSTOMIZED_LOOKUP:
            // In case of customized lookup, no polynomials from the tuple are being used
            return compute_lookup_term_polynomial_offset(lookup_index - 1);
        default:
            bb::assert_failure("Invalid lookup type");
            return SIZE_MAX;
        }
    }
 
    static constexpr size_t compute_table_term_polynomial_offset(size_t table_index)
    {
        // If it's the starting index, then we need to find out how many polynomials were taken by lookup terms
        if (table_index == 0) {
            return compute_lookup_term_polynomial_offset(NUM_LOOKUP_TERMS);
        }
 
        switch (Settings_::TABLE_TYPES[table_index - 1]) {
        case BASIC_TABLE:
            // If the previous lookup was a basic table, add lookup tuple size (it was using just a linear combination
            // of polynomials)
            return compute_table_term_polynomial_offset(table_index - 1) + Settings_::LOOKUP_TUPLE_SIZE;
        case CUSTOMIZED_TABLE:
            // In case of customized table, no polynomials from the tuple are being used
            return compute_table_term_polynomial_offset(table_index - 1);
        default:
            bb::assert_failure("Invalid lookup type");
            return SIZE_MAX;
        }
    }
};
 
// clang-format off
template <typename S>
concept GenericLookupSettings = requires {
    // We allow looking up multiple items per row from a variable number of table columns. These values are not
    // bound to the real number of columns the lookup operates on. We allow looking up virtual columns (i.e.,
    // combinations of columns) from virtual table columns (i.e., combinations of table columns).
    requires std::is_same_v<decltype(S::NUM_LOOKUP_TERMS), const size_t>;
    requires std::is_same_v<decltype(S::NUM_TABLE_TERMS), const size_t>;
 
    // An array defining the types of the lookups performed. They can be BASIC_LOOKUP or CUSTOMIZED_LOOKUP
    requires std::is_same_v<decltype(S::LOOKUP_TYPES), const std::array<uint8_t, S::NUM_LOOKUP_TERMS>>;
    // An array defining the types of the tables used. They can be BASIC_TABLE or CUSTOMIZED_TABLE
    requires std::is_same_v<decltype(S::TABLE_TYPES), const std::array<uint8_t, S::NUM_TABLE_TERMS>>;
    // An array specifying the degree of the lookup terms
    requires std::is_same_v<decltype(S::LOOKUP_TERM_DEGREES), const std::array<size_t, S::NUM_LOOKUP_TERMS>>;
    // An array specifying the degree of the table terms
    requires std::is_same_v<decltype(S::TABLE_TERM_DEGREES), const std::array<size_t, S::NUM_TABLE_TERMS>>;
 
    requires std::is_same_v<decltype(S::LOOKUP_TUPLE_SIZE), const size_t>; // Number of columns to batch for basic lookups
 
    // Degree of the polynomial expression indicating whether the inverse polynomial exists at a given row
    requires std::is_same_v<decltype(S::INVERSE_EXISTS_POLYNOMIAL_DEGREE), const size_t>;
 
    // Settings also require the following methods, but some of them are templated, so we can't check them here.
    // 1) Settings::inverse_polynomial_is_computed_at_row(const AllValues& row), method to compute whether the inverse polynomial should be computed at a given row
    // 2) Settings::compute_inverse_exists<Accumulator>(const AllEntities& in), method to compute the value of the inverse_exists polynomial at a given row
    // 3) Settings::template compute_lookup_term<Accumulator, size_t>(const AllEntities&, const Parameters&), method to compute the lookup term at a given index
    // 4) Settings::template compute_table_term<Accumulator, size_t>(const AllEntities&, const Parameters&), method to compute the table term at a given index
    // 5) Settings::get_nonconst_entities(AllEntities&), method to extract non constant references to the columns used in the relation
    // 6) Settings::get_const_entities(const AllEntities&), method to extract constant references to the columns used in the relation
};
 
// clang-format on
template <typename Settings, typename FF_> class GenericLookupRelationImpl {
  public:
    using FF = FF_;
    using PolynomialStructure = LookupPolynomialStructure<Settings>;
 
    static constexpr size_t NUM_LOOKUP_TERMS = Settings::NUM_LOOKUP_TERMS;
    static constexpr size_t NUM_TABLE_TERMS = Settings::NUM_TABLE_TERMS;
 
    static constexpr size_t LOOKUP_TUPLE_SIZE = Settings::LOOKUP_TUPLE_SIZE;
 
    static constexpr size_t compute_lookup_term_product_degree()
    {
        size_t accumulated_degree = 0;
        for (size_t i = 0; i < NUM_LOOKUP_TERMS; i++) {
            size_t current_degree = 0;
            switch (Settings::LOOKUP_TYPES[i]) {
            case BASIC_LOOKUP:
                current_degree = 1;
                break;
            case CUSTOMIZED_LOOKUP:
                current_degree = Settings::LOOKUP_TERM_DEGREES[i];
                break;
            default:
                bb::assert_failure("Invalid lookup type");
            }
            accumulated_degree += current_degree;
        }
        return accumulated_degree;
    }
 
    static constexpr size_t compute_table_term_product_degree()
    {
        size_t accumulated_degree = 0;
        for (size_t i = 0; i < NUM_TABLE_TERMS; i++) {
            size_t current_degree = 0;
            switch (Settings::TABLE_TYPES[i]) {
            case BASIC_TABLE:
                current_degree = 1;
                break;
            case CUSTOMIZED_TABLE:
                current_degree = Settings::TABLE_TERM_DEGREES[i];
                break;
            default:
                bb::assert_failure("Invalid table type");
                break;
            }
            accumulated_degree += current_degree;
        }
        return accumulated_degree;
    }
 
    static constexpr size_t compute_second_subrelation_degree()
    {
        // Account for inverse polynomial, read count, and table term predicate
        constexpr size_t ADDITIONAL_DEGREE = 3;
        constexpr size_t TOTAL_TERM_PRODUCT_DEGREE =
            compute_lookup_term_product_degree() + compute_table_term_product_degree();
 
        size_t max_degree = 0;
        for (size_t i = 0; i < NUM_LOOKUP_TERMS; i++) {
            size_t current_degree = 0;
            switch (Settings::LOOKUP_TYPES[i]) {
            case BASIC_LOOKUP:
                current_degree = 1;
                break;
            case CUSTOMIZED_LOOKUP:
                current_degree = Settings::LOOKUP_TERM_DEGREES[i];
                break;
            default:
                bb::assert_failure("Invalid lookup type");
            }
            size_t adjusted_degree = TOTAL_TERM_PRODUCT_DEGREE - current_degree;
            max_degree = std::max(max_degree, adjusted_degree);
        }
        for (size_t i = 0; i < NUM_TABLE_TERMS; i++) {
            size_t current_degree = 0;
            switch (Settings::TABLE_TYPES[i]) {
            case BASIC_TABLE:
                current_degree = 1;
                break;
            case CUSTOMIZED_TABLE:
                current_degree = Settings::TABLE_TERM_DEGREES[i];
                break;
            default:
                bb::assert_failure("Invalid table type");
                break;
            }
            size_t adjusted_degree = TOTAL_TERM_PRODUCT_DEGREE - current_degree;
            max_degree = std::max(max_degree, adjusted_degree);
        }
        return max_degree + ADDITIONAL_DEGREE;
    }
 
    // (Sub)relation lengths: equal to 1 + relation degree
    static constexpr size_t LOOKUP_TERM_ACCUMULATED_DEGREE = compute_lookup_term_product_degree();
    static constexpr size_t TABLE_TERM_ACCUMULATED_DEGREE = compute_table_term_product_degree();
    static_assert(LOOKUP_TERM_ACCUMULATED_DEGREE > 0);
    static_assert(TABLE_TERM_ACCUMULATED_DEGREE > 0);
 
    static constexpr size_t FIRST_RELATION_PARTIAL_LENGTH =
        std::max(LOOKUP_TERM_ACCUMULATED_DEGREE + TABLE_TERM_ACCUMULATED_DEGREE + 1,
                 Settings::INVERSE_EXISTS_POLYNOMIAL_DEGREE) +
        1; // inverse polynomial correctness sub-relation
    static constexpr size_t SECOND_RELATION_PARTIAL_LENGTH =
        compute_second_subrelation_degree() + 1; // 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, LENGTH };
 
    // The first subrelation must be satisfied at every row.
    // The second subrelation must be satisfied when summed across the entire trace
    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)
    {
        // A lookup could be enabled by one of several selectors or witnesses, so we want to give as much freedom as
        // possible to the implementor
        return Settings::template compute_inverse_exists<Accumulator>(in);
    }
 
    template <typename Accumulator, size_t index, typename AllEntities>
    static Accumulator lookup_read_counts(const AllEntities& in)
    {
 
        static_assert(index < NUM_TABLE_TERMS);
        using View = typename Accumulator::View;
 
        return Accumulator(View(
            std::get<PolynomialStructure::get_read_count_polynomial_index(index)>(Settings::get_const_entities(in))));
    }
 
    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;
 
        return Accumulator(View(std::get<PolynomialStructure::get_lookup_term_predicate_index(lookup_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(table_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(lookup_index);
        const FF beta = params.beta;
        const FF gamma = params.gamma;
 
        if constexpr (Settings::LOOKUP_TYPES[lookup_index] == BASIC_LOOKUP) {
            // In this case we batch all the lookup columns pertaining to this lookup term using the randomness beta
            Accumulator result = Accumulator(0);
 
            const auto all_polynomials = Settings::get_const_entities(in);
            bb::constexpr_for<start_polynomial_index, start_polynomial_index + LOOKUP_TUPLE_SIZE, 1>(
                [&]<size_t i>() { result = (result * beta) + View(std::get<i>(all_polynomials)); });
 
            return result + gamma;
        } else if constexpr (Settings::LOOKUP_TYPES[lookup_index] == CUSTOMIZED_LOOKUP) {
            return Settings::template compute_lookup_term<Accumulator, lookup_index>(in, params);
        } else {
            bb::assert_failure("Invalid lookup type");
            return Accumulator(0);
        }
    }
 
    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(table_index);
        const FF beta = params.beta;
        const FF gamma = params.gamma;
 
        if constexpr (Settings::TABLE_TYPES[table_index] == BASIC_TABLE) {
            // In this case we batch all the lookup columns pertaining to this lookup term using the randomness beta
            Accumulator result = Accumulator(0);
 
            const auto all_polynomials = Settings::get_const_entities(in);
 
            bb::constexpr_for<start_polynomial_index, start_polynomial_index + LOOKUP_TUPLE_SIZE, 1>(
                [&]<size_t i>() { result = (result * beta) + View(std::get<i>(all_polynomials)); });
 
            return result + gamma;
        } else if constexpr (Settings::TABLE_TYPES[table_index] == CUSTOMIZED_TABLE) {
            return Settings::template compute_table_term<Accumulator, table_index>(in, params);
        } else {
            bb::assert_failure("Invalid table type");
            return Accumulator(0);
        }
    }
 
    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,
                                                            GenericLookupRelationImpl<Settings, FF>,
                                                            ContainerOverSubrelations,
                                                            AllEntities,
                                                            Parameters,
                                                            false>(accumulator, in, params, scaling_factor);
    }
};
 
template <typename Settings, typename FF>
using GenericLookupRelation = Relation<GenericLookupRelationImpl<Settings, FF>>;
 
} // namespace bb