Given a set of MSM inputs {scalar, point}, sort by scalar, sum the points that share a scalar, then perform the MSM with the resulting set of unique scalars. This is something we want to do anyway but it's especially critical in conjunction with the structured trace because certain polynomials, e.g. Z_permutation, will have large constant regions (i.e. in the "dead" space within the fixed blocks) and thus committing to them will be much more efficient with this optimization.
Note: this work should include special handling for points multiplied by 0. The issue is to ensure that structured versions of polynomials are as cheap to commit to as their unstructured counterparts. This should almost be automatically handled by the MSM sorting optimization. We just need to make sure we're not doing any work only to multiply things by 0, which is what we might do if we don't have particular handling for 0 scalars in the MSM routines. (e.g. we don't want to sum all of the points with scalar 0 then multiply the result by 0. Just ignore the points with 0 scalars to begin with)
Given a set of MSM inputs {scalar, point}, sort by scalar, sum the points that share a scalar, then perform the MSM with the resulting set of unique scalars. This is something we want to do anyway but it's especially critical in conjunction with the structured trace because certain polynomials, e.g. Z_permutation, will have large constant regions (i.e. in the "dead" space within the fixed blocks) and thus committing to them will be much more efficient with this optimization.
Note: this work should include special handling for points multiplied by 0. The issue is to ensure that structured versions of polynomials are as cheap to commit to as their unstructured counterparts. This should almost be automatically handled by the MSM sorting optimization. We just need to make sure we're not doing any work only to multiply things by 0, which is what we might do if we don't have particular handling for 0 scalars in the MSM routines. (e.g. we don't want to sum all of the points with scalar 0 then multiply the result by 0. Just ignore the points with 0 scalars to begin with)