Sorry about the delay with this, I have just gone through all the lottery drawing ideas and this is the best one I found mainly because I don't have to store 200 million+ ticket numbers for each round and the "window" system for picking winners is what I already use.
I have a few modifications to this idea though to make it easier to verify and implement. So, this is how the lottery will work with my modifications:
1) Before a lottery round starts, a server seed will be generated and it's hash will be provided.
2) After a lottery round is concluded, a list of user id's and tickets will be produced in a text file ordered by ascending user id's. This order will be used to create the "ticket-windows" as Zhor and edge777 have described below.
Twitter is ideal for this because it will provide a timestamp that can be verified to check that the block number provided is in the future. Also, tweets cannot be edited, only deleted so if I delete the original tweet and post a new one after the block has been mined, it will have a timestamp greater than the timestamp of the block used for the client seed.
4) The server seed, block hash and an incrementing nonce will be used to draw the 10 lottery winners.
Please let me know if this can be exploited in any way or if it needs clarification. I believe this is the easiest implementation that can also be verified quickly by users. I am still open to ideas until I proceed with implementing this (in the next few weeks) so please post your ideas and if something better comes along, I'll use that. If not, the reward will be divided equally between edge77 and Zhor.
The original idea is below.
well, hello everybody from bitcointalk,
i bumped into this forum searching for information about the new free-roll bonus. I saw wetsuits post asking about a provably fair lottery.
I would love to make the lottery provably fair but unfortunately there is no method of doing so as far as I know. Hence, I have done the next best thing which is to offer users a chance to opt out of the lottery and receive reward points instead if they feel the lottery is rigged. You can do this from the PROFILE page.
I willl offer 1 BTC to anybody who can provide me with a way to make the lottery provably fair in issuing tickets and picking out winners. The system described should be able to handle hundreds of millions of tickets and verification for users should be fairly easy and straightforward. You can post your ideas here and I'll go through them and reward the idea that we use.
Both the free roll and the dice game are provably fair and the website will be going completely ad-free as of today.
first of all, i have to say that i liked edge77's idea about converting ticket counts to ticket-windows.
You can design a system something like this:
Let's say, Person A bought 5,000 tickets, Person B bought 9,000 tickets, Person C bought 50,000 and Person D bought 1,17,000 tickets
User A : 5,000 tickets
User B : 9,000 tickets
User C : 50,000 tickets
User D : 1,17,000 tickets
Combined, total tickets : 1,81,000
Generate a random number between 0 and 1,81,000 [note by Zhor: this should be 180,999]
Set a windows like below :
0-5,000--- User A wins [note: again, 0-4999]
5,000-14,000--- User B wins [note: 5000 - 13,999. you get the point.]
9,000-64,000--- User C wins
64,000-1,81,000 ---User D wins // User D with most tickets has the largest window
...
the problem with that system is, that it is *not* provably fair, even though the "random number" chosen to pick the winner could be provably fair picked.
In the example above, a user could say, that the order of the windows (first user A, then B) has been manipulated so that the "right" user wins.
This is why i have come up with an adaption to get this system fully provable.
The idea is, we would need "public" knowledge about the exact amount of tickets each user had at the end of the lottery and about the order of the "ticket-windows".
If we simply publish the order of windows at the beginning of the lottery and add the number of tickets of each user at the end of the lottery-period, everything would be fine.
But i assume that it is no good idea to publish all these information, since anybody could find out a lot of interesting things, like how many users have below 1000 tickets, who are the top 10 of players with the most tickets and much more.
Imagine you knew the exact amount of tickets of all users for each lottery. you can even track the activity of every user.
Thats why we are going to hash these information and only publish the hashes.
To prove that the order of ticket-windows has not been altered after the drawing, we will create a "client(s)-seed" out of hashes of 3-tupels (UserID:FirstTicketNumber:TicketCount) of EVERY user. Lets have a look at the steps of the whole system:
1. publish hashed serverseed at the beginning of lottery-period [and nonce]
2. wait for the ending of lottery period
3. create ticket windows for every user (á la edge77)
4. send 3-tupel and hashed 3-tupel to every user (UserID:FirstTicketNumber:TicketCount)
5. publish all hashed 3-tupels
6. condense (hash again) all hashed 3-tupels into client-seed (to get an appropriate length) [and publish client-seed]
7. use server-seed and client seed to pick a provably fair random number. look up matching ticket-window and user (who wins!)
8. publish server-seed
this is only for one tier of lottery winners. to adapt this for 10 winners, we should probably add a nonce to the client- and server-seeds and count this up as we roll (at least) 9 more numbers. If we roll a user who already has won a bigger price, just reroll with nonce+1 again.
using this system, we can prove to any user:
a) that the server-seed has been chosen at the beginning of the lottery-period. (same as in free roll and multiply roll)
b) that his position in the list of ticket windows has been picked *before* choosing the winning number.
to prove b) the user has received his own 3-tupel of his UserID, the number of his first Ticket (in the example of edge77 this would be 0 for User A, 5000 for user B, 9000 for User C and 64 000 for User D), and the amount of his tickets.
he can now hash this 3-tupel by himself and search for that hash in the public list of all 3-tupel-hashes (see step 5!).
for example his hash could look like this: 344fbaff44ddcd7ca5d65b0324f4c40d01af30a5e7fabd4a18d69f80e4fa521f
now the list of all these 3-tupel hashes could look like this: ...:35fe8b392f1b2dfbc4745e52bba71750452f7a911e8d4cb31dd9ade427bf905b:344fbaff44ddcd7ca5d65b0324f4c40d01af30a5e7fabd4a18d69f80e4fa521f:347bb84f4d5260e8e1e1b759834df0095ee6e2225c31fdc8c5b060a637f36a16:...
and that list has been hashed to the final (public) clients-seed: ccb686936c6d0f33b97bc7d2b18db2f639381387c3ec813a11981b39d139d48b
he should find HIS has in the list of 3-tupels hashes and he should be able to hash the list of 3-tupel hashes into the client-seed.
that will verify that his position and amount of tickets were used to create the winning-number.
however if you want to verify that USER XYZ indeed won the first price, you only need to publish his 3-tupel (UserID:FirstTicketNumber:TicketCount).
anybody can then verify that this user indeed had the ticket-window that the winning number fell into, by finding his hash in the list of all 3-tupel-hashes.
for 2-nd price or 3rd price everybody knows that the nonce will be altered (+1 for 2nd price, +2 for third price and so on...)
so what do you guys think? is this too complicated? does it have security flaws? is it too much of edge77's idea? or is it not "convincing" enough?
also i humbly ask for your forgiveness if you find any spelling or grammar mistakes, since i am not a native english speaker.
..... lift ya ass and start recruiting. 