Commit 0cf9afe

Optimizing EIP-4844 transaction validation for mempool (using KZG proofs) (#5088) * Fix missing variables/funcs in validate_blob_transaction_wrapper() There is no `tx.message.blob_commitments` anymore, or `kzg_to_commitment()` * Introduce KZGProof as its own type instead of using KZGCommitment * Introduce high-level logic of new efficient transaction validation To validate a 4844 transaction in the mempool, the verifier checks that each provided KZG commitment matches the polynomial represented by the corresponding blob data. | d_1 | d_2 | d_3 | ... | d_4096 | -> commitment Before this patch, to do this validation, we reconstructed the commitment from the blob data (d_i above), and checked it against the provided commitment. This was expensive because computing a commitment from blob data (even using Lagrange basis) involves N scalar multiplications, where N is the number of field elements per blob. Initial benchmarking showed that this was about 40ms for N=4096 which was deemed too expensive. For more details see: https://hackmd.io/@protolambda/eip-4844-implementer-notes#Optimizations https://github.com/protolambda/go-ethereum/pull/4 In this patch, we speed this up by providing a KZG proof for each commitment. The verifier can check that proof to ensure that the KZG commitment matches the polynomial represented by the corresponding blob data. | d_1 | d_2 | d_3 | ... | d_4096 | -> commitment, proof To do so, we evaluate the blob data polynomial at a random point `x` to get a value `y`. We then use the KZG proof to ensure that the commited polynomial (i.e. the commitment) also evaluates to `y` at `x`. If the check passes, it means that the KZG commitment matches the polynomial represented by the blob data. This is significantly faster since evaluating the blob data polynomial at a random point using the Barycentric formula can be done efficiently with only field operations (see https://hackmd.io/@vbuterin/barycentric_evaluation). Then, verifying a KZG proof takes two pairing operations (which take about 0.6ms each). This brings the total verification cost to about 2 ms per blob. With some additional optimizations (using linear combination tricks as the ones linked above) we can batch all the blobs together into a single efficient verification, and hence verify the entire transaction in 2.5 ms. The same techniques can be used to efficiently verify blocks on the consensus side. * Introduce polynomial helper functions for transaction validation * Implement high-level logic of aggregated proof verification * Add helper functions for aggregated proof verification Also abstract `lincomb()` out of the `blob_to_kzg()` function to be used in the verification. * Fixes after review on the consensus PR

GitHub Diff