Throwing dice remotely

Imagine a group sitting somewhere on the high plains of Wyoming, roughly thirteen thousand years ago. Someone flips a handful of marked pieces of bone into the air. All five land face up, and someone howls in triumph and collects their winnings.

Thirteen thousand years later, we still throw dice for fun. But unlike our ancestors, we cannot always huddle around the fire and watch the results as they happen. We might not be in the same room when throwing the dice, or the die may not even exist as a physical object.

As soon as the players are separated, the problem of cheating appears. Without gravity and entropy as a shared source of randomness, we have two straightforward choices to get our roll results:

• Let the remote player roll and trust the honor system.
• Agree on a trusted external source of randomness.

Neither of these is great. The first one lets any player cheat trivially. The usual solution is to only play with players you trust, but only half of that is under the player's control: if an honest player has a genuine lucky streak, a verified dice roll serves to protect his own reputation against accusations of cheating.

The other is unsatisfying on a psychological level. In the analog world, we take great care to ensure that people are responsible for their own fate. A gameshow host may present a candidate with a choice of three sealed candidates. A D&D player rolls their character's ability checks. A WH40k player rolls their attacks, and their opponent rolls the corresponding defense. So if the server hands out a predetermined random value, the player is demoted to a passive observer.

So to roll dice remotely, we are looking for a protocol with these three properties:

1. It resists adversarial manipulation of the randomness.
2. Every possible outcome could be achieved depending on the players choice.
3. The result is verifiable after the throw.

A history of remote dice rolling

The problem is much older than the internet, and even older than computers.

This section was supposed to be a single paragraph of historical background, but, as usually happens when you look at primary sources, the actual history turns out to be endlessly fascinating.

The Numbers Game

The earliest example I'm aware of is the numbers game, a type of illegal lottery popular in the 19th century USA. Players would bet a small amount of money on a three-digit number, and would win around 600 times their wager if they got it right. The problem, then, was to generate a random three digit number.

Modern lotteries use public ceremonies with special ball drawing machines and results notarized by public officials, but that was hardly a practical solution for an illegal lottery.

So the bookmakers looked for publicly available random numbers. In Harlem, Casper Holstein noticed that the New York Clearing House did literally post a daily random number every day. An employee would write the total of daily clearances between member banks on a chalk board at 10 am. The winning number was determined by combining the second and third digits from the bank clearings with the third digit from the Federal Reserve Bank balance.

Casper Holstein, 1926. The portrait ran in Opportunity magazine after he endowed the Holstein Prizes for its annual writers' contest; the numbers game paid for them. Via Wikimedia Commons, public domain.

By chosing the number in this way, Holstein could guarantee a fair draw and he quickly displaced the previous operators who were using spinning wheels in their own headquarters that could be easily rigged.

In todays words, the clearing house served as a public randomness beacon. It did not do so willingly, however, and from 1931 it only published rounded totals to combat the widespread use of its numbers in illegal gambling.

The stock market method

The first direct analogue emerges a few decades later from Catonsville, Maryland. There, on a hill overlooking the Avalon neighborhoud, Charles S. Roberts founds The Avalon Game Company.

They focused on complex, rule-heavy war games featuring historical scenarios and quickly grew on the back of a number of successful releases.

Since wargaming was a niche hobby, players turned to play-by-mail schemes to be able to find opponents. Avalon Hill supported this by selling official play-by-mail kits of their games that allowed wargames across the country to duel each other.

Unlike existing play-by-mail games like correspondence chess, Avalon Hill games depended on random dice rolls to resolve the results of combat each turn.

So they came up with the following scheme: Players would write down which unit was attacking whom this turn, and for every attack they would choose one stock on the NYSE and a target date.

The receiver could then resolve the dice rolls by buying a newspaper on that date and using the last digit of the stock’s sales-in-hundreds figure as the result.

Reading through early issues of Avalon Hill's wargaming magazine The General, it's striking how prominent the problem is. Almost every issue has some proposals or improvements for remote random number generation protocols.

The very first issue already has a sophisticated example: Contest No. 1 hands the reader a multiple-battle situation from Afrika Korps, to be divided into no more than five attacks on a printed Operations Sheet. Each reader would choose a stock for each attack. The editors then resolved every entrant's combat themselves, and the ten readers whose attacks did best would win a free game (The General, Vol. 1 No. 1, 1 May 1964, p. 5). It is a remote dice roll run at the scale of a whole readership, and the magazine is explicit that it is nothing new: "Combat will be resolved exactly as in the Afrika Korps Play-by-Mail kit." Each battle's result came from "the last digit of the Sales-in-Hundreds column" for the stock, read against a combat results table built for base ten instead of the usual six-sided dice.

