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

нормально отношусь. более того, часто использую. и вообще много доисторических эфективных протоколов просто диктуют подобное поведение: NAT+tcp/ip (а о udp вообще страшно подумать), ISO 8583,...

Когда вероятность настолько низка - черт с ней, а то надо начинать беспокоиться о сбоях памяти от космических лучей.

Впрочем, Bzr не использует модную концепцию content addressability.

> И общий вопрос -- как вы относитесь к коду, который by design имеет ненулевую вероятность некорректного поведения?

Плохо. А свой код я вообще ненавижу, мне он кажется просто говном. Когда я параноидально (именно параноидально =)) пытаюсь свести вероятность некорректного поведения к минимуму, то рождаются такие монструозные и уродски выглядящие конструкции, что хочется сделать rm -fr project и написать всё с нуля. А если пытаюсь написать с нуля, то получается то же самое...

*уныние*

Вопрос в тему: а вас беспокоит возможность некорректного поведения программы из-за возможного целочисленного переполнения int, даже если произойти это может только если программа будет работать без остановки десяток лет? А вот у меня такая шиза имеется...

> И общий вопрос -- как вы относитесь к коду, который by design имеет ненулевую вероятность некорректного поведения?

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

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

Ничего страшного, мне больше интересно что будет если у двух коммитов контрольная сумма совпадёт.

> который by design имеет ненулевую вероятность некорректного поведения?

Лишь бы это документировано было.

>А вот у меня такая шиза имеется...

Я думал, я один такой патологический перфекционист.

>беспокоит возможность некорректного поведения программы из-за возможного целочисленного переполнения int

Совершенно не беспокоит. Просто надо использовать правильные ЯП, в которых такую возможность просто так не создать.

>что будет

скорее всего, оба файла будут иметь одинаковое содержимое (наверное, содержимое того файла, который был закоммичен первым).

>И общий вопрос -- как вы относитесь к коду, который by design имеет ненулевую вероятность некорректного поведения?

Если это необходимое зло (т.е., не получится избавиться от этой вероятности), то нормально. ИМХО, в распределенной системе вроде git по-другому не получится решить проблему назначения идентификаторов.

Ну, и конечно, все зависит от того, на каком пространстве событий задана эта вероятность. Одно дело — если эта вещь не зависит от действий пользователей (космические лучи), то на нее можно заранее спокойно закрыть глаза. Гораздо серьезнее, когда вероятностное пространство состоит возможных действий пользователя.

> Просто надо использовать правильные ЯП

Использовать эти самые "правильные" ЯП возможно далеко не всегда. Можете себе представить видео декодер на lisp'е? Я нет.

> ИМХО, в распределенной системе вроде git по-другому не получится решить проблему назначения идентификаторов.

Получится.

> Можете себе представить видео декодер на lisp'е?

Можно. Люди для Haskell'а биндинги к SSE делают, ничего так, на тестах шустро крутится. Правда, тут гамак и конечная цель несколько несоотносятся - но можно (к примеру, чтобы не учить и не использовать тошнотворные языки...)

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

эти языки зачастую и полезные возможности использовать мешают.

>> Можете себе представить видео декодер на lisp'е?

> Можно. Люди для Haskell'а биндинги к SSE делают, ничего так, на тестах шустро крутится.

Только это уже не программа на Хаскеле, ага?

> Можете себе представить видео декодер на lisp'е? Я нет.

Esli lisp zapuskaetsya pryamo na zheleze, to pochemu net?

> Esli lisp zapuskaetsya pryamo na zheleze, to pochemu net?

Нет, всё-таки сложно представить более вакуумносферическую штуку, чем видео-декодер написанный на лиспе и работающий на железной лисп-машине...

> ИМХО, в распределенной системе вроде git по-другому не получится решить проблему назначения идентификаторов.

ну, например, UUID+hash, или даже один UUID принципиально отличается от одного hash. Потому что в UUID (который time- и MAC- based) приняты понятные меры для предотвращения коллизии. А один hash это просто упование на авось.

> UUID (который time- и MAC- based) приняты понятные меры для предотвращения коллизии. А один hash это просто упование на авось.

Вообще-то в SHA этих мер принято еще больше :)

> Только это уже не программа на Хаскеле, ага?

Почему же? В Хаскеле монады кошерны - какая тогда разница, какую абстракцию реального мира они представляют?

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

Сферический псевдокод в вакууме.

int foo()
{
 if(someVariable < INT_MAX)
   return ++someVariable;
 else
   throw new PolniyPizdetsException("this program can not run so long without restart");
}

> Вообще-то в SHA этих мер принято еще больше :)

там приняты криптографические меры.

В UUID приняты административные меры.

Поэтому, при условии соблюдения административных правил, с UUID birthday paradox не работает. А с любым хэшем работает.

> с UUID birthday paradox не работает. А с любым хэшем работает.

Мм... это как? Имеется в виду, что хэш от одинаковых данных одинаков?

