# Minimal VDF randomness beacon

It loos like one can actually design a threshold signature scheme where half of the good guys guys can go off line

A simple example:

1. You have less than 1/3 N bad guys
2. The random beacon R is “1/3 N out of N” threshold signature of the epoch number.
3. Everyone first pre-commits a hash of the signature share (pre-commit phase)
4. Everyone reveals the signature share S_i (reveal phase)
5. Once 1/3N signature shares are revealed they are combined into a threshold signature.

In this scheme only half of the good guys need to be online in order for the system to work …
Bad guys can not derive the number unless at least one good guy reveals his share

I guess you assume all live validators will participate in every round. If you use committees (like of size 128 as proposed above), the chances of failure are not negligible.

With the VDF beacon you only need 1 honest validator per committee of size 128. With your proposed threshold signatures you need at least 43 honest validators per committee of size 128.
With a third of the validators being honest and live, the chance to get a bad committee is around 50%. With half of the validators honest and alive the chance is 0.006% (according to my quick and dirty excel sheet).

It will do better with bigger committees, but that will increase the overhead.

2 Likes

Will VDF output & evaluation proof be part of crystallized state?

Also, what happens in an event all proposers fail to include R1 or its proof during epoch 1? When epoch 2 starts, the proposers will have to include R2 right?

Also, @JustinDrake have you given any thoughts to Tor’s randomness beacon? I know the use case is different but how does it compare to the other blockchains’ randomness beacons and would it be possible to analyze it to determine if it could be an alternate candidate in addition to the current RANDAO+VDF scheme.

This may be either good or very bad.

For VRF if there is a split between Europe and the States, there will be two different random numbers generated R_1 and R_2 and this is bad. There will be no way to put R_1 and R_2 together again! You will have an unfixable fork!

Therefore, the fact that you only need one good guy to generate a random number can be a catastrophe under some circumstances.

Basically in case of a network split you will end up with two groups of good guys generating two different random numbers, these two random numbers leading to a selection of two different sets of validators and then the entire system irrecoverably splitting and crashing!

Contrary to that, the threshold signature algorithm will stall for the duration of the split, and then work again perfectly, which is actually exactly the behavior you want!

1 Like

In the family of VDFs we are considering there are at least 4 setups which could work in practice. Two are fully trustless (class groups, nothing-up-my-sleeve RSA moduli), one is quasi-trustless (RSA MPC), and one is trusted-in-theory-but-ok-in-practice (RSA-2048). IMO the best-case scenario is for the RSA MPC to be feasible.

(As a side note, the modulus is always public. It’s the factorisation of the modulus that should be secret.)

Note that the ceremony for an RSA modulus uses different crypto to the Powers of Tao ceremony.

As indicated by @denett this does not work because the sampling process will weaken your honesty assumption. (Dfinity’s sampling weakens the global 2/3 honesty to 1/2 local honesty.) Sampling is required because the Distributed Key Generation (DKG) scales quadratically with the number of participants, and in practice you can’t get much more than 1,000 participants.

Another thing to consider is that there are two ways in which the Dfinity beacon can fail. Citing the whitepaper: “We treat the two failures (predicting and aborting) equally”. By improving liveness you make the readomness beacon easier to predict.

Finally, the RANDAO + VDF approach allows for arbitrarily low liveness assumptions. (For example, we could have a 1% liveness assumption by making the RANDAO epoch longer.)

In practice the actual randomness (as returned by the randomness opcode) will be a 32-byte hash of the VDF output. As such, the VDF outputs and the evaluation proofs are just “witnesses” and do need to be part of the beacon state. As for VDF output hashes, it may make sense to store the last n (e.g. n = 1024) in the state and push the rest to a double-batched Merkle accumulator.

The VDF output r_i should get included by epoch i + A_{max} + 1. From the point of view of the application layer, the randomness opcode will return `0x0` until r_i is included onchain. So any delay should be handled by the application.

From the point of view of RANDAO using the r_i we can set N be to conservative, e.g. N = A_{max} + 3. In case of a catastrophic failure we need the spec to specify some sort of behaviour. My gut feel is that gracefully falling back to RANDAO is perfectly OK.

I had a quick look and it seems to be basically RANDAO.

Right, forkfulness at the RANDAO level is a grinding opportunity for RANDAO + VDF. Applications that need to protect themselves from this grinding opportunity (e.g. billion-dollar lotteries) need to wait until Casper finality of the randomness to get the similar guarantees to Dfinity/Tendermint.

Strong liveness allows dApps (if they so choose to) to operate in the context of weak finality when strong finality is not available. In other words, strong liveness pushes the “safety vs liveness” tradeoff to the application layer instead of stalling all dApps unnecessarily when finality cannot be reached.

4 Likes

Is there any known ongoing research in evaluating and applying permutation polynomials over finite fields as VDFs? Why are not they considered as potential candidates @JustinDrake? Is there some strong security assumption which is kinda prohibitive? Or is it just too complex for the EVM?

I fail to understand why would the fork be unfixable and why would the system crash? As far as I know, Eth 2.0 has the “bleed out” model for offline validators, which gives us around 12 days to resolve the partition? Only after that period is when the fork will become permanent, and the system will not crush in any of these two cases.

