The Fair Lottery

The Fair Lottery

Summary

The fair lottery is a thought experiment of a fictitious lottery. Each participant in the lottery is indistinguishable from any other entrant into the lottery. The probability of each entrant winning is uniformly distributed, regardless of the amount of tickets purchased.

Rules of the Fair Lottery

  1. All participants are indistinguishable
  2. The number of participants is unknown
  3. All participants must obtain at least one ticket
  4. Each participant has equal chance of winning the lottery regardless of the tickets they hold
  5. Winners of the lottery must be greater than 1 and less than the number of tickets sold

Notes

I. Tickets can be free or sold
II. Lottery drawing can rely on provided entropy but is not required
III. A participant is not discrete and can collude or collaborate with n other participants. A participant is abstract and represents a unified holder of tickets in the lottery.

Appendix

2 Likes

I would be interested in hearing people’s solutions. Feel free to comment in the thread for clarification.

A simple solution would be : use the random number from random beacon to get the winner.
You cannot get some solution more scalable and secure.

The proposition isn’t about randomness, randomness can be provided externally. The question is regarding uniform distribution of odds of winning. A solution has implications for Sybil attacks.

This seems impossible unless you have a unique-identity solution; otherwise any participant can obtain multiple tickets and thus pretend to be two or more participants.

2 Likes

That’s what makes it a fun problem

The kernel of the problem statement seems to be “sybil resistance”. Since there’s no way to make proxy voting expensive or enforce identities, it seems impossible.

I believe the problem may be framed as “who gets chosen to create the next block” (ie. that’s the “lottery”). So from that framing, our current best-effort solutions in this space of PoW, PoS, and the like come to mind. But the result for these solutions isn’t that every participant gets equal chance of winning, since the identity mechanism can favor certain people (ie. someone with more hash power, or with more stake).

This is a problem that’s fun to think about. In terms of coming up with a “hard” solution, it seems impossible due to the fact that anyone can enter the lottery multiple times as long as they can obtain more than one unique ticket. It seems we would need to turn to game theory. You would need some kind of mechanic that either forces or encourages participants who hold more than one ticket to reveal themselves since this is the only way to calculate their odds of winning.

2 Likes

Exactly where my head is at right now

I think it is fairly simple to prove the impossibility of such a system. Here’s a sketch of a proof:

  1. Assume you have a perfect lottery system, that satisfies all the properties stated in the problem.
  2. Conduct the fair lottery and select a winner.

At this point, it is entirely possible for the winner to be a member of a completely out of band coalition of lottery ticket participants who have been forced or tricked into giving up their winnings should they be selected.

  1. The organizer of this coalition collects the winnings, with probability proportional to the size of his coalition.

Thus unless you can enforce the constraints down to the basest level of physics you cannot have a provably fair lottery. In fact, the stated constraints of the lottery creates incentives to attack other legitimate honest players, which is probably not what you want.

Joseph ", REALLY…now, let’s become great friends and share secret’s
I want to know it all! I always knew I was going to achieve great things, Gods Plan.
I am wondering how Ethereum knew? Obviously, tracking my man hours of Labor on the Internet.I am so blessed, and grateful.

Thank You,
Ethereum