ECDSA signature optimization and more DoS prevention #1349

These 6 commits:

1. Implement an ECDSA signature cache, which should cut the amount of CPU time spent verifying signatures in half (because transaction signatures are verified before going into the memory pool and then again when the block is accepted). Please review that commit very carefully, since it is the very heart of transaction security.
2. Implement several "belt and suspenders" changes to prevent possible denial-of-service attacks involving sending orphan transactions (suggested by Sergio Demian Lerner) or transactions with lots of inputs.

Tested by:

• writing new unit tests, and stepping through the code in the debugger while running the new tests
• running the new code under valgrind for more than 24 hours on the main network

Blown up by 6d64a0bfed8636da4a0a5b7a4bf68cff2abbf035, after merging by hand it dies because key.cpp doesn't #include <sync.h>. Introduces a harmless looking signed compare warning key.cpp:388:3.

Have it running on a node now.

Code appears correct to me. Comments inline... IMO push those refactors into the tree immediately.

@jgarzik if your 'log-worthy event' comment is also on the oversized orphans (like 183 instead of 191), I thought the same thing.

both, really

@gmaxwell : I want to keep this pull based on 0.6.2 in case we decide we need a 0.6.3. @jgarzik : ACK, I'll fix the comments. I think encapsulation in a class is overkill. @SergioDemianLerner : excellent catch on vSpent, and I 100% agree this code needs extremely careful review and as much testing as we can throw at it. I also like your suggestion to only cache valid signatures; it has the added benefit of making the code a lot simpler.

ACK

Gavin: can you estimate the time it takes to verify a signature compared to the time it takes to get the result from the cache? There should be a factor of at least 100x between them, but the test code seems to disagree with this.

@SergioDemianLerner I'll isolate and benchmark the cache unit test to see why cached signatures are taking 50ms to validate. Note that all of the CScript interpreter machinery is still being run (I am testing/measuring at the VerifySignature() level, not a the CKey:: level).

What I did:

Used valgrind --tool=callgrind and hacked versions of test/DoS_tests.cpp to isolate and measure just the cached signature verification code.

What I found:

Two things slow down cached signature verification:

1. Decompressing compressed public keys. Using uncompressed public keys almost doubles performance (from 110ms to validate 500 inputs to 60ms). If we need/want to further optimize verification then a compressed->uncompressed cache would get a 25% or so speedup.

2. The remaining 60ms is dominated by the serializing/hashing done; if we needed/wanted to further optimize this code then having transactions cache their SIGHASH_whatever hashes might be worthwhile so they're not repeatedly recomputed. However, the transaction I'm using for this benchmark is not a typical transaction (it has 100 inputs), and the bottleneck for transaction verification might be somewhere else for more realistic transactions.

Finally, in the future very-high-level optimization schemes for transactions might be implemented; for example, if you have a peer that you can completely trust to give you only valid transactions then you could skip all verifications and take it on faith that all transactions from that peer are valid (with, perhaps, a random 1-in-100 audit to make sure the peer hasn't been corrupted). So spending a lot of time on micro-optimizations may not be the best way forward.

Great! A lot of useful information! Remember that I had suggested caching (outpoint,script)->bool and not the signature verification (signature,pubkey)->bool to get all possible speedups.

@SergioDemianLerner Thats actually a bad idea. Otherwise I can just create endless numbers of scripts of the form push $randomnumber pop [normal script] with no computation on my part in order to bypass the cache.

We're caching only the scripts that verify ok so that kind of attack does not work.

Also I had suggested caching (outpoint,hash(script)) -> bool to reduce memory consumption.

@SergioDemianLerner PUSH $randomnumber POP {normal script} will also validate if {normal script} would have also validated— but it will have a different hash.

See follow-up pull #1380.

@gmaxwell You are right. Scripts cannot be easily cached. We would need an pushdown automata parser and optimizer to compress scripts and erase all garbage. It would be interesting to program such an algorithm to allow clients to "standarize" scripts, detect and remove hidden messages while transactions are passed from peer to peer. We may even create a transaction antivirus !! (just joking, I remember transaction signature do not withstands such modifications...)

Although IsStandard() check would prevent "PUSH $randomnumber POP {normal script}" scripts from being forwarded, so it may be possible to cache at that level too.

@SergioDemianLerner I picked a toy example, and besides, we wouldn't want to adopt a design which strongly discouraged expanding IsStandard in the future.

ACK.