Bitcoin Forum

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?

if you generate a duplicate address (which is not going to happen) all the wallets whether Full wallet or SPV will show you the transactions that said address had before, and you can see that even if there is no UTXO left in it!

and this is apart from the extremely small chance of that happening. i am sure someone is going to come along and break down the math here soon.

if it is a new brand address it has no transaction

If the address wasnt used but someone else also has the private key, you cant know.

schrodinger's cat

if you cant see it, did it really happen?

Not really, the address is either used (for payments) or not. It wouldnt be in a state where both is equally likely.


Thats rather philosophical, but idea that the world only is in motion when humans perceive it is rather strange to me, so yes.

if 2 people have an cat (same address) in a box (wallet address pool of 20-100 addresses yet to be used) but cannot yet see if its an active address ready to jump out and walk around (collide and be spent by other person) or not.. ...  have they yet collided.. :D

my point is that you can never know until you do something.

---

general point to everyone

but to avoid the risks, things like random numbers/wallet seed/private key entropy should be high to avoid the chance.

assume you have the best random entropy that exists today
the chances of you choosing a specific address someone you know already has, colliding with you and/or you finding that same specific address is
2 out of 904625697166532776746648320380374280100293470930272690489102837043110636675

however the chances of a random collision with a random address is
a few million out of 904625697166532776746648320380374280100293470930272690489102837043110636675

if randomness does not produce a random factor of 75digits.. then your not grabbing a private key from the fall allotment of possible keys

EG if randomness was only between 0-200
then it will only produce 200 keys before repeating (colliding) with keys its already produced

EG if randomness was just an 8 character (alphabet only) brainwallet password
then there will only produce 208827064576 keys before repeating (colliding) with keys its already produced

---

there has already been many brain wallet collissions. so yes collissions have happened and will happen
there has already been a few bad RND collissions. so yes collissions have happened and will happen

but to ensure the chances of you colliding. can be mitigated by having a 75 digit random factor to maximise the pool of addresses you can randomly land on

Gmaxwell and others have been advising against brainwallets for a reason... they are not and will never be safe. Just get bitcoin core and backup your wallet.dat, it's the best way to go to avoid weird shit from happening.

I guess electrum is safe if you like that route, but i feel safer with core. Also worrying about this thing is like worrying about the chances of a big asteroid hitting earth and destroying it... it can happen, but the chances are so slow that it's better to not think about it to avoid unnecessary stress.

Hmm, makes sense seen like that.

---

That was not the reason, the reason was and is that humans are bad at producing sufficient entropy for the brainwallet to be random (see the post by franky). This is true for the security of all wallets, if the entropy source sucks a collision is (significantly) more likely.

I think that bitcoin wallet would not allow anybody to have a collision with an existing address that would be not a problem of every users of bitcoin,

well if these kind of problem would occur in bitcoin, people would just make their new account and hope they can get that has a bitcoin on it, There would be an uproar in the bitcoin community that certain bitcoin would just ended up to another person

Your post is a classic example of a useless shitpost. Please stop responding in threads where the subject is out of your league.

This should probably be watched by anyone who wants to use a brainwallet: DEF CON 23 - Ryan Castellucci - Cracking CryptoCurrency Brainwallets (https://www.youtube.com/watch?v=foil0hzl4Pg). He even posted an update (not entirely sure if the account is genuine):

lauda as not only a moderator, but as a sig campaign organiser yourself. you could and should just report him to his sign campaign manager and lose him his earning status. that would shut him up
...


a trillion pass phrases. thats only:
9 alphabet characters deep
8 alphanumeric characters deep
7 alphanumericsymbol characters deep

I've already done that, thank you for the heads up though.

---

Let's get back to the interesting stuff, shall we?

This is actually a very good thought experiment, with the analogy to Schrodinger's cat and quantum uncertainty. I would still be inclined to say that the collision occurred even though it was not observed by anyone. Do collisions that have no impact or have not been noticed by someone matter? I would say no. Even though the chances of one are extremely improbable, it may happen without someone noticing one.

Standard random generators are quite useless for cryptography indeed. For better randomness, one could attempt to map data from some naturally occuring events (aside from the traditional method of using cryptographically safe PRNG e.g. ChaCha20)

The probability of that happening can be close to nothing. I am sure there is a way to check and monitor so that in case it can happen then it can be remedied fast.

i guess if there was a way, there was also a way for a quantum computer in the future to get the private from the unrevealed public key, so it make sense

but it also true that if someone would see his coin vanished for no reason, suddenly, he can see the address at which they are sent and maybe thinking about a collision...

Lauda should be banned.  What a fucktard to talk down to people like that.  This forum is full of shitheads and Lauda is their leader.

I don't think there's going to be anybody "breaking down the math" soon. If that will ever happen, it's going to happen because a user has been lucky or so. Otherwise, if anybody finds a formula that works, I guess they'd go for the wallets rich list which would mean total disaster for Bitcoin, probably a price level of 2011-2012.. going back to that year's level isn't fun for anybody. Although the possibility is very small.. I don't think it never happened. Who knows how many addresses have already been duplicated by mistake when generating them offline and nobody found that out? I have printed over 50 I think, I bet the BTC millionaires have to print thousands to hide their original address.

Does the problem with the random generator problem at Blockchain.info count as a probability killer?  ;D .... I think as soon as something like

this happens, someone would have made a noise about it somewhere. The thing is, IF it happened to you, would you report it? Let's say the

address has 100 bitcoins for example. I doubt that MANY people would say anything, if that happens to them.  ;)

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.

With the address collision issue, there is an eventuality as well, but for the examples to be comparable, the
address collision can not be a natural occurrence, but with an advanced bruteforcing system designed to cause
and find collisions, which would represent the radioactive material in the box.

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.

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.


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.

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

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.



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.

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

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

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

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.

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

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 (https://blockchain.info/es/address/1111111111111111111114oLvT2)

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.

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.

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.

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

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 (https://bitcoin.stackexchange.com/questions/22/is-it-possible-to-brute-force-bitcoin-address-creation-in-order-to-steal-money/3205#3205).

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.

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.

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

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.

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. 

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.

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.