> В Хаскеле монады кошерны - какая тогда разница, какую абстракцию реального мира они представляют?

Ааааа, держите меня трое!!!!!111111 %)

Разница простая - упаковав в трижды кошерную монаду Си-код, ты внес в программу всю номенклатуру проблем Си, включая молчаливое переполнение int.

> И общий вопрос -- как вы относитесь к коду, который by design имеет ненулевую вероятность некорректного поведения?

Отношусь нормально к легко поправимым допущениям, что в 99,9999999% случаев будет работать безошибочно. Пример: подразумевание того, что в /tmp всегда найдётся место для пары мегабайт.

Чувствую себя весьма неуютно, когда приходится применять недоказанный алгоритм или приближённый алгоритм без подсчёта погрешности. Пример: уточнение по Рунге, адаптивные алгоритмы интегрирования.

> Разница простая - упаковав в трижды кошерную монаду Си-код, ты внес в программу всю номенклатуру проблем Си, включая молчаливое переполнение int.

Какой набор слов, а смысла нет! Объясни свою мнимую связь между SSE, языком C, и "молчаливым переполнением int"

> Какой набор слов, а смысла нет!

Дислектик?

> Объясни свою мнимую связь между SSE, языком C, и "молчаливым переполнением int"

Вообще-то связал Хаскел и SSE ты, а не я.

> Можете себе представить видео декодер на lisp'е? Я нет.

http://augustss.blogspot.com/2009/01/llvm-arithmetic-so-we-want-to-compute-x....

- интересный пример. Правда, не Лисп, а Хаскелл - но всё же.

> языком C

ты явно к нему неровно дышишь. Я про него ничего не писал в посте про Haskell и SSE.

>> языком C

>ты явно к нему неровно дышишь. Я про него ничего не писал в посте про Haskell и SSE.

Подставь вместо "Си" "ассемблер" - ничего же не изменится.

> Мм... это как? Имеется в виду, что хэш от одинаковых данных одинаков?

нет.

Это основной пойнт UUID -- он борется с birthday paradox административными методами.

Хороший хэш ведет себя как случайная функция (но, безусловно на одном файле она постоянна, не в этом дело). Поэтому если мы будем брать разные файлы, то для хэшей работает BP -- то есть чтобы добиться повторения нужно взять не 2^160 разных файлов, а порядка 2^80.

С правильным UUID такое не работает, он борется с BP административными методами. Если взять крайний случай, то всем выдает UUID центральный комитет, тогда понятно что никакого BP не будет, потому что центральный комитет будет выдавать последовательные числа. В time- и MAC- based UUID центрального комитета конечно нет, но маки выдаются центральным комитетом, а во вторых время служит центральным комитетом, плюс в рамках одной машины комитетом служит ОС.

> birthday paradox

Да что такое этот парадокс применительно к хэшам?

> Если взять крайний случай, то всем выдает UUID центральный комитет

Ну этот случай можно вообще не рассматривать.

> В time- и MAC- based UUID центрального комитета конечно нет, но маки выдаются центральным комитетом, а во вторых время служит центральным комитетом

MAC-и сталкиваются (хотя карты с одинаковыми MAC стараются поставлять в разные регионы), времени в распределенной системе верить нельзя... ну и интересно было бы увидеть анализ вероятности столкновения UUID, конечно. Подозреваю, что он будет сильно выше 2^80.

> Да что такое этот парадокс применительно к хэшам?

http://en.wikipedia.org/wiki/Birthday_attack

Используй меркуриал - там вероятность такой проблемы намного меньше.

>не 2^160 разных файлов, а порядка 2^80.

Да, для проекта, содержащего 1180591620717411302826 патчей это довольно серьёзная проблема.

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

солнце погаснет быстрее чем такое у кого-то случится, даже если git будет использовать каждый человек планеты каждый день

> И общий вопрос -- как вы относитесь к коду, который by design имеет ненулевую вероятность некорректного поведения?

Параноя не должна мешать жить. Надо реально смотреть на вещи, не надо придумывать себе виртуальных проблем. Хотя если эту вероятность некорректнорго поведения можно легко свести к 0, то желательно сделать это, но если из-за этого проект станет неповоротливым параноидальным монстром - то нахер надо! "Упрощай на столько, на сколько можешь, но не больше".

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

>солнце погаснет быстрее чем такое у кого-то случится

Тогда солнце уже много раз погасло %)

>солнце погаснет быстрее чем такое у кого-то случится

это действительно, если мы тянем хэши по одному из множества всех значений хэша

Вероятность посчитать не сложно.

http://ru.wikipedia.org/wiki/%D0%9F%D0%B0%D1%80%D0%B0%D0%B4%D0%BE%D0%BA%D1%81...

Если взять 6 миллиардов коммитов (одного проекта) в день в течении десяти тысяч лет, то вероятность что хеши двух состояний совпадут составляет приблизительно 1.1E-16.

