7
$\begingroup$

When creating a Bitcoin account, you need to issue a couple of private/public ECDSA-keys. Then, you derive your account address by taking a 160-bit hash (through sha-256 and ripemd) of the public key and use a custom base58 algorithm to convert it to alphanumerical values (see the picture below, I took it from this page).

Computing Bitcoin Keys

My question is that collisions might happen (not necessary malicious ones, but incidental ones). I would like to know if there is a specific mechanism in the Bitcoin protocol to sort out these collisions and be ensured that the payment is going to the right place.

In fact, I tried to look down at the protocol details but could not find anything dealing with this problem. The only reference I found is on the Bitcoin-wiki and it states that:

Collisions (lack thereof)

Since Bitcoin addresses are basically random numbers, it is possible, although extremely unlikely, for two people to independently generate the same address. This is called a collision. If this happens, then both the original owner of the address and the colliding owner could spend money sent to that address. It would not be possible for the colliding person to spend the original owner's entire wallet (or vice versa). If you were to intentionally try to make a collision, it would currently take 2^107 times longer to generate a colliding Bitcoin address than to generate a block. As long as the signing and hashing algorithms remain cryptographically strong, it will likely always be more profitable to collect generations and transaction fees than to try to create collisions.

It is more likely that the Earth is destroyed in the next 5 seconds, than that a collision occur in the next millenium.

I found this explanation extremely unsatisfactory... If some of you has a better explanation than that or knows about a prevention mechanism that has been planted into the Bitcoin protocol, I would be delighted to read from it.

$\endgroup$
  • 10
    $\begingroup$ Why is "it's very unlikely to happen" unsatisfactory to you? That statement is at the heart of all crypto. $\endgroup$ – CodesInChaos Mar 19 '16 at 10:21
  • $\begingroup$ Well, I know that occurrences of such collisions will happen with a very low probability. And, this is fine for me. But, at least, I would have expected that, during the creation of a BTC address, one would check that the current address does not appear in the blockchain... But, still, this is not enough as the creation should occurs in a decentralized manner, so two addresses in collision might be created a the same time and checking the blockchain at the same time as well (I agree that we are here speaking of an extremely low probability). $\endgroup$ – perror Mar 19 '16 at 10:29
  • 1
    $\begingroup$ You'd expect a collision after $2^{80}$ public keys. This is only feasible (maybe) for state-sponsored attackers with massive supercomputers. The chance of this happening in the wild is extremely low. $\endgroup$ – SEJPM Mar 19 '16 at 12:09
  • 1
    $\begingroup$ To add to @SEJPM, that is a collision of the public-key hash after $2^{80}$ public keys. It is still likely that you will not have a colliding private key. $\endgroup$ – mikeazo Mar 19 '16 at 16:56
  • 1
    $\begingroup$ Once again, I do not want to consider a malicious attacker, but a "shit happen" case. The fact that you have $1/2^{80}$ chance to get it does not means that this will never happen... $\endgroup$ – perror Mar 19 '16 at 19:05
7
$\begingroup$

Cryptography (and real security in general) offer quantitative analysis of the security provided - Meaning, real security products will describe how long they will resist a certain class of attack.

With cryptography, we select our parameters such that the time required to perform the best attack would exceed the amount considered to be practical, realistic, or feasible.

With a larger input space then output space, collisions must exist - therefore the only solution is to:

  • Accept that collisions must exist
  • Make collisions so rare as to not be a problem

This is exactly what the bitcoin protocol has more or less done. Granted, $2^{80}$ could arguably be a little bit bigger for more comfort; Bitcoin could have used bigger hash functions, but they may have been limited by availability at the time. If you were going to re-design it, I'm sure you would use larger sizes now. But that's always easy to say in retrospect...

$\endgroup$
  • 1
    $\begingroup$ It takes $2^{80}$ hash invocations to find a collisions, but $2^{-80}$ is not a meaningful probability in this here. $\endgroup$ – CodesInChaos Jul 4 '17 at 17:18
2
$\begingroup$

In this application we don't care about attackers generating collisions with themselves. What we care about is.

  1. Two legitimate users inadvertently generating the same address.
  2. An attacker deliberately trying to generate collisions with the addresses of existing unspent outputs.

We can't reduce the risks of these to zero but we can reduce them to negligible levels.

Lets consider case 1 first. I don't know a good way to find the total number of addresses that have ever been used but we can get an upper bound by taking the size of the blockchain and dividing it by the size of an address. The blockchain is now about 150GB, divide that by 20 gives us an upper bound of about 7.5 billion addresses. 7.5 billion is approximately $2^{33}$. In reality the blockchain contains a lot more than just addresess and so I expect the real number is going to be lower than this since the blockchain carries a bunch of stuff other than addreses.

The probability of an accidental collision can now be approximated by the equation.

$$p \approx \frac{n^2}{2m}$$

If we assume there are $2^{33}$ addresses in use and we assume that the hash function is uniform then the chance of an inadvertent collision is.

$$p \approx \frac{2^{66}}{2^{161}} = \frac{1}{2^{95}}$$


Now onto the malicious side. The malicious actor is attempting to find an address collision with an "unspent" output. Finding a collision with an output that has already been spent doesn't help him.

According to https://blockchain.info/charts/utxo-count there are about 67 million unspent outputs. 67 million is approximately $2^{26}$ so the probability of the attackers hash matching an existing unspent output is about $\frac{1}{2^{133}}$.

Now of course the attacker can try many times. Lets assume that generating an address takes the same effort as attempting to hash a block (in reality it takes more). Lets assume that the attacker has as much hashing power as the whole bitcoin network put together and that they run their attack for a century. The total bitcoin network hashrate is about $2^{64}$ hashes per second and there are about $2^{32}$ seconds in a century.

$p \approx \frac{1}{2^{133}} \times 2^{64} \times 2^{32} = \frac{1}{2^{37}}$

Bottom line, it's far far easier to mine bitcoin legitimately than to steal it through hash collisions.

$\endgroup$
-4
$\begingroup$

Actually you people are missing one simple factor in your calculations that is often omitted. If you were the crypto experts you claim to be you would not so easily brush off his question as stupid. Arrogance and assumption is the calling card of weak security policy.

What are you missing? Some crypto wallets are being generated by seeds from human input, which are MORE likely to produce a collision compared to randomly generated seeds. If you would like to argue the math and common sense of this fact, you will lose.

You should understand the difference between truly random and pseudo-random and how that applies to crypto. A seed is essentially a password in the application of crypto currency wallets. Which is better? A truly random password or a pseudo-random password? You and I know that answer to this question and it's not debatable.

While I'll agree that collision is highly unlikely given the scope of possible key sequences, it IS NOT as unlikely as some have proposed simply because there is a human factor involved.

OP, your question is valuable and so is your concern. The answer to your question is there are no checks in place for this collision problem. Devs have taken the lazy approach and relied on pure probability, even though history is full of examples where such assumptions failed. Instead of actually coming up with a good solution they have kicked the can down the road and left it to chance. A good chance btw but STILL chance.

$\endgroup$
  • 2
    $\begingroup$ This is Crypto.SE where we handle cryptographic things. The fail due to "human factor" you describe is an implementation problem (programming) which merely shows that cryptography, just like everything else, will fail when humans decide to ignore the exact and clearly defined (in this case cryptographic) guidelines and specifications provided. What you are saying compares to blaming breathing from being insufficient to survive because some human might decide to stop doing it. While humanity has definitely evolved during past millennia, there's no failsafe for idiocracy (here: inapt coders). $\endgroup$ – e-sushi Jan 6 '18 at 2:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.