barretenberg icon indicating copy to clipboard operation
barretenberg copied to clipboard

Reorganize and/or remove MsmSorter

Open ledwards2225 opened this issue 4 months ago • 0 comments

The MsmSorter class was designed to facilitate efficient commitment to polynomials with many repeated coefficients. The idea was to sort the scalars/points by scalar, sum the points sharing a common scalar, then perform the MSM using pippenger on the reduced inputs. This turns out to be not quite what we need since the primary polynomial where it might apply is z_perm (in the structured execution trace context), and there the constant coefficients appear in known "blocks" which can be explicitly extracted making sorting unnecessary.

Much of the key logic in this class was related to the batched affine addition algorithm. This has been duplicated (with some modifications) in a new class BatchedAffineAddition. If it seems worthwhile to keep the SortedMsm logic around, we could refactor it to utilize the more up to date and efficient logic in BatchedAffineAddition. Otherwise we can simply remove it altogether.

ledwards2225 avatar Oct 10 '24 18:10 ledwards2225