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
All participants are indistinguishable
The number of participants is unknown
All participants must obtain at least one ticket
Each participant has equal chance of winning the lottery regardless of the tickets they hold
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.
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.
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.
I think it is fairly simple to prove the impossibility of such a system. Here’s a sketch of a proof:
Assume you have a perfect lottery system, that satisfies all the properties stated in the problem.
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.
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.
We have presented a new scheme called DDPFT—Dynamic Delegated Power Fault Tolerance, which should resolve this. It can be divided into three phases:
Committee election:
for every epoch, select a large scale of committee(about 1024 nodes). This can be done according to RANDAO algorithm.
Block proposal :
For round n+1, on block of n’s arrival, Get new VRF result: R_{n+1}={\rm signautre}c(R_n), where c is the codebase of block n, the new R{n+1} is published on block body.
each node calculates its opportunity: and , where HMR is Hash of node M in round R, Opm is the opportunity for node M
Fixed number, such as 99 or 149, of delegates for new round is calculated out accord to R, the can be those whose addresses are shortest distance to Rn+1
Node delays for a while according to Opm and sends vote requests to those delegated after timeout if needed. Nodes who had sent vote request is called as candidates.
Delegates should wait for a specified time to collect vote request as much as possible. After timeout, sort vote requests by Opm, and then create votes. Different votes have different priority, which is the order of sorted requests.
Delegates send votes to each candidate.
A candidate collects votes and calculates its weight, weight of node m is Wm.
Node delays for a while according to Wm, then create and broadcast new block if no block with higher weight arrives.
Time Delayed Broadcast:
On new block’s arrival, each node should delay and wait for a while on the block’s weight.
Benefits:
Opm is according to node’s power, inspired by Filecoin, this power can be any measurable capacity of node, such as storage or just stake.
Block codebase gains most reward and delegates gets least, reducing incentive of delegates for signing in different fork.
Signing in different votes with same priority is easy to find and will be punished.
Delegates who abide specified time will have the most possibility to be rewarded, which will guarantee block generation time.
Block with more weight will be propagated faster and larger scale
Liveness assurance: If block with more weight failed, the least one will propagated instead.
Fast finalization: Blocks with more that 50% of 1st priority are finalized.
The consensus is designed for multi-layer sharding system, any challenge and discuss will be very appreciated. This is the first time to post on ethresear.ch, should i create a new thread to discuss this?
