5 ms·

Very interesting. As well as other usages it seems this would be one way to host online games. The app itself being the only thing served centrally and then in

Very interesting. As well as other usages it seems this would be one way to host online games. The app itself being the only thing served centrally and then instances of the app get served by website visitor's to host their own private workspace/gamespace. So all data created in that instance would remain private to that instance and the clients that connect to it. Is that a reasonable use case or am I misunderstanding?

pmontra 4y ago
Imagine a card game with a deck and two players. The deck knows which player got which card. Each player knows its own cards and the ones on the table. The deck should not run in the browser of one of the players because that player could inspect the status of the deck and know which cards were handed to the other one. To answer your question: maybe, but for almost any game you need a trusted third party that holds the secret state of the game. A third browser somewhere or a headless server? Exceptions: complete information games like go, chess and checkers. Everything is public. Games with a dice like backgammon starts to be problematic because how can one player trust the dice of the other player? A shared random seed would let them know in advance all the rolls.
- bo1024 4y ago
  Cryptography can solve this, see: https://en.wikipedia.org/wiki/Mental_poker https://en.wikipedia.org/wiki/Mental_poker
  - ranguna 4y ago
    Although promising, I don't see how this umbrella concept helps solve the issue. Could you be more precise on the exact step by step protocol that would allow for a fair exchange of two random numbers and subsequent result without allowing the parties to cheat?
    - bo1024 4y ago
      Sorry, not my area of expertise. I wasn't aware of the caveats brought up in your other post.
- denkmoon 4y ago
  Most games just accept this. One of the most profitable games in history (GTA Online) is trivially hackable because there is no server maintaining state, it's just peers telling each other what they did.
- yeneek 4y ago
  > "how can one player trust the dice of the other player?" I have an algorithm for that. To roll a dice: 1. both players create a random x bytes long number. 2. both players make a hash from their number and then send it to the other one. 3. players exchange their random numbers and check if hashes are correct 4. concat both players random numbers and hash it to get the final random number By exchanging hashes, both players can be sure that other player didn't tamper with their random number after getting yours. (edited formatting)
  - pmontra 4y ago
    Maybe there are well known attacks against this scheme. Let's try a naive one. Conditions first: it's a 6 sides die. I need 1 to win, you need 2. The final number will be the hash of step 4 modulo 6. Let's try a naive implementation with 1 byte long numbers, no random bits to fill out the unused 5 bits of that byte. When I receive your hash I compare it with the only 6 possible hashes (micro rainbow table.) I know your number is 4. The possible pairs will be 14, 24, 34, 44, 54, 64 (how we mix the bits of those pairs is deterministic so let's do a simple n*10+m.) If the hash of one pair modulo 6 is 1, I'll give you the hash of the first number of that pair otherwise maybe you cheated and sent me a hash that will at least ensure that I don't win now ;-) We can add random bits, a lot of them, with the idea of making sure that the time I must spend is a very long one and exceed a timeout. However I must know where your number is in those bits. Let's say the number is at position 5 and you sent me the hash for 9999499999. I can try to be lucky and find your number by hashing random ones, then try to find a number with a digit <= 6 in its fifth position so that I win and send you that hash. Occasionally I will be able to generate a good number for me, not all the times. As a side note, a friend working with inmates told me that when they play backgammon they share the same dice because they don't trust the other player not to have loaded dice. Those dice become a trusted third party. If they are loaded, the distribution is the same for everybody. Finally, is the random distribution of your method still uniform? I didn't reason about it.
    - yeneek 4y ago
      If the random numbers can be 1-6, then yes, it would be trivial to attack. If the numbers are 300 bytes long, then it's impossible to predict. > "I can try to be lucky and find your number by hashing random ones," If we were using sha-256, then you would be very impossibly lucky. There are 2^256 possible hash values for sha-256. It's extremely unlikely, that you would find a collision in the lifetime of the universe.
- jonititan 4y ago
  In this instance the server is the browser of whoever started the session and the others are clients? I was imagining a browser based Maptool. https://www.rptools.net/toolbox/maptool/ https://www.rptools.net/toolbox/maptool/
noAnswer 4y ago
Multiplayer games of old where usually p2p. DoS attacks from sad losers an cheating put an end to that.
- meibo 4y ago
  A lot of things did, not just what you mentioned. It's a lot harder to replicate a high amount of data to a high amount of players in p2p, since you have to send that data to everyone you're playing with, and you're basically limiting yourself to residential connections/wifi which are still crappy and have a high amount of lag. For the kind of fast-paced games people make/expect nowadays, this isn't really acceptable anymore.

