Playing cards with ECDSA and HD wallets

[ertil]

Now, card games are usually played by using centralized websites, where all players trust some server. It seems that things could be done differently, in more decentralized way.

First, each player generate HD wallet master private key. That should remain secret forever and that will be used later to prove ownership of the cards. Next, each player generate master public key. That key is used to determine the order of the cards in player's deck. In this way, it is guaranteed by ECDSA that the player cannot simply put cards in any chosen order. Of course, it is possible to generate master private key many times in advance to get some first cards in selected order, but it will work only in single player games and will be quite limited to few cards. Also, in single player games, simply using private key, public key and address without HD wallet is sufficient.

However, if there are at least two players, then all outcomes should depend on other player's behaviour. Both players can make their moves in some local blockchain. Mining will not be needed here, because cheating attempts are impossible once master addresses of all players are settled. If anyone will cheat, then it will be proven during the game (if someone will pick for example more Aces than are present in any deck) or in the end, where someone will provide non-matching public key. It will be also clearly visible, who and when cheated.

Before making the first move, both players generate their master private keys, master public keys and reveal master addresses, just to make sure that nobody will change its deck during the game. Since then, assuming that all players will keep their private keys secret, there is no way of creating a valid local chain without other player's cooperation.

The trick is: each player will know its public key (so the order of the cards), but the second player will decide, which card should be picked. And because this decision will be based on some address generated by upfront-agreed derivation path, the second player cannot really choose any card, the only possible way is just revealing some child address that was settled upfront by revealing master address for HD wallet.

In short:

master private key = ownership of the deck
master public key = revealed deck
master address = hidden deck
child public key = part of the proof that the second player's next move was ok
child address = base for the second player's next move

Because everything is deterministic, nobody will change any card. In the end, when one of the player wins, both of them should reveal their master public keys. In this way both players can verify that the whole game was honest and that nobody passed some random hashes or modified keys. It will be also trivial to see who and when cheated if there were any such cases. Thoughts?

[1714726791]

1714726791

[1714726791]

1714726791

[nullius]

Thoughts?

How do you map the pseudorandomness of keys to cards?  —Or more precisely:  How does your scheme generate the ordering of cards in a deck?

The ordering of a deck of cards is a permutation.  You have not explained how you permute a single deck of cards, in a way that is agreed between players.  You need to do a Fisher-Yates shuffle, or something similar—but you want to do it based on BIP 32 keys, you want to do it based on keys held by different players, and you must somehow do it without letting any player discover any other player’s cards.

I read your post twice; and I do not see any hint of how to solve this problem.  (There are other issues, but let’s start here.  N.b. that because 52! is not a power of 2, you will need a very big state space to do this securely...)

[odolvlobo]

Look up ECDH. It is a way of combining two private keys to create a shared key without revealing the private keys.

One advantage of using ECDH with the system you are proposing are that all the keys are deterministic and known at the start, so the opponent cannot manipulate their private keys without being detected.

Another advantage is that the actual keys used to determine the outcomes cannot be predicted because they are derived from the private keys of both opponents.

How do you map the pseudorandomness of keys to cards?  —Or more precisely:  How does your scheme generate the ordering of cards in a deck?

52! is a 225 bit number, so 256 bits should be sufficient for generating a random sequence of cards.

I bet a simple shuffle like this will work:

Code:

  x = generate_entropy 256
  cards = [0..51]
  for i in [51..1]
     to = x % (i+1)
     x = x / (i+1)
     swap cards[i], cards[to]

   

[nullius]

Look up ECDH. It is a way of combining two private keys to create a shared key without revealing the private keys.

One advantage of using ECDH with the system you are proposing are that all the keys are deterministic and known at the start, so the opponent cannot manipulate their private keys without being detected.

Another advantage is that the actual keys used to determine the outcomes cannot be predicted because they are derived from the private keys of both opponents.

I know quite well what ECDH is.  I also know about commit-and-reveal schemes using ECDH or similar.  OP didn’t mention ECDH; he spoke of ECDSA.  Moreover, and more importantly, ECDH does not solve the problem.

The players in a multiplayer card game need to agree on a shared card order which is secret to all of them, such that each of them knows only his own cards.  Whereas ECDH lets two parties agree on a secret known to both of them, over an insecure channel; or as you imply, it can commit the players to their keys, such that each player knows only his own key.  How does this help, praytell?

OP seemed to imply some sort of cut-and-choose protocol:

The trick is: each player will know its public key (so the order of the cards), but the second player will decide, which card should be picked.

But I don’t see how that helps, either:  All players must use the same permutation of the deck; it must be an unbiased pseudorandom permutation; but none of the players can know the permutation.

I bet a simple shuffle like this will work:

