The first commit is a rebased version of Hal's feb 2011 patch. The second commit improves the code a bit (precalculate constants, and use BN_CTX_get for temporary values).
This reduces reindexing time for the first 210k blocks (script checks enabled everywhere, 4 verification threads, -dbcache=900) from 1h14m to 1h1m on my system.
I don't think the 20% speedup is worth the extra code complexity. I could be convinced if there are some EC crypto experts hanging around who will chime in and say "oh, yeah, that's an obvious optimization and implementation looks correct...."
It seems to me that this type of low-level speedup would be better implemented in OpenSSL. I don't know if they would accept a patch to speed up one curve or not, but ideally I think that is where this code belongs.
Hal claims that it can be increased to 40% with some other changes, but they weren't immediately clear to me. I think Pieter's plan was to get this in (as it has the structural changes) and then talk to an EC expert he may have access to about doing the rest. That might satisfy both your concerns.
I would note that script checking all txn with Hal is similar in performance to script skipping before the checkpoint without Hal (if not faster). In terms of the uncertainty wrt security implications I'd prefer the former.
I was a little over eager in my last claim there: syncing from start to 210000 the current parallel checking branch without hal is 23:58 while without checkpoints but with hal it's 37:10 for me (47:21 hal-less).
If we decide to include low-level crypto code like this, we could just as well include all the ECDSA code (for the particular curve that we use) so that we can build with OpenSSL built without ECDSA.
Refactored the optimized algorithm into an almost exact copy of OpenSSL's own ecdsa_do_verify() function, but using an optimized version of EC_POINT_mul().
New commit: if compiled with -DVERIFY_OPTIMIZED_SECP256K1, checks will be compiled in that compare the generic OpenSSL code with the specialized one. It's not enabled by default, but I verified it for the entire current block chain & unit tests.
They're independent.
Added verification code for checking k == k1 + lambda_k2 and for checking p2 == lambda_p. Verified against unit tests and testnet.
EDIT: and mainnet now as well.
New commit: implemented a small improvement suggested by Hal.
Added a commit to build the core .o files for tests separately, and add - DVERIFY_OPTIMIZED_SECP256K1 to them, so the unit tests now compare the internal values in ECDSA verification between optimized and non-optimized code.
Added a fuzzer that compares intermediate values during validation in optimized and non-optimized code, for message hashes with a random 1-bit difference for every real check.
Automatic sanity-testing: PASSED, see http://jenkins.bluematt.me/pull-tester/1f369d512b5b5c66e9623d2eaf9692eee9b11d36 for binaries and test log.
It would be good if someone checks this new implementation against timing attacks. Systems that automatically sign transactions (like exchanges) may be vulnerable to key recovery using timing attacks.
This code isn't used for signing.
Ok, I will check against specially crafted pubkeys/signatures in a few weeks. I've found bugs in other implementations.
@SergioDemianLerner: thanks!
Rebased.
Added precomputation of G (doable as a separate pull if necessary), which improves verify performance by 2-3% (consistently), and turn off Hal's optimizations by default; -turbo turns them on.
How do these pulls get tagged updated, when I see no changes here? Rebase?
I don't intend to keep this updated, as I'm working on a separately library that implements ECDSA directly, with much more optimizations than this pullreq does. See http://github.com/sipa/secp256k1
You missunderstood my comment, this pull or issue was listed updated for me and I asked what made Github think it was updated. I think your work on this is great, but my intention was just to understand Github here.