[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Cryptography] A Scheme for Verifiable Lottery

Now there are a lot of online lotteries, or giveaways, usually they would
involve and trusted third party to draw the prize, yet there's little to no
reason those third party should be trusted. To me, a good lottery scheme have
these properties:

 1. No need to trust the organizer
 2. No need to trust the participants
 3. No need to trust any third party
 4. Results are random
 5. Cannot be set in a way that favors some participants
 6. Cannot be set in a way that exclude some participants
 7. Do not need to publish the list of participants
 8. Participants can prove they did or did not win
 9. Participants can prove to others they did or did not win
10. Can set any number of winners
11. Can set tiers of winners
12. Easy to implement
13. Fast to compute
14. Fun

The solution I came up with is follows:

Post the following info:
  A Lottery name, this needs to be unique each time
  MAC tag of a chosen "lucky number"
  The number of winners
When participants sign-up, they are given some sort of proof for joining,
"Lottery name + username" signed with the organizer's keypair (for example)
Calculate participants' score from their unique username
  score = min(hash(1, <lottery name>, <username>),
              hash(2, <lottery name>, <username>),
              hash(<lucky number>, <lottery name>, <username>))
Winners are the participants with the lowest scores.
Announce the winner, the lucky number with the MAC key used to generate the tag

The rationale for the repeated hashing is that since the randomness are picked
by the organizer, there's no way to stop them from favoring someone by trying
possible lucky numbers. Therefore with this scheme, they would need to give
everyone else at least the same number of tries, making picking favorites

My scheme implementation of this idea https://sr.ht/~shironeko/lotte/

The cryptography mailing list
cryptography AT metzdowd.com