FCMP++ Coding CompetitionThe Monero community is excited to announce the launch of the FCMP++ (Full-Chain Membership Proofs) Optimization Coding Competition!
See all contest details here:
https://github.com/j-berman/fcmp-plus-plus-optimization-competitionWhat is FCMP++?FCMP++ is one of the most significant privacy enhancements to Monero since its inception. This upgrade would improve sender-privacy from 1 in 16 to 1 in over 150 million while maintaining compatibility with existing wallets and addresses!
About the CompetitionWe're looking to optimize the performance of two critical libraries used in FCMP++
This is your chance to make a direct contribution to Monero's future while competing for 350xmr (~$70,000 at time of writing) in rewards and global recognition.
Competition DetailsHow to EnterResourcesJoin us in shaping the future of financial privacy!
Questions? Join #monero-dev on
or reach out through the competition GitHub repository.
FCMP++ Optimization CompetitionThe contest will open for submissions
Monday, April 28th at 17:00 UTC, and we will stop accepting submissions
Monday, June 30th at 17:00 UTC!The goal of this contest is to provide optimized implementations of helioselene:
https://github.com/kayabaNerve/fcmp-plus-plus/tree/develop/crypto/helioselene and ec-divisors:
https://github.com/kayabaNerve/fcmp-plus-plus/tree/develop/crypto/divisorsWhile any method of achieving faster performance will be accepted, the following scopes of work are highlighted.
helioselene uses crypto-bigint:
https://github.com/kayabaNerve/fcmp-plus-plus/tree/develop/crypto/divisorsfor its arithmetic. Replacing its field arithmetic with a tailored implementation will likely provide significant savings. The prime used for the field introduced by the Helios/Selene cycle is a Crandall prime with fast reduction algorithms available accordingly.
ec-divisors performs polynomial multiplications/divisions which are quite expensive without an FFT. While we can't assume it'll be used with curves which are FFT friendly, it would be valid to define a trait to specify a FFT-friendly multiplicative group to use with a curve (so long as such groups are feasible to find for arbitrary curves). This would enable implementing ECFFT:
https://arxiv.org/abs/2107.08473reducing the computational complexity of ec-divisors.
Requirements- 1. Implementations must run in constant time.
Implementations will be reviewed for a variety of non-constant-time operations:
https://bearssl.org/constanttime.html
All branches and memory access must be constant with regards to the secrets operated over. We do assume shifts and multiplications execute in constant time.
Additionally, code will be run through wasm-cycles:
https://github.com/j-berman/wasm-cycles/
to verify a constant cycle count when compiled for wasm32v1-none. This is incomprehensive to certain issues such as cache side-channel attacks, yet represents an automated way to eliminate some types of non-constant-time code.
- 2. Submissions must be written by the submitter and licensed under MIT at time of submission.
Code written by third parties must be included as a properly attributed dependency and not directly submitted. Code generated by LLMs also will not be accepted.
- 3. Submissions must compile with both Rust stable 1.69 and 1.84.
Usage of nightly features is not allowed.
- 4. Submissions must support targets with alloc yet not std.
wasm32v1-none is the provided example of such a target. If the submission builds and runs on it, it meets this criteria.
This requirement does prevent the usage of threads which are expected to be used at a higher level by calling code.
- 5. Submissions must not have platform-specific code.
While various intrinsics would produce the best performance on their respective targets, the point of this competition is to create baseline libraries usable regardless of context.
- 6. Submissions must not include any unsafe code.
- 7. Dependencies must be pre-approved.
Please create an issue requesting to use a dependency, or contact @jberman:monero.social on Matrix. We will approve dependencies on a case-by-case basis.
- 8. The total maximum source code size is 1 million bytes.
- 9. Submissions which rely on tables/caches built at time of compilation must contain code to deterministically reproduce those tables. This code must be able to be called at runtime.
This reproduction code is counted towards the total code size. If a table/cache cannot be built at compile time, then the time to build the table will be included in the total runtime, amortized over 10 thousand calls.
- 10. Submissions must pass the provided test suite and run with the provided benchmark.
Modifications to the test suite and benchmark are not allowed, except for adding/extended trait implementations for elliptic curves tested with the ec-divisors lib.
- 11. Submissions must score at least 20% better than the reference.
This is the baseline performance improvement target intended to disqualify trivial submissions.
- 12 Anonymous submissions are allowed.
JudgingSubmissions have a joint score based on:
- Their benchmarks while running on a machine with specs listed below
- Their cycle count from wasm-cycles
Machine specs (we may use a different machine with similar specs):
- AMD Ryzen 5600G (your code must not take advantage of the integrated graphics)
- Debian 12
- 16GB RAM
Submissions which allocate more than 96 MB of WASM pages will have their score decreased by 10% for each additional 32 MB allocated (allocating 96.1 MB will face a 10% penalty and allocating 128.1 MB will face a 20% penalty).
We reserve the right to select a winner based on our discretion, and rule out submissions for reasons we may not have identified above. For example, if the fastest code has issues we did not identify above, we may select the 2nd fastest code. We aim to ship the winning code in Monero.
The judges will be:
Judges provide a good-faith promise that we will not participate as contestants in the competition.
We may add judges in the future at our discretion.
If you have any questions, do not hesitate to ask in IRC/Matrix #monero-dev, or create an issue.
PrizesThe best submission for an optimized helioselene will be awarded 100 XMR.
The best solution for an optimized ec-divisors will be awarded 250 XMR.
How to get startedFor helioselene, visit helioselene-contest:
https://github.com/j-berman/fcmp-plus-plus-optimization-competition/blob/main/helioselene-contestFor ec-divisors, visit ec-divisors-contest:
https://github.com/j-berman/fcmp-plus-plus-optimization-competition/blob/main/ec-divisors-contestHow to submitWe will acknowledge receipt of your submission via a "thumbs up" reaction to your PR.
You may also submit a patch to @jberman:monero.social on Matrix:
https://matrix.to/#/@jberman:monero.social