Ballot box with multiple parties. All can read it, or none can read it

Question

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

Answer 1

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.

Answer 2

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:

• Secure Multiparty Computations on Bitcoin. Marcin Andrychowicz, Stefan Dziembowski, Daniel Malinowski, Lukasz Mazurek . IEEE Security & Privacy 2014.

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