Перетасовка колоды

Коммутативное шифрование:

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

Протокол:

Алиса и Боб выбирают протокол шифрования со следующими функциями.

1. E _K (X) — это X , зашифрованный ключом K
2. D _K [ E _K (X) ] = X для всех K и X
3. Е _К [ Е _J (X) ] = Е _J [ Е _К (Х) ]
   • т.е. E(X) коммутативно
4. Для заданных X и E _K (X) вычислительно невозможно вывести K
5. Даны X и Y , J и K такие, что E _J (X) = E _K (Y) не могут быть найдены
   • т.е. E(x) устойчив к столкновениям

Теперь, когда у Алисы и Боба есть схема шифрования:

1. Боб берет пятьдесят две карты ( «2C», «3C»,..., «AS» ) и шифрует каждую с помощью ключа B.
2. Боб перемешивает зашифрованные карты в случайном порядке и отправляет колоду Алисе.
   • Алиса не видит карты, так как не знает B
3. Алиса выбирает пять карт и отправляет их обратно Бобу.
   • Это рука Боба. Боб может видеть эти карты, так как он знает B
4. Алиса отправляет Бобу еще пять карточек, но сначала шифрует их с помощью ключа А.
   • Каждая карта теперь зашифрована как EA [ EB _{( X} ) ] , что эквивалентно EB [ EA _{( X} ) ] по свойству № 4.
5. Боб расшифровывает эти карты и отправляет их обратно
   • Боб не может видеть карты, так как он не знает А. Алиса, однако, может их видеть, и это ее рука.

Аналогичным образом можно взять больше карт. После игры Алиса и Боб раскрывают A и B , чтобы убедиться, что ни один из игроков не обманул.

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

Использование в контрактах:

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

Поскольку исходный код контрактов Ethereum может быть проверен, это должно быть так же просто, как использование ГСЧ для случайного выбора карт из колоды. Любой, кто хочет убедиться, что колода правильно перемешана, может проверить исходный код контракта.

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

Использование случайности по запросу

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

contract Deck {
   uint8[52] deck;

   function getRandomNumber() returns (uint) {
       ...;
   }

   function shuffle() {
      uint8[52] memory unshuffled;

      for (uint8 i=0; i < 52; i++) {
          unshuffled[i] = i;
      }

      uint cardIndex;

      for (i=0; i < 52; i++) {
          cardIndex = getRandomNumber() % (52 - i);
          deck[i] = unshuffled[cardIndex];
          unshuffled[cardIndex] = unshuffled[52 - i - 1]
      }
   }
}

Этот контракт представляет каждую из 52 карт как целое число от 0 до 51 включительно. Вызов shuffleфункции заполнит deckпеременную хранилища колодой из 52 карт в случайном порядке.

Реагирование на случайный ввод.

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

contract Deck {
   uint8[52] deck;

   function shuffle(bytes randomBytes) {
      if (randomBytes.length < 52) throw;

      uint8[52] memory unshuffled;

      for (uint8 i=0; i < 52; i++) {
          unshuffled[i] = i;
      }

      uint8 cardIndex;

      for (i=0; i < 52; i++) {
          cardIndex = uint8(randomBytes[i]) % (52 - i);
          deck[i] = unshuffled[cardIndex];
          unshuffled[cardIndex] = unshuffled[52 - i - 1];
      }
   }
}

Эта версия контракта требует включения не менее 52 байт случайности в вызов shuffle.

Если вы хотите, чтобы карты не повторялись, то это довольно сложная задача. Более простая проблема заключается в том, что нам все равно, если одна и та же карта сдается несколько раз (например, у вас туз пик, а у меня туз пик).

Рассмотрим простую игру с двумя игроками. Каждому игроку раздается по 1 карте, и это нормально, что оба игрока могут получить одну и ту же карту. Это можно представить, как две карты раздаются из двух разных колод. Чтобы реализовать это, мы можем думать о каждой карте как об индексе от 0 до 51 (включительно). Вот как правильно сгенерировать карту игрока 1, чтобы только он знал, что это такое.

1. Игрок 2 генерирует случайное число в диапазоне 0..51, называемое p2_offset. Затем он генерирует случайную строку с именем p2_secret (например, «pcjshjfgn»). Затем он отправляет sha3(p2_offset, p2_secret) в блокчейн.
2. Игрок 1 генерирует случайное число в диапазоне 0..51, называемое p1_offset, и случайную строку p1_secret и отправляет sha3(p1_offset, p1_secret) в блокчейн.
3. Игрок 2 раскрывает p2_offset и p2_secret контракту Ethereum, который проверяет, что sha3 этих значений соответствует тому, что он отправил ранее.
4. Игрок 1 теперь может выяснить, какая у него карта, выполнив (p2_offset + p1_offset) мод 52. Обратите внимание, что игрок 2 не знает, что это за карты, потому что p1_offset ему неизвестен.
5. Игрок 1 может раскрыть свою карту, указав в контракте p1_offset и p1_secret. Опять же, контракт проверит, что sha3 этих значений соответствует тому, что игрок 1 отправил ранее.

Тот же подход можно использовать для создания карты игрока 2.

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