Code:

  x = generate_entropy 256
  cards = [0..51]
  for i in [51..1]
     to = x % (i+1)
     x = x / (i+1)
     swap cards[i], cards[to]

That is a

Fisher-Yates shuffle

...however, you have implemented it with modulo bias.  It is one of the most common implementation errors of this type; if I had guessed one error that would pop up in this thread, it would have been modulo bias.  Dealing with randomness is hard!

Your to variable must be selected from a uniform random distribution in the range of [0, i].  Your entropy is (I hope) uniformly random in the range of [0, 2²⁵⁶ - 1].  Using the % to go from one range to another introduces a bias; and it’s bad enough if enough money is on the line, someone will probably exploit it in practice.  The floor division that you apply to your remaining entropy will also introduce some additional bias.

If given an input of 256 uniform random bits (still not explained), and a goal of Fisher-Yates shuffling a card deck, I would suggest using the 256 bits of entropy as the input to a KDF, using the KDF to expand the entropy, and then using chunks of the expanded entropy with the algorithm described in my above-linked “modulo bias” post to pick numbers uniformly at random in the ranges of [0, 51], [0, 50], [0, 49], ... [0, 1].

But be wary of how you do this, because...

so 256 bits should be sufficient for generating a random sequence of cards.

Well, it depends how you apply them.  You need for each of the 52! possible card permutations to be equiprobable (or so close to it that any bias is negligible).  If you get this part wrong, then you can run into a sort of a different version of the modulo bias problem...  See what I said about “state space”.  It will not be a problem if you use a KDF as I said.  It may be a problem if you try to design your own ad hoc scheme for turning the random seed you have into the random numbers you need.

52! is a 225 bit number,

Nit:  It is actually a 226-bit number.  2^225.581... has 226 binary digits.

[ertil]

How do you map the pseudorandomness of keys to cards?

All that is needed is just taking 52 public keys, one key per card, then sorting that numbers in ascending order and assigning cards, based on derivation path. So, for example:

Code:

extended private masterkey: tprv8ZgxMBicQKsPefDgWnYApRE8SGtB8Gvjkyt8RgxicXzWTvwFkqKUeQxH6p5o7hJD5hPwVcCjmTPZrBbGjJmfjhsCAzJWV2Dq5gaSjXDvhYf
some/derivation/path/0 = first card   0386d6e8bc789dd73cdb86f782dee6f94a83574271996807e3df455c10426fdf45 bcrt1qdxshjs8affcu2vy8n246hhprylnj3jsy7uv55k
some/derivation/path/1 = second card  0297b618d4f7e9d8983d16a256a4787ec9220d8ceaa00a090fb29a5ba7f835dc86 bcrt1q409ndw5tdj5l2ekl5jg852lw8gk0qmr7tyn77y
some/derivation/path/2 = third card   039bffe6c3f1d0d878d4b1865c71f74c0a3518c755baa3e053d41be4baa772779b bcrt1qe6hgeva7eanyx6dldg8kq5k65tj3w9ut6m2pgy
...
some/derivation/path/51 = last card   03122fba75e1dcef642161d20f986a6e9f25ffe9ea7a449331efe9a3d795b3c4aa bcrt1qv6qqxljscujxdw674ef0vgz8qgwq4fm3snk86t

After sorting:

Code:

some/derivation/path/47               02015c365e23915e8c6924f59c9fcc07cfe18be3c6532d882bcee5ce08f68528c5 bcrt1qc2wlex6p6qa85f2htqydq9gk39yamnme92tuzv
some/derivation/path/25               022f0fa0c1a88825ff7a2646259b3160f340c9d3659835808875154ec0999c4262 bcrt1q097pvjxxz04hlhpq43mfe50ufv3qxdhuyhss5w
some/derivation/path/45               023af7c60fa08d2fe91e65f9d9dbdaa1d6e74c3733bd6606058f4dd47a627f81c0 bcrt1qw70j2zkarzqca9agvr3lazkwxkvfy9ag4arzka
...
some/derivation/path/10               03fdb472ae03469055be518f1f8024a94c7f055bc89849a14886d07a5a5a2491e8 bcrt1q08vtg5lmfhlh5lp0x642p7uwcjcyvrln0jlkty

And then, only the owner of the master public key can know the order of the cards. But still, the player does not know if the first card will be 47 and then 25, and then 45. It is just the order of the cards in its deck, but which card will be picked first? It depends on other player's key and on all previous moves in the whole game so far.

[nullius]

That’s a much clearer explanation, at least of the first part of it:  You are essentially trying to build a cryptographically secure hash table of the integers.  The second part, the use of those values, still seems unclear; but I suggest breaking this down into pieces for analysis.

There is no reason to use public-key cryptography:

