databus_lookup_relation.hpp

Go to the documentation of this file.

// === AUDIT STATUS ===
// internal:    { status: Complete, auditors: [Sergei], commit: }
// external_1:  { status: not started, auditors: [], commit: }
// external_2:  { status: not started, auditors: [], commit: }
// =====================
 
#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"
#include "barretenberg/stdlib_circuit_builders/databus.hpp"
 
namespace bb {
 
template <typename FF_> class DatabusLookupRelationImpl {
  public:
    using FF = FF_;
 
    // Note: All three subrelations use length 6 to make efficient use of shared computation. Shortening (1b)/(2) to
    // length 5 forces the shared factors (lookup_term, table_term, read_selector, inverses, `I*L*T - 1`) to be
    // recomputed and is a net loss in performance.
    static constexpr size_t INVERSE_READ_SUBREL_LENGTH = 6;  // deg 5: (I*L*T - 1) * is_read
    static constexpr size_t INVERSE_WRITE_SUBREL_LENGTH = 6; // deg 4: (I*L*T - 1) * count
    static constexpr size_t LOOKUP_SUBREL_LENGTH = 6;        // deg 4: (is_read*T - count*L) * I
    static constexpr size_t NUM_SUB_RELATION_PER_IDX = 3;    // the number of subrelations per bus column
 
    // Per-bus subrelation layout: (1a) inverse-on-read, (1b) inverse-on-write, (2) lookup identity.
    // The whole-relation arrays below repeat this layout once per bus column.
    static constexpr std::array<size_t, NUM_SUB_RELATION_PER_IDX> PER_BUS_SUBREL_LENGTHS{
        INVERSE_READ_SUBREL_LENGTH,
        INVERSE_WRITE_SUBREL_LENGTH,
        LOOKUP_SUBREL_LENGTH,
    };
    // (1a) and (1b) are per-row identities; (2) is a sum across the trace.
    static constexpr std::array<bool, NUM_SUB_RELATION_PER_IDX> PER_BUS_LIN_INDEPENDENT{ true, true, false };
 
    template <typename T, size_t N>
    static constexpr std::array<T, N * NUM_BUS_COLUMNS> repeat_per_bus(const std::array<T, N>& pattern)
    {
        std::array<T, N * NUM_BUS_COLUMNS> out{};
        for (size_t bus = 0; bus < NUM_BUS_COLUMNS; ++bus) {
            for (size_t i = 0; i < N; ++i) {
                out[(bus * N) + i] = pattern[i];
            }
        }
        return out;
    }
 
    static constexpr std::array<size_t, NUM_SUB_RELATION_PER_IDX * NUM_BUS_COLUMNS> SUBRELATION_PARTIAL_LENGTHS =
        repeat_per_bus(PER_BUS_SUBREL_LENGTHS);
    static constexpr std::array<bool, NUM_SUB_RELATION_PER_IDX * NUM_BUS_COLUMNS> SUBRELATION_LINEARLY_INDEPENDENT =
        repeat_per_bus(PER_BUS_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
        if (!in.q_busread.is_zero()) {
            return false;
        }
        bool all_counts_zero = true;
        bb::constexpr_for<0, NUM_BUS_COLUMNS, 1>(
            [&]<size_t bus_idx>() { all_counts_zero &= BusData<bus_idx, AllEntities>::read_counts(in).is_zero(); });
        return all_counts_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; }
    };
 
    // 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; }
    };
 
    // 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; }
    };
 
    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_table_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_lookup_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,
                                              const size_t start_index = 0)
    {
        BB_BENCH_NAME("Databus::compute_logderivative_inverse");
        auto& inverse_polynomial = BusData<bus_idx, Polynomials>::inverses(polynomials);
        const auto& column_selector = BusData<bus_idx, Polynomials>::selector(polynomials);
        const auto& read_counts = BusData<bus_idx, Polynomials>::read_counts(polynomials);
 
        const size_t num_rows = circuit_size - start_index;
        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(num_rows, min_iterations_per_thread);
 
        parallel_for(num_threads, [&](ThreadChunk chunk) {
            BB_BENCH_TRACY_NAME("Databus::compute_inverses/chunk");
            for (size_t j : chunk.range(num_rows)) {
                size_t i = j + start_index;
                // Determine if the present row contains a databus operation
                const bool is_read = polynomials.q_busread[i] == 1 && column_selector[i] == 1;
                const bool nonzero_read_count = 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_lookup_term<FF>(row, relation_parameters) *
                                 compute_table_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)
    {
        // Subrelation indices for this bus column
        constexpr size_t subrel_idx_inv_read = NUM_SUB_RELATION_PER_IDX * bus_idx;      // (1a)
        constexpr size_t subrel_idx_inv_write = NUM_SUB_RELATION_PER_IDX * bus_idx + 1; // (1b)
        constexpr size_t subrel_idx_lookup = NUM_SUB_RELATION_PER_IDX * bus_idx + 2;    // (2)
 
        using Accumulator = typename std::tuple_element_t<subrel_idx_inv_read, ContainerOverSubrelations>;
        using CoefficientAccumulator = typename Accumulator::CoefficientAccumulator;
 
        const auto inverses_m = CoefficientAccumulator(BusData<bus_idx, AllEntities>::inverses(in));
        const auto read_counts_m = CoefficientAccumulator(BusData<bus_idx, AllEntities>::read_counts(in));
 
        const Accumulator inverses(inverses_m);
        const Accumulator read_counts(read_counts_m);
        const auto lookup_term = compute_lookup_term<Accumulator>(in, params);
        const auto table_term = compute_table_term<Accumulator, bus_idx>(in, params);
        const auto read_selector = get_read_selector<Accumulator, bus_idx>(in);
 
        // Shared factor in (1a) and (1b): I*L*T - 1
        const auto common = lookup_term * table_term * inverses - FF(1);
 
        // (1a) Inverse correctness on read rows: (I*L*T - 1) * is_read = 0
        std::get<subrel_idx_inv_read>(accumulator) += (common * read_selector) * scaling_factor;
 
        // (1b) Inverse correctness on write rows: (I*L*T - 1) * count = 0
        std::get<subrel_idx_inv_write>(accumulator) += (common * read_counts) * scaling_factor;
 
        // (2) Lookup identity: (is_read*T - count*L) * I = 0.
        // No scaling factor here since this constraint is enforced across the entire trace, not per-row.
        Accumulator tmp = read_selector * table_term;
        tmp -= read_counts * lookup_term;
        tmp *= inverses;
        std::get<subrel_idx_lookup>(accumulator) += tmp;
    }
 
    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