Verifiable Randomness

Why Decentralized RNG Has Never Been Achieved

Feb 06, 2023

In Poker Secured Web2, It Solves Web3, we discussed how the decades-old Mental Poker problem unlocks the keys to decentralized data, which eliminates oracles and secures bridges. In part two, we’re going to discuss truly verifiable randomness and why no has solved it. That is, until Ontropy was born and created on-chain entropy.

Skip to the bottom to read our poker analogy of Dynamic User Entropy, history’s first truly verifiable randomness protocol. Our explanations will be simple and non-technical today. In part three, the finale, we’ll talk math and cryptography!

Source: Templeton

Why is Verifiable Randomness So Important?

According to Bonneau and Nikolaenko of A16Z,

“In some applications, such as gambling and multiplayer games, randomness adds fun. In other applications, randomness provides a fair way to allocate non-divisible resources, ranging from green cards, to the assignment of circuit court judges to cases, to seeding in sports tournaments. Traditionally, we’ve relied on trusted authorities to generate randomness for these protocols, but in the web3 world, we’ll need to do better.”

Ontropy was invented to bring verifiable randomness to poker. So, our first use cases of a verifiable randomness function (VRF) are targeted to gaming. But applications stretch much farther. One of our clients, for instance, needs a VRF for custom NFT generation. Another, for providing a wheel of discount coupons when checking out of their marketplace.

The most significant use case of our VRF is security. This currently represents a quarter of our business, from encryption services to secure seed phrase generation (which is currently centralized) to the consensus mechanisms of several L1s and L2s.

With consensus mechanisms, like Proof of Stake, many are aware of the possibility of a 51% attack. Yet, even Vitalk Buterin argued that this threshold could be reduced to 36% by compromising the pseudorandom selection of validators. Even more, Proof of Stake blockchains can be damaged and entirely controlled by an even lower percentage over time. Ethereum admits that

“One of the nodes on the network is the block proposer for the current slot, having previously been selected pseudo-randomly using RANDAO.”

An attacker who is the last validator in the committee can exploit RANDAO by biasing the scheme to become the next validator. An attacker with a 7% stake, for example, can increase their chance of becoming the block proposer by 1% every six minutes, exponentially increasing their rewards and staking power. This attack could start at even lower percentages of control, but would take longer.

Graph showing the percentage increase in proposals per epoch when biasing the RANDAO

Source: ETH2Book

This is why randomness matters, and how it can go wrong. Now let’s talk about how to create a more secure VRF.

Verifiable Randomness Requirements

The previous example highlighted the difficulties of achieving randomness specifically in adversarial situations, like online games, multi-party password generation, and the aforementioned consensus mechanisms. To avoid exploitations, a protocol must be

Unbiasable. No party, or even a majority of the parties, should be able to influence the result of the protocol, in any way.
Unpredictable. No one can predict future outputs of the protocol, even having the knowledge of all the previous outputs.
Verifiable. The previous two conditions must be easy to prove, and all parties receive the same outcome.
Fault Tolerant. The most difficult requirement, these conditions must apply down to one party. Otherwise, a coalition of every party but a single user could collude without the user knowing.

Therefore, a true VRF must be decentralized and take input from every participating party. It must maintain privacy until the reveal, and be fast and cheap in its execution and proof. Finally, it must be immune to the Dropout Problem, which we will discuss later.

Current “Solution” Failings

There are dozens of web2 and web3 solutions that claim to provide verifiable or, even worse, true randomness. Every single one of these fails and leaves open the possibility for profitable exploitation.

ChainLink and Other Random Oracles

The most common way to get randomness in web3 is to use an oracle. An oracle is a theoretically decentralized network that brings external data onto a blockchain. The most popular of these data feeds are for asset prices for DeFi transacting and lending, and for randomness.

The problem with VRF oracles is that they are fundamentally centralized. Either a single party takes a pseudorandom data source, like the weather, or a network of validators combine numbers together to produce an output. While the latter is better, because oracles suffer from a cost-size tradeoff dilemma, the number of validators is extremely low. This same problem impacts price feeds, but we’ll tell that story another week.

On web3’s largest oracle network, ChainLink, there are only 95 nodes on Ethereum and 30 on Polygon. At a given time, a VRF request might be processed by only one or two validators. If we wanted this number to be higher, we would have to incur exponentially higher costs. Currently, ChainLink VRF costs $4 on Ethereum and a few cents on Polygon—neither of which are sustainable for high volume applications like games or processing blocks.

Here, Vitalik Buterin, the co-founder of Ethereum, expresses his concerns about Chainlink:

Source: Reddit

While ChainLink does employ some cryptography to ensure fairness, the system fails at being unbiasable, as the VRF is centralized; unpredictable, as results are public; verifiable, as it lacks transparency; or fault tolerant, as it fails the Dropout Problem. Improving any of these facets would only further increase cost.

Commitment Schemes

A simple technique that many have used in the Mental Poker problem involves each player generating a random value, rᵢ, and announcing a cryptographic commitment, cᵢ, which is created by applying an encryption to rᵢ.

