[pmontra]

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.

[yeneek]

> "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)

[ranguna]

I'm currently working on a multiplayer game and I really really wanted to do this, but even if it works in principal, it fails in practice.

On step 3, this exchange does not happen exactly at the same time. If I'm playing with someone and we reach step 3, I could intentionaly hold myself from sending my data over, wait for the other player to send their data, and if their data wins against my (unsent) data, then I can simply choose not to send my data over (abort), forcing a tie.

This is easy enough to detect and you could just ban people that do this repetidly, but these people would just create new accounts whenever they get banned.

Hence, a cheater can either force a tie or win.

If you go down the rabbit whole on how you could theoricaly do this exchange fairly, you'll discover that this is provably impossible if you do not control the computational power of all parties (if you did, you could employ a time-locked puzzle with proof of work, for example).

This is known as a fair exchange with a fail-stop or secure-with-abort model.

See: http://www.cs.utexas.edu/~shmat/courses/cs395t_fall04/pagnia...

https://crypto.stackexchange.com/a/25458

https://crypto.stackexchange.com/a/26624

https://crypto.stackexchange.com/questions/8333/is-there-a-w...

http://www.iacr.org/archive/eurocrypt2010/66320221/66320221....

[yeneek]

Good point. Honestly, I think that it won't happen often. Who would wan't to sacrifice all fun to have bunch of blocked accounts with a few wins?

[ranguna]

It could potentially happen all the time if your game is played with high stakes. But yeah, for you average casual game it's a non issue.

[bo1024]

Hmm, "exchange is at least as hard as consensus". Guess you need to run your game on a blockchain? :)

[ranguna]

Yeah blockchain could work as a trustable 3rd party impossible to manipulate. Although I'm not sure there's any blockchain out there capable of handling realtime games, but can work for other types of games for sure.

[pmontra]

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]

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.

[denkmoon]

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.

[bo1024]

Cryptography can solve this, see: https://en.wikipedia.org/wiki/Mental_poker

[ranguna]

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]

Sorry, not my area of expertise. I wasn't aware of the caveats brought up in your other post.

[jonititan]

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/