About Collision

[shorena]

schrodinger's cat

if you cant see it, did it really happen?

Actually, from my understanding of the schrodinger's cat Gedankenexperiment, if you can't see whether it has happened or not then it simultaneously BOTH did and didn't happen until it has been observed by someone.

If the state of possible collision is never observed by anyone then it will remain indefinitely in this state of superposition.

If it the state of possibile collision eventually is observed then the wave function will collapse and it will either have happened or not have happened.

During the state of superposition, it will have some percentage of having happened and some other percentage of having not happened.  Those percentages will be determined by the likelihood of it having happened.

Also, if i recall correctly, there is highly radioactive material in the box, so the cat will die at some point and that
is what is being determined. So the percentage of having happened versus having not happened, is of the death
of the cat, which is a sure eventuality in this experiment.

It doesnt really matter whats in the box, whats important is that there is a chance for it to be in one state and a chance for it to be in another. In Schrödingers Gedankenexperiment he used a very small amount of radio activ material which could decay a single atom within a given time span. This was used as switch for a deadly gas which would either kill the cat or not depending on whether an atom decayed or not. This was constructed to be of equal chance. An address collision is not of equal chance to it not happening, but its still the same general principle I think.

-snip-
But yes, address collision only exists when it is observed in the wild, like when a superposition ends and the
observed result is determined. Problem is that under normal circumstances, whether it is ever observed and
how to prove it is true collision (outside of random number generator errors and etc) is another issue.

Id say the collision happened even when no one noticed it. Shit already broke you just didnt realize it yet. Whoever sends coins to the address in question first will reveal the information to the other person also in control.

[calkob]

first of all this is not about the probability of a collision, we all know about that

let's assume that one happened already, there is a way to know if this is true? how can someone be sure that one address was not replicated already aside from the improbability?

I'm not sure there is any way to find this out, apart from having your bitcoin moved (not stolen cause it was their key to)  it would be an absolute disaster if it happens for the person in question.  but the odds of this happening are crazy and the odds of it happening twice are just beyond working out, so i think we can trust the math   

[AgentofCoin]

schrodinger's cat

if you cant see it, did it really happen?

Actually, from my understanding of the schrodinger's cat Gedankenexperiment, if you can't see whether it has happened or not then it simultaneously BOTH did and didn't happen until it has been observed by someone.

If the state of possible collision is never observed by anyone then it will remain indefinitely in this state of superposition.

If it the state of possibile collision eventually is observed then the wave function will collapse and it will either have happened or not have happened.

During the state of superposition, it will have some percentage of having happened and some other percentage of having not happened.  Those percentages will be determined by the likelihood of it having happened.

Also, if i recall correctly, there is highly radioactive material in the box, so the cat will die at some point and that
is what is being determined. So the percentage of having happened versus having not happened, is of the death
of the cat, which is a sure eventuality in this experiment.

It doesnt really matter whats in the box, whats important is that there is a chance for it to be in one state and a chance for it to be in another. In Schrödingers Gedankenexperiment he used a very small amount of radio activ material which could decay a single atom within a given time span. This was used as switch for a deadly gas which would either kill the cat or not depending on whether an atom decayed or not. This was constructed to be of equal chance. An address collision is not of equal chance to it not happening, but its still the same general principle I think.

Yes, I forgot about deadly gas.
The example is not about equal chance. It is used to describe quantum superstates.
In quantum theory, there is an equal chance of address collision happening and not happening.
In this theory both has occured, until an observer can observe otherwise.
Address collision as a probability or chance is different than it as a superstate.
Address collision as to probability or chance is definitely not equal.

-snip-
But yes, address collision only exists when it is observed in the wild, like when a superposition ends and the
observed result is determined. Problem is that under normal circumstances, whether it is ever observed and
how to prove it is true collision (outside of random number generator errors and etc) is another issue.

Id say the collision happened even when no one noticed it. Shit already broke you just didnt realize it yet. Whoever sends coins to the address in question first will reveal the information to the other person also in control.