Contest No. 1, The General, Vol. 1 No. 1, 1 May 1964, p. 5. The Afrika Korps position readers had to break down into no more than five attacks, with the resolution rules printed underneath it: the closing transactions of Monday, June 1, 1964, read against the special Play-by-Mail Combat Results Table.

The entry blank on the next page lays the protocol out as a table:

Entry blank, The General, Vol. 1 No. 1, 1 May 1964, p. 6. Column (d) is the player's contribution, chosen from the fourteen stocks listed at the foot of the form. Column (e) is the beacon, pre-printed and identical for every entrant. Columns (g) and (h) belong to the house, and the instruction at the top says so: "FILL IN COLUMNS (a), (b), (c) and (d) only".

The tables were being retrofitted as they went. In March 1965 the magazine printed a "Play-by-Mail Table for Afrika Korps" (Vol. 1 No. 6, p. 7), because a rules revision had added a German supply roll and a postal game had no die to roll it with. On the board the Axis player rolls once a turn on a Supply Table (Afrika Korps rules, 12.2); by post he picks a stock for supplies exactly as he would for an attack, and its last digit decides whether the convoy arrives. The table is instructive, because it shows a weakness of the method: Even if the stock method produced uniform random digits from 0–9, the original game tables were made for six-sided dice:

Only the middle row converts exactly. The postal Axis player loses fewer convoys than he should through the summer of 1941 and more of them from December on. It is a small distortion, but it is baked into every game played by mail, and it is there because ten is not divisible by six.

Four months later, Contest #8 uses a reduced version of the same scheme: You are in a Mercedes on the last lap at Le Mans, and to win you must take every corner one gear above specification. The Racing Plan lists six corners, and for each one "you must select the stock that will act as the die roll".

Contest #8, The General, Vol. 2 No. 2, July 1965, p. 7. Everything the protocol needs is on the page: the rule, the beacon and the date to read it on, the table that turns a digit into an outcome, the ten stocks to choose between, and a form whose third column is reserved for the house — "Result (AH use only)".

Here, the whole strategic aspect of the earlier contest is removed. It is essentially a raffle, but one that goes to great lengths to give agency to the reader instead of just choosing a random entry.

The strategic form came back a year later. Contest No. 13 sets up a Guadalcanal position in which the Marines must clear three Japanese units from Mt. Austen, and the Operations Sheet "lists the battles exactly as they are to be fought": three attacks, each resolved by a stock the reader picks from a group of fifteen (The General, Vol. 3 No. 1, May 1966, p. 15). Two details stand out. The group is made up of names like Chrysler, Ford, General Electric and IBM, issues heavy enough to be printed in any paper's abbreviated listing, which is the same reasoning the kits give for recommending familiar stocks. And the combat table is being bent to fit the postal game once more: "Because Jap Units have no retreat routes, retreats will be considered eliminations instead."

Contest No. 13, The General, Vol. 3 No. 1, May 1966, p. 15. The Guadalcanal position, the fifteen stocks to choose from, and an Operations Sheet with the three battles pre-printed. The judges read the last digit of the sales-in-hundreds column for Monday, June 13, 1966 against the Guadalcanal Play-by-Mail casualty table.

The weaknesses of the method were apparent to the gamers of the time. For example, Volume 5 has a list of error handling routines that the players should follow in case the method fails (The General, Vol. 5 No. 4, November–December 1968, p. 9).

If the closing transaction date is missing, use the day after the postmark on the attacker's envelope, and "the entire stock clipping and the attackers postmarked envelope must be sent back to him" — the evidence travels with the dispute. If the newspaper does not list the stock that day, or the attacker forgot to name one at all, both players fall back on a reserve agreed before the game began: "each player selects 5 stocks and sends the list to his opponent. These stocks are not to be used during regular turns so that they may be used in these situations. List must be used in its original order."

A keystream from two letters

Another reader in 1968 tackled the problem of generating larger numbers of random digits. Capt. Richard R. Nichols had been playing Guadalcanal by post, where "the long range of artillery can be difficult to solve" because an artillery barrage needs one random result per shot, and there could be tens of shots per turn. His fix (p. 10) is to name two letters instead — one for the attacker's fire and one for the defender's, "example: A and D" — and then read a stream out of the newspaper. The defender turns to the A section of the stock tables, runs down the sales-in-hundreds column and strings the digits together until he has one per shot. Nine shots, nine digits.

In today's vocabulary, Capt. Nichols proposed a keystream generator, a short seed expanded into an arbitrarily long run of digits. From a two-letter seed, we get as many random digits as the barrage happens to need.

