Can we please stop saying that it is improbable to generate an inuse key?

[mustyoshi]

Because I'm sure we're all aware that due to the nature of random number generators, and implementations, the more widespread the adoption of Bitcoin, the more likely it is that we will see key collisions.

Are we even sure that ECDSA even has an unbiased distribution?

[1715151721]

1715151721

[1715151721]

1715151721

[1715151721]

1715151721

[1715151721]

1715151721

[gadman2]

I don't think you fully understand how large 2^256 is:

[mustyoshi]

I don't think you fully understand how large a 2^256 is:

That image is exactly what I'm talking about it.

And I don't think you understand how easily a flawed RNG can shorten the work required to bruteforce a key, let alone generate an inuse one on accident.

[retrend]

Facts and maths are great, but you never know do you!

That's why I've had my vanitygen running on the satoshi wallets since 2011.  

[gadman2]

Make your own key by hand then

[DeathAndTaxes]

No those of us that understand math won't keep saying that because it is accurate.  Of course is you are worried about flawed PRNG then use a true hardware random number generator (quantum effect or avalanche noise).

There is no known bias to the distribution of ECDSA public keys.  Even if some bias did exist 2^256 is a large space it would take a rather massive bias in distribution in order for there to even be a 1% chance of collision in the thousand years.

[mustyoshi]

Make your own key by hand then

Pretty sure my RNG would be very easy to bruteforce.

Facts and maths are great, but you never know do you!

That's why I've had my vanitygen running on the satoshi wallets since 2011.  

I really want you to be telling the truth, and I really want you to succeed, just to prove that it can be done.

[phillipsjk]

Technically, addresses are only 160bit hashes.

If that RNG is not working properly, that is a bug in the RNG. Bitcoin has already exposed problems with the Android RNG.

[mustyoshi]

Technically, addresses are only 160bit hashes.

If that RNG is not working properly, that is a bug in the RNG. Bitcoin has already exposed problems with the Android RNG.

Even if you produced an address collision, you still need a private key that can sign the tx.

[phillipsjk]

Even if you produced an address collision, you still need a private key that can sign the tx.

Yes, but it does not have to be the same public/private key pair.

[mustyoshi]

Even if you produced an address collision, you still need a private key that can sign the tx.

Yes, but it does not have to be the same public/private key pair.

Hmm, so then we'll see collisions even sooner.

[Gabi]

Unless the algorythm is cracked, no, we will not see collisions, stop spreading FUD.

[kokojie]

I don't think you fully understand how large 2^256 is:

Isn't it 2^160? since bitcoin address is actually a 160bit hash.

Now 2^160 is still quite large, but let's assume every person on earth uses Bitcoin, and has 100 addresses (the default of Bitcoin qt client pre-generates 100 addresses).

Now we are down to (2^160)/700B

Are you still confident that it's large enough?

[phillipsjk]

Yes, but it does not have to be the same public/private key pair.

Hmm, so then we'll see collisions even sooner.

No, my point is if you are deliberately trying to cause collisions, making the hash function collide should be about 2⁹⁶ times easier. I did not say it would happen before the sun burns out.

Are you still confident that it's large enough?

Yes. I recall reading that merely counting to 2¹²⁸ would theoretically take more energy than is in the known Universe. Although, for a hash collision, you would only need 2⁸⁰ attempts on average.
Edit: 700Billion = 2^39.3; about the equivalent of DVD encryption (limited to 40bits by US export restrictions at the time).

[mustyoshi]

I don't think you fully understand how large 2^256 is:

Isn't it 2^160? since bitcoin address is actually a 160bit hash.

Now 2^160 is still quite large, but let's assume every person on earth uses Bitcoin, and has 100 addresses (the default of Bitcoin qt client pre-generates 100 addresses).

Now we are down to (2^160)/700B

Are you still confident that it's large enough?

