Jump to content
  • Advertisement
Sign in to follow this  
gpmelendez

Cryptographically secure p2p implementation of GG

This topic is 1860 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hello,

 

 

I have a question about how to create a mutual p2p trust between two players of this game. We have this stratego-like board game with game pieces of various ranks. When a there is a challenge between two pieces (they go to the same square) the winner (higher rank) is determined by a third party. The opponent's game pieces are never revealed to the other player.
 
How would I make a p2p program that doesn't require a third party and doesn't reveal the game pieces?
 
Problems with some suggestions:
 
Mental Poker - no, because the cards are revealed at some point.
Homomorphic encryption - no, because this requires the same encryption key.
Yao's millionare problem - no, because the higher piece doesn't always win, there are exceptions (see Spy and Private in the wiki link below)
 
Edited by mudslinger

Share this post


Link to post
Share on other sites
Advertisement

How would I make a p2p program that doesn't require a third party and doesn't reveal the game pieces?

It is logically impossible to do so.
Someone needs to make a decision which piece is stronger.
That someone needs to know the strength of both pieces.
You only have the two players to choose from to decide "someone."
Ergo, at least one of the players needs to know the strength of both pieces.

You have two choices:
1) Introduce a neutral third party, not under control of the two players. Typically, this is why online games use game servers hosted by the game operator. For a strategy game, it's quite likely you can have thousands of games running at the same time on a single server.
2) Relax the design, such that one of the players' computers (or both) knows all the game pieces, but don't display it to the user. A player using a memory scanner can find out all the pieces, but a casual player will still have a good game.

Share this post


Link to post
Share on other sites

1) Introduce a neutral third party, not under control of the two players. Typically, this is why online games use game servers hosted by the game operator. For a strategy game, it's quite likely you can have thousands of games running at the same time on a single server.
2) Relax the design, such that one of the players' computers (or both) knows all the game pieces, but don't display it to the user. A player using a memory scanner can find out all the pieces, but a casual player will still have a good game.

 

This defeats the point of my question. I don't think it's entirely impossible. Yao's millionaire problem comes pretty close.

 

This isn't really for a game, it's more of a thought experiment.

 

EDIT: I believe the problem is Secure Multi-party Computation, I just don't know how to implement it exactly yet.

Edited by mudslinger

Share this post


Link to post
Share on other sites

Someone needs to make a decision which piece is stronger.
That someone needs to know the strength of both pieces.
You only have the two players to choose from to decide "someone."
Ergo, at least one of the players needs to know the strength of both pieces.

What part of my argument are you saying is incorrect?
In the end, a compare-and-branch needs to happen in a CPU to decide that A is stronger than B.
To do that, you need to know the relative strengths of the pieces.
To do that, you need to impart strength information to the deciding side -- if not absolute, then at least relative enough that the other end *may* end up knowing the exact strength.

You can make some bit of obscuration by using some kind of binary search. "Is your pieces stronger than X?" If no, and I know is my piece, or weaker than my piece, then I know that the decision is made, without knowing exactly what the other piece is -- just that it is at least strong enough for X. If I choose X to not necessarily be my particular piece strength, sometimes some information can be held back. But, other times, the exact information is necessarily needed, when piece A is exactly one quantum stronger than piece B.

Share this post


Link to post
Share on other sites

But it is possible to compare two values from different parties without revealing those two values.

 

http://www.proproco.co.uk/million.html

 

I believe I currently have a solution in my head. 

 

EDIT: I plan to use the millionaire solution (link above) to compare pieces. To guard against players cheating the system by always sending a high piece, both players exchange encrypted piece positions with each other at game start. at game end, the decryption keys are exchanged to determine if they had been telling the truth.

 

It's rough, but it looks doable.

Edited by mudslinger

Share this post


Link to post
Share on other sites
As a simpler (and less secure) option to the millionaire solution, would be for Alice to send bob a table of 100 different units, and request that bob send back 100 booleans indicating if that unit would win the battle. Alice then picks out the vale for the actual unit there, and tells bob the result (and the system below detects lies later).
On average, there'll be 50 units on the list that match Alice's claimed outcome, so bob does know with a 1/50 chance what Alice's unit was... Alice also knows the strength of bob's unit, in that she knows the results for 100 hypothetical battles against it... Actually, maybe this isn't a good idea at all ;-/

both players exchange encrypted piece positions with each other at game start. at game end, the decryption keys are exchanged to determine if they had been telling the truth.

Some online card games work this way, and it should be extendable to any game with deterministic rules, as long as you're ok with deferring cheat detection until the very end of the game, when it's ok to reveal all the secrets. In a many-player game, if one player drops out half way through, there's no way to validate their actions (unless everyone gives their keys to a trusted 3rd party at the start).

Share this post


Link to post
Share on other sites

But it is possible to compare two values from different parties without revealing those two values.

 

http://www.proproco.co.uk/million.html

 

I believe I currently have a solution in my head. 

 

EDIT: I plan to use the millionaire solution (link above) to compare pieces. To guard against players cheating the system by always sending a high piece, both players exchange encrypted piece positions with each other at game start. at game end, the decryption keys are exchanged to determine if they had been telling the truth.

 

