Authors: Vlad Gluhovsky gluk256@gmail.com, Daniel A. Nagy nagydani@epointsystem.org
The objective of the presented algorithm is to generate a fair random bit after k blocks in face of an adversary controlling 0 < m ≪ 1 of overall hashing power. More specifically, we assume the adversary to be able to prevent a specific block from being finalized in the block chain with probability m. We consider a coin toss fair, if for any value attached to the outcome, it is possible to set k large enough that the expected cost of influencing the result is greater than the expected profit from doing so.
For each block, we define Rᵢ to be bit i from a pseudorandom IID bitstream R seeded by the block hash. The algorithm is initialized by setting S to R₀ in the first block b after all bets have been committed. In each subsequent block b + n such that 1 ≤ n < k, S is overwritten by R₀ in 1 / n of cases of possible sequences of R₁… or, in practice, a good enough approximation thereof.
The final value of S is going to be the R₀ value of one of the k blocks, with uniform 1 / k probability.