Prize Sponsor: Polkadot Pioneer Prize
Prize Architect: Manta Network
Multi-Scalar multiplication (MSM) operations are essential building blocks for zk computations. This prize will focus on minimizing latency of these operations on client-type devices and blockchain-based VMs, specifically the WebAssembly (WASM) runtime.
Achieve the lowest combined latency of MSM over a range of input vector lengths in WASM runtimes.
We focus on variable-base MSM [1], which is widely used in zkSNARKs. Formally, variable-base MSM takes an input vector of elliptic curve points
and an input vector of finite field elements from the associated scalar field
Here, n is the input vector length (i.e., the number of elements in a vector).
The output is an elliptic curve point Q:
- The implementation must provide the following interface in JavaScript [2]:
compute_msm(point_vec, scalar_vec)
-
The function name is
compute_msm -
There are two input vectors: point_vec for a vector of elliptic curve points and scalar_vec for a vector of finite field elements.
-
The output is a single elliptic curve point.
-
The implementation can be constructed either in high-level language (Rust, C, C++, Javascript) or manually written WebAssembly.
-
The submitted WASM module can be run in Chrome 96, Firefox 90, Safari 15.2, Wasmtime 0.33.
-
Only the following WASM features are allowed: “JS Bigint to Wasm i64 integration”, “Bulk memory operations”, “Multi-value”, “Import & export of mutable globals”, “Reference types”, “Non-trapping float-to-int conversions”, and “sign-extension operations”. We allow these features since they are currently implemented in popular engines [3].
-
The MSM must be over the BLS12-381 G1 curve.
-
The submission should produce correct outputs on input vectors with length up to 2^18. The evaluation will be using input randomly sampled from size 2^14 ~ 2^18, which is the range that we find covers most use cases.
-
The submissions will be evaluated in single-threaded runtime without allowing OpenCL feature. This makes the submission more applicable for targeted execution environments, such as a wasm module in metamask-snap.
-
All submissions must include documentation (in English) sufficient to understand the approach being taken.
June 10 - Competition begins
July 25 - Mid-competition submission due
September 10 - Final submission due
Submissions will be analyzed for both correctness and performance.
We will provide a set of test input/output pairs so that the competitors can sanity check the correctness of their code.
The final correctness of the submission will be tested using randomly sampled test inputs/outputs that are not disclosed to the competitors during the competition in addition to the test input/output distributed to the competitor. All these test cases will be generated using Arkworks reference implementation. Submissions failed in any test cases will be judged as incorrect and lose the opportunity to win the prize.
To evaluate the performance of each submission, the prize committee will sample a large number (N > 200) of input vectors at random, in terms of both the input vector length and the point values. The input vector length will be sampled between 2^14 and 2^18. Then, we compute the multi-scalar multiplication using the submission. The submitted score will be the relative speedup from arkworks implementation, measured across 100 trials. More specifically, we compute the submitted score as follows:
Given N randomly selected input vectors, we measure the latency of baseline (i.e., Arkworks) as
We measure the latency of submission as
We compute the submitted score as
Intuitively, the submitted score represents the relative speedup from baseline over a range of input vector lengths.
In addition, all submissions will be manually reviewed by the prize committee.
-
Competitors will be provided with access to a Coreweave-provided virtual workstation: consisting of an NVIDIA Quadro RTX 4000 with 8GB of GDDR6 RAM and 5 vCPU cores with 30 GB of CPU RAM.
-
The baseline will be the Arkworks MSM implementation over BLS12-381 G1. This baseline is originally implemented in Rust. We compile the rust implementation to WASM runtime (through wasm-pack 0.10.2) as the baseline. Submissions must beat this baseline by at least 10% in order to be eligible for the prize.
The prize amount will be divided among the top three finishers according to the following proportions: 65% to winning implementation, 25% to second place, and 10% to third place.
In the event that there are only two qualifying submissions, first place will receive 70% of the prize pool and second place 30%. In the event there is only one qualifying submission, they will receive 100% of the prize pool.
Prizes will be given out in good faith and in the sole discretion of the prize committee.
All submission code must be open-sourced at the time of submission. Code and documentation must be dual-licensed under both the MIT and Apache-2.0 licenses
Why BLS-12-381?
-
BLS12-381 curve is used in BLS signature [4]
-
For Poseidon hash, BLS12-381 is more efficient than BLS12-377. Poseidon hash is widely used in many industry products such as Filecoin and Zcash. The performance of Poseidon hash is critical. To make Poseidon hash secure, BLS12-377 needs around 66% more computation and latency than BLS12-381.
Please include your implementation under the submission folder and update evaluate.sh correspondingly. You may also adapt submission_compute_msm function in the www/index.js file.
If there are any questions about this prize, please contact boyuan@manta.network
[1] Scalar-multiplication algorithms. https://cryptojedi.org/peter/data/eccss-20130911b.pdf
[2] compute_msm interface in Javascript. https://github.com/Manta-Network/wasm-zkp-challenge/blob/main/www/index.js#L22
[3] Web Assembly Roadmap. https://webassembly.org/roadmap/
[4] BLS Signature. https://datatracker.ietf.org/doc/draft-irtf-cfrg-bls-signature/04/