What would the math be behind these claims?

[Remember remember the 5th of November]

I was reading up on whether it was possible to get faster performance on key generation and came across this post https://crypto.stackexchange.com/questions/29885/can-a-billion-elliptic-curve-keys-be-generated-on-a-laptop-in-less-than-an-hour

The very last post claims pretty high numbers and wanted to know if it was bull or real. If it's real what would the math be for those kinds of speeds? And what is referred by "symmetrie" of seck256k1?

[AdolfinWolf]

I was reading up on whether it was possible to get faster performance on key generation and came across this post https://crypto.stackexchange.com/questions/29885/can-a-billion-elliptic-curve-keys-be-generated-on-a-laptop-in-less-than-an-hour

The very last post claims pretty high numbers and wanted to know if it was bull or real. If it's real what would the math be for those kinds of speeds? And what is referred by "symmetrie" of seck256k1?

And what is referred by "symmetrie" of seck256k1?

An elliptic curve in theory will always look like this;


In bitcoin, it's just slightly different. https://bitcoin.stackexchange.com/questions/21907/what-does-the-curve-used-in-bitcoin-secp256k1-look-like

Which means that there are (obviously) 2 "solutions" for every X(?) (Which i think are the compressed vs uncompressed keys he is referring to?)

I have no clue what the difference between them is, apart from the different byte sizes (resulting in only the compressed version being used in bitcoin nowadays(?)).
(EDIT; http://learnmeabitcoin.com/glossary/public-key)

This is really were my (already limited) understanding of it all stops. I'm not entirely sure how credible his answer is, (or mine  ) especially since he is doubling the number twice for "symmetry"?

I mean: 30 million uncompressed public keys, or 60 million (if you accept both uncompressed and compressed format) keys in 1 second.

If you exploit then the symmetrie of the secp256k1 curve, you can double this number for free (120 million public keys in 1 second). If you use endomorphism too, you could get over 220 million of public keys in 1 second. Only via CPU.

Aren't you already exploiting the symmetrie of the curve by using both uncompressed and compressed public keys?
How can he just double that number for uncompressed v compressed keys as described in the first sentence of his answer...?


As per http://learnmeabitcoin.com/glossary/public-key;
This is an uncompressed key

Code:

04fe53c78e36b86aae8082484a4007b706d5678cabb92d178fc95020d4d8dc41ef44cfbb8dfa7a593c7910a5b6f94d079061a7766cbeed73e24ee4f654f1e51904

This is a compressed one;

Code:

03df51984d6b8b8b1cc693e239491f77a36c9e9dfe4a486e9972a18e03610a0d22

I don't get how he just comes up with these out of thin air as per his answer of "simply doubling/"accepting" them"....?
I feel like i'm completely misunderstanding this...






Per Pieter Wuille;

From an EC point of view, you have one private key with one corresponding public key.

The problem is, public keys can be serialized in two ways - compressed (33 bytes) or uncompressed (65 bytes). One is slightly harder to deal with, but as storage space is more critical in Bitcoin, we prefer to use the compressed one. Thus, we now have one private key that corresponds to (from Bitcoin's point of view, as we deal with the serialized versions) two public keys. Each of these public keys has an address (as the hash is calculated from the serialized public key). So, 1 private key, 2 public keys, 2 addresses.

So when you want to import a private key, the software has to know which of the public keys (with corresponding address) should be used. The solution is to add a flag bit to the base58 encoding of the private key, notifying the importer whether or not to use the compressed public keys. Typically, these get called compressed and uncompressed private keys - but it's really just a bit saying whether the corresponding public key is compressed or not.

The only reason not to use a compressed public key is that not all software supports it (they were introduced in Bitcoind/Bitcoin-Qt 0.6 only).

@MoonShadow: EC public keys are actually not numbers but a pair of numbers (X and Y coordinate), and the Y coordinate can be calculated from the X coordinate. That is how "compression" works - it's just a somewhat less redundant encoding. Testnet is unrealted to this.

[aplistir]

Edit:
Noticed that they are talking just about generating public&private key pairs and not about generating addresses.
When generating a key pair you do get uncompressed and compressed addresses with the same work

Uncompressed and compressed addresses both have the same public point on the curve.

The only difference is that they are presented differently. Uncompressed public point has both the X and Y-coordinates, while compressed has only the X-coordinate and a byte that tells if we have the odd or even Y-coordinate. That makes the compressed  key shorter by half.

Using symmetry you can get another point, with the same X and the opposite Y-coordinate. and both compressed and uncompressed addresses for that point.

In addition you can also make SewWit addresses for all of those points.

However, you cannot double the amount of generated addresses without additional work. To get an address from a public key (compressed, uncompressed or SegWit) you will need to do 3* SHA256 hashes and 1* RIPEMOD160 hash and then convert the result to base58

Doing the 4 hashes requires a lot of calculations so you wont be getting any extra addresses without doing a lot of extra calculations.

[Remember remember the 5th of November]

Yes this is just about the keypairs. Alright, so I understand that you get 2 bitcoin addresses per one private key depending on compressed/uncompressed. But still 30 million keys, is quite a lot. Even vanitygen can only do 500k/s with point addition(though we do include sha256 and ripemd160 hashing).

[arulbero]

I was reading up on whether it was possible to get faster performance on key generation and came across this post https://crypto.stackexchange.com/questions/29885/can-a-billion-elliptic-curve-keys-be-generated-on-a-laptop-in-less-than-an-hour

The very last post claims pretty high numbers and wanted to know if it was bull or real. If it's real what would the math be for those kinds of speeds? And what is referred by "symmetrie" of seck256k1?

I wrote that answer.

The current speed of the public keys generation on my laptop is 185 MKeys/s (I compute only compressed keys, only the "x" coordinates). It's real.

If I computed "y" coordinates too I could exploit the fact that (x,y) and (x, p-y) (that is the "symmetrie") are 2 valid points and maybe I would get more speed.
 

I'm talking about public keys generation, not addresses generation. The performance of addresses generation  is obviously lower, about 12.7 MAddresses/s (always on cpu)

If we compare vanitygen and my library on writing addresses speed (not only generation) the difference is even bigger:  

--> https://bitcointalk.org/index.php?topic=25804.msg23710724#msg23710724


Secp256k1 library too is using optimizations to get more speed:  https://bitcointalk.org/index.php?topic=2934774.msg30174356#msg30174356

[achow101]

Even vanitygen can only do 500k/s with point addition(though we do include sha256 and ripemd160 hashing).

Vanitygen is pretty slow and does not used optimized key generation code. If you use an optimized library like libsecip256k1 (which is used in BItcoin Core), it can be much faster.

[Remember remember the 5th of November]

I was reading up on whether it was possible to get faster performance on key generation and came across this post https://crypto.stackexchange.com/questions/29885/can-a-billion-elliptic-curve-keys-be-generated-on-a-laptop-in-less-than-an-hour

The very last post claims pretty high numbers and wanted to know if it was bull or real. If it's real what would the math be for those kinds of speeds? And what is referred by "symmetrie" of seck256k1?

I wrote that answer.

The current speed of the public keys generation on my laptop is 185 MKeys/s (I compute only compressed keys, only the "x" coordinates). It's real.

If I computed "y" coordinates too I could exploit the fact that (x,y) and (x, p-y) (that is the "symmetrie") are 2 valid points and maybe I would get more speed.
 

I'm talking about public keys generation, not addresses generation. The performance of addresses generation  is obviously lower, about 12.7 MAddresses/s (always on cpu)

If we compare vanitygen and my library on writing addresses speed (not only generation) the difference is even bigger:  

--> https://bitcointalk.org/index.php?topic=25804.msg23710724#msg23710724


Secp256k1 library too is using optimizations to get more speed:  https://bitcointalk.org/index.php?topic=2934774.msg30174356#msg30174356

Should I assume that you do not wish to make the math available? Or is it already implemented in libsecp256k1? Cause millions of combos per second is pretty good, on a CPU too.

[arulbero]

Should I assume that you do not wish to make the math available? Or is it already implemented in libsecp256k1? Cause millions of combos per second is pretty good, on a CPU too.

The math is available https://bitcointalk.org/index.php?topic=1573035.msg17676647#msg17676647
not the code.

I think that almost everything is implemented in libsecp256k1 already, but my software does only one thing: it generates consecutives keys.

[Remember remember the 5th of November]

Thank you. I'll have a look at libsecp256k1 + your proposed changes.

[Remember remember the 5th of November]

Using libsecp256k1+sipa's ec grind commit(which uses endomorphism) I get at most 13 million public keys per second(per core) using a batch of 4096. Which means 4 cores would equal roughly 52 million keys per second on my 8700k. If we use both compressed and uncompressed, I guess it automatically goes to ~104Mkeys/s.

[arulbero]

Using libsecp256k1+sipa's ec grind commit(which uses endomorphism) I get at most 13 million public keys per second(per core) using a batch of 4096. Which means 4 cores would equal roughly 52 million keys per second on my 8700k. If we use both compressed and uncompressed, I guess it automatically goes to ~104Mkeys/s.

Very good speed!
It took months to me to get my current 45 million points (only x) per second (per core) on my mobile Xeon.
On my laptop if I use 4 cores the speed is less than 4x.

I compute three points: x, beta*x, beta2*x. With "45 million points per second" I mean 15 million of (x, beta*x,beta2*x). Do you compute the y coordinates too?

From these 3 points you can get 6 compressed public keys: "02x", "03x", "02beta*x", "03beta*x", "02beta2*x", "03beta2*x".

If you have the y coordinate too, you can get the uncompressed keys: "04xy", "04beta*xy", "04beta2*xy", "04x(p-y)", "04beta*x(p-y)", "04beta2*x(p-y)"

Then in 1 second I could get about 90 million compressed public key per core, and at least 170 million compressed and uncompressed public keys per core.