«Это случайно» — утверждение, а не факт. Чтобы выбор был честным, должны выполняться два условия: источник чисел не должен быть предсказуемым, и каждый вариант должен быть равновероятным.
Оба условия реализуемы, оба часто выполняются неверно, и отказывают они независимо. У инструмента может быть превосходный источник случайности и предвзятое отображение — или идеально равномерное отображение, питаемое предсказуемыми числами.
Откуда берётся случайность
Настоящая случайность берётся из физических процессов, не определяемых предшествующим состоянием:
- Радиоактивный распад — момент распада атома предсказать нельзя
- Тепловой шум — случайные колебания напряжения в резисторе
- Атмосферный шум — фоновые помехи от грозовой активности
- Квантовое измерение — исходы, которые действительно неопределённы
Компьютер не может наблюдать их напрямую. Он считывает показания аппаратного генератора — /dev/urandom и его аналогов, — который сам инициализируется физическими процессами. Это истинный генератор случайных чисел.
Гораздо более частый случай — генератор псевдослучайных чисел: детерминированный алгоритм, порождающий последовательность, которая лишь выглядит случайной.
next = (previous × multiplier + increment) mod modulusКлючевое свойство очевидно. Если вы знаете алгоритм и зерно, вы можете вычислить каждое значение, которое когда-либо выдаст последовательность. Не приблизительно — точно. Именно поэтому Math.random(), который используют большинство сайтов, непригоден для всего, что имеет значение: его результат определяется внутренним состоянием, и восстановление этого состояния по наблюдаемым значениям делает каждый будущий результат предсказуемым.
Промежуточный вариант, который решает вопрос
Современные платформы не используют «сырую» аппаратную энтропию при каждом вызове. Они применяют криптографически стойкий ГПСЧ — детерминированный, но инициализируемый аппаратной энтропией и устроенный так, что наблюдение за результатами не раскрывает состояние.
| Аппаратный TRNG | CSPRNG | Обычный ГПСЧ | |
|---|---|---|---|
| Основан на физической энтропии | Да | Да | Нет |
| Детерминирован при известном состоянии | Нет | Да | Да |
| Результат раскрывает состояние | Нет | Нет | Да |
| Подходит для розыгрыша призов | Да | Да | Нет |
CSPRNG детерминирован ровно в том смысле, в каком детерминировано любое используемое вами ПО. Приемлемым его делает то, что его состояние нельзя восстановить по уже выданным значениям.
Браузеры предоставляют это через crypto.getRandomValues(). Именно этот источник используют розыгрыши здесь.
Равномерность — отдельная проблема
Хорошего источника недостаточно. Отображение случайного числа в выбор всё ещё может быть предвзятым, и именно эту ошибку допускает большинство инструментов.
Наивный подход — масштабирование случайного числа с плавающей точкой от 0 до 1 на диапазон — смещает результат к началу. При 40 именах некоторые случайные значения выходят за границу последней корзины, и если их обрезать, а не отбросить, первое имя выпадает чуть чаще последнего.
Смещение настолько мало, что его никто не замечает, — именно поэтому оно сохраняется в большинстве реализаций.
Правильный подход — выборка с отбраковкой: тяните значение, и если оно попадает в неполную последнюю корзину, отбросьте его и тяните снова. Распределение становится строго равномерным, так что у каждой записи шанс 1/N — в том числе при выборе из 40 имён, где реализация с масштабированием даёт первому имени чуть более высокую вероятность.
Та же техника используется в здешнем генераторе коротких идентификаторов, где доля принятых значений — 252/256, а итоговое смещение — около двух частей на десять миллионов. Достаточно мало, чтобы не иметь значения, и достаточно мало, чтобы небрежная реализация осталась незамеченной, — именно поэтому это стоит измерять.
Три человеческие ошибки, которые не вина инструмента
Ошибка игрока. После пяти «орлов» подряд кажется, что пора «решке». Каждый бросок независим. Монета не помнит о несправедливости, и правильная вероятность после пяти «орлов» по-прежнему ровно 1/6 на сторону.
Иллюзия кластеризации. Серии в случайных данных кажутся закономерными, потому что вы их ищете. Три одинаковых результата подряд случаются гораздо чаще, чем подсказывает интуиция. А по-настоящему случайные данные на коротких отрезках выглядят неровными — последовательность, которая кажется идеально ровной, скорее подделана, чем настоящая.
Парадокс дней рождения. В группе из 23 человек двое, скорее всего, родились в один день. Это арифметика, а не психология, но она показывает, почему люди так плохо оценивают случайность: отдельные вероятности крошечны, но они перемножаются.
Общее здесь то, что одно наблюдение ничего не доказывает — ни в ту, ни в другую сторону. Розыгрыш, показавшийся странным, так же неинформативен, как и тот, что выглядел аккуратным.
Две ошибки, которые важнее всего на практике
Разобрав механизм, стоит назвать то, что на самом деле идёт не так, когда выбор оспаривают, — и ни одна из этих ошибок не касается источника.
Оператор переписал результат. Повторный розыгрыш, ручная правка, пропуск отсутствующего имени во время выбора. Идеальный генератор и изменённый итог — это всё равно изменённый итог, и это видно любому, кто наблюдал.
Список был не тем, что опубликован. Добавление имени или тихое исключение одного из них меняет выбор независимо от алгоритма.
Обе — сбои процесса, и обе предотвращает записанный розыгрыш. Поэтому запись со списком участников в кадре ценнее любого технического свойства: она исключает и то и другое.
Где такая строгость оправданна
Для выбора обеда всё это не важно. Любой генератор выдаст приемлемый обед.
Это становится критичным, когда есть ставка, репутация или юридический аспект:
- Розыгрыши призов и конкурсы. Проверяемый результат — сама суть
- Распределение сотрудников или обязанностей. Люди будут изучать процесс
- Научная и клиническая рандомизация. Стандарт в этой области — задокументированная, с зерном, воспроизводимая случайность
- Регуляторные и аудиторские контексты. Задокументированная случайность часто требование, а не пожелание
Требования во всех этих случаях одни и те же, и они коротки: список фиксирован и опубликован, веса опубликованы, если они есть, источник не предсказуем, а результат записан с видимым списком.
Как проверить это самому
Вы не можете провести аудит CSPRNG во вкладке браузера, но можете рассуждать о механизме, и этого достаточно.
Спросите, что за источник. Если ответ — «случайная функция», уточните, не тот ли это предсказуемый вариант. crypto.getRandomValues() — конкретный, проверяемый ответ.
Спросите, как достигается равномерность. Если в ответе масштабирование числа на диапазон и ни слова о выборке с отбраковкой, отображение, вероятно, предвзято. Немного, но измеримо.
Спросите, что мог изменить оператор. Если ничего — результат защитим. Если имя можно пропустить или розыгрыш перезапустить — нет, независимо от источника.
Страница честности подробнее описывает реализацию на этом сайте. Её стоит прочитать один раз, если вы выбираете инструмент для решения, которое будут оспаривать.