Unnoticed by him his underlying source of randomness is not uniformly distributed. The digits come from the decimal spellings of trading volumes, and the leading digit of a naturally occurring quantity is not uniform: small ones dominate, which is Benford's law. Most figures in a sales-in-hundreds column are only one or two digits long, so most of the stream consists of leading digits, and the stream comes out heavy with 1s. Nichols prints his own worked example — 1, 2, 4, 1, 3, 1, 7, 1, 4 — and four of those nine shots are 1s. Whatever a 1 means on the artillery table, a postal barrage delivers it a good deal more often than the board intends.

The base-six fix

Avalon Hill eventually addressed the ten-versus-six mismatch in the kits themselves. Rather than keep printing a special base-ten combat results table for every title, the later kits told the player to fold the digit down to a six-sided range and then use the ordinary table off the board. The Stalingrad kit spells out the arithmetic under the heading Base 6: "transform the Sales-in-Hundreds number to a base six number by dividing the Sales-in-Hundreds number by 6. The remainder is the new base 6 number. If 6 divides evenly into the Sales-in-Hundreds number, the 0 remainder is treated as a 6." Its worked example divides 832 by six, keeps the remainder of four, and notes that "a base 6 number of 4 which in a 4-1 attack in AFRIKA KORPS means Defender Back 2."

The conversion is what let the kits drop the custom tables: a remainder in the range one to six can be read against the combat results table already printed on the board, so the postal game and the face-to-face game finally resolve combat on the same odds. The kits also keep steering the player toward heavily traded issues — "we recommend that you pick the more familiar ones that would be listed even in the most abbreviated Stock Market report" — which is put as a point about newspaper coverage, and happens to be the condition under which the conversion behaves.

Stock-based random streams

Six years later, in 1974, Tom Oleson proposes a variant of the scheme that does away with the base conversion altogether (The General, Vol. 11 No. 4, November–December 1974, p. 28).

Instead the player names a rank. A day or two before mailing, he picks a slot on the paper's most-active list — ninth most active, say — and says so in his turn. On the chosen day both players look up which stock actually landed in that slot, find it in the full alphabetical listings, and rule a line under it and under every sixth stock after that. Each block of six is one die roll, and the roll is the position within the block of the stock with the highest closing price. First stock highest means a 1, sixth means a 6.

Oleson's worked example, The General, Vol. 11 No. 4, November–December 1974, p. 28. The clipping is the New York Stock Exchange listing from the Baltimore Sun of Thursday, October 17, 1974. On the right, Grand Union sits in the ninth slot of the 15-most-active list — the rank Oleson named before mailing his turn. On the left, Grand Union is found again in the alphabetical listing and a line is ruled under it and under every sixth stock after that; the digit written beside each block is the position of its highest closing price. The first block runs GrantW–GtNNek, where Gt N Nek closes at 40⅞ in sixth position, so the first roll is a 6.

This avoids folding or truncating a decimal digit: the six faces come from six positions, and if the six prices are equally likely to fall in any order then the highest is equally likely to sit in any slot. Under that assumption, the construction gets a flat d6 out of the newspaper rather than an approximation of one. He even includes a discussion of seed quality: "don't pick above the, say, 4th most active. Some news development might make the top stock somewhat predictable for a few days, but surely no one can predict the 5th most-active, or the 7th."

Compared to the original scheme, the precise layout of the stock table now matters, so it is important that both players have newspapers with exactly the same stocks in the same order. Since that can be difficult for two players who are a long distance apart, Oleson recommends sending a photocopy of the paper along so the other player is able to verify the results.

While this scheme is pretty solid, it suffers from a similar issue as Nichols' proposal above: The underlying NYSE stock listings are not a good source of randomness. In this case, his example has two types of Houston First Financial Group stocks with different dividends that are listed right below each other. Their prices are correlated, in the sense that a stock with lower dividends should have a lower price, so whenever these two share the same group the die result will be systematically skewed.

Oleson also nicely explains why anyone would bother with all this effort to get verifiable random numbers: "PBM can be done on the honor system, but even if you trust your opponent, you wonder how he can keep trusting you when you get a run of luck."

Entropy mixing by mail

While the attempts above are refinements of the NYSE-based scheme, there is another line of work that tries to avoid the centralized authority completely. In September 1966 a player named Tony Leal proposed the "New PBM System" (The General, Vol. 3 No. 3, September 1966, p. 12):

The main advantage that this system has over the current one is that the base-6 combat results tables may be used instead of the base-10 ones. That is, it is possible to simulate the roll of the die (without any cheating) and thus eliminate the use of newspapers.