Not according to quantum theory. The superposition exists because no observation has occurred.
The observation can either be by human, animal, or machine. It is the act of observation that
causes the superposition to literally "transform" into one of the potential states. Before the observation,
it is actually both in real time. It is complicated, but for example light can be a particle and a wave in real
time, but once it is physically observed by an observer, it changes to one or the other, but prior to that change,
it is actually both in real time. The cat example is just a simple way to visualize it (Cat is both alive and dead).

Collision, in the context of Superposition states, can only be observed, when the superposition is transformed,
such as when your privatekey (that is 100% impossible for another to have by any other means other than wild
collision), is used to move your coins to another address. It would thus transform that address privatekey from
the superposition to the state of collision.

In quantum theory, it is currently believed that the observer is actually the creator.
So, in a way, if tree falls in the woods, does it make a sound? the answer is no, not without a single observer.
But it could be argued as to Bitcoin, that address collisions is always observed by the blockchain itself.

[franky1]

no quantum theory is not that mythical
if you wipe away non descriptive buzzwords like super-position and think rationally. its simple.

its just opening up the idea that things are not black and white, on or off, dead or alive, binary..  .. not 2 options
its meant to open peoples minds to more options.

yea some people go absurdly beyond the rational because they think the quantum theory allows them to think irrationally. but thats not what its about.

Schroedinger cat is in the state of dying.. there is a chance of saving it by opening the box early. or waiting longer where the chance it dies is higher.

like hospitals. when someones heart stops.. they are physically dead.
but doctors do a 'code blue' and run to the patient saying the patient is dying. and try resuscitation the patient. its only minutes later do doctors declare the patient is dead, even if his body gave out minutes earlier

like hospitals. when someones heart is working.. they are physically alive. but have multiple cancers and in extreme pain
so doctors say the patient is dying. and discuss euthanasia as a humane option. its only minutes later do doctors declare the patient is dead, or alive depending on if they euphanize or not

what you see and think may be different to reality so things are not as black and white as alive and dead. on or off, theres always a grey area in everything.

quantum computing is not some outer space wormhole, time twisting theory.
its simply instead of using the old binary 2option switch.. its using more than 2 options.
eg
its not 0v=0 or 1v=1..
its 0v=0   0.33v=1   0.66v=2   1v=3  its as simple as that.

its about if and maybe.. aswell as yes no / on off / true false

[Pattberry]

quantum computing is not some outer space wormhole, time twisting theory.
its simply instead of using the old binary 2option switch.. its using more than 2 options.
eg not 0 volt=0 1volt=1.. its 0v=0  0.33v=1   0.66v=2   1v=3  its as simple as that.

its about if and maybe.. aswell as yes no / on off / true false

To be frank franky you are just awesome and i really do like the kind of explanation you give for each and every reply of yours,i really never understood what quantum computing is all about but knew it was really fast ,but this explanation was swift hope you are in the teaching profession .
And for the OP collision is a possibility because bitcoin addresses are generated randomly but the chances are really slim lets say about 1.6225928e+32 chance that to happen.

[AgentofCoin]

no quantum theory is not that mythical
if you wipe away non descriptive buzzwords like super-position and think rationally. its simple.

its just opening up the idea that things are not black and white, on or off, dead or alive, binary..  .. not 2 options
its meant to open peoples minds to more options.

yea some people go absurdly beyond the rational because they think the quantum theory allows them to think irrationally. but thats not what its about.

Schroedinger cat is in the state of dying.. there is a chance of saving it by opening the box early. or waiting longer where the chance it dies is higher.

like hospitals. when someones heart stops.. they are physically dead.
but doctors do a 'code blue' and run to the patient saying the patient is dying. and try resuscitation the patient. its only minutes later do doctors declare the patient is dead, even if his body gave out minutes earlier

like hospitals. when someones heart is working.. they are physically alive. but have multiple cancers and in extreme pain
so doctors say the patient is dying. and discuss euthanasia as a humane option. its only minutes later do doctors declare the patient is dead, or alive depending on if they euphanize or not

what you see and think may be different to reality so things are not as black and white as alive and dead. on or off, theres always a grey area in everything.
...

It is interesting you would write all the above to only say that it is "irrational".
Nothing you stated directly refutes what I have stated.
Quantum mechanic's current understanding is exactly what I have stated.
If you read more on it, you will ultimately be forced to agree.

