barretenberg
barretenberg copied to clipboard
Reorganize and/or remove MsmSorter
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.