Both players agreed in advance on fixed days of the month on which all correspondence would be sent, the gap between those days chosen to match "the amount of time required for mail delivery from one player to the other". On each such day both mailed a list of numbers from one to six, one per battle, in an agreed order. When the lists arrived, "the numbers, in order, are added together modulo 6. This produces a 'die roll'."

Neither contribution determined the roll by itself, and neither player could choose after seeing the other's list. Two envelopes crossing in the post hid the numbers while they travelled, and the agreed mailing dates meant neither player could simply wait.

It also had a bug, which Leal wrote down himself. The defender cannot know how many battles the attacker will declare, so his list may run short, and the suggested remedy was "starting the list over again from the beginning". By then the attacker holds the defender's entire list. Once it repeats he knows every remaining contribution, and can pick his own numbers to produce whichever face he likes. The article's third claimed advantage — "There is no possibility of cheating" — holds only while the randomness lasts.

What the scheme does guarantee is worth stating precisely, because it is stronger than it looks. Adding modulo 6 is a group operation, and on a group the uniform distribution absorbs: if either contribution is uniform and independent of the other, the sum is uniform, no matter how the other player chose.¹ A player who picks his own numbers uniformly at random is therefore safe against an opponent who sends the same digit every time. He does not need his opponent to be fair, only himself. That is the property worth having, and it is exactly what the printed addition table is for — any combining table that is not a Latin square gives it away.

By 1968 the scheme had a name and a small maintenance record. Richard C. Giberson's "Jutland Play-by-Mail" (The General, Vol. 5 No. 4, November–December 1968, p. 5) recommends "the mod 6 method", credits Leal by issue, and adds two patches: rolls that can repeat need spare randomness allocated up front — "a second number might be listed for each battle in case a '6' is rolled" — and a contribution must not be reused for two different rolls, so "players should list offensive and defensive numbers" separately.

The weakness nobody was looking for is not about cheating at all. The mod 6 method says nothing about where a player's six numbers are supposed to come from, and "it makes no difference how the numbers are chosen" is a claim about manipulation, not about distribution. Feed the scheme a skewed source and the skew survives the arithmetic.

Skewed sources were exactly what the hobby had lying around. For players staying with stocks, Giberson also gives a conversion from a last digit to a die result — "1-6 as is, 7 = 1, 8 = 2, 9 = 5, and 0 = 4" — and it is a fair picture of what base ten looks like after it has been squeezed into six faces: ten digits will not divide evenly, so four of the faces come up twice as often as the other two.

A player who reached for a digit and folded it that way, rather than for the die in the game box, would be contributing this:

The arithmetic is doing real work even when it is fed badly: a skew of nearly seven points on each side comes out as one and a third on the sum, because errors like these multiply rather than accumulate. Adding two bad dice gives you a much better die. But it never quite goes away, and the reason is the absorbing property read backwards. Nothing inside the protocol manufactures uniformity. If neither player brings any, a uniform result is not guaranteed.

The clean repair is to reject instead of fold: take a digit, discard it if it is 0, 7, 8 or 9, and use the next one. If the original digits are uniform, the six surviving outcomes are exactly equal, and Leal’s sum then lands exactly flat. The obvious objection is that a postal player cannot keep asking the newspaper for another digit — but he never needed the newspaper. His contribution is his own private number, chosen at his own desk, and there is a die in the game box. The base-ten problem belongs to the beacon, and the whole point of the mod 6 method was that it had stopped using one. The skew only gets in if a player carries a habit across from the old scheme.

Rejection also works without interaction in a shared stream of uniform decimal digits: both players skip every 0, 7, 8 and 9 and read on until they have enough results. Rejecting 40% of the digits means reading about 67% more digits on average. But this does not repair Nichols' stream: if its input digits are biased, the surviving digits need not be equally likely either. Reading further down the newspaper solves a shortage of digits, not a bias in their distribution.

International dice rolling

Wargaming was not limited to the United States. In March 1966, "in response to numerous requests from Avalon Hill fans in the U.S.A. and abroad", a group founded the Intercontinental A.H. Kriegspiel Society (The General, Vol. 2 No. 6, March 1966, p. 1), recruiting "especially those living in foreign countries".

However, this presented a logistical problem. An Avalon Hill enthusiast living in rural Finland might have some trouble obtaining the NYSE stock results on some random weekday. The society recognized the difficulty right in the very first sentence of their first announcement: "A Battle Results Relay Station has been established for international games, where the stock results method would be impractical."

