databus_lookup_relation.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 <array>
#include <tuple>
 
#include "barretenberg/common/constexpr_utils.hpp"
#include "barretenberg/common/thread.hpp"
#include "barretenberg/polynomials/univariate.hpp"
#include "barretenberg/relations/relation_types.hpp"
 
namespace bb {
 
template <typename FF_> class DatabusLookupRelationImpl {
  public:
    using FF = FF_;
    static constexpr size_t NUM_BUS_COLUMNS = 3; // calldata, return data
    // the actual degree of this subrelation is 3, and requires a degree adjustment of 1.
    // however as we reuse the accumulators used to compute this subrelation for the lookup subrelation, we set the
    // degree to 4 which removes the need of having degree adjustments for folding.
    static constexpr size_t INVERSE_SUBREL_LENGTH = 5; // deg + 1 of inverse correctness subrelation
    static constexpr size_t INVERSE_SUBREL_LENGTH_ADJUSTMENT = 0;
    // the max degree of this subrelation is 4
    static constexpr size_t LOOKUP_SUBREL_LENGTH = 5; // deg + 1 of log-deriv lookup subrelation
    static constexpr size_t LOOKUP_SUBREL_LENGTH_ADJUSTMENT = 0;
    static constexpr size_t READ_TAG_BOOLEAN_CHECK_SUBREL_LENGTH =
        3; // deg + 1 of the relation checking that read_tag_m is a boolean value
    static constexpr size_t READ_TAG_BOOLEAN_CHECK_SUBREL_LENGTH_ADJUSTMENT = 0;
    static constexpr size_t NUM_SUB_RELATION_PER_IDX = 3; // the number of subrelations per bus column
 
    static constexpr std::array<size_t, NUM_SUB_RELATION_PER_IDX * NUM_BUS_COLUMNS> SUBRELATION_PARTIAL_LENGTHS{
        INVERSE_SUBREL_LENGTH,                // inverse polynomial correctness subrelation (bus_idx 0)
        LOOKUP_SUBREL_LENGTH,                 // log-derivative lookup argument subrelation (bus_idx 0)
        READ_TAG_BOOLEAN_CHECK_SUBREL_LENGTH, // read_tag_m* read_tag_m - read_tag_m (bus_idx 0)
        INVERSE_SUBREL_LENGTH,                // inverse polynomial correctness subrelation (bus_idx 1)
        LOOKUP_SUBREL_LENGTH,                 // log-derivative lookup argument subrelation (bus_idx 1)
        READ_TAG_BOOLEAN_CHECK_SUBREL_LENGTH, // read_tag_m* read_tag_m - read_tag_m (bus_idx 1)
        INVERSE_SUBREL_LENGTH,                // inverse polynomial correctness subrelation (bus_idx 2)
        LOOKUP_SUBREL_LENGTH,                 // log-derivative lookup argument subrelation (bus_idx 2)
        READ_TAG_BOOLEAN_CHECK_SUBREL_LENGTH, // read_tag_m* read_tag_m - read_tag_m (bus_idx 2)
    };
 
    static constexpr bool INVERSE_SUBREL_LIN_INDEPENDENT = true;         // to be satisfied independently at each row
    static constexpr bool LOOKUP_SUBREL_LIN_INDEPENDENT = false;         // to be satisfied as a sum across all rows
    static constexpr bool READ_TAG_BOOLEAN_CHECK_LIN_INDEPENDENT = true; // to be satisfied independently at each row
 
    // The lookup subrelations are "linearly dependent" in the sense that they establish the value of a sum across the
    // entire execution trace rather than a per-row identity.
    static constexpr std::array<bool, NUM_SUB_RELATION_PER_IDX * NUM_BUS_COLUMNS> SUBRELATION_LINEARLY_INDEPENDENT = {
        INVERSE_SUBREL_LIN_INDEPENDENT, LOOKUP_SUBREL_LIN_INDEPENDENT, READ_TAG_BOOLEAN_CHECK_LIN_INDEPENDENT,
        INVERSE_SUBREL_LIN_INDEPENDENT, LOOKUP_SUBREL_LIN_INDEPENDENT, READ_TAG_BOOLEAN_CHECK_LIN_INDEPENDENT,
        INVERSE_SUBREL_LIN_INDEPENDENT, LOOKUP_SUBREL_LIN_INDEPENDENT, READ_TAG_BOOLEAN_CHECK_LIN_INDEPENDENT
    };
 
    template <typename AllEntities> inline static bool skip([[maybe_unused]] const AllEntities& in)
    {
        // Ensure the input does not contain a read gate or data that is being read
        return in.q_busread.is_zero() && in.calldata_read_counts.is_zero() &&
               in.secondary_calldata_read_counts.is_zero() && in.return_data_read_counts.is_zero();
    }
 
    // Interface for easy access of databus components by column (bus_idx)
    template <size_t bus_idx, typename AllEntities> struct BusData;
 
    // Specialization for calldata (bus_idx = 0)
    template <typename AllEntities> struct BusData</*bus_idx=*/0, AllEntities> {
        static auto& values(const AllEntities& in) { return in.calldata; }
        static auto& selector(const AllEntities& in) { return in.q_l; }
        static auto& inverses(AllEntities& in) { return in.calldata_inverses; }
        static auto& inverses(const AllEntities& in) { return in.calldata_inverses; } // const version
        static auto& read_counts(const AllEntities& in) { return in.calldata_read_counts; }
        static auto& read_tags(const AllEntities& in) { return in.calldata_read_tags; }
    };
 
    // Specialization for secondary_calldata (bus_idx = 1)
    template <typename AllEntities> struct BusData</*bus_idx=*/1, AllEntities> {
        static auto& values(const AllEntities& in) { return in.secondary_calldata; }
        static auto& selector(const AllEntities& in) { return in.q_r; }
        static auto& inverses(AllEntities& in) { return in.secondary_calldata_inverses; }
        static auto& inverses(const AllEntities& in) { return in.secondary_calldata_inverses; } // const version
        static auto& read_counts(const AllEntities& in) { return in.secondary_calldata_read_counts; }
        static auto& read_tags(const AllEntities& in) { return in.secondary_calldata_read_tags; }
    };
 
    // Specialization for return data (bus_idx = 2)
    template <typename AllEntities> struct BusData</*bus_idx=*/2, AllEntities> {
        static auto& values(const AllEntities& in) { return in.return_data; }
        static auto& selector(const AllEntities& in) { return in.q_o; }
        static auto& inverses(AllEntities& in) { return in.return_data_inverses; }
        static auto& inverses(const AllEntities& in) { return in.return_data_inverses; } // const version
        static auto& read_counts(const AllEntities& in) { return in.return_data_read_counts; }
        static auto& read_tags(const AllEntities& in) { return in.return_data_read_tags; }
    };
 
    template <size_t bus_idx, typename AllValues> static bool operation_exists_at_row(const AllValues& row)
    {
        auto read_selector = get_read_selector<FF, bus_idx>(row);
        auto read_tag = BusData<bus_idx, AllValues>::read_tags(row);
        return (read_selector == 1 || read_tag == 1);
    }
 
    template <typename Accumulator, size_t bus_idx, typename AllEntities>
    static Accumulator compute_inverse_exists(const AllEntities& in)
    {
        using CoefficientAccumulator = typename Accumulator::CoefficientAccumulator;
 
        const auto is_read_gate = get_read_selector<Accumulator, bus_idx>(in); // is this a read gate
        const auto read_tag_m =
            CoefficientAccumulator(BusData<bus_idx, AllEntities>::read_tags(in)); // does row contain data being read
        const Accumulator read_tag(read_tag_m);
        // Relation checking: is_read_gate == 1 || read_tag == 1
        // Important note: the relation written below assumes that is_read_gate and read_tag are boolean values, which
        // is guaranteed by the boolean_check subrelation. If not, fixing one of the two, the return value is a linear
        // function in the other variable and can be set to an arbitrary value independent of the fixed value. See the
        // boolean_check subrelation for more explanation.
        //         degree 2(2)   1             2 (2)        1       // Degree 3 (3)
        return is_read_gate + read_tag - (is_read_gate * read_tag); // Degree 3 (5)
    }
 
    template <typename Accumulator, size_t bus_idx, typename AllEntities>
    static Accumulator get_read_selector(const AllEntities& in)
    {
        using CoefficientAccumulator = typename Accumulator::CoefficientAccumulator;
 
        auto q_busread = CoefficientAccumulator(in.q_busread);
        auto column_selector = CoefficientAccumulator(BusData<bus_idx, AllEntities>::selector(in));
 
        //          degree    1                1           2 (2)
        return Accumulator(q_busread * column_selector);
    }
 
    template <typename Accumulator, size_t bus_idx, typename AllEntities, typename Parameters>
    static Accumulator compute_write_term(const AllEntities& in, const Parameters& params)
    {
        using CoefficientAccumulator = typename Accumulator::CoefficientAccumulator;
        using ParameterCoefficientAccumulator = typename Parameters::DataType::CoefficientAccumulator;
 
        const auto& id = CoefficientAccumulator(in.databus_id);
        const auto& value = CoefficientAccumulator(BusData<bus_idx, AllEntities>::values(in));
        const auto& gamma = ParameterCoefficientAccumulator(params.gamma);
        const auto& beta = ParameterCoefficientAccumulator(params.beta);
 
        // Construct value_i + idx_i*\beta + \gamma
        // degrees         1(0) 0(1)  1(1)       0(1)
        return Accumulator(id * beta + value + gamma); // degree 1 (1)
    }
 
    template <typename Accumulator, typename AllEntities, typename Parameters>
    static Accumulator compute_read_term(const AllEntities& in, const Parameters& params)
    {
        using CoefficientAccumulator = typename Accumulator::CoefficientAccumulator;
        using ParameterCoefficientAccumulator = typename Parameters::DataType::CoefficientAccumulator;
 
        // Bus value stored in w_1, index into bus column stored in w_2
        const auto& w_1 = CoefficientAccumulator(in.w_l);
        const auto& w_2 = CoefficientAccumulator(in.w_r);
        const auto& gamma = ParameterCoefficientAccumulator(params.gamma);
        const auto& beta = ParameterCoefficientAccumulator(params.beta);
 
        // Construct value + index*\beta + \gamma
        return Accumulator((w_2 * beta) + w_1 + gamma); // degree 1 (2)
    }
 
    template <size_t bus_idx, typename Polynomials>
    static void compute_logderivative_inverse(Polynomials& polynomials,
                                              auto& relation_parameters,
                                              const size_t circuit_size)
    {
        BB_BENCH_NAME("Databus::compute_logderivative_inverse");
        auto& inverse_polynomial = BusData<bus_idx, Polynomials>::inverses(polynomials);
 
        size_t min_iterations_per_thread = 1 << 6; // min number of iterations for which we'll spin up a unique thread
        size_t num_threads = bb::calculate_num_threads_pow2(circuit_size, min_iterations_per_thread);
        size_t iterations_per_thread = circuit_size / num_threads; // actual iterations per thread
 
        parallel_for(num_threads, [&](size_t thread_idx) {
            size_t start = thread_idx * iterations_per_thread;
            size_t end = (thread_idx + 1) * iterations_per_thread;
            bool is_read = false;
            bool nonzero_read_count = false;
            for (size_t i = start; i < end; ++i) {
                // Determine if the present row contains a databus operation
                auto q_busread = polynomials.q_busread[i];
                if constexpr (bus_idx == 0) { // calldata
                    is_read = q_busread == 1 && polynomials.q_l[i] == 1;
                    nonzero_read_count = polynomials.calldata_read_counts[i] > 0;
                }
                if constexpr (bus_idx == 1) { // secondary_calldata
                    is_read = q_busread == 1 && polynomials.q_r[i] == 1;
                    nonzero_read_count = polynomials.secondary_calldata_read_counts[i] > 0;
                }
                if constexpr (bus_idx == 2) { // return data
                    is_read = q_busread == 1 && polynomials.q_o[i] == 1;
                    nonzero_read_count = polynomials.return_data_read_counts[i] > 0;
                }
                // We only compute the inverse if this row contains a read gate or data that has been read
                if (is_read || nonzero_read_count) {
                    // TODO(https://github.com/AztecProtocol/barretenberg/issues/940): avoid get_row if possible.
                    auto row = polynomials.get_row(i); // Note: this is a copy. use sparingly!
                    auto value = compute_read_term<FF>(row, relation_parameters) *
                                 compute_write_term<FF, bus_idx>(row, relation_parameters);
                    inverse_polynomial.at(i) = value;
                }
            }
        });
 
        // 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(inverse_polynomial.coeffs());
    };
 
    template <typename FF,
              size_t bus_idx,
              typename ContainerOverSubrelations,
              typename AllEntities,
              typename Parameters>
    static void accumulate_subrelation_contributions(ContainerOverSubrelations& accumulator,
                                                     const AllEntities& in,
                                                     const Parameters& params,
                                                     const FF& scaling_factor)
    {
        using Accumulator = typename std::tuple_element_t<4, ContainerOverSubrelations>;
        using CoefficientAccumulator = typename Accumulator::CoefficientAccumulator;
        using ShortAccumulator = std::tuple_element_t<2, ContainerOverSubrelations>;
        const auto inverses_m = CoefficientAccumulator(BusData<bus_idx, AllEntities>::inverses(in)); // Degree 1
        Accumulator inverses(inverses_m);
        const auto read_counts_m = CoefficientAccumulator(BusData<bus_idx, AllEntities>::read_counts(in)); // Degree 1
        const auto read_term = compute_read_term<Accumulator>(in, params);                                 // Degree 1
        const auto write_term = compute_write_term<Accumulator, bus_idx>(in, params);                      // Degree 1
        const auto inverse_exists = compute_inverse_exists<Accumulator, bus_idx>(in);                      // Degree 3
        const auto read_selector = get_read_selector<Accumulator, bus_idx>(in);                            // Degree 2
 
        // Determine which pair of subrelations to update based on which bus column is being read
        // The inverse relation subrelation index
        constexpr size_t subrel_idx_1 = NUM_SUB_RELATION_PER_IDX * bus_idx;
        // The lookup relation subrelation index
        constexpr size_t subrel_idx_2 = NUM_SUB_RELATION_PER_IDX * bus_idx + 1;
        // The read_tag boolean check subrelation index
        constexpr size_t subrel_idx_3 = NUM_SUB_RELATION_PER_IDX * bus_idx + 2;
 
        // Establish the correctness of the polynomial of inverses I. Note: inverses is computed so that the value
        // is 0 if !inverse_exists. Degree 3
        // degrees            3    =              1           1              1           3
        std::get<subrel_idx_1>(accumulator) += (read_term * write_term * inverses - inverse_exists) * scaling_factor;
 
        // Establish validity of the read. Note: no scaling factor here since this constraint is enforced across the
        // entire trace, not on a per-row basis.
 
        // degree  3   =         2          1
        Accumulator tmp = read_selector * write_term;
        // degree 2 =             1           1
        tmp -= Accumulator(read_counts_m) * read_term;
        // degree 1
        tmp *= inverses;
        std::get<subrel_idx_2>(accumulator) += tmp; // Deg 4 (4)
 
        const auto read_tag_m = CoefficientAccumulator(BusData<bus_idx, AllEntities>::read_tags(in));
        const auto read_tag = ShortAccumulator(read_tag_m);
        // // this is done by row so we have to multiply by the scaling factor
        // degree                                    1        1            1      =      2
        std::get<subrel_idx_3>(accumulator) += (read_tag * read_tag - read_tag) * scaling_factor;
    }
 
    template <typename ContainerOverSubrelations, typename AllEntities, typename Parameters>
    static void accumulate(ContainerOverSubrelations& accumulator,
                           const AllEntities& in,
                           const Parameters& params,
                           const FF& scaling_factor)
    {
        // Accumulate the subrelation contributions for each column of the databus
        bb::constexpr_for<0, NUM_BUS_COLUMNS, 1>([&]<size_t bus_idx>() {
            accumulate_subrelation_contributions<FF, bus_idx>(accumulator, in, params, scaling_factor);
        });
    }
};
 
template <typename FF> using DatabusLookupRelation = Relation<DatabusLookupRelationImpl<FF>>;
 
} // namespace bb