barretenberg icon indicating copy to clipboard operation
barretenberg copied to clipboard

structured polys: reduce amount of CRS points needed

Open ludamad opened this issue 5 months ago • 1 comments

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)

ludamad avatar Sep 10 '24 15:09 ludamad