Secret state? - Githubissues

ryanschneider commented 6 years ago

I'm curious if you've thought about how to handle secret state like a deck to draw from and players hands? Perhaps using key pairs to encrypt/decrypt the state? For a deck, this would require a trusted server component that can decrypt, deal, and re-encrypt the deck state, but feels like an approach that works.

I planned on using such an approach for a game I wanted to make using Firebase but never got around to building the backend (though I have an old iOS Swift 2 code base for the prototype client using Game Centers old pass and play system). it was basically Leterpress with Poker hands, perhaps I'll try porting it to this time permitting (but it needs secret state, hence my question).

nicolodavis commented 6 years ago

Very good question.

This wasn't really on the roadmap for v1.0, but I think we should prioritize it. Maybe just have all secret information only on the server? A deck of cards could just show how many cards there are on the client (it doesn't really need anything else in order to render the deck).

I don't see the value in encryption for this use case.

a3qz commented 6 years ago

I have experimented with this a little bit in side projects, and the only approach to this that has seemed feasible to me other than "trust your players not to dig into the javascript on your site to cheat" is to, in multiplayer, assign each instance a unique identity and for items such as player's hands and the deck in card games, let the server handle what each player is given/can see.

This library seems at least for now more focused on running the whole game client side and like a more traditional board game, which makes the trust the player approach seem fairly reasonable.

ryanschneider commented 6 years ago

So, IMO, the main value of encryption is that the same state can continue to be seen and replicated by all parties, but the private parts would only be visible by those who have access.

Imagine this state object for a game of heads up Texas Holdem:

{
    deck: {
        count: 42,
        encrypted_contents: "encrypted w/ Server key"
    },
    pot: 30,
    board: ["Ad", "3h", "2s"]
    players: [
        {
            hand: {
                count: 5,
                encrypted_contents: "encrypted w/ p1 key"
            },
            chips: 200
        },
        {
            hand: {
                count: 5,
                encrypted_contents: "encrypted w/ p2 key"
            },
            chips: 270
        }
    ]
}

And then imagine a pure transform function D(State, Keys...) that decrypts encrypted_contents when it's valid for one of the keys passed in.

P1's view of the State becomes D(State, P1Key):

{
    deck: {
        count: 42,
        encrypted_contents: "encrypted w/ Server key"
    },
    pot: 30,
    board: ["Ad", "3h", "2s"]
    players: [
        {
            hand: {
                count: 5,
                encrypted_contents: "encrypted w/ p1 key",
                                contents: [ "As", "Kd" ] // added by state xform function
            },
            chips: 200
        },
        {
            hand: {
                count: 5,
                encrypted_contents: "encrypted w/ p2 key"
            },
            chips: 270
        }
    ]
}

While P2's would be D(State, P2Key):

{
    deck: {
        count: 42,
        encrypted_contents: "encrypted w/ Server key"
    },
    pot: 30,
    board: ["Ad", "3h", "2s"]
    players: [
        {
            hand: {
                count: 5,
                encrypted_contents: "encrypted w/ p1 key"
            },
            chips: 200
        },
        {
            hand: {
                count: 5,
                encrypted_contents: "encrypted w/ p2 key",
                                contents: [ "3d", "3c" ] // added by state xform function
            },
            chips: 270
        }
    ]
}

And, if the server has access to the p1 and p2 keys, it would have a complete view of the plaintext state D(State, [P1Key, P2Key, ServerKey]):

{
    deck: {
        count: 42,
        encrypted_contents: "encrypted w/ Server key",
                contents: [ /*...*/ ] // added by state xform function
    },
    pot: 30,
    board: ["Ad", "3h", "2s"]
    players: [
        {
            hand: {
                count: 5,
                encrypted_contents: "encrypted w/ p1 key",
                                contents: [ "As", "Kd" ] // added by state xform function
            },
            chips: 200
        },
        {
            hand: {
                count: 5,
                encrypted_contents: "encrypted w/ p2 key",
                                contents: [ "3d", "3c" ] // added by state xform function
            },
            chips: 270
        }
    ]
}

Likewise there would be an encryption function E(State, Keys...) that removes contents and updates the encrypted_contents value as well, such that E(D(State, Keys...), Keys...) == State.

This implementation requires a trusted server. There are encryption models that don't (see: https://en.wikipedia.org/wiki/Mental_poker) however I think that's way outside the scope of a v1, where as I think something like the above could be on the v1.x roadmap.

If worried about cheating (and on any multiplayer game on the Internet you need to be), there are some other things to keep in mind if going down this route sounds interesting:

