Bitcoin Forum

Bitcoin => Development & Technical Discussion => Topic started by: pmlyon on June 17, 2013, 01:03:44 PM



Title: ECDsa Verification Speed
Post by: pmlyon on June 17, 2013, 01:03:44 PM
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


Title: Re: ECDsa Verification Speed
Post by: piotr_n on June 17, 2013, 02:08:46 PM
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.


Title: Re: ECDsa Verification Speed
Post by: Remember remember the 5th of November on June 17, 2013, 02:13:54 PM
If this was implemented in C, it would be faster. I can see how the Java implementation can be slower.


Title: Re: ECDsa Verification Speed
Post by: jackjack on June 17, 2013, 02:17:57 PM
You can try jasvet to see how much time it takes in Python


Title: Re: ECDsa Verification Speed
Post by: piotr_n on June 17, 2013, 02:43:43 PM
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.


Title: Re: ECDsa Verification Speed
Post by: pmlyon on June 17, 2013, 04:21:32 PM
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.


Title: Re: ECDsa Verification Speed
Post by: piotr_n on June 17, 2013, 04:28:27 PM
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 :)


Title: Re: ECDsa Verification Speed
Post by: pmlyon on June 17, 2013, 04:31:15 PM
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. :)


Title: Re: ECDsa Verification Speed
Post by: Mike Hearn on June 18, 2013, 09:24:20 AM
The fastest implementation is this one:

https://github.com/sipa/secp256k1


Title: Re: ECDsa Verification Speed
Post by: piotr_n on June 18, 2013, 10:44:41 AM
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! :)


Title: Re: ECDsa Verification Speed
Post by: pmlyon on June 18, 2013, 11:40:37 AM
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. :)


Title: Re: ECDsa Verification Speed
Post by: Remember remember the 5th of November on June 18, 2013, 11:42:43 AM
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?


Title: Re: ECDsa Verification Speed
Post by: jackjack on June 18, 2013, 11:46:54 AM
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


Title: Re: ECDsa Verification Speed
Post by: riplin on June 24, 2013, 02:37:37 AM
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.


Title: Re: ECDsa Verification Speed
Post by: piotr_n on June 24, 2013, 09:22:20 AM
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


Title: Re: ECDsa Verification Speed
Post by: MatthewLM on June 24, 2013, 02:53:16 PM
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?


Title: Re: ECDsa Verification Speed
Post by: piotr_n on June 24, 2013, 03:04:09 PM
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.


Title: Re: ECDsa Verification Speed
Post by: riplin on June 24, 2013, 05:42:21 PM
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.


Title: Re: ECDsa Verification Speed
Post by: piotr_n on June 24, 2013, 05:49:19 PM
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.


Title: Re: ECDsa Verification Speed
Post by: runeks on June 28, 2013, 01:30:00 AM
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 (http://sourceforge.net/projects/openssl-net/files/openssl-net/), although I haven't tried it. It does add the clutter of OpenSSL though (large dependency).


Title: Re: ECDsa Verification Speed
Post by: riplin on July 08, 2013, 06:38:52 PM
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.

I'm trying to verify the correctness of a secret key (basically, check if not zero and below a certain number, as can be seen in the Satoshi client) using this library, specifically, this function:

Code:
/** Verify an ECDSA secret key.
 *  Returns: 1: secret key is valid
 *           0: secret key is invalid
 *  In:      seckey: pointer to a 32-byte secret key
 */
int secp256k1_ecdsa_seckey_verify(const unsigned char *seckey) {
    secp256k1_num_t sec;
    secp256k1_num_init(&sec);
    secp256k1_num_set_bin(&sec, seckey, 32);
    int ret = secp256k1_num_is_zero(&sec) ||
              (secp256k1_num_cmp(&sec, &secp256k1_ge_consts->order) >= 0);
    secp256k1_num_free(&sec);
    return ret;
}

Please note, in all functions in this library, 0 == bad, 1 == good.

I'm finding three issues. The first one is, secp256k1_num_is_zero returns 1 if it's zero, else, it returns 0.

In the comment above, it states that 1 == valid. So it should be doing !secp256k1_num_is_zero(&sec).

Second, it's doing an ||, but both tests should be 1, so that should be &&.

And third, he &sec is compared to &secp256k1_ge_consts->order (which is the same as the upper bound number in the Satoshi client, it's basically doing a > b, and then testing if a (&sec) is larger or equal to b. But it should be doing ... < 0 at the end, since a should be less than b.

It looks like the whole thing is inverted and the return value should be 0 == good an 1 == bad.


Title: Re: ECDsa Verification Speed
Post by: jackjack on July 12, 2013, 10:07:35 AM
It looks like the whole thing is inverted and the return value should be 0 == good an 1 == bad.
That's it


Title: Re: ECDsa Verification Speed
Post by: Pieter Wuille on July 12, 2013, 11:49:27 PM
It looks like the whole thing is inverted and the return value should be 0 == good an 1 == bad.

Thanks, fixed!


Title: Re: ECDsa Verification Speed
Post by: slothbag on September 26, 2013, 05:51:23 AM
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.

Hey pmlyon, I am interested in a C# implementation of the ECDSA based message sign & verify in Bitcoin-QT.. See this thread https://bitcointalk.org/index.php?topic=297097.0 (https://bitcointalk.org/index.php?topic=297097.0). Hhave you had a go at implementing that in your project yet?


Title: Re: ECDsa Verification Speed
Post by: pmlyon on September 28, 2013, 09:51:40 PM
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.

Hey pmlyon, I am interested in a C# implementation of the ECDSA based message sign & verify in Bitcoin-QT.. See this thread https://bitcointalk.org/index.php?topic=297097.0. Hhave you had a go at implementing that in your project yet?


Hi, we haven't implemented that in our project yet, but I think this thread may help you: https://bitcointalk.org/index.php?topic=279752.0

Josh has a link there to a managed wrapper he wrote around the sipa secp256k1 verifier:
https://github.com/joshlang/Secp256k1.NET
https://github.com/sipa/secp256k1

I plan on using these when we get to that stage, but haven't looked at them yet.