Struct Pippenger

pub struct Pippenger;

Available on crate feature alloc only.

Implements a version of Pippenger’s algorithm.

The algorithm works as follows:

Let n be a number of point-scalar pairs. Let w be a window of bits (6..8, chosen based on n, see cost factor).

1. Prepare 2^(w-1) - 1 buckets with indices [1..2^(w-1)) initialized with identity points. Bucket 0 is not needed as it would contain points multiplied by 0.
2. Convert scalars to a radix-2^w representation with signed digits in [-2^w/2, 2^w/2]. Note: only the last digit may equal 2^w/2.
3. Starting with the last window, for each point i=[0..n) add it to a a bucket indexed by the point’s scalar’s value in the window.
4. Once all points in a window are sorted into buckets, add buckets by multiplying each by their index. Efficient way of doing it is to start with the last bucket and compute two sums: intermediate sum from the last to the first, and the full sum made of all intermediate sums.
5. Shift the resulting sum of buckets by w bits by using w doublings.
6. Add to the return value.
7. Repeat the loop.

Approximate cost w/o wNAF optimizations (A = addition, D = doubling):

cost = (n*A + 2*(2^w/2)*A + w*D + A)*256/w
         |          |       |     |   |
         |          |       |     |   looping over 256/w windows
         |          |       |     adding to the result
   sorting points   |       shifting the sum by w bits (to the next window, starting from last window)
   one by one       |
   into buckets     adding/subtracting all buckets
                    multiplied by their indexes
                    using a sum of intermediate sums

For large n, dominant factor is (n*256/w) additions. However, if w is too big and n is not too big, then (2^w/2)*A could dominate. Therefore, the optimal choice of w grows slowly as n grows.

This algorithm is adapted from section 4 of https://eprint.iacr.org/2012/549.pdf.

Trait Implementations

impl VartimeMultiscalarMul for Pippenger

type Point = EdwardsPoint

The type of point being multiplied, e.g., RistrettoPoint.

fn optional_multiscalar_mul<I, J>(scalars: I, points: J) -> Option<EdwardsPoint>

where I: IntoIterator, I::Item: Borrow<Scalar>, J: IntoIterator<Item = Option<EdwardsPoint>>,

Given an iterator of public scalars and an iterator of Options of points, compute either Some(Q), where $$ Q = c_1 P_1 + \cdots + c_n P_n, $$ if all points were Some(P_i), or else return None.

fn vartime_multiscalar_mul<I, J>(scalars: I, points: J) -> Self::Point

where I: IntoIterator, I::Item: Borrow<Scalar>, J: IntoIterator, J::Item: Borrow<Self::Point>, Self::Point: Clone,

Given an iterator of public scalars and an iterator of public points, compute $$ Q = c_1 P_1 + \cdots + c_n P_n, $$ using variable-time operations.

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 0 bytes