Two months later, in the next issue, the society announced a successor: "ICRK Replaces Stock System" (The General, Vol. 3 No. 1, May 1966, p. 4). What replaces the beacon is a pre-shared table, mailed out by AHIKS itself. The International Combat Resolution Key was a sheet of four hundred pre-rolled results in lettered columns and numbered rows, generated by a neutral officer of the society and issued per match, bound to one opponent and one game. Each of the four hundred numbers was good for exactly one roll, and the players requested a fresh sheet when the old one ran low.

Each round, the attacker would choose a column, say B, and then use values B1, B2, etc. for their dice rolls. When the B column was used up, he would randomly choose some other column to continue.

The defender would then look up the values of the B column on his side of the sheet, use them to calculate the results, then cut that column off the sheet and mail the paper itself back along with his next turn (AHIKS).

As the society writes, "this eliminates the need for stock listings and saves much time and inconvenience."

One flaw that this scheme has is that the defender knows the possible values in plain text, so if he saw that for example all remaining columns started with a 6 he would know for sure what the result of the next dice roll of the other player would be and could in theory use that information to gain some advantage on his turn.

Playing in real time

The schemes so far have been using letters to exchange information. In many, the delay of the post office is even an essential part of the protocol. But even before the internet, modern technologies were used to facilitate remote gaming.

In 1966, C. Norman Peacor proposes a novel "Play-by-Air" protocol that is aimed at readers who are also licensed radio amateurs. He opens by observing that neither the die nor the stock market approach is feasible in this situation (The General, Vol. 2 No. 6, March 1966, p. 7). His replacement is this. Group the attacks into threes. Then, starting with the defender, the two players alternate digit for digit until each has spoken a four-digit number. Multiply the two numbers together — "and don't forget to agree on the answer" — and read off the fourth, fifth and sixth digits from the right as the results of the three attacks.

The security of this scheme rests entirely on the operators being unable to perform 8-digit mental arithmetic fast enough to choose the last number in an advantageous manner. There were probably people alive in 1966 that could have broken the scheme, like the prodigious Wim Klein, but for whatever reason there seems to be little overlap with the wargaming-enthusiast ham radio operator community.

Maybe with a bit more mainstream appeal, a "Play-by-Phone" routine from William J. M. Gilbert (pp. 9–10) finds a beacon that answers instantly. The attacker names a person; the defender immediately names a number between one and ten; that is repeated for each battle, and then both hang up. Only afterwards does the defender look the name up in "a previously agreed upon phone book", add the last digit of the phone number to the last digit of the number he quoted, and keep the last digit of the sum.

Another reader took it apart in the next issue. David J. Simecek had been playing by phone for years before the routine was published, and he thinks steps 3 to 5 "make it much harder then necessary" (The General, Vol. 3 No. 1, May 1966, p. 4). His version drops the arithmetic entirely. One player calls off a page number, "followed without pause by the other party naming a column and item number"; each notes the numbers, once per combat. Afterwards both look up the coordinates in the book — columns left to right, items top to bottom — and take the last digit of whatever number is sitting there.

So the phone book stops being a lookup keyed by a name and becomes what it physically is: a few hundred shared pages of cheap random digits. And it is quick: "so fast that in the early moves of Afrika Korps more than one round can be played in a single conversation."

All three schemes replace the slowness of the USPS by finding something else that is also slow. From today's perspective, we can already see how that will lead to problems once it is computers that exchange the random numbers.

Outside the United States

It is surprisingly hard to find traces of remote dice-rolling outside the AHIKS orbit.

In the UK, there was a healthy PBM community from the mid-1970s, but it focused mostly on GM-led games where there was a trusted central authority that would also roll the dice.

There are scattered reports of German wargamers playing both homegrown and US-imported combat simulation games in a peer-to-peer style, but I haven't been able to dig up any mention of how they generated random digits.

For the Soviet Union and the Eastern bloc I wasn't even able to confirm that they had any play-by-mail gaming community at all, apart from the hugely popular correspondence chess which doesn't contain any randomness.

If anyone has that obscure stack of 1970s European gaming magazines in their attic, now would probably be a good time to digitize and preserve them before they get lost to history forever.

The age of computers

The medium that would take the delay away was being assembled a few hundred miles up the coast. Electronic mail already existed in 1965, in the sense that users of MIT's Compatible Time-Sharing System could leave messages in each other's mailboxes. In 1971 Ray Tomlinson, at Bolt Beranek and Newman in Cambridge, bolted a file-transfer program onto the local message program so that a message could be dropped into a mailbox on a different machine. Within two years a study found that mail made up around three quarters of the traffic on that network.

However, while email existed, computers were still expensive pieces of technology reserved for large businesses and universities, and there was no nationwide network to move emails from one pocket to the other. This only started to change in the 1980s. From 1984 the hobbyist FidoNet moved messages between bulletin boards over long-distance phone calls at night, growing from a hundred nodes to several thousand by the end of the decade.

