[mozesz_mi_kliknac]

Coś na luźny piąteczek dla programistów i nie tylko:

Ile commitów potrzebujesz w repozytorium, zanim możesz zacząć martwić się o kolizje?

Skrót SHA-1 jest ciągiem 40 znaków heksadecymalnych... czyli 4 bity na znak razy 40... 160 bitów. Teraz wiemy, że 10 bitów to w przybliżeniu 1000 (dokładnie 1024), co oznacza, że istnieje 1 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 różnych haszy SHA-1... 1048.

Co to jest odpowiednik? Cóż, Księżyc składa się z około 1047 atomów. Więc jeśli mamy 10 księżyców... i losowo wybierzesz jeden atom na jednym z nich... a następnie pójdziesz dalej i wybierzesz losowy atom na nich ponownie... wtedy prawdopodobieństwo, że wybierzesz ten sam atom dwa razy, jest prawdopodobieństwem, że dwa dane commit'y git'a będą miały ten sam hash SHA-1.

Rozwijając to, możemy zadać pytanie...

Ile commitów potrzebujesz w repozytorium, zanim zaczniesz się martwić o kolizje?

To odnosi się do tak zwanych "ataków urodzinowych", które z kolei odnoszą się do "Paradoksu urodzinowego" lub "Problemu urodzinowego", który mówi, że kiedy wybierasz losowo z danego zbioru, potrzebujesz zaskakująco mało wyborów, zanim stanie się bardziej prawdopodobne, że wybrałeś coś dwa razy. Ale "zaskakująco mało" jest tutaj bardzo względnym terminem.

Wikipedia ma tabelę prawdopodobieństwa kolizji Paradoksu Urodzinowego. Nie ma tam wpisu dla 40 znakowego hasha. Ale interpolacja wpisów dla 32 i 48 znaków daje nam zakres 5*1022 commitów git z prawdopodobieństwem 0,1% kolizji. To jest pięćdziesiąt tysięcy miliardów miliardów różnych commitów, lub pięćdziesiąt Zettacommits, zanim osiągniesz nawet 0,1% szansy, że masz kolizję.

Suma bajtowa samych hashów dla tych commitów byłaby większa niż wszystkie dane generowane na Ziemi przez rok, co oznacza, że musiałbyś wypuszczać kod szybciej niż YouTube wypuszcza filmy. Powodzenia z tym :D

Chodzi o to, że o ile ktoś nie powoduje kolizji celowo, prawdopodobieństwo, że jedna z nich zdarzy się losowo jest tak oszałamiająco małe, że możesz zignorować ten problem.

#programowanie #programista15k #ciekawostki #technologia

[balrog84]

@mozesz_mi_kliknac: A czasami ludzie pytają co te koparki bitcoinowe tam liczą i na co ta energia idzie, czy jest jakiś pożytek, w sumie można powiedzieć, że szukają kolizji w SHA-256.

[zibizz1]

@mozesz_mi_kliknac: mi na razie tylko raz zdarzyła się kolizja na 10 znakach w jednym repo

[SkorpionX]

Księżyc składa się z około 1047 atomów

@mozesz_mi_kliknac co? Unikatowych? Nie ma tyłu w Tablicy Mendelejewa. A jeśli w sumie z 1047 to jest dość mały...

[mozesz_mi_kliknac]

@balrog84: ale niekompletnych :) formalnie to nie są kolizje, tylko hashe spełniające pewne zasady - w tym przypadku ileś pierwszych znaków to mają być same zera

[balrog84]

@mozesz_mi_kliknac: Wiem, chodziło mi raczej o sytuację, w której dwie koparki dorzucając różne 'nonce' wygenerują ten sam hash. Tylko w sumie mogę się mylić, bo raczej blok z transakcjami może być różny. A poza tym to jest w ogóle abstrakcja, bo takiej kolizji ludzkość nie znalazłaby choćby liczyła do końca Wszechświata.

Albo inaczej, taka kolizja mogłaby być wyłapana, przez wystąpienie 2x tego samego hasha w łańcuchu bloków.