Как обрабатывать повторяющиеся хэши
AFAIK git просто доверяет хэшу sha1 быть уникальным, поэтому он не обрабатывает случаи, когда два хэша столкнутся (я знаю, это маловероятно).
Из любопытства, какой был бы хороший способ справиться с подобными конфликтами? Я думаю о том, чтобы проверить размер файла, если он совпадает.
Есть ли кто-нибудь, способный сделать некоторую математику, чтобы определить, насколько я уменьшу вероятность конфликта?
Или я слишком много думаю об этом, и SHA1 достаточно хорош на практике?
3 ответов:
SHA1 достаточно хорош на практике. При слегка оптимистичных предположениях вероятность столкновения двух различных объектов составляет примерно один из двух возможных. 2160. Из-за" проблемы дня рождения " шанс растет удивительно быстро с большим количеством объектов, но требуется очень много роста, чтобы приблизиться к вашим шансам быть пораженным молнией: около 1 из 700 000 в любой данный год, или 1 из 3000 в вашей жизни (та же ссылка). (Да, я знаю, что эти цифры не имеют значения. похоже, они работают вместе. Я просто использую их номера.)
В конечном счете, однако, git, вероятно, должен переключиться на вариант SHA с большим числом битов. Это разобьет все те скрипты, которые предполагают, что SHA-1 всегда ровно 40 символов. :- )
В какой-то момент я написал и вычислил следующее (Не знаю, была ли моя математика правильной или нет)
Обратите внимание, что Git помещает 4 различных типа объектов в одно адресное пространство - коммиты, большие двоичные объекты, деревья, теги. Git уже проверяет, что хэшируемое содержимое идентично, поэтому проверка размеров файлов ничего не делает.Парадокс дня рождения-для 365 ведер, у вас есть 50% шанс столкновения в 23, и 99,9% шанс на 70, и 99,9999 на 100, но вы этого не сделаете. хит 100% до 366 (високосные годы исключены). Нормальный человек мог бы догадаться, что вы не будете на 50% примерно до 180.
Для пространства SHA addresss 160 бит у вас есть 50% шанс столкновение, когда вы добавили 1.42*10^24 объекта. Git не справляется столкновений, а вместо этого предполагает, что они никогда не произойдут.
Существует ряд методов для работы с хэш-конфликтами. Они всегда используются, когда ваше пространство вывода хэша мало (например, 16 бит или меньше). Алгоритмы множественного хэша или ведра-самые популярные из тех, что я видел на практике.
Есть ли кто-нибудь, способный сделать некоторую математику, чтобы определить, насколько уменьшу ли я вероятность конфликта?
Или я слишком много думаю об этом, и SHA1 достаточно хорош на практике?
Ты слишком много думаешь. Невозможно объяснить, почему, не объяснив, насколько маловероятно, что это произойдет, и шансы таковы ... у нас даже нет гиперболы о том, насколько это маловероятно.
Вот, попробуйте: на пятикарточном стаде ваши шансы получить флеш-рояль равны 1 в 649739.
Итак, вы играете в пятикарточный стад, и кто-то за столом получает флеш-рояль.Затем в следующей раздаче он получает еще один флеш-рояль.
Затем в следующей раздаче он получает еще один флеш-рояль.
Затем в следующей раздаче он получает еще один флеш-рояль.
Тогда ему придется бить тебя по камню-ножницы-бумага четыре раза подряд.
Вот еще один. Скажем, проект ядра Linux генерирует миллион файлов в секунду. Если бы он это делал ... , каждую секунду, начиная с большого взрыва, ему все еще не хватало 2^80 файлов, необходимых для достижения 50-50 шансов.
Или: вы идете в магазин на углу и покупаете один, только один, лотерейный билет на Мега-Миллионы. В субботу ты узнаешь, что выиграл миллион долларов!. Черт возьми, если тебе так повезет, тебе, наверное, стоит купить лотерейный билет. Поэтому вы идете в магазин на углу и покупаете один, всего один, лотерейный билет на Мега-Миллионы. Приходите в среду, и вы узнаете, что выиграли еще один миллион долларов! Черт возьми, если тебе так повезет, тебе, наверное, стоит купить лотерейный билет. Поэтому вы идете в магазин на углу и покупаете один, всего один, лотерейный билет на Мега-Миллионы. В субботу ты узнаешь, что выиграл еще один миллион долларов!
Как бы вы ни надеялись, сколько бы вы ни мечтали о том, что Вам повезет в любом из этих сценариев, это примерно то, о чем вы должны беспокоиться.
Comments