The General welcomed the new medium enthusiastically. Writing in the second week of December 1989, the magazine's AREA columnist notes that "the advantage of PBEM in comparison to PBM is the dramatic reduction in the transit time for moves" and is looking for reports from gamers who have already played games by email (Vol. 26 No. 1, p. 24).

One year later, Russ Gifford argues "The Case for PBEM" and is already part of an established online wargaming community consisting of hundreds of players. He acknowledges that using email makes cheating easier, but cost and convenience are more important: "in Email, your move is in your opponent's mailbox as soon as you send it!" (pp. 50–51).

Of course, it was not lost on the players that the sophisticated dice-rolling schemes did not translate to e-mail. However, the speed and convenience of the new medium were ultimately more important:

We make use of an honor system for resolving die and dice rolls. Worried about someone cheating? Sure, it would be easy. They can do so in most of the other systems I've tried too, so why work so hard to prevent the unpreventable? If you play with someone you think might be cheating, your option is simple: don't play with them again.

Eventually, the use of dice servers seems to have become the method of choice for generating fair dice rolls.

For example, the rec.games.pbm FAQ answered "How can I generate trustable dice rolls?" by recommending the dice@danpost4.uni-c.dk server, which would roll for both players and mail each of them the result, keeping a permanent record for later verification (rec.games.pbm FAQ).

Similarly, in a post on 2 May 1989 a player on rec.games.pbm asks how remote opponents could convince one another that their dice were honest. The first reply suggests some sort of passthrough email proxy that parses the email body for expressions like {2d6+1} and replaces them with the result of the roll. ²

The same thread also suggests the serverless, cryptographic replacement for Leal's scheme: Both players send each other encrypted versions of their dice rolls, and then in a second step exchange the encryption keys. The post even contains C code implementing the idea. However, as far as I can tell this never gained widespread acceptance, likely because adding a second round of communication to every turn negates a lot of the convenience of playing via e-mail.

Multiplayer dice-rolling

On 25 September 1993 Mayan Moudgill was asking a multiplayer variant of the question on rec.games.pbm:

A group of people are playing a game over e-mail. They need to throw dice every turn. Unfortunately, they can't find somebody "trustworthy" to do it for them. So, how can they throw dice[?]

Again, the group quickly had an answer for a suitable cryptographic protocol:

Each player generates a large random number, computes the MD5 hash, and then discloses the hash to the other players. Each player is now committed to his number, since no ther number will produce the same hash. Then each player reveals his number to the others, the result is summed [...] and the result mod 6 is the die roll.

I have not found an implementation of this proposal; dice servers offered a more convenient solution.

Hidden-information games

Unsurprisingly, AHIKS was also interested in the topic. The AHIKS Europe newsletter carried an article in 1994 about "information on the use of cryptographic software in PBEM". ³

It starts from the assumption that a trustworthy dice server exists and is used by both players, and then explains how to use PGP to extend that for games requiring more advanced hidden information: For example, in the game 'The Emperor Returns' one player maintains the current position of Napoleon as hidden information. To prevent him from secretly switching that position, he encrypts his initial game state and any subsequent updates using PGP and sends those to the opponent. After the game, he sends the private key and the opponent can verify the position was correctly calculated during the game. He also notes that for some multiplayer games this can be used to have one player participate both as GM and player, by publicly committing to his moves and sending them PGP-encrypted to the other players before receiving theirs and evaluating all moves as the GM.

Remote Card Games

The next innovations seems to have come from trading card games.

In April 1996 Philip G. Meyers posted "A SYSTEM FOR PLAYING MAGIC BY EMAIL WITH NO REFEREE" to rec.games.pbm. ⁴ Each player shuffles and numbers his own deck at his own desk, then sends the opponent an encoded version of the list; the order is fixed before play and can be checked against the encoding once the game is over.

The idea is correct, but it suffers from a lack of suitable cryptographic primitives available to the author in BASIC: The encoding is a short routine, and it only obfuscates. Anyone willing to read the listing can invert it and recover the supposedly hidden deck order.

Netrunner players were doing something similar by the middle of 1997. Pierre Savoie, writing to rec.games.trading-cards.misc, describes exchanging encrypted card lists at the start of a game and decrypting them at the end, ⁵ so that neither player can quietly reorder a deck once he knows what he needs to draw. That is the chess adjournment envelope with a cipher for a flap: a commitment to hidden information rather than a jointly generated shuffle, and the surviving post does not say what the cipher was.

