Обработка столкновений, близких к невозможным, по обязательному значению

Question

Существует множество систем, которые зависят от уникальности определенного значения. Все, что использует GUID, приходит на ум (например, реестр Windows или другие базы данных), но также и вещи, которые создают хэш из объекта, чтобы идентифицировать его, и поэтому этот хэш должен быть уникальным.

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

Другие реализации, однако (по-видимому) зависят от уникальности. Мой пример (вот что заставило меня спросить об этом) - это идентификаторы ревизии Mercurial. entry на Mercurial список рассылки правильно утверждает

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

Но даже самая маленькая вероятность не означает невозможность. Теперь я не хочу объяснять, почему полностью опираться на уникальность (это обсуждалось, например, here). Это очень ясно для меня.

Скорее, я хотел бы знать, (возможно, с помощью примеров из вашей собственной работы):

• Существуют ли какие-либо рекомендации относительно того, охватывающих эти невероятные случаи так или иначе?

• Следует ли их игнорировать, потому что более вероятно, что особенно сильные солнечные ветры приводят к неправильному считыванию жесткого диска?

• Должны ли они, по крайней мере, быть протестированы, если только сбой с сообщением «Я сдаюсь, вы сделали невозможное» для пользователя?

• Или должны ли эти случаи обрабатываться изящно?

Для меня, особенно следующий интересен, хотя они несколько рискованных-Филей:

• Если вы не обрабатывать эти случаи, что вы делаете против инстинктивного чувства, что дон» t слушайте вероятности?

• Если вы справляетесь с ними, как вы оправдываете эту работу (для себя и других), учитывая, что существуют более вероятные случаи, которые вы не обрабатываете, например сверхновости?

Answer 1

• Если обращаться с ними, как вы оправдываете эту работу (для себя и других), учитывая, есть более вероятные случаи, не обрабатывать, как сверхновая звезда?

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

Однако не каждый клиент GUID-кода должен проверять его правильность, особенно в производственном коде. Это то, что должны делать единичные тесты, поэтому компромисс между ценой отсутствия ошибки, которую может испортить ваша фактическая польза, но модульные тесты не проводились, несмотря на то, что вы все время игнорировали ваши библиотеки.

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

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

• Или должны ли эти случаи обрабатываться изящно?

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

Answer 2

Учитывая хороший 128 бит хэш, то, вероятно, сталкивающихся с определенным значением хеш-функции данного случайного вход:

1/2 ** 128, которая приблизительно равна 3 * 10 ** -39.

Вероятность отсутствия столкновений (p) приведенных n образцов может быть вычислена с использованием логики, используемой для объяснения birthday problem.

p = (2 ** 128)!/(2 ** (128 * n) * (2 ** 128 - n)!) 

где ! обозначает факторную функцию. Затем мы можем построить вероятность каких-либо столкновений как с увеличением числа проб:

Probability of a random SHA-1 collision as the number of samples increases. http://img21.imageshack.us/img21/9186/sha1collision.png

Между 10**17 и 10**18 хэшей мы начинаем видеть нетривиальные возможности столкновения с 0,001% до 0,14% и, наконец, 13% с 10**19 хешей. Таким образом, в системе с миллионом миллиардов записей, учитывающих уникальность, вероятно, неразумно (и такие системы мыслимы), но в подавляющем большинстве систем вероятность столкновения настолько мала, что вы можете положиться на уникальность ваших хэшей для всех практических целей.

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