(кто может, уточните эти цифры; мог ошибиться в формулах)

>Тогда солнце уже много раз погасло %)

SHA1, конечно, broken (по словам великого и ужасного), но мне кажется, что ты сам не состоянии найти коллизии.

Кстати, надо убедить Линуса перевести git на sha256, хотя бы.

> SHA1, конечно, broken (по словам великого и ужасного), но мне кажется, что ты сам не состоянии найти коллизии.

Ы. Ты математег, ага? "Искать коллизии", надо же %)

Чтобы получить коллизию, о которой говорил dilmah, надо всего лишь закоммитить в два разных клона одно репозитория одинаковый файл. И _всё_. Ты считаешь, что на всей планете никто и никогда не провел, например, импорт vendor branch'a таким образом (по ошибке, конечно)? ;) И против таких коллизий git устойчив by design.

>всего лишь закоммитить в два разных клона одно репозитория одинаковый файл

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

Ключевое слово "разных".

P.S. Нужно учесть, что гиту ЕМНИП важнее общий хеш, а не хеш конкретного файла, но суть идеи топикпастера, думаю, понятна.

> В том сообщении, на которое ты отвечал были следующие буковки: "что будет если в git закоммиттить 2 разных файла с одинаковым хэшем?"

> Ключевое слово "разных".

Ну это и будут "два разных файла". У них будет одинаковое содержимое, да. Если настоящий вопрос был "как git реагирует на коллизию, которая возможна с вероятностью 2^80", то Линус отвечал на этот вопрос. Где-то в архивах это есть.

P.S. SHA-1 не взломан, IIRC. Так что я лично не волновался бы на тему коллизий (если бы пользовался git).

>Ну это и будут "два разных файла". У них будет одинаковое содержимое, да.

А что у них будет разное? :) Давай всё-таки исходить из разумного допущения, что если у файлов одинаковые названия и одинаковое содержимое, то они одинаковые.

Если же речь про два одинаковых файла под разными именами, то это git'у по барабану, и случается такое сплошь и рядом.

>с вероятностью 2^80

Откуда взялась цифра 2^80?

>Линус отвечал на этот вопрос

По-моему, об этом-то и спрашивал dilmah. Если дашь ссылку, буду очень признателен.

> И общий вопрос -- как вы относитесь к коду, который by design имеет ненулевую вероятность некорректного поведения?

Миллионы вселенных родятся и умрут раньше, чем в GIT-е встретится коллизия с хеш-суммой на одном файле.

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

>> Ну это и будут "два разных файла". У них будет одинаковое содержимое, да.

> А что у них будет разное? :)

Имена.

> Давай всё-таки исходить из разумного допущения, что если у файлов одинаковые названия и одинаковое содержимое, то они одинаковые.

А если хотя бы одно из двух - разное, то и файлы разные. Я из этого и исхожу.

> Откуда взялась цифра 2^80?

http://www.linux.org.ru/jump-message.jsp?msgid=3577340&cid=3577914

>>Линус отвечал на этот вопрос

>По-моему, об этом-то и спрашивал dilmah. Если дашь ссылку, буду очень признателен.

Это было еще в старом git@. По-быстрому нашлось http://www.gelato.unsw.edu.au/archives/git/0504/0676.html, но там нет высказывания Линуса. Еще прикольная нить: http://www.gelato.unsw.edu.au/archives/git/0504/1793.html

> Миллионы вселенных родятся и умрут раньше, чем в GIT-е встретится коллизия с хеш-суммой на одном файле.

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

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

> во первых, вероятность коллизии гораздо выше.

Во вторых - время жизни вселенной много меньше, чем считалось до недавних пор. Есть основания полагать, что в скором времени (в ближайшие несколько миллиардов лет) скорость убегания дальних галактик начнет расти экспоненциально, и наша вселенная помрет еще до того, как погаснет наше солнце. Она и до этого росла по экспоненте, но ввиду того, что эта экспонента была очень пологой (в отрицательной части своей), этого не было заметно.

> P.S. SHA-1 не взломан, IIRC. Так что я лично не волновался бы на тему коллизий (если бы пользовался git).

Привет всем.

А как же:

http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
http://www.rsa.com/rsalabs/node.asp?id=2927

> http://www.schneier.com/blog/archives/2005/02/sha1_broken.html

"They can find collisions in SHA-1 in 2^69 calculations, about 2,000 times faster than brute force. Right now, that is just on the far edge of feasibility with current technology" - это по-твоему взлом?

> http://www.rsa.com/rsalabs/node.asp?id=2927

"Although it is clear that the approach is viable, the improved message modification calculations have not been confirmed by experts. As with the work of [WYY], this work estimates the difficulty of an attack, rather than producing an actual collision. No actual collision for SHA-1 has been exhibited to date. However 2^63 is within reach of a distributed computing effort" - это считается взломом?

Так что либо давай более новые данные, либо не взломан :D