The same author casually mentions that he also has a method to roll dice fairly, with no cheating possible, over email, using encrypted numbers (rec.games.trading-cards.misc, 24 June 1997), but no specifics of the protocol seem to have survived.

Enter cryptography

While all of this was going on, the nascent field of cryptography started to develop and approach these same questions from a mathematical perspective. In 1979 Shamir, Rivest and Adleman circulated Mental Poker, which asks whether two players who do not trust each other, and who have no cards, no dealer and nothing but a telephone line, can play a fair hand. Their construction encrypts the deck under a cipher that commutes: Alice encrypts the fifty-two cards under her key and shuffles, Bob encrypts them again under his and shuffles, and because the two encryptions can be peeled off in either order, a card can be handed to one player and opened without the other learning what it was.

Manuel Blum reduced the same idea to its core two years later, in Coin flipping by telephone: Alice and Bob have divorced, moved to different cities, and must decide who keeps the car. At an impasse for rational arguments, they agree to flip a coin. But Alice cannot simply flip and report the result, and Bob cannot be trusted to call it honestly after hearing it. Blum's answer is to make Alice publish a value that is derived from her choice but does not reveal it — a commitment — let Bob guess, and only then have Alice open it, with the arithmetic of the commitment making it infeasible for her to open it two ways.

Despite what one might expect, there seems to have been very little interaction between the cryptographers and the wargaming community. Neither the PBM schemes nor the dice server authors cited cryptographic papers, and the cryptographers did not point out the use of their schemes for PBM gaming.

The earliest examples of explicit cross-pollination I could find are in 2005, when a user in Matrix Games' World in Flames forum pointed out that Bruce Schneier's book Applied Cryptography contains chapters that might be useful for designing a secure PBEM commitment scheme (forum discussion).

The sealed table

Now, let's move from history to the present.

Remember, we want to be able to roll a die remotely.

The pragmatic choice would be a dice-rolling server, but this would leave the full agency with the server: It's not the user that rolls a die, the server does it and just notifies the user of the result.

So, the first instinct is to solve it like this:

A die can be treated as a lookup table. For a d6, the face list is:

[1, 2, 3, 4, 5, 6]

Choosing a random position in this table is equivalent to rolling the die.

Of course the user must not be able to predict which position corresponds to which outcome, so the following protocol is used to mask them:

The session is necessary to prevent replay attacks: The server must not allow the roll to be evaluated multiple times, to prevent the player from trying different indices until they get a result they like.

However, as we'll see below, it's not yet quite a usable solution.

Why sending tables does not scale

Games such as Warhammer 40,000 routinely ask for large pools of dice. A roll of 40d6 requires forty separately shuffled tables. Bigger attacks and bulk resolution can require still more. And of course, for a computer it is no problem to roll, say, 512d4294967296. We should not make such throws impractical by requiring gigabytes of encrypted tables to cross the network.

Another problem turns up when the number of dice throws becomes variable. For example, the popular solo dungeoneering game Four Against Darkness uses the concept of "exploding dice", where on a roll of 6 you may re-roll and add the result to the previous roll. This process continues as long as you keep throwing sixes.

There are only two obvious workarounds:

• Pre-allocate a large pile of extra tables. Most will be wasted, and whatever limit was chosen becomes an accidental rule when a sufficiently long chain of explosions reaches it.
• Stop halfway through and issue another sealed-table challenge. That adds a fresh commitment and another network round trip to what players experience as one roll.

All in all, a rather annoying situation.

Protocol, second attempt

For the solution, we need to take one step back.

To pick a random position in a table, we don't need to send the whole table over the network. It is enough if the other side can construct the same table.

But if the other side gets an exact recipe for constructing the table, how can we prevent it from cheating when choosing the position in the table?

By committing to a random permutation that will be used to shuffle the table.

More specifically, the server creates a seed for a chosen pseudorandom number generator (PRNG) and publishes a cryptographic commitment to it. The player chooses positions for all result tables that occur when evaluating the desired dice roll. Then the server reveals the seed, and the output of the PRNG stream is used to compute the permutation applied to each table. Both player and server can then compute the result of the dice roll locally.

The commitment stays the same size whether the roll contains one d20, forty d6s, or a hundred d8s. No table crosses the network.

One nice property is that, like in Leal's 1966 scheme, neither side needs to trust the other’s RNG: as long as either side can generate true random values, the other side can produce broken or predictable randomness and the resulting distribution will still be uniformly random.

That is particularly relevant when the flow is initiated by the server itself, for example an RPG server that wants to delegate an attack roll to the player. A client could let the player choose a hidden position, for example by presenting a UI with twenty hidden panels that get revealed after the player chooses.

