Bitcoin Forum
October 20, 2018, 01:37:29 AM *
News: Make sure you are not using versions of Bitcoin Core other than 0.17.0 [Torrent], 0.16.3, 0.15.2, or 0.14.3. More info.
 
   Home   Help Search Donate Login Register  
Pages: [1]
  Print  
Author Topic: Collisions  (Read 138 times)
brawdias
Newbie
*
Offline Offline

Activity: 84
Merit: 0


View Profile WWW
April 28, 2018, 03:47:13 PM
 #1

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?
1539999449
Hero Member
*
Offline Offline

Posts: 1539999449

View Profile Personal Message (Offline)

Ignore
1539999449
Reply with quote  #2

1539999449
Report to moderator
1539999449
Hero Member
*
Offline Offline

Posts: 1539999449

View Profile Personal Message (Offline)

Ignore
1539999449
Reply with quote  #2

1539999449
Report to moderator
The Bitcoin network protocol was designed to be extremely flexible. It can be used to create timed transactions, escrow transactions, multi-signature transactions, etc. The current features of the client only hint at what will be possible in the future.
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1539999449
Hero Member
*
Offline Offline

Posts: 1539999449

View Profile Personal Message (Offline)

Ignore
1539999449
Reply with quote  #2

1539999449
Report to moderator
1539999449
Hero Member
*
Offline Offline

Posts: 1539999449

View Profile Personal Message (Offline)

Ignore
1539999449
Reply with quote  #2

1539999449
Report to moderator
1539999449
Hero Member
*
Offline Offline

Posts: 1539999449

View Profile Personal Message (Offline)

Ignore
1539999449
Reply with quote  #2

1539999449
Report to moderator
jackg
Copper Member
Legendary
*
Offline Offline

Activity: 1162
Merit: 1111


View Profile
April 28, 2018, 04:13:56 PM
Merited by bones261 (1), Jet Cash (1)
 #2

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
Legendary
*
Offline Offline

Activity: 1162
Merit: 1152


View Profile
April 28, 2018, 04:30:19 PM
 #3

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
Copper Member
Legendary
*
Offline Offline

Activity: 1162
Merit: 1111


View Profile
April 28, 2018, 04:36:12 PM
 #4

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
Copper Member
Member
**
Offline Offline

Activity: 204
Merit: 17


View Profile
April 28, 2018, 06:40:18 PM
 #5

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
Copper Member
Legendary
*
Offline Offline

Activity: 1162
Merit: 1111


View Profile
April 28, 2018, 06:59:23 PM
 #6

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
Hero Member
*****
Offline Offline

Activity: 714
Merit: 600



View Profile WWW
April 29, 2018, 04:07:21 PM
 #7

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
Sr. Member
****
Offline Offline

Activity: 490
Merit: 312


View Profile
April 30, 2018, 01:06:36 PM
 #8

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
Copper Member
Legendary
*
Offline Offline

Activity: 1162
Merit: 1111


View Profile
April 30, 2018, 05:42:00 PM
 #9

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
Hero Member
*****
Offline Offline

Activity: 714
Merit: 600



View Profile WWW
May 01, 2018, 08:05:08 PM
 #10

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
Copper Member
Legendary
*
Offline Offline

Activity: 1162
Merit: 1111


View Profile
May 01, 2018, 10:31:48 PM
 #11

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

Pages: [1]
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!