Topic: Chances of a collision - page 2. (Read 4762 times)

You have to "cook the books" for something like that to happen. The person described above had to put himself in positions where conditions where lightning would strike. I'm not saying he did it on purpose, but maybe next time he sees a storm cloud over head and begins to smell ozone he should head inside.  You could do the same with bitcoin and use poor RNG to generate addresses and you then put yourself in a position where a collision is more likely. For instance using the brainwallet "cat" or "satoshi nakamoto" those are technically collisions but they are due to poor RNG not a fault in the bitcoin protocol.

What about this guys:

http://www.dailymail.co.uk/news/article-2711202/It-cooks-inside-like-microwave-Man-61-survives-struck-lightning-10-TIMES.html

So we know that being hit by lightning 10 times is possible , thus:

A 0.000000000000000000000000000152% chance has already happened, and probably even more times around the world, so i`d say

Anything between  1e-28 and 1e-40 chance is probable to happen in our lifetime.

Now you guys say that (on another thread i saw this):



Thus that is a 1.5e-28 probability that if 1 billion people create addresses, then 1 address can easily be REVEALED!

So consider this, a person can easily create more then 1 addresses, i think the average per person is around 5-6.
(Excluding the fact that there can be malicious guys that create billions of addresses /day, searching for filled balances)

But even if we go with 5-6/life, and looking for 1 billion people (conservative future users of bitcoin).

That is 5,500,000,000 /2^160 = 3.7632527118098114697658753457492e-39

So that is 3.76e-39, and we know around 1e-40 is probable, thus at least 1 unlucky fellow from that 1 billion users will get its account hacked.
And this is only conservatively speaking in a passive situation, involuntary collision (if hackers start to actively search for bitcoin addresses with the purpose of finding them, then we are even more in trouble)

I think the probability should be at most 1e-100, but preferably even lower a 1e-200 to be safe, we need new format of the private key, 2^160 is too little, not to mention, the guy above me said that its only 2^80 which is very unsafe

As pointed out the probability of a 'collision' is 1 in 2⁸⁰ but  a collision isn't useful to attack Bitcoin or steal funds.  Given the magnitude of 2⁸⁰ relative to the number of addresses any collision is almost certain to be between to unused keys very likely between two keys that will never be generated by anyone else.  That doesn't give you any way to disrupt the network or steal funds.   To do that would require not just a collision attack but a preimage attack which has a complexity of 2¹⁶⁰ against a single key and with only a linear reduction if attacking a set of keys (i.e. look for preimage against any 'funded address').

There are 2¹⁶⁰ addresses.  That means that by the time you've got sqrt(2¹⁶⁰) addresses, assuming uniform distribution (which is valid on cryptographic keys) there are even odds that some two of them have collided.  That means you'd need 2⁸⁰ addresses before a collision occurred.  That's about 1.2 septillion addresses required before a collision between any two becomes likely. 

For some sense of scale, Earth weighs about five times that many kilograms. 

Ah, yes, I missed that at first too.  The masses of poorly thought-out posts on this forum has encouraged me into the bad habit of skim reading everything not written by a small white-list of known good posters.

Sure.  If the RNG is flawed then the chances of finding a collision are improved.  I agree it's most likely that this newkey function is used under the hood when people create new addresses in their blockchain.info wallets so there should be plenty of addresses containing funds to collide with.

What the probability of collision is is open to speculation.  Theoretically, anything from [number of existing addresses] / 2¹⁶⁰ up to 1 is possible and, absent the code, we only really have the fact that no-one's found a collision so far to guide us.


I agree that the keys would not be repeated and the addresses would not be random.  However, the RIPEMD-160 step (assuming RIPEMD-160 itself is not badly flawed) ensures that the addresses will be seemingly random and address collisions will not be practically predictable (precisely as Bitcoin mining gives rise to unpredictable block generation times).

I think that it is safe to say, for all intents and purposes, that the chance of a collision happening is 0.

I guess the reasoning is that using a potentially flawed generator (that is widely in use) probably increases your probability of finding an address with a balance as opposed to working through the problem space in a pure fashion.  This is only true if the generator is non-random in some repetitive fashion (i.e. it is more likely than purely by chance to repeat some address).  If the generator is simply counting up from 1 for example the key/address would not be repeated (but would still not be random).

My mistake.  A more careful look revealed that indeed you are checking for any addresses which have ever received funds.


I don't know the details of the sources of random used by blockchain.info's newkey.  While I agree that there is the possibility of a flaw in the RNG leading to unexpected long-term behaviour of the script, I maintain that the best way of resolving this potential flaw is to throw out the RNG altogether.  A collision generator has no need for anything random.

I was simply responding to the OP's question "how would somebody trying to cause a collision notice that they've succeeded?"  What I provided is perfectly valid to his question, it attempts to create a collision based on poor RNG and let's you know if you found one. What you posted everyone already knows.


Yea I quite aware of the # of addresses...


No it doesn't, it checks total amount the address has ever received, in other words checks to see if the address has ever been used.


The script is checking the RNG of blockchain's (https://blockchain.info/q/newkey) tool. It has no extra points of entropy like bitaddress.org and could very well be flawed. Do you know the RNG behind this newkey tool?

Yes, all this speculation takes RIPEMD-160 into account.  It is because of the RIPEMD-160 that a collision is going to look like having two different private/public keypairs which correspond to the same address.


Cool.  Note that a collider doesn't need high-quality randomness for each address.  Just working through all the private keys in order from 1 to 115792089237316195423570985008687907852837564279074904382605163141518161494336 would be fine (yes, there are quite a lot of different private keys).

Anyway.  At 320 addresses per hour and assuming all else constant, you should be finding an address collision once every 121 billion trillion trillion years on average (similar to the way a new block is generated once every 10 minutes on average so expect some variance).  Notice that you'd actually be generating a collision on average once every 7.8 billion trillion trillion years but because your code checks collisions by checking for a balance and most addresses in the blockchain have a balance of 0 you'll be missing a lot.

I feel it's worth comparing this to Bitcoin block generation.  A script which generates 320 hashes per second will find a block on average once every 72 trillion years.  Given that many CPUs are capable of hashing 10 000 times faster and that an address with non-zero balance contains about 3.2 BTC (compared with the average block payout of about 25 BTC) we see that anyone looking to run this code for profit would be about 100 trillion trillion times better off just CPU mining Bitcoin.

Here's some super simple code I wrote for a mini bitcoin address collider. I call it mini because it only does 324 address per hour, however the RNG process being used is unclear. If the RNG is flawed there is a better chance of collision.  

Blockchain.info  provides this (https://blockchain.info/q/newkey) which is supposed to create a fresh public/private key pair whenever you call that address. Since the RNG process behind these addresses are unclear is the reason I'm using it. There's a limit of ~1 query per 10 seconds or you'll get banned/blocked which is why this script only does about 320 per hour.  It pulls the new key (assuming RNG is good) and then we use the address info and return the total amount received to that address and plugs everything into a DB. If total amount received is ever greater than 0 then you have a collision. Or you can also query your DB to see if there are any repeats.

Put it in a cron job to run every 5 minutes.

well............ have you considered ripemd160? I mean it is easier (lol easier) to find collision in 160 than 256.

Just to clarify: there's a wide margin between finding an address collision in this fashion and breaking Bitcoin*.  The latter would at bare minimum require something like the hypothetical futuristic Mount Everest machine I described above.

The cluster could probably be used to solve chess and maybe even run Crysis but it will not break Bitcoin.

*I'm assuming there is no subtle bug which would cause problems should two outputs at the same address be moved simultaneously using different keys.

And do not forget this people all this is just t point out that Bitcoin is no impossible to break. But again there is nothing "impossible" in security system, It is just relative security to the gain. No one would do such thing to find a collision, This is alot of money for a hackathon to say haha I found a collision haha..... -_-

Hmm...  Maybe about 30 exajoules (roughly 8000 terrawatt hours).  This is assuming we can be clever about how matching pairs are checked for and most of the drives can be powered down for most of the year.

Switching off both China and the US and diverting the power to the cluster should be sufficient.

And that is not mentioning the power drain for this!

I understood Grumpster to be asking about colliding with one of the currently existing addresses rather generating two addresses which collide with one another.  If we're just looking for two distinct private keys which yield the same address then indeed the Birthday Problem applies.  The average number of addresses you'd need to generate to find such a beast is approximately 1.5 trillion trillion (a little bit more than square_root(2¹⁶⁰)).

This problem is far closer to tractable.  All we'd need is about 2 billion gaming rigs running for a year, each with about 20 000 terrabytes of storage.

With a few basic cryptographic assumptions, the chance of a single randomly (uniformly) generated Bitcoin address colliding with an existing address is simply: [number of existent addresses] / 2¹⁶⁰.

At the moment of writing (block #348386), there are 66 214 306 distinct addresses recorded in the blockchain (93.5% of which are empty by the way).  This yields a probability of about 4.5 * 10^-41 (about 1 in 22 000 trillion trillion trillion).


Not to my knowledge.


Such hardware would need to be able to generate close to 2¹⁶⁰ / [number of existent addresses].

A decent CPU might manage to generate 500 000 addresses per second.  Working with a companion GPU well-suited to the task and you might be looking at 20 million addresses per second.

"What about ASICs?" I hear you ask.  Well, let us suppose that you could design a machine a billion times faster than this for the same mass of hardware and power consumption.  We'll assume the machine can also check addresses against the relatively tiny pre-set list of existing ones as fast as the new ones are generated.

A cluster of these machines capable of "getting close" (lets say having a fair chance of generating a collision within a year) will draw about as much power as consumed in all other human activities combined and weigh about as much as Mount Everest.

It boils down to the birthday paradoxon with 1 in 2¹⁶⁰ instead of 1 in 365. The number of addresses that have a balance is probably among bc.i's stats.


here is another one -> https://bitcointalksearch.org/topic/understanding-public-and-private-keys-633308

I was looking them up, if you search for "bitcoin address collision" you'll see links - like the two above.
:-)