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
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.
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:
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.
Overview
This RFC goal is facilitating contribution to Halo2 backend.
While trying to implement https://github.com/privacy-scaling-explorations/halo2curves/issues/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
The Halo2-KZG proof system is split into:
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:
And a "frontend" like zkevm-circuit can be build on top.
Stretch goal: We use additive notation for elliptic curves not multiplicative notation,
multi_exp
should bemulti_scalar_mul
Changes required
There are actually very few changes needed to implement the first part
Note: this will have the library depart from upstream Zcash, but this seems to have been an intent from the start as https://github.com/privacy-scaling-explorations/halo2curves/pull/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: