Public Parameters

Let \(\mathbb{G}\) be a cyclic group of prime order \(p\) with generator \(g\). Denote \(\mathbb{Z}_p\) to be the set of integers modulo \(p\). Let \(\mathsf{EncodeToCurve}\) be a hash function mapping a bit string to an element in \(\mathbb{G}\). Let \(\mathsf{ChallengeGeneration}\) be a hash function mapping arbitary input length to a \(256\) bit integer.

Note that, in the paper of [PWHVNRG17], the functions \(\mathsf{EncodeToCurve}\) and \(\mathsf{ChallengeGeneration}\) are modeled as random oracle model. This is used to prove the security of the VRF.

The cofactor parameter mentioned in the irtf draft is set to \(1\).

The \(\mathsf{Eval}\) function is split into 2 functions: \(\mathsf{Prove}\) and \(\mathsf{ProofToHash}\). The \(\mathsf{Prove}\) function returns the proof of the ECVRF, and the \(\mathsf{ProofToHash}\), returns the ECVRF output.

ECVRF Construction

\(\mathsf{KeyGen}(1^{k})\): Choose a random secret value \(sk \in \mathbb{Z}_p\) and the secret key is set to be \(sk \). The public key is \(pk=g^{sk}\).

\(\mathsf{Prove}(sk,X)\): Given the secret key \(sk\) and an input \(X\), the proof \(\pi\) of ECVRF is computed as follow:

  1. Compute \(h=\mathsf{EncodeToCurve}(X,pk)\).

  2. Compute \(\gamma=h^{sk}\).

  3. Choose a value \(k\) uniformly in \(\mathbb{Z}_p\).

  4. Compute \(c=\mathsf{ChallengeGeneration}(h,pk,gamma,g^k,h^k)\).

  5. Compute \(s \equiv k-c.sk \pmod{q}\).

  6. The proof \(\pi\) of the VRF is computed as \(\pi=(\gamma,c,s)\).

\(\mathsf{ProofToHash}(gamma)\): Given input \(\gamma\) that is calculated during the \(\mathsf{Prove}\) function, this function returns the output of ECVRF.

  1. Compute \(gammastr=\mathsf{PointToString}(\gamma)\).

  2. Let \(gammastr=PointToString(\gamma)\).

  3. Let \(suite-string\)="0x01".

  4. Let \(separator-front\)="0x03".

  5. Let \(separator-back\)="0x00".

  6. Let \(Y=\mathsf{keccak}(suite-string || seperator-front || gammastr || seperator-back)\).

  7. Return \(Y\).

\(\mathsf{Verify}(pk,X,Y,\pi)\): Given the public key \(pk\), the VRF input \(X\), the VRF output \(Y\) and its proof \(\pi=(\gamma,c,s)\), the verification step proceeds as follow:

  1. Check if \(\gamma\) and \(pk\) is on the curve.

  2. Compute \(u=pk^cg^s\).

  3. Compute \(h=\mathsf{EncodeToCurve}(X,pk)\).

  4. Compute \(v=\gamma^ch^s\).

  5. Check if \(c=\mathsf{ChallengeGeneration}(h,pk,gamma,g^k,h^k)\). If the check is valid, output \(Y=\mathsf{ProofToHash}(\gamma)\), otherwise output \(Invalid\).