• Quick Start
• Prize Desription
• Judging
• Prize Allocation
• Submission Instruction
• FAQs
• Further Questions
• Trouble Shooting
• Reference

Ensure you have:

• Git LFS installed
• Node.js 16 or later installed
• Yarn v1 or v2 installed

Then run the following:

git clone https://github.com/demox-labs/webgpu-msm && cd webgpu-msm

yarn

Run a local server on localhost:4040.

yarn start

Note -- running webgpu functions will only work on browsers compatible with webgpu.

Multi-Scalar multiplication (MSM) operations are critical for building proofs and zk computations. They are also some of the slowest operations in these processes, especially running on consumer-grade hardware. This z-prize seeks to optimize for consumer-grade devices running msms in a browser environment.

Achieve the fastest MSM run in a browser over a range of input vector lengths and a range of consumer hardware.

The implementation must provide the following interface in JavaScript: compute_msm = async (baseAffinePoints: BigIntPoint[] | U32ArrayPoint[] | Buffer, scalars: bigint[] | Uint32Array[]| Buffer): Promise<{x: bigint, y: bigint}>

1. The function name is compute_msm

2. There are two input vectors: baseAffinePoints for a vector of elliptic curve affine points and scalars for a vector of finite field elements. There are three options for how the inputs are ingested, using bigints or Uint32Arrays or Buffers:

   a.

   BigIntPoint: {
     x: bigint,
     y: bigint,
     t: bigint,
     z: bigint
   }
   scalar: bigint
   

   b.

   BigEndian
   U32ArrayPoint: {
     x: Uint32Array,
     y: Uint32Array,
     t: Uint32Array,
     z: Uint32Array
   }
   scalar: Uint32Array
   

   c.

   LittleEndian
   points: Buffer,
   scalars: Buffer
   

   Note -- the inputs are affine points, so the z property will be 1n or [0, 0, 0, 0, 0, 0, 0, 1]. The t property is the field multiplication of x by y.

3. The output is a single elliptic curve affine point: { x: bigint, y: bigint }.

• The submission should produce correct outputs on input vectors with length up to 2^20. The evaluation will be using input randomly sampled from size 2^16 ~ 2^20.

• The submissions will be evaluated in a browser context on a variety of consumer-grade hardware.

• All submissions must include documentation (in English) sufficient to understand the approach being taken.

4. Do I have to provide support for all three of the input types?

• No. You only need to take one of the three types as inputs to the msm_compute function, and you may pass in whichever input type you'd like to accept in the AllBenchmarks.tsx file. You may cast your inputs to whatever type you'd like to accept, and casting will not affect the runtime performance. For example:

export const compute_msm = async (
  baseAffinePoints: BigIntPoint[] | U32ArrayPoint[] | Buffer,
  scalars: bigint[] | Uint32Array[] | Buffer
  ): Promise<{x: bigint, y: bigint}> => {
  const pointsAsBigIntPoint = baseAffinePoints as BigIntPoint[];
  const pointsAsUint32ArrayBigEndian = baseAffinePoints as Uint32Array[];
  const pointsAsBufferLittleEndian = baseAffinePoints as Buffer;
  .
  .
  .
  }

For passing in whichever input type you'd like to accept, modify the Benchmark for your msm in the AllBenchmarks.tsx file.

<Benchmark
  name={'Your bigInt MSM'}
  disabled={disabledBenchmark}
  baseAffinePoints={baseAffineBigIntPoints}
  scalars={bigIntScalars}
  expectedResult={expectedResult}
  msmFunc={compute_msm}
  postResult={postResult}
  bold={true}
/>

<Benchmark
  name={'Your buffer MSM'}
  disabled={disabledBenchmark}
  baseAffinePoints={bufferPoints}
  scalars={bufferScalars}
  expectedResult={expectedResult}
  msmFunc={compute_msm}
  postResult={postResult}
  bold={true}
/>

<Benchmark
  name={'Your u32 MSM'}
  disabled={disabledBenchmark}
  baseAffinePoints={u32Points}
  scalars={u32Scalars}
  expectedResult={expectedResult}
  msmFunc={compute_msm}
  postResult={postResult}
  bold={true}
/>

Submissions will be analyzed for both correctness and performance. 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.

We have provided test case data and answers to sanity-check your msm function against, as well as multiple msm implementations to check against.

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 Aleo's reference wasm 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 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^16 and 2^20. Then, we will compute the multi-scalar multiplication using the submission. The submitted score will be the relative speedup from the provided best webgpu msm implementation, averaged across many trials.

In addition, all submissions will be manually reviewed by the prize committee.

The baseline will be the Demox Labs WebGPU MSM implementation over BLS12-377 G1. This baseline is originally implemented in typescript and wgsl. Submissions must beat this baseline by at least 10% in order to be eligible for the prize.

Prizes will be given out in good faith and in the sole discretion of the prize committee.

• August 1 - 2023 Registration Opens
• September 15 - Competition Begins
• February - Submission Deadline
• March - Winners Announced

Please include your implementation under the submission folder. The compute_msm function in submission/submission.ts will be run when benchmarking your submission.

The goal of this track is to enhance the efficiency of client-side proving for the Aleo proof system using various web technologies.

Yes, you are allowed to use WebGPU and multithreading (web workers) to enhance performance.

The competition will use BLS12-377 as the elliptic curve.

The competition encourages the use of widely supported web technologies. There are no strict restrictions on the technologies you can use, but the focus is on ensuring client proving speed on different devices.

Access to evaluation platforms will not be provided. The benchmarking aims to test solutions on various commodity devices and seeks general browser environment improvements. Most WASM features that work within Chrome v115 are allowed, including multithreading through web workers.

Yes! WebGPU may be used for any amount of the submission implementation.

You can use all of the WASM features that work within chrome v115. Multithreading is allowed for instance but browsers don't have threads so you have to use web workers to accomplish this using something like: https://github.com/GoogleChromeLabs/wasm-bindgen-rayon.

If there are any questions about this prize:

• Ask in the zprize discord: https://discord.gg/DKqrz6F42D.
• Consult the zprize website: https://www.zprize.io/

Common issues:

• If you are unable to run the webgpu benchmarks, ensure you are using a webgpu-compatible browser.
• If you are not able to load the test case data, be sure you have installed git LFS. You can either reclone the repo after installing git LFS or run git lfs fetch && git lfs pull.
• If you run into general npm package errors, make sure you have nodejs v16 or later installed.
• If you are using webgpu functions and getting all 0s as output, you may have hit an out of memory error in the gpu. Reduce your input size or consider breaking your computions into smaller steps.
• If you are running on a windows machine with multiple graphics cards (ie. integrated chip + dedicated card) you can force Chrome to use one of them via windows settings. Go to Settings -> Graphics Settings -> Custom options for apps -> Select / add Chrome -> Options -> Select graphics preference

[1] Scalar-multiplication algorithms. https://cryptojedi.org/peter/data/eccss-20130911b.pdf

[2] compute_msm functions in Typescript/WebGPU/WASM https://github.com/demox-labs/webgpu-msm/blob/main/src/reference/reference.tsj

[3] wgsl reference https://www.w3.org/TR/WGSL/

[4] aleo wasm reference https://github.com/demox-labs/aleo/blob/gpu-expose/wasm/src/account/address.rs#L167