1
$\begingroup$

"Skull" or "Skull and Roses" is a table top game. The rules can be found here.

I was thinking of how I could play this game P2P. At first it seemed easy: Each time I had to place a card face down I would make a choice hash it, send it to my opponent, and then when it needed to be checked you could give out your answer and it could be verified by hashing it. The problem is that without all players revealing all of their card at the end of a round, there is no way to verify that someone didn't put down more than one skull, or put down more roses than they had. This problem seems like a simplified version of mental poker to me, so I am hoping someone with more knowledge on the subject would know how to play this game without a trusted third party.

In case the link provided goes dead here is a synopsis of the rules: Each player gets a hand of 4 cards: 3 rose cards and 1 skull card. At the start of each hand each player places one card from their hand face down. Next players take turn place another card from their hand face down on top of their previously placed cards. When it is your turn instead of placing another card face down you are also allowed to "challenge". To challenge you announce a number of less than or equal to the number of cards placed down. You now enter a new phase of the game where players take turns naming larger and larger numbers until someone either decides to "pass" (not naming a larger number), or someone names a number equal to the number of face down cards. When the "challenge" phase is over the last player to call a number has to flip over that many cards. If the player flips over a skull he has to discard a rose card for the rest of the game, however if he does not flip over a skull card, he gets a point. Everyone now collects the cards they played face down, and a new round begins. First player to two points wins.

$\endgroup$
  • $\begingroup$ Could you please include a description of the game in the question? Both to make it self-contained as well as to protect against link rot. $\endgroup$ – Maeher Jan 21 at 8:54
  • $\begingroup$ Do you want to prevent the players from making an illegal move or is it sufficient that they are caught after the round is over? $\endgroup$ – Maeher Jan 21 at 9:03
  • $\begingroup$ Preventing them from making an illegal move is preferable, but I think it's sufficient if they are caught when the round is over. $\endgroup$ – Julian Jan 21 at 9:15
  • $\begingroup$ I'm not sure if I'm missing something. But basically you need every player to post their intent secretly as a hash proof before each round, and after the round there's a revealing phase where every hand needs to be checked against the initial proof. Is that right? $\endgroup$ – Veilkrand Jan 24 at 8:54
1
+50
$\begingroup$

Assuming that it's sufficient to catch a cheating player after the round is over, this seems trivial to implement using only bit commitments.

Let $\mathsf{Com}$ be a bit commitment scheme.

At the beginning of each round:

Each player $P_i$ chooses a random index $j\gets \{1,2,3,4\}$, computes $$ c_i^k := \begin{cases}\mathsf{Com}(0)&\text{if } k\neq j\\ \mathsf{Com}(1)&\text{if } k= j\end{cases} $$ for $k\in \{1,2,3,4\}$, and publishes $(c_i^1,c_i^2,c_i^3,c_i^4)$. These commitments represent their randomly shuffled cards.

**Placing cards:* Whenever a player wants to play a card, they simply broadcast an index $k$. This signifies that they placed the card represented by $c_i^k$.

Flipping cards: When the player who won the challenge wants to flip a card, the player who played it simply opens the corresponding commitment.

Once the game has concluded, everyone opens all of their commitments and it can be checked that they indeed committed to exactly one $1$ and three $0$s.

If you want to catch cheating players immediately, you can add a non-interactive zero knowledge proof to the first message, pricing that the commitments are to exactly one $1$ bit and three $0$s.

The hiding property of the commitment scheme should prevent anyone from knowing any (but their own) placed cards, while binding prevents players from opening cards they did not play.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Where can I find more information on writing an implementation of this kind of "non-interactive zero knowledge proof" $\endgroup$ – Julian Jan 24 at 3:54
  • $\begingroup$ I'm also curious what type of bit commitment scheme you would recommend for a practical implementation. $\endgroup$ – Julian Jan 29 at 2:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.