Building a Lottery, Part 4

The trouble with public PRNGs

The problem with building gambling games on public blockchains is that everyone can see everything. Just like I can see your complete history of transactions, you too can peer inside my contract and see what’s going on.

Even variables marked as “private” in Solidity aren’t really private — they’re just not publicly accessible to other contracts. If you have the right tools to inspect the internal state of a contract, what’s hidden there is still plain to see.

Commit and Reveal

One often-proposed solution is the “commit-reveal” scheme, which comes in many flavors. The gist of these schemes is that someone (or many someones) commit to revealing some secret in the future, and provide proof of what that secret is now. Generally, this proof comes in the form of a hash, because hashes are hard to find the pre-image of, but easy to verify later. By providing a hash of the secret, one provides a guarantee of the value they eventually reveal later. This provides secrecy.

However, this comes at a cost. At the end of the day, the last one with a secret has all the information before everyone else — and they can use or abuse this how they see fit.

In the Lotto contract, this commit-reveal scheme is implemented through the curator, since a manual step is required to end rounds and create new ones. This also provides an outside source of entropy that can (almost) be verified to not have been gamed (more on that later). Users provide entropy by buying tickets, but the final piece comes from the secret that is committed to at the start of the round. By ensuring that all sources of entropy are committed by the last block, it can be proven that the outcome cannot be gamed by the curator (through, say, picking and choosing on which block to reveal the secret).

If we can assume that the curator is disinterested in the outcome of the draw (because he gets paid when anyone wins), this is a reasonably safe and secure PRNG for our purposes. However, this is where blockchain PRNGs, in general, start to fall apart.

Gaming the system

The weak point in this whole setup is that the curator has to be trusted. If the curator cares about the outcome, he can predict the winning numbers at any point in time — even before the closing block. Should the reward be great enough, he could even conspire to rig the game.

The issue arises because the output of the PRNG used to pick tickets and gather entropy from the users can be somewhat reliably predicted. Granted, it would require collusion with a miner or for the curator to be a miner herself, but it can be done — in theory.

The theory basically goes: If the curator controls enough hashpower to have a good chance of mining the final block, she can pre-compute the resultant outcome of the accumulated entropy for any number of picks. Combined with her knowledge of the committed secret, she can essentially birthday attack the PRNG until she finds picks that, when picked in the proper order, leave the user-accumulated entropy in such a state that when she reveals her secret, the winning numbers picked belong to her.

Realistically, this is not a very plausible attack. It assumes the curator is also a miner, or that he is collaborating with complicit miners (with sufficient hashpower) to game the system. It also assumes a little bit of custom infrastructure to reliably generate the necessary collisions in the time it takes to mine a block; because one of the inputs to the PRNG is the block’s timestamp, that timestamp must be committed to when attempting to generate collisions.

About trust

In order for the Lottery (in its current form) to be a viable and fun game, it requires that the curator be trusted. The downside to this trust is that if the curator cheats, there’s not really any good way of telling.

For my implementation and deployment of the Lottery, I planned to automate the curator, thus guaranteeing its disinterest in outcomes. At the start of every round, it would generate a secure random seed as the secret, and then deploy a new round with the commitment to that seed. At the close of every round, it would automatically reveal the commitment, pay out the winners (if any), collect its own fee, and repeat.

Again, though, this comes down to trust.

Alternatives?

After releasing the contract, I had a series of interesting conversations around this particular PRNG, the issues of trust and vectors of attack described above, and tried to come up with a solution that might work under the constraints of a Lottery.

Random beacons were mentioned, distributing the secret among many curators, letting users add their own commitments — but they all suffer from the same flaw: the last user to reveal has more information than everyone else, and thus can influence the outcome.

In the event the outcome of them revealing their commitment isn’t favorable, they can simply choose to not reveal their commitment. This, in turn, leads to a “hostage” problem. If every commitment is required to be revealed, simply not revealing lets them hold the outcome hostage, and can be used as leverage. On the other hand, if not all commitments are required to be revealed, an adversary can submit many commitments and choose any combination of them to reveal in order to gain an advantage.

The other solution to the hostage problem is to require a deposit that is returned when the secret is revealed. This, too suffers from an economic flaw: the deposit must always be greater than any potential gain to be had from withholding the result. If the deposit is less than the winnings (for example), an adversary may choose to simply not reveal their commitment if that results in them winning.

For a game like a lottery, this is obviously not a viable solution. Given that the winnings can increase over time, it becomes impossible to predict just how large the payout will be — and thus how large of a deposit is required.

In the end, I decided that there simply is no good solution to the information asymmetry problem inherent to all blockchain PRNGs.

Which brings us back to trust.

Miscellany

There are a few other flaws with the current iteration of the Lottery contract as it currently exists.

First, the ticket price is too low. The gas costs to run the PRNG are actually rather high, and in fact are higher than the cost of a ticket at 1 finney. If it costs more to generate additional entropy than it does to buy a ticket, it’s not a very economically attractive game to play.

Second, the odds of winning are far too low. I picked 4x picks from 0–63, which puts the likelihood of a number being chosen as the winning number at around 1:2²⁴. In order for there to be an approximately 50% chance of any winners, 2²³ tickets must be purchased. This is a very large number. Too large, in fact, for a week-long lottery round. Nobody will want to play a lottery you can maybe win in a thousand years.

Finally (and I touched on this in the first part), user interactions with the contract are too expensive. The PRNG can easily be slimmed down, as it’s a little over-engineered to reduce the likelihood of the system being gamed. However, if it’s going to suffer from the problem of trust regardless of the solution, a simpler solution will suffice to generate random tickets and ensure good distributions, while costing far less in gas prices.

Next steps…

Honestly, this depends on interest. If the trust issues are acceptable for a game (provided proof of automation, perhaps), I may endeavour to create a clean interface for it and finish off the whole dapp development cycle. I may do that regardless, purely as an exercise for myself.

Also, in the midst of all of this madness about predictability and PRNGs, I came up with a slightly better game. So at the very least, stay tuned for the next one.