Optimize verify_kzg_proof_multi_impl
#3584
Conversation
|
While this PR does provide a pretty big speed up in cell verification times, we've decided that we would rather have a slower but more readable spec. This implementation is more complex than we'd like. Also, cell verification is not the bottleneck in the tests; proof generation is by far the slowest (most expensive) part. I'm going to close this PR. If in the future we decide this PR would be useful, we can re-open it then. |
|
If implementations were to use this as an optional optimization, would they still be compliant with the current spec, is there a change in security-level? |
|
@mratsim Yes, it would still be compliant. We expect implementations to use optimizations. With that in mind, the reference tests (which are a work in progress) should help identify issues. I don't believe this changes any security assumptions. |
Note: this only pertains to peerDAS (EIP-7594). When adding a new
reverse_bits_limitedhelper function I noticed thatverify_kzg_proof_multi_implwas pretty inefficient. This new code is originally based on @dankrad's implementation ofcheck_proof_multiin the eth-research repo. We use this new implementation in c-kzg-4844's das branch.On my system, it took 613ms to verify a single cell proof with the old implementation. With this PR, it takes 22ms. It could be even faster if the roots of unity were pre-computed, but that only takes about 5ms so I don't think it's worth changing.
Fixes #3575.