The term "superposition" is not a buzzword. I am baffled by that comment.
My comments are strictly as to Quantum physics and the Schrodinger's Cat
example as to address collision, and have nothing to do with quantum computing.

Prior to your most recent statement, I am not aware of anyone making a comment
as to quantum computing in this thread.

Nevertheless, quantum computing, as you are defining, is the simplest level of that form
of operation. As it becomes more advanced, things you consider "mystical" can be performed.
The mathematics already predict those outcomes, no matter how bizarre and irrational to some
people it may seem to be.

[franky1]

It is interesting you would write all the above to only say that it is "irrational".
Nothing you stated directly refutes what I have stated.
Quantum mechanic's current understanding is exactly what I have stated.
If you read more on it, you will ultimately be forced to agree.

The term "superposition" is not a buzzword. I am baffled by that comment.
My comments are strictly as to Quantum physics and the Schrodinger's Cat
example as to address collision, and have nothing to do with quantum computing.

Prior to your most recent statement, I am not aware of anyone making a comment
as to quantum computing in this thread.

Nevertheless, quantum computing, as you are defining, is the simplest level of that form
of operation. As it becomes more advanced, things you consider "mystical" can be performed.
The mathematics already predict those outcomes, no matter how bizarre and irrational to some
people it may seem to be.

quantum theory
quantum mechanics
quantum computing. is all about quanta

in short once you pull away the big science buzzwording. its the simple fact of... more options.(quantity quantitate)

quantum theory can go so absurdly irrational that quantum theorists would think that it was ok to escalate the amount of options of Schroedinger cat to hypotheses that while in the box an asteroid can enter the earth's atmosphere and cause a sonic boom which echo's inside the box and scares the cat into having a heart attack so the chances of death are higher.

thats just one example of where trying to bring quantum theory into a debates can end up going down an irrational rabbit hole.

as for me taking the opportunity to meander an already meandered topic even further off topic(of collisions) i tried to redirect it back into the realm of other conversations in other topics (bitcoin based, not cat death based) to explain quantum computing.. seeing as this is a bitcoin forum and more people care about quantum theory in regards to bitcoin, rather than a cat

lastly i said mythical
meaning a myth a theory a story.
anything is a myth until it is busted.

i prefer science fact when dealing with current and future tech. and although quantum does open up more options, sticking to rational and practical idea's without doing deep into a rabbit hole of absurd possibilities is what i try to keep to

[RawDog]

Collisions are actually far easier than you think.  I am working on that now.

Stay tuned.

Just think, my VanityGen trys about 880,000 keys per second.  Every hour, I check over 300 million keys.  Still think I won't find a collision?  There has to be one out there somewhere.

[franky1]

Collisions are actually far easier than you think.  I am working on that now.

Stay tuned.

are you going page by page through directory.io..
if so ill remind my great great great great great great grandchildren to check in on your great great great great great great grandchildren when they inherit your project after we both pass away and have been rotting for a few centuries

[ArcCsch]

