Pippenger's Algorithm
Reduction of multi-scalar multiplication (MSM) into double and add operations
AKA "Bucket" method
Motivation
Improve upon Double-and-add by reducing the total number of double and add operations needed for MSM.
Algorithm Process
Introduction
Multi-Scalar Multiplication (MSM) refers to the efficient computation of expressions in the following form:
: the -th -bit scalar
: the -th point on an elliptic curve
Pippenger's algorithm speeds up MSM by dividing each scalar into multiple -bit chunks, and then grouping and processing scalars by their corresponding bit positions (windows).
1. Scalar Decomposition
First, we decompose the scalars :
: the number of bits per window
: the total number of windows
Through this definition, we can rewrite the original MSM summation as follows:
Note that is the sum for the -th window.
2. Bucket Accumulation
Given our , we denote buckets as the following:
Or in other words, refers to the bucket in window consisting of the summation of points with the same .
Note that must be within the range ; however, if is 0, as is the scalar multiplier, the result of the bucket will be 0. Therefore, the practical range of is .
3. Bucket Reduction
Thus, in total, a window will be re-structured as follows:
Note that the computation of a singular is computed through a running sum of recursive summations and not through further scalar multiplications.
Complexity Cost:
Original:
Bucketed:
C++ Implementation
Bucket ReduceBucketPoints(const std::vector<Bucket>& buckets) {
Bucket res = Bucket::Zero();
Bucket sum = Bucket::Zero();
for (size_t i = buckets.size() - 1; i != SIZE_MAX; --i) {
sum += buckets[i];
res += sum;
}
return res;
}
Example
// Round 1
sum = B_(4,1);
res = B_(4,1);
// Round 2
sum = B_(3,1) + B_(4,1);
res = B_(4,1) + [B_(3,1) + B_(4,1)];
// Round 3
sum = B_(2,1) + B_(3,1) + B_(4,1);
res = B_(4,1) + [B_(3,1) + B_(4,1)] + [B_(2,1) + B_(3,1) + B_(4,1)];
// Round 3
sum = B_(1,1) + B_(2,1) + B_(3,1) + B_(4,1);
res = B_(4,1) + [B_(3,1) + B_(4,1)] + [B_(2,1) + B_(3,1) + B_(4,1)] + [B_(1,1) + B_(2,1) + B_(3,1) + B_(4,1)];
// Total:
res = B_(1,1) + 2*B_(2,1) + 3*B_(3,1) + 4*B_(4,1);
4. Window Reduction - Final MSM Result
With the finished individual window computations, we return to the total MSM summation and add all windows together:
In practice, the computation is calculated recursively from to like so:
Complexity Cost
C++ Implementation
Bucket ReduceWindows(uint32_t lambda, uint32_t s, const std::vector<Bucket>& buckets) {
Bucket res = Bucket::Zero();
uint32_t window_num = static_cast<uint32_t>(std::ceil(lambda / s));
for (uint32_t j = window_num - 1; j != UINT32_MAX; --i) {
for (uint32_t i = 0; i < s; ++i) {
res = res * 2;
}
res += buckets[j];
}
return res;
}
Complexity Analysis
To compute , is required:
Each needs :
Final needs:
Total complexity
Optimization Table (When , )
2
134,218,624
4
67,110,848
8
33,570,784
16
18,874,352
32
68,727,865,336
64
147,573,952,589,680,607,228
128
1,361,129,467,683,753,853,853,498,429,727,074,942,974
🔍 This clearly shows that selecting an optimal value is critical for performance.
Example
Let's try to run Pippenger's on the following simple example:
1. Scalar Decomposition
Let's define our bits per window to be 2. In this case, since the maximum amount of bits needed to constrain the values 12, 9, and 13 is 4, we will have windows.
Note that in binary we have:
Decomposing our , , and results in the following:
2+3. Bucket Accumulation + Reduction
Given our of 2, we now have buckets of for a given window . Our windows are now re-structured to buckets like so:
From bottom up, in our bucket accumulation stage we compute the buckets:
...and in our bucket reduction stage we compute the windows:
4. Window Reduction - Final MSM Result
Putting all the windows together for the MSM sum, we get the following:
References
Written by ryan Kim &Ashley Jeong of A41
Last updated