Multiplayer RNG

From JookWiki
Revision as of 02:43, 1 September 2022 by Jookia (talk | contribs) (Add section on best-effort generation)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

For a while now my friend Koz has been throwing around the idea of a peer-to-peer multiplayer card game. These games rely heavily on random numbers for things like drawing from card decks. Here's my idea for a protocol to accomplish that.

Overview[edit | edit source]

The protocol assumes the following:

  • Players can generate numbers they trust to be random
  • Players distrust numbers generated by other players
  • These random numbers are secret unless told to other player

These assumptions seem reasonable to me at least and match my expectations of multiplayer games.

The protocol I propose here works like this:

  1. Each player generates a random number
  2. They prove to other players they have generated their number
  3. All players reveal their numbers
  4. The numbers are mixed to generate a final random number seed

Step 2 is necessary to prevent players from picking numbers could unmix other player's numbers.

The mixing agent here needs to ensure that no player's randomness (or entropy) is removed, only added.

Concrete specification[edit | edit source]

Using modern cryptography primitives the protocol works like this.

Each player does this:

  1. Agree on which players will be participating in the generation
  2. Generate a random 256-bit number
  3. Hash the number using BLAKE3
  4. Announce the hash to other players
  5. Wait for other players to announce hashes
  6. Associate the hash with the announcing player
  7. If a player doesn't send a hash, bail out of generation
  8. Announce the random number
  9. Wait for other players to announce random numbers
  10. All players wait for all random numbers to arrive
  11. If a player doesn't send a number, bail out of generation
  12. Associate the number with the announcing player
  13. Hash each player's number using BLAKE3
  14. Validate that the hash matches the hash sent earlier
  15. If a hash doesn't match, bail out of generation
  16. XOR together all player's numbers to create a final number seed

This requires two round trips and results in a number with an entropy of at least 256 bits.

This is a large number intended for seeding some per-turn number generator, such as picking multiple cards from a deck or calculating damage.

Best-effort generation[edit | edit source]

Bailing out if a player doesn't send a valid input ensures there's two outcomes: No seed, or a seed that each player agrees is fair. Having a fair seed is great, but having no seed is perhaps even worse than an unfair seed.

An interesting property of the protocol is that all player's inputs are generated independently of each other and shown to be independent. Instead of bailing out of generation it's possible to just continue but discard a player's input or lack thereof. This is identical to the player not participating in the generation in the first place.

The main challenge from this approach is convincing a player that they were fairly and necessarily left out of the generation process. A player who disconnects will probably agree it's fair to be cut out of the process. A player who temporarily loses connectively might grumble about fairness if they don't get a say in a roll. A player who keeps getting lag spikes when it's time generate a number and never getting a chance to participate may not.

Prior work[edit | edit source]

Credit for the original idea comes from Distributed Random Number Generation on StackOverflow. However that protocol has a few oddities to me at least:

Instead of generating a large random number that's easy to pass from some source of entropy (like random bytes), it generates a smaller number. This requires using a random number generator to get a small number, salting the number to avoid guessing the hash (by generating a larger random number like we do), and then use addition as the mixing agent.

That seems trickier to implement.