Algorand Releases First Open-Source Code: Verifiable Random Function

Part I

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.

VRF Syntax and Properties

A VRF is a triple of algorithms Keygen, Evaluate, and Verify.

• Keygen(r) → (VK, SK). On a random input, the key generation algorithm produces a verification key VK and a secret key SK pair.
• Evaluate(SK, X) → (Y, ⍴). The evaluation algorithm takes as input the secret key SK, a message X and produces a pseudorandom output string Y and a proof ⍴.
• Verify(VK, X, Y, ⍴) → 0/1. The verification algorithm takes as input the verification key VK, the message X, the output Y and the proof ⍴. It outputs 1 if and only if it verifies that Y is the output produced by the evaluation algorithm on inputs SK and X.

Informally, for a fixed key-pair and an input X, a VRF produces a unique pseudorandom verifiable output.

More technically:

• The output Y is unique. That is, it’s impossible to find another output (together with a valid proof) for a given key-pair (VK, SK) and input X.
• The output Y is pseudorandom, which means that it looks “random” to any third party that does not see the associated proof ⍴. (Note, that given the proof ⍴, it’s easy to distinguish Y from a random output by invoking the verification algorithm and checking the result).
• The above properties should hold even if a the key-pair (VK, SK) is adversarially chosen by the user.

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.

VRF use in the Algorand Blockchain

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:

1. Compute Evaluate(SK, Qr) → (Y, ⍴). Here, Qr is a “magic” seed string that is available to everyone in the system.
2. Check that Y falls within a certain range [0, P] that depends on the stake the user holds in the system.

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).

A random self-selected small committee is selected via cryptographic sortition.

Further notes worth addressing:

1. The uniqueness and pseudo-randomness properties of the VRF are crucial in ensuring that no user can brute-force their way through multiple outputs Y until she finds one that falls within her desired range. Such attack is mitigated by the uniqueness property of the VRF because once the seed Qr is fixed, the VRF function can only be used to produce a single output. Moreover, the verification key VK must have entered into the system before block r, at the time when the seed Qr was essentially unpredictable. Altogether, a user cannot bias the output Y to fall within their desired range, which is where the pseudo-randomness property comes into play.
2. The above computation is extremely cheap. Each user only needs to perform a single Evaluate function computation to decide if they are selected to serve on the committee. (In practice, the computation is similar to computing a signature of a message).
3. A new and independent committee is chosen for each round of the Byzantine Agreement. This is possible due to the unique property of the Algorand Byzantine Agreement called player replaceability. Briefly, different users are able to participate in different rounds of the Byzantine Agreement without having to pass any state to each other. This allows Algorand to satisfy a high level of security, where a user is allowed to be dynamically corrupted after any message they send as part of the protocol.

Our VRF choice

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.

algorand/libsodium

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.

draft-irtf-cfrg-vrf-03 - Verifiable Random Functions (VRFs)

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!