Источник случайности, к которому каждый может получить независимый, удобный и надежный доступ?

Существует ли источник случайности, к которому любой человек в мире может получить независимый, удобный и надежный доступ? Например, 10-й десятичный знак температуры в Мехико достаточно случайный.Но Бобу неудобно получать независимый доступ, и в любом случае его нельзя надежно измерить.

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

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

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

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

Observable Entropy автоматически собирает случайные данные из общедоступных источников каждые пять минут, сохраняя и хешируя содержимое этих полученных данных. Хэш каждого файла источника данных затем комбинируется и детерминистически хэшируется, в результате чего получается окончательный подписанный хэш SHA2-256, представляющий всю собранную энтропию в виде нового поддающегося проверке общедоступного случайного значения.

В настоящее время система собирает данные из следующих общедоступных источников на каждом интервале:

• Заголовок последнего блока биткойн-блокчейна
• Заголовок последнего блока Stellar Blockchain
• Заголовок последнего блока блокчейна Ethereum
• Дранд Случайный маяк
• Маяк случайности NIST
• Hacker News, 10 лучших историй и ссылки на контент
• Временная метка UTC

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

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

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

Кроме того, исторические и последние значения энтропии доступны через общедоступный API (который представляет собой просто прокси-сервер, предназначенный для чтения последних необработанных данных из репозитория Github и не имеющий собственного кеша или хранилища данных). Вот пример вывода из https://entropy.truestamp.com/latest.

Я считаю, что это соответствует каждому из ваших исходных требований:

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

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

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

ОБНОВЛЕНО 25.08.2021 в связи с комментарием @fgrieu:

Спасибо за комментарий @fgrieu. Я постараюсь ответить на ваши вопросы или попросить дать дополнительные разъяснения по потенциальным проблемам, которые, по вашему мнению, могут присутствовать.

(1) инсайдеры могут узнать результат раньше других

В этой реализации нет «инсайдеров», имеющих доступ к конечным данным, которые хэшируются для формирования конечной энтропии. Сбор данных осуществляется с помощью автоматизации, предоставляемой рабочими процессами Github Actions. Собранные данные, как и подписанный маяк Drand, никому не известны до тех пор, пока они не будут собраны (каждый получает новый подписанный случайный маяк). В этом случае единственным инсайдером будет кто-то в Github, у которого есть доступ к их инфраструктуре и который может извлечь содержимое памяти для этого скрипта после того, как он выполнит 500 000 раундов SHA-256. Даже в этом маловероятном сценарии они будут иметь доступ к конечному значению энтропии в течение нескольких миллисекунд после того, как оно будет зафиксировано, и станет общедоступным для всех в репозитории Github. Этот проект, который собирает энтропию каждые пять минут, скорее всего, не чувствителен к такому уровню детализации времени.Могут быть сценарии, в которых ранний (~ 1 с) предварительный просмотр конечного значения был бы достаточно полезен для злоумышленника, чтобы заставить скомпрометировать Github. Однако я не думаю, что это повлияет на варианты использования, для которых предназначен этот проект.

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

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

Я рассмотрел концепцию «инсайдеров» выше. Существуют источники, которые собирает Observable Entropy, которые могут быть известны посторонним, которые хотят попытаться манипулировать окончательным выводом, отправив свои собственные данные атаки, однако это не удастся, поскольку злоумышленник не может знать собранные сценарием значения маяка Drand или временную метку. когда скрипт запускается, оба из которых известны только самому скрипту во время выполнения.

Мне неизвестны какие-либо атаки на несколько раундов SHA2-256, которые позволили бы злоумышленнику предсказать, какие биты вывода будут изменены для достижения желаемого результата.

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

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

(3) распространение результата не является мгновенным, поэтому даже у неинсайдеров может быть зацепка; и сетевые манипуляции могут искусственно вырастить это

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

Потребности оригинального плаката, скорее всего, можно было бы удовлетворить, используя только Маяк случайности NIST или же Дранд Маяк в одиночестве. Но это требует определенной степени доверия к инфраструктуре и ее владельцам для каждого. Это решение распространяет это доверие на несколько общедоступных и поддающихся проверке источников (включая вас самих) со всеми источниками, поддающимися проверке постфактум. Это ключевое отличие от систем, которые, например, наблюдают за природными явлениями, которые не позволяют другим проверять после наблюдения.

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

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

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

Я знаю, вы сказали, что «без синхронизации друг с другом», но другие люди упомянули блокчейн, поэтому я хотел упомянуть классную статью, которую я прочитал:

https://jbonneau.com/doc/BGB17-IEEESB-proof_of_delay_ethereum.pdf

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

Или, по крайней мере, это мое понимание этого.