Synchronizacja danych Drzewa Merkle Fałszywie Pozytywne

Question

Drzewa Merkle (aka hash drzew) są używane do synchronizacji danych zarówno w "Cassandra" & "Dynamo".

jak w przypadku innych funkcji mieszającej, istnieje prawdopodobieństwo, że poszczególne dane mogą mieć taką samą wartość skrótu:

istnieje X i Y, gdy [! Y = X], ale [mieszania (x) = mieszania (y)]

Wraz z narastaniem "dużych danych" w NOSQL, prawdopodobieństwo pojawienia się takich danych staje się większe.

Oznacza to, że w miarę jak zbiory danych stają się większe, prawie pewne jest, że różne węzły w drzewie Merkle przyniosą ten sam hash rodziców.

Przy takiej okazji, kiedy dwie różne maszyny w gromadzie przemierzają swoje drzewa merkle, otrzymają fałszywy alarm, że ich dane są spójne. Jeśli do tej gałęzi drzewa nie zostaną zapisane żadne dane, urządzenia pozostaną niezsynchronizowane na zawsze.

Jak to się dzieje?

Answer 1

Większość systemów tego nie obsługuje. Czemu? Ponieważ prawdopodobieństwo posiadania dwóch różnych wejść o tej samej wartości mieszania jest bardzo, bardzo niskie. Z dobrą funkcją haszującą (której myślę, że używasz), powinno to zbliżyć się do 1/2^{hash-bitów}. A ponieważ większość skrótów dla tych celów ma co najmniej 128 bitów, otrzymasz prawdopodobieństwo 1/2^128 takiej kolizji. Jest to około 2,9387359e-39 (0. {38 zeroes} 29387359).

Używanie skrótu 160-bitowego (którego większość z tych systemów używa, haszy SHA-1), jest wystarczająco dobre, gdy masz w bazie danych tyle obiektów, ile jest ziaren piasku na świecie. Że nadal istnieje mniejsze prawdopodobieństwo niż 1/2, że dojdzie do kolizji. Nie martwiłbym się więc przypadkiem, w którym dochodzi do kolizji. Prawdopodobieństwo, że tak się dzieje, jest naprawdę zbyt niskie.