//! Variable-time multi-scalar multiplication for batch signature verification. //! //! [`Term`]s arrive decompressed and recoded into signed digits. Small batches use Straus's //! method, whose only per-window fixed cost is the shared doublings, and a parallel run splits //! their terms across workers. Larger batches use Pippenger's bucket method: the kernel processes //! one term per private bucket stripe at once, so updates within each wave never collide. //! //! Bucket multiplication runs on strategy-supplied `(window, term range)` tiles. The strategy //! cuts a window into term ranges only where the extra tile's fold pays for itself. Each worker //! reuses private bucket scratch across its tiles. Tiles of the same window are added together, //! and one short Horner fold positions the window sums. use super::scalar::Scalar; use crate::curve::{G, GAffine, LANES, msm::Backend}; #[cfg(not(feature = "std"))] use alloc::vec::Vec; use commonware_parallel::{Grid, Sequential, Strategy}; use commonware_utils::NZUsize; use core::num::NonZeroUsize; /// Bounds on the per-batch window width [`width_for`] may pick. The lower bound sizes every /// term's digit array ([`MAX_WINDOWS`]); the upper bound caps each tile's bucket-array footprint. const MIN_WIDTH: u32 = 6; const MAX_WIDTH: u32 = 10; /// Digit capacity per [`Term`]: enough windows for the narrowest width. Recoding at a wider /// width simply leaves the top entries zero (see [`Scalar::signed_digits`]). const MAX_WINDOWS: usize = 256usize.div_ceil(MIN_WIDTH as usize); /// `256` scalar bits divided into `width`-bit windows, rounding up. Recoding into *signed* digits /// (see [`Scalar::signed_digits`]) can carry a final `+1` out of the top window, but a [`Scalar`] /// is always below `L < 2^253`, which leaves the top window room to absorb that carry at every /// width from [`MIN_WIDTH`] to [`MAX_WIDTH`]. const fn num_windows(width: u32) -> usize { 256usize.div_ceil(width as usize) } /// One bucket per nonzero digit *magnitude*: a signed digit only ever needs a bucket for /// `abs(digit)`, which ranges `1..=2^(width-1)`, half as many buckets as the `1..2^width` an /// unsigned digit would need (see [`Scalar::signed_digits`]). const fn num_buckets(width: u32) -> usize { 1usize << (width - 1) } /// Picks the window width for a batch of `terms` MSM terms, run in parallel or serially: wider /// windows mean fewer bucket-fill passes over the terms (the input-proportional cost) but a /// bigger bucket array for every fill/fold instance to initialize, fold, and keep cache-resident. /// /// The width grows by half a bit per bit of batch size, more slowly than the textbook /// `log2(terms) - 4` rule, because a wide bucket array (`8 * 2^(width-1)` points on AVX-512) /// also costs L2 misses, not just fold arithmetic. A parallel run picks the width a serial run /// would pick for half as many terms, capped one below [`MAX_WIDTH`]: every worker holds its own /// bucket array, and a window cut into several tiles is folded once per tile. pub(super) fn width_for(terms: usize, parallel: bool) -> u32 { let bits = terms.max(2).ilog2(); if parallel { ((bits + 3) / 2).clamp(MIN_WIDTH, MAX_WIDTH - 1) } else { ((bits + 4) / 2).clamp(MIN_WIDTH, MAX_WIDTH) } } /// One MSM term: a decompressed, mixed-addition-prepared point together with its scalar's signed /// digits. The digits are recoded before the MSM, which then reads them once per window. Digits /// are stored as `i16` (ample for any width up to 16) to keep the per-term footprint, and /// therefore each pass's memory traffic, small; entries above the chosen width's window count /// stay zero. #[derive(Clone, Copy)] pub(super) struct Term { point: GAffine, digits: [i16; MAX_WINDOWS], } impl Term { /// Recodes `scalar` at `width` (the batch-wide value from [`width_for`]; every term of one /// MSM must use the same width). pub(super) fn new(point: GAffine, scalar: &Scalar, width: u32) -> Self { let mut term = Self::zero(point); term.recode(scalar, width); term } /// A term for `point` with scalar zero. pub(super) const fn zero(point: GAffine) -> Self { Self { point, digits: [0; MAX_WINDOWS], } } /// Replaces this term's scalar with `scalar`, recoded as in [`Term::new`]. pub(super) fn recode(&mut self, scalar: &Scalar, width: u32) { let digits: [i32; MAX_WINDOWS] = scalar.signed_digits(width); self.digits = digits.map(|d| d as i16); } } /// Total number of terms across `chunks`. fn total_terms(chunks: &[&[Term]]) -> usize { chunks.iter().map(|chunk| chunk.len()).sum() } /// The subslices of `chunks` covering global term indices `[start, end)`, where the global index /// runs across the chunks in order: how every consumer here reads an arbitrary cut of the logical /// term sequence without the caller ever flattening its slices into one allocation. fn pieces<'a>( chunks: &'a [&'a [Term]], start: usize, end: usize, ) -> impl Iterator + 'a { let mut offset = 0; chunks.iter().filter_map(move |chunk| { let chunk_start = offset; offset += chunk.len(); let lo = start.max(chunk_start); let hi = end.min(chunk_start + chunk.len()); (lo < hi).then(|| &chunk[lo - chunk_start..hi - chunk_start]) }) } /// One past the highest bucket any digit of `window` lands in over global range `[start, end)` /// (`0` if none does, i.e. the largest digit *magnitude*; see [`Scalar::signed_digits`]). Every /// bucket at or above this is still the identity after a fill and would contribute nothing to /// the bucket fold. When the terms are a small or sparse range (a tiny batch or the windows above /// the digits of a short scalar such as a 128-bit batch coefficient), that is *most* of the /// buckets. Computed as a standalone prescan over the recoded digits (cheap: one digit load and a /// compare per term, no point arithmetic) rather than tracked inside the bucket-fill loop, which /// keeps that work out of the fill's hot wave prologue. fn used_buckets(chunks: &[&[Term]], start: usize, end: usize, window: usize) -> usize { pieces(chunks, start, end) .flatten() .map(|term| term.digits[window].unsigned_abs() as usize) .max() .unwrap_or(0) } mod bucketed { use super::{Backend, G, Term}; use crate::curve::msm::fold_buckets; #[cfg(not(feature = "std"))] use alloc::{vec, vec::Vec}; /// Independent bucket stripes that a worker reuses across tiles, with the largest digit /// magnitude its current tile has added (zero until the tile adds a nonzero digit). pub(super) struct Scratch { buckets: Vec, used: usize, } impl Scratch { /// Allocates bucket stripes for windows of `width` bits. pub(super) fn new(_: B, width: u32) -> Self { Self { buckets: vec![G::IDENTITY; B::STRIPES * super::num_buckets(width)], used: 0, } } /// Adds the digits of `window` over global term range `[start, end)` to the current /// tile. pub(super) fn fill( &mut self, backend: B, chunks: &[&[Term]], start: usize, end: usize, window: usize, width: u32, ) { // A range whose digits in this window are all zero adds nothing. Returning before the // clear below also lets a tile with no nonzero digit finish without a fold. let used = super::used_buckets(chunks, start, end, window); if used == 0 { return; } // The tile's first nonzero digits clear the buckets the previous tile left behind. if self.used == 0 { self.buckets.fill(G::IDENTITY); } // The range can span several chunks, so the backend fills one piece at a time. The // tile's largest digit lets its fold skip the buckets above it. let nb = super::num_buckets(width); for piece in super::pieces(chunks, start, end) { backend.fill_buckets(&mut self.buckets, nb, piece, |term| { (&term.point, term.digits[window]) }); } self.used = self.used.max(used); } /// Ends the current tile and returns its window's contribution, *before* the doubling /// shift that positions it. A tile without nonzero digits contributes the identity /// without a fold. pub(super) fn finish(&mut self, backend: B, width: u32) -> G { match core::mem::take(&mut self.used) { 0 => G::IDENTITY, used => fold_buckets(backend, &self.buckets, super::num_buckets(width), used), } } } /// Computes the full MSM with backend bucket filling and an independent scalar fold. /// One bucket allocation is reused across every window. #[cfg(test)] pub(super) fn multiscalar_mul_serial( backend: B, chunks: &[&[Term]], width: u32, ) -> G { let nb = super::num_buckets(width); let total = super::total_terms(chunks); let mut result = G::IDENTITY; let mut buckets = vec![G::IDENTITY; B::STRIPES * nb]; for window in (0..super::num_windows(width)).rev() { for _ in 0..width { result = result.double(); } let used = super::used_buckets(chunks, 0, total, window); for piece in super::pieces(chunks, 0, total) { backend.fill_buckets(&mut buckets, nb, piece, |term| { (&term.point, term.digits[window]) }); } let mut sum = G::IDENTITY; for digit in (0..used).rev() { for stripe in 0..B::STRIPES { sum = sum.add(buckets[stripe * nb + digit]); } result = result.add(sum); } buckets.fill(G::IDENTITY); } result } } /// Computes the full MSM over `chunks` with an independent scalar fold. #[cfg(test)] fn multiscalar_mul_terms_serial(backend: B, chunks: &[&[Term]], width: u32) -> G { bucketed::multiscalar_mul_serial(backend, chunks, width) } /// Computes `sum(points[i] * scalars[i])` serially: the reference the differential tests below /// compare the strategy-generic path against. #[cfg(test)] fn multiscalar_mul_points_serial( backend: B, points: &[GAffine], scalars: &[Scalar], width: u32, ) -> G { debug_assert_eq!(points.len(), scalars.len()); let terms: Vec = points .iter() .zip(scalars) .map(|(point, scalar)| Term::new(*point, scalar, width)) .collect(); multiscalar_mul_terms_serial(backend, &[&terms], width) } /// Straus's method (see [`crate::curve::msm::straus`]) over `terms`. fn straus(backend: B, terms: &[&Term], width: u32) -> G { backend.with_lanes(crate::curve::msm::Straus::new( terms, num_windows(width), width, |term| (&term.point, term.digits.as_slice()), )) } /// A bucket tile's fixed cost, in terms: folding its buckets. Merging the stripes and updating two /// running sums takes about `STRIPES + 1` additions per bucket, on lanes where each addition /// fills one term per stripe. const fn tile_cost(width: u32) -> NonZeroUsize { NZUsize!(num_buckets(width) * (B::STRIPES + 1)) } /// The window at tile row `slot`. /// /// Short scalars leave the high windows sparse, so windows differ in cost. A parallel run claims /// whole rows in order or gives each worker a share of cells over consecutive rows, so low and /// high windows alternate to mix cheap and expensive rows. const fn interleaved_window(slot: usize, windows: usize) -> usize { if slot.is_multiple_of(2) { slot / 2 } else { windows - 1 - slot / 2 } } /// Pippenger's bucket method over `chunks`. Each strategy-supplied `(window, term range)` tile /// fills its window's buckets piece by piece and folds them once, the partials of each window are /// added, and the backend positions the window sums. fn buckets(backend: B, chunks: &[&[Term]], width: u32, strategy: &impl Strategy) -> G { let windows = num_windows(width); let total = total_terms(chunks); let grid = Grid { rows: windows, tile_cost: tile_cost::(width), }; strategy.run_tiles(total, &[grid], 1, |tiles| { // Rows are windows in interleaved order, and columns are terms. Each worker reuses one set // of bucket stripes across its tiles, and each tile yields a partial for its window. let partials = tiles.fill_collect_vec( || bucketed::Scratch::new(backend, width), |scratch, slot, range| { let window = interleaved_window(slot, windows); scratch.fill(backend, chunks, range.start, range.end, window, width); }, |scratch, slot| { let window = interleaved_window(slot, windows); (window, scratch.finish(backend, width)) }, ); // A window cut into several tiles has several partials, which the backend sums before // shifting each window into place. backend.combine_windows(partials, windows, width) }) } /// Computes the full MSM over `chunks`, whose terms were recoded at `width` (see [`width_for`] and /// [`Term::new`]). From [`Backend::PARALLEL_STRAUS_TERM_CUTOFF`] terms, [`buckets`] runs its tiles /// serially or in parallel. Below it, the strategy chooses between a serial body, which uses /// [`straus`] below [`Backend::STRAUS_TERM_CUTOFF`] and [`buckets`] above it, and Straus split /// across workers. pub(super) fn multiscalar_mul( backend: B, chunks: &[&[Term]], width: u32, strategy: &impl Strategy, ) -> G { let total = total_terms(chunks); if total >= B::PARALLEL_STRAUS_TERM_CUTOFF { return buckets(backend, chunks, width, strategy); } let terms = || -> Vec<&Term> { pieces(chunks, 0, total).flatten().collect() }; strategy.run( total, || { if total < B::STRAUS_TERM_CUTOFF { return straus(backend, &terms(), width); } buckets(backend, chunks, width, &Sequential) }, || { // Consecutive lane groups split into contiguous parts, one per strategy batch, each // with its own accumulator. strategy.run_batches(total.div_ceil(LANES), NonZeroUsize::MIN, LANES, |batches| { let terms = terms(); batches .map_collect_vec( |ranges| ranges, |groups| { let part = &terms[groups.start * LANES..(groups.end * LANES).min(total)]; straus(backend, part, width) }, ) .into_iter() .fold(G::IDENTITY, G::add) }) }, ) } #[cfg(test)] mod tests { use super::*; use crate::{ curve::Backend, test::strategy::{Assembly, AssemblyBoundary}, }; #[cfg(not(feature = "std"))] use alloc::vec; use arbitrary::Unstructured; use commonware_invariants::minifuzz::Builder; use commonware_parallel::{ Sequential, mocks::{Explorer, pooled}, }; use core::any::type_name; use rand_core::Rng as _; use std::panic::{AssertUnwindSafe, catch_unwind}; /// The widths every differential test sweeps: [`width_for`]'s full output range. const TEST_WIDTHS: [u32; 5] = [6, 7, 8, 9, 10]; /// Returns `n` affine points selected directly from arbitrary encodings. Invalid encodings /// map to one of the two basic subgroup edge cases so every input remains usable. fn arbitrary_affine_points( u: &mut Unstructured<'_>, n: usize, ) -> arbitrary::Result> { (0..n) .map(|_| { let bytes: [u8; 32] = u.arbitrary()?; Ok(GAffine::decompress(&bytes).unwrap_or_else(|| { if bytes[0] & 1 == 0 { GAffine::IDENTITY } else { GAffine::BASEPOINT } })) }) .collect() } /// Returns `n` [`Term`]s over arbitrary points and scalars, recoded at `width`. fn arbitrary_terms( u: &mut Unstructured<'_>, n: usize, width: u32, ) -> arbitrary::Result> { arbitrary_affine_points(u, n)? .into_iter() .map(|point| { let scalar: Scalar = u.arbitrary()?; Ok(Term::new(point, &scalar, width)) }) .collect() } /// Expands one drawn seed into enough bytes for every draw a test makes, so its points and /// scalars stay random however short the fuzzer's input is. fn expand(u: &mut Unstructured<'_>) -> arbitrary::Result> { let mut bytes = vec![0; 1 << 19]; commonware_utils::TestRng::new(u.arbitrary()?).fill_bytes(&mut bytes); Ok(bytes) } fn points_equal(actual: G, expected: G) -> bool { actual.add(expected.negate()).is_identity() } /// Splits `terms` into owned chunks of the given (deliberately uneven, stripe-unaligned) /// sizes, with any remainder in one final chunk. fn split_terms(mut terms: Vec, sizes: &[usize]) -> Vec> { let mut chunks = Vec::new(); for &size in sizes { if terms.len() <= size { break; } let rest = terms.split_off(size); chunks.push(terms); terms = rest; } chunks.push(terms); chunks } /// Borrows a set of owned chunks as the slice-of-slices shape the MSM API takes. fn refs(chunks: &[Vec]) -> Vec<&[Term]> { chunks.iter().map(Vec::as_slice).collect() } #[test] fn canonical_edge_terms_match_bitwise_multiplication() { // Zero, one, the largest 128-bit value, `2^252` and its two neighbors (all below `L`), // and `L - 1`, each on the basepoint, a torsion point, and their sum. let mut top = [0u8; 32]; top[31] = 0x10; let top = Scalar::from_canonical_bytes(&top).unwrap(); let one = Scalar::from_u128(1); let torsion = GAffine::decompress(&[0u8; 32]).unwrap().to_extended(); let scalars = [ Scalar::ZERO, one, Scalar::from_u128(u128::MAX), top.add_mod_l(&one.neg_mod_l()), top, top.add_mod_l(&one), one.neg_mod_l(), ]; let backend = crate::curve::test_backend(); // One term is recoded at every width in turn, and both Straus and the bucket method must // match bitwise double-and-add exactly. for scalar in scalars { for point in [ GAffine::BASEPOINT.to_extended(), torsion, GAffine::BASEPOINT.to_extended().add(torsion), ] { let expected = point.scalar_mul(scalar.bits_be()); let mut term = Term::zero(point.to_affine()); for width in TEST_WIDTHS.into_iter().rev() { term.recode(&scalar, width); let chunks = [&[term][..]]; assert!(points_equal(straus(backend, &[&term], width), expected)); assert!(points_equal( buckets(backend, &chunks, width, &Sequential), expected )); } } } } #[test] fn strategy_callbacks_return_assembled_msm() { fn parallel_cutoff(_: B) -> usize { B::PARALLEL_STRAUS_TERM_CUTOFF } // The first count takes parallel Straus through `run_batches`, and the second the bucket // method through `run_tiles`. `Assembly` stops at that operation, which must assemble // the final point rather than return partials. for count in [LANES + 1, parallel_cutoff(crate::curve::test_backend())] { let terms = vec![Term::new(GAffine::BASEPOINT, &Scalar::from_u128(1), MIN_WIDTH); count]; let strategy = Assembly::default(); let stopped = catch_unwind(AssertUnwindSafe(|| { multiscalar_mul( crate::curve::test_backend(), &[&terms], MIN_WIDTH, &strategy, ) })); assert!(stopped.unwrap_err().is::()); assert_eq!(*strategy.outputs.lock(), [type_name::()]); } } #[test] fn width_for_matches_tuned_widths() { // The tuned widths, as (signatures, parallel, width), for batches of 2 * signatures + 1 // terms. for (sigs, parallel, expected) in [ (1024, true, 7), (4096, true, 8), (16384, true, 9), (65536, true, 9), (1024, false, 7), (4096, false, 8), (16384, false, 9), (65536, false, 10), ] { assert_eq!( width_for(2 * sigs + 1, parallel), expected, "sigs={sigs} parallel={parallel}" ); } // Clamps: tiny batches never drop below MIN_WIDTH, huge parallel batches never exceed // MAX_WIDTH - 1 (bucket footprint), huge serial batches never exceed MAX_WIDTH. assert_eq!(width_for(1, true), MIN_WIDTH); assert_eq!(width_for(usize::MAX, true), MAX_WIDTH - 1); assert_eq!(width_for(usize::MAX, false), MAX_WIDTH); } #[test] fn matches_naive_double_and_add() { struct Compute<'a> { points: &'a [GAffine], scalars: &'a [Scalar], width: u32, } impl crate::curve::WithBackend for Compute<'_> { type Output = G; fn call(self, backend: B) -> G { multiscalar_mul_points_serial(backend, self.points, self.scalars, self.width) } } let backend = crate::curve::test_backend(); Builder::default() .with_seed(0) .with_search_limit(1) .test(|u| { let bytes = expand(u)?; let u = &mut Unstructured::new(&bytes); let points = arbitrary_affine_points(u, 100)?; let scalars = (0..100) .map(|_| u.arbitrary()) .collect::>>()?; for n in [0, 1, 2, 5, 8, 9, 32, 64, 100] { let points = &points[..n]; let scalars = &scalars[..n]; let expected = points .iter() .zip(scalars) .fold(G::IDENTITY, |acc, (point, scalar)| { acc.add(point.to_extended().scalar_mul(scalar.bits_be())) }); for width in TEST_WIDTHS { let actual = multiscalar_mul_points_serial(backend, points, scalars, width); assert!(points_equal(actual, expected), "n={n} width={width}"); let accelerated = crate::curve::with_backend(Compute { points, scalars, width, }); assert!(points_equal(accelerated, expected), "n={n} width={width}"); } } Ok(()) }); } /// Slice boundaries are pure layout: any split of the same terms (including stripe-unaligned /// and empty slices, whose tail waves pad with identity lanes) must produce the same point as /// one contiguous slice. #[test] fn chunked_matches_single_chunk() { struct Check; impl crate::curve::WithBackend for Check { type Output = (); fn call(self, backend: B) { Builder::default() .with_seed(0) .with_search_limit(1) .test(|u| { let bytes = expand(u)?; let u = &mut Unstructured::new(&bytes); let terms = arbitrary_terms(u, 100, 7)?; for n in [1, 2, 5, 8, 9, 32, 64, 100] { let terms = terms[..n].to_vec(); let single = split_terms(terms.clone(), &[]); let mut chunks = split_terms(terms, &[1, 3, 7, 9, 24]); chunks.push(Vec::new()); let expected = multiscalar_mul_terms_serial(backend, &refs(&single), 7); let actual = multiscalar_mul_terms_serial(backend, &refs(&chunks), 7); assert!(points_equal(actual, expected)); } Ok(()) }); } } crate::curve::WithBackend::call(Check, crate::curve::test_backend()); crate::curve::with_backend(Check); } #[test] fn strategy_path_matches_serial() { struct Check; impl crate::curve::WithBackend for Check { type Output = (); fn call(self, backend: B) { Builder::default() .with_seed(0) .with_search_limit(1) .test(|u| { let bytes = expand(u)?; let u = &mut Unstructured::new(&bytes); for width in TEST_WIDTHS { let terms = arbitrary_terms(u, 600, width)?; let cutoff = B::STRAUS_TERM_CUTOFF; for n in [0, 1, 2, 5, 32, cutoff - 1, cutoff, 600] { let chunks = split_terms(terms[..n].to_vec(), &[64, 64, 64, 64]); let chunks = refs(&chunks); let expected = multiscalar_mul_terms_serial(backend, &chunks, width); let actual = multiscalar_mul(backend, &chunks, width, &Sequential); assert!(points_equal(actual, expected), "n={n} width={width}"); } } Ok(()) }); } } crate::curve::WithBackend::call(Check, crate::curve::test_backend()); crate::curve::with_backend(Check); } #[test] fn straus_matches_serial_across_lane_boundaries() { struct Check; impl crate::curve::WithBackend for Check { type Output = (); fn call(self, backend: B) { Builder::default() .with_seed(0) .with_search_limit(1) .test(|u| { let bytes = expand(u)?; let u = &mut Unstructured::new(&bytes); for width in [6, 8, 10] { let mut terms = arbitrary_terms(u, 383, width)?; // Terms 8 through 16 have scalar zero, like the padding in batch // verification's units, so every lane width sees whole groups // without a nonzero digit. for term in &mut terms[8..17] { *term = Term::zero(term.point); } // Counts on both sides of multiples of `LANES`, up to the largest // batch that any backend's serial run hands to Straus. for n in [1, 7, 8, 9, 16, 17, 33, 383] { let expected = multiscalar_mul_terms_serial(backend, &[&terms[..n]], width); let refs: Vec<&Term> = terms[..n].iter().collect(); let sequential = straus(backend, &refs, width); assert!(points_equal(sequential, expected), "n={n} width={width}"); } } Ok(()) }); } } crate::curve::WithBackend::call(Check, crate::curve::test_backend()); crate::curve::with_backend(Check); } /// Straus over hand-picked digits matches an independent Horner evaluation exactly, so /// torsion components are checked too. #[test] fn straus_matches_horner_for_edge_digits() { struct Check; impl crate::curve::WithBackend for Check { type Output = (); fn call(self, backend: B) { let base = GAffine::BASEPOINT.to_extended(); let torsion = GAffine::decompress(&[0; 32]).unwrap(); let mixed = GAffine::decompress(&base.add(torsion.to_extended()).compress()).unwrap(); let points = [GAffine::BASEPOINT, torsion, GAffine::IDENTITY, mixed]; for width in TEST_WIDTHS { let nb = num_buckets(width) as i16; let windows = num_windows(width); let cycle = [0, 1, -1, 2, -2, nb - 1, 1 - nb, nb, -nb]; // The top window and window 1 are zero for every term, so every kernel skips // all of their groups. Window 2 is `-nb` in every lane. let terms: Vec = (0..17) .map(|i| Term { point: points[i % points.len()], digits: core::array::from_fn(|window| match window { 1 => 0, 2 => -nb, _ if window + 1 >= windows => 0, _ => cycle[(i + window) % cycle.len()], }), }) .collect(); // Evaluate each term's digits by Horner's rule with scalar arithmetic. let values: Vec = terms .iter() .map(|term| { let point = term.point.to_extended(); (0..windows).rev().fold(G::IDENTITY, |acc, window| { let acc = (0..width).fold(acc, |acc, _| acc.double()); let digit = term.digits[window]; let magnitude = digit.unsigned_abs(); let multiple = point.scalar_mul( (0..width).rev().map(|bit| magnitude & (1 << bit) != 0), ); acc.add(if digit < 0 { multiple.negate() } else { multiple }) }) }) .collect(); for n in [1, 2, 3, 7, 8, 9, 16, 17] { let terms = &terms[..n]; let expected = values[..n] .iter() .fold(G::IDENTITY, |sum, &value| sum.add(value)); let refs: Vec<&Term> = terms.iter().collect(); assert!( points_equal(straus(backend, &refs, width), expected), "n={n} width={width}" ); } } } } crate::curve::WithBackend::call(Check, crate::curve::test_backend()); crate::curve::with_backend(Check); } #[test] fn tile_parallel_matches_serial_under_real_parallelism() { struct Check; impl crate::curve::WithBackend for Check { type Output = (); fn call(self, backend: B) { // Every call takes its most parallel shape. Planning parallelism above the pool // size runs more tasks than threads, so threads that finish claim pending rows. // Where the grid is shared as cells, they take the back halves of pending shares, // and each stolen half can cut a window at an arbitrary term. let strategy = Explorer::parallel(&pooled(NZUsize!(4), NZUsize!(32))); Builder::default() .with_seed(0) .with_search_limit(1) .test(|u| { let bytes = expand(u)?; let u = &mut Unstructured::new(&bytes); for width in [6, 8, 10] { let terms = arbitrary_terms(u, 1100, width)?; for n in [0, 1, 300, 1024, 1100] { let chunks = split_terms( terms[..n].to_vec(), &[128, 128, 128, 128, 128, 128], ); let chunks = refs(&chunks); let expected = multiscalar_mul_terms_serial(backend, &chunks, width); let actual = multiscalar_mul(backend, &chunks, width, &strategy); assert!(points_equal(actual, expected), "n={n} width={width}"); } } Ok(()) }); } } crate::curve::WithBackend::call(Check, crate::curve::test_backend()); crate::curve::with_backend(Check); } #[test] fn window_partials_reuse_scratch_across_zero_windows() { struct Check; impl crate::curve::WithBackend for Check { type Output = (); fn call(self, backend: B) { let point = GAffine::BASEPOINT; for width in TEST_WIDTHS { let scalar = Scalar::from_u128((1u128 << (2 * width)) | 1); let terms = [Term::new(point, &scalar, width)]; // The digits in windows 0, 1, and 2 are 1, 0, and 1. The zero window must not // fold the buckets window 0 left behind, and window 2 must clear them. let mut scratch = bucketed::Scratch::new(backend, width); for (window, expected) in [point.to_extended(), G::IDENTITY, point.to_extended()] .into_iter() .enumerate() { scratch.fill(backend, &[&terms], 0, terms.len(), window, width); let actual = scratch.finish(backend, width); assert!( points_equal(actual, expected), "window={window} width={width}" ); } } } } crate::curve::WithBackend::call(Check, crate::curve::test_backend()); crate::curve::with_backend(Check); } /// Splitting a window's bucket fill at an arbitrary global index (deliberately not a slice /// boundary), either into two tiles whose partials are added or into two pieces of one tile, /// must Horner-fold to the exact same point as running the whole MSM over the full range at /// once. This is the correctness argument the tile-parallel [`multiscalar_mul`] relies on to /// combine same-window tiles with a single addition and to fill a tile in pieces. #[test] fn split_window_partials_match_whole_range() { struct Check; impl crate::curve::WithBackend for Check { type Output = (); fn call(self, backend: B) { const WIDTH: u32 = 7; Builder::default() .with_seed(0) .with_search_limit(1) .test(|u| { let bytes = expand(u)?; let u = &mut Unstructured::new(&bytes); let terms = arbitrary_terms(u, 100, WIDTH)?; for n in [1, 2, 5, 8, 9, 32, 64, 100] { let chunks = split_terms(terms[..n].to_vec(), &[n / 3, n / 3]); let chunks = refs(&chunks); let total = total_terms(&chunks); let mid = total / 2; let expected = multiscalar_mul_terms_serial(backend, &chunks, WIDTH); // Every window's sum is computed twice with one reused scratch: as two // tiles whose partials are added, and as one tile filled in two pieces. let nw = num_windows(WIDTH); let mut split = vec![G::IDENTITY; nw]; let mut pieced = vec![G::IDENTITY; nw]; let mut scratch = bucketed::Scratch::new(backend, WIDTH); for window in 0..nw { scratch.fill(backend, &chunks, 0, mid, window, WIDTH); let left = scratch.finish(backend, WIDTH); scratch.fill(backend, &chunks, mid, total, window, WIDTH); split[window] = left.add(scratch.finish(backend, WIDTH)); scratch.fill(backend, &chunks, 0, mid, window, WIDTH); scratch.fill(backend, &chunks, mid, total, window, WIDTH); pieced[window] = scratch.finish(backend, WIDTH); } // Positioning either set of window sums must reproduce the whole MSM. for partials in [split, pieced] { assert!(points_equal( backend.combine_windows( partials.into_iter().enumerate(), nw, WIDTH ), expected, )); } } Ok(()) }); } } crate::curve::WithBackend::call(Check, crate::curve::test_backend()); crate::curve::with_backend(Check); } /// [`pieces`] must hand back exactly the requested global range, in order, for any cut, /// including cuts inside slices, across slice boundaries, and touching empty slices. #[test] fn pieces_covers_exact_global_ranges() { Builder::default() .with_seed(0) .with_search_limit(8) .test(|u| { let chunks = split_terms(arbitrary_terms(u, 50, 7)?, &[1, 7, 0, 24]); let mut chunks = refs(&chunks); chunks.insert(2, &[]); let total = total_terms(&chunks); assert_eq!(total, 50); let flat: Vec<*const Term> = chunks .iter() .flat_map(|chunk| chunk.iter().map(|t| t as *const Term)) .collect(); for (start, end) in [(0, 50), (0, 0), (3, 3), (0, 1), (7, 9), (1, 40), (49, 50)] { let got: Vec<*const Term> = pieces(&chunks, start, end) .flat_map(|piece| piece.iter().map(|t| t as *const Term)) .collect(); assert_eq!(got, flat[start..end], "range ({start}, {end})"); } Ok(()) }); } }