ECDsa Verification Speed

[pmlyon]

Hi, I'm working on a c# node implementation and I have a question around the verification of ECDsa signatures. I'm using the BouncyCastle library and calling ECDsaSigner.VerifySignature is taking ~100ms on a quad-core i5-2500K cpu. This means that if I max out all 4 cores I can process about 40 signatures per second. This seems extremely slow to me but I've not used ECDsa before. Does this seem like a reasonable signature verification speed? The wiki scalability page mentions being able to do tens of thousands of signature verifications per second.

Thanks,

Paul

[piotr_n]

For such a CPU OpenSSL needs ~1ms per operation. Even less, if you use 64 bit arch.
So I would say that 100ms is not reasonable.

[Remember remember the 5th of November]

If this was implemented in C, it would be faster. I can see how the Java implementation can be slower.

[jackjack]

You can try jasvet to see how much time it takes in Python

[piotr_n]

I once had similar problem in Go - it's a pretty optimal compiler, but its current implementation of the big numbers lib is far away from optimal.

So for me it was like 10ms per op, which was still to long, so I decided to use the openssl implementation.
For a moment I even had a solution with a TCP server (written in C, with openssl) that was doing the ECDSAs for my actual app. That was pretty crazy, though it worked..
Later I figured out how to combine the openssl lib with my go app and ever since then it works as fast as I needed.

Most of the languages these days allow creation of wrappers for native libs - that's probably the best way for you to go as well.

[pmlyon]

Thanks everyone! What I have now is functional at least; it's good to know that the performance can be improved down the line.

P.S. Does anyone have much interest in a c# implementation? I started this mostly to educate myself, but I'm making more progress than I was expecting.

[piotr_n]

P.S. Does anyone have much interest in a c# implementation? I started this mostly to educate myself, but I'm making more progress than I was expecting.

If you started, just finish it - turn it into a full node.
It will give you a great satisfaction and the community need other clients.
Bittorrent would have never became a success if people would have stuck to the original python download dialogs.

Personally I believe that the future of bitcoin is not in the official client - the official core is just too important and no sane developer will want to risk breaking it, which will surely paralyze its further development. Since it will be harder and harder to add new features there, sooner or later alternative clients will just beat it on the functionality and a speed of development.

As for your further possible concerns, since I've been there I can tell you that the biggest challenge, besides the ECDSA performance, is a proper database for UTXO.
Forget about anything SQL based. Unless you want to make a node for testnet only

[pmlyon]

Heh, SQL Server is what I'm currently using, but I haven't gotten around to implementing the UTXO yet. We'll see how that goes.

[Mike Hearn]

The fastest implementation is this one:

https://github.com/sipa/secp256k1

[piotr_n]

The fastest implementation is this one:

https://github.com/sipa/secp256k1

Wow, it's great.
187us versus OpenSSL's 1008us, on my test laptop.

Sipa for president!

[pmlyon]

Wow, that's gotta be near 1000x better performance than I'm currently getting. It sucks that my verification speed is going to hamstrung by this for now, but I've got a million others things left to implement anyway.

[Remember remember the 5th of November]

The fastest implementation is this one:

https://github.com/sipa/secp256k1

I don't suppose I can use this library for even speedier address creation?

[jackjack]

The fastest implementation is this one:

https://github.com/sipa/secp256k1

I don't suppose I can use this library for even speedier address creation?

If you mean private key -> public key (or address), I'm sure you can
If you mean creating a private key, no

[riplin]

Regarding that secp256k1 library,


I've been trying to get it to compile in Visual Studio, but there are some issues with it, namely the secp256k1_fe_mul_inner and secp256k1_fe_sqr_inner inner have a sysv_abi calling convention, that VS doesn't understand and it's using __int128 that VS doesn't support.

Maybe I can get something to work via MingW, but I'll save that for another day.

Edit: defining field 10x26 looks promising.

[piotr_n]

Regarding that secp256k1 library,


I've been trying to get it to compile in Visual Studio, but there are some issues with it, namely the secp256k1_fe_mul_inner and secp256k1_fe_sqr_inner inner have a sysv_abi calling convention, that VS doesn't understand and it's using __int128 that VS doesn't support.

Maybe I can get something to work via MingW, but I'll save that for another day.

Edit: defining field 10x26 looks promising.

It works fine in mingw.
You just need some changes in the config script and a slightly different Makefile.
See build_windows.txt in my fork: https://github.com/piotrnar/secp256k1

[MatthewLM]

A faster and smaller alternative to OpenSSL would be nice, but does sipa's library implement all of the OpenSSL quirks that are necessary to implement a full bitcoin node? Also has anyone thought of a GPU library for the ECDSA code?

[piotr_n]

A faster and smaller alternative to OpenSSL would be nice, but does sipa's library implement all of the OpenSSL quirks that are necessary to implement a full bitcoin node?

The only thing except ECDSA are SHA256 and RIMP160 hashing funcs, but both are easy to implement without OpenSSL.

Though from what I heard, they are currently busy adding some X509 stuff, so eventually it will need OpenSSL even more. Unless Terminator will get Gavin's ass first, in which case there may be some more time to see the reference code with no OpenSSL dependency.

[riplin]

Regarding that secp256k1 library,


I've been trying to get it to compile in Visual Studio, but there are some issues with it, namely the secp256k1_fe_mul_inner and secp256k1_fe_sqr_inner inner have a sysv_abi calling convention, that VS doesn't understand and it's using __int128 that VS doesn't support.

Maybe I can get something to work via MingW, but I'll save that for another day.

Edit: defining field 10x26 looks promising.

It works fine in mingw.
You just need some changes in the config script and a slightly different Makefile.
See build_windows.txt in my fork: https://github.com/piotrnar/secp256k1

I managed to get it to compile in Visual Studio. 32bit right now because 64bit OpenSSL seems to be giving me some linker trouble (_ prefix on the BN_* functions). Haven't had the time to look at that yet.

[piotr_n]

I managed to get it to compile in Visual Studio. 32bit right now because 64bit OpenSSL seems to be giving me some linker trouble (_ prefix on the BN_* functions). Haven't had the time to look at that yet.

We can only appeal to spia to make a version without openssl/gmp dependencies, which would be just perfect.

[runeks]

Hi, I'm working on a c# node implementation and I have a question around the verification of ECDsa signatures. I'm using the BouncyCastle library and calling ECDsaSigner.VerifySignature is taking ~100ms on a quad-core i5-2500K cpu. This means that if I max out all 4 cores I can process about 40 signatures per second. This seems extremely slow to me but I've not used ECDsa before. Does this seem like a reasonable signature verification speed? The wiki scalability page mentions being able to do tens of thousands of signature verifications per second.

Thanks,

Paul

If you can find C# bindings for OpenSSL, that will greatly speed things up. There's this, although I haven't tried it. It does add the clutter of OpenSSL though (large dependency).