Ok. Makes more sense. I was trying to get around the computation part for more than 30 minutes. That's "hard". Not a problem for a once a week game, or even a daily game, but it does mean you have to set aside processing this. This is slow to compute AND slow to verify (please correct me if I'm wrong.)
You're not wrong, but you are kind of missing the point. It is slow *on purpose* so that the miner can't tell whether the block he just mined makes him win or lose, and so he can't cheat by withholding a block that makes him lose. By the time he figures out that his block makes him win it has already been orphaned, so he may as well just publish the block immediately and not try cheating the lottery.
It would be better if it was slow to figure out who won but very quick to verify the result, but nobody was able to come up with a way to do that, and so pevpot uses a calculation that is just as slow to verify as it is to run the first time.
The ideal algorithm would be:
a) slow to determine who won given a list of tickets and the mined block hash
b) quick to verify the winner given a list of tickets, the mined block hash, and the winner
c) deterministic, so that step a) always gives the same winner for the same inputs
It's not hard to find systems which give us any two of these three:
A+C: The current system has (a) and (c), but there's no quick verification step.
B+C: Just using the block hash gives us (b) and (c) - it's instant to verify, and deterministic, but step (a) is also instant and so the miner can cheat.
A+B: We can get (a) and (b) using some kind of proof-of-work algorithm. We search for a nonce such that sha256(blockhash+nonce) starts with 10 zeroes (or whatever difficulty is suitable), then use that new hash to determine the winner. It's slow to find such a nonce, and quick to verify that the nonce works, but it isn't deterministic. Lots of different nonces would work, and give different winners. We could insist that the nonce search starts at zero and works upwards, such that only the lowest such nonce is accepted, but then verification is no longer instant, since we have to replicate the whole proof of work to check that the given nonce is the lowest one that works.
Can you find a method that gives all three of (a), (b), and (c)? It shouldn't rely on any "server secret", since we have no way of knowing for sure that the server owner isn't also playing the game.
I'd also like to avoid external secrets, meaning "real life" secrets. These include actual lottery results from maybe Mega Millions or Powerball. (Although that certainly makes it provably fair, as no way would anyone know the Powerball results before the draw, unless all the balls were rigged.)
Re-read what you just said: that's provably fair unless it isn't... Using powerball numbers isn't provably fair - it is relying on the trust that whatever process they use to select balls isn't rigged. There's no proof that it isn't, and so the game is "trustably" fair, not provably fair.
(except for the case of BaB)
Right now I'm taking a break with running bustabit and working on something totally unrelated to bitcoin or gambling