Verifiable random function

Silvio Micali, Michael Rabin and Salil Vadhan originally developed the concept of verifiable random functions in 1999. Verifiable random functions are public key-versions of keyed cryptographic hashes. This means that anyone with a public key can verify the correctness of any hash that was created by holders of secret keys and their computed hashes. The ability to publicly verify the correctness of hash calculations without a way to discover the secret key makes verifiable random functions useful for preventing dictionary attacks on data structures that are hash based. Verifiable random functions are used in applications requiring key transparency, Domain Name System Security Extensions (DNSSEC), and cryptocurrencies.

History

Algorand was one of the pioneers to use the verifiable random function (VRF) to perform secret cryptographic sortition of committees for their blockchains consensus protocol (a byzantine agreement protocol). After successfully implementing the verifiable random function in their blockchain protocol other cryptocurrency began adopting the verifiable random function for leader or committee selection.

Syntax and properties

Their are three parts of a verifiable random function: keygen, evaluate, and verify. The keygen (r) uses a random input for the algorithmic generation of a verification key (VK) and a secret key (SK) pair. The evaluation (Y, ⍴) portion of verifiable random functions is an algorithm taking the secret key (SK) and a message X as an input and producing a pseudorandom output string Y and a proof ⍴. The final verification (VK, X, Y, ⍴) step of verifiable random functions uses another algorithm taking the verification key (VK), the massage X, the output Y, and the proof ⍴ as inputs. The verification algorithm will give an output of 1 if it determines Y is an output produced by the inputs of the secret key (SK) and message X by the evaluation algorithm.