Minimal VDF randomness beacon

random-number-generator

#22

The amount of time the randomness is known before it is used is called the “lookahead”. People running the commodity ASIC have one epoch of lookahead. An attacker with hardware that is A_{max} times faster than the commodity ASIC has A_{max} epochs of lookahead.

Adaptive attacks (e.g. DoS, bribing, …) on proposers and committees is largely orthogonal to the randomness beacon for two reasons:

  1. Hardening against adaptive attacks is done with “private elections” (and hence private lookahead). There are various schemes (e.g. see my proposed scheme using ring signatures) that work regardless of the randomness beacon.
  2. Adaptive attacks (especially networking DoS attacks) are possible even for randomness beacons with small public lookahead (e.g. Dfinity’s scheme).

PoW and Algorand’s cryptographic sortition are two private election schemes but neither is unbiasable.


#23

Thanks for the great design and talk, Justin. I’m super curious about the design of the MPC for trustless construction of the RSA modulus. Is that described in more detail anywhere, at this point?

I think it’s worth pointing out, with Algorand, that while the last potential revealer can bias the result, there is no incentive for them to do so, and there will be many applications of random beacons where that is the case. It would only make sense for them to do so if the outcome they can predict from their last revelation would be unfavorable to them.


#24

The Ligero team is developing and implementing the MPC. They will present it to various MPC experts on Feb 3 at “VDF day” (a research event organised by the Ethereum Foundation and Filecoin). They are working towards a formal description of the protocol with a proof of security.

while the last potential revealer can bias the result, there is no incentive for them to do so

The analysis for Algorand is similar to that of RANDAO. A last revealer has the incentive to bias the randomness (by not revealing) when that makes them the last revealer (with sufficiently high probability) for the next 2+ slots. An attacker can also somewhat manipulate the committee selection process to his advantage.


#25

A last revealer has the incentive to bias the randomness (by not revealing) when that makes them the last revealer (with sufficiently high probability) for the next 2+ slots

You mean when he has the option to either be the last revealer of the last committee round, or the next leader? I guess it’s possible, if his stake is large enough, and depending on the reward structure.

This consideration in isolation would imply that the leader reward should be lower than the rewards for the last-round committee members!

The Ligero team is developing and implementing the MPC.

Can’t wait! Any hints on the MPC framework they’re using, or other aspects of their approach?


#26

A large enough attacker can exploit the randomness to facilitate a takeover of the system with less total stake. Micro-incentivisation cannot fix this because there are significantly larger external incentives at play. (Think of attacks by a government, or someone who has a huge short position on Algorand.)


#27

You’re right. I wonder whether they’ve included that in their analysis. It does seem like it would change the calculations in Appendix A of this paper.