что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?

:-) Собственно, там самое интересное это то, что это уже не брутфорс. А для хэш-функции, с точки зрения математики, это уже broken. А практически пока ещё рано паниковать, конечно :-).

> это уже не брутфорс

вспомнился вежливый лось из анекдота

> А для хэш-функции, с точки зрения математики, это уже broken

А, с точки зрения математики... тогда конечно. То, что о нахождении реальной коллизии за 4 года так и не сообщалось, с точки зрения математики несущественно, очевидно же.

Так что у меня вопрос: как вы относитесь к тому, что крыши домов не укрпеляют против попадания метеоритов?

Линус и ко впаривают некорректный код. Они используют неинъективную функцию там, где требуется инъективная.

> Они используют неинъективную функцию там, где требуется инъективная.

А то, что все контрольные суммы не 100% ошибок ловят - тебя не волнует? :)

:-) Ну, так-то оно конечно так. Но когда-то и про MD5 думали, что, мол, долго ещё до реально-найденных коллизий. А вон оно как вышло. Мощности компьютеров растут очень быстро. Придёт время... :-)
А вот насчёт метеоритов я более-менее спокоен (насчёт sha-1, кстати, тоже :-) ). По крайней мере, сущестуют наблюдатели небесных тел, которые мне сообщат когда надо из дому бежать :-). Не думаю, что сколько-нибудь разрушительный метеорит проскользнёт незамеченным :-). А бабки потом с государства будем трясти, как потерпевшие от природных катаклизмов. Хм... интересно, а страховка от этого существует :-)?

> Но когда-то и про MD5 думали, что, мол, долго ещё до реально-найденных коллизий.

IIRC, коллизий MD5 "in the wild" найдено не было - все были подобраны специально. И в любом случае, SHA1 малость посильнее будет :)

Ну а для тех, кто любит неинъективные функции, разработанные специальными комитатами, есть bzr.

> По крайней мере, сущестуют наблюдатели небесных тел, которые мне сообщат когда надо из дому бежать :-). Не думаю, что сколько-нибудь разрушительный метеорит проскользнёт незамеченным :-)

Ненене, они следят только за крупными метеоритами, от которых всемкапец. А мелкие, которые пробивают крыши (есть случаи, ага) - это ответственность строителей :D

> А то, что все контрольные суммы не 100% ошибок ловят - тебя не волнует? :)

не волнует

>> А то, что все контрольные суммы не 100% ошибок ловят - тебя не волнует? :)

> не волнует

Необнаруживаемые баги в железе - не волнуют, а в софте - волнуют? "Где логика?" (c) анекдот

%)

Впрочем, здравое design decision (его слямзили у Monotone и OpenCM, кстати) не отменяет факта, что Git угребищен :)

А что не в этом мире не угрёбищно :-)?

> Ну а для тех, кто любит неинъективные функции, разработанные специальными комитатами, есть bzr.

я выбираю RCS, пока остановился на darcs. Видно, что разумный человек делает, не то что чухонский гопник Линус и его гойманда.

>> Ну а для тех, кто любит неинъективные функции, разработанные специальными комитатами, есть bzr.

> я выбираю RCS, пока остановился на darcs

Дело твое, но даже хаскеляторы ушли с него на Git. DARCS слишком революционная система, неизвестно, доведут ли ее до ума вообще. IIRC, в DARCS 2.0 используется такое же хранилище, как в Git, со всеми его проблемами :D

ИМХО, если не вестись на пиар, то из DVCS нужно выбирать либо Mercurial, либо Bzr. Но Bzr тормоз.

Дык все что связано с хэшами - подвержено ненулевой вероятности коллизии. Теория множеств мать ее итить.

Ну случится это один раз - удалят этот файл из репозитория и заново зальют. И хэш не повторится. Кроме того файлы с тем же хэшем с очень маленькой вероятностью будут представлять из себя что-то осмысленное.

Вообще ненулевая вероятность ошибки - это нормально для реального мира но не для всех задач. Для хранения версии исходников в распределенной системе версий - потянет. Мало того эта штука катит и для репликации в некоторых важных базах данных, хранящих в т.ч. информацию о ваших фининасах и здоровье... бугога :D

> Ну случится это один раз - удалят этот файл из репозитория и заново зальют. И хэш не повторится.

O_o с чего бы ему не повториться?

> O_o с чего бы ему не повториться?

дык табы на пробелы заменят. Все зло от табов.

> Ну случится это один раз - удалят этот файл

так, в том то и дело, что у меня большое подозрение, что если это случится, то это не будет выявлено сразу, а повлечет коррупцию данных и таинственные глюки.

Я был бы более спокоен, если бы они использовали CRC32, но зато протестировали код, обрабатывающий коллизии.

> Дык все что связано с хэшами - подвержено ненулевой вероятности коллизии. Теория множеств мать ее итить.

я не вижу необходимости здесь опираться только на один хэш (кроме мнимой красоты и упрощения кода).

>> O_o с чего бы ему не повториться?

> дык табы на пробелы заменят.

Дык это ж другой файл будет.

> Все зло от табов.

Клевета :D

> O_o с чего бы ему не повториться?

Ну например в комментарий допишут одну строчку где будет сказано /* a collision happened */ и тогда оно не повторится.

> а повлечет коррупцию данных и таинственные глюки.

да почему?

> Дык это ж другой файл будет.

О чем и речь.

> > > а повлечет коррупцию данных и таинственные глюки.

> да почему?

а где доказательства того, что кто-то продумывал код на случай коллизии? Я ж говорю, луше бы CRC32 использовали, чтобы протестировать этот код.

