Accidental Collisions

Success!

I must report a small victory in my crypto journey. After two days of trying, I was finally able to split my pre-August bitcoin into two coins each with its own B slightly tilted in two opposite directions. Yay! I first transferred all the coins away from the original wallet, then exported my private keys into a notepad, found the right address pair, entered it into an Electron wallet, and voila, saw my assets as BCC. The problem was that the wallet showed all the coins transferred out (?!), with “unconfirmed” next to it.

I panicked a bit at first, went to blockchair.com to check my address which still showed all the BCC in place and BTC transferred out as it should be. Tried to work with ABC Wallet but before it managed to download all the history of the bitcoin chain, with all its splits and forks and -wits to date, my Electron came to its senses and showed the correct balance.

A concern…

What it confirmed to me, - in addition to the self-promotion from a tyro to a novice, - was how easy it is to claim the assets assigned to any address if its private key is known. Since any key pair is unique, any generated and published public key is forever vulnerable to eventual, accidental, or not so accidental, collision with another randomly generated public key, and whoever knows the private key can claim the assets assigned to that public key.

In my understanding, all the cryptos operate the same way and thus possibly are vulnerable to this “perceived” flaw in the system. Let me say that I am very far from being a “techy” type. I only read and learn as much as necessary to move forward with what I have to do. It has been a fascinating process to dig in and understand technology behind the cryptosphere. May be this absence of sufficient experience still does not allow me to brush off the accidental collisions concern with ease. Over the past couple of months I have found myself coming back to this issue, especially as the markets keep climbing up undeterred, and the number of participants grows.

Reaching out for answers

I went on a Slack forum to ask about it, and here is an edited exchange featuring the most relevant comments:

“Bittax Question (BQ): Accidental collisions are an obvious problem. I am surprised that bitcoin came as far as it has now. Am I correct in thinking that it is possible for a random address generator to generate the same address as an existing address and thus cause a “collision,” where two key holders will be in possession of the same private key that opens the same public key?

Answer/Comment (A/C): Essentially it’s 100% certain there is going to be an address collision when you randomly generate addresses. This collision is so rare that it can take over 1 million years to popup or tomorrow. If you have a neat solution to solve this then you are welcome to share them with us. (Bittax: do you?)

A/C: I think I calculated the odds for collision on Bitcoin and it was a number like 64 zero's behind it...

A/C: I agree that it might be a point people make in the future but the math is the math - you're infinitely more likely to lose your funds to the bank literally collapsing before an address collision steals your funds.

A/C: Has there ever been even one actual collision reported in the history of crypto? (Bittax: I am not aware of any such situation but would be great to hear if anyone was. The crypto has not been that popular yet.)

A/C: I agree with a concern of collision, but my bank messes up way more than even the dumbest hashes collide..
Bittax comment: Sure, but a bank returns your money after a bit of screaming. Not possible here.

A/C: Am I mistaken in thinking that the worry should more be with intentional collisions rather than random? (Bittax: this person hit the issue right on the head, that’s what I am mostly worried about.)

A/C: Regarding your concerns of collision in ... there is 68^62 potential addresses = 4,1262219762811934458417701385818e+113. Random Generating the exact same address twice in our lifetime doesn’t seem likely. (Bittax: however, if this technology is to be built for the lifetimes of many generations to come, that’s how the investors are viewing it, is the foundation strong enough?)

A/C: How did this dumb s---t ended up on this channel?

A/C: Well if someone knows your private key then they can sign for you and spend all your funds. But guessing a private key is impossible.

BQ: One doesn't need to “guess” a particular key, all is needed is to know various randomly generated key pairs. When a known key pair pops up on the blockchain, one can see the public key, see how much money is in there, wait till there is "enough," and pull the trigger. It might take five, ten, fifteen, or fifty years but a distinct threat. It’s like fishing on a quiet lake, all you need is patience.

A/C: No..Number space too big.. One of the consequences of the second law of thermodynamics is that a certain amount of energy is necessary to represent information. To record a single bit by changing the state of a system requires an amount of energy no less than kT, where T is the absolute temperature of the system and k is the Boltzman constant. (Stick with me; the physics lesson is almost over.)