Private keys are random points of an elliptic curve, there are about 2^256 of them.
Publlic keys are also points on a curve, they generated from private keys using a complicated (bijective?) elliptic curve based function, there are also about 2^256 of them.
Addresses are generated by hashing the private key, there are about 2^160 of them.
Therefore, there are about 2^(256-160)=2^96 keys per address.
If you search keys randomly for one containing bitcoin (the hard part, but RawDog apparentlly has a quantum computer running Grover's algorithm in his basement...and probably a nuclear reactor to provide power), if you find one, it is very likely to be a different one than the one that was originaly used.

Therefore, RawDog can offer to return the coins in exchange for the orginal key, and publish both keys to prove the hash collision.
However, that would not prove that RawDog found a preimage, and collisions in hash160 actually do not actually impact the security of bitcoin if used properly because a preimage is needed to steal coins from an existing address.
In fact, it only takes about 2^80 time to find a hash160 collision, this can is barely in the realm of classical computing (as far as I know, it also requires 2^80 space, which is quite impractical, but there may be a time-space tradeoff I don't know about).
The simplest way to prove a preimage is to find something that hashes to 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000, then publish it.
So RawDog, if you want to convince people of the existance of your super-fast quantum computer, set it to work on finding a preimage to the zero string, and collect the 56.80944011 BTC on it:
https://blockchain.info/es/address/1111111111111111111114oLvT2

[AgentofCoin]

It is interesting you would write all the above to only say that it is "irrational".
Nothing you stated directly refutes what I have stated.
Quantum mechanic's current understanding is exactly what I have stated.
If you read more on it, you will ultimately be forced to agree.

The term "superposition" is not a buzzword. I am baffled by that comment.
My comments are strictly as to Quantum physics and the Schrodinger's Cat
example as to address collision, and have nothing to do with quantum computing.

Prior to your most recent statement, I am not aware of anyone making a comment
as to quantum computing in this thread.

Nevertheless, quantum computing, as you are defining, is the simplest level of that form
of operation. As it becomes more advanced, things you consider "mystical" can be performed.
The mathematics already predict those outcomes, no matter how bizarre and irrational to some
people it may seem to be.

quantum theory
quantum mechanics
quantum computing. is all about quanta

in short once you pull away the big science buzzwording. its the simple fact of... more options.(quantity quantitate)

quantum theory can go so absurdly irrational that quantum theorists would think that it was ok to escalate the amount of options of Schroedinger cat to hypotheses that while in the box an asteroid can enter the earth's atmosphere and cause a sonic boom which echo's inside the box and scares the cat into having a heart attack so the chances of death are higher.

thats just one example of where trying to bring quantum theory into a debates can end up going down an irrational rabbit hole.

as for me taking the opportunity to meander an already meandered topic even further off topic(of collisions) i tried to redirect it back into the realm of other conversations in other topics (bitcoin based, not cat death based) to explain quantum computing.. seeing as this is a bitcoin forum and more people care about quantum theory in regards to bitcoin, rather than a cat

lastly i said mythical
meaning a myth a theory a story.
anything is a myth until it is busted.

i prefer science fact when dealing with current and future tech. and although quantum does open up more options, sticking to rational and practical idea's without doing deep into a rabbit hole of absurd possibilities is what i try to keep to

There is no such thing as facts in science, there is only theories that have
stood the test of time, and people regard those ongoing theories as facts.
Many things you might refer to as facts are actually still theories, such as
gravity. Personally, I believe in gravity, but that does not mean it is the
correct final answer to the question, just that it currently fits our
understanding as well as answers other problems correctly in addition.

Observation changing outcomes and superpositions are not buzzwords
nor irrationalities and absurdities. They are considered standard today.

What you consider a rabbit hole, sometimes leads to new ideas and
answers. I'm pretty sure many influential physicist of the past and even
Satoshi himself went down a few rabbit holes. At one time in history,
banging certain rocks together to create fire was considered a rabbit hole.

Unknown address collision being like quantum superstates is at least a little
more interesting than the average convo on this forum. Whether it is something
worth discussion at all here, is different than disregarding it as pseudoscience.

[RawDog]

Private keys are random points of an elliptic curve, there are about 2^256 of them.
Publlic keys are also points on a curve, they generated from private keys using a complicated (bijective?) elliptic curve based function, there are also about 2^256 of them.
Addresses are generated by hashing the private key, there are about 2^160 of them.
Therefore, there are about 2^(256-160)=2^96 keys per address.
If you search keys randomly for one containing bitcoin (the hard part, but RawDog apparentlly has a quantum computer running Grover's algorithm in his basement...and probably a nuclear reactor to provide power), if you find one, it is very likely to be a different one than the one that was originaly used.

Therefore, RawDog can offer to return the coins in exchange for the orginal key, and publish both keys to prove the hash collision.
However, that would not prove that RawDog found a preimage, and collisions in hash160 actually do not actually impact the security of bitcoin if used properly because a preimage is needed to steal coins from an existing address.
In fact, it only takes about 2^80 time to find a hash160 collision, this can is barely in the realm of classical computing (as far as I know, it also requires 2^80 space, which is quite impractical, but there may be a time-space tradeoff I don't know about).
The simplest way to prove a preimage is to find something that hashes to 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000, then publish it.
So RawDog, if you want to convince people of the existance of your super-fast quantum computer, set it to work on finding a preimage to the zero string, and collect the 56.80944011 BTC on it:
https://blockchain.info/es/address/1111111111111111111114oLvT2

Your dumb fucking idea relates to finding the key to 1 specific address.  I am looking for the key to any of millions addresses that have bitcoin stored on them.  So, my problem is much, much, much easier than your stupid problem.  

That is why it is possible to find some bitcoin on an address - because I am not trying to find the key to just one single address.

Fucking stupid people piss me off.

[Some Mouse]

Private keys are random points of an elliptic curve, there are about 2^256 of them.
Publlic keys are also points on a curve, they generated from private keys using a complicated (bijective?) elliptic curve based function, there are also about 2^256 of them.
Addresses are generated by hashing the private key, there are about 2^160 of them.
Therefore, there are about 2^(256-160)=2^96 keys per address.
If you search keys randomly for one containing bitcoin (the hard part, but RawDog apparentlly has a quantum computer running Grover's algorithm in his basement...and probably a nuclear reactor to provide power), if you find one, it is very likely to be a different one than the one that was originaly used.

Therefore, RawDog can offer to return the coins in exchange for the orginal key, and publish both keys to prove the hash collision.
However, that would not prove that RawDog found a preimage, and collisions in hash160 actually do not actually impact the security of bitcoin if used properly because a preimage is needed to steal coins from an existing address.
In fact, it only takes about 2^80 time to find a hash160 collision, this can is barely in the realm of classical computing (as far as I know, it also requires 2^80 space, which is quite impractical, but there may be a time-space tradeoff I don't know about).
The simplest way to prove a preimage is to find something that hashes to 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000, then publish it.
So RawDog, if you want to convince people of the existance of your super-fast quantum computer, set it to work on finding a preimage to the zero string, and collect the 56.80944011 BTC on it:
https://blockchain.info/es/address/1111111111111111111114oLvT2

Your dumb fucking idea relates to finding the key to 1 specific address.  I am looking for the key to any of millions addresses that have bitcoin stored on them.  So, my problem is much, much, much easier than your stupid problem.  

That is why it is possible to find some bitcoin on an address - because I am not trying to find the key to just one single address.

Fucking stupid people piss me off.

Forgive my ignorance but can you explain more on how determining if Bitcoin is actually on an address or not add the complexity of the problem? To my understanding you would need an indexed database addressed synced with the blockchain or to use a 3rd party service api which I assume is much slower then having your own indexed db.

[SaltySpitoon]

Collisions are actually far easier than you think.  I am working on that now.

Stay tuned.

Just think, my VanityGen trys about 880,000 keys per second.  Every hour, I check over 300 million keys.  Still think I won't find a collision?  There has to be one out there somewhere.

Nope. 300 million seems like a lot until you realize billions, trillions, quadrillions, octodecillions are nothing compared to the probability of a collision. I'll have to find my post referencing it, but I wrote a paper on electron/atom phasing. Theres a really old story about shaolin monks being able to phase through solid objects, with their proof being a man who was found part way through a wall, with no damage to the wall and various other structural engineering things that I don't care about that show that he wasn't built into the wall. Without getting too deep into the theory of it, the electrons in your atoms have a chance of passing through those of another substance if they hit together at the same resonant frequency, causing the atoms to effectively "teleport" through material. There are a few octillion atoms in a human body (1x10^27). Again, I'd have to find all of the math again to actually prove it to you, so take this as anecdotal evidence until I do, but my conclusion was that if 7 billion people on earth walked into walls non stop for 76 years without break, with a 1 second interval between bumping into the wall and trying again, there was something like a 0.75% chance that someone would walk through a wall.

That is a far greater chance of happening than finding a collision. People always post that infographic talking about converting the solar system into energy and creating a perfect quantum computer. I'm saying you have a much higher chance of walking through a wall than colliding. Is it impossible? Well, I suppose not, there was that monk that was inexplicably found in a wall. But the chance is so low, its not worth wasting your time on.

Generate some neat Bitcoin addresses, and sell them. Use the proceeds to buy lottery tickets.


*edit* Google has a DWave Quantum computer that you can rent for $10-20k/hour of compute time. I wouldn't be surprised if someone has already tried to use it to find a collision.

[ArcCsch]

Your dumb fucking idea relates to finding the key to 1 specific address.  I am looking for the key to any of millions addresses that have bitcoin stored on them.  So, my problem is much, much, much easier than your stupid problem.  

That is why it is possible to find some bitcoin on an address - because I am not trying to find the key to just one single address.

Fucking stupid people piss me off.

(Over)estimate of total hashes taken for mining bitcoin:
nhash=(2 *10^18/second)(8years)(pi*10^7 seconds/year) < 2^89
Number of addresses containing bitcoin:
ncoin<21000000BTC/(10^-8 BTC)<2^51
Number of addresses:
naddress=2^160
Multiplying:
ncoin*nhash<2^140
prob=naddress/(ncoin*nhash)<2^-20<0.000001
Therefore, if you spend all the mining power ever used by the network, you have less then a one-in-a-milion chance of finding anything.
Also, note that all my estimates are very heavily slanted in your favor, and I am ignoring the time taken by list comparisons.
Yes, I did not include the fact that miners actually take two hashes, but this is canceled by the fact that addresses with one satoshi are not worth hacking.
In conclusion, if RawDog has so much hashpower, he should probably mine instaid, or go on with the quantum supercomputer (while you are at it, don't forget to build a nuclear reactor to power it).

Theres a really old story about shaolin monks being able to phase through solid objects...

Another good one:
There is a story about an Indian temple in Kashi Vishwanath which contains a large room with three time-worn posts in it surrounded by 64 golden disks. Brahmin priests, acting out the command of an ancient prophecy, have been moving these disks, in accordance with the immutable rules of the Brahma, since that time. The puzzle is therefore also known as the Tower of Brahma puzzle. According to the legend, when the last move of the puzzle will be completed, the world will end. It is not clear whether Lucas invented this legend or was inspired by it.
Who do you think would succede first, RawDog or the Brahmin priests?

[Lauda]

Your dumb fucking idea relates to finding the key to 1 specific address.  I am looking for the key to any of millions addresses that have bitcoin stored on them.  So, my problem is much, much, much easier than your stupid problem.  

Wrong. The 'fastest' method would be a birthday attack, and you still need O(n/2) operations (i.e. 2^128 operations for SHA256 if you had enough memory). Just because you aren't looking for a specific key to collide with, that doesn't really make it likely to find a collision in this case.

Nope. 300 million seems like a lot until you realize billions, trillions, quadrillions, octodecillions are nothing compared to the probability of a collision.

Let's add some numbers in here:

In order to spend money sent to a Bitcoin address, you just need to find a ECDSA public key that hashes to the same 160-bit value. That will take, on average, 2^160 key generations.

Supposing you could generate a billion (2^30) per second, you need 2^130 seconds.

Doing this in parallel using a billion machines requires only 2^100 seconds.

Getting a billion of your richest friends to join you gets it down to only 2^70 seconds.

There are about 2^25 seconds per year, so you need 2^45 years.

The age of the Universe is about 2^34 years so far — better get cracking!

Source.

[shorena]

-snip-

-snip-
Id say the collision happened even when no one noticed it. Shit already broke you just didnt realize it yet. Whoever sends coins to the address in question first will reveal the information to the other person also in control.

Not according to quantum theory.

Storing data on a disk is not a quantum thing though. Even if, the data was stored at the very least in memory by a machine and thus it was observed. Furthermore it was not only observed but also modified and stored.

Your dumb fucking idea relates to finding the key to 1 specific address.  I am looking for the key to any of millions addresses that have bitcoin stored on them.  So, my problem is much, much, much easier than your stupid problem.  

Wrong. The 'fastest' method would be a birthday attack, and you still need O(n/2) operations (i.e. 2^128 operations for SHA256 if you had enough memory). Just because you aren't looking for a specific key to collide with, that doesn't really make it likely to find a collision in this case.

Nope. 300 million seems like a lot until you realize billions, trillions, quadrillions, octodecillions are nothing compared to the probability of a collision.

Let's add some numbers in here:

In order to spend money sent to a Bitcoin address, you just need to find a ECDSA public key that hashes to the same 160-bit value. That will take, on average, 2^160 key generations.

Supposing you could generate a billion (2^30) per second, you need 2^130 seconds.

Doing this in parallel using a billion machines requires only 2^100 seconds.

Getting a billion of your richest friends to join you gets it down to only 2^70 seconds.

There are about 2^25 seconds per year, so you need 2^45 years.

The age of the Universe is about 2^34 years so far — better get cracking!

Source.

Your source is wrong slightly off as it ignores the birthday paradox. Due to it, on average you have found a collision after checking half of the keyspace with almost certainty. Thus you only need 2^159 key generations. Not that it changes the numbers in any significant way.

[pawel7777]

...
Your source is wrong slightly off as it ignores the birthday paradox. Due to it, on average you have found a collision after checking half of the keyspace with almost certainty. Thus you only need 2^159 key generations. Not that it changes the numbers in any significant way.

Why half? According to the birthday paradox, you'd have near certainty (99.9%) of finding 2 people with matching birthday with as little as 70 people. So wouldn't you need roughly one fifth (366/70) of the key space?

Also, doesn't the "2^160 generations" relate to finding any collision (defined as randomly generating 2 identical priv keys), so including zero-balance ones (also those previously generated by attacker)? If so, finding collision with specific (non-zero) addresses would be a lot harder.

And is the birthday paradox even applicable for targeting specific addresses? I thought it's only about finding any matching pair.

[shorena]

...
Your source is wrong slightly off as it ignores the birthday paradox. Due to it, on average you have found a collision after checking half of the keyspace with almost certainty. Thus you only need 2^159 key generations. Not that it changes the numbers in any significant way.

Why half? According to the birthday paradox, you'd have near certainty (99.9%) of finding 2 people with matching birthday with as little as 70 people. So wouldn't you need roughly one fifth (366/70) of the key space?

It just goes for a higher probability (I dont remember how many decimal 9 digits, but its essentially 100%) and a factor two is easier to handle since almost all of these calculations are done for binary numbers.

Also, doesn't the "2^160 generations" relate to finding any collision (defined as randomly generating 2 identical priv keys), so including zero-balance ones (also those previously generated by attacker)? If so, finding collision with specific (non-zero) addresses would be a lot harder.

There are 2^256 different private keys, but because of the use of RIPEMD-160 it is assumed that 2^96 private keys result in the same address. Compressed und uncompressed pubkey are usually ignored. IIRC You try to find a collision with one specific address, thus finding one with a balance would be easier as your chance increases from 1 in 2^160 to ~8*10^7 in 2^160.

Finding a collision with any hash you create yourself is even easier as it would only take 2^80 operations. -> https://en.wikipedia.org/wiki/Collision_attack#Classical_collision_attack

And is the birthday paradox even applicable for targeting specific addresses? I thought it's only about finding any matching pair.

Yes, its just an example for a more general problem -> https://en.wikipedia.org/wiki/Birthday_problem#Cast_as_a_collision_problem

[DannyHamilton]

...
Your source is wrong slightly off as it ignores the birthday paradox. Due to it, on average you have found a collision after checking half of the keyspace with almost certainty. Thus you only need 2^159 key generations. Not that it changes the numbers in any significant way.

Why half? According to the birthday paradox, you'd have near certainty (99.9%) of finding 2 people with matching birthday with as little as 70 people. So wouldn't you need roughly one fifth (366/70) of the key space?

Keep in mind that there will NEVER be more than 2.1 X 10¹⁵ addresses that have any bitcoins in them at all at any given moment in time.  (And in reality the number will be MUCH less.)

The birthday paradox assumes that there are 365 possibilities, AND as you add more people (attempts), more of those possibilities are occupied which increases the chance of colliding.

With bitcoin, the number of occupied (bitcoin storing) addresses is fixed at less than 2.1 X 10¹⁵, and doesn't increase beyond that as more addresses are generated.  As such, the odds of any randomly generated address colliding with a bitcoin storing address don't increase the way they do with the birthday paradox.

As shorena has pointed out, what does increase is the odds that you will collide with one of the empty addresses that you already generated.