Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I am trying to create a decentralized moderation system for the game Diplomacy, a game for seven players. In each round of a face-to-face game, each player writes their moves on paper then puts it in a box; all moves are read at once. The game was popular as play-by-mail: you mail your moves to a magazine publisher, who aggregates all moves and publishes game updates to everyone. In each round of an online game, each player sends their moves to a third-party "moderator", who then aggregates the moves and relays all moves to all players. The players must agree beforehand to a third-party moderator.

I would like to create a decentralized system without the need for a moderator. Each player can run a web-accessible server. Each round, each player will broadcast their moves (encrypted somehow) to all other players. When all players have broadcasted their moves, only then can all players read the other players' moves.


Initially, I thought of using something like the Three-pass Protocol: Player A writes a message, puts it in a box with Padlock A, and sends it to Player B. Player B puts Padlock B on the box and returns it to Player A. Player A removes Padlock A and returns the box to Player B. Player B can now remove Padlock B and read the message.

The players would be arranged in a ring: Player A always passes messages to Player B, Player B always passes messages to Player C, etc. So each message ends up in a box with seven padlocks on it. Only when it has gone around the entire ring can all the players read the messages.

But this doesn't solve the problem of noncooperation: On the sixth pass, Player D can stop sending messages to Player E, read everyone else's moves, and not cooperate further.

Player D and Player F can also choose to cooperate with eachother, and keep Player E out of the loop. That would be bad for Player E.

In a game like Diplomacy, it is not acceptable to allow one player to read any other player's moves without all players reading all moves.


Another thought is for each player to privately send their moves, locked in a box, to each other player (via private-public keys). When a player receives the box, then that player broadcasts to everyone, "hey everyone, player X sent me a box which hashes to abc123!". When everyone finds that everyone else has received all other boxes, then they can swap them back. This allows some player to lie to everyone else, but the downside is "nobody gets anything".


I think I'm on the right track here, but I'm not sure. Is this a correct way of thinking about the problem? Has this already been done (I can't find another solution already)?

share|improve this question
1  
Woo, go Diplomacy! There are "Commitments" which might be worth considering - as in you make eacy player commit to their moves then reveal them later. The issue with using commitments is that someone could refuse to show their moves, but if they do this then you can just eject them from the game or similar. I can't think of a method where you could force players to both commit and to open their commitments. –  figlesquidge Jun 19 at 19:35
    
In that case, I would have each player broadcast the hash of their moves to everyone else. Then, everyone must broadcast the plaintext for verification? –  Joe Frambach Jun 19 at 19:40
    
That doesn't work, since one can just try inputs. $\;$ –  Ricky Demer Jun 19 at 21:17
    
You mean that given a hashed value, the recipients can find the original message by brute force? The commitment phase could be set 5 minutes before the reveal phase, with a long salt. –  Joe Frambach Jun 19 at 21:30
1  
I suppose one could try something like that, but I don't see any reason to prefer doing so $\hspace{.92 in}$ over using an actually secure commitment scheme. $\;$ –  Ricky Demer Jun 19 at 21:43
add comment

2 Answers 2

up vote 3 down vote accepted

See malleability and commitment schemes.
You are apparently looking for a collusion-preserving implementation of simultaneous broadcast.
By letting each processor control at least one player and directing each processor to choose a random bit for each of its players and outputting the xor of all players' random bits, the resulting coin-flipping protocol is as fair as the system. $\:$ Thus, one smacks straight into this paper's impossibility result.
The ways I know of to get around that impossibility result are:

$\;$ time-lock puzzles, with which the amount of work needed for cooperating players
$\;$ to read the messages is "not too much more" than the amount of work needed for
$\;$ adversarial players to read the messages, and in both cases; the relevant work only
$\;$ needs a small amount of memory and is not (known to be feasibly) parallelizable

$\;$ partial fairness, so that when more than 1/3 of the players are cooperating
$\;$ (in particular, when there are only 2 players) and the number of possible messages is small,
$\;$ cooperating players get "not much less" information than adversarial players get

$\;$ having lots of moderators that only need to be contacted if a player stops participating
$\;$ before or during a reveal phase, each of whom is assigned a small positive integer weight
$\;$ (presumably less than the threshold I'll mention later in this text-block, otherwise there's no point
$\;$ in using more than one moderator), so that if [the sum of the weights assigned to adversarial
$\;$ moderators] is less than [the threshold chosen before the reveal phase begins] is less than or
$\;$ equal to [the sum of the weights assigned to the moderators who appear to be cooperating]]
$\;$ then the "All can read it, or none can read it" property holds

