Инструменты разработчика · Генератор UUID
Сколько случайных битов имеет v4 UUID? 122, а не 128
· Как это работает
uuid криптография API-интерфейс браузера
Шесть из 128 bits в случайном UUID фиксированы стандартом, оставляя 122 для случайности. В этом посте показано, как честно оценить вероятность столкновения и почему настоящие столкновения происходят из-за сломанных генераторов, а не из-за математических вычислений.
Вопрос архитектора: получим ли мы когда-нибудь дубликат? — откуда берется беспокойство и почему ответ зависит от генератора
Архитектор спрашивает: если мы будем генерировать 10 миллионов UUID в день в течение десяти лет, получим ли мы когда-нибудь дубликат? Честный ответ: почти наверняка нет, если генератор криптографически безопасен; почти наверняка да, если сломан генератор. Математика RFC 9562 верна: UUID v4 со случайными битами 122 имеет вероятность столкновения примерно n² / 2 в 123-й степени, где n — количество сгенерированных идентификаторов. Для большинства реальных систем эта вероятность незначительна. Загвоздка в том, что эта формула предполагает, что каждый бит действительно случайен. Если в генераторе есть утечка, повторяется или был задан предсказуемо, формула неверна, и дублирование становится неизбежным. 128-битная структура включает четыре бита версии (0100 для v4) и два бита варианта (10 для RFC 9562), которые фиксированы и установлены стандартом.
О каких шести битах идет речь — о четырех битах версии и двух битах вариантов, и почему они устанавливаются, а не случайны.
Остается 122 bits для случайности. Формулировку иногда называют 2 для случайных битов 122, что дает уникальные значения. Используя приближение парадокса дня рождения, вероятность хотя бы одного столкновения среди n случайно сгенерированных значений составляет примерно n² / 2 с точностью до 123-го. Для n = 1 миллионов это (10^6)² / 2^123 = 10^12 / 9. 3 × 10^36, что примерно равно 10^-25. Для n = 10 миллиардов это все еще около 10^-16. Это не «фактически ноль»; это «вы никогда этого не увидите». Приближение дня рождения дает конкретный способ расчета риска: подсчитайте UUID, которые вы планируете сгенерировать, возведите это число в квадрат, разделите на 2 в 123-й степени. Если генератором является crypto.getRandomValues браузера, каждый бит поддерживается энтропией операционной системы. Если это математика.
Приближение дня рождения простыми словами: вероятность хотя бы одного столкновения среди n идентификаторов равна примерно n в квадрате, разделенному на 2 на 123.
Для UUID, созданного неподходящим генератором или генератором повторяющихся состояний, математическая модель не работает, поскольку ее предположение о независимости неверно. Фиксированное тестовое начальное значение, скопированное фикстуру или снимок процесса могут воспроизводить значения, даже если текст все еще содержит полубайт версии-4. Это дефекты реализации, а не свидетельство того, что расчет поля 122 был неправильным. Другой банальный источник — копирование одного и того же буквального идентификатора в несколько приборов и последующее объединение их данных. При исследовании дубликатов сохраняйте генератор, политику заполнения, жизненный цикл процесса и историю импорта. Не переходите от одного повторяющегося значения к утверждению, что независимый вывод CSPRNG исчерпал пространство UUID.
Рабочий пример — включение заявленной скорости генерации и временного интервала в аппроксимацию, с отображением каждого шага, чтобы вы могли заменить свои собственные цифры.
Разветвление процесса без ресинхронизации случайных состояний. Ошибка, при которой вместо crypto.getRandomValues использовалось Math.random. Тестовое приспособление, изготовленное вручную с использованием одного и того же UUID в несколько рядов и случайно использованное в производстве. Старая версия библиотеки UUID, в которой было ограничение диапазона или ошибка состояния. Ни один из этих сценариев не включает в себя математику приближения дня рождения; они связаны с нарушением реализации или эксплуатационными ошибками. Честно рассчитайте риск столкновения для вашей системы: посчитайте скорость генерации UUID (в секунду, в день, в год), спроецируйте ее на время работы системы и подставьте общую сумму в формулу дня рождения. Если ваша система генерирует 100,000 UUID в день в течение пяти лет (всего 182 миллионов), вероятность коллизии равна (1. 82 × 10^8)² / 2^123 ≈ 3. 3 × 10^-22, что незначительно.
Откуда на самом деле берутся дубликаты — семена Math.random, клонированные виртуальные машины, разветвленные процессы с скопированным состоянием и копирование и вставка в фикстуры.
Если вы генерируете 10 миллионов в секунду в течение года (всего 315 триллионов), вероятность равна (3. 15 × 10^14)² / 2^123 ≈ 10^-10, который по-прежнему исчезающе мал. Эти оценки предполагают, что каждый бит независим и случайен. Генератор ToolAcre использует crypto.getRandomValues, что дает вам случайность, поддерживаемую CSPRNG; операция — единственная часть, которой вам нужно доверять. Никогда не полагайтесь на вероятность коллизии как на оправдание пропуска надлежащих проверок авторизации. UUID не является паролем, не токеном доступа и не секретом, даже если это 122 случайные биты. Уникальность – это преимущество; непредсказуемость — это отдельное (и более важное) свойство, которое предотвращает угадывание. Математика дня рождения учитывает уникальность; он не касается времени жизни (должен ли срок действия этого UUID истечь? ), секретности (нужно ли его хешировать перед сохранением?) или авторизации (доказывает ли наличие этого UUID что-либо о вызывающем абоненте?). Генератор ToolAcre предоставляет вам UUID на основе CSPRNG со случайными битами 122, что означает, что математика уникальности верна, а непредсказуемость верна. Все остальное — проверка токена, срок действия, контроль доступа — является обязанностью вашего приложения. Формула вероятности предполагает независимость каждого сгенерированного UUID от предыдущих поколений. Если ваша система генерирует идентификаторы из одного экземпляра CSPRNG, и каждый вызов извлекает новую случайность из ОС, предположение о независимости сохраняется. Если ваша система использует кэшированное состояние CSPRNG или заполненный генератор без повторного заполнения ОС, предположение не работает. Риск коллизии резко возрастает, если источник энтропии исчерпан (происходит в некоторых встроенных системах или виртуальных машинах под нагрузкой) или если случайное состояние никогда не сбрасывается между процессами (разветвление процесса без повторного заполнения CSPRNG).
Чего это не касается — уникальность версий 1 и 7, которая основана на временных метках и последовательности часов, а не только на случайности.
Резервный вариант ToolAcre вызывает crypto.getRandomValues для каждого массива байтов и не сохраняет состояние PRNG уровня приложения. Ответственность за внутреннее устройство платформы остается за браузером и операционной системой. Моделирование столкновений с реальными генераторами показывает разницу между теорией и устаревшей практикой. Генератор, построенный с помощью Math.random, начиная с того же начального числа, будет создавать идентичные последовательности; вы увидите первое столкновение UUID в пределах нескольких сотен или нескольких тысяч сгенерированных значений, а не после значений 2^60 (квадратный корень из 2^122), как предсказывает приближение дня рождения. Генератор, использующий crypto.getRandomValues из энтропии звуковой ОС, будет создавать коллизии только тогда, когда теоретическая вероятность станет неизбежной (около 2^60 UUID), число настолько велико, что вы никогда его не достигнете. Генератор, использующий слабый или повторно используемый источник энтропии (часто встречается в плохо реализованных библиотеках UUID или тестовых средах), будет создавать коллизии где-то посередине.
Вывод: доверяйте математике, проверяйте генератор — генератор ToolAcre использует CSPRNG браузера, и это та часть, которую нельзя подделывать.
Пакетный тест может выявить реализацию, которая возвращает константу или воспроизводит очевидную последовательность, но пройденный образец не может доказать будущую уникальность. Производственные системы по-прежнему должны применять ограничение уникальности везде, где дублирующиеся идентификаторы могут повредить данные. Импорт заслуживает особого внимания, поскольку две допустимые исходные системы уже могут содержать один и тот же литеральный идентификатор, а фикстуры можно копировать в разных средах. Тесты ToolAcre проверяют, что пакет 500 содержит 500 различных значений; это регрессионная проверка для данной реализации, а не статистическая гарантия. Если появляется дубликат, сохраните доказательства и проверьте пути создания, импорта, фиксации и хранения, прежде чем приписывать причину.