Randomness on Blockchain: Theoretical obstacles and practical solutions

Home \ Articles \ Randomness on Blockchain: Theoretical obstacles and practical solutions

Alice and Bob want to play a dice game over the internet with some money at stake. They think, “why pay for an escrow service, when Ethereum is available?”. Is their intuition correct? Is it possible to play dice using an Ethereum smart contract. A short answer would yes, they can. However, what are the hidden costs entailed in their decision? Generating random numbers in a blockchain network is a subtle topic. But before delving into the topic we must first realize the important role random numbers play in our life.

Random numbers are used left and right in every application. To name a few, everytime we connect to applications such as Facebook or Gmail, both our computer and the server generate random numbers. These numbers are a crucial to ensure that our communication with Gmail is secure. Another example would be the gambling industry whose profits rely solely on secure random number generation.

To understand why random number generation is a subtle topic, we must first understand how transactions are added to the blockchain. To add a transaction to the blockchain, the users of the network, which have diverging interest, need agree on the transaction history. To understand how this is achieved and without any loss of generality we will examine how transactions are added to the Bitcoin ledger. Based on that it would be easy to develop an intuition on the theoretical obstacles of random number generation in blockchain network.

According to the Bitcoin protocol (and all the blockchain protocols) each node maintains its own copy of the ledger. When a node wants to interact with the blockchain, it creates a transaction and signs it with her private key, thus proving her identity to the network. Afterwards, it broadcasts the transaction other users of the network it knows. The users that receive the transaction check whether the transaction is valid. For example in the Bitcoin network the nodes will check whether the node making the transaction has sufficient funds. The valid transactions are re-broadcast to the network thus ensuring that the whole network will eventually learn about them (Gossip based communication). Then, miners collect a sufficient number of transactions that float in the network, arrange those transactions in a block and try to append(mine) that block to the blockchain. When a miner appends a new block, she broadcasts the new blockchain to the network. Finally, all the users of the network download the new blockchain and verify that the protocol was followed correctly thus ensuring that the new blockchain is valid.

Now imagine the following scenario: Alice, Bob and Charlie are playing the following game. Alice will let the miner flip a coin and if the result is “heads” she will send 50 Eth to Bob and if it’s “tails” she will send it to “Alice”. Now imagine two different miners working independently that want to add this queer transaction to the blockchain. The miners with high probability will have different results in the coin flipping and as a result will disagree on who is receivers from the transactions. This diverging opinion on the transaction history by the miners will cause eventually the whole network to collapse. This is, from a high level perspective, the reason why random number generations is a subtle topic in blockchain network.

Due to the importance of random numbers, numerous solutions have been offered to alleviate the problem. However, none of the solutions comes for free. This a crucial point that we must consider when designing a system that relies on random numbers. Let’s consider the options available. To find randomness there are the following solutions:

 

  1. Using the hash of the previous block

This method relies on the pseudo-randomness offered by hash functions. In this scheme, Alice tells the miners to produce a random number based on the block they create. When this method is chosen the miner is in an advantageous position to exploit our system. This advantage comes from the fact that the miner is the first one to calculate the random number. Jumping back to the game between Alice, Bob and Charlie. Imagine that Bob is the miner. Then Bob in case he loses the coin-flip, he can choose not to publish the new block. This scenario is known as block-withholding attack in the crypto-community.

 

  1. Using a Randomness-as-a-service provider:

Randomness-as-a-service providers can be separated into to two categories, centralized and decentralized. The centralized ones, are trusted companies that upon request provide you with a random number produced by them in exchange for a small fee. In theory the introduction of a trusted party is deeply contradicting with the core idea of Ethereum, decentralized-applications (dAPPs). However, it is widely used in practice from providers like oraclize. On the other hand, decentralized Randomness-as-a-service providers rely on cryptography to generate random numbers. The idea behind those services are quite complex but in deep down they rely on  Blum’s coin flipping over the telephoneprotocol (I recommend you to look this protocol up, as it relies on simple ideas used in extremely smart manner). The problem with those approach is that they are computationally expensive and this in Ethereum is translated in high transaction costs. Additionally, their security depends a lot on the user. As food for though one should ask themselves the following question “How random the password qwerty is?”.

 

In general, on chain randomness is an open problem. You can visit the Ethereum Github page for other solutions that are not mentioned in this post Ethereum research.

RELATED POSTS