Несколько мыслей о git и hash функциях
Знаете что, друзья мои. Задумался я тут о hash tables, коллизиях и прочей подобной фигне.
И вот что я подумал. Читал про git несколько популярных статеек примерно вот такого содержания:
"Assuming we have a good uniform hash function, the chance that any given
pair of different file versions produces an identical hash is 1/2^160.
The chance that there are no collsions is (1-1/2^160)^(2^114). What is
this numerically? Well, (1-a)*(1-b) = 1 - a - b + a*b. When multiplying
probabilities very close to 1 (a and b small), the probability is
a little bit larger than (1-(a+b)).
Likewise, when exponentiating proabilities very close to 1, (1-a)^n is
a bit larger than 1-n*a.
Thus, the probability of no collisions is a bit larger than (1 - 2^114/2^160),
or (1 - 2^-46). The probability of one or more collisions is a bit *less*
than 2^-46, 1 in 70 trillion."
Или говоря русским языком, git использует SHA1, что подразумевает 160 битный hash. А дальше, извините меня, товарищи, но нам начинают какую-то лапшу на уши вешать.
Почему это он, чтобы посчитать вероятность отсутствия коллизий, возводит вероятность отсутствия коллизии в паре в степень числа испытаний? Это что за математика такая?
Вот, к примеру, посмотрим на малых числах. Скажем, хеш у нас двубитный - 0, 1, 2 или 3. Мы делаем выборку из трех значений. Какова вероятность отсутствия коллизий? Ну, разумеется, (3/4) * (2/4) = 3/8. Три испытания, в первом коллизия исключена, все номера свободны. Во втором один номер занят, вероятность не попасть в него - 3/4. В третьем - два заняты, вероятность не попасть 1/2. Обобщая формулу, получаем, что вероятность отсутствия коллизии - M!/((M-N)!* M^N). Где M - максимальное число для хеша (в случае SHA1 - 2^160), а N - количество испытаний.
p(M,N) = M!/((M-N)!* M^N);
А по его логике получаются смешные вещи. Он рассуждает так. Вероятность того, что будет коллизия между - двумя 1/4. А чтобы посчитать вероятность отсутствия коллизии для трех - надо (1 - 1/4) возвести в куб. Не спрашивайте меня, почему он так рассуждает. Я, как и вы, отказываюсь это понимать. У него, таким образом, получается смешная формула:
p(M,N) = (1 - 1/M)^N
Надо ли говорить, что она не имеет никакого отношения к действительности? То есть, вообще никакого. Дальнейшие его выводы о невозможности коллизии в git можно опустить. В них нет решительно никакого зерна.
А есть у нас вот что. Есть у нас геометрическая прогрессия. Правда с очень небольшим коэфициентом. А вовсе не арифметическая, как нам тут пытаются втюхать. Я сейчас затрудняюсь посчитать такие большие факториалы, как 2^160, но вообще, по хорошему, надо бы посчитать аккуратно. Там несложная рекурсивная формула. В принципе, единственная трудность написать програмку - слишком большие числа. Мне сейчас не досуг.
Похоже, не все так оптимистично с вероятностью коллизий, друзья мои. Совсем не все. Боюсь, что коллизии в git очень даже возможны.
Но каковы git-щики. Вот так по простому промывают нам (и себе) мозги. А мы кушаем. Я ведь случайно начал в формулки вдумываться. Тоже верил на слово.
И главное, если бы это единственная ссылка была, где это рассуждение встречается. Кто-то один когда-то ошибся (ну очень хотелось человеку подтвердить свои надежды, что все безопасно), а другие перепечатывают не вникая.
Может и ошибаюсь, конечно. Но уж больно очевидная ошибка у человека в рассуждениях. Не учел, что с каждым новым испытанием вероятность коллизии растет.
И вот что я подумал. Читал про git несколько популярных статеек примерно вот такого содержания:
"Assuming we have a good uniform hash function, the chance that any given
pair of different file versions produces an identical hash is 1/2^160.
The chance that there are no collsions is (1-1/2^160)^(2^114). What is
this numerically? Well, (1-a)*(1-b) = 1 - a - b + a*b. When multiplying
probabilities very close to 1 (a and b small), the probability is
a little bit larger than (1-(a+b)).
Likewise, when exponentiating proabilities very close to 1, (1-a)^n is
a bit larger than 1-n*a.
Thus, the probability of no collisions is a bit larger than (1 - 2^114/2^160),
or (1 - 2^-46). The probability of one or more collisions is a bit *less*
than 2^-46, 1 in 70 trillion."
Или говоря русским языком, git использует SHA1, что подразумевает 160 битный hash. А дальше, извините меня, товарищи, но нам начинают какую-то лапшу на уши вешать.
Почему это он, чтобы посчитать вероятность отсутствия коллизий, возводит вероятность отсутствия коллизии в паре в степень числа испытаний? Это что за математика такая?
Вот, к примеру, посмотрим на малых числах. Скажем, хеш у нас двубитный - 0, 1, 2 или 3. Мы делаем выборку из трех значений. Какова вероятность отсутствия коллизий? Ну, разумеется, (3/4) * (2/4) = 3/8. Три испытания, в первом коллизия исключена, все номера свободны. Во втором один номер занят, вероятность не попасть в него - 3/4. В третьем - два заняты, вероятность не попасть 1/2. Обобщая формулу, получаем, что вероятность отсутствия коллизии - M!/((M-N)!* M^N). Где M - максимальное число для хеша (в случае SHA1 - 2^160), а N - количество испытаний.
p(M,N) = M!/((M-N)!* M^N);
А по его логике получаются смешные вещи. Он рассуждает так. Вероятность того, что будет коллизия между - двумя 1/4. А чтобы посчитать вероятность отсутствия коллизии для трех - надо (1 - 1/4) возвести в куб. Не спрашивайте меня, почему он так рассуждает. Я, как и вы, отказываюсь это понимать. У него, таким образом, получается смешная формула:
p(M,N) = (1 - 1/M)^N
Надо ли говорить, что она не имеет никакого отношения к действительности? То есть, вообще никакого. Дальнейшие его выводы о невозможности коллизии в git можно опустить. В них нет решительно никакого зерна.
А есть у нас вот что. Есть у нас геометрическая прогрессия. Правда с очень небольшим коэфициентом. А вовсе не арифметическая, как нам тут пытаются втюхать. Я сейчас затрудняюсь посчитать такие большие факториалы, как 2^160, но вообще, по хорошему, надо бы посчитать аккуратно. Там несложная рекурсивная формула. В принципе, единственная трудность написать програмку - слишком большие числа. Мне сейчас не досуг.
Похоже, не все так оптимистично с вероятностью коллизий, друзья мои. Совсем не все. Боюсь, что коллизии в git очень даже возможны.
Но каковы git-щики. Вот так по простому промывают нам (и себе) мозги. А мы кушаем. Я ведь случайно начал в формулки вдумываться. Тоже верил на слово.
И главное, если бы это единственная ссылка была, где это рассуждение встречается. Кто-то один когда-то ошибся (ну очень хотелось человеку подтвердить свои надежды, что все безопасно), а другие перепечатывают не вникая.
Может и ошибаюсь, конечно. Но уж больно очевидная ошибка у человека в рассуждениях. Не учел, что с каждым новым испытанием вероятность коллизии растет.