ECDsa Verification Speed | Bitcointalksearch.org

pmlyon

member

Activity: 72

Merit: 10

Quote from: slothbag on September 26, 2013, 12:51:23 AM

Quote from: pmlyon on June 17, 2013, 11:21:32 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://bitcointalksearch.org/topic/cancelled-c-gurus-need-signmessage-verifymessage-fill-in-the-blanks-297097. 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://bitcointalksearch.org/topic/sipas-secp256k1-for-net-279752

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.

slothbag

sr. member

Activity: 369

Merit: 250

Quote from: pmlyon on June 17, 2013, 11:21:32 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://bitcointalksearch.org/topic/cancelled-c-gurus-need-signmessage-verifymessage-fill-in-the-blanks-297097. Hhave you had a go at implementing that in your project yet?

Pieter Wuille

legendary

Activity: 1072

Merit: 1181

Quote from: riplin on July 08, 2013, 01:38:52 PM

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

Thanks, fixed!

jackjack

legendary

Activity: 1176

Merit: 1280

May Bitcoin be touched by his Noodly Appendage

Quote from: riplin on July 08, 2013, 01:38:52 PM

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

That's it

riplin

member

Activity: 116

Merit: 10

Quote from: piotr_n on June 24, 2013, 12:49:19 PM

Quote from: riplin on June 24, 2013, 12:42:21 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.

runeks

legendary

Activity: 980

Merit: 1008

Quote from: pmlyon on June 17, 2013, 08:03:44 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, although I haven't tried it. It does add the clutter of OpenSSL though (large dependency).

piotr_n

legendary

Activity: 2053

Merit: 1356

aka tonikt

Quote from: riplin on June 24, 2013, 12:42:21 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.

riplin

member

Activity: 116

Merit: 10

Quote from: piotr_n on June 24, 2013, 04:22:20 AM

Quote from: riplin on June 23, 2013, 09:37:37 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.

piotr_n

legendary

Activity: 2053

Merit: 1356

aka tonikt

Quote from: MatthewLM on June 24, 2013, 09:53:16 AM

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.

MatthewLM

legendary

Activity: 1190

Merit: 1004

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

legendary

Activity: 2053

Merit: 1356

aka tonikt

Quote from: riplin on June 23, 2013, 09:37:37 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

riplin

member

Activity: 116

Merit: 10

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.

jackjack

legendary

Activity: 1176

Merit: 1280

May Bitcoin be touched by his Noodly Appendage

Quote from: Remember remember the 5th of November on June 18, 2013, 06:42:43 AM

Quote from: Mike Hearn on June 18, 2013, 04:24:20 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

Remember remember the 5th of November

legendary

Activity: 1862

Merit: 1011

Reverse engineer from time to time

Quote from: Mike Hearn on June 18, 2013, 04:24:20 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?

pmlyon

member

Activity: 72

Merit: 10

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.

piotr_n

legendary

Activity: 2053

Merit: 1356

aka tonikt

Quote from: Mike Hearn on June 18, 2013, 04:24:20 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!

Mike Hearn

legendary

Activity: 1526

Merit: 1134

The fastest implementation is this one:

https://github.com/sipa/secp256k1

pmlyon

member

Activity: 72

Merit: 10

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.

piotr_n

legendary

Activity: 2053

Merit: 1356

aka tonikt

Quote from: pmlyon on June 17, 2013, 11:21:32 AM

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

member

Activity: 72

Merit: 10

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.

Topic: ECDsa Verification Speed (Read 3180 times)