How to Design a Marijuana-License Lottery

http://www.newyorker.com/tech/elements/how-to-design-a-marijuana-license-lottery?mbid=social_twitter

by coloneltcb • 10 years ago

5 1 10 years ago

sibrahim• 10 years ago

Lottery designer here. Some clarifications on the article:

Re: getting a random number from 1 to 5 from a d6, my point got stripped out of the article and it's possible to come away with the wrong impression. Modular arithmetic is the wrong thing to do here as it introduces bias (just reroll sixes instead). Using modular arithmetic correctly can be illustrated with a d12: reroll 11 or 12 and use remaining rolls mod 5 (rather than always rerolling 6-12). This completely standard result extends to any desired number range.

To prevent any single person being able to fix the lottery, different people got the two randomness components which were then combined with exclusive or. An air-gapped computer and a cryptographic commitment scheme were used to ensure independent generation no one person could usefully subvert (so we were immune to an Eddie Tipton style attack before his case made the news).

Why not use a cryptographically secure pseudorandom number generator (CSPRNG)? Avoiding lottery loser lawsuits.

First, a note about basic structure: licenses were allocated and applied for by jurisdiction (city/county) so the stream of random numbers was used to serially run separate lotteries in each jurisdiction. Each lottery produces a full permutation so requires log(n!) bits of entropy.

If you used less than ~1200 bits of entropy when seeding your CSPRNG (either initially or periodically reseeding), then applicants could argue (correctly, though somewhat misleadingly) that some outcomes in the cartesian product of individual lottery results could never be produced by the system and try to get the results thrown out on this basis.

Indeed, with a small seed, one could say that the outcome of any particular lottery is determined by the outcomes of the other jurisdictions. That is, the other lottery results determine the seed (nonconstructively, for a CSPRNG) with high probability which trivially determines the current lottery result. This trick has been used (against much weaker systems) to cheat at online poker by using your hole+flop cards to reveal all cards: https://news.ycombinator.com/item?id=288138

Using a CSPRNG with a large seed/state space resolves this possible objection if you use a TRNG (true random number generator) to generate that seed. But if you do this, there isn't much reason to involve a CSPRNG at all (at best it's just another whitening step on top of the TRNG).

How to Design a Marijuana-License Lottery

Related Stories