Topic: About Collision (Read 2143 times)

Yes, that youtube comment is from me.


When cracking passwords, exhaustive search with a character set is the last thing one tries. Breaking weak passwords and passphrases dozens or characters long or more is common with the proper tools.

Agreed that current data drives and their storage ability are not directly using quantum
mechanics. My statements within this thread, originated after Danny commented to Franky's
statement: "schrodinger's cat - if you cant see it, did it really happen?", which Danny then advised
was not about whether it really happened, but that both have already occurred and both exist according
to quantum mechanics. I then commented about address collision in the context of superposition which
Danny expounded upon prior, and I stated that the blockchain may observe this collision itself. You then
commented to me stating "Id say the collision happened even when no one noticed it. Shit already broke
you just didnt realize it yet.". Then I replied stating that address collision happening without observation
is not possible in quantum theory, which was the only way I was discussing the topic from the start.
I was never saying or intending to say that Bitcoin address collision is actually occurring on a quantum
state, just the address collision prior to observation can be likened to the superposition in quantum
mechanics.

So it is interesting because the thread is about probability of address collision which can
be quantified, as you guys have done so already, but address collision like a superstate can not be,
and in that way, you can not tell me whether a collision has already occurred naturally, but only its
probability prior to observation. When the observation is made, and we can "know" yes or no, then
I no longer have interest since it has been solved and defined.

The reality here is that we are both correct as to our opinions and understanding, it is just that you
are talking about address collision in the probability provable sense and I am talking about it in the
quantum sense. We are both correct, but my comments should only be taken in the abstract, since
Bitcoin address collision clearly is not occurring on a true quantum level. Though it could be argued,
on the abstract, that all possible address collisions have already occurred prior to the creation of
quantum storage since that data would not be bound by spacetime, but that is another issue.

I did not intend to convey that unknown address collision was in fact a quantum superstate.

Fools and their fancy math theories.  You'll have your proofs once I take your bitcoin. 

It is 'mathematically impossible' (1/64,000,000) to win the lottery too, yet someone does it every week. 

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.

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.


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


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

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.

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

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.

Let's add some numbers in here:
Source.

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

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.

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.

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.

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.

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

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

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.

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

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.

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.

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