I personally have over 100M private keys generated. But even 100 addresses per person is an understatement, the spec recommends never using an address twice, especially since once you sign a tx, it becomes that much easier for a QC to crack your private key.

Unless the algorythm is cracked, no, we will not see collisions, stop spreading FUD.

Personally I believe it's FUD to exclaim that we WONT see collisions.

There have been a few cases where wallet implementations have resulted in extremely reduced keyspaces.

[Gabi]

If you make a wallet that always choose the same 3 keys then yes of course it will have collisions, but it will be faulty software. It is like making a fail bitcoin client wich crash on start and then blaming the bitcoin algorithm for that, nonsense.

[btc_jumpnrl]

In time there will be collisions because the probability is not 0. However, not only do you have to match an in-use key, that key also has to carry a balance.

By brute-forcing keys, the probability is the lowest. Anything related to a vanitygen that's not truly random, is at risk of being brute-forced as it seriously diminishes the keyspace. As time goes on, if people do not adhere do the rinse-and-don't-reuse address policy, the collision probability will increase. People are already generating lists upon lists of private keys just for the sake of generating them. As hardware and storage technology increases, its less of a monetary drain to just let a computer go to work generating Millions upon Millions of addresses every second.

The probability is non-zero, but thats also why they say its improbable not impossible.

[Gabi]

On a side note, let's stop the misuse of the word "collision" please. A "collision" in an algorithm is when two different inputs give the same result.

A fail wallet client having a fail keyspace and always giving the same keys is not a collision, is just a fail

[mustyoshi]

On a side note, let's stop the misuse of the word "collision" please. A "collision" in an algorithm is when two different inputs give the same result.

A fail wallet client having a fail keyspace and always giving the same keys is not a collision, is just a fail

I suppose you're right. It's semantics really though.

In time there will be collisions because the probability is not 0. However, not only do you have to match an in-use key, that key also has to carry a balance.

By brute-forcing keys, the probability is the lowest. Anything related to a vanitygen that's not truly random, is at risk of being brute-forced as it seriously diminishes the keyspace. As time goes on, if people do not adhere do the rinse-and-don't-reuse address policy, the collision probability will increase. People are already generating lists upon lists of private keys just for the sake of generating them. As hardware and storage technology increases, its less of a monetary drain to just let a computer go to work generating Millions upon Millions of addresses every second.

The probability is non-zero, but thats also why they say its improbable not impossible.

I can't wait to get my hands onto a ASIC designed to generate keys.

[DeathAndTaxes]

I personally have over 100M private keys generated. But even 100 addresses per person is an understatement, the spec recommends never using an address twice, especially since once you sign a tx, it becomes that much easier for a QC to crack your private key.

The later is only assuming a QC with sufficient qubits (~40,000) to implementing Shor's algorithm against 256 bit keys is ever possible.  The largest quantum computer which has implemented Shor's algorithm is 5 qubits.  It "cracked" the number 21 into the prime factors 7 & 3 (5 bit encryption if you want to call it that) after a mere 9 months.

Still you misunderstand that scope.   It doesn't matter how many addresses have been used in the past.  To steal funds you would need to produce a collision with a funded address.

Given a max of 2.1 quadrillion satoshis there simply can never be more than 2.1 quadrillion funded addresses.  Even if you assume 2.1 quadrillion funded addresses (dubious but good for an absolute upper bound) that puts the possibility of a preimage attack at 2^160 / ~2^50 = 2^110 which is many magnitudes beyond what is possible with brute force.

Another way to look at it is the Bitcoin network has ~30 PH/s.  Let assume all of that could be used to brute force keys instead.  Now lets also assume that it is as easy to compute and check a pubkeyhash (it isn't).  There are roughly 1 million funded PubKeyHashes.  If the entire network attempted to brute force them it would take on average 823,233 years to break a single pubkeyhash and the payoff would be a random amount of bitcoins but the average reward would be ~2.1 BTC.   The chance of a collision in a century would be 0.0121%.