After all players have made their commitments public, their choices for random inputs are locked, but the commitments do not divulge information about other players' inputs. During the second stage, each player makes their commitment known by publishing it. The random values are then combined in some way, for instance by applying XOR or, preferably, hashing their combination.

This protocol is straightforward and produces an output with the desired properties as long as at least one participant selects its value randomly. However, it has a classic drawback: when all participants except one have revealed their random value, the final participant can partially control the result.

If the last participant is not satisfied with the final result, they can opt not to publish their value, thereby causing the protocol to fail. Ignoring the contribution of a faulty participant does not resolve the issue, as it still gives an attacker the option of choosing between two outputs (one calculated with their contribution and one without). This problem has a close resemblance to the Dropout Problem in Mental Poker, as we’ll explore later.

Ethereum’s RANDAO

Ethereum utilizes a similar mechanism to commitment schemes, but attempts to solve the Dropout Problem by forcing validators to stake ETH and seizing their collateral if they do not publish their random value.

RANDAO works by having each validator commit to a hash onion H(H(H(…S…))) when joining the validator set. When it's their turn to provide entropy, they reveal one layer from that onion. If the current block reward is low, the validator may forgo revealing and bias the randomness in their favor for the next selection.

This results in a 1 bit input of entropy. Vitalk Buterin argued that if the validators collude, this bias increases quickly with 36%, not 51%, being able to completely take over the network. Although certain security measures could increase this threshold, an even smaller coalition could gain power over time, as we mentioned earlier.

Hashes, DRAND, and Other Partial Solutions

Hashes are often proposed as randomness solutions for games and lotteries. Simply using the block hash suffers from the same problem as RANDAO, but with the added detriment that the miner/validator does not need to be a relevant party. In RANDAO, biasing the randomness is possible, but the presence of other validators increases the threshold for security.

In a lottery, one single person, not 36% or 51%, could validate, or not validate a block, completely controlling the source randomness for a casino or game. This is especially problematic because bets scale, making incentives to cheat extremely high. Spreading out the source randomness over multiple hashes does not work as the final validator, who can observe the previous hashes, ultimately determines the entire result.

DRAND is a centralized, but vetted group of validators that release random seeds every 30 seconds. Of course, one of these 16 validators could be compromised and control the randomness for hundreds of encryptions and security applications. But the larger problem is that the data is not on-demand or private. This means this approach cannot be used for games, consensus mechanisms, or with sensitive consumer data.

VDFs are interesting, but are not on-demand and are relatively expensive. Possible variances in output prevent their usage in most high frequency applications, although Ontropy is researching some VDF-like solutions.

The Dropout Problem

As we’ve alluded to in this entire article, the Dropout Problem is a principal reason why VRFs and Mental Poker are so difficult. Randomness must be unpredictable, unbiasable, verifiable, and fault tolerant. Essentially, you need to have a bunch of strangers give each other private data in a way that everyone can verify is fair, but without knowing what the data is and without trusting any third party or middleman. Then, the winner needs to prove they won, while the majority is incentivized to lie and keep their bet.

This is why even the most advanced Mental Poker solutions have failed to satisfy all four requirements. Specifically, because the final output is always determined by one party, they can predict and bias the result by revealing or refusing to reveal the commitment. Although seemingly an edge-case, the Dropout Problem allows just a single user to break the trust and randomness in the protocol at any point.

So, let’s consider some potential solutions. The first, described in “Dropout-Tolerant TTP- Free Mental Poker” by Jordi Castella-Roca, Francesc Sebe, and Josep Domingo-Ferrer, is based on re-initiating the protocol if some players have left prematurely but allow players to veto the dead cards without letting other players know what cards are vetoed.

This method is known to be not fair because it allows a coalition of two or more unfair players to change the probability distribution of the cards in the deck. For example, one player gets:

which is one of the top hands in the Texas No-Limit Hold’em game, and another player that is colluding with the first one gets:

That is not nearly as good. It comes out that the player with [7,2], can always leave the game prematurely to improve the first player’s chances of getting flush.

That happens because these two cards, desired by the first player, will be returned to the deck and are guaranteed not to be distributed to other players. This probability distribution change is easily exploitable by even amateur poker players, which results in massive winning difference over a large sample of hands played. The number of such possible cheating scenarios is huge and renders this approach unusable.

The second main method, used in “Kaleidoscope: An Efficient Poker Protocol with Payment Distribution and Penalty Enforcement” by Bernardo David, Rafael Dowsley, and Mario Larangeira, is focused on penalizing players for not completing the protocol. This second method is not practical for real-world applications either, because it changes the rules of the original game by introducing financial frictions that are only partially effective at preventing cheating. Players would need to post large collaterals to play with small bets, disincentivizing cheating but also harshly punishing “honest mistakes,” like network failures.

The third main method involves changing the dealing sequence in poker to create a set of rules that mitigate the Dropout Problem. This greatly impacts the playing experience and is a poker-specific solution. As the intent of studying Mental Poker is to unlock cryptographical solutions to verifiable randomness and distributed data transfers at large, solution three is not ideal either.

Source: Ontropy

Dynamic User Entropy With an Analogy

