Unbiasable Randomness with VDF

The one you use for a billion dollars lottery. Not for some tiny dice games.

Biasability of Distributed RNGs

Distributed RNGs are susceptible to biasing and manipulating, including Nakamoto Consensus, Private VRFs, PVSS, and Unique Threshold Signature. They could use many setups and cryptographic schemes, but in the end, they all rely on some efficient PRNG.

Those PRNGs are so efficient that the calculation time is almost always instant, once they have the input. The quicker the calculation is, the more time they spare to cheat. They could spend this biasing time to grind and/or withhold the input or try to contact and collude with other participants.

Biasing a distributed RNG is surprisingly easy on blockchains. One can just anonymously publish a biasing contract and bribe away any of the existing distributed RNG.

if ("you can commit a valid input" && "the output is not what I want")
{
    if ("the input is not committed") {
        transfer(you, reward + slashed + bribe);
    } else {
        bribe = bribe × 2; // increase the bribe
    }
}

Verifiable Delay Function

To make an RNG truly unbiasable, the idea is to delay the calculation so the output is only known long after the input has been committed. When no one can see the output yet, no one can bias it.

Input Source

With VDF, we can have an unbiased random number using an biasable input. One can argue that using a RANDAO output as the input for a VDF will produce an unbiasable random seed.

Let's look at a biasing contract for RANDAO-VDF:

// we have all the time in the world to prepare this
let S = [s0, s1, ..sn-1] where VDF(PACK(s0, s1, ..sn-1)) = WhatIWant.

for each i in [0..n) {
    if (seeder[i].seed == s[i]) {
        transfer(seeder[i], reward + slashed + bribe);
    } else {
        // someone is not compromised, should increase the bribe
        revert; // no one gets the bribe either
    }
}

Now the RANDAO-VDF setup can be biased since the input and output of the RANDAO can be made secretly available much earlier in time.

Input Age

The key here is time. (One could guess from the name 'delay'.)

It's not how complex or decentralized the input is constructed, it's how recent the data is available that matter. The age of the data is the time elapsed from the first moment it became available. The older the data is, the more it's vulnerable to randomness prediction and manipulation.

The best way to make the data more recent, is to aggregate it from many different sources since the age of an aggregated data is the age of the most recent source.

Block hash is a valuable source of recent data, since changing any part of a block will create an avalanche effect to every following block hash.

Hence, to know the next

$N$ block hashes in advance, one must (A) control 100% sealers of those

$N$ blocks and (B) isolate the network in entirely

$N$ block time, i.e. no transaction from outside can be included. Effectively making a blockchain non-operational for the whole duration.

Setup

Requirements

The VDF implementation of POA Network and Harmony using class groups based on approaches described in the following papers:

• Simple Verifiable Delay Functions. Pietrzak, 2018
• Efficient Verifiable Delay Functions. Wesolowski, 2018

Using class groups allows the VDF proof to be public verifiable without the trusted setup.

Reward System

Rewards will be given to VDF evaluators (or miners) to incentivize the public computation. The reward system must have the following properties:

• The quicker the result is submitted the more reward it earns.
• Re-submitting the same result is not beneficial.
• No one can steal other work.

Design

The VDF RNG has 2 phases, which is designed to:

• Attract better and more powerful VDF evaluator.
• Incentivize multiple VDF evaluators instead of just the best one.
• Weed out the Class Group failure cases.

Challenge

The RNG process is started when a challenger submits a request with:

• $T$: number of blocks for the whole process.
• $UserEntropy$: optional user entropy data.

Evaluation

VDF evaluators race for the rewards by calculating the challenge submitted. When an evaluator finishes her job and found the VDF result along with the

$Output$, she will submit her

$Commitment=Hash(Address+Output)$ to the chain, but not the

$Output$ itself.

Verfication

After the evaluation time is finished,

$Output$ can be submitted.

$Output$ is verified by using the pre-compiled contract, supported by the consensus.

If there are more than 1 valid

$Output$s, the random number cannot be secured. Challenger must request a new random process since there's no reliable value to be used.

If there is only 1 valid

$Output$ submitted in the Verification phase, the random number is successfully generated. Anyone can use the random number after the Verification phase ends, which is

$T$ blocks after the Challenge transaction is confirmed.

Rewards

Let's call

$B_i$ is the block that the

$i^{th}$ success evaluator has her Commitment submitted during the Evaluation phase.