pmontra 4y ago

Imagine a card game with a deck and two players. The deck knows which player got which card. Each player knows its own cards and the ones on the table. The deck should not run in the browser of one of the players because that player could inspect the status of the deck and know which cards were handed to the other one. To answer your question: maybe, but for almost any game you need a trusted third party that holds the secret state of the game. A third browser somewhere or a headless server? Exceptions: complete information games like go, chess and checkers. Everything is public. Games with a dice like backgammon starts to be problematic because how can one player trust the dice of the other player? A shared random seed would let them know in advance all the rolls.

bo1024 4y ago
Cryptography can solve this, see: https://en.wikipedia.org/wiki/Mental_poker https://en.wikipedia.org/wiki/Mental_poker
- ranguna 4y ago
  Although promising, I don't see how this umbrella concept helps solve the issue. Could you be more precise on the exact step by step protocol that would allow for a fair exchange of two random numbers and subsequent result without allowing the parties to cheat?
  - bo1024 4y ago
    Sorry, not my area of expertise. I wasn't aware of the caveats brought up in your other post.
denkmoon 4y ago
Most games just accept this. One of the most profitable games in history (GTA Online) is trivially hackable because there is no server maintaining state, it's just peers telling each other what they did.
yeneek 4y ago
> "how can one player trust the dice of the other player?" I have an algorithm for that. To roll a dice: 1. both players create a random x bytes long number. 2. both players make a hash from their number and then send it to the other one. 3. players exchange their random numbers and check if hashes are correct 4. concat both players random numbers and hash it to get the final random number By exchanging hashes, both players can be sure that other player didn't tamper with their random number after getting yours. (edited formatting)
- pmontra 4y ago
  Maybe there are well known attacks against this scheme. Let's try a naive one. Conditions first: it's a 6 sides die. I need 1 to win, you need 2. The final number will be the hash of step 4 modulo 6. Let's try a naive implementation with 1 byte long numbers, no random bits to fill out the unused 5 bits of that byte. When I receive your hash I compare it with the only 6 possible hashes (micro rainbow table.) I know your number is 4. The possible pairs will be 14, 24, 34, 44, 54, 64 (how we mix the bits of those pairs is deterministic so let's do a simple n*10+m.) If the hash of one pair modulo 6 is 1, I'll give you the hash of the first number of that pair otherwise maybe you cheated and sent me a hash that will at least ensure that I don't win now ;-) We can add random bits, a lot of them, with the idea of making sure that the time I must spend is a very long one and exceed a timeout. However I must know where your number is in those bits. Let's say the number is at position 5 and you sent me the hash for 9999499999. I can try to be lucky and find your number by hashing random ones, then try to find a number with a digit <= 6 in its fifth position so that I win and send you that hash. Occasionally I will be able to generate a good number for me, not all the times. As a side note, a friend working with inmates told me that when they play backgammon they share the same dice because they don't trust the other player not to have loaded dice. Those dice become a trusted third party. If they are loaded, the distribution is the same for everybody. Finally, is the random distribution of your method still uniform? I didn't reason about it.
  - yeneek 4y ago
    If the random numbers can be 1-6, then yes, it would be trivial to attack. If the numbers are 300 bytes long, then it's impossible to predict. > "I can try to be lucky and find your number by hashing random ones," If we were using sha-256, then you would be very impossibly lucky. There are 2^256 possible hash values for sha-256. It's extremely unlikely, that you would find a collision in the lifetime of the universe.
jonititan 4y ago
In this instance the server is the browser of whoever started the session and the others are clients? I was imagining a browser based Maptool. https://www.rptools.net/toolbox/maptool/ https://www.rptools.net/toolbox/maptool/

noAnswer 4y ago

Multiplayer games of old where usually p2p. DoS attacks from sad losers an cheating put an end to that.

meibo 4y ago
A lot of things did, not just what you mentioned. It's a lot harder to replicate a high amount of data to a high amount of players in p2p, since you have to send that data to everyone you're playing with, and you're basically limiting yourself to residential connections/wifi which are still crappy and have a high amount of lag. For the kind of fast-paced games people make/expect nowadays, this isn't really acceptable anymore.