Many of you told us that you understood Proof of Result for the first time after our car-garage analogy. Let’s do it again! This time, we’ll use poker to explain Dynamic User Entropy, the first truly verifiable randomness protocol. The counting machine is the smart contract code, locks are encryptions, and moving the boxes represent each player’s addition of randomness.

You and two opponents want to play poker. All of you are competitive and will do anything to gain an edge. You believe these two opponents may collude together to win. So, you place the 52 cards into 52 identical boxes, and lock them with a key. The two other players leave the room, so you can shuffle the boxes. You leave, and another player enters, places their own lock, and moves around the boxes. The final player does this as well, and you and the other player re-enter.

You each take two boxes, your private cards, and unlock the other players’ boxes. Each player is then able to unlock their boxes in private and view their cards. You begin dealing the river, the public cards, by unlocking three boxes. You hand them to the next player, who takes off their locks, with the final player doing the same. All three cards are now visible to everyone. You place your bets by moving chips into a counting machine in the center of the table. This process of revealing cards and betting repeats two more times, and the game concludes.

All players then insert their cards into the counting machine, which will distribute the pot to the winning hand. Assuming cooperation, each player can prove fairness as even if both opponents collude and do not move around the boxes, they can not tell your order, or gain access without your key.

The process so far represents current VRFs. While better than centralized randomness, cooperation, of course, cannot be assumed. The opponents can easily break the system by refusing to show their cards, contesting the results, or by dropping out and not unlocking additional cards.

Source: Ontropy

Let’s modify this process so that each box contains three cards, instead of one, and every card is signed by the players ahead of time. Now, every player will have immutable access to revealed cards. A single player can thus submit the public cards and their private cards to the machine without cooperation from the opponents. If the opponents refuse to participate, the counting machine will distribute the rewards to the player who submitted the cards.

This is effectively a proof of participation (PoP) mechanism that partially prevents the Dropout Problem. Because the cards were signed ahead of time, opponents cannot produce other cards that contain all three signatures. The signatures represent the distributed key generation (DKG) process.

The addition of PoP and DKG make refusing to show cards unprofitable and contesting results impossible. They also ensure that an honest player cannot be accused of refusing to participate. Because every player has access to all of the cards and the counting machine, the submission of cards by an opponent and subsequent accusation of dropping out will result in every player, honest and not, submitting their cards. With access to all cards, the counting machine will distribute the pot accordingly.

However, players can still refuse to unlock cards. If you unlock a public card, there will be only two locks remaining. If your opponents collude, they can unlock the boxes in secret and choose to reveal the cards only if the outcome is beneficial for them.

Ontropy adds an additional PoP mechanism by allowing a player to prove they unlocked the box when they were supposed to by submitting the unlocked lock. How this is accomplished cryptographically is extremely complicated and will be explained in a later addition, but this feature achieves fault tolerance down to one fair player, even with a hostile majority.

In the scenario of five players, where two are colluding, their refusal to unlock even one box would mean the game cannot be completed. This is the Dropout Problem. While Dynamic User Entropy cannot yet be fully open source, we can describe how Ontropy solved this 40-year-old problem at a high level.

Now instead of placing the cards into 52 boxes at the beginning of a game, suppose that each player has their own set of 52 boxes with 52 cards and 52 locks, and that cards are only distributed when needed.

When you request a private card, you will pick a box from your personal deck. Each opponent will do the same. You now have five boxes in front of you, one from every player. Each opponent now unlocks their boxes, revealing four cards. You will do the same, but will not show your card. Your final card will be a sum of all five cards (e.g. Ace of Spades, 1 + King of Diamonds, 51 = King of Hearts, 52), which you can compute easily. Because all cards are signed, and the math for adding card values is agreed before, you can easily prove your final card.

This process can be repeated for all cards, public and private. This “deal cards when needed” approach is the “dynamic” in Dynamic User Entropy. Now, if a player drops out, the remaining players can deal and reveal additional cards without that player.

Yet, there is another problem. Because adding cards together adds even more entropy, there is no guarantee that the final card is not already in play (if card 22 represents a Six of Hearts, then there are many combinations of five numbers that yield a 22). Therefore, every final card will need to be checked for collisions, but without revealing the card value itself.

Source: Ontropy

Now we reach the end! To check for collisions, we utilize homomorphic encryption. Continuing with our analogy, imagine now that each player has 52 unique locks. Each lock on every box has a relationship with the card inside, so a box containing the Six of Hearts might feature an encrypted version of “22,” which might be “52” (using a simple encryption of adding 30). This would allow players to determine if the cards inside two boxes are the same, just be looking at the public lock, and without revealing the card value itself. Of course, your mind jumps to zero-knowledge proofs now. It’s funny how complicated the seemingly straightforward task of generating verifiable randomness is, isn’t it?

There are further complications that invite the discussion of VDFs and time-locked encryptions, but the dynamically adding boxes with unique markings that allow the game to continue seamlessly without players that have dropped out analogy describes the fascinating cryptography behind the verifiable randomness and Mental Poker problems. You just learned about homomorphic encryption, zero-knowledge proofs, distributed key generation, and multi-party computation without even realizing it!