Blockdraw’s Golle Algorithm: A distributed p2p cryptographic algorithm for generating provably random outcomes

When you play a game on D2W.bet you will find a tab labelled, “Golle Algorithm.” During gameplay, you will see various information shown there in real time (Group formed, secret key exchanged, time stamps, etc…) that provides the player with information that shows how we are generating that random number for that game. For most people that information is currently a bunch of gobbly goop or useless gibberish that the player can’t use. But in reality we are providing you will absolute proof that your game was fair and that the final result was not determined by a central source, but cooperatively as part of a mathematical group. You don’t see that a lot of magic is happening in the browser plugin we developed that is working in a peer-to-peer fashion with you and other players. In this article, we provide a high-level explanation of how we used an algorithm (built into a browser plugin) originally developed for dealing Poker remotely and enhanced it to create the world’s first provably fair and provably random games in the world.

Traditionally, online card-playing games closely mimic what occurs in real-life. The first step is usually to shuffle a deck of cards, then to deal according to the rules of the game, and then play. In real life, the shuffling presents a potential exploit, because dealers can cheat. They can stack the deck, float cards, bottom deal, top deal, and more. There’s no way to prevent this kind of skilled cheating, so the accepted practice is to rotate the dealer to even out any advantage gained.

Online gambling has a similar pitfall. The first step is shuffling the deck, an expensive computer operation. But that gives the dealer an unfair advantage because their program now knows the contents of the deck. Two approaches are common. The first is to treat the dealer as a trusted third party, which fails when they aren’t. The second is to use an encrypted shuffle to hide the cards from the dealer, but this creates even more computational overhead. Ideally, what we want is a way to deal cards that is fair and efficient.

That’s what the Golle algorithm does. In 2005, at the Palo Alto Research Center, Phillippe Golle created a fully decentralized peer-to-peer method to deal cards that is significantly more efficient than extant Mental Poker algorithms. The essential innovation is: rather than shuffle a whole deck up front, we randomly choose a card each time one is needed. The cards are encrypted in such a way that:

• The back of each card uniquely identifies the front. Anyone can be shown all the card backs and verify all the cards are there.
• No one knows which card is which. But since the backs are distinguishable, we can easily tell when cards are different. (or the same, see collisions below)
• A card front can only be revealed when all peers cooperate. This is done by sharing a joint key distributed among the group of peers.

To be even more precise, the Golle algorithm doesn’t select a card from a deck. It chooses a random number between 0 and r-1 from among r = 52 outcomes, and we can interpret the numbers {0, 1, … , r-1} as being distinct cards. Moreover, we can choose any integer r > 1 we want. That means Golle works for all games of chance, not just card games. We can pick a Chinese tile, spin a wheel, flips coins, and roll dice using the same method. This covers all popular casino games, including but not limited to: Baccarat, Blackjack, Poker, PaiGow Poker, PaiGow, Mahjong, Sic Bow, Craps, Roulette, and Slot Machines.

The only subtlety is that there are two different games of chance: independent trials and alphabet depletion. Rolling dice is easy because we don’t need to know the previous rolls. But once a card is dealt or a (unique) tile is chosen, it can’t be used again. Golle calls this handling a collision, and the solution is easy: just randomly deal again. This incurs extra computation when it happens, but since the number of cards dealt is small compared to the deck size, this is a minor issue. Even accounting for collisions the overall cost is still much smaller than whole-deck shuffling: Golle uses 2–4 times less modular exponentiations than the second best runner up, which does full shuffling using mix-networks.

Let’s examine the algorithm in more detail. Golle needs a few supporting pieces to work properly, all of which are well known and have reference implementations:

• Secure communication protocol. The peers need to be able to interact with each other without anyone else eavesdropping. There are a wide variety of equivalent choices here; we’ll be using RFC 4419.
• Homomorphic encryption. If E(r) is the encrypted ciphertext of plaintext r, this means that E(r1) E(r2) = E(r1 + r2). Several options are available; we use El Gamal, which was also chosen in the Golle paper.
• Distributed private key. Let p be the number of players. We need a private key k = k1 + k2 + … + kp jointly held so that each player i only has the part ki. The clear winner here is the Pedersen Protocol. (not to be confused with Chaum-Pedersen, another cryptographic tool)