Given that k = 1.38×10-16 erg/°Kelvin, and that the ambient temperature of the universe is 3.2°Kelvin, an ideal computer running at 3.2°K would consume 4.4×10-16 ergs every time it set or cleared a bit. To run a computer any colder than the cosmic background radiation would require extra energy to run a heat pump.

Now, the annual energy output of our sun is about 1.21×1041 ergs. This is enough to power about 2.7×1056 single bit changes on our ideal computer; enough state changes to put a 187-bit counter through all its values. If we built a Dyson sphere around the sun and captured all its energy for 32 years, without any loss, we could power a computer to count up to 2192. Of course, it wouldn't have the energy left over to perform any useful calculations with this counter.
But that's just one star, and a measly one at that. A typical supernova releases something like 1051 ergs. (About a hundred times as much energy would be released in the form of neutrinos, but let them go for now.) If all of this energy could be channeled into a single orgy of computation, a 219-bit counter could be cycled through all of its states.

These numbers have nothing to do with the technology of the devices; they are the maximums that thermodynamics will allow. And they strongly imply that brute-force attacks against 256-bit keys will be infeasible until computers are built from something other than matter and occupy something other than space.

BQ: Thanks! I was not concerned with brute force. Rather with an accident, intentional or unintentional. But thanks, it answers my question. There does not seem to be any specific guards against a possibility of a collision apart from a very low probability.

A/C: Correct..it is counterintuitive at first.. But number space makes that probability infinitesimally small. (Assuming entropy and randomness in keys)”

I found this comment exchange interesting. People seem to have thought about this quite a bit, and concluded that despite an obvious possibility, there is not much to worry about.

Speculations

Here is my take on it. We marvel at how the universe, our galaxy, and the solar system have all come together. How little probability we might have had to be making our terrestrial journey as planet Earth and as people on this planet. There might have been a different planet with a different name with different creatures on it but instead this is us. If we are creating millions of universes inside of our digital crypto realm, why would accidents be so improbable from occurring when we see how many wonderfully random events came together to create everything around us? I am not saying that someone could “guess” a random pair, I am saying that eventually (may be even during the next hundred years) random key generators will start generating the keys that have been generated previously and thus collisions will occur.

This is not a FUD (“fear uncertainty and doubt”) opinion. I am investing money, time, and effort into this technology alongside with everyone else, and would like to be wrong on accidental collisions. But no one was able to make me doubt the conclusion.

What if there is someone who keeps generating various random keys, billions of them. Say that he or she or them can generate one key every three seconds. Let’s say that this bad actor operates one hundred computers designed for this task. In one year, it’s possible to have a database of only one billion of such key pairs. That’s a tiny fraction, of course. But remember that we are patiently fishing in a quiet lake populated by lazy fish. From the other end, the adoption of the crypto grows. Each person who is moderately involved in this, may generate about thirty new addresses a year on average and use them for various needs. Say thirty billion of new addresses that are waiting to collide with one billion from that rogue database. Very tiny probability indeed.

But the time goes on, year after year, both parties keep on with their tasks. In addition to individuals, there are corporations, businesses, more and more and more. There is lesser and lesser space in our millions of universes with each birthday…. and, finally, a collision takes place. A proven random or by design collision in any crypto is sufficient to sow panic among unprepared investors and users, after which many may sell off and asset values may crumble.
Now, what’s very important, in my opinion, is for all the investors, institutions as well as individuals, to understand clearly how this technology operates. Before investing, they should realize that each time when they create a wallet, an address inside a wallet, they throw a little stone into a huge space of millions of universes and safety of their assets (that may represent a lion portion of their lifetime savings) depends, among other important things, on whether this stone hits another in this blind petanque game.

Questions

Am I wrong to suggest that as a community, we shall anticipate this very remote possibility and build in defenses early on? Is there an issue here either for now or for later? How could/should we address this “issue?”

Do you agree or disagree with me? Do you have any specific ideas which could either make collisions more remote or completely eliminate them? Please, leave your comments or send me a message.

By the way, just to reiterate. We are years away from this becoming a real issue. However, now is the right time to start thinking about.

I am leaving you with a video that I found today. It describes in more details why a collision is possible.