Jump to content
Toggle sidebar
JookWiki
Search
Create account
Log in
Personal tools
Create account
Log in
Pages for logged out editors
learn more
Contributions
Talk
Navigation
Main page
Recent changes
Random page
All pages
Help about MediaWiki
Tools
What links here
Related changes
Special pages
Page information
Editing
Multiplayer RNG
Page
Discussion
English
Read
Edit
Edit source
View history
More
Read
Edit
Edit source
View history
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
[[Category:Research]] 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 == 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: # Each player generates a random number # They prove to other players they have generated their number # All players reveal their numbers # 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 == Using modern cryptography primitives the protocol works like this. Each player does this: # Agree on which players will be participating in the generation # Generate a random 256-bit number # Hash the number using BLAKE3 # Announce the hash to other players # Wait for other players to announce hashes # Associate the hash with the announcing player # If a player doesn't send a hash, bail out of generation # Announce the random number # Wait for other players to announce random numbers # All players wait for all random numbers to arrive # If a player doesn't send a number, bail out of generation # Associate the number with the announcing player # Hash each player's number using BLAKE3 # Validate that the hash matches the hash sent earlier # If a hash doesn't match, bail out of generation # 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 == 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 == Credit for the original idea comes from [https://stackoverflow.com/questions/224058/distributed-random-number-generation 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.
Summary:
Please note that all contributions to JookWiki are considered to be released under the Creative Commons Zero (Public Domain) (see
JookWiki:Copyrights
for details). If you do not want your writing to be edited mercilessly and redistributed at will, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource.
Do not submit copyrighted work without permission!
To edit this page, please answer the question that appears below (
more info
):
Who owns this wiki?
Cancel
Editing help
(opens in new window)