Ты ж не забывай, что хэши используют вовсе не только для иденитификации файлов, а вообще всех объектов в системе -- патчсетов например.

> а где доказательства того, что кто-то продумывал код на случай коллизии?

А это невозможно. В систему заложено предположение "коллизий не будет".

> хэши используют вовсе не только для иденитификации файлов, а вообще всех объектов в системе -- патчсетов например.

Патчсеты - это не в Git, а в Darcs. Но тоже по хэшам, да.

>а где доказательства того, что кто-то продумывал код на случай
>коллизии?

Да никакой код и не нужен. Нужен процесс. Вот ты купил машину, поездил на ней какое-то время и надо масло менять. Вот ты уже и попал в ситуацию когда система не в состоянии решить внутренние проблемы - появился процесс. Так же точно и с коллизиями - возникает необходимость, осуществляется maintenance.

>Ты ж не забывай, что хэши используют вовсе не только для
>иденитификации файлов, а вообще всех объектов в системе -- патчсетов
>например.

И что? Даже если у патчесета и у файла один и тот же хэш - это все равно разные сущности. Системе на это полюбому пофиг.


>Я ж говорю, луше бы CRC32 использовали, чтобы протестировать этот
>код.

Дык какая разница? Протестировать систему можно используя простую хэш функцию x -> 1. Будет со 100% выдавать коллизию.

Посмотри как в базах данных живут с ключами в виде GUID-ов, для обеспечения уникальности ключа. Бывают коллизии, но их фиксят ручками и для той частоты с которой коллизии случаются - решение вполне оправдано.

> Посмотри как в базах данных живут с ключами в виде GUID-ов, для обеспечения уникальности ключа.

Это совсем другая вещь.

> Бывают коллизии, но их фиксят ручками

Ну и как разрешать конфликты в Git? То есть можно на каждом fetch сравнивать объекты с совпадающими хэшами, но системой будет невозможно пользоваться :D

> Посмотри как в базах данных живут с ключами в виде GUID-ов, для обеспечения уникальности ключа.

UUID, генерируемый правильно, по RFC, с использованием MAC, time и счетчиков кардинально отличается от хэшей.

> Ну и как разрешать конфликты в Git? То есть можно на каждом fetch сравнивать объекты с совпадающими хэшами, но системой будет невозможно пользоваться :D

не верю, что это нерешаемая проблема. Нужно просто поддерживать дополнительные ID, а не довольствоваться "внутренним" ID, который определяется как хэш содержимого.

> UUID, генерируемый правильно, по RFC, с использованием MAC, time и счетчиков кардинально отличается от хэшей.

И чем же? Вероятность коллизии есть и для него.

>> Ну и как разрешать конфликты в Git? То есть можно на каждом fetch сравнивать объекты с совпадающими хэшами, но системой будет невозможно пользоваться :D

> не верю, что это нерешаемая проблема

Решается она с такими накладными расходами, что придется отказаться от схемы.

Чем? Есть большее множество, которое отображается в меньшее множество. Будут коллизии. Хоть ты как заисголяйся над алгоритмом.

> Нужно просто поддерживать дополнительные ID, а не довольствоваться
> "внутренним" ID, который определяется как хэш содержимого.

А когда дополнительный ID совпадет с другим дополнительным ID, тогда придумаем третий ID? И так до тех пор пока множества не станут равны? :).

> И чем же? Вероятность коллизии есть и для него.

обсуждалось же выше.. birthday paradox убивается.

Компаниям выдают неперескающиеся диапазоны маков, если конкретная компания реюзает маки, то это ее проблема, не нужно покупать их карты.

Время нужно майнтейнить, есть ntp.

Плюс там используются дополнительные счетчики.

Если UUID все-таки совпадают, то это распиздяйство, а не кирпич с неба на голову упал.

> А когда дополнительный ID совпадет с другим дополнительным ID, тогда придумаем третий ID? И так до тех пор пока множества не станут равны? :)

нет конечно.

> Компаниям выдают неперескающиеся диапазоны маков, если конкретная компания реюзает маки, то это ее проблема, не нужно покупать их карты.

Никогда не знаешь наперед.

> Время нужно майнтейнить, есть ntp.

Ага, в глобальном масштабе.

> Если UUID все-таки совпадают, то это распиздяйство

А обнаруживать это как?

А как?

> Компаниям выдают неперескающиеся диапазоны маков

Дык два разных mac-а выдадут одинаковый хэш. Точно так же как два разных файла могут выдать одинаковый хэш.

> Дык два разных mac-а выдадут одинаковый хэш.

в uuid мак, время и счетчик не хэшируются, они включаются in plain.

То есть на одном маке можно легко создать два одинаковых хэша?

> То есть на одном маке можно легко создать два одинаковых хэша?

что-то я тебя совсем не понимаю..

Если я тебя правильно понял, ты сказал что наличие уникального mac адреса позволяет получить неповторяющийся хэш. Я тебе привел пример того как хэш может быть повторен.

я говорил, что DRCS можно реализовать, не опираясь на предположение о том, что коллизии в хэшах можно игнорировать.

Нам нужны ID для объектов, они же не обязаны быть только хэшем содержимого. Мы можем добавить к ним UUID. Мы можем добавить к ним имена. Наконец, нам в любом случае нужно от каждого пользователя DRCS иметь криптографическую подпись, а стало быть его identity. Все это мы можем включить в Id.

Разумеется, в этом случае в репозитории должно быть отдельное хранилище для Id.

Я не понимаю о чем спор.

Это не решает задачу обеспечения уникальности идентификатора ресурса.