• Elliptic curve public keys are not uniform random strings.  That may or may not have an impact here; but it is irrelevant, because...
• It is an unnecessary complication.  Simplicity is better for security analysis.

BIP 32 uses HMAC-SHA512 internally.  Why not simply use that directly, without any point multiplications, with the player committing to a random seed in an ordinary commit-and-reveal scheme?

• Alice picks a seed S_Alice, and commits SHA-256(S_Alice) to Bob; Bob picks a seed S_Bob, and commits SHA-256(S_Bob) to Alice.  (For brevity, I will omit describing Bob’s side of this in the next steps.)  After the game is concluded, Alice and Bob will reveal their respective seeds to each other for retrospective proofs that neither party cheated.  <edit> As I specified it, this would, of course, be vulnerable to length extension such that a party could search for a more favourable seed after committing.  This could be solved by requiring a constant-length seed (say, 256 bits), or by using HMAC with a protocol-specified key, or by using a hash that is not vulnerable to length extension. </edit>
• For each of the integers 0 to n, Alice calculates a hash H_{Alice, n} = HMAC-SHA512(key = S_Alice, data = n), using a protocol-defined encoding of n such as a 64-bit integer in network byte order.
• Alice sorts the list with H_{Alice, n} as the sort key and n as the value, to create a pseudorandom permutation of the integers in range [0, n].

So far, so good?  I hypothesize that this can be reduced to the security of HMAC-SHA512 in the random oracle model; at least, I don’t immediately see any way to attack this without attacking HMAC-SHA512.  (If I am wrong, somebody please point out the flaw...)


Next question:  How is this turned into a hand of cards?

For ease of analysis, assume an oversimplified card game:  Alice and Bob are each dealt 1 card (*).  Each player looks at his or her own card, then chooses an amount to bet; after both players bet, they reveal their cards to each other.  The player with the highest-valued card wins.

It is just the order of the cards in its deck, but which card will be picked first? It depends on other player's key and on all previous moves in the whole game so far.

So, at the point marked * above, exactly what data do Alice and Bob exchange?  (Note that there have been no previous moves.)  You seem to imply that there is another layer of indirection in mapping these randomly sorted lists of integers to card values:  Alice and Bob each produce a permutation; and their permutations are merged interactively, step by step, to form the deck of cards.  Am I on the right track here?

[ertil]

Why not simply use that directly, without any point multiplications, with the player committing to a random seed in an ordinary commit-and-reveal scheme?

Because it would work only if everything will be used outside of coins. But if BTC on-chain coins are involved or even BTC-LN coins, or maybe some other altcoins, then standardness rules apply. And then making some transaction with for example OP_SHA256 will be non-standard. Maybe in testnet, signet or regtest it will be ok, but in real life scenario it should sooner or later be somehow connected with real money, so there is a need of getting the whole game history and turning it into some transaction that will allow the winner to claim the reward in a decentralized way.

But yes, you are right, it could be simpler, and in case of free P2P game (with no coins or other goods involved), we could get rid of addresses and just use SHA-256 of some seed.

How is this turned into a hand of cards?

If you have two players and each of them has 52 cards, it is simple. The same if there are two players and one of them has all black cards and another player has all red cards. It is simple in all cases where players start from the same cards (sorted in different order) and the chances of winning depends more on their skills rather than their luck. But of course if both players use one shared deck of 52 cards, then things are more complicated.

The semi-centralized way is having someone acting as Escrow and holding the cards. Then, we have two players and one Escrow, all cards are unknown to both players. But this way is somewhat centralized, because both parties have to trust Escrow. So, if players want to split the deck to make it unbalanced (where one player could for example get four Aces), then it is definitely possible if they know how their shared deck is splitted, but still the order of the cards will be unknown and decided on-the-fly.

For ease of analysis, assume an oversimplified card game:  Alice and Bob are each dealt 1 card (*).  Each player looks at his or her own card, then chooses an amount to bet; after both players bet, they reveal their cards to each other.  The player with the highest-valued card wins.

The more I think about this example, the more interesting it gets. It is equivalent to the problem of Playing Dice with transactions. So far, I think that both players should create a transaction, where they both put their coins on some 2-of-2 multisig wallet, choose their seeds, reveal hash of their seeds, and then reveal their seeds after signing their betting transaction. By using provably fair dice algorithm, they can simply check who won the prize. And then, if the loser sends coins to the winner, everything works as desired. If the loser became uncooperative, then funds will be locked on multisig wallet, as long as needed to solve that dispute (which could be never, but then only these two player lose and everyone else wins, because there will be less coins in circulation, so everyone else's coins will be worth more). Earlier I thought about some kind of "emergency timelocks" or "making it non-risky for each party", but it seems that risk of losing funds is necessary.

(Note that there have been no previous moves.)

The first move they made was revealing the hash of their public keys (or seeds if you want to make it simpler). By choosing their master private keys, generating master public keys from them and revealing master addresses, they started playing the game and they made everything deterministic from that point. And that kind of data can be hashed and used during the first time when the first player picks the first card.

exactly what data do Alice and Bob exchange?

I assume that Alice want to pick her first card. She needs:
1) her deck
2) Bob's public key
3) game's public key
The first one was explained above, she has her deck of 52 cards and it is shuffled correctly. The second one is taken from Bob, because Alice cannot know the next card without Bob's agreement. The third one is just the hash of the block that is multiplied by the ECDSA generator point. So, she could sum Bob's public key and game's public key. Then, she could add this point to each card to see, which one has the lowest public key and pick it.

