logderivative_library.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/constexpr_utils.hpp"
#include "barretenberg/common/thread.hpp"
#include "barretenberg/common/tuple.hpp"
 
#include <span>
#include <typeinfo>
 
namespace bb {
 
template <typename FF, typename Relation, typename Polynomials, bool UseMultithreading = false>
void compute_logderivative_inverse(Polynomials& polynomials, auto& relation_parameters, const size_t circuit_size)
{
    using Accumulator = typename Relation::ValueAccumulator0;
    constexpr size_t READ_TERMS = Relation::READ_TERMS;
    constexpr size_t WRITE_TERMS = Relation::WRITE_TERMS;
 
    auto& inverse_polynomial = Relation::get_inverse_polynomial(polynomials);
    const size_t offset = inverse_polynomial.start_index();
    const auto compute_inverses = [&](size_t start, size_t end) {
        for (size_t i = start; i < end; ++i) {
            // TODO(https://github.com/AztecProtocol/barretenberg/issues/940): avoid get_row if possible.
            auto row = polynomials.get_row(i + offset);
            bool has_inverse = Relation::operation_exists_at_row(row);
            if (!has_inverse) {
                continue;
            }
            FF denominator = 1;
            bb::constexpr_for<0, READ_TERMS, 1>([&]<size_t read_index> {
                auto denominator_term =
                    Relation::template compute_read_term<Accumulator, read_index>(row, relation_parameters);
                denominator *= denominator_term;
            });
            bb::constexpr_for<0, WRITE_TERMS, 1>([&]<size_t write_index> {
                auto denominator_term =
                    Relation::template compute_write_term<Accumulator, write_index>(row, relation_parameters);
                denominator *= denominator_term;
            });
            inverse_polynomial.at(i) = denominator;
        }
        FF* ffstart = &inverse_polynomial.coeffs()[start];
        std::span<FF> to_invert(ffstart, end - start);
        // Compute inverse polynomial I in place by inverting the product at each row
        // Note: zeroes are ignored as they are not used anyway
        FF::batch_invert(to_invert);
    };
    if constexpr (UseMultithreading) {
        const size_t min_iterations_per_thread = 128;
        size_t num_threads = bb::calculate_num_threads_pow2(inverse_polynomial.size(), min_iterations_per_thread);
        const size_t rows_per_thread = inverse_polynomial.size() / num_threads;
        parallel_for(num_threads, [&](size_t thread_idx) {
            const size_t start = thread_idx * rows_per_thread;
            const size_t end = (thread_idx == num_threads - 1) ? circuit_size : (thread_idx + 1) * rows_per_thread;
            compute_inverses(start, end);
        });
    } else {
        compute_inverses(0, inverse_polynomial.size());
    }
}
 
template <typename FF, typename Relation, typename ContainerOverSubrelations, typename AllEntities, typename Parameters>
void accumulate_logderivative_lookup_subrelation_contributions(ContainerOverSubrelations& accumulator,
                                                               const AllEntities& in,
                                                               const Parameters& params,
                                                               const FF& scaling_factor)
{
    constexpr size_t READ_TERMS = Relation::READ_TERMS;
    constexpr size_t WRITE_TERMS = Relation::WRITE_TERMS;
 
    using Accumulator = typename std::tuple_element_t<0, ContainerOverSubrelations>;
    using View = typename Accumulator::View;
 
    auto lookup_inverses = View(Relation::get_inverse_polynomial(in));
 
    constexpr size_t NUM_TOTAL_TERMS = READ_TERMS + WRITE_TERMS;
    std::array<Accumulator, NUM_TOTAL_TERMS> lookup_terms;
    std::array<Accumulator, NUM_TOTAL_TERMS> denominator_accumulator;
 
    // The lookup relation = \sum_j (1 / read_term[j]) - \sum_k (read_counts[k] / write_term[k])
    // To get the inverses (1 / read_term[i]), (1 / write_term[i]), we have a commitment to the product of all inverses
    // i.e. lookup_inverse = \prod_j (1 / read_term[j]) * \prod_k (1 / write_term[k])
    // The purpose of this next section is to derive individual inverse terms using `lookup_inverses`
    // i.e. (1 / read_term[i]) = lookup_inverse * \prod_{j /ne i} (read_term[j]) * \prod_k (write_term[k])
    //      (1 / write_term[i]) = lookup_inverse * \prod_j (read_term[j]) * \prod_{k ne i} (write_term[k])
    bb::constexpr_for<0, READ_TERMS, 1>(
        [&]<size_t i>() { lookup_terms[i] = Relation::template compute_read_term<Accumulator, i>(in, params); });
    bb::constexpr_for<0, WRITE_TERMS, 1>([&]<size_t i>() {
        lookup_terms[i + READ_TERMS] = Relation::template compute_write_term<Accumulator, i>(in, params);
    });
 
    bb::constexpr_for<0, NUM_TOTAL_TERMS, 1>([&]<size_t i>() { denominator_accumulator[i] = lookup_terms[i]; });
 
    bb::constexpr_for<0, NUM_TOTAL_TERMS - 1, 1>(
        [&]<size_t i>() { denominator_accumulator[i + 1] *= denominator_accumulator[i]; });
 
    auto inverse_accumulator = Accumulator(lookup_inverses); // denominator_accumulator[NUM_TOTAL_TERMS - 1];
 
    const auto inverse_exists = Relation::template compute_inverse_exists<Accumulator>(in);
 
    // Note: the lookup_inverses are computed so that the value is 0 if !inverse_exists
    std::get<0>(accumulator) +=
        (denominator_accumulator[NUM_TOTAL_TERMS - 1] * lookup_inverses - inverse_exists) * scaling_factor;
 
    // After this algo, total degree of denominator_accumulator = NUM_TOTAL_TERMS
    for (size_t i = 0; i < NUM_TOTAL_TERMS - 1; ++i) {
        denominator_accumulator[NUM_TOTAL_TERMS - 1 - i] =
            denominator_accumulator[NUM_TOTAL_TERMS - 2 - i] * inverse_accumulator;
        inverse_accumulator = inverse_accumulator * lookup_terms[NUM_TOTAL_TERMS - 1 - i];
    }
    denominator_accumulator[0] = inverse_accumulator;
 
    // each predicate is degree-1
    // degree of relation at this point = NUM_TOTAL_TERMS + 1
    bb::constexpr_for<0, READ_TERMS, 1>([&]<size_t i>() {
        std::get<1>(accumulator) +=
            Relation::template compute_read_term_predicate<Accumulator, i>(in) * denominator_accumulator[i];
    });
 
    // each predicate is degree-1, `lookup_read_counts` is degree-1
    // degree of relation = NUM_TOTAL_TERMS + 2
    bb::constexpr_for<0, WRITE_TERMS, 1>([&]<size_t i>() {
        const auto p = Relation::template compute_write_term_predicate<Accumulator, i>(in);
        const auto lookup_read_count = Relation::template lookup_read_counts<Accumulator, i>(in);
        std::get<1>(accumulator) -= p * (denominator_accumulator[i + READ_TERMS] * lookup_read_count);
    });
}
 
template <typename FF, typename Relation, typename ContainerOverSubrelations, typename AllEntities, typename Parameters>
void accumulate_logderivative_permutation_subrelation_contributions(ContainerOverSubrelations& accumulator,
                                                                    const AllEntities& in,
                                                                    const Parameters& params,
                                                                    const FF& scaling_factor)
{
    constexpr size_t READ_TERMS = Relation::READ_TERMS;
    constexpr size_t WRITE_TERMS = Relation::WRITE_TERMS;
 
    // For now we only do simple permutations over tuples with 1 read and 1 write term
    static_assert(READ_TERMS == 1);
    static_assert(WRITE_TERMS == 1);
 
    using Accumulator = typename std::tuple_element_t<0, ContainerOverSubrelations>;
    using View = typename Accumulator::View;
 
    auto permutation_inverses = View(Relation::get_inverse_polynomial(in));
 
    constexpr size_t NUM_TOTAL_TERMS = 2;
    std::array<Accumulator, NUM_TOTAL_TERMS> permutation_terms;
    std::array<Accumulator, NUM_TOTAL_TERMS> denominator_accumulator;
 
    // The permutation relation =  1 / read_term - 1 / write_term
    // To get the inverses (1 / read_term), (1 / write_term), we have a commitment to the product ofinver ses
    // i.e. permutation_inverses =  (1 / read_term) * (1 / write_term)
    // The purpose of this next section is to derive individual inverse terms using `permutation_inverses`
    // i.e. (1 / read_term) = permutation_inverses * write_term
    //      (1 / write_term) = permutation_inverses * read_term
    permutation_terms[0] = Relation::template compute_read_term<Accumulator, 0>(in, params);
    permutation_terms[1] = Relation::template compute_write_term<Accumulator, 0>(in, params);
 
    bb::constexpr_for<0, NUM_TOTAL_TERMS, 1>([&]<size_t i>() { denominator_accumulator[i] = permutation_terms[i]; });
 
    bb::constexpr_for<0, NUM_TOTAL_TERMS - 1, 1>(
        [&]<size_t i>() { denominator_accumulator[i + 1] *= denominator_accumulator[i]; });
 
    auto inverse_accumulator = Accumulator(permutation_inverses); // denominator_accumulator[NUM_TOTAL_TERMS - 1];
 
    const auto inverse_exists = Relation::template compute_inverse_exists<Accumulator>(in);
 
    // Note: the lookup_inverses are computed so that the value is 0 if !inverse_exists
    std::get<0>(accumulator) +=
        (denominator_accumulator[NUM_TOTAL_TERMS - 1] * permutation_inverses - inverse_exists) * scaling_factor;
 
    // After this algo, total degree of denominator_accumulator = NUM_TOTAL_TERMS
    for (size_t i = 0; i < NUM_TOTAL_TERMS - 1; ++i) {
        denominator_accumulator[NUM_TOTAL_TERMS - 1 - i] =
            denominator_accumulator[NUM_TOTAL_TERMS - 2 - i] * inverse_accumulator;
        inverse_accumulator = inverse_accumulator * permutation_terms[NUM_TOTAL_TERMS - 1 - i];
    }
    denominator_accumulator[0] = inverse_accumulator;
 
    // each predicate is degree-1
    // degree of relation at this point = NUM_TOTAL_TERMS + 1
    std::get<1>(accumulator) +=
        Relation::template compute_read_term_predicate<Accumulator, 0>(in) * denominator_accumulator[0];
 
    // each predicate is degree-1
    // degree of relation = NUM_TOTAL_TERMS + 1
    std::get<1>(accumulator) -=
        Relation::template compute_write_term_predicate<Accumulator, 0>(in) * denominator_accumulator[1];
}
 
} // namespace bb