Multi-Scalar Multiplication (MSM)

The Multi-Scalar multiplication (MSM) competition tasked us with building an FPGA design to multiply $2^26$ points on the BLS12-377 elliptic curve (with the G1 subgroup generator) by scalars from the associated 253 bit scalar field and add them all as fast as possible.

The mathematical formulation of the MSM problem is as follows:

\[MSM(p, s) = ∑↙{i=0}↖{N-1} p_{i} s_{i}\]

where $p_{i}$ are points on the BLS12-377 elliptic curve, $s_{i}$ are scalars from a corresponding 253-bit scalar field and $N$ is the number of points. The points $p_{i}$ are known at initialization, but the scalars $s_{i}$ are only known during evaluation.

The challenge here is that point addition (adding two elliptic curve points together) and point multiplication (multiplying a point on an elliptic curve by a scalar) are both very expensive operations.

The platform targeted was Amazon f1.2xlarge, which uses a Xilinx UltraScale+ VU9P FPGA with DDR memory banks. We have utilized the aws-fpga Vitis flow in our implementation.

Design overview

Our implementation is built around pippenger’s algorithm, splitting work between the FPGA and the host. The pages below describe the architecture of our design and the main FPGA controller to compute bucket aggregation.

The heart of the computation is performed by a 1-per-cycle throughput mixed adder. The pages below detail the mathematics behind the implementation of the adder.

We discuss the low-level engineering implementation details, final results and reproduction guides in the pages below.

Some possible improvements on our work are noted here.

Hardcaml on the Web

Configure our designs, download RTL and perform simulations all within your browser!

Code structure

The code is built from various libraries within our submission repository. API Docs are available here.