[nullius]

Why not simply use that directly, without any point multiplications, with the player committing to a random seed in an ordinary commit-and-reveal scheme?

Because it would work only if everything will be used outside of coins. But if BTC on-chain coins are involved or even BTC-LN coins, or maybe some other altcoins,

Ah, I see what you are trying to do.  I did not see your previous thread; and it was not clear from OP that you are using the public keys to handle the wagered funds.

How is this turned into a hand of cards?

If you have two players and each of them has 52 cards, it is simple. The same if there are two players and one of them has all black cards and another player has all red cards. It is simple in all cases where players start from the same cards (sorted in different order) and the chances of winning depends more on their skills rather than their luck. But of course if both players use one shared deck of 52 cards, then things are more complicated.

My assumption was that cards are being dealt from a shared deck, so that the protocol could be applied to any traditional card game such as blackjack, poker, etc.  Thus, if Alice is dealt the Queen of Hearts, then Bob needs to pick a random card from a 51-card deck that does not contain the Queen of Hearts—and Bob is not allowed to know which card is missing.  (It seems obvious; but I have found that in such matters, it is important to state such things explicitly and precisely so as to avoid subtle mistakes.)

This thread caught my attention because I have tried to solve this problem before—but not integrated with Bitcoin transactions.  I did not yet find a practical solution which satisfied all of the various requirements I imposed.  Computing the state of the deck is a weird case of secure multiparty computation, where each party only has access to limited information; and I don’t know enough about MPC to say if there may already be an existing solution.  (I also suspect that what I am attempting may be impossible; but I have not been able to produce an impossibility proof, either.)

I will need to think more about what you have explained thus far...  Interesting problem.

Note:  My previous post has been edited with a bugfix, CVE-2021-NULL.  Whoops.

[vjudeu]

My assumption was that cards are being dealt from a shared deck, so that the protocol could be applied to any traditional card game such as blackjack, poker, etc.  Thus, if Alice is dealt the Queen of Hearts, then Bob needs to pick a random card from a 51-card deck that does not contain the Queen of Hearts—and Bob is not allowed to know which card is missing.  (It seems obvious; but I have found that in such matters, it is important to state such things explicitly and precisely so as to avoid subtle mistakes.)

One solution to this problem is removing duplicated cards on-the-fly, but that is quite strange solution. So that if Alice picked the Queen of Hearts, Bob can still pick any of the 52 cards (because he cannot know Alice's card) and then, if they both picked the Queen of Hearts, then they compare their public keys for their cards. The lower one remains, the other is discarded and replaced by the next card from deck. It would work fine in single card game, because the first card is also the last card, but in typical game it is too weird to be used.

[NotATether]

We don't need HD wallets or elliptic curve cryptography for this, just HMAC-SHA256. We can just extend the notion of client/server seeds and nonces that casinos use where each player generates their own client seed that's never broadcasted over the network, and they also generate a "server seed" except there's no central server here, the player broadcasts his own server seed to all the other placers.

So each player will have their own client seed and the other players' n-1 server seeds (they does not use their own server seeds), and their own nonce.

We are basically treating all the other players as "servers" in that they provide their own seed.

Then for eg player 3 to make a random number, they can run HMAC-SHA256(player 1 server seed + player 2 server seed + your client seed + player 4 server seed + ... + your nonce) where the "+" is concatenation of these random bits.

Then calculate a random number by dividing the 256-bit space into equal bins, and seeing in which "bin" the hash falls into, and use that bin as the random number.

For example, to only make numbers between 1 and 52, divide the possible hmac sha256 space into 52 different parts , in such a way that "1" will be numbers between 0 to (2^256 /52), 2 will be (2^256 /52) to (2^256 * 2/52) and so on.

This allows people to be able to refresh both their own client seed (and with it the nonce), or refresh their own server seed, which it has to update to all other players, so that the changing server seed only affects the other players' random number generator. This can be used for example if a player is not feeling particularly lucky.

Here, no blockchain is needed to synchronize game state, so gameplay becomes faster.