MSM
Last updated
Last updated
The Multi-Scalar Multiplication (MSM) operation consists of multiplying a vector of finite field elements by a vector of elliptic curve points and summing the resulting vector into a single point. The Pippenger bucketing algorithm is typically applied, and well-documented in existing literature [REF]. The cuSnark library utilizes a generalized version of the winning 2022 zprize MSM implementation, documentation of which can be found here [REF].
The following table outlines the performance improvements yielded with just the cuSnark MSM employed, showing the (CPU baseline) and accelerated results for the different proof stages in a set of proofs of various sizes. Times are in seconds, obtained on a AMD EPYC 7702 64-Core Processor with 4x NVIDIA GeForce RTX 3090 (24 GB) GPUs.
| Proof Stage | 2^20 rows, 1135 columns | 2^25 rows, 5 columns |
|---|---|---|
Initialization
(6.04) 6.08
(1.40) 1.41
Generate Instance
(0.05) 0.05
(1.05) 1.05
Generate Advice
(381.78) 339.69
(6.68) 4.07
Generate Lookups
(57.99) 57.19
(2.10) 1.86
Commit Permutations
(146.59) 75.80
(23.72) 13.74
Eval_h
(1069.09) 1070.57
(66.55) 66.75
Compute Evaluations
(9.81) 7.49
(35.75) 6.10
Multiopen
(18.71) 18.94
(28.82) 11.61
Total
(1690.05) 1575.82
(166.10) 106.59