-
Notifications
You must be signed in to change notification settings - Fork 7
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Optimize Eliptic Curve math for EdDSA-Poseidon #65
Comments
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
|
@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. @ozgurarmanc is currently working on it. cc @vplasencia (she is also working on other WASM packages). |
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). |
That could be the second step. We can open a good first issue for it on ZK-Kit.
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. |
Open Task RFP for Semaphore and Zupass
Executive Summary
Project Details
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
Administrative Details
Additional Information
Submission Details
The text was updated successfully, but these errors were encountered: