[Cryptography] A Scheme for Verifiable Lottery

[John-Mark Gurney]

Yunxiang Li wrote this message on Wed, Nov 25, 2020 at 11:31 +0800:
> 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
> impossible.
> 
> My scheme implementation of this idea https://sr.ht/~shironeko/lotte/

Seems to me that a better way is similar to the coin flip implemented
by keybase: https://book.keybase.io/docs/chat/coin-flip

This way, each lottery entrant has some input into the random number
system that ends up picking the winner.  This helps ensure that even
the last entrant has influence, and prevents any possibility that the
winner is known till the last entrant has entered their ticket...

This can be further protected by each entrant committing to a secret,
but then not reveiling the secret till the lottery is closed...  Biggest
issue w/ this step is that everyone must send in their secret after
the lottery closes, and that could take quite a bit of time...

-- 
  John-Mark Gurney				Voice: +1 415 225 5579

     "All that I will do, has been done, All that I have, has not."