Optimize Eliptic Curve math for EdDSA-Poseidon

[artwyman]

Open Task RFP for Semaphore and Zupass

Executive Summary

• Project Overview: The underlying elliptic curve code for EdDSA-Poseidon signing and verification needs optimization. Porting to AssemblyScript or WASM seems a promising way to make it faster.

Project Details

• Motivation: Semaphore V4 is based on EdDSA-Poseidon signatures, using the TypeScript implementation in zk-kit. Zupass is adopting Semaphore V4 as it's primary notion of identity, and also using EdDSA-Poseidon signatures for the POD (Provable Object Datatype) format (see zupass.org/pod). In my testing, signing takes ~51ms (in a browser on my MacBook), of which 47ms is the 3 elliptic curve multiplies. 47ms is okay for a user action which has to sign/verify one thing, but could become problematic in a high-frequency server environment, or in a client which is latency sensitive (e.g. a 60 FPS graphics update has 16ms/frame)

By reusing keygen steps, it would be possible to reduce that to 1 multiply. Signature verification, however, is always going to be 2 EC multipies. The vast majority of that time is in the "inv" function in the baby-jubjub library (which I assume is calculating multiplicative inverse). That library is straightforward TypeScript, and probably a good candidate for porting to a more optimal algorithm implemented in a more hardware-friendly way (AssemblyScript, WASM).

There is prior art of WASM-optimized versions of similar algorithms in circomlibjs.

• Scope of Work: Profile EdDSA signing and verification, optimize as much as possible.

• Expected Outcomes: Optimized version of zk-kit/baby-jubjub and zk-kit/eddsa-poseidon

CC @cedoor to clarify remaining details below.

Qualifications

• Skills Required: Elliptic curve cryptography, performance profiling, TypeScript
• Preferred Qualifications: AssemblyScript, WebAssembly

Administrative Details

• Grant Liaison(s): [Name, GitHub, email of the person(s) responsible for evaluating and keeping track of this project.]
• Estimated Project Duration: [Timeframe for project completion, including any key deadlines.]
• Project Complexity: [Rate the project's difficulty level as Easy, Medium, or Hard. Explain the reasons for this.]

Additional Information

• Proposed by @artwyman on behalf of the Zupass team.

Submission Details

• Proposal Deadline: The deadline for submitting proposals is the end of this round of the Acceleration Program. Refer to current round
• Submission Instructions: Please submit your proposal as an issue and link back to this issue in your proposal. Refer to proposal template for more details.