Bitcoin Forum

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?

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

http://miguelmoreno.net/wp-content/uploads/2013/05/fYFBsqp.jpg

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.

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.  

Make your own key by hand then :)

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.

Pretty sure my RNG would be very easy to bruteforce.



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

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.

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

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

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

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?

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.


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).

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.

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.

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.

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.

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.


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

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%. 

Bitcoin addresses (2¹⁶⁰)
1461501637330902918203684832716283019655932542976

Earth Population
7218626512

Bitcoin addresses per person in Earth
202462564713848561306988538198010461031

Thats Two and two quintillion, four hundred sixty two quadrillion, five hundred sixty four trillion, seven hundred thirteen billion, eight hundred forty eight million, five hundred five thousand,  hundred thirty eight hundred-quintillionths

Lol @ vanitygen. I've written a much optimized version. With 30k addresses, it generates AND compares with 33 million keys per second on the CPU. Vanitygen is much slower.

In depends on what you mean by "time".  If given an infinite amount of computing power, an infinite amount of storage space and an infinite amount of time.  However under more realistic constrainsts you may never see a 160 bit collision before the heat death of the universe.  So saying "there will be collisions" especially the plural is dubious.  There may eventually be a collision but even that isn't guaranteed.

Which for the purpose of this dubious scenario is like the guy with a bucket emptying the ocean laughing at the guy with a teaspoon trying to do the same thing. :)

Even so, my version is on the CPU and is therefore much efficient than a GPU which uses more watts. The key to this optimization is that I skip the base58 phase and use the RIPEMD160 hash and compare the bytes in a boolean expression. This way I also don't need to use PCRE ot strcmp. On my i5-4670k I do 33 million keys per second(which are compared to the list of 30k addresses) per thread.

The only downside is this method requires a list of keys in a file, they are supplied in base58 format and inside they are decoded back to their RIPEMD160 states.

It is improbable to generate an inuse key. That is a fact.

Given enough time some miner will eventually solo mine a series of 1000 blocks, one-second apart.  The probability is not zero, so it'll eventually happen, right?

This ^

It *is* improbable.

"B-but it's only got 4 digits, it can't be that big!"

i think the OP is trying to make the point that if there are
1000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000
privkeys (i know i know i have not done enough zeros.. its an example)

but a rndom generator only deals with a length of
1000000000000000000000000000000000000000000000

then everyones address would be somewhere between
1 and 1000000000000000000000000000000000000000000000

leaving the other keys above the 1000000000000000000000000000000000000000000000 never touched

I don't think you fully understand how insignificant this is to my algorithm.
Oh boy...  :D

2^256 is approx. 10^77, the age of our universe is 4x10^17 s approx. Even if you had a trillion machines (10^12) generating 100 million addresses per second since the big bang you would cover the 0.00000000000000000000000000000000000000001% of the 256 bit configuration space. It is more likely that a frappuccino pass through Mark Karperles by tunnel effect.

Edit: if we only consider the 160-bit space corresponding to the public key hash. The same trillion machines working since the Big Bang would only cover the 0.000000000001%, so it can be safely said that generating used keys is improbable.

I don't think people realize how much is "possible" if you only include P=0 events as impossible.  

For example, the laws of physics are reversible.  Video record someone "breaking" the triangular group of pool balls, as the balls scatter into an unorganized state.  Now play this recording backwards and watch the balls all converge to the organized triangle, popping the cue ball back against the player's cue.  Calculate the physics of every collision for the "backwards event" and you'll see that no laws of physics were violated.  The "backwards event" is possible.  

But you won't be able to make it happen!!

For any event that can happen (e.g., cracking an egg), the backwards event can also happen with some probability (uncracking an egg).  It is just so vastly improbable that physicists assume it will never happen and call this the "Second Law of Thermodynamics."  But it's not a law at all--it's just a bold statement that extremely unlikely events do not actually happen.  

do you know the probability of life being created on any planet in the universe.
now
multiply that by the probability of that life being more then just a 1 celled organism
multiply that by the probability of that life having different abilities, such as swimming, flying walking
multiply that by the probability of that life gaining intelligence to communicate with each other (like birds)
multiply that by the probability of that life gaining intelligence to communicate with each other to such an extent that they can work together to do things.
multiply that by the probability of that life gaining intelligence to communicate with each to learn how to make objects like axes and clubs(Neanderthals)
multiply that by the probability of that life gaining intelligence to develop even further to then make computers to automate tasks

now you probably have a very large number, which is right.. we are an improbable number, that many things had to combine in the right way for it to happen.

... yet 7 billion of us all have the same ability to walk talk and build.

,, nothings impossible, just improbable

I don't think any of us have to worry. This can be mitigated by the much greater probability that there is pirate gold buried in your backyard. The chances of a treasure chest in your yard from a privateer must be many times greater than an encryption collision. So relax, if your key is generated by another peer you can just start looking for the treasure.

There are more possible private keys than there are grains of sand on Earth.

Is a collision possible? Certainly.

Is it going to happen in your lifetime? Not a chance.

I think I'm in love with you.

People still realize how wide the spectrum is for a collision. Therefore we must use words like improbable.
Let me steal something: Now ←-------------- Very Soon -------- Soon -------- Soon-ish ---------------→ End of Time
Now, it's possible that one collision might Soon-ish.

Good one, mate.

You should be much more worried about being hit by an asteroid.

Dat genius

I think vector of attacking a the RNG is much more interesting...

That is probable attack vector if you know the implementation and hardware. I don't think many use truly random generation in key generation... At current levels of power and computing this isn't feasible, but it might be at some point...

If you actually do generate a duplicate key, I would be much more concerned about a flaw in the software used to generate the key.  Scrap that program and use a different method to generate keys.

How many of us have a way to generate secure(private) random data or even sufficiently random seeds... And I'm using random here for not pseudo-random that is seeded and then algorithmically generated...

If you did generated an in use wallet private key.
You just hit the world's lowest probability to win jackpot and you deserve to keep the money. :p
It's easier to get struck by lightning 10 days in a row than generating an in use wallet key.
http://what-if.xkcd.com/2/
Still easier than guessing all SAT questions right though.

Roll a bunch of dice?  Flip a bunch of coins?  It may not be particularly useful for random wallets where a new random private value is needed for each private key however it would be fairly easy to do for a deterministic wallet.

True, one should always speak in relative terms. You have as many chances of having a collision as you have chances of being killed by a 22-carat pure gold meteorite at the time you generate your key.

Or of being struck by lightning in the same spot 10,000 times in a row for seven weeks straight. And surviving to tell the tale.

Can we stop saying that it's improbable that this will happen?  :D

It's 50:50. Either you generate an address that's already in use, or you don't.

To make myself clear I've done the calculation of the acumulative probability of a collision as the addresses are generated. This probability increases with the square of the number of generated addrsses. If we consider the most restrictive case: the 160 bit space of the public key hash, a 1% probabiliy of bitcoin addresses collision will be reached when 1.2x10^23 bitcoin addresses are generated. This means that a million machines generating 30 million addresses/second each would need a thousand years to reach a 1% probability of a single collision.

Of course even that overstates the scenario in the OP which is a "inuse key".  Given the size of the key space in the highly improbable event of a collision it is very likely between two unfunded addresses created by the same mass creating entity.