News

Weblinks

Octarine

Files

Dip

Home

Email Diplomacy without a GM

or 'How to play without being cheated'

by

Murky

Introduction

You want to play Diplomacy by Email? However you're a paranoid type and you can't trust the GM not to be in league with one of the players and to reveal your every order to them. Is it possible to play email diplomacy without a GM at all? Is it possible to do this without opening up any new security holes?

In this article I will attempt to show a protocol where players can do just this.

The protocol will address the following problems:

How may power preferences be assigned in a fair manner?
How can players ensure that nobody can learn their moves before they are ready to reveal them?
How can they make sure that every player has committed to a set of moves before any moves are revealed.

It is assumed that each player has access to PGP. Some other program could be used, but this is probably the most widely available. It is also assumed that players have exchanged public keys. You should look at the PGP pages for more information.

I shall address the easier problem of the game mechanics first, i.e. actually writing and processing the orders, only then will I discuss the assigning of powers.

Playing the game

Let us start our hypothetical game.

Negotiations have taken place as usual, and players are ready to write their orders. These orders are written by each player and saved as a text file, and a copy is reproduced below.

In my examples I use filenames which make life easier for me as a web maintainer, ideally the players would use filnames to suit them, i.e. f_s1901m.txt

These are orders for demonstration purposes in
the article 'Email Diplomacy without a GM' which
may be found on

http://www.ftech.net/~monark/dip/files/no_gm.htm
------------------------------------------------
Here are the orders for France in S1901M

F Bre - MAO
A Mar - Spa
A Par - Bur
------------------------------------------------

The player would then apply a hash function to this file. A hash function is a mathematical function which produces a small string from an input. If the input changes slightly then the hash will change dramatically. It is very unlikely, if one has a good hash function, to be able to find two messages which hash to the same thing. Also, it is very hard to go from the hash function to the message. PGP, fortunately has a built in hash function - the hash function is then digitally signed, so that ONLY that player could have produced a given file. This means that players cannot subsequently disown a given hash - and that no player can produce a false set of orders for a given power.

The signed hash should be saved to it's own file.

To produce the signed hash, we issue the following command to PGP:

pgp -sba <filename> -u <username>

i.e.

pgp -sba crypdip1.txt -u mark

For more information about PGP commands type pgp -h

A file is produced called, in my case, crypdip1.asc, which is then sent to all players via a mailing list as an attachment to an email. Each player will save the file in a safe place, it will be needed later.

Here is the signed hash of the above text file.

That player is now committed to a set of orders.

Incidentally, if you are to work through these examples you'll need to add my my public key to your keyring.

Once all players have committed to a set of orders, we can now reveal the orders.

The text file containing the orders are sent as an attachment to the same mailing list as before, and the usual rules of diplomacy are applied in order to process. There will need to be a prearrangement regarding the treatment of typos (e.g. A Bre-MAO instead of F Bre-MAO) and so on. The players would take it in turns to actually process the orders once the orders are revealed.

Obviously, each player would want to check whether the orders were changed at the last minute by someone who has seen the orders of his neighbours - this is where the signed hash comes into play.

The player would save the order file to the same directory as the signed hash and issue the following command.

pgp <hashname> <ordername>

i.e.
pgp crypdip1.asc crypdip1.txt

If the orders have not been changed then you'll see a message which says:

Good signature from user <name>

If there has been a problem then you will see a message which says:

WARNING: Bad signature, doesn't match file contents!

This error will occur if so much as a single character has been added, removed, or changed. Each player can therefore be sure that the orders had not been changed.

In the event of a bad signature the player's units would be deemed to have all been ordered to stand.

There is a flaw with this system, namely that players will get to see who has already written orders. This can be solved by making use of a third party who collects the hashes and publishes them when they are all submitted. Each player would check the hash and publically claim it before any orders are revealed. The third party does not need to be trusted to the same extent as a GM would, at worst they can say that 'Italy has committed to orders'.

Assigning powers

Now we need to discuss how powers are assigned to players without the use of a GM. It is assumed that you are familiar with the method of assigning powers described in the FAQ.

For this protocol, one player is needed to run the protocol, however this player will not be able to influence the protocol.

The first step is for each player to commit to a power preference list, in exactly the same way as they commit to a set of orders. When each is committed the orders are revealed, and checks are performed as above. I'll use the example in the FAQ as a demonstration.

	List	Meaning
1	AE(GI)R	Austria most wanted, then England, Germany/Italy equal preference, if not Russia, if not then this player doesn't care.
2	FRG	France, then Russia, then Germany
3	(EFG)TI(AR)	England/Russia/France equal pref. Then Turkey, then Italy, if not then the remaining two have equal preference
4	E	England - if not this player doesn't care
5		This player has no preference.
6	FRA	France, then Russia, if not Austria, then
7	GRA	Germany, then Russia, if not Austria, then don't care.
8	%REG	This is a reserve player, who wants to play if Russia, England or Germany drops out.

For initial power assignments we can ignore player 8.

This would be resolved as follows :

First, each player gets the first choice where it is unopposed.

Austria: Player 1
England
France
Germany
Italy
Russia
Turkey

2. FRG
3. (EFG)TI(.R)
4. E
5
6. FR
7. GR

France England and Germany are all involved in conflict. We need a way to generate random decision - based on equal fairness to all. In particular, player 3 should not gain an unfair advantage - so if brackets are to be allowed it should be made clear that a weighting is to be applied to compensate for multiple choices.

