barretenberg
barretenberg copied to clipboard
structured polys: reduce amount of CRS points needed
Problem: with new structured poly PR, we require up to 1.5x CRS points than before
Breakdown of problem leading to more SRS points being requested:
- pippenger_unsafe_optimized_for_non_dyadic_polys allows for non-power-of-2 field amounts but requires power-of-2 SRS amounts
- this should be OK - but we may have a start_index which offsets this span. This means the power of 2 might be calculating from midway into the polynomial
- the worst case is we have a start_index() about half way through while we round it up to a power of 2, meaning it takes the full CRS amount of points (as pippenger assumes this) ~1.5x CRS points because
Solution candidates:
- we can live with this and add functionality to compute needed CRS points
- relax this either using the other pippenger (non-dyadic optimized one)
- relax pippenger to allow for these CRS points to be undefined (and can be considered 0 as the scalar is assumed to be 0)
- pass a PolynomialSpan instead of span to pippenger and not only consider > .size() as 0 but also checking both start and end index in the current zero-assuming code (see scalar_multiplication.cpp +253)