Protocol, the third

The above looks good until we get back to the exploding dice. On the server side, everything works nicely: each seed defines a stream of permutations, so whenever a six is rolled we generate one more for the next roll. However, the client has the problem that they do not know how many rolls will be performed in advance, so they don't know how many indices to send. Any finite number has some chance of being insufficient. A simple scheme like "just repeat the same index while rolling" would allow the server to brute force a seed that has the same value at that index position for however many turns it desires the roll to continue. Even an approach like "use the next random value from the RNG stream" is susceptible to the same attack, because the index is ultimately just a mod 6 value so it's still easy for the server to brute force a sequence that has the same index and dice value for these positions.

The solution is to require the player to supply fresh entropy along with the chosen indices. Then each index can be viewed as the initial value of an index sequence, a sequence of length one for the default case, or a longer sequence for an exploding die.

The only downside is that the player cannot explicitly choose an index for subsequent dice, but that seems like an acceptable trade-off since the overall sequence is still determined by their initial choice.

A player who wants full control can of course always get that back by manually rolling a single d6 and manually simulating an exploding die by re-rolling as needed.

A dice-rolling language

Player and server also need to agree on the exact order and table shape of the rolls to be performed.

This was supposed to be the meat of the article, but the history turned out to be too good to cut, so here is the short version.

The notation is already the thing the two sides agreed to roll, so making it also the thing that numbers the tables costs nothing: walk the expression from left to right, and every die it asks for takes the next permutation from the seed and the next index from the player. The shape of each table is not a choice either — a die's table is its face list, 1..N for a standard die and the literal list for a custom one. A 1d{1,1,6} is a table of three entries with a repeat in it, and since a permutation only moves entries around, the weighting survives being shuffled.

What is left is bookkeeping, and the bookkeeping is the entire protocol surface. Both sides have to agree on which die draws which index, because a disagreement about that produces a mismatch indistinguishable from a lie. So the rules have to be written down even where they look obvious:

• Dice are consumed in evaluation order, left to right. A program of several ;-separated pipelines consumes them pipeline by pipeline — including a pipeline ending in discard, which still rolls and therefore still spends indices even though it shows nothing.
• Every die that is rolled draws exactly one index, including the dice that are then thrown away: the losing repetition of an advantage, the three dice max(4d6, 1) does not keep, the sub-cutoff dice of a threshold, subtracted dice. Flat modifiers draw nothing, because nothing is rolled.
• Within one pool, dice are consumed a size at a time — standard sizes ascending, then custom face-list dice in the order the notation introduces them — and in count order within a size. So 2d20 + 3d6 spends its three d6 indices before its two d20 ones, and written order is not consumption order.
• advantage and disadvantage consume whole rolls, one repetition after another. Which repetition won is decided afterwards and changes nothing about what was spent.
• Explosions consume in waves rather than depth first. The pool is rolled; every die showing its maximum face adds one die to the next wave; that wave is rolled out in full before any dice it in turn produces. A chain therefore does not occupy a contiguous run of indices. This is worth stating precisely because the intuitive reading — an exploding die immediately followed by its own extras — is a different consumption order, and it verifies to a different result rather than to an error.
• The explosion cap is part of the protocol rather than an implementation detail. A thousand extra dice per die size ends the chain, and a verifier that stops anywhere else disagrees with the server on precisely the rolls players find most memorable.
• reroll spends a full first roll, then one further index per kept die, in the order those dice were rolled.
• Dice that exist only because of what was rolled — an explosion wave's extras, a reroll's replacements — take their index from the player's seed rather than from the submitted list. That is what keeps the submitted indices lined up with the dice the notation actually names, instead of letting a later click land on an extra die that appeared in front of it.
• Nested wrappers evaluate inside out. explode(advantage(2d6)) spends both advantage repetitions first, then whatever the explosion adds to the winner.
• A saved reference draws nothing: save freezes its result, so the reference replays the same dice for free. save_pool binds only the definition, so every reference re-rolls it and draws a fresh set of indices — twice over in atk + atk.
• A check consumes its left side and then its right. A product consumes its count before the body that count repeats.
• An index outside the table is reduced modulo the table size rather than rejected. The player's index needs no particular distribution — that is what the absorbing property is for — so strictness protects nothing here, and a strict server turns a harmless client bug into a failed roll.

None of that is interesting, which is the point. It is Pollock's ruling from 1968 — "List must be used in its original order" — rewritten for an expression tree, and it is the same discipline a precommitted sequence needs: fixing the numbers is not enough if a player can later choose which event receives each number.

Try it out

Try rolling dice yourself at roll.nerdwolke.de.