Prize Sponsor: Mina Foundation
Prize Architect: Mina / O(1) Labs
The Bootleproof inner-product argument used in Halo-type SNARKs is one of the more costly operations for provers. This prize focuses on improving the performance of this operation in browser-based provers.
Competitors should provide, using the arkworks library and its curves implementations, a function
fn combine(g1: &[ark_pallas::Affine], g2: &[ark_pallas::Affine], chal: &[bool]) -> Vec<ark_pallas::Affine>;
The semantics of this function should be as in this gist.
-
Runtime must be WASM
-
The MSM must be over the Pallas curve as described.
-
Web workers may be used
NOTE: All submissions must include documentation (in English) sufficient to understand the approach being taken.
June 17 - Competition begins
July 25 - Mid-competition submission due
September 17 - Final submission due
Submissions will be analyzed for both correctness and performance.
Submissions will be tested against the sample implementation described in the above gist.
Random arrays g1 and g2 of size 2^16 and a random challenge of 128 bits will be selected to test the speed of the implementation. The score of the submission will be the average performance across 100 trials.
In addition, all submissions will be manually reviewed by the prize committee.
The fastest existing implementation is here, which makes use of Pallas’s curve-endomorphism (x, y) -> (base_endo_coeff * x, y), where base_endo_coeff = 0x2D33357CB532458ED3552A23A8554E5005270D29D19FC7D27B7FD22F0201B547
It also makes use of multithreading and batched-affine operations.
The endomorphism-based scalar multiplication is defined in section 6.2 of the Halo paper.
Implementations will be compiled to WASM and benchmarked on a consumer-laptop with at least 8 cores in Google Chrome.
The prize amount will be divided among the top two finishers according to the following proportions: 75% to winning implementation and 25% to second place.
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.
If there are any questions about this prize, please contact Brett Carter at brett@o1labs.org