Verifiable random function

In cryptography, a verifiable random function (VRF) is a public-key analogue of a keyed cryptographic hash. It is a pseudo-random function that provides publicly verifiable proofs of its outputs' correctness. Given an input value x, the owner of the secret key SK can compute the function value y = F_SK(x) and the proof p_SK(x). Using the proof and the public key $PK=g^{SK}$, everyone can check that the value y = F_SK(x) was indeed computed correctly, yet this information cannot be used to find the secret key. The concept of a VRF was introduced by Micali, Rabin, and Vadhan in 1999.

Constructions

The original construction was rather inefficient.

Later, in 2005, an efficient and practical verifiable random function was proposed by Yevgeniy Dodis and Aleksandr Yampolskiy. The following is only for intuition and is secure only when the input $x$ is from a small domain (the authors then extend it to a larger domain):

$F_{SK}(x)=e(g,g)^{1/(x+SK)}\quad {\mbox{and}}\quad p_{SK}(x)=g^{1/(x+SK)},$

where e(·,·) is a bilinear map. To verify whether $F_{SK}(x)$ was computed correctly or not, one can check if $e(g^{x}PK,p_{SK}(x))=e(g,g)$ and $e(g,p_{SK}(x))=F_{SK}(x)$.

One can also define the Dodis-Yambolskiy random function as a function $V_{x}:\{1,\dots ,d\}\to \mathbb {G}$ (where $\mathbb {G}$ is a group generated by g with prime order t) given by $$V_{x}:m\mapsto {\begin{cases}g^{\frac {1}{x+m}}{\text{ if }}x+m\neq 0{\pmod {t}}\\1_{\mathbb {G} }{\text{ elsewise}}\end{cases}}.$$

Dodis and Yampolskiy showed this is secure if it is hard to break the "decisional bilinear Diffie-Helman inversion assumption" in the group $\mathbb {G}$. The proof of security relies on a new decisional bilinear Diffie-Hellman inversion assumption, which asks given $(g,g^{x},\ldots ,g^{(x^{q})},R)$ as input to distinguish $R=e(g,g)^{1/x}$ from random.

In 2015, Hofheinz and Jager constructed a VRF which is provably secure given any member of the "(n − 1)-linear assumption family", which includes the decision linear assumption. This is the first such VRF constructed that does not depend on a "Q-type complexity assumption".

Uses and applications

VRFs provide deterministic precommitments which can be revealed at a later time using proofs which can only be generated by a private key. This is useful for providing a 1:1 mapping of low entropy inputs (e.g. names, email addresses, phone numbers) to some random values which can be committed to in advance, e.g. through a timestamping service such as a transparency log.

Unlike traditional digital signature algorithms, VRF outputs can be published publicly without being subject to a preimage attack, even if the verifier knows the public key (but not the proof). This is useful to prevent enumeration of the names/identifiers in a directory which is using a transparency system.

In cryptocurrency

The Internet Computer cryptocurrency uses a VRF to produce a decentralized random beacon whose output is unpredictable to anyone until they become available to everyone. More precisely, its protocol allows clients to agree on a VRF (i.e. a commitment to a deterministic pseudorandom sequence) and to produce one new output thereof every round by using threshold signatures and distributed key generation.

Algorand uses VRFs to perform cryptographic sortition. In this platform, every block produces a new random selection seed, and a user secretly checks whether they were selected to participate in the consensus protocol by evaluating a VRF with their secret participation key and the selection seed. (This also produces a proof, which the user can send to anyone to show that they have been selected to participate.) Thusly, accounts are selected to propose blocks for a given round. The particular VRF that Algorand uses was originally proposed by Sharon Goldberg, Moni Naor, Dimitris Papadopoulos, Leonid Reyzin, and Jan Včelák and currently undergoing standardization; Algorand's own implementation of this function has been open-source since October 2018.

In May 2020, Chainlink announced that it launched Chainlink VRF, a service that uses verifiable random functions to generate verifiable randomness on-chain. To use Chainlink VRF, a smart contract supplies a seed (which should be unpredictable to the oracles to whom it is provided), and the seed in turn is used to generate a random number that is sent back to the contract; this is published on-chain along with a proof and verified using the oracle's public key and the application's seed. Each oracle, when generating randomness, uses its own secret key.