Make sure that `g1_lincomb()` handles input zero points correctly about c-kzg-4844 HOT 5 CLOSED

Weeding out the zeros does look tricky, though maybe it's worth benchmarking if it's worthwhile? One way to do it would be to make a copy of p (and coeffs), then make a single pass over it swapping any zeros (and the corresponding coeff) with the last element.

from c-kzg-4844.

Wrote a unittest that demonstrates the bug: 8b7ef36

And a demontration of the simple fix: 84c9ef9

Marked the PR as draft for now. Will give a shot at the "weed out zeroes" approach later.

from c-kzg-4844.

Weeding out the zeros does look tricky, though maybe it's worth benchmarking if it's worthwhile? One way to do it would be to make a copy of p (and coeffs), then make a single pass over it swapping any zeros (and the corresponding coeff) with the last element.

I did not feel smart enough to do the swapping strategy, so I implemented a more naive weeding out strategy here: asn-d6@42f6e18 That was a quick implementation for benchmarking; the logic is a bit dicey so there might be bugs.

The benefits of the weeding out strategy start to be visible in batch verify with n=16 where we get an 8% speed boost, and at n=32 we get a 10% speed boost. For smaller n the performance is almost identical (after all we always do the naive MSM for n < 8).

My intuition tells me to go with the simple strategy of #140 upstream for now, and if this performance ever becomes problematic we can switch to the more involved weeding out strategy. After all, IIUC we mainly care for mempool verification performance where transactions are not gonna have multiple blobs.

from c-kzg-4844.

Here is a proper implementation of the weed out strategy: #156

I would appreciate a review here as this significantly complicates the logic of g1_lincomb()
/cc @jtraglia @xrchz @dankrad

from c-kzg-4844.

Closing this in favor of #156 (comment)

from c-kzg-4844.