Which keys are valid for which parts of the state tree should also be defined somewhere (either in code or in a section only editable by the trusted server). This prevents a user from doing something crazy like encrypting the board w/ their key.
The encrypted contents should include the path to the contents (e.g. players[0].hand) to prevent copy attacks (otherwise a player could swap the deck and their hand when submitting, and the server might decrypt and re-encrypt).
Likewise you might want a nonce in the overall state (just a value that increases by 1 with each turn submission), and embed that in the encrypted contents as well, to prevent replay attacks (A player keeping his encrypted hand from 3 turns ago and then pasting it back in later). However, this requires then re-encrpyting w/ the new nonce on each submission.
These aren't high-value secrets, the keys just need to be big enough to prevent brute-forcing during a game (but keep in mind that a player could decrypt a game several months later with enough compute power to learn if you were bluffing in the final hand or not).
New keys should be used per game, and distributed at the start. Since there's already a trusted server required it should probably just generate the keys for each game and give them to the player outside of the state.

Anyways, I think my key point is that cryptography would let a single state be shared by all players without giving all the players access to all the information, which IMO feels simpler and more in line w/ the React/Redux philosophies than trying to manage and merge different states per player in an adhoc way.

confusingstraw commented 6 years ago

This seems really similar to the issue I submitted ( #23 ), so I guess I'll just share my opinion here. I think cryptography is overkill for the intended use-case. I think for most games, showing the client only the information it needs to know is a more accurate abstraction than cryptography.

As far as philosophy goes, I believe that for most multiplayer games the client state is essentially just a projection of a subset of the global state (the authoritative source). It seems like the cryptography approach effectively achieves the same goal, but I don't really see any tangible value it adds.

If the goal is a p2p approach, there still needs to be some master (or host, to use gaming terminology), so I'm having trouble seeing any unique benefit this confers.

a3qz commented 6 years ago

I agree with @rgfoley, for the intended use case, an implementation of encryption would add overhead and complexity when really that kind of data is better off staying in an "authoritative source" and letting the server handle things that the player should not have access to.

In theory in a symmetric game with hidden areas, what the players have in their states would still follow the same structure, just it would represent different things, and would be interpreted by the server.

w74 commented 6 years ago

i say having "hidden" information is important (especially if we want demos as hidden role games are the easiest to program) but crypto is a little too much.

Kinrany commented 6 years ago

It would be nice to separate the game logic from the visibility rules.

Maybe you could use something like GraphQL to specify the part of the game state that is available to each player?

jmcshane commented 6 years ago

I want to echo @rgfoley as I research how to use this library to implement a couple specific games I am interested in testing out. It would be great to have the game object have "client" plugins and "server" plugins to the game object, where the client plugin data goes to the browser based on a matching playerId of some sort and the server plugin data does not appear to any user.

I'm definitely interested in contributing in this direction, but would like to hear more from @nicolodavis before proceeding.

nicolodavis commented 6 years ago

Some great ideas in here. Thanks for the discussion, guys!

Let's start with something simple, and expand from there as we see use-cases that need them. There are two parts to what needs to happen for this feature to become a reality:

1. Make the client-side code aware of who the current player is

A simple prop to the returned React component on the client will do. In reality, the notion of a player needs to become a first-class citizen in the library.

ReactDOM.render(<App gameid="..." currentPlayer="..." />, ...)

2. Define areas of state that are private

I actually think a simple object inside G that's reserved for players will do the trick.

G: {
  players: {
    0: {...},
    1: {...},
    2: {...},
  }
}

I've used 0, 1 and 2 as keys here, but depending on what [1] does to how players are keyed, this will need to change accordingly. Whenever a players object is used inside G, the framework will know to delete all the keys that don't correspond to the current player before sending it over to the client.

@jmcshane Do you want to take a stab at this? I can take [1] if you want to do [2].

ryanschneider commented 6 years ago

For [2] there’s also the server-only state (e.g. a deck in poker).

On Tue, Dec 19, 2017 at 8:56 PM Nicolo John Davis notifications@github.com wrote:

Some great ideas in here. Thanks for the discussion, guys!

Let's start with something simple, and expand from there as we see use-cases that need them. There are two parts to what needs to happen for this feature to become a reality:

Make the client-side code aware of who the current player is

A simple prop to the returned React component on the client will do. In reality, the notion of a player needs to become a first-class citizen in the library.

ReactDOM.render(, ...)

Defining areas of state that are private

I actually think a simple object inside G that's reserved for players will do the trick.

G: { players: { 0: {...}, 1: {...}, 2: {...}, } }

I've used 0, 1 and 2 as keys here, but depending on what [1] does to how players are keyed, this will need to change accordingly. Whenever a players object is used inside G, the framework will know to delete all the keys that don't correspond to the current player before sending it over to the client.

@jmcshane https://github.com/jmcshane Do you want to take a stab at this? I can take [1] if you want to do [2].

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/google/boardgame.io/issues/16#issuecomment-352964830, or mute the thread https://github.com/notifications/unsubscribe-auth/AADRENPZl5BwuJ25eE_7HkS5mnwnKWyrks5tCJOCgaJpZM4RE0EI .

nicolodavis commented 6 years ago

Good point. Actually there isn't a good story for that (yet).

The server currently merely relays information between clients, and doesn't really do much more. With #7 and other ideas in this space, we'll eventually need to have the server start being a "player", at which point the model we have here should fit naturally (with the syntax modified suitably).

ryanschneider commented 6 years ago

Maybe just a convention that player 0 is the game itself? If so maybe call it clients instead of players, and make the distinction between the server (which just relays messages), and the “game client” which is client 0 and has access to the entire client state.

I’m just spitballing I’m sure much better terms can be decided on.

On Tue, Dec 19, 2017 at 9:47 PM Nicolo John Davis notifications@github.com wrote:

Good point. Actually there isn't a good story for that (yet).

The server currently merely relays information between clients, and doesn't really do much more. With #7 https://github.com/google/boardgame.io/issues/7 and other ideas in this space, we'll eventually need to have the server start being a "player", at which point the model we have here should fit naturally (with the syntax modified suitably).

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/google/boardgame.io/issues/16#issuecomment-352970982, or mute the thread https://github.com/notifications/unsubscribe-auth/AADREKRCScDYx3bLaae3w8nR1o5pCQEgks5tCJ99gaJpZM4RE0EI .

Kinrany commented 6 years ago

Three other things:

Sharing secret information. Games like Secret Hitler, or something with teams.
Fog of war in a game with tiles, like Carcassonne.
Would making information public (e.g. player's position on the board) mid-turn work fine?

amitport commented 6 years ago

This is one of the main use-cases I considered for cardforest.com (demo), which was my attempt on making something very similar to boardgame.io (think boardgame.io + stackblitz) (a bit outdated) (not released)

Instead of using redux (which wasn't really a thing when I started), I used a mutable state object wrapped in a proxy that keeps track of changes (open source at https://github.com/CardForest/master-class). This makes writing the game logic a lot more natural. This also made it possible to write specialized serialization adapters that can decide how to serialize the changes/state for each player.

vdfdev commented 6 years ago

@nicolodavis Definitively we are going to need one "player" to be the game itself. Specially when there is dice, we can model the dice being an action taken by this player.

The only thing to keep in mind, though, is that we shouldn't assume that this player must live in the server. If the person is playing a single player game, there should be no need to connect to the internet. Specially given efforts on Progressive Web Apps, which I want to explore, we could have an installed app that runs offline with AI and all.

But if it is a multiplayer game, we definitively want the server to be throwing the dices, keeping the secret state, etc...

confusingstraw commented 6 years ago

I think a good starting point is to acknowledge the server as the golden source of state information for the game at any given time. From there, each player is given some filtered view of the state that corresponds to what they need to know. Using that information, the player dispatches actions that cause the state to change on the server and the cycle continues.

For games like chess, the server view and player view are the same thing, so no filtering is needed. For games like poker, the server should know both players' hands, but should only let a player see their own hand.

The downside of the approach mentioned by @nicolodavis is that you may want to broadcast some partial state (for example, the number of cards in the other player's hand), which makes having player-specific slices a bit difficult to work with.

Another challenge presented by this method is how to support team-oriented games. Imagine a card game consisting of two teams of two players. They cannot see the other team's cards, but they can see their partner's cards.

Even more challenging would be state that is revealed only to certain players. Imagine a strategy game. Perhaps, by default, I cannot see another player's resources. If some kind of "spy" unit allows me to see that player's resources, how do I conditionally show that state?

I think if we start to consider the myriad exceptions to each rule, the solution is to support "hooks" in the server logic to apply filtering rules to the global state. These "hooks" would amount to the business logic that makes up the rules of a particular game. From there, we can use the method suggested by @nicolodavis to just have player-specific slices of state, and let the server worry about hydrating them with "need-to-know" information.

amitport commented 6 years ago

@rgfoley sorry for repeating the shameless plug (last time, I promise), but https://amitport.gitbooks.io/master-class/content/docs/serialization.html is a valid implementation for all the use cases you mention (not perfect, a bit out dated, but worth looking into).

The state object has a snapshot method that accepts a mapper function. The mapper is called on every property in the state object tree (deep properties), it has access to context (such as the property's location and schema options) and can map the property value to something else (e.g., an object representing an hidden/partial/augmented state) (I can go into more details, if anyone is interested 😶 )

nicolodavis commented 6 years ago

I think some sort of mapping function (a reducer, essentially) that takes the global state and provides a client specific view makes a lot of sense.

The filtering I suggested above based on the players object could be one such reducer that comes bundled with the library. The user is free to implement more complex ones for other game types.

I need to think a bit more about the server as a player. Let us talk about that in a separate issue #38. I agree that this should not dilute the single player experience, which is important while prototyping.

nicolodavis commented 6 years ago

@amitport cardforest looks really neat, btw!

nicolodavis commented 6 years ago

Tracking effort in this space here if people are curious about the roadmap. If anyone wants to contribute code, feel free to grab one the items in the Unstarted section.

nicolodavis commented 6 years ago

Closing this in favor of the one remaining item at #72

boardgameio / boardgame.io

Secret state? #16

1. Make the client-side code aware of who the current player is

2. Define areas of state that are private