Quote from: CIYAM Open on February 15, 2014, 03:29:06 PM

Well - one big snag with a "use case" that I think a few had hoped we would be able to do.

We were thinking of something like a Nxt "lottery" where you would send amounts to the "script" and after x amount of time it would pay out its balance to a "winner".

The problem is that it doesn't seem possible to get "random" data in Nxt. People can change txid's (due to malleability) and forgers can simply omit transactions including those that run the script making it impossible for such a lottery to be actually "fair". Also TF means that you can actually predict some hashes even in the future (was BCNext trying to tell us "not to gamble"?).

Perhaps there is something we haven't thought of yet to still make this possible so if anyone has a great idea about that please let us know!

If the lottery takes place over a long time, you could use info from a block that's generated a long time after lottery entries are no longer allowed, long enough to be essentially unpredictable.

Alternatively, this might be one way to do it. There's a flaw, I'll explain a patch to it later to keep the description simple.

1) Before the lottery starts, lottery starter chooses a hash function Hash() with range 0 to N-1 inclusive, and also picks a number OFFSET. He announces Hash, Hash(OFFSET) and the number of lottery winners publicly.

2) During the lottery, all lottery participants and the lottery starter each pick a different number l_i and announce it publicly in any order.

3) At the end of the lottery, lottery starter reveals OFFSET. Hash(l_i + OFFSET) is computed for all lottery participants and the lottery starter, and the winners are the participants whose hashes are closest to that of the lottery starter's in Z/N (i.e. regarding N-1 as "wrapping around" to 0).

If Hash is a strong hash function and if OFFSET is essentially uniform random from the perspective of the participants, then the lottery is fair, since the distribution of the Hash(l_i + OFFSET)s will be essentially uniform random and unpredictable before the lottery has ended. Any Evil Dave (note the space!) who waits until the last possible moment before announcing their l_ED so as to get as much info as possible about the other participants' l_i s can still do no better than making a random choice of l_ED.

The hitch is that this depends on OFFSET being difficult to predict. Consequently this depends on the lottery starter being competent and honest: they need to choose OFFSET sufficiently randomly, and not reveal it to any of the participants before the lottery has finished. But there is much lower burden for OFFSET to be difficult to predict than there is for the draw (all the Hash(l_i + OFFSET)) to be, since there's a large computation burden in order to make use of any bias in the distribution of OFFSET: If Evil Dave wants to find a favourable l_ED, he will need to compute Hash(l_i + OFFSET) for all participants i and all likely OFFSETs, whereas anyone verifying the lottery only needs to compute Hash(l_i + OFFSET) for all i and a fixed offset. Hash() could also be chosen to be many iterations of a common hash function.

So a way to adjust it without depending on the honesty of the lottery starter is, instead of having the lottery starter choose OFFSET, to have OFFSET be determined by the lottery participants in a difficult to predict way (not necessarily uniform random). OFFSET = sum of account numbers of all participants might work, if participants don't need to pre-register for the lottery.