I generally favor consistency over availability (that’s why I like e.g. Dfinity’s beacon or Tendermint consensus), but there’s a really strong argument in favor of Ethereum’s (and Bitcoin’s) “WW3-proof” approach - if you keep your assets on a blockchain, you want them to be available all the time, especially if there’s some sort of catastrophe going on. Unfortunately, Dfinity and Tendermint can not guarantee that. How do you argue that?

2 Likes

Generating two different numbers when there is a chain split is not a problem when the chain’s have not yet been finalized. After a reconnect, one chain can win and the other is discarded.

I think the splitting does not depend on the random number beacon, but is a design choice of Casper. Even with your beacon the chain can split, because you will only need one third of the validators on every chain to continue. After Casper slashed validators on the other side of the ocean for not participating, the random numbers will diverge en we might end up with two finalized blockchains.

If you use the 1/2N threshold, you can not have a chain split, but the chain can halt when less than half of the validators are good and online.

1 Like

The permutation polynomials have been considered:

1. Sloth: Only provides a constant gap between evaluation time and verification time. For it to be practical to build a Sloth VDF ASIC the multiplier needs to be of reasonable size (say, at most 4096 bits, yielding a ~2048 gap). This 2048 gap only applies if the evaluator and verifier run on the same hardware, making CPU verifiers useless in practice (unless you use intermediate values, but then bandwidth becomes an issue). This means you now need VDF ASICs for verifiers as well. You could have a cryptoeconomic scheme (e.g. see here) but a cryptographic scheme is clearly preferable (less trust, less complexity).
2. MiMC: Basically the same as Sloth but worse: smaller gap for equivalently sized multipliers, and more complex intermediate non-arithmetic operations.
3. Guralnick and Muller: I was told by various experts (Dan Boneh, Benedikt Bünz) that these polynomials are too risky because no one has seriously tried to break them. A promising approach, though.
4. Sloth++ with SNARKs: Based on the research on ASIC multipliers my guess is that the basic step in Sloth++ (e.g. 256-bit modular squaring) can be done in ~1 nanosecond. So the SNARK prover stands no chance to keep up unless it is itself implemented as an ASIC. It’s unclear building a SNARK ASIC that is fast enough is practical.
5. Sloth++ with STARKs: This is currently our best candidate for a quantum-secure VDF. The situation is similar to the above except 1) STARKs are quantum-secure, 2) STARKs provers are faster, 3) recursive STARKs are harder 4) STARKs are not as mature.

Is there a permutation polynomial you think should be (re)considered?

The EVM has no bearing on VDFs (other than the randomness opcode yielding hashes of VDF outputs). The VDF logic is implemented at the consensus layer.

8 Likes

Wow! what a thorough summary! Thanks a lot! I do not have any specific attack or proposition yet but really like Guralnick and Muller polynomials. I want to have a closer look at them in the next few weeks.

Can you illustrate how this is going to work even if Casper is added to the picture?

My understanding is that if there is a network split, two random numbers are generated.
Then these two numbers will cause different block proposers to be selected on two different sides of the split - correct? In this case I am not sure how Casper validators should behave. Casper validators assume that block proposals are made by valid proposer, but if there are two different sets of valid block proposers, I am not sure Casper validators can help to resolve it.

May be it is going to work, the problem will be that the system may end up so complex, that current ETH developers - the guys that develop geth, parity, cpp-ethereum etc. will not be able to understand it or debug it … If something goes wrong, they will have to analyze potential interplay of validators, proposers, network splits etc.

I am keeping my money on the PoW network!!!

I suggest we take this discussion offline—feel free to DM me—as it is not specific to VDFs, or even randomness beacons.

It is natural for general-purpose consensus protocols to favour liveness. (In that sense, Dfinity got it “wrong”.) @naterush puts it eloquently:

An available consensus protocol (that is aware of what is safe) can simulate a consistent one (just by only showing finalized blocks), but not the other way around.

Casper FFG is that layer of detectable safety that dApps can rely upon (if required). In other words, a consensus protocol that favours availability is generic in the sense that it pushes the safety vs liveness tradeoff to the application layer:

• Liveness is available out of the box for dApps that require liveness.
• Safety is available by filtering out non-finalised blocks for dApps that require safety.

Casper validators should subjectively follow the fork choice rule.

3 Likes

You could fund the ASIC as a public good with liberal radicalism!

Why wouldn’t you use VDF with say, a blockhash N blocks ago? There are probably issues around using a public piece of data for an input to the VDF.

I guess it may be to do with that other proposers may jump in to someone else’s slot and use the public piece of data to compute the VDF, potentially more quickly the assigned proposer. I’m asking because Harbour MVP are looking to use this (with PoW for the mean time). FMI see here.

We want the beacon’s safety to fallback to RANDAO if the VDF is (partially or fully) broken. Blockhashes are a much weaker fallback than RANDAO. Also we want to launch the beacon chain in 2019 and the VDF ASICs will not be ready until 2020, so RANDAO is a bootstrapping mechanism.

2 Likes

If a bad guy can do VDF that is Amax times faster, will this give the bad guy plenty time to prepare a DDoS attack against committee member at the future epoch?

1 Like

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.

3 Likes

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.

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.