Здравствуйте.
Знаете, иногда я вижу, что группе людей нужно выбрать некий случайный объект. Например, дежурного, если нет графика, или он запутался (по поводу «правильных» графиков дежурств я бы тоже рассказал). Или же, что меня начало в последнее время раздражать, победителя в каком-либо конкурсе репостов.
Проблема следующая. Организаторы конкурса заявляют, что вот вам последовательность действий, совершите её для участия в конкурсе (например, сделайте репост этой записи), а затем мы такого-то числа выберем случайного победителя из репостнувших. Люди совершают все эти действия, приходит долгожданный день и мы получаем…
Победителя. В лучшем случае мы так же получим видео, как организатор при помощи random.org выбирает номер, а затем находит победителя в какой-нибудь таблице.
Однако здесь кроется одна неувязка. Организаторы обещают честный рандом, но ничего, кроме их честного слова мы не имеем. Они могут сотни раз снимать видео, пока не выпадет нужное число, подменить сайт на локалхосте и так далее. Нет никаких гарантий, что мы получили действительно случайный выбор.
Я же считаю, что системы должны быть спроектированы таким образом, чтобы совершить нечто неправильное в них не было возможно, поэтому…
Итак, мы имеем группу из N участников. Нам требуется получить нечто случайное, чтобы каждый участник был согласен с тем, что этот случайный объект был получен честным образом.
В реальном мире, если выбор бинарен — мы можем попросить кого-нибудь подбросить монетку (впрочем, можно бросать её долго, получить нужное кол-во бит и затем получить что угодно). И мы будем видеть, что он действительно её бросил, что она взлетела, крутилась в воздухе, приземлилась и выпал действительно орёл или решка.
Но в интернете мы не можем видеть, что кто-то действительно что-то куда-то подбрасывает.
Поэтому нам нужен алгоритм, который бы не был централизированным и был бы легко проверяем. Первое, что приходит на ум — попросить у каждого участника любых случайных данных, склеить их с данными полученными от других участников, посчитать от этого какой-нибудь хеш и использовать его как зерно для генератора псевдослучайных чисел.
Но в такой схеме есть два недостатка — время и посредник.
В реальном мире мы могли бы написать случайные данные каждого участника на бумажки, кинуть их в урну, а затем, когда все бросили свои данные — достать их из урны и провести ритуал получения Истинного Рандома. В наших реалиях, к сожалению, у нас нет такой урны.
Мы можем попробовать обменяться своими данными с другими участниками, однако в игру вступает время. Нельзя обменяться данными одновременно. И тогда участник, который должен «бросить» свои данные последним, имея данные всех остальных может подобрать такие данные, которые бы заставили бы рандом стать на его сторону.
Или же можно попросить кого-нибудь «подержать» данные для нас, т.е. найти незаинтересованного посредника. Однако этот вариант не является сильно надёжным, т.к. посредника всё же можно чем-либо заинтересовать.
Второе, что приходит на ум — нужно каким-то образом зашифровать нашу виртуальную урну, чтобы посмотреть её содержимое можно было только после окончания вбрасывания своих листков.
Можно действительно зашифровать, например, так: каждый участник создаёт свою пару публичного и приватного ключа, делится со всеми своим открытым, шифрует свои данные, делится со всеми зашифрованными. Когда раунд обмена зашифрованными данными закончился — все открывают свои закрытые ключи, расшифровывают зашифрованные данные, получают незашифрованные, склеивают, хешируют, кормят ГПСЧ, получают вожделенный рандом.
Но согласитесь, что для выбора одного случайного числа создавать криптоключи — довольно дорого. Поэтому вместо этого можно воспользоваться теми же хешами. В начале все договариваются о некой соли, чтобы никто не мог использовать какой-либо словарь коллизий и открывать совершенно другие данные. Затем хешируют свои данные (должно быть достаточное количество бит, чтобы невозможно было за разумное время просто отбрутфорсить хеши всех участников), делятся, вскрываются.
Т.е. мы получаем децентрализированную трёхраундную (обмен ключами/выбор соли, «закрытое голосование», «вскрываемся») систему выбора некого случайного зерна группой людей. Причём каждый из людей может собственноручно проверить легитимность итогового выбора. И ни участники, ни организатор не могут повлиять на конечный исход.
Применимо ли это на практике в виде чего-либо? Можно ли улучшить схему?
Автор: Rulexec