The manager of the protocol would then send a message saying words to the effect that

'France is now to be decided. Player 2 gets one shot at France, Player 6 gets one shot, and player 3 gets one third of a shot. I.e. Players 2 and 6 get 3 chances each, player 3 gets ine chance. There are seven outcomes.
A number between zero and six inclusive is to be generated, if zero, one or two then player 2 gets France. If three then player 3 gets France, else player six gets France.'

A random number now needs to be generated in order to decide the ownership of France. This means that the player managing the protocol has no way of affecting the result, as the interpretation of the result is decided in advance. The problem becomes 'how can a random number between zero and six inclusive be generated such that everyone is sure that no slight of hand was involved.'

Each player is asked to commit to a number between 0 and 6 - publishing the signed hash as usual. Note that hashes of previous number choices should not be reused, they should be generated afresh each time. Once all are published then the files containing the numbers are revealed.

The numbers are totalled, e.g. 0 + 4 + 3 + 6 + 6 + 2 + 5 = 26.

The result is then divided by, in this case, 7, and the remainder is found. In this case the remainder is 5, and this means that player 6 gets France.

Note, if Player 3 does NOT get France, then they should still only get 1/3 of a shot at England or Germany!

Any individual player can affect the final result, but they cannot predict how they will affect it.

It is possible for a player to cheat by waiting for all other players to reveal their numbers, and then choosing whether or not to reveal their own number. They could claim a disk problem, for instance. Fortunately there is a way to get around this - and it looks complex. Fortunately the initial preparative stages can be automated and the final number revealing stages can only be performed by those who are meant to perform them.

Each player could follow the following protocol, at the very least one player would follow the new protocol, and this player's number would be revealed last of all.

A player would choose their number, and then encrypt it with the public key of all other players (in the order specified below), signing each stage with their own private key. These signatures would all be published.

I.e. if M is the message, Ea(M) means encrypt M with the key belonging to player A. Eab(M) means encrypt the message so that players A or B can decode it. S(M) is a signature - this time it is left attached to the message.

The 'last number message' consists of an encryption of the committed to number, and a series of signatures.

The player, A, first encrypts to players B, C, D and E. The reason for this will be discussed later. The resulting message would be signed, and the signature left attached. Then the player would encrypt to F and G, E and F, D and E, C and B, B and G. At each stage the message would be signed.

I.e. it consists of and email containing the following attachments.

S(Ebg(S(Ebc(S(Ede(S(Eef(S(Efg(S(Ebcde(M))))))))))))
The detached file, S(M)

This may seem complex, but it is a simple matter to write a batch file to do this job, setting the private key password as an environment variable to save time.

Once all other numbers are published, A would reveal message M, and everyone would check it with S(M). It is possible that player A would have two numbers, one for which the hash is encrypted, and one for the hash which is revealed. To save time one would continue to assign other powers - but in the background the following protocol would be followed as a check that the player didn't try something weird by creating two different values for M for each message.

This protocol would also be followed if player A refused to reveal their value of M.

In order to reveal the number choice, all other players must work together to find it. HOWEVER, one player working alone could not stop the decryption.

When the committed code was first sent, all players can check that it was published by player A.

In order to begin to reveal the number, players B or G first decrypt the function Ebg(S(Ebc(S(Ede(S(Eef(S(Efg(S(Ebcde(M))))))))))).

This reveals S(Ebc(S(Ede(S(Eef(S(Efg(S(Ebcde(M)))))))))), which is then published. All players can use the signature to check that B and G did not cheat - and if you want to be very paranoid, B and G can both check upon each other.

Next either B or C can decrypt to produce S(Ede(S(Eef(S(Efg(S(Ebcde(M)))))))), which is published.

This is repeated until either F or G produces S(Ebcde(M)). Any player other than F or G can decrypt this.

M is then published, players B, C, D, and E can vouch that it resulted from the decryption, A signed it and previously published S(M), and so F or G should believe it. The reason for this last stage is so that F and G cannot collude and decide not to reveal the number by claiming a corrupt file - they do not know what the number is. Similarly, once S(Ebcde(M)) is published a conspiracy between players A to E is needed if F and G are to be deceived.

Therefore, the chance of cheating is minimal:

Player A cannot refuse to reveal their number except in the short term - though they can refuse to supply a number or provide an error which would mean that the decryption failed. This would be deemed in advance to their having supplied a zero (for instance).
Any one other player cannot unilaterally have an 'accident' in decryption which means that the message cannot be checked, as each stage can be done be one of two players.
In order to obtain M prematurely requires a conspiracy of 5 from 6 players.
Should the protocol break down and two players relied upon at a given stage fail to decrypt, then player A can still reveal the number as S(M) is already published. After all - this protocol is purely to prevent cheating on the part of A. Once A is committed to the encryption string then they cannot change it once numbers start to be published.

Once this protocol has assigned one power, we now eliminate that power from the lists and take a second pass to assign the next power. This is repeated until all powers are assigned.

So, there you have it, diplomacy without a GM - the hardest thing you have to do is choose the powers - and even this is simple if the last player to reveal a number decides not to cheat - this encryption method is merely to ensure that they can't!

Do let me know if you try it!

Related Pages

Random Power Assignment

Return to the files index.