Могут ли противные агенты подбрасывать монеты?

9

Я думал об одноранговых играх, рассматривая простую игру с подбрасыванием монет.

Вы открываете свою версию P2PCoinFlipping Beta 2.3, и она отображает список серверов имен игроков. После выбора ближайшего сервера появляется табло из самых счастливых игроков. Вы выбираете игрока с самым высоким рейтингом, и игра начинается. С тех пор, как вы начали битву, противник выбирает сторону монеты, головы, и вам назначают хвосты. Появляется симпатичная маленькая графика, изображающая падающую монету, которая в итоге приземляется на головы Жаль, ты проиграл.

Но откуда вы знаете, что результат справедлив?

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

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

random peer-to-peer AnnanFay
источник
Хотя не отвечая на вопрос, именно поэтому многопользовательский режим на сервере хорош - пусть сервер будет арбитром. Интересной идеей было бы полагаться на какую-то стороннюю службу в качестве флиппера. Можно ли, например, использовать онлайн-генератор GUID (например, guidgenerator.com ) в качестве основы для системы?
Тим Холт

Ответы:

6

Эта процедура сделает работу:

  1. каждый из двух пиров генерирует случайное число.
  2. каждый пир создает соленый хеш своего номера и отправляет его другому пиру.
  3. любой узел отклоняет запрос, если он получил тот же хеш, который отправил.
  4. как только оба узла подтверждают получение хэшей друг друга, каждый затем отправляет другому свое действительное случайное число.
  5. каждый узел проверяет, что хеш, отправленный другим, на самом деле является хешем случайного числа. отклонить обмен.

  6. результат броска монеты - XOR младшего значащего бита каждого числа, то есть

    (a & 1) ^ (b & 1)

Альтернативное решение:

  1. Каждый из двух пиров решает, кто должен идти первым. Давайте назовем их А и Б, просто чтобы быть оригинальными.
  2. Узел A генерирует свое случайное число, создает из него соленый хеш и отправляет хэш узлу B.
  3. B генерирует свое случайное число и отправляет его в A.
  4. A отправляет свое случайное число в B.
  5. B проверяет, что соленый хеш является хешем числа, которое он получил.
  6. результат броска монеты - это XOR младшего значащего бита каждого числа, как указано выше.

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

Майкл Слэйд
источник
1
Этот протокол, как описано, уязвим для атаки повторного воспроизведения, когда один одноранговый узел просто повторяет сообщения другого однорангового узла, чтобы результат был равен 0. Однако для предотвращения этой атаки можно внести несколько простых изменений.
Ильмари Каронен
Эта версия должна быть в порядке.
Майкл Слэйд
Как это останавливает пира, который просто выбирает число, а не генерирует его случайным образом?
Kylotan
@Kylotan: Это не так, но если хотя бы один из пиров выбирает случайно, результат будет случайным.
Ильмари Каронен
2
Одному перу нечего постоянно выигрывать, даже не выбрав 0, потому что тогда это дает другому пру преимущество. Окончательный результат зависит в равной степени от числа участников.
Майкл Слэйд
2

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

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

StarCraft II является хорошим примером. Это игра, в которой разведка имеет решающее значение, и знание того, что делает враг, может дать феноменальное преимущество, и призы в 5 или более фигур регулярно зависят от результатов. , , и все же оба компьютера хранят все игровое состояние в любое время! Это просто написать программу, которая позволит вам наблюдать за противником и получать от него огромную поддержку.

Оказывается, никто из серьезных конкурентов не использует эти программы. Это слишком легко обнаружить («Эй, Джим, как ты всегда узнаешь, что я строю, в тот момент, когда я его строю?») И просто не стоит проблем.

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

ZorbaTHut
источник