It's rough, but it looks doable.

 

Yes, but the point hplus0603 was making is that there is always some unevitable amount of information leakage about the other player's piece simply by virtue of knowing the result of the comparison and the value of your own piece. In some cases, or if you don't have many pieces, this may often be enough to deduce the other player's piece. For example, using cards, if my card is a king and you still win, then I know you have an ace, no matter how much cryptography and obfuscation you throw at the problem. A fix would be to increase the number of different pieces, or perform the comparison less often. Another method is to change the number of pieces dynamically, but this doesn't make for a very enjoyable game since the comparison is no longer consistent with what people would expect. If this caveat is unacceptable to you, your problem has no solution.

 

Otherwise, if this is fine (and hopefully it is) then Yao's approach seems doable since you probably don't have that many pieces. Now as for cheating, your solution works if the initial state + the movement information received by each player is enough to derive the game's state at any turn. You could also send the encrypted game state every turn with no information leakage for faster failure response (1 turn) but perhaps it is not worth it. Make sure to implement a commitment scheme as well so that a player can't "change his mind" on his game state once the keys are revealed (by revealing a fake key which decrypts to what he wants - not likely to succeed in practice but it can be done depending on your encryption scheme and the complexity of the game state).

Share this post


Link to post
Share on other sites

...

if this is fine then Yao's approach seems doable since you probably don't have that many pieces.

...

your solution works if the initial state + the movement information received by each player is enough to derive the game's state at any turn. 

...

a player can't "change his mind" on his game state once the keys are revealed (by revealing a fake key which decrypts to what he wants - not likely to succeed in practice

...

 

I thought of these, it is a yes on all three points. It is the nature of the game that the strength of a piece is partially revealed after a challenge (e.g. opponent's piece won, it's stronger than mine). 

Edited by mudslinger

Share this post


Link to post
Share on other sites

Yes, but the point hplus0603 was making is that there is always some unevitable amount of information leakage about the other player's piece simply by virtue of knowing the result of the comparison and the value of your own piece.

I believe that is by design in such games. This partial information is what the player uses to formulate their plan.

 

Just a thought, if you could impose a strict weak ordering on the ranks, I believe you can have a simple protocol to resolve the combat. Conceptually, each peer starts at the lowest value piece and asks if the other peer can beat it using their actual piece. If not, the peer asks if the next highest rank can beat it. And so on, stopping as soon as one player reveals they can beat that particular value. No more information is leaked than necessary.

 

For example, player A has a middling piece (e.g. "Lt. Colonel") but player B has a highly ranked piece (e.g. "Major General"). The protocol would be like so:

A -> B: Can you beat a flag: yes
B -> A: Can you beat a flag: yes
 
 
A -> B: Can you beat a spy: yes
B -> A: Can you beat a spy: yes
 
 
A -> B: Can you beat a private: yes
B -> A: Can you beat a private: yes
 
 
A -> B: Can you beat a sergeant: yes
B -> A: Can you beat a sergeant: yes
 
// ...
 
 
A -> B: Can you beat a major: yes
B -> A: Can you beat a major: yes
 
 
A -> B: Can you beat a Lt. Colonel: no
B -> A: Can you beat a Lt. Colonel: yes
 
 
 
 
 

Thus both players conclude that player B wins, without B revealing the exact value of the winning piece.

 

Unfortunately, the game you linked to does not appear to have this property, in particular due to the "Spy". Forcing the game logic to fit a strict weak ordering would probably also reduce some of the "strategy", by eliminating such interesting ranks; potentially making the game considerably less fun.

 

Maybe there is a clever way to handle such a case, but I cannot see it. The protocol would have be modified such that if a spy would lose, the spying peer can "reveal" the spy to allow the protocol to continue. Such an implementation would reduce the information being leaked to "just" spies (though they are quite a notable piece).

 

 

For example, player A has a their officer level piece (e.g. "Sergeant") and player B has a spy. The protocol would be like so:

A -> B: Can you beat a flag: yes
B -> A: Can you beat a flag: yes
 
A -> B: Can you beat a spy: yes
B -> A: Can you beat a spy: no, but I am a spy
 
A -> B: Can you beat a private: yes
B -> A: Can you beat a private: no, but I am a spy
 
A -> B: Can you beat a sergeant: no
B -> A: Can you beat a sergeant: yes

So the sergeant would be removed.

 

Maybe some of the uncertainty could be reclaimed by adding more special pieces to the mix, though the protocol itself might break down entirely too. Just thinking out loud, I may have made a mistake in my reasoning.

Share this post


Link to post
Share on other sites

No more information is leaked than necessary.

That's very open to cheating. I can pretend to have another piece, and thus get a good read on what your piece is.
The same holds for the Millionaire's problem -- if I can force a comparison with an arbitrary value, I can gain information.

If it were me, I wouldn't worry about players who are attaching to my game and reading that level of game state out of RAM.
If you need to play this for money or in tournament play, play should be on controlled hardware (e g in a physical location.)
For casual play, someone cheating online will just end up getting matched against other players also cheating online if your matchmaking is good enough :-)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!