# MSM

## Overview

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].

## Performance

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.

<table><thead><tr><th width="227">Proof Stage</th><th width="248">2^20 rows, 1135 columns</th><th>2^25 rows, 5 columns</th></tr></thead><tbody><tr><td>Initialization</td><td>(6.04) 6.08</td><td>(1.40) 1.41</td></tr><tr><td>Generate Instance</td><td>(0.05) 0.05</td><td>(1.05) 1.05</td></tr><tr><td>Generate Advice</td><td>(381.78) 339.69</td><td>(6.68) 4.07 </td></tr><tr><td>Generate Lookups</td><td>(57.99) 57.19</td><td>(2.10) 1.86 </td></tr><tr><td>Commit Permutations</td><td>(146.59)  75.80</td><td>(23.72) 13.74 </td></tr><tr><td>Eval_h</td><td>(1069.09) 1070.57</td><td>(66.55) 66.75 </td></tr><tr><td>Compute Evaluations</td><td>(9.81) 7.49</td><td>(35.75) 6.10 </td></tr><tr><td>Multiopen</td><td>(18.71) 18.94</td><td>(28.82) 11.61</td></tr><tr><td>Total</td><td>(1690.05) 1575.82</td><td>(166.10) 106.59</td></tr></tbody></table>