We must integrate these three features together to reveal a card. We need the entire joint key k to decrypt a card. Each player contributes their piece ki, secretly encrypted into E(ki). Then all the pieces are combined homomorphically

E(k1) E(k2) … E(kp) = E(k1 + k2 + … + kp) = E(k)

into E(k), which is then used to unveil the card. The magic of the algorithm is that all this can be done without anyone ever revealing the ki; only the ciphertexts need be used. For a face up card, everyone securely shares their E(ki) with all other players, so everyone can independently calculate the card. For a card shown only to one player, every other player securely tells them their E(ki), so only they can see what their own card is.

Choosing a card at random uses exactly the same process, with all the ki replaced by ri. Everyone randomly chooses a number ri in {0, 1, … , r-1}, we add the results using homomorphism, and take a final number modulus 52 to ensure we are in the correct range. So altogether, we can only randomly choose the card as a group, and only reveal the cards as a group. Thus, every peer is guaranteed their participation is necessary and consequential.

The Golle algorithm is logically correct but isn’t practically robust. We’ve made significant improvements to account for real-world situations like network congestion and player timeouts, as well as shored up common exploits like false testimony and buffer overruns. We’ve further extended the theory by proving the probability distribution function, which was provided for in the original paper. And, we have made other proprietary improvements that significantly extend the technology. We can prove that as long as there is one honest player (using the algorithm as intended) the deck will be fair (random outcomes are equiprobable). All our improvements and their proofs of correctness will be released in a separate paper.

The Golle algorithm is a perfect match for our intended usage. It enables us to create any casino game of chance in a fair, decentralized way. Even more serendipitously, it generates exactly the information needed to provide airtight verification. This dovetails nicely with our LEAP architecture. To illustrate, the initial step in Golle is generating all the card backs (which are the encryptions E(0), E(1), …, to E(r-1)). Every player sees this set before play begins, so they may verify all cards are present. Thus, it is safe to publicly post to the Performance chain. From that point forward, our application has created a binding commitment to a fair game; there’s no way that we (or any other player) can alter the deck. Similar binding commitments and consensus data are published each card draw and player action, making it possible to reconstruct the entire game, and impossible for anyone (us included) to later deny or spoof what happened. This reconstruction can be done without reference to implementation, which is another reason why the code on the on our blockchains is ultimately superfluous to verification.

In fact, while we currently run Golle on blockchains, Golle itself is a trustless protocol that does not require the use of Blockchains. It is entirely peer-to-peer except for that fact that to ensure security we also provide a secret to the group (Golle requires that at least one group member does not cheat); but that secret does not directly determine the outcome, that is done only with the sum of the groups selected secrets.

What is particularly special for players, for all open face cards/dice (i.e. that is events dice games, roulette, or other games where all results are revealed), Blockdraw can make (and will soon provide) an open source tool that allows you to upload the information (from a JSON file) we provided you in real time (and also stored on our Hyperledger blockchains) to validate that the game was fair (and that we could not know the outcome before anyone else). All of this is because of the nature of Golle (including pieces like the Pederson process described above). And here is the best part, in addition to being able to prove that our games were fair, we can also prove they were random!

As part of our roadmap, we will eventually make the randomness that the user creates open source. Currently, we use OpenSLL to generate randomness for our browser plug-in. But in the next two months, as part of our plan to roll out our Golle Validator, we will open source this piece of the process. What this means is that not only will we be able to prove that our randomness was generated in a decentralized fashion, but we will be able to prove that it was generated randomly.

This is simply a game changer: provably fairness and provable randomness.

No online casino in the world can make that claim, because no other casino created the distributed randomness we do when we use the Golle algorithm.

|Footnote: We started talking about distributed randomness for Blockchain applications in 2017, now in 2019, once again the industry is following our lead with several former ICOs adopting Dfinity’s distributed randomness. We continue to think our P2P Golle approach is superior since it allows us to offer trustless randomness in any cryptocurrency.