О протоколе честного покера

Тема в разделе "Разработка", создана пользователем tabi2018, 9 июн 2018.

  1. tabi2018

    tabi2018 Постоянный пользователь Проверенный

    Аннотация
    На недавней конференции по финансовой криптографии, проходившей в марте этого года, был представлен доклад о протоколе честного покера по названием "Kaleidoscope: An Efficient Poker Protocol with Payment Distribution and Penalty Enforcement". Ниже приводится сокращенный перевод первого раздела доклада.


    Калейдоскоп: эффективный протокол покера с распределенными платежами и штрафными санкциями

    1. Введение.
    Началу разработки протокола дистанционной игры в покер положили авторы
    знаменитой и популярной криптосистемы асимметричного шифрования RSA в своей статье "Mental poker". Эта проблема связана с очень интересными вопросами организации распределенных игр. Например, надежное тасование карт в распределенной игре требует от каждого удаленного игрока участия в данной процедуре; в противном случае безопасность не может быть гарантирована для участников.

    Ментальный покер, криптография и рынок азартных игр. Изучение ментального покера и других карточных игр послужили серьезным стимулом для исследований в области криптографии. Начиная с 80-х годов прошлого века исходная работа Шамира и др. вдохновляла последователей к изучению ментального покера, например [11]. Первые протоколы для ментального покера имели множество ограничений и только в следующее десятилетие были улучшены благодаря многочисленным работам большого числа авторов, например [3,33,32,9,25,29,28].

    Объем рынка покера. Начиная со времени «покера бума» 2000-х годов, онлайн-покер стал финансово крепкой отраслью, что нашло отражение в престижных экономических изданиях [15]. В значительной мере рост интереса к онлайн азартным играм связан с появлением онлайн-казино. Например, в отчете Financial Times [1] отмечается, что глобальный рынок международных азартных онлайн-игр оценивается в 40 млрд долларов, в том числе и крупнейшее казино с 22 млн пользователями и доходом в 2,5 млрд дол. Поскольку в США были внесены законодательные ограничения на азартные онлайн игры, то американские игроки стали использовать сайты, расположенные в других странах. После ухода американцев с прибыльного рынка британские фирмы успешно заполнили образовавшийся ваккум.

    О доверии к казино. Нынешняя модель азартных онлайн-игр основана на доверии и честности казино, которое единолично отвечает за генерацию случайных чисел, используемых для тасования карт. Напротив, игра в реальном мире покера не требует почти никакого доверия между игроками или между игроками и третьими лицами, такими как казино. В текущей модели само казино или злоумышленник, работающий в казино, может сильно повлиять на исход игры, манипулируя случайностью, используемой для тасования карт или утечкой дополнительной информации игрокам. И такие случаи уже произошли (подробнее см. Раздел «Целостность и справедливость» [30]). Такое положение вещей представляет собой явный недостаток онлайн-покера в сравнении с визуально контактирующими игроками за игровым столом. Для преодоления этой проблемы разработаны криптографические методы ментального покера, позволяющие надежно играть в онлайн-покер без услуг доверенных казино.

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

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

    Требования к протоколу покера. Современное состояние разработок протокола покера неудовлетворительно. Перечислим базовые требования к протоколу покера для его успешного развертывания в реальном мире, когда на карту ставятся очень большие деньги:
    1. Эффективность при высокой производительности, сравнимой с обычным "ручным" протоколом покера.
    2. Безопасность: должно быть реализовано формальное доказательство безопасности на основе имитационного моделирования.
    3. Штрафы: игроки не должны прерывать начатую партию или в противном случае наказываются штрафами.
    4. Вознаграждения: требтся найти мханизм безопасного распределение вознаграждения игрокам
    Хотя в работах [20] и [7] достигнут фундаментальный прогресс в разработке пунктов (3) и (4) базовых требований к протокол, тем не менее ни одно из их решений не отвечает одновременно условиям (1) и (2).

    1.1 Вклад команды разработчиков протокола "Калейдоскоп". Протокол «Калейдоскоп», назван честь одноименного покерного фильма шестидесятых годов прошлого века [18]. Главная цель команды разработчиков состояла в созданиие покерного протокола, который удовлетворял бы всем четырем вышеперечисленным требованиям. В процессе работы над протоколом были сформулированы дополнительно две важные задачи:
    1. Протокол должен быть эффективным с доказуемой гарантией безопасности. Такого важного требования не было в предыдущих покерных протоколах.
    2. Необходимо сократить объем данных хранимых в блокчейне, который является сильно ограниченным ресурсом.

    В целом наш вклад в создание честного покерного протокола состоят в следующем:
    1. Дано первое полноценное определение безопасности для покера на основе имитационного моделирования.
    2. Разработан первый покерный протокол, который доказуемо реализует определение безопасности (раздел 3).
    3. Достигнуто примерно 10-кратное улучшение вычислительных и коммуникационных характеристик при работе с картами по сравнению с предыдущими работами.
    4. Существенно уменьшен объем хранимых в блокчейне данных по механизму принудительного исполнения штрафов и выплате вознаграждений (раздел 4).
    Наша цель состоит в обеспечении надежной гарантии безопасности игры на всех ее стадиях. В связи с этим потребовалось определить функциональность покера, которая включает в себя исполнение правил игры, штрафование за отказ от начатой партии и гарантии в получении вознаграждений. Насколько нам известно, такое моделирование всей покерной игры как идеальной функциональности проведено впервые.

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

    Согласно протоколу игральные карты рассматриваются как тексты, зашифрованные по известному криптоалгоритму El Gamal [3] с важными отличиями в генерации ключей и тасовании карт. В частности, значительно улучшена эффективность процедуры тасования карт благодаря применению последних достижений в криптографической схеме "доказательства с нулевым разграшением (см. прим. перев. *)".

    1.2 Обзор и содержание нашего протокола. Далее представлен более подробный обзор нашего протокола.

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

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

    Общий обзор протокола:
    1. Первоначально участники игры фиксируют в сессионном контракте сумму денежного залога и величину денежных ставок.
    2. Игроки первоначально запускают выполнение покерного протокола вне блокчейна. Поскольку отказ любого участника игровой сессии может привести к сбою в работе протокола покера, то игрокам необходимо записать состояние игры в сессионном контракте для разрешения в будущем возможных спорных проблем. Все записи игроков закрепляются электронной подписью. При формировании игровой контрольной точки участники игры должны самостоятельно подписать статусные переменные, однозначно задающие состояниес игры в фиксированный момент времени.
    3. В конце игры окончательные суммы выплат подписываются всеми игроками. Участники игры обращаются к блокчейну для честного распределения наличности, которое выполняется в соответствии с сессионным контрактом.
    4. При возникновении спорной ситуация игрок может запросить обращение к сессионному контракту. Чтобы не получать штрафы каждый игрок записывает в сессионном контракте свои свидетельства, с помощью которых может быть проверен статус игровой партии.
    Депозит d, который каждый из n участников безопасно закрыл в контракте, должен быть достаточным для выплаты суммы компенсации q для всех других сторон, то есть d ≥ q (n - 1). Очевидно, что денежная компенсация q должна быть связана с максимально возможной величиной ставки m каждого игрока; в противном случае у коррумпированных сторон будет стимул прервать ход игры, если они заметят, что игра закончится плохо для них.

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