Proposal: Optimize Elliptic Curve math for EdDSA-Poseidon

[aagbotemi]

General Grant Proposal

• Project: Optimize Elliptic Curve math for EdDSA-Poseidon https://github.com/privacy-scaling-explorations/acceleration-program/issues/65

Project Overview :page_facing_up:

Overview

This project aims to optimize the underlying elliptic curve code for EdDSA-Poseidon signing and verification in the zk-kit library. The primary focus will be on improving performance through algorithmic enhancements and implementation in Rust with WebAssembly (WASM) compilation, while maintaining compatibility with the existing TypeScript interface.

Project Details

The project will address the performance bottlenecks in the current implementation of EdDSA-Poseidon, specifically targeting the elliptic curve operations that dominate the computation time. Key aspects of the project include:

1. Algorithmic Improvements:

   • Modify the signing process to reuse keygen steps, reducing the number of elliptic curve multiplications from 3 to 1.
   • Implement an optimized algorithm for the "inv" function in the baby-jubjub library, which calculates the multiplicative inverse.
   • Explore and implement Montgomery Ladder-based algorithms for further performance gains.

2. Rust Implementation:

   • Reimplement the core elliptic curve operations in Rust, focusing on the Baby-JubJub curve.
   • Utilize Rust's performance characteristics and safety features to create a robust and efficient implementation.

3. WebAssembly Compilation:

   • Compile the Rust implementation to WebAssembly to enable high-performance execution in browser environments.
   • Create a TypeScript wrapper to seamlessly integrate the WASM module with the existing zk-kit library.

4. Compatibility and Fallback:

   • Maintain the existing pure TypeScript implementation as a fallback for environments where WASM is unavailable.
   • Implement a runtime check to use the optimized WASM version when available, falling back to the TypeScript version when necessary.

5. Benchmarking and Validation:

   • Develop a comprehensive suite of benchmarks to measure performance improvements across various operations and environments.
   • Ensure that all optimizations maintain the security properties of the original implementation.

The technology stack will include:

• Rust for core implementation
• WebAssembly (WASM) for browser compatibility
• TypeScript for wrapper and fallback implementation
• zk-kit library integration

Team :busts_in_silhouette:

Team members

• Name: Abiodun Awoyemi
• Email: aabiodunawoyemi@gmail.com
• Telegram: abiodunAWOYEMI
• Discord: gbotemi

Team Website

• https://github.com/aagbotemi

Team's experience

I am an open source developer with a strong focus on cryptography and zero-knowledge proofs. My experience is particularly relevant to this project:

• Developed a comprehensive collection of cryptographic and zero-knowledge algorithms implemented from scratch in Rust, including:
  • Elliptic Curve implementations, directly applicable to optimizing EdDSA-Poseidon
  • Digital Signature schemes such as ECDSA and Schnorr, providing insights for EdDSA optimization
  • Finite Field arithmetic, crucial for efficient elliptic curve operations
  • Sumcheck Protocol and GKR Protocol, demonstrating expertise in advanced cryptographic constructions
  • Implementation of encryption and decryption algorithms for various cryptosystems Key Exchange Protocols like Diffie-Hellman and RSA, showcasing understanding of secure communication principles

This hands-on experience with low-level cryptographic implementations in Rust positions me well to tackle the optimization challenges of EdDSA-Poseidon, particularly in reimplementing core operations for improved performance and WASM compatibility.

Team Code Repos

• https://github.com/aagbotemi

Development Roadmap :nut_and_bolt:

Overview

• Total Estimated Duration: 2.5 months
• Total Estimated Working Hours: 400 hours
• Full-time equivalent (FTE): 1
• Expected Start Date: October 1, 2024
• Expected End Date: December 15, 2024

Milestone 1: Algorithmic Optimization and Rust Implementation

• Estimated Duration: 4 weeks
• FTE: 1
• Estimated delivery date: October 28, 2024

Deliverables and Specifications

1. Optimized signing algorithm implementation in Rust
   • Reuse keygen steps to reduce EC multiplications from 3 to 1
   • Implement and benchmark Montgomery Ladder-based algorithm
2. Optimized "inv" function for multiplicative inverse calculation
   • Research and implement the most efficient algorithm for the Baby-JubJub curve
3. Core Baby-JubJub curve operations implemented in Rust
   • Include all necessary operations for EdDSA-Poseidon
4. Preliminary benchmarks comparing new Rust implementation to original TypeScript version
5. Documentation of algorithmic improvements and implementation details

Milestone 2: WASM Compilation and TypeScript Integration

• Estimated Duration: 4 weeks
• FTE: 1
• Estimated delivery date: November 25, 2024

Deliverables and Specifications

1. WebAssembly compilation of Rust implementation
   • Ensure compatibility with major browsers and Node.js environments
2. TypeScript wrapper for WASM module
   • Seamless integration with existing zk-kit API
3. Fallback mechanism to pure TypeScript implementation
   • Runtime detection of WASM support
   • Automatic fallback to TypeScript version when WASM is unavailable

Milestone 3: Optimization, Documentation, and Final Delivery

• Estimated Duration: 2 weeks
• FTE: 1
• Estimated delivery date: November 15, 2024

Deliverables and Specifications

1. Comprehensive documentation
2. Example applications demonstrating integration and performance benefits
3. Blog post or technical article describing the optimization process and results

[cedoor]

Hi @aagbotemi, it seems that several parts of this proposal are already being developed for zk-kit as open issues.

We are therefore closing this issue https://github.com/privacy-scaling-explorations/acceleration-program/issues/65, and adding open issues on zk-kit for the remaining tasks, which are too small for a grant.

Sorry for the late notice.