Collisions

[brawdias]

I googled about this term but I am still not able to understand what collisions are. Can you explain a real example for a begginer ?  People are losing money because of that? Any cryptocurrency protected against that?

[jackg]

I googled about this term but I am still not able to understand what collisions are. Can you explain a real example for a begginer ?  People are losing money because of that? Any cryptocurrency protected against that?

Bitcoin IS protected against collisions (as far as we know).

To understand this a bit better we need to look into the bitcoin protocols:
1. A bitcoin address is the hash of the private key.
2. The private key is the only thing that controls the money on the network.

If we imagine a bitcoin address is a number from 1 to 1000000 (for example) and a private key is 1 to 1000000000000. The modulus of an address max (the division after a remainder) is considered the hash.
Say a private key of 1000000000001
The modulus of this with 1000000 = 1
The modulus of the private key 1100000000001 with 1000000 would also spit out a remainder of one. That's a collision and it's a big issue when it happens.

Bitcoin uses a hashing algorithm of SHA256 which is still considered computationally secure/collision free (as far as I know).

When funds are sent, they're sent to an address. If two addresses match, BOTH private keys can spend the funds. As miners only have the address to hash when an input is signed. Therefore, this causes a huge issue if a collision gets found.


Something that is mistaken as a collisions is a mutual generation of the SAME private key and it's normally due to bad number generation (either intentional or accidental). It is partly the reason why things such a vanity addresses (where you try to get a specific address by mining for it through multiple ones that follow the same protocol rules) are considered less secure than regular RANDOM addresses.

[cellard]

There is a project called "Large Bitcoin Collider" in which they constantly generate keys and try to find a private key that has funds on them. They claim they have found several private keys and some of them had funds?

https://lbc.cryptoguru.org/trophies

How come? there must be something going on about that. I would like to know how these keys were generated. Weak wallet? I hope none of these belong to a Bitcoin Core generated address..

[jackg]

There is a project called "Large Bitcoin Collider" in which they constantly generate keys and try to find a private key that has funds on them. They claim they have found several private keys and some of them had funds?

https://lbc.cryptoguru.org/trophies

How come? there must be something going on about that. I would like to know how these keys were generated. Weak wallet? I hope none of these belong to a Bitcoin Core generated address..

These aren't really collisions. They're just mining addresses to check for funds.

Normally bad number generation is the culpret. I do like testing my computers' random number generator by certain programs before generating any private key-public key pair to at least see the sudo-randomness is still random enough.

They also seem to be mining addresses that have no funds in them also which is fairly useless. I'd also question whether their script is good or whether they use it to pull users' private keys from their computers also... (which is probably more likely).

[mattcode]

Normally bad number generation is the culpret. I do like testing my computers' random number generator by certain programs before generating any private key-public key pair to at least see the sudo-randomness is still random enough.

What tool do you use to audit randomness?

[jackg]

Normally bad number generation is the culpret. I do like testing my computers' random number generator by certain programs before generating any private key-public key pair to at least see the sudo-randomness is still random enough.

What tool do you use to audit randomness?

I built a generator myself that selects random numbers and adds to each count by one each time based on the nubmers index in a list. It's not a very efficient program but it doesn't really need to be. I run a few million iterations of numbers between 1 and 1000 normally just to check everything is at the right average.

E.G

Code:

n[int] = array[length:1000]
For (n→0 to n→1000000)
                nTmp = produce random number between 1 and 1000
                array[nTemp] += 1
                n += 1

Is the general gist. You'd obviously run it across a few different languages/compilers just in case they use different amounts than bitcoin core uses.

[bob123]

There are 2 terms of collisions related to crypto.
The first (address collision) has already been explained pretty detailed by jackg.
The other form of 'collision' which you could be talking about would be hash collision.

A hash collision is found when you found a X and Y which does produce the same hash (e.g. sha256(x) = sha256(y)).
Finding a hash collision (or better: being able to find appropriate hash collisions; which can't be done without advanced quantum computers) would reduce the security of BTC dramatically.

There hasn't been a hash collision for sha256 yet. A lot of technologies rely on sha256 to be collision resistance.
The first quantum computers in a few years (or decades) won't be able to 'crack' those hashes.


What exactly related to 'collisions' are you interested in?

[wilwxk]

Normally bad number generation is the culpret. I do like testing my computers' random number generator by certain programs before generating any private key-public key pair to at least see the sudo-randomness is still random enough.

What tool do you use to audit randomness?

You dont really need a tool to audit the randomness of the bitcoin software, you can use a trusted tool like the haveged, generate a random data and use this random data to generate your private key, avoiding to trust in the bitcoin software.

[jackg]

Normally bad number generation is the culpret. I do like testing my computers' random number generator by certain programs before generating any private key-public key pair to at least see the sudo-randomness is still random enough.

What tool do you use to audit randomness?

You dont really need a tool to audit the randomness of the bitcoin software, you can use a trusted tool like the haveged, generate a random data and use this random data to generate your private key, avoiding to trust in the bitcoin software.

Actually, yes, that's another step.
There was a service suggesting that you roll a 6 sided die a certain number of times to generate yourself a private key that is totally random.

[bob123]

There was a service suggesting that you roll a 6 sided die a certain number of times to generate yourself a private key that is totally random.

Dice tossing seems to be random but in reality only is pseudorandom.
Each small 'anomaly' of the dice could already hurt the randomness. Thats also the reason why casinos are always replacing/renewing their dices. To get as close as possible to randomness.

While a dice isn't completely random it probably won't play any role when creating a private key since the variance is too low to be exploited.
Generating true randomness is a tough task.

[jackg]

There was a service suggesting that you roll a 6 sided die a certain number of times to generate yourself a private key that is totally random.

Dice tossing seems to be random but in reality only is pseudorandom.
Each small 'anomaly' of the dice could already hurt the randomness. Thats also the reason why casinos are always replacing/renewing their dices. To get as close as possible to randomness.

While a dice isn't completely random it probably won't play any role when creating a private key since the variance is too low to be exploited.
Generating true randomness is a tough task.

Everything that exists is pseudorandom. Everything has limits to the randomness that can be created. Dropping coffee beans or marbles onto a surface has a limit to the number of random places it can be based on the size of the area the balls are dropped on and also the central point of the fall (if you do it enough times then it'll happen in the same way twice).

Obviously, the ability of something being random should be measured before trying to use it to make a private key. Rolling a dice 100 times at least and noting down a tally of the values you get each time (and then look for the simple comparirsons you can draw from there to determine the accuracy of the dice you're using).