[Cryptography] [cryptography] NIST Randomness Beacon

[Peter Todd]

On Tue, Nov 12, 2013 at 10:10:13AM +0100, Adam Back wrote:
> (Top posted, so sue me, my text explains itself without the history).
> 
> Thats a big cc list.  I think you could create a beacon with bitcoin hash
> chain by having miners reveal a preimage for 6 old, consecutive blocks where
> the newest of the 6 old blocks is itself 6-blocks confirmed.  (ie reveal
> preimage on blocks 7-12.  The xor of those preimages defines a rolling
> beacon (new output every block, just with reference to blocks 7-12 relative
> to the current block depth).

A non-interactive approach could be to make use of random walks.

Suppose we want to create a single random bit from a single block hash.
Takethe right-most 127-bits, none of which are involved in the target
calculation, and calculate a random walk. If the sum of the walk is > 0,
call the bit a 1, and if < 0, call the bit a zero.

How much effort would it take to skew the probability distribution of
that one bit? The RMS distance after n steps is \sqrt(n), or about 11.3
in the case of 127 steps.(*) I'm handwaving here, but essentially we can
say that on average you'd need to select about 12 bits to have a decent
chance of forcing the bit to the value you want. But that takes 2^12
work, so even if you had 100% of the hashing power it's infeasible and
usually you'll have no control at all. (but sometimes you're block will
be the tie-breaker!)

*) Or 128 steps, and if the sum = 0, consider it a failed round and take
the next block instead.

A similar idea to other proposals for using "strengthening" of course,
but this has the advantage that we can make clear guarantees about
exactly what probability the attacker has of being able to influence a
given bit with however much hashing power. This also gives you options
to shape that probability distribution: a "closest wins" lottery using,
say, 256 sequential blocks to produce 64 bits, might want to assign more
bits to the walks for the MSBs of the random number, calculating them
from many blocks, than the LSBs which might take bits from only a few
blocks.

Anyway, it'd be interesting to develop the math for this idea more
fully.

-- 
'peter'[:-1]@petertodd.org
0000000000000003c3095cb8e7e25a516e8eef8314a20a2e68ab7df7d567a8db
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: Digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20131112/90ce6596/attachment.pgp>