scalar_multiplication_fast.hpp

Go to the documentation of this file.

#pragma once
 
#include "barretenberg/common/thread.hpp"
#include "barretenberg/ecc/curves/bn254/bn254.hpp"
#include "barretenberg/ecc/curves/grumpkin/grumpkin.hpp"
#include "barretenberg/polynomials/polynomial.hpp"
#include <string>
 
#include <atomic>
#include <cstddef>
#include <cstdint>
#include <span>
#include <vector>
 
namespace bb::scalar_multiplication {
 
size_t window_bits_tuning_oversub_factor(size_t n_input);
 
// `external_glv_doubled`: optional caller-supplied [P, φP, ...] interleaved buffer
//   (length 2*n). When non-empty, every n_input is treated as GLV-eligible and the
//   doubled points are aliased instead of recomputed — the batched driver uses this
//   to share the doubled SRS prefix across MSMs in a batch.
// `external_arena`: optional caller-supplied scratch buffer ≥ this MSM_fast's required
//   bytes. When empty, allocated per-MSM_fast and freed at return. The batched driver
//   supplies a single arena sized to the largest member.
// `dedup_info`: MSM dedup pre-pass hint — 0 = off, 1 = hinted (no estimate), >=2 = a caller-measured
//   duplicate count used to discount the window-selection point count.
template <typename Curve>
typename Curve::Element pippenger_round_parallel(
    PolynomialSpan<const typename Curve::ScalarField> scalars,
    std::span<const typename Curve::AffineElement> points,
    size_t dedup_info = 0,
    std::span<const typename Curve::AffineElement> external_glv_doubled = {},
    std::span<std::byte> external_arena = {},
    size_t max_threads = 0) noexcept;
 
extern template curve::BN254::Element pippenger_round_parallel<curve::BN254>(
    PolynomialSpan<const curve::BN254::ScalarField> scalars,
    std::span<const curve::BN254::AffineElement> points,
    size_t dedup_info,
    std::span<const curve::BN254::AffineElement> external_glv_doubled,
    std::span<std::byte> external_arena,
    size_t max_threads) noexcept;
 
extern template curve::Grumpkin::Element pippenger_round_parallel<curve::Grumpkin>(
    PolynomialSpan<const curve::Grumpkin::ScalarField> scalars,
    std::span<const curve::Grumpkin::AffineElement> points,
    size_t dedup_info,
    std::span<const curve::Grumpkin::AffineElement> external_glv_doubled,
    std::span<std::byte> external_arena,
    size_t max_threads) noexcept;
 
// ===================================================================================
// Public API (interface-compatible with the legacy `scalar_multiplication::MSM_fast` class).
// ===================================================================================
//
// `pippenger_fast`        — handle_edge_cases routed: false → fast affine round-parallel,
//                      true → Jacobian fast path (handles point-at-infinity / equal-x
//                      bucket collisions).
// `pippenger_unsafe_fast` — always the fast path; caller asserts linear-independence of points.
// `MSM_fast<Curve>::msm`            — single-MSM_fast convenience wrapper (returns AffineElement).
// `MSM_fast<Curve>::batch_multi_scalar_mul` — multi-MSM_fast driver: runs each MSM_fast via `pippenger_fast`
//                                       and returns a vector of AffineElement results.
 
template <typename Curve>
typename Curve::Element pippenger_fast(PolynomialSpan<const typename Curve::ScalarField> scalars,
                                       std::span<const typename Curve::AffineElement> points,
                                       bool handle_edge_cases = true,
                                       size_t dedup_info = 0) noexcept;
 
template <typename Curve>
typename Curve::Element pippenger_unsafe_fast(PolynomialSpan<const typename Curve::ScalarField> scalars,
                                              std::span<const typename Curve::AffineElement> points,
                                              size_t dedup_info = 0) noexcept;
 
extern template curve::BN254::Element pippenger_fast<curve::BN254>(
    PolynomialSpan<const curve::BN254::ScalarField> scalars,
    std::span<const curve::BN254::AffineElement> points,
    bool handle_edge_cases,
    size_t dedup_info) noexcept;
 
extern template curve::Grumpkin::Element pippenger_fast<curve::Grumpkin>(
    PolynomialSpan<const curve::Grumpkin::ScalarField> scalars,
    std::span<const curve::Grumpkin::AffineElement> points,
    bool handle_edge_cases,
    size_t dedup_info) noexcept;
 
extern template curve::BN254::Element pippenger_unsafe_fast<curve::BN254>(
    PolynomialSpan<const curve::BN254::ScalarField> scalars,
    std::span<const curve::BN254::AffineElement> points,
    size_t dedup_info) noexcept;
 
extern template curve::Grumpkin::Element pippenger_unsafe_fast<curve::Grumpkin>(
    PolynomialSpan<const curve::Grumpkin::ScalarField> scalars,
    std::span<const curve::Grumpkin::AffineElement> points,
    size_t dedup_info) noexcept;
 
template <typename Curve> class MSM_fast {
  public:
    using Element = typename Curve::Element;
    using ScalarField = typename Curve::ScalarField;
    using AffineElement = typename Curve::AffineElement;
 
    static AffineElement msm(std::span<const AffineElement> points,
                             PolynomialSpan<const ScalarField> scalars,
                             bool handle_edge_cases = false,
                             size_t dedup_info = 0) noexcept;
 
    static std::vector<AffineElement> batch_multi_scalar_mul(std::span<const AffineElement> points,
                                                             std::span<PolynomialSpan<ScalarField>> scalars,
                                                             bool handle_edge_cases = true,
                                                             std::span<const uint32_t> dedup_infos = {}) noexcept;
};
 
extern template class MSM_fast<curve::Grumpkin>;
extern template class MSM_fast<curve::BN254>;
 
// `pippenger_round_parallel` falls back to `trivial_msm_threaded` when each worker
// would receive fewer than this many points (after the n_active filter). Exposed so tests
// and bench targets can pin behaviour at the boundary.
inline constexpr size_t MIN_PTS_PER_THREAD_FOR_PIPPENGER = 24;
 
// Points-per-worker floor below which intra-MSM multithreading loses to its parallel_for barrier
// overhead. Drives both the worker-count pick in pippenger_round_parallel and the batch driver's
// concurrent/sequential split. SIZE_MAX forces single-threaded on wasm.
#ifdef __wasm__
inline constexpr size_t MSM_MIN_PTS_PER_THREAD = SIZE_MAX;
#else
inline constexpr size_t MSM_MIN_PTS_PER_THREAD = 256;
#endif
 
// Point-count bound for the batch driver's concurrent/sequential split on wasm. Intra-MSM work is
// always single-threaded on wasm (MSM_MIN_PTS_PER_THREAD == SIZE_MAX), so the native split rule
// `n < MSM_MIN_PTS_PER_THREAD * pool_width` would classify every member as small and route them all
// through the concurrent pool, whose per-worker arena is sized to the largest member and caps the
// worker count by memory budget. This finite bound keeps large members on the sequential shared-arena
// path so the concurrent pool retains full worker width. Members at or below it dispatch one-per-worker.
inline constexpr size_t SMALL_MSM_BATCH_THRESHOLD = size_t{ 1 } << 13;
 
// Per-MSM_fast arena sizer. Returns 0 for shapes that fall back to the Jacobian-fast path
// (no affine arena). Mirrors the inline budget calc inside `pippenger_round_parallel`;
// declared here so the test suite can exercise the same sizer.
template <typename Curve>
size_t compute_arena_bytes_for_msm(size_t n_input,
                                   bool external_glv_provided,
                                   bool dedup_active = false,
                                   size_t max_threads = 0) noexcept;
 
namespace round_parallel_detail {
 
// Above this N, GLV's 2x point-count cost outweighs the windows-halved benefit.
#ifdef __wasm__
inline constexpr size_t GLV_SMALL_N_THRESHOLD = size_t{ 1 } << 16;
#else
inline constexpr size_t GLV_SMALL_N_THRESHOLD = size_t{ 1 } << 13;
#endif
 
template <typename Curve>
typename Curve::Element pippenger_round_parallel_jacobian_fast(std::span<const typename Curve::ScalarField> scalars,
                                                               std::span<const typename Curve::AffineElement> points,
                                                               size_t min_pts_per_thread_override = 0,
                                                               size_t max_threads = 0) noexcept;
 
extern template curve::BN254::Element pippenger_round_parallel_jacobian_fast<curve::BN254>(
    std::span<const curve::BN254::ScalarField> scalars,
    std::span<const curve::BN254::AffineElement> points,
    size_t min_pts_per_thread_override,
    size_t max_threads) noexcept;
 
extern template curve::Grumpkin::Element pippenger_round_parallel_jacobian_fast<curve::Grumpkin>(
    std::span<const curve::Grumpkin::ScalarField> scalars,
    std::span<const curve::Grumpkin::AffineElement> points,
    size_t min_pts_per_thread_override,
    size_t max_threads) noexcept;
 
} // namespace round_parallel_detail
 
template <typename Curve>
typename Curve::Element trivial_msm(PolynomialSpan<const typename Curve::ScalarField> scalars_span,
                                    std::span<const typename Curve::AffineElement> all_points) noexcept;
 
extern template curve::BN254::Element trivial_msm<curve::BN254>(
    PolynomialSpan<const curve::BN254::ScalarField> scalars_span,
    std::span<const curve::BN254::AffineElement> all_points) noexcept;
 
extern template curve::Grumpkin::Element trivial_msm<curve::Grumpkin>(
    PolynomialSpan<const curve::Grumpkin::ScalarField> scalars_span,
    std::span<const curve::Grumpkin::AffineElement> all_points) noexcept;
 
template <typename Curve>
typename Curve::Element trivial_msm_threaded(PolynomialSpan<const typename Curve::ScalarField> scalars_span,
                                             std::span<const typename Curve::AffineElement> all_points,
                                             size_t max_threads = 0) noexcept;
 
extern template curve::BN254::Element trivial_msm_threaded<curve::BN254>(
    PolynomialSpan<const curve::BN254::ScalarField> scalars_span,
    std::span<const curve::BN254::AffineElement> all_points,
    size_t max_threads) noexcept;
 
extern template curve::Grumpkin::Element trivial_msm_threaded<curve::Grumpkin>(
    PolynomialSpan<const curve::Grumpkin::ScalarField> scalars_span,
    std::span<const curve::Grumpkin::AffineElement> all_points,
    size_t max_threads) noexcept;
 
} // namespace bb::scalar_multiplication