Dealing a card on ethereum

writeup.org

Problem

Alice and Bob wants to deal one card to each other in a trustless way.

Data

An encoding of the deck

52 integers are fixed in the contract that represent 52 cards in the deck. Call this uint[52] deck

N

A large number.

Secrets for Alice and Bob

Pair of secret numbers K and L are generated in the front-end such that GCD(K, phi(N)) = 1 and L.K = 1 (mod N)

Protocol

Note: All arithmetic from now are modulo N.

Commit_Alice

Alice sends the numbers deck[0]**K_Alice, ..., deck[51]**K_Alice in a random order and stores it in uint[52] cards

Commit_Bob

Bob picks two indices from cards, call it, alice_index and bob_index

Play_Bob

Bob sends cards[bob_index]**K_Bob, call it bob_card

Play_Alice

Alice sends bob_card**L_Alice, call it bob_card

Reveal_Alice

Alice reveals keys K_Alice and L_Alice

Reveal_Bob

Bob reveals keys K_Bob and L_Bob

Verify

1. Check if cards[alice_index]**L_Alice is in deck.
2. Check if bob_card**L_Bob is in deck.
3. Optionally check if cards[0]**L_Alice, ... cards[52]**L_Alice is same as deck.

Sample contract

// SPDX-License-Identifier: GPL v3
pragma solidity >= 0.7.0;
pragma experimental ABIEncoderV2;

enum State {
	  Commit_Alice,
	  Commit_Bob,
	  Play_Bob,
	  Play_Alice,
	  Reveal_Alice,
	  Reveal_Bob,
	  Done
}

struct Secret{
	  uint K;
	  uint L;
}

struct Instance {
	  address alice;
	  address bob;
	  uint[52] cards;
	  uint8 alice_index;
	  uint8 bob_index;
	  uint bob_card;
	  State state;
	  Secret alice_secret;
	  Secret bob_secret;
}

contract Game {

	  // The encoding of 2♠, ..., A♠, 2♥, ..., A♥, 2♦, ..., A♦, 2♣, ..., A♣
	  uint[52] deck;
	  /* TODO Fix value of N */
	  uint constant N = type(uint).max;

	  mapping (uint => Instance) data;
	  uint index = 0;

	  constructor() {
		  /* TODO store an encoding of deck */
	  }

	  function commit_alice(uint[52] memory cards) public returns (uint _index) {
		  Instance memory instance;
		  instance.alice = msg.sender;
		  instance.cards = cards;
		  instance.state = State.Commit_Alice;
		  _index = index;

		  data[index] = instance;
		  ++index;
	  }

	  function commit_bob(uint _index, uint8 alice_index, uint8 bob_index) public returns (uint) {
		  /* TODO verify state */

		  data[_index].state = State.Commit_Bob;
		  data[_index].bob = msg.sender;
		  data[_index].alice_index = alice_index;
		  data[_index].bob_index = bob_index;

		  return index;
	  }

	  function play_bob(uint _index, uint card) public {
		  /* TODO verify state and sender */

		  data[_index].state = State.Play_Bob;
		  data[_index].bob_card = card;
	  }

	  function play_alice(uint _index, uint card) public {
		  /* TODO verify state and sender */

		  data[_index].state = State.Play_Alice;
		  data[_index].bob_card = card;
	  }

	  function reveal_alice(uint _index, Secret memory alice_secret) public {
		  /* TODO verify state and sender  */

		  data[_index].alice_secret = alice_secret;
	  }

	  function reveal_bob(uint _index, Secret memory bob_secret) public {
		  /* TODO verify state and sender */

		  data[_index].bob_secret = bob_secret;
	  }

	  function verify(uint _index) public returns (bool) {
		  /* TODO Compute correctness */
		  data[_index].state = State.Done;
	  }
}

References

1. https://people.csail.mit.edu/rivest/pubs/SRA81.pdf
2. https://www.youtube.com/watch?v=mthPiiCS24A