VRF-ed25519

Verifiable Random Functions () allow key-pair owners, , to evaluate a pseudorandom function in a provable way given a randomness seed. Any party with access to the verification key, , the randomness seed, the proof and the generated randomness can indeed verify that the value is computed as expected. The VRF specification has changed overtime in Cardano, and the nodes use a different algorith, pre-Babbage and post-Babbage (if there exists a reference to the HF, we should point it out). We expose both specifications, and the motivations for such a change.

Generalised specification

We use an additional hash function to that introduced in the Notation section. In particular one that maps a binary input to an element of the group , .

Pre Babbage

A function, in pre-Babbage eras, is defined by the following three algorithms:

  • follows the exact same procedure as described in ed25519. Output key pair . We refer to the signing key in the Ed25519 section as .
  • takes as input a keypair and a message , and returns the randomness together with a proof . Use to derive . Let . Let . Compute as defined in procedure as in ed25519. Let . Compute . Finally, return the proof and the randomness .
  • takes as input a message , a verification key and a vrf proof , and returns or . It parses the proof as , and computes . Let and . Compute the challenge . If , then return , otherwise, return .

Post Babbage

A function, in post-Babbage eras, is defined by the following three algorithms:

  • follows the exact same procedure as described in ed25519. Output key pair . We refer to the signing key in the Ed25519 section as .
  • takes as input a keypair and a message , and returns the randomness together with a proof . Use to derive . Let . Let . Compute as defined in procedure as in ed25519. Let . Compute . Finally, return the proof and the randomness .
  • takes as input a message , a verification key and a vrf proof , and returns or . It parses the proof as , and computes . Next, compute . Finally, if and , then return , otherwise, return .

This change allows for batch verification of proofs, which achieve up to a times two improvement in verification time, in exchange of a larger proof.

Parameters of instantiation

Some of the concrete parameter instantiations also differ between pre-Babbage and post-Babbage eras. We begin by describing those which coincide, and follow with a separate description for the ones that differ.

  • Parameter and suite : We set . We choose the suite , as defined in the standard draft1. This sets the parameter as and the following parameters.
  • Curve: We define the curve, and by consequence the finite prime order field, security parameter, cofactor, prime order subgroup and generator, as described in the ed25519 paper2. In particular, we use Edwards25519 which is birationally equivalent to Curve25519.
  • Hash: As a hashing algorithm we use SHA512.

Pre Babbage

We proceed with the specifications on pre-Babbage eras.

  • Draft version: pre-Babbage eras are build on top of Version 03 of the standards draft3.
  • Deserialization: A proof is represented by 80 bytes: the first 32 bytes, , represent the point , the following 16 bytes, , represent the scalar , and the final 32 bytes, , represent the scalar . A public key is also represented as 32 bytes, . Deserialization is valid only if:
    • when read as a little-endian integer, it is smaller than .
    • does not represent a low order point (by checking against a precomputed blacklist of size , and when read as a little-endian integer, it is smaller than .
  • Hash to curve : Elligator mapping, over a scalar computed by hashing . The mechanism is described in Section~5.4.1.2 of version 3 of the draft. Note that for implementing the mechanism as described in the draft, the sign bit is cleared before calling the elligator function, meaning that the latter always works with sign = 0 (see function). See Appendix A.4 of version 3 of the draft for test vectors.

Post Babbage

We finalize with the specifications of post-Babbage eras.

  • Draft version: post-Babbage eras are build on top of a batch-compatible version of Version 10 of the standards draft4. The specific construction is described in the technical spec studying the security of batch compatibility5.
  • Deserialization: A proof is represented by 128 bytes: the first 32 bytes, , represent the point , the following 32 bytes, , represent the point , the following 32 bytes, , represent the point , and the final 32 bytes, , represent the scalar . A public key is also represented as 32 bytes, . Deserialization is valid only if:
    • when read as a little-endian integer, it is smaller than .
    • when read as a little-endian integer, is smaller than .
    • does not represent a low order point (by checking against a precomputed blacklist of size , and when read as a little-endian integer, it is smaller than .
  • Hash to curve : Hash to curve algorithm as defined in the hash to curve standard6, version 12, Section 6.8.2 (non uniform version). For test vectors, one can use those presented in Appendix J.5.2 of that same document. Reference implementation can be found in the libsodium fork.
1

Goldberg, Reyzin, Papadopoulos and Včelák, Verifiable Random Functions (VRFs); version 15

2

Bernstein, Duif, Lange, Schwabe and Yang, High-Speed High-Security Signatures

3

Goldberg, Reyzin, Papadopoulos and Včelák, Verifiable Random Functions (VRFs); version 03

5

Badertscher, Gazi, Querejeta-Azurmendi and Russell, On UC-Secure Range Extension and Batch Verification for ECVRF

6

Faz-Hernández, Scott, Sullivan, Wahby and Wood, Hashing to Elliptic Curves