RFC: Move MSM and FFT in this repo and offer a standard interface

[mratsim]

Overview

This RFC goal is facilitating contribution to Halo2 backend.

While trying to implement #163, in particular the "extended jacobian coordinates" steps, our team is significantly slowed down by having to deal with 2 different repos.

In particular, to accelerate MSM we need to improve the backend in halo2curves repo, but the benefit can only be benchmarked in halo2 which is a very clunky workflow.

Given that MSM is a significant bottleneck and focus point, there are likely ongoing changes that will be done by backend teams. In particular there are GPU provers running on Taiko testnet that uses a modified Halo2/Halo2curves and would be delighted to have a standard MSM/NTT API for acceleration.

Proposal

1. The Halo2-KZG proof system is split into:

   • an "engine" repo that implements proof systems
   • and a "backend" repo that exposes the primitives to implement the engine.

2. The backend repo should allow easy integration and benchmark of backends and accelerators
   for example I have identified the following accelerators focused backend that mirror halo2curves on GPU:

   • https://github.com/ingonyama-zk/icicle/
   • https://github.com/supranational/sppark
   • Applications for GPU-accelerated halo2 in Taiko grants:
     • [Grant Application]: SuperScalar - Taiko Prover Optimization taikoxyz/grants#35
     • [Grant Application]: ZK.WORK - GPU-based Taiko Prover Optimization taikoxyz/grants#68

   And a "frontend" like zkevm-circuit can be build on top.

3. Stretch goal:
   We use additive notation for elliptic curves not multiplicative notation, multi_exp should be multi_scalar_mul

Changes required

There are actually very few changes needed to implement the first part

• in halo2proofs/arithmetic.rs
  • Move MSM to halo2curves https://github.com/privacy-scaling-explorations/halo2/blob/fe71cd4647630d3af03d9cb72d301a431537974c/halo2_proofs/src/arithmetic.rs#L28-L174
  • Move FFT to halo2curves https://github.com/privacy-scaling-explorations/halo2/blob/fe71cd4647630d3af03d9cb72d301a431537974c/halo2_proofs/src/arithmetic.rs#L176-L289

Note: this will have the library depart from upstream Zcash, but this seems to have been an intent from the start as #29 by @kilic actually moves the MSM into halo2curves.

Furthermore, porting any MSM or FFT enhancement from Zcash Halo2-IPA should be easy as those are very self-contained functions.

API for accelerator extension

To be discussed, the idea is that by just exposing the right traits in a GPU repo like icicle or sppark (or even a CPU repo like blstrs or constantine)

Benefits:

• Easier to extend
• Easier to produce benchmarks and comparison between implementation
• Easier to do differential fuzzing of implementations
• Marketing:
  • the standard would make it easier to be used in papers for improvement comparisons.
  • this is a way for the library to gain traction and critical mass among GPU/FPGA accelerator solutions, and then as a backend for zkVMs and zkEVMs, which ultimately lead to more devs improving the library.

[kilic]

I totally agree and I also think we can even start with just copying MSM and FFT things to here from pse/halo2 then optimisations may come after

[mratsim]

Closed by merging privacy-scaling-explorations/halo2#86