Rigging the Vote: Uniqueness in Verifiable Random Functions

This blog post presents a whirlwind overview of Verifiable Random Functions (VRFs) as used by several leading-edge blockchains, and shows how a very interesting and recently found implementation oversight causes the VRF’s assurance of uniqueness to fall apart. As VRFs are commonly used for selecting blockchain consensus voting committees, this can result in a rigged vote on the progression of consensus.

Blockchains can be considered to be distributed consensus systems that have historically used compute-intensive Proof of Work (PoW) techniques to control forward progress. As PoW can be extremely energy intensive, more advanced techniques known as Proof of Stake (PoS) have emerged that use a voting committee to control forward progress. Each node can independently self-determine whether they are a member of an upcoming voting committee through the results of a VRF, where the input originates from the current consensus state and the node’s secret key, the unique and deterministic output (alongside a node’s stake) determines the membership result, and the whole process can be subsequently verified by any/all interested third parties. If a set of nodes can maliciously join the voting committee by manipulating the VRF results, they can then vote for the wrong next consensus state.

While Verifiable Random Functions can be traced back to 1999, the subject gained new momentum in March 2017 with the release of the Internet Research Task Force (IRTF) Crypto Forum Research Group (CFRG) document draft-irtf-cfrg-vrf-00 which is now up to version 15. That document defines a VRF to be “…the public-key version of a keyed cryptographic hash. Only the holder of the secret key can compute the hash, but anyone with the public key can verify the correctness of the hash”. Simplistically, the VRF functionality consists of 3 API functions using elliptic curve techniques (hence ECVRF) that provide an assurance of uniqueness central to the discussion below. Additional background on VRFs and their multiple assurances can be found in the two prior posts noted below that were written back when the IRTF CFRG VRF document was at version 5.

1. Reviewing Verifiable Random Functions
2. Exploring Verifiable Random Functions in Code

VRF Specification Section 5.1 ECVRF Prove

This first API function utilizes an input called the alpha_string which originates with the current consensus state (e.g., perhaps the last agreed block hash) along with a secret key SK (synonymous with x below). The alpha_string is public and common to all nodes, while the secret key is fixed and specific to a particular node. The output is a VRF proof which can be loosely thought of as a seed Gamma alongside its signature/witness c and s. The steps below are simplified for clarity, where B is a generator and q is the curve order.

ECVRF Prove() Steps:

1. Use the SK as x to calculate the public key Y = x*B
2. Encode the alpha_string to an elliptic curve point H
3. Calculate Gamma = x*H
4. Generate a deterministic nonce k
5. Calculate c = Hash(Y, H, Gamma, k*B, k*H)
6. Calculate s = (k + c*x) mod q
7. Return the proof as {Gamma, c, s}

Spoiler: the implementation oversight involves a missing Gamma from the hash inputs on step 5. A node holds the calculated proof c and s elements in reserve and optionally discloses them much later during the verification step. Meanwhile, the Gamma value is used in the next function to generate the actual ‘randomness’.

VRF Specification Section 5.2 ECVRF Proof to Hash

This second API function utilizes the input Gamma as calculated in the above Prove() function and returns the final ‘randomness’ called beta_string. This output directly depends upon the hash of Gamma, while the previously calculated c and s values are not used here. The cofactor is just a curve-specific constant.

ECVRF Proof_to_Hash() Steps:

1. Given a valid decoding of {Gamma, c, s}
2. beta_string = Hash(domain_separators || cofactor * Gamma || domain_separator)
3. Return the beta_string

The calculated beta_string is the critical value used by a blockchain to allow nodes to self-determine if they are on an upcoming voting committee. The beta_string would be inspected for particular characteristics, such as its magnitude relative to a node’s stake. As each node has a different secret key SK, each node will calculate a different beta_string result. As the process from alpha_string and SK to beta_string is deterministic, there should only be one possible result. The concept of selecting a voting committee through VRF results would be broken if a node could simply rerun the process until a desired result were obtained.

Note that the nonce k does not directly participate in the calculation of the beta_string. If an adversary chose to play games with the k value, it would not result in a different beta_string (which is the only value assured of uniqueness).

VRF Specification Section 5.3 ECVRF Verify

This third API function utilizes the Gamma, c and s values calculated by the Prove() function, along with the original alpha_string, to verify that a particular beta_string was indeed generated legitimately. The beta_string could be considered a commitment with the Verify() performing a sort of signature verification.

ECVRF Verify() Steps:

1. Given a valid decoding of {Gamma, c, s}, public key Y, and alpha_string
2. Encode the alpha_string to an elliptic curve point H
3. Calculate U = s*B - c*Y
4. Calculate V = s*H - c*Gamma
5. Calculate c' = Hash(Y, H, Gamma, U, V)
6. If c and c' are equal, the proof is "VALID" otherwise it is "INVALID"

Note that the nonce k value is never seen by itself. It is ‘hidden’ in the scalars used to multiply elliptic curve points. Thus, a wrongly chosen k cannot be detected and this in fact becomes central to the break.

Nodes can demonstrate legitimate membership on the voting committee by disclosing their proof {Gamma, c, s} for anyone to verify, assuming the characteristics of the beta_string are acceptable.

Uniqueness

If the above functionality is implemented correctly, the VRF output beta_string is assured to be unique. The IRTF CFRG VRF specification defines Full Uniqueness in section 3.1 as follows:

Uniqueness means that, for any fixed VRF public key and for any input alpha, it is infeasible to find proofs for more than one VRF output beta.

In the context of blockchains, this can be visualized as: given a current state alpha_string and a single secret/public key pair, a node can only generate a single output beta_string that passes verification. Thus, ‘the dice that determine a node’s voting committee membership for the current state can only be rolled once’.

Breaking Uniqueness

As mentioned in the spoiler above, a hash function that misses Gamma in both Prove() step 5 and Verify() step 5 will seem to work fine in practice but its uniqueness can be broken with some effort. Specifically, for a given alpha_string and secret key, a malicious prover can generate arbitrary proofs that will correctly verify under their public key. Let us choose k and calculate a proof of the following form using exponential notation (where cInv is c^-1). Note that the hash does not contain Gamma, which is the source of the ‘opportunity’ as the oversight allows c to be calculated fully independently of Gamma.

{Gamma = H^{(sk + cInv)}, c = Hash( Y || H || B^{(k + 1)} || H^k ), s = k + (sk + cInv) * c}

If multiple proofs of this form were generated by multiple choices of k, then we have multiple Gamma values that would then result in different non-unique beta_strings. But would they verify?

Given an instance of the above proof, the Verify() steps will calculate the following two values.

U = B^s – Y^c = B^{(k + (sk + cInv)c)} – B^sk*c = B^{(k + sk*c + 1 – sk*c)} = B^{(k + 1)}
V = H^s – Gamma^c = H^{(k + (sk + cInv)}c) – H^{(sk + cInv)*c} = H^{(k + sk*c + 1 – sk*c – 1)} = H^k

This will result in the following c’ which will indeed validate.

c’ = Hash( Y || H || B^{(k + 1)} || H^k)

As a result, a set of nodes can rerun Prove() with different choices of k until the obtain a beta_string that gains membership on the voting committee. At that point, the fake electors can vote for world peace.

The author would like to thank Parnian Alimi, Giacomo Pope, Kevin Henry, Eli Sohl, Aleksandar Kircanski and Paul Bottinelli of NCC Group’s Cryptography Services team for their review of this post. All issues remain with the author.