Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

structured polys: reduce amount of CRS points needed #1097

Closed
ludamad opened this issue Sep 10, 2024 · 1 comment · Fixed by AztecProtocol/aztec-packages#9098
Closed

structured polys: reduce amount of CRS points needed #1097

ludamad opened this issue Sep 10, 2024 · 1 comment · Fixed by AztecProtocol/aztec-packages#9098
Assignees
@lucasxia01
Milestone
Memory Optimizations

Comments

@ludamad
Copy link
Collaborator

ludamad commented Sep 10, 2024 •
edited
Loading

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)
@lucasxia01 lucasxia01 self-assigned this Sep 13, 2024
@lucasxia01
Copy link
Contributor

From discussion, Adam and I think the 4th option is the best in terms of fully fixing the amount of SRS points we get, maintaining efficiency, and also in terms of simplicity

@ludamad ludamad mentioned this issue Sep 24, 2024
Closed
@lucasxia01 lucasxia01 mentioned this issue Sep 26, 2024
Merged
@lucasxia01 lucasxia01 added this to the Memory Optimizations milestone Oct 4, 2024
@lucasxia01 lucasxia01 mentioned this issue Oct 9, 2024
Merged
AztecBot pushed a commit that referenced this issue Oct 16, 2024
@lucasxia01 @AztecBot
fix: Reduce SRS size back to normal (#9098)
23afa26 
Resolves #1097.

Previously, we had to bump up SRS sizes to 1.5x the dyadic circuit size
because structured polynomials meant that we could commit starting from
the start_index of the polynomial, but because pippenger likes a power
of 2 points, that meant that we sometimes exceeded the
dyadic_circuit_size during a roundup to a power of 2.

This PR fixes this by using PolynomialSpans to store the scalars. Note
that these scalars do not necessarily represent polynomials anymore, so
maybe this object can be renamed. The PolynomialSpan allows us to store
a start_index with the scalars, where the start_index here means the
offset into the span of points that the scalars start at. For example,
if we are committing to a polynomial which starts at index 13, and has
13 length. The points we will use will now be [10, 26) instead of [13,
29) previously. The start_index here would be 3 because the scalars
start at 13, which is 3 after the points start.

The range for the points is chosen to the be the earliest power of 2
window that fits the scalars, meaning we try to shift it as left as
possible. This means that will never exceed the dyadic_circuit_size as a
result, so we can keep the old (and good) SRS sizes.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@lucasxia01 lucasxia01

Labels
None yet
Projects
None yet
Milestone
Memory Optimizations
Development

Successfully merging a pull request may close this issue.

fix: Reduce SRS size back to normal AztecProtocol/aztec-packages
2 participants
@ludamad @lucasxia01