.


(A moderator that merely cannot be contacted or has lost its private key
is neither adversarial nor one who appears to be cooperating.)

To emphasize, even if all moderators are adversarial, the only thing they can do is let players
who stop participating violate the desired "All can read it, or none can read it" property.
In particular, each message must still be chosen independently of the other messages.

It may be that there are other ways around that impossibility result; in particular,
I don't see a reason why the 1/3 threshold should be critical for partial fairness.
Even if there aren't, it appears to me that one could combine the "partial fairness" option with the
"lots of moderators" option in a way that is at least as good as the latter but also provides partial fairness when the latter's inequalities are not too far off and the number of possible messages is small.

Note that I have no idea which of the three options I
described are compatible with being collusion-preserving.

share|improve this answer
    
Well, that impossibility result is quite depressing. I'm going to think about the human aspect of the problem: how to incentivize cooperation, and what to do to detractors. Would be a shame to end a game due to one detractor. –  Joe Frambach Jun 19 at 22:01
    
When using the "lots of moderators" option, it would take at least half of the moderators to violate the $\;\;\;$ all-or-none property, not just "one detractor". $\:$ Also, even if that happens, each detracting player can only hide that player's own message from the rest of the players, i.e., the non-detractors' messages still get revealed and still must be independent of each other. $\;\;\;\;$ –  Ricky Demer Jun 19 at 22:13
    
I'll accept the impossibility solution. I think it would be difficult to maintain independent arbiters while also playing the game. It would add an aspect of mistrust. –  Joe Frambach Jun 20 at 5:08
    
(Especially in a game explicitly built around misleading fellow players!) –  figlesquidge Jun 20 at 9:01
add comment

This is very difficult, if you don't trust anyone, as Ricky Demer explains. You can have each party publish a commitment to their move. However, the main problem is that a malicious party might decide not to open their commitment.

For instance, suppose Alice publishes a(non-malleable) commitment to her move, and Bob publishes a commitment to his move. Then, after both values are public, we ask them to open their commitments and reveal their moves. If they both reveal their moves, we can verify that they have correctly opened the commitment (and haven't tried to later change their move). But what if Alice opens her commitment and publishes her move, and then Bob regrets his choice of move and decides not to publish his move? Then we have no way to figure out what Bob's move was, and we're stuck. Everyone might know that Bob is not cooperating, but they still can't figure out what his move is.

One approach is to use deterrence. For instance, we could establish rules in advance saying that if Bob doesn't open his commitment and publish the opened value within a set time, he automatically loses the game. But now what if Bob claims he opened it, but actually didn't? What if he sends his opening value to some players but not to others? What if he claims that his connection dropped for reasons out of his control? What if he sees that opening his move would lead him to surely lose anyway? (Then he has no incentive to reveal the opening to his commitment.) In any case, if there is a dispute like this, how will disputes be resolved? It's not clear how to resolve such disputes without a moderator.

One recent positive result shows how to do fair multi-party secure computation, by taking advantage of Bitcoin to build timed commitments. A timed commitment is one where Alice commits to a value (e.g., her move), and pays a deposit of a certain number of Bitcoins. If Alice later opens her commitment and reveals her move within a set time period, she gets her deposit back. If she doesn't, the other parties get to split her deposit, so they are at least compensated for Alice's misbehavior. This both incentivizes Alice to follow the protocol (cheating will cost her) and compensates the other plays for cheating. There are recent schemes for building a timed commitment where no trusted moderator or escrow agent is needed; the Bitcoin protocol essentially plays the role of the escrow agent, and release of Alice's deposit happens automatically. I don't know whether this might allow to provide a workable solution to your problem, but it is an interesting new direction and the techniques are very clever. Here is one example of a recent paper looking at this sort of scheme:

Of course, one problem with the Bitcoin-based solution is that everyone has to use Bitcoin and be willing to pay a deposit just to play a game of Diplomacy, which might be a total non-starter in practice (even if they do get the deposit back).

share|improve this answer
    
The other problem is that the commitment scheme might be malleable. $\;$ –  Ricky Demer Jun 20 at 22:24
    
@RickyDemer, yes, that's another possible problem if you do it wrong, but that one is easy to solve with standard methods (there are many standard schemes for non-malleable commitments). The issue I described is the harder one and the core of challenge, as far as I can see. –  D.W. Jun 20 at 22:51
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.