and libsecp256k1 offers 5x validation speeds.
Okay, I've asked around on IRC and got this:
in order to sign or verify the tx, each input has to construct a special version of the tx and hash it. so if there are n inputs there are nxn hashes to be done. hence quadratic scaling.
the TLDR I believe is: ecdsa operations are the most computationally expensive part of verifying transactions, for normal, small size transactions, but they scale linearly with the size (number of inputs).whereas if a transaction in current bitcoin has tons of inputs, the bottleneck moves over to the hashing/preparing data to to be signed, because that time depends on the *square* of the number of inputs.
so usually it's ultra small, but it blows up for large N inputs.
Why doesn't libsecp256k1 have an effect on this?
because libsecp256k1 is an ECC library so it's only the "ecdsa" part in the above.
Hopefully this helps, albeit I doubt that many are going to understand it. It certainly isn't easy.
Luada, again we owe you a debt of gratitude. You do the work the rest of us are too lazy to do. Now I am beginning to understand why the verification process scales quadratic; not that me understanding matters per se but it is nice to know.