[zapps-wg] Randomness Beacon

Fri Feb 16 12:10:47 EST 2018

Right, of course, I forgot to mention that the sources of entropy should be 
extracted at the same time, so an atacker would need to manipulate one source 
and predict the rest.

Also, I forgot to mention another possible source: the Tor directory 
authorities use a multiparty computation scheme to produce a random value each 
day, to be used by the onion service protocol v3. Maybe it would be worth 
considering it.

El viernes, 16 de febrero de 2018 18:00:54 (CET) usted escribió:
> If you add many sources and mix it together, it doesn't necessarily
> force an adversary to compromise all of them, they could just manage
> to compromise one and adaptively influence the output based on the
> output of the others. Adding sources arbitrarily doesn't increase
> confidence on its own.
> 
> Bitcoin block with a delay function gives us a pretty good one, since
> we can argue it would require enormous computing power and/or a large
> block withholding attack to influence the outcome in any meaningful
> way. Once you have a single good beacon, I'm worried that our
> (potentially arbitrary) choice from the countless other potential
> beacons harms analysis.
> 
> Sean
> 
> On Fri, Feb 16, 2018 at 9:33 AM,  <mmarco at unizar.es> wrote:
> > In order to reduce the probability of a powerful adversary influencing the
> > beacon, I would propose to use several sources of entropy, mixing them
> > together (maybe concatenating and hashing) and use the result as a seed
> > for a PRNG. The mentioned bitcoin block could be one of those sources,
> > but we can also add more. Some ideas:
> > 
> > - Results of sports competitions (i.e.: we commit to use the results of
> > the
> > NBA playoffs, or something like that)
> > - Values of several stock markets at a given future date.
> > - Some meteorological information, like "the maximum temperature reached
> > in
> > these cities in this given future date, as given by the official daily
> > report of these organizations.
> > - Some astronomical phenomena: things like solar activity at a given
> > future
> > instant (again, as reported by a specific set of observatories that
> > regularly reports those things), radiation of a specific pulsar...
> > - number of births/deaths/marriages... in a given set of countries/cities/
> > whatever (as reported by the corresponding institutions...)
> > 
> > Of course, we need to be very specific in advance about how these pieces
> > of
> > information will be collected and represented. But once done that, each
> > one of them would add extra entropy. That way,  an adversary that wants
> > to predict or influence the result of the beacon, would need a huge
> > social power to manipulate both sport competitions, stock markets,
> > scientific institutions, statistical services... And even then, the
> > meteorological/astronomical reports could only be manipulated to a
> > limited extent (it would be too evident if the maximum reported
> > temperature differs more than a few degrees to the one that people
> > actually experienced in that place).
> > 
> > 
> > El viernes, 16 de febrero de 2018 0:37:05 (CET) Sean Bowe via zapps-wg
> > 
> > escribió:
> >> The Powers of Tau security proof (see
> >> https://eprint.iacr.org/2017/1050) holds in the "random beacon model,"
> >> meaning that we must apply a random beacon at the end of the ceremony.
> >> It's not good enough to use (say) a hash of the transcript, because of
> >> adaptive attacks (the last participant could predict the beacon
> >> output). We must apply a beacon that is queried after the ceremony has
> >> completed.
> >> 
> >> There is some good news on this front:
> >> 
> >> 1. We *can* query reasonably secure beacons. More on that later.
> >> 2. Even if the beacon is partially controlled by an adversary, we only
> >> lose a bit of security for every bit of the beacon output that is
> >> influenced by the adversary. This means our beacon could be somewhat
> >> broken and we'll live in acceptable security bounds.
> >> 3. Even if the beacon is _totally_ insecure, it may not even matter
> >> because we may be able to prove the MPC is secure using the same
> >> assumptions the proving system itself uses. We haven't had time to
> >> write a security proof of this yet.
> >> 4. Even if we choose a _totally_ insecure beacon, you can just apply
> >> your own beacon instead (one that you're more confident in, or perhaps
> >> the result of a random coinflip protocol depending on what you're
> >> doing).
> >> 
> >> But, let's choose a pretty good beacon anyway. Some notes on that:
> >> 
> >> * There is a large space of possible choices for a beacon, so it's
> >> important that we choose the most obvious and reliable one we can
> >> think of.
> >> * It's important that we choose when we intend to query it, before we do
> >> so. * The result of the beacon (and how the beacon is applied to the
> >> parameters, such as what PRNG we use, and the code) needs to be
> >> determined before we query the beacon.
> >> * Since we could choose multiple beacons (and adaptively select from
> >> them) we need to publish our choice of a beacon widely, using
> >> signatures and social media, so that proof we had attempted to do so
> >> would be easy to find.
> >> * Anything else?
> >> 
> >> So, what beacon should we use? I'm borrowing my recommendation from
> >> advice given by Joseph Bonneau.
> >> 
> >> I think that we should select a Bitcoin block height (in advance) and
> >> iteratively SHA256 the eventual block (hash or header) n times to
> >> produce the seed of a ChaCha20 PRNG, which is then used to apply the
> >> beacon to the parameters. This iterative function is not intended to
> >> be a proof-of-work function but instead a "delay function," so it is
> >> deliberately not parallelizable. As the time required for a powerful
> >> adversary to compute the delay function grows (with respect to the
> >> average time between blocks) we become more and more confident the
> >> result could not be significantly influenced.
> >> 
> >> How large should n be? I think n=2^40 would be enough, since even if
> >> we're off by a couple orders of magnitude the adversary cannot
> >> influence enough bits of the result for it to really matter.
> >> 
> >> Other questions include: How should we choose the block height? Should
> >> we hash the header or the block hash or even the whole block?
> >> 
> >> Sean

Type: application/pgp-signature
Size: 833 bytes
Desc: This is a digitally signed message part.
URL: </pipermail/zapps-wg/attachments/20180216/90c72179/attachment.sig>