[148141] in cryptography@c2.net mail archive
Re: [Cryptography] [cryptography] NIST Randomness Beacon
daemon@ATHENA.MIT.EDU (Peter Todd)
Tue Nov 12 15:34:23 2013
X-Original-To: cryptography@metzdowd.com
Date: Tue, 12 Nov 2013 11:12:10 -0500
From: Peter Todd <pete@petertodd.org>
To: Adam Back <adam@cypherspace.org>
In-Reply-To: <20131112091013.GA23676@netbook.cypherspace.org>
Cc: CodesInChaos <codesinchaos@gmail.com>, cpunks <cypherpunks@cpunks.org>,
Cryptography Mailing List <cryptography@metzdowd.com>,
"cryptography@randombit.net" <cryptography@randombit.net>
Errors-To: cryptography-bounces+crypto.discuss=bloom-picayune.mit.edu@metzdowd.com
--===============8727617252405195911==
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="CUfgB8w4ZwR/yMy5"
Content-Disposition: inline
--CUfgB8w4ZwR/yMy5
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
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).
>=20
> 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 wh=
ere
> 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 relati=
ve
> 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 =3D 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
=66rom 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.
--=20
'peter'[:-1]@petertodd.org
0000000000000003c3095cb8e7e25a516e8eef8314a20a2e68ab7df7d567a8db
--CUfgB8w4ZwR/yMy5
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.11 (GNU/Linux)
iQEcBAEBCAAGBQJSglNaAAoJEBmcgzuo5/CFNf0H/2FTBRoonDM0pc7bbapbknkm
vOeeQfTnAy0E/bR0HoGRsz+jjZUHgWWxLBiZa5YOIQXxkeL69inElzpGALi4tHOy
Y3wLCAJbp1o1/p3+N791Yut69jgRqPunTyz7mIJaTUn4LL+NYBk3L8Mf4RLcE0dL
u0AB/60QdKaxW3IovlNWlW0PDxv88PlBmIPvfak+OOB9Runn2WOCUMTPHFisFog1
t1Q7XkrOpqsAo1L687F921B9lZ2L2ZIXPWXhq4Mn2mPhlg66n0StfKPgIl0DOyww
fv0bRm6pUq9ZnVo5Mq2tq0fygQUOii7CDxZtgtl81HL7h20oUbiL7yisEeChU6Y=
=0rqn
-----END PGP SIGNATURE-----
--CUfgB8w4ZwR/yMy5--
--===============8727617252405195911==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography
--===============8727617252405195911==--
