Random Number Generation functionality

[aesedepece]

This is the discussion thread for an eventual Witnet Improvement Proposal introducing Random Number Generation (RNG) functionality.

Just in the same way as price feeds are the fundamental oracle-based building block for many DeFi protocols RNGs are
quickly becoming a keystone building block for non-fungible tokens (NFTs).

Many use cases are arising in which the smart contracts generating the NFTs are in need of reliable and tamper-proof
random inputs for their generative algorithms ensuring the "uniqueness" of each piece. That is, they need to randomly
assign a distinguishable set of scarce attributes or traits to each newly minted NFT unit.

The case for oracle-powered RNGs expands beyond NFTs, as many other constructs also benefit from random inputs, e.g.
in the area of gaming, lotteries, gambling, random committee selection, etc.

Due to the robustness and flexibility of the crowd-attestation mechanism of the Witnet protocol, there is a huge
opportunity to add RNG capabilities to it with very little and self-contained changes.

In particular, the mechanism we are trying to introduce consists on a new type of data request in which no external data
sources are queried, and nodes are instead required to secretly commit secret sequences of bytes. The rest of the
protocol follows in the traditional way, with the only addition of a new reducer function that concatenates the
revealed values in a deterministic order and hashes the sequence together so as to produce a single, uniform
and pseudo-random output that will be used as the result of the request.

Due to the overlap of Witnet's inherent commitment scheme with this last aggregation step, there is no need for the
committed bytes to be verifiably random. Under the assumptions of stock hashing functions, even if the committers
collude around crafting their commitments in such a way that the output is favorable to them, as long as 1 single
committer remains independent and commits a value that is secret to the rest, the final result will hold the desired
randomness properties.

[drcpu-github]

Cool. A small technical summary would probably be a good idea to start the discussion?

[aesedepece]

I've updated the message above to bring some arguments to the table.

[drcpu-github]

I assume that blocks with a tally containing a generated random number are checked for validity? In other words, all other nodes in the network will check whether the revealed values are added in the correct order and afterwards hashed correctly?

If the node operators can just submit any number (e.g. it does not need to be derived from a certain seed), does that not weaken the randomness because if a number of operators collude, the range of randomness is decreased?

I wonder whether the fact that you can technically calculate the random value one epoch before it is included in a block (and a couple of epochs before it is sent over the bridge) can be abused. I assume smart contract developers will need to take that into account.

[aesedepece]

Your assumption is correct. As per the current protocol, tallies don't have a verification algorithm per se. Every validator produces the tallies from the reveals on their own and check whether the tallies in a block candidate have a 1:1 byte match with the locally generated ones.

It is true that in the scenario of N-1 colluding witnesses, the 1 that didn't collude has some power to control the diversity of possible outputs (e.g. by always reporting a fixed value) because the diversity of possible outputs for a hash function is always the smaller of two numbers: the actual input size and a fixed output size. But even so, as the non-colluder doesn't know the identities nor the values to be committed by the colluders, they cannot really predict the output, which may be not that "unique" but will still be uniform. Moreover, without any guarantee of success, there's no real incentive to even try to perform such trickery. Also note that the N-1 security assumption is actually much higher than our general BFT assumption, i.e. "2/3rds of ARS is honest".

On your third point: yes! the random value can be "predicted" as soon as all committed values are revealed. Can this be exploited? Only if the consumer contract does a very poor job. Imagine for example a lottery: this can be an issue if the contract keeps issuing tickets after the randomness is requested. As long as ticket selling stops right before or at the same time as the randomness is requested, you are fine. This is a common requirement to all asynchronous randomness sources (example)

[drcpu-github]

My main issue with node operators being able to submit any value they like is not that the output can be predicted or manipulated, but rather that certain outputs basically don't exist. If we think about a lottery with a number of tickets distributed and each ticket being assigned a certain value that needs to be drawn to win, this would mean some tickets cannot ever win. It is technically not predictable which tickets cannot win, but it still seems to me that not every ticket having an equal chance of winning could be a problem?

[aesedepece]

The thing is that uniformity of the output is still guaranteed, so it's perfectly fine for any use case in which the range is orders of magnitude smaller than 2^256, e.g. lotteries.