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.

[artwyman]

Based on parallel work elsewhere, I think there area also opportunities for algorithmic improvements here, not just improvements based on AssemblyScript/WASM optimization. We just got a big speedup in an embedded C implementation of signing by switching to Mbed-TLS code with an algorithm based on a Montgomery Ladder. We had to adapt it to the Baby-JubJub curve

• Mbed-TLS source came from here: https://github.com/Mbed-TLS/mbedtls/pull/5819
• Baby-Jubjub code for signing ended up here: https://github.com/antimatter15/microPOD/blob/main/DuckV4/pod_util.h#L300

[cedoor]

@artwyman I think this proposal can actually be moved to zk-kit as the second part of this issue: https://github.com/privacy-scaling-explorations/zk-kit.rust/issues/9.

@ozgurarmanc is currently working on it.

cc @vplasencia (she is also working on other WASM packages).

[artwyman]

@artwyman I think this proposal can actually be moved to zk-kit as the second part of this issue: privacy-scaling-explorations/zk-kit.rust#9.

Sounds great! I've subscribed to that issue, though I only see mention of building a compatible rust crate. Is there implied work to make that rust implementation available in JS/TS via WASM? That would meet our optimization needs, though I'd prefer if zk-kit provided the TS wrapper to deal with the mechanics of loading/running WASM. I'm not familiar with how to do that.

Also as an aside, if WASM is the approach to optimization, it might still be valuable to provide the pure-TypeScript version too (as a separate package). There are some environments where WASM is unavailable. We've run into that in Zupass for iPhones in "lockdown mode" which disable WASM. I'm not sure we'll do this, but I could imagine someday having to write some code with an if statement to use a fast impl if WASM is available, or the slower impl if not. Note that Zupass is always going to require WASM for things like making proofs, but I could imagine wanting basic functionality (like login and viewing tickets) to work without WASM, and that basic functionality depends on EdDSA signatures (or after we finish upgrading to Semaphore V4 it will).

[cedoor]

Is there implied work to make that rust implementation available in JS/TS via WASM?

That could be the second step. We can open a good first issue for it on ZK-Kit.

It might still be valuable to provide the pure-TypeScript version too.

Sure, we can still provide the JS library we already have on zk-kit: https://github.com/privacy-scaling-explorations/zk-kit/tree/main/packages/eddsa-poseidon.