Caucus subprotocol of Fantomette


#1

The Caucus protocol for leader election and networked randomness in section 5 of the Fantomette paper has interesting parallels with Al’s randomness proposal.

In Caucus, randomness outputs change every block and VRFs are evaluated on the previous randomness output R_{n-1}, but if nobody wins then nodes update the randomness with a VDF. In other words, all but a few nodes start running the VDF every round, which sounds wasteful, although not as wasteful as proof-of-work. I suppose nodes can simply not compute the VDF and participate only when they win by VRF, making them slightly later after VDF rounds. I believe the VDF’s proof could be bound to a public key held by whoever computed the VDF, so that rewards accrue to whoever publishes a VDF output.

An interesting point here is that VDFs are sensitive to the ratio between their delay and the time period in which they collect their input values, which normally results in running them for long periods, like three hours in the Ethereum proposal. There is only one input in Caucus’ cases, which only relatively few nodes can bias and only by equivocating or by through choice of the previous block. As a result, Caucus has extremely short VDF delays.

Actually the paper hints that VDF runs should be rare, but if the parameters were adjusted to make VDF runs rarer by making VRF wins easier, then attackers would increase their odds of multiple VRF simultaneous wins, and correspondingly more choices for biasing the randomness.

Also, they bootstrap Caucus with PVSS which sounds reasonable. We might do something similar for bootstrap any similar randomness scheme, including Al’s idea.

In Fantomette itself in section 6, they reduce this bias due to choosing the previous block with a fork-choice rule, inspired by GHOST, that favors blocks “well connected”, but that makes the previous block a deterministic choice of the referenced previous blocks.

I’m actually not convinced by their arguments on reducing bias due to previous block selection. I’d expect some time parameter t so that VRFs were evaluated on the randomness from t blocks back, so the fork-choice rule would have more time to limit choices, i.e. R_n := R_{n-t} xor VRF_sk(R_{n-t}), like in Al’s randomness proposal. Afaik, there is no reason for the xor here either since R_n := VRF_sk(R_{n-t}) seemingly has the same properties.


#2

Looks interesting, but is it enough to have a secure leader election protocol for a finality gadget? They do not prove eventual consistency, at least not in section 5. There is a fork choice rule they specify in section 6, but it seems fairly specific to their consensus, I have not looked too much into that yet.


#3

We’re considering randomness rather different from RANDAO plus a slow VDF but that actually looks similarly compatible with a fast VDF. We’ll think about this style of fast VDF some. We can go through the proofs some too, partially to see if we believe them, but mostly to look for evidence that Al’s ideas or similar make sense, and to see if this is specific to leader election, as opposed to say committee formation.

As an aside, Justin Drake has an informative post about choosing VDF delays:


And their overall VDF scheme is described in https://ethresear.ch/t/minimal-vdf-randomness-beacon/3566


#4

Al and I discussed randomness today, including Caucus. We’re fairly nervous about the randomness being based on the previous blocks randomness because it gives runs of block winners more power, and it gives block producers have an inventive to build on different chains.

We discussed if the current block’s VRF seed could be based on the VRF output n blocks in the past. If so, we should not base the VDF off this past block because doing so gives too much time to evaluate the VDF, or else makes the VDFs too expensive and unpredictable. In other words, we require sequences of VDF evaluations to actually be sequential.

Instead, we’d want a “block/VRF skip” VDF seeded by the previous block’s VRF, or all VRFs between 1 and n blocks ago, as well as the most recent VDF output that triggered a “block/VRF skip”. In other words, we’d have a “separate VDF track” for skipping blocks.

In this scheme, we do not benefit from the unbiasability VDFs normally grant, but Caucus’s unbiasability arguments look pretty suspect too. We not sure if this actually beats measuring relative time and accounting for network time delays much.

Also Al pointed out you might want “exponential backoff” when skipping blocks. These exponential time delay increases would increase how much drops in block production slowed down the chain.

I’ll write up separate notes on our discussions around proving that nodes do not skip their VRF wins. Those protections help against chain speed attacks, but do not help us here because a block producer could always ensure their block never made it into the chain but instead only exists as an uncle.