logderivative_library.hpp

#pragma once
#include <typeinfo>
 
namespace proof_system::honk::logderivative_library {
 
template <typename Flavor, typename Relation, typename Polynomials>
void compute_logderivative_inverse(Polynomials& polynomials, auto& relation_parameters, const size_t circuit_size)
{
    using FF = typename Flavor::FF;
    using Accumulator = typename Relation::ValueAccumulator0;
    constexpr size_t READ_TERMS = Relation::READ_TERMS;
    constexpr size_t WRITE_TERMS = Relation::WRITE_TERMS;
 
    auto lookup_relation = Relation();
    auto& inverse_polynomial = lookup_relation.template get_inverse_polynomial(polynomials);
    for (size_t i = 0; i < circuit_size; ++i) {
        auto row = polynomials.get_row(i);
        bool has_inverse = lookup_relation.operation_exists_at_row(row);
        if (!has_inverse) {
            continue;
        }
        FF denominator = 1;
        barretenberg::constexpr_for<0, READ_TERMS, 1>([&]<size_t read_index> {
            auto denominator_term =
                lookup_relation.template compute_read_term<Accumulator, read_index>(row, relation_parameters);
            denominator *= denominator_term;
        });
        barretenberg::constexpr_for<0, WRITE_TERMS, 1>([&]<size_t write_index> {
            auto denominator_term =
                lookup_relation.template compute_write_term<Accumulator, write_index>(row, relation_parameters);
            denominator *= denominator_term;
        });
        inverse_polynomial[i] = denominator;
    };
 
    // todo might be inverting zero in field bleh bleh
    FF::batch_invert(inverse_polynomial);
}
 
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;
 
    auto lookup_relation = Relation();
 
    using Accumulator = typename std::tuple_element_t<0, ContainerOverSubrelations>;
    using View = typename Accumulator::View;
 
    auto lookup_inverses = View(lookup_relation.template 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])
    barretenberg::constexpr_for<0, READ_TERMS, 1>(
        [&]<size_t i>() { lookup_terms[i] = lookup_relation.template compute_read_term<Accumulator, i>(in, params); });
    barretenberg::constexpr_for<0, WRITE_TERMS, 1>([&]<size_t i>() {
        lookup_terms[i + READ_TERMS] = lookup_relation.template compute_write_term<Accumulator, i>(in, params);
    });
 
    barretenberg::constexpr_for<0, NUM_TOTAL_TERMS, 1>(
        [&]<size_t i>() { denominator_accumulator[i] = lookup_terms[i]; });
 
    barretenberg::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 = lookup_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
    barretenberg::constexpr_for<0, READ_TERMS, 1>([&]<size_t i>() {
        std::get<1>(accumulator) +=
            lookup_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
    barretenberg::constexpr_for<0, WRITE_TERMS, 1>([&]<size_t i>() {
        const auto p = lookup_relation.template compute_write_term_predicate<Accumulator, i>(in);
        const auto lookup_read_count = lookup_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);
 
    auto permutation_relation = Relation();
 
    using Accumulator = typename std::tuple_element_t<0, ContainerOverSubrelations>;
    using View = typename Accumulator::View;
 
    auto permutation_inverses = View(permutation_relation.template 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] = permutation_relation.template compute_read_term<Accumulator, 0>(in, params);
    permutation_terms[1] = permutation_relation.template compute_write_term<Accumulator, 0>(in, params);
 
    barretenberg::constexpr_for<0, NUM_TOTAL_TERMS, 1>(
        [&]<size_t i>() { denominator_accumulator[i] = permutation_terms[i]; });
 
    barretenberg::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 = permutation_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) +=
        permutation_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) -=
        permutation_relation.template compute_write_term_predicate<Accumulator, 0>(in) * denominator_accumulator[1];
}
} // namespace proof_system::honk::logderivative_library