Oct 09, 2018
By: Sergey Gorbunov
A Verifiable Random Function (VRF) is a cryptographic primitive that maps inputs to verifiable pseudorandom outputs. VRFs were Introduced by Micali (founder of Algorand), Rabin, and Vadhan in ’99. Today the primitive is used in various cryptographic schemes, protocols, and systems.
Algorand pioneered the use of VRF to perform secret cryptographic sortition to select committees to run the consensus protocol. This allows the Algorand blockchain to achieve the scale and performance necessary to support millions of users. By now, other blockchain projects are using the idea in the consensus protocols to perform leader or committee selection.
In this blog, we will cover the basics of VRF; discuss how its key properties allow for unique and secure committee selection in the Algorand blockchain, and expand on the specific VRF we chose to implement at Algorand.
A VRF is a triple of algorithms Keygen, Evaluate, and Verify.
Informally, for a fixed key-pair and an inputX, a VRF produces a unique pseudorandom verifiable output.
It is interesting to note that while VRF is similar to a signature scheme, it has crucial distinctions:
a) in a signature scheme, many possible valid signatures may exist for a given input, and
b) signatures are unpredictable overall, but some of the signature bits may be highly predictable. VRF outputs satisfy a stronger pseudo-randomness property.
Recall that at the core of the Algorand Blockchain is a fast Byzantine Agreement protocol. However, the agreement is not performed between all users in the network. Instead, it is confined to a small randomly chosen committee of users for each round.
Now, each user in the Algorand network holds a secret key SK, while her verification key VK is publicly known to everyone. Each user participating in the Algorand network wants to decide if she should be in the committee to run Byzantine Agreement for block r, she needs to do the following:
If the above check passes, then the user holds a proof consisting of values (Y, ⍴) which validates their committee membership for block r. Given (Y, ⍴) and the user’s verification key VK, anyone can verify that Y is a valid unique output and that it falls within a desired range (hence, validating that the user holding VK was indeed chosen to serve on the committee for block r).
Further notes worth addressing:
Algorand is committed to true decentralization. Hence, we believe it is important to allow anyone to audit our core code, report issues, and propose changes.
Today we are happy to announce the open-source version of our VRF implementation. We forked the widely popular libsodium cryptographic library and extended it with our implementation.
We chose to implement the VRF which is currently undergoing standardization, by Sharon Goldberg, Moni Naor, Dimitris Papadopoulos, Leonid Reyzin, and Jan Včelák.
Standardization of cryptographic primitives is just as important as open-source deployment in allowing third parties to discuss and agree on specifics of their implementations details.
Please take a look and let us know what you think!