Faster computation of quotient polynomial for large rotation sets #107
Comments
|
IIRC the max Rotation we have is 20something. Maybe this was reduced in the last months. @han0110 will be able to clarify. From there we can judge whether to implement this or not. |
|
In that case since N is around 2^20 anyways probably there's no immediate need. |
|
I completelly agree! And wouldn't be harmfull at all. So definitely worth exploring at some point. I'm not sure if we will prioritize this item. But definitely will be happy to recieve PRs implementing it! |
…-hk/dev-feature/gl-112-implement-generic-range-check Implement generic range check
…-hk/dev-feature/53-gen-eccc Implement Ecc Chip for Pluto ... and Vesta and Eris # Project Context This issue corresponds to the Milestone 3 updated SOW task "New: Extend EccChip to support Pluto". There is no corresponding GitHub issue, since this is the Pluto/Eris analog of supporting Pallas, which was the starting state. However, the work for this issue overlaps significantly with SOW task "zcash#578: Extend EccChip to support ~~Vesta~~ Eris" ([zcash#578](zcash#578)), since it seems easiest to just generalize to all curves at the same time. So, while we only need to ensure Pluto support for Milestone 3, the strategy we're using also gives Eris and Vesta support "for free". This builds on top of privacy-scaling-explorations#145 directly, depends directly on privacy-scaling-explorations#143 and privacy-scaling-explorations#144 as well, and is the culmination of generalization work that started at a lower level with privacy-scaling-explorations#101, privacy-scaling-explorations#107, and privacy-scaling-explorations#114. The corresponding Galois internal issue is [Galois#53](https://gitlab-ext.galois.com/iog-midnight/halo2/-/issues/53). # Issue Description Generalize the Ecc Chip to arbitrary curves, allowing any assumptions that apply to all of Pallas, Vesta, Pluto, and Eris. This work is broken up into several subtasks, concerned with updating the major components of the Ecc Chip ([vbsm](privacy-scaling-explorations#143), [fbsm](privacy-scaling-explorations#145), and [point witnessing](privacy-scaling-explorations#144)), along with the final work here of updating the full Ecc Chip to use all of the updated components, have tests for all curves, and provide instantiations for all curves. Behind the scenes there are various traits associated with the vbsm and fbsm generalizations, but the final Ecc Chip interface exposes `EccCurve` and `EccField` as the traits required for curves and fields used with Ecc Chip (and of course these traits are implemented for Pallas, Vesta, Pluto, Eris, and their fields).
|
It seems that this optimization wouldn't make an improvement in most common cases (where R< logN). |
halo2/halo2_proofs/src/poly/kzg/multiopen/shplonk/prover.rs
Line 25 in 246ce4e
The current division algorithm is O(N * R) where N is degree of polynomial and R is size of rotation set. For small R this is optimal, but as an improvement for larger R we may consider adding a separate FFT-based algorithm to do it in O(N log N). Just flagging this as a possibility, maybe in practice no one uses close to log N number of rotations.
Here's a random reference implementation with further references: https://stackoverflow.com/a/44854935
The text was updated successfully, but these errors were encountered: