# Different choices for randomness

## The problem

One of the critical design goals of Witnet is the unpredictability of the committees that are in charge of resolving the data requests. In order to achieve such unpredicatability committees are selected at random for every data request based on a reputation score and a public beacon.

However, deciding how that such public beacon looks is a critical component for the system. Lets take for a moment the bitcoin example, in which the public beacon is composed by the hash of the previous block. If we utilized such a beacon, the previous miner could reorder transactions, or decide which transactions to include to affect the hash of the block and therefore, its potential eligibility for future data requests.

More specifically, in Witnet the elegibility of the committee is generated using a verifiable random function (VRF) having as inputs the blockHash of the last block and the epoch,
VRF(blockHash || epoch).

As before, the use of the blockHash iincentives malicious actors to reorganize trnasactions in blocks so that the changes of being eligible increase.
Thus we need to study different mechanisms that can potentially mitigate these issues.

## Some solutions

#### 1. VRFs as randomness generators

One of the main issues with using the block hash as a beacon is that a miner can modify the resuting block hash to favor its odds in the next epoch. Therefore, one could think of utilizing something non-malleable by a miner as the input to the VRF, for instance, the epoch. The problem with this is that such an approach is predictable, and therefore the nodes would know for which epoch they would be eligible beforehand.

How can we improve upon this? Lets review what properties we need:
- Unpredictability
- Non-malleable

Those two properties are fullfilled by VRF outputs. Therefore why dont we utilize the VRF output of the previous epoch as a beacon for the current one? VRF outputs are already been transmitted between nodes to prove their eligibility. In this sense, the only thing that nodes would need to do is pin the VRF output into the block header. In short:

$Beacon_i = (VRF(Beacon_{i-1}) || sk_{i-1}) = VRF(VRF(Beacon_{i-2})|| sk_{i-2}) =$
$= ... = VRF(VRF(....(VRF(epoch_0)|| sk_0))),$

where $sk_j$ represents the secret key of the node that was elected in epoch $j$.

Such an scheme would favor unpredictability (no one knows who is going to be eligible as VRF outputs will be different for different keys) and become non-malleable, as the output of the VRF is deterministic for a given input.

#### 2. Distribute the randomness over the last blocks

Distribute the randomness over the last N blocks. The idea is to make the beacon be composed of a single bit from each of the last 32 blockhashes. This way the input of the VRF is composed of 32 bits, and a miner could influence at most one bit. This way a given miner can only influence a single bit on the following beacons. Of course one thing that needs to be discussed in this option is what to use as input in the first 31 blocks of the chain.

### VDF + VRF

In order to avoid the problom described above, on solution that can be taken into account is the uses of Verifiable Delay Functions (VRF). This functions take a prescribed time to be computed, even in parallel computations. However, this functions can be easily verified.
This characterictic of them guarantees that no maliciuos actor can influence the output since the inputs will be finalized before the VDF.

The classic example of this kind of function is finding the square root of x modules p, which implies the computation of log(p) squaring while the verification implies only one simple square.

In our case, the use of these functions would be to use thema as a complementation of the VRF. More specifically, given the las block hash H(B):

- A node *i* compiles ri = VRF(*si*|H(B)| epoch).
- With the ri recieved in the network, an R is computed, that will be the input of the VDF.
- The random value is calculated as Rand = VDF(R). This would be the value compared by the nodes as it is done now in Witnet with the VRF( blockHash| epoch).

The above contruction is just an idea of how could be integrated a VDF in the Witnet Network. (https://talk.harmony.one/t/unbiasable-randomness-generation-with-vrf-and-vdf/52)

On the other hand, the implemetation of this solutions has some drawbacks. First it is sometimes inconvinient to have such a delay for retrieveing inputs. Second, the functions usually are implemented in ASIC devices, increasing the cost.

### RANDAO
RANDAO is a DAO based Random Number Generator based on an economically incentivized commit-reveal scheme. It works as described in the following steps:

- Participants that wish to participate in the RANDAO protocol need to lock M eth in the contract.
- In the first phase, participants pick a random secret s and publish sha3(s)
- If not enough commitments have been proposed, no random number is generated for that block
- If enough commitments are proposed, participants need to publish their secret.
- If all participants publish s correctly, a function is applied over those values to get the random number
- If one participant fails to publish s, it is slashed, the locked money is distributed over those peers that published s and the random number is computed over the renamining values.
- If two or more participants fail to publish s, they are slashed, the slashed amount is distributed over the participants that published s but no random number is computed at this block height.
-
### SGX

One possibility to obtain a random Beacon is to ask a trusted hardware to generate it for us. Hardware Random Number Generators are able to obtain close to pure random numbers as they are based on physical sources like sensors that are good sources of entropy. Now, given that hardware can produce True Random Numbers, the next challenge is to provide guarantees that such a RNG has been used. That is indeed what Intel Software Guard Extensions are for.

IntelSGX provides cryptographic guarantees of the integrity of the code running inside its platform as well as the correctness of the output. This is offered thanks to the attestation and memory encryption properties. However, intelSGX has been demonstrated to be vulnerable to both side-channel and fault attacks. While the first offer little advantage to attackers when dealing with public beacons, the latter are considered a problem if the fault attack can induce predictable faults. In that scenario, an attacker hosting a public-beacon generator SGX instance could induce faults that benefit himself.

Furthermore, the economic incentives around these kind of scheme need to be well designed. SGX does not have network capabilities and thus needs to rely on the host OS to relay the information generated. If such information is public or retrieved through a side channel attack the host OS could deny relaying the beacon to the requested network. In those cases, we can expect the SGX instance hoster to have some economic penalties.