After the Verification phase is finished with success, the valid

$Output$ will be used on each Commitment to verify and pay each evaluator with the following rate of reward:

$R_i=\sum _{i=0}^{n-1}{\mathrm{\Delta }}_i\times r^i$

Where r is the reduction rate and

${\mathrm{\Delta }}_i=B_{i+1}-B_i$.

To prevent early evaluator griefing attack, r must have this proved condition:

$0<r<\frac{1}{2}$

This reward system has the following properties:

• The sooner the Commitment is submitted, the more reward evaluator will get.
• The later the next Commitment is submitted, the more reward the previous evaluator will get.
• Re-committing the same
  $Output$ (with the same or different Commitment) will cause the evaluator losing her reward.
• Two or more evaluators committing in the same block will have the same reward.

Rationale

A good VDF system should attract calculation power from the public to secure the network, as well as incentivize them to continuously works. Unlike PoW where there's a random chance for everyone, VDF calculation doesn't take chance, the fastest one always wins. When there's always the same winner, runner-ups will leave. That's why we should also reward the runner-up and some after that.

To have the random number truely unbiasable, the VDF result should always be the same whether who does the calculation. Since the result is the same, revealing it too early will let others copy your work, and get the rewards without working at all. The hash-commit and reveal-verify mechanism allow honest worker will get rewards they deserve.

The rewards system where the more people committing correct results after you do, the less prize you will get, prevent early evaluator griefing attack. Submitting the same result, or sharing it with your accomplices does not bring any profit, but only loosing more of your prize.

Security Parameters

• $MinSubmission$: this is a protocol configurable param for a minimum of VDF verificators to maintain a stable network.
• $MaxSpeed$: speed of the all-time fastest VDF evaluation, in
  $iteration/block$.
• $MinSpeed$: average speed of recent
  $MinSubmissio{n}^{th}$ evaluator
• $t$: number of the iteration for the VDF evaluation. We want to have the
  $t$ so even the slowest of
  $MinSubmission$ evaluators can have rewards, so
  $t=T_e\times MinSpeed$ with
  $T_e$ is the number of block for evaluation phase.

To prevent pre-image grinding attack, the

$UserEntropy$ has to be submitted before

$T_0=\frac{t}{MaxSpeed}\ge InputAge$

So the

$T_e$ must be chosen so that:

$T_e\ge InputAge\times \frac{MaxSpeed}{MinSpeed}$

In PoW consensus where miners don't have any spare time to delay the winning block propagation, their only option to bias the result is to give up their winning block. InputAge as short as a block time can give reasonable security against the VDF pre-image attack.

With PoS consensus, miners have at least a block time to delay the block propagation. InputAge of 2 blocks is safe against a single miner pre-image attacks. For security against n-miners colluding pre-image attack, InputAge should not be less than 1+n blocks.

Class Group Failure Handling

The verification phase allows honest

$Output$ to be submitted after the false-positive

$Output$ is successfully verified.

A challenge with more than one valid

$Output$ is a failure case of Class Group setup and safely discarded. Challenger is recommended to request for another RNG challenge.

Attack Vectors

Pre-image attack

Pre-image attack can happens when challenge request doesn't follow the security guideline of

$T_e\ge InputAge\times \frac{MaxSpeed}{MinSpeed}$. Or the

$MaxSpeed$ is greatly incorrect due to either:

• Attacker has secretly developed a superior ASIC or FPGA for the VDF calculation.
• The reward system is not attractive enough for the top tier VDF evaluators.

Censorship attack

Miners can censor the Commitment transaction to get the most out of the reward share. This only affects the temporary reward distribution, not the biasiability of the mechanism.

Early Evaluators Griefing attacks

Early evaluators can spam the Commitment right before the next evaluator submit their works to cut down their rewards. This also cut down their own reward, so it's not economically efficient to keep attacking for a long time.

Late Evaluators Griefing attacks

Later evaluators can also spam the Commitment to cut down rewards of all previous evaluators. This also removes their own reward, so it's not economically efficient to keep attacking a long time.

Bribing Attacks

Early evaluators can bribe late evaluators not to submit their work, in exchange for more reward, resulting in more reward is distributed as a whole. This attack does not affect the biasability of the result. The only harm is done is more reward is distributed by the system, causing more inflation.

Future Development

With Watermarking Proof implemented, we can merge the Evaluation and Verification to one phase, remove the Commitment transactions and prevent early evaluator griefing attack.