protogalaxy_prover_internal.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/common/container.hpp"
#include "barretenberg/common/op_count.hpp"
#include "barretenberg/common/thread.hpp"
#include "barretenberg/honk/execution_trace/execution_trace_usage_tracker.hpp"
#include "barretenberg/protogalaxy/prover_verifier_shared.hpp"
#include "barretenberg/relations/relation_parameters.hpp"
#include "barretenberg/relations/relation_types.hpp"
#include "barretenberg/relations/utils.hpp"
#include "barretenberg/ultra_honk/oink_prover.hpp"
 
namespace bb {
 
template <class DeciderProvingKeys_> class ProtogalaxyProverInternal {
  public:
    using DeciderPKs = DeciderProvingKeys_;
    using Flavor = typename DeciderPKs::Flavor;
    using FF = typename Flavor::FF;
    using DeciderPK = typename DeciderPKs::DeciderPK;
    using RelationUtils = bb::RelationUtils<Flavor>;
    using ProverPolynomials = typename Flavor::ProverPolynomials;
    using Relations = typename Flavor::Relations;
    using AllValues = typename Flavor::AllValues;
    using SubrelationSeparators = typename Flavor::SubrelationSeparators;
    static constexpr size_t NUM_KEYS = DeciderProvingKeys_::NUM;
    using UnivariateRelationParametersNoOptimisticSkipping =
        bb::RelationParameters<Univariate<FF, DeciderProvingKeys_::EXTENDED_LENGTH>>;
    using UnivariateRelationParameters =
        bb::RelationParameters<Univariate<FF, DeciderProvingKeys_::EXTENDED_LENGTH, 0, /*skip_count=*/NUM_KEYS - 1>>;
    using UnivariateSubrelationSeparators =
        std::array<Univariate<FF, DeciderPKs::BATCHED_EXTENDED_LENGTH>, Flavor::NUM_SUBRELATIONS - 1>;
 
    // The length of ExtendedUnivariate is the largest length (==max_relation_degree + 1) of a univariate polynomial
    // obtained by composing a relation with Lagrange polynomial-linear combination of NUM-many decider pks, with
    // relation parameters regarded as variables.
    using ExtendedUnivariate = Univariate<FF, (Flavor::MAX_TOTAL_RELATION_LENGTH - 1) * (DeciderPKs::NUM - 1) + 1>;
    // Represents the total length of the combiner univariate, obtained by combining the already folded relations with
    // the folded relation batching challenge.
    using ExtendedUnivariateWithRandomization =
        Univariate<FF, (Flavor::MAX_TOTAL_RELATION_LENGTH - 1 + DeciderPKs::NUM - 1) * (DeciderPKs::NUM - 1) + 1>;
 
    using ShortUnivariates = typename Flavor::template ProverUnivariates<DeciderPKs::NUM>;
 
    using ExtendedUnivariates =
        typename Flavor::template ProverUnivariatesWithOptimisticSkipping<ExtendedUnivariate::LENGTH,
                                                                          /* SKIP_COUNT= */ DeciderPKs::NUM - 1>;
 
    using ExtendedUnivariatesType =
        std::conditional_t<Flavor::USE_SHORT_MONOMIALS, ShortUnivariates, ExtendedUnivariates>;
 
    using TupleOfTuplesOfUnivariates = typename Flavor::template ProtogalaxyTupleOfTuplesOfUnivariates<DeciderPKs::NUM>;
    using TupleOfTuplesOfUnivariatesNoOptimisticSkipping =
        typename Flavor::template ProtogalaxyTupleOfTuplesOfUnivariatesNoOptimisticSkipping<DeciderPKs::NUM>;
 
    using RelationEvaluations = decltype(create_tuple_of_arrays_of_values<typename Flavor::Relations>());
 
    static constexpr size_t NUM_SUBRELATIONS = DeciderPKs::NUM_SUBRELATIONS;
 
    ExecutionTraceUsageTracker trace_usage_tracker;
 
    ProtogalaxyProverInternal(ExecutionTraceUsageTracker trace_usage_tracker = ExecutionTraceUsageTracker{})
        : trace_usage_tracker(std::move(trace_usage_tracker))
    {}
 
    inline static FF process_subrelation_evaluations(const RelationEvaluations& evals,
                                                     const SubrelationSeparators& challenges,
                                                     FF& linearly_dependent_contribution)
    {
        // Initialize result with the contribution from the first subrelation
        FF linearly_independent_contribution = std::get<0>(evals)[0];
        size_t idx = 0;
 
        auto scale_by_challenge_and_accumulate =
            [&]<size_t relation_idx, size_t subrelation_idx, typename Element>(Element& element) {
                if constexpr (!(relation_idx == 0 && subrelation_idx == 0)) {
                    using Relation = typename std::tuple_element_t<relation_idx, Relations>;
                    // Accumulate scaled subrelation contribution
                    const Element contribution = element * challenges[idx++];
                    if constexpr (subrelation_is_linearly_independent<Relation, subrelation_idx>()) {
                        linearly_independent_contribution += contribution;
                    } else {
                        linearly_dependent_contribution += contribution;
                    }
                }
            };
        RelationUtils::apply_to_tuple_of_arrays_elements(scale_by_challenge_and_accumulate, evals);
        return linearly_independent_contribution;
    }
 
    Polynomial<FF> compute_row_evaluations(const ProverPolynomials& polynomials,
                                           const SubrelationSeparators& alphas,
                                           const RelationParameters<FF>& relation_parameters)
 
    {
 
        PROFILE_THIS_NAME("ProtogalaxyProver_::compute_row_evaluations");
 
        const size_t polynomial_size = polynomials.get_polynomial_size();
        Polynomial<FF> aggregated_relation_evaluations(polynomial_size);
 
        // Determine the number of threads over which to distribute the work
        const size_t num_threads = compute_num_threads(polynomial_size);
 
        std::vector<FF> linearly_dependent_contribution_accumulators(num_threads);
 
        // Distribute the execution trace rows across threads so that each handles an equal number of active rows
        trace_usage_tracker.construct_thread_ranges(
            num_threads, polynomial_size, /*use_prev_accumulator_tracker=*/true);
 
        parallel_for(num_threads, [&](size_t thread_idx) {
            for (const ExecutionTraceUsageTracker::Range& range : trace_usage_tracker.thread_ranges[thread_idx]) {
                for (size_t idx = range.first; idx < range.second; idx++) {
                    const AllValues row = polynomials.get_row(idx);
                    // Evaluate all subrelations on given row. Separator is 1 since we are not summing across rows here.
                    const RelationEvaluations evals =
                        RelationUtils::accumulate_relation_evaluations(row, relation_parameters, FF(1));
 
                    // Sum against challenges alpha
                    aggregated_relation_evaluations.at(idx) = process_subrelation_evaluations(
                        evals, alphas, linearly_dependent_contribution_accumulators[thread_idx]);
                }
            }
        });
 
        aggregated_relation_evaluations.at(0) += sum(linearly_dependent_contribution_accumulators);
 
        return aggregated_relation_evaluations;
    }
    static std::vector<FF> construct_coefficients_tree(std::span<const FF> betas,
                                                       std::span<const FF> deltas,
                                                       const std::vector<std::vector<FF>>& prev_level_coeffs,
                                                       size_t level = 1)
    {
        if (level == betas.size()) {
            return prev_level_coeffs[0];
        }
 
        auto degree = level + 1;
        auto prev_level_width = prev_level_coeffs.size();
        std::vector<std::vector<FF>> level_coeffs(prev_level_width / 2, std::vector<FF>(degree + 1, 0));
        parallel_for_heuristic(
            prev_level_width / 2,
            [&](size_t parent) {
                size_t node = parent * 2;
                std::copy(prev_level_coeffs[node].begin(), prev_level_coeffs[node].end(), level_coeffs[parent].begin());
                for (size_t d = 0; d < degree; d++) {
                    level_coeffs[parent][d] += prev_level_coeffs[node + 1][d] * betas[level];
                    level_coeffs[parent][d + 1] += prev_level_coeffs[node + 1][d] * deltas[level];
                }
            },
            /* overestimate */ thread_heuristics::FF_MULTIPLICATION_COST * degree * 3);
        return construct_coefficients_tree(betas, deltas, level_coeffs, level + 1);
    }
 
    static std::vector<FF> construct_perturbator_coefficients(std::span<const FF> betas,
                                                              std::span<const FF> deltas,
                                                              const Polynomial<FF>& full_honk_evaluations)
    {
        auto width = full_honk_evaluations.size();
        std::vector<std::vector<FF>> first_level_coeffs(width / 2, std::vector<FF>(2, 0));
        parallel_for_heuristic(
            width / 2,
            [&](size_t parent) {
                size_t node = parent * 2;
                first_level_coeffs[parent][0] =
                    full_honk_evaluations[node] + full_honk_evaluations[node + 1] * betas[0];
                first_level_coeffs[parent][1] = full_honk_evaluations[node + 1] * deltas[0];
            },
            /* overestimate */ thread_heuristics::FF_MULTIPLICATION_COST * 3);
        return construct_coefficients_tree(betas, deltas, first_level_coeffs);
    }
 
    Polynomial<FF> compute_perturbator(const std::shared_ptr<const DeciderPK>& accumulator,
                                       const std::vector<FF>& deltas)
    {
        PROFILE_THIS();
        auto full_honk_evaluations =
            compute_row_evaluations(accumulator->polynomials, accumulator->alphas, accumulator->relation_parameters);
        const auto betas = accumulator->gate_challenges;
        BB_ASSERT_EQ(betas.size(), deltas.size());
        const size_t log_circuit_size = accumulator->log_dyadic_size();
 
        // Compute the perturbator using only the first log_circuit_size-many betas/deltas
        std::vector<FF> perturbator = construct_perturbator_coefficients(std::span{ betas.data(), log_circuit_size },
                                                                         std::span{ deltas.data(), log_circuit_size },
                                                                         full_honk_evaluations);
 
        // Populate the remaining coefficients with zeros to reach the required constant size
        for (size_t idx = log_circuit_size; idx < CONST_PG_LOG_N; ++idx) {
            perturbator.emplace_back(FF(0));
        }
        return Polynomial<FF>{ perturbator };
    }
 
    template <size_t skip_count = 0>
    BB_INLINE static void extend_univariates(ExtendedUnivariatesType& extended_univariates,
                                             const DeciderPKs& keys,
                                             const size_t row_idx)
    {
        if constexpr (Flavor::USE_SHORT_MONOMIALS) {
            extended_univariates = std::move(keys.row_to_short_univariates(row_idx));
        } else {
            auto incoming_univariates =
                keys.template row_to_univariates<ExtendedUnivariate::LENGTH, skip_count>(row_idx);
            for (auto [extended_univariate, incoming_univariate] :
                 zip_view(extended_univariates.get_all(), incoming_univariates)) {
                incoming_univariate.template self_extend_from<NUM_KEYS>();
                extended_univariate = std::move(incoming_univariate);
            }
        }
    }
 
    template <size_t relation_idx = 0>
    BB_INLINE static void accumulate_relation_univariates(TupleOfTuplesOfUnivariates& univariate_accumulators,
                                                          const ExtendedUnivariatesType& extended_univariates,
                                                          const UnivariateRelationParameters& relation_parameters,
                                                          const FF& scaling_factor)
    {
        using Relation = std::tuple_element_t<relation_idx, Relations>;
 
        //  Check if the relation is skippable to speed up accumulation
        if constexpr (!isSkippable<Relation, decltype(extended_univariates)>) {
            // If not, accumulate normally
            Relation::accumulate(std::get<relation_idx>(univariate_accumulators),
                                 extended_univariates,
                                 relation_parameters,
                                 scaling_factor);
        } else {
            // If so, only compute the contribution if the relation is active
            if (!Relation::skip(extended_univariates)) {
                Relation::accumulate(std::get<relation_idx>(univariate_accumulators),
                                     extended_univariates,
                                     relation_parameters,
                                     scaling_factor);
            }
        }
 
        // Repeat for the next relation.
        if constexpr (relation_idx + 1 < Flavor::NUM_RELATIONS) {
            accumulate_relation_univariates<relation_idx + 1>(
                univariate_accumulators, extended_univariates, relation_parameters, scaling_factor);
        }
    }
 
    ExtendedUnivariateWithRandomization compute_combiner(const DeciderPKs& keys,
                                                         const GateSeparatorPolynomial<FF>& gate_separators,
                                                         const UnivariateRelationParameters& relation_parameters,
                                                         const UnivariateSubrelationSeparators& alphas,
                                                         TupleOfTuplesOfUnivariates& univariate_accumulators)
    {
        PROFILE_THIS();
 
        // Determine the number of threads over which to distribute the work
        // The polynomial size is given by the virtual size since the computation includes
        // the incoming key which could have nontrivial values on the larger domain in case of overflow.
        const size_t common_polynomial_size = keys[0]->polynomials.w_l.virtual_size();
        const size_t num_threads = compute_num_threads(common_polynomial_size);
 
        // Univariates are optimized for usual PG, but we need the unoptimized version for tests (it's a version that
        // doesn't skip computation), so we need to define types depending on the template instantiation
        using ThreadAccumulators = TupleOfTuplesOfUnivariates;
 
        // Construct univariate accumulator containers; one per thread
        // Note: std::vector will trigger {}-initialization of the contents. Therefore no need to zero the univariates.
        std::vector<ThreadAccumulators> thread_univariate_accumulators(num_threads);
 
        // Distribute the execution trace rows across threads so that each handles an equal number of active rows
        trace_usage_tracker.construct_thread_ranges(num_threads, common_polynomial_size);
 
        // Accumulate the contribution from each sub-relation
        parallel_for(num_threads, [&](size_t thread_idx) {
            // Construct extended univariates containers; one per thread
            ExtendedUnivariatesType extended_univariates;
 
            for (const ExecutionTraceUsageTracker::Range& range : trace_usage_tracker.thread_ranges[thread_idx]) {
                for (size_t idx = range.first; idx < range.second; idx++) {
                    // Instantiate univariates, possibly with skipping toto ignore computation in those indices
                    // (they are still available for skipping relations, but all derived univariate will ignore
                    // those evaluations) No need to initialize extended_univariates to 0, as it's assigned to.
                    constexpr size_t skip_count = DeciderPKs::NUM - 1;
                    extend_univariates<skip_count>(extended_univariates, keys, idx);
 
                    const FF pow_challenge = gate_separators[idx];
 
                    // Accumulate the i-th row's univariate contribution. Note that the relation parameters passed
                    // to this function have already been folded. Moreover, linear-dependent relations that act over
                    // the entire execution trace rather than on rows, will not be multiplied by the pow challenge.
                    accumulate_relation_univariates(thread_univariate_accumulators[thread_idx],
                                                    extended_univariates,
                                                    relation_parameters, // these parameters have already been folded
                                                    pow_challenge);
                }
            }
        });
 
        RelationUtils::zero_univariates(univariate_accumulators);
        // Accumulate the per-thread univariate accumulators into a single set of accumulators
        for (auto& accumulators : thread_univariate_accumulators) {
            RelationUtils::add_nested_tuples(univariate_accumulators, accumulators);
        }
        // This does nothing if TupleOfTuples is TupleOfTuplesOfUnivariates
        TupleOfTuplesOfUnivariatesNoOptimisticSkipping deoptimized_univariates =
            deoptimize_univariates(univariate_accumulators);
        //  Batch the univariate contributions from each sub-relation to obtain the round univariate
        return batch_over_relations(deoptimized_univariates, alphas);
    }
 
    ExtendedUnivariateWithRandomization compute_combiner(const DeciderPKs& keys,
                                                         const GateSeparatorPolynomial<FF>& gate_separators,
                                                         const UnivariateRelationParameters& relation_parameters,
                                                         const UnivariateSubrelationSeparators& alphas)
    {
        // Note: {} is required to initialize the tuple contents. Otherwise the univariates contain garbage.
        TupleOfTuplesOfUnivariates accumulators{};
        return compute_combiner(keys, gate_separators, relation_parameters, alphas, accumulators);
    }
 
    template <typename TupleOfTuplesOfUnivariatePossiblyOptimistic>
    static TupleOfTuplesOfUnivariatesNoOptimisticSkipping deoptimize_univariates(
        const TupleOfTuplesOfUnivariatePossiblyOptimistic& tup)
    {
        // If input does not have optimized operators, return the input
        if constexpr (std::same_as<TupleOfTuplesOfUnivariatePossiblyOptimistic,
                                   TupleOfTuplesOfUnivariatesNoOptimisticSkipping>) {
            return tup;
        }
 
        const auto deoptimize = [&]<size_t outer_idx, size_t inner_idx>(auto& element) {
            auto& element_with_skipping = std::get<inner_idx>(std::get<outer_idx>(tup));
            element = element_with_skipping.convert();
        };
 
        // Note: {} is required to initialize the tuple contents. Otherwise the univariates contain garbage.
        TupleOfTuplesOfUnivariatesNoOptimisticSkipping result{};
        RelationUtils::apply_to_tuple_of_tuples(result, deoptimize);
        return result;
    }
 
    static ExtendedUnivariateWithRandomization batch_over_relations(
        TupleOfTuplesOfUnivariatesNoOptimisticSkipping& univariate_accumulators,
        const UnivariateSubrelationSeparators& alphas)
    {
        auto result =
            std::get<0>(std::get<0>(univariate_accumulators)).template extend_to<DeciderPKs::BATCHED_EXTENDED_LENGTH>();
 
        size_t idx = 0;
        const auto scale_and_sum = [&]<size_t outer_idx, size_t inner_idx>(auto& element) {
            if constexpr (outer_idx == 0 && inner_idx == 0) {
                return;
            }
 
            auto extended = element.template extend_to<DeciderPKs::BATCHED_EXTENDED_LENGTH>();
            extended *= alphas[idx];
            result += extended;
            idx++;
        };
 
        RelationUtils::apply_to_tuple_of_tuples(univariate_accumulators, scale_and_sum);
        RelationUtils::zero_univariates(univariate_accumulators);
 
        return result;
    }
 
    static std::pair<typename DeciderPKs::FF, std::array<typename DeciderPKs::FF, DeciderPKs::NUM>>
    compute_vanishing_polynomial_and_lagranges(const FF& challenge)
    {
        FF vanishing_polynomial_at_challenge;
        std::array<FF, DeciderPKs::NUM> lagranges;
        constexpr FF inverse_two = FF(2).invert();
 
        if constexpr (DeciderPKs::NUM == 2) {
            vanishing_polynomial_at_challenge = challenge * (challenge - FF(1));
            lagranges = { FF(1) - challenge, challenge };
        } else if constexpr (DeciderPKs::NUM == 3) {
            vanishing_polynomial_at_challenge = challenge * (challenge - FF(1)) * (challenge - FF(2));
            lagranges = { (FF(1) - challenge) * (FF(2) - challenge) * inverse_two,
                          challenge * (FF(2) - challenge),
                          challenge * (challenge - FF(1)) / FF(2) };
        } else if constexpr (DeciderPKs::NUM == 4) {
            constexpr FF inverse_six = FF(6).invert();
            vanishing_polynomial_at_challenge =
                challenge * (challenge - FF(1)) * (challenge - FF(2)) * (challenge - FF(3));
            lagranges = { (FF(1) - challenge) * (FF(2) - challenge) * (FF(3) - challenge) * inverse_six,
                          challenge * (FF(2) - challenge) * (FF(3) - challenge) * inverse_two,
                          challenge * (challenge - FF(1)) * (FF(3) - challenge) * inverse_two,
                          challenge * (challenge - FF(1)) * (challenge - FF(2)) * inverse_six };
        }
        static_assert(DeciderPKs::NUM < 5);
 
        return { vanishing_polynomial_at_challenge, lagranges };
    }
 
    static Univariate<FF, DeciderPKs::BATCHED_EXTENDED_LENGTH, DeciderPKs::NUM> compute_combiner_quotient(
        FF perturbator_evaluation, ExtendedUnivariateWithRandomization combiner)
    {
        std::array<FF, DeciderPKs::BATCHED_EXTENDED_LENGTH - DeciderPKs::NUM> combiner_quotient_evals = {};
 
        constexpr FF inverse_two = FF(2).invert();
        constexpr FF inverse_six = FF(6).invert();
        for (size_t point = DeciderPKs::NUM; point < combiner.size(); point++) {
            auto idx = point - DeciderPKs::NUM;
            FF lagrange_0;
            FF vanishing_polynomial;
            if constexpr (DeciderPKs::NUM == 2) {
                lagrange_0 = FF(1) - FF(point);
                vanishing_polynomial = FF(point) * (FF(point) - 1);
            } else if constexpr (DeciderPKs::NUM == 3) {
                lagrange_0 = (FF(1) - FF(point)) * (FF(2) - FF(point)) * inverse_two;
                vanishing_polynomial = FF(point) * (FF(point) - 1) * (FF(point) - 2);
            } else if constexpr (DeciderPKs::NUM == 4) {
                lagrange_0 = (FF(1) - FF(point)) * (FF(2) - FF(point)) * (FF(3) - FF(point)) * inverse_six;
                vanishing_polynomial = FF(point) * (FF(point) - 1) * (FF(point) - 2) * (FF(point) - 3);
            }
            static_assert(DeciderPKs::NUM < 5);
 
            combiner_quotient_evals[idx] =
                (combiner.value_at(point) - perturbator_evaluation * lagrange_0) * vanishing_polynomial.invert();
        }
 
        return Univariate<FF, DeciderPKs::BATCHED_EXTENDED_LENGTH, DeciderPKs::NUM>(combiner_quotient_evals);
    }
 
    template <typename ExtendedRelationParameters>
    static ExtendedRelationParameters compute_extended_relation_parameters(const DeciderPKs& keys)
    {
        using UnivariateParameter = typename ExtendedRelationParameters::DataType;
        ExtendedRelationParameters result;
        size_t param_idx = 0;
        for (auto& param : result.get_to_fold()) {
            Univariate<FF, DeciderPKs::NUM> tmp(0);
            size_t key_idx = 0;
            for (auto& key : keys) {
                tmp.value_at(key_idx) = key->relation_parameters.get_to_fold()[param_idx];
                key_idx++;
            }
            param = tmp.template extend_to<UnivariateParameter::LENGTH, UnivariateParameter::SKIP_COUNT>();
            param_idx++;
        }
        return result;
    }
 
    static UnivariateSubrelationSeparators compute_and_extend_alphas(const DeciderPKs& keys)
    {
        UnivariateSubrelationSeparators result;
        size_t alpha_idx = 0;
        for (auto& alpha : result) {
            Univariate<FF, DeciderPKs::NUM> tmp;
            size_t key_idx = 0;
            for (auto& key : keys) {
                tmp.value_at(key_idx) = key->alphas[alpha_idx];
                key_idx++;
            }
            alpha = tmp.template extend_to<DeciderPKs::BATCHED_EXTENDED_LENGTH>();
            alpha_idx++;
        }
        return result;
    }
 
    static size_t compute_num_threads(const size_t domain_size)
    {
        const size_t max_num_threads = get_num_cpus_pow2(); // number of available threads (power of 2)
        const size_t min_iterations_per_thread =
            1 << 6; // min number of iterations for which we'll spin up a unique thread
        const size_t desired_num_threads = domain_size / min_iterations_per_thread;
        size_t num_threads = std::min(desired_num_threads, max_num_threads); // fewer than max if justified
        num_threads = num_threads > 0 ? num_threads : 1;                     // ensure num threads is >= 1
 
        return num_threads;
    }
};
} // namespace bb