relation_types.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 "barretenberg/ecc/curves/bn254/fr.hpp"
#include "nested_containers.hpp"
#include <algorithm>
 
template <typename T>
concept IsField = std::same_as<T, bb::fr> /* || std::same_as<T, grumpkin::fr> */;
 
namespace bb {
 
template <typename Params, typename View>
using GetParameterView = std::conditional_t<IsField<typename Params::DataType>, typename Params::DataType, View>;
 
template <typename T>
concept HasSubrelationLinearlyIndependentMember = requires(T) {
    { std::get<0>(T::SUBRELATION_LINEARLY_INDEPENDENT) } -> std::convertible_to<bool>;
};
 
template <typename T>
concept HasParameterLengthAdjustmentsMember = requires { T::TOTAL_LENGTH_ADJUSTMENTS; };
 
template <typename Relation, size_t subrelation_index> constexpr bool subrelation_is_linearly_independent()
{
    if constexpr (HasSubrelationLinearlyIndependentMember<Relation>) {
        return std::get<subrelation_index>(Relation::SUBRELATION_LINEARLY_INDEPENDENT);
    } else {
        return true;
    }
}
 
template <typename RelationImpl>
consteval std::array<size_t, RelationImpl::SUBRELATION_PARTIAL_LENGTHS.size()> compute_total_subrelation_lengths()
{
    if constexpr (HasParameterLengthAdjustmentsMember<RelationImpl>) {
        constexpr size_t NUM_SUBRELATIONS = RelationImpl::SUBRELATION_PARTIAL_LENGTHS.size();
        std::array<size_t, NUM_SUBRELATIONS> result;
        for (size_t idx = 0; idx < NUM_SUBRELATIONS; idx++) {
            result[idx] = RelationImpl::SUBRELATION_PARTIAL_LENGTHS[idx] + RelationImpl::TOTAL_LENGTH_ADJUSTMENTS[idx];
        }
        return result;
    } else {
        return RelationImpl::SUBRELATION_PARTIAL_LENGTHS;
    }
};
 
template <size_t NUM_KEYS, size_t NUM_SUBRELATIONS>
consteval std::array<size_t, NUM_SUBRELATIONS> compute_composed_subrelation_partial_lengths(
    std::array<size_t, NUM_SUBRELATIONS> SUBRELATION_PARTIAL_LENGTHS)
{
    std::transform(SUBRELATION_PARTIAL_LENGTHS.begin(),
                   SUBRELATION_PARTIAL_LENGTHS.end(),
                   SUBRELATION_PARTIAL_LENGTHS.begin(),
                   [](const size_t x) { return (x - 1) * (NUM_KEYS - 1) + 1; });
    return SUBRELATION_PARTIAL_LENGTHS;
};
 
template <typename Relation, typename AllEntities>
concept isSkippable = requires(const AllEntities& input) {
    { Relation::skip(input) } -> std::same_as<bool>;
};
 
template <typename Flavor, typename ProverPolynomialsOrPartiallyEvaluatedMultivariates, typename EdgeType>
concept isRowSkippable =
    requires(const ProverPolynomialsOrPartiallyEvaluatedMultivariates& input, const EdgeType edge_idx) {
        { Flavor::skip_entire_row(input, edge_idx) } -> std::same_as<bool>;
    };
 
template <typename RelationImpl> class Relation : public RelationImpl {
  public:
    using FF = typename RelationImpl::FF;
 
    static constexpr std::array<size_t, RelationImpl::SUBRELATION_PARTIAL_LENGTHS.size()> SUBRELATION_TOTAL_LENGTHS =
        compute_total_subrelation_lengths<RelationImpl>();
 
    static constexpr size_t RELATION_LENGTH = *std::max_element(RelationImpl::SUBRELATION_PARTIAL_LENGTHS.begin(),
                                                                RelationImpl::SUBRELATION_PARTIAL_LENGTHS.end());
 
    static constexpr size_t TOTAL_RELATION_LENGTH =
        *std::max_element(SUBRELATION_TOTAL_LENGTHS.begin(), SUBRELATION_TOTAL_LENGTHS.end());
 
    template <size_t NUM_KEYS>
    using ProtogalaxyTupleOfUnivariatesOverSubrelationsNoOptimisticSkipping =
        TupleOfUnivariates<FF, compute_composed_subrelation_partial_lengths<NUM_KEYS>(SUBRELATION_TOTAL_LENGTHS)>;
    template <size_t NUM_KEYS>
    using ProtogalaxyTupleOfUnivariatesOverSubrelations =
        TupleOfUnivariatesWithOptimisticSkipping<FF,
                                                 compute_composed_subrelation_partial_lengths<NUM_KEYS>(
                                                     SUBRELATION_TOTAL_LENGTHS),
                                                 NUM_KEYS - 1>;
    using SumcheckTupleOfUnivariatesOverSubrelations =
        TupleOfUnivariates<FF, RelationImpl::SUBRELATION_PARTIAL_LENGTHS>;
 
    using SumcheckArrayOfValuesOverSubrelations = ArrayOfValues<FF, RelationImpl::SUBRELATION_PARTIAL_LENGTHS>;
 
    // These are commonly needed, most importantly, for explicitly instantiating
    // compute_foo_numerator/denomintor.
    using UnivariateAccumulator0 = std::tuple_element_t<0, SumcheckTupleOfUnivariatesOverSubrelations>;
    using ValueAccumulator0 = std::tuple_element_t<0, SumcheckArrayOfValuesOverSubrelations>;
};
} // namespace bb