Speeding up verification of digital signatures

[prezbo]

Wow! Impressive how fast you did this!

Thanks, but it is mostly the fact that the bouncy castle library has an EC point library built in.

Also, the formula just "worked".  I had expected an hour or two of debugging at least.

- I suppose that addition can be sped up in bounty castle because parameter 'A' is zero for the BC curve.

Dunno.  It looks like addition doesn't actually depend on the curve parameters, weirdly.

It should, but that's probably taken care of in the addition part of the code. I don't think you can do much better than what you've done. This article proposes some additional improvements on the naive double-and-add but I've just skimmed the paper so not sure if it's worth the effort.

[Altoidnerd]

You should send your work to the development mailing list.  This looks like something good.

The big blockchain problem is a serious one.  Great work...

Sorry that I can only help if its written in python, I'm a very bad programmer.

[TierNolan]

You should send your work to the development mailing list.  This looks like something good.

Well, a 2.5X improvement isn't that ground-breaking.

It would have to be much higher to make it worth it, due to the added risk.

[Altoidnerd]

It would help adoption.  The QT startup time is getting bad.  It would buy the core devs time to work another more permanent solution.  But I don't know how feasible this is without a fork or something.

basically, you're not gonna get core dev's attention here anymore.  But run it by them because it looks like you did your homework.  Thats my 2 bits.

[prezbo]

It would help adoption.  The QT startup time is getting bad.  It would buy the core devs time to work another more permanent solution.  But I don't know how feasible this is without a fork or something.

basically, you're not gonna get core dev's attention here anymore.  But run it by them because it looks like you did your homework.  Thats my 2 bits.

It wouldn't cause a fork, it's just another, more efficient version of checking signatures to the one already used - which is check every signature individually.

[Altoidnerd]

I highly encourage TierNolan to try to get some attention to this.  He can handle the mailing list I'd say he has the chops.

[gmaxwell]

It wouldn't cause a fork, it's just another, more efficient version of checking signatures to the one already used - which is check every signature individually.

There is risk in anything changed.

We get a 6x increase from changing from openssl (which is faster than bouncy castle) to libsecp256k1, but we've not switched to that it in the reference software in part because of concern for the correctness of the implementation as it is not very mature and has not had a lot of review. That also doesn't have the integration complexity of batch validation.

We (at least Sipa and I) were previously aware of batch validation and IIRC sipa experimented with it some for another curve.

Are you really getting a 2.5x while not having the y coordinate sign and doing combinatorial recovery?  If so thats really surprising to me.

Can you try implementing this on top of libsecp256k1? Getting a speedup on a very slow implementation— even though the speedup is purely algorithmic— is less interesting than getting it on a state of the art implementation.

[TierNolan]

Are you really getting a 2.5x while not having the y coordinate sign and doing combinatorial recovery?  If so thats really surprising to me.

No, it assumes that R is known.

For actual implementation, it would require that an odd/even bit is provided. 

The square root operation is an additional potential slow down.

Signatures that don't include this info could be marked as non-standard and have to be individually checked.  If it was non-standard to not include the info and the reference client included it, then most transactions would have the extra info.

Can you try implementing this on top of libsecp256k1? Getting a speedup on a very slow implementation— even though the speedup is purely algorithmic— is less interesting than getting it on a state of the art implementation.

I could have a look.  Is it worth it if R has to be provided?

[gmaxwell]

So, if you just need the sign of R.y and still get a reasonable speedup then maybe (e.g. with the sqrt cost). If you have to have the full value for R thats far less clear, as it would increase the signature size by 32 bytes, and thats not really acceptable. (Also even with R— I don't think you can avoid the sqrt because I think you need to check that R is actually on the curve, otherwise I think you'll create an attack)