Module schnorrkel::vrf

Implementation of a Verifiable Random Function (VRF) using Ristretto points and Schnorr DLEQ proofs.

Warning We warn that our VRF construction supports malleable outputs via the *malleable* methods. These are insecure when used in conjunction with our HDKD provided in dervie.rs. Attackers could translate malleable VRF outputs from one soft subkey to another soft subkey, gaining early knowledge of the VRF output. We suggest using either non-malleable VRFs or using implicit certificates instead of HDKD when using VRFs.

We model the VRF on “Making NSEC5 Practical for DNSSEC” by Dimitrios Papadopoulos, Duane Wessels, Shumon Huque, Moni Naor, Jan Včelák, Leonid Rezyin, andd Sharon Goldberg. https://eprint.iacr.org/2017/099.pdf We note the V(X)EdDSA signature scheme by Trevor Perrin at https://www.signal.org/docs/specifications/xeddsa/#vxeddsa is almost identical to the NSEC5 construction, except that V(X)Ed25519 fails to be a VRF by giving signers multiple outputs per input. There is another even later variant at https://datatracker.ietf.org/doc/draft-irtf-cfrg-vrf/

We support individual signers merging numerous VRF outputs created with the same keypair, which follows the “DLEQ Proofs” and “Batching the Proofs” sections of “Privacy Pass - The Math” by Alex Davidson, https://new.blog.cloudflare.com/privacy-pass-the-math/#dleqproofs and “Privacy Pass: Bypassing Internet Challenges Anonymously” by Alex Davidson, Ian Goldberg, Nick Sullivan, George Tankersley, and Filippo Valsorda. https://www.petsymposium.org/2018/files/papers/issue3/popets-2018-0026.pdf

As noted there, our merging technique’s soundness appeals to Theorem 3.17 on page 74 of Ryan Henry’s PhD thesis “Efficient Zero-Knowledge Proofs and Applications” https://uwspace.uwaterloo.ca/bitstream/handle/10012/8621/Henry_Ryan.pdf See also the attack on Peng and Bao’s batch proof protocol in “Batch Proofs of Partial Knowledge” by Ryan Henry and Ian Goldberg https://www.cypherpunks.ca/~iang/pubs/batchzkp-acns.pdf

We might reasonably ask if the VRF signer’s public key should really be hashed when creating the scalars in vrfs_merge*. After all, there is no similar requirement when the values being hashed are BLS public keys in say https://crypto.stanford.edu/~dabo/pubs/papers/BLSmultisig.html In fact, we expect the public key could be dropped both in Privacy Pass’ case, due to using randomness in the messages, and in the VRF case, provided the message depends upon shared randomness created after the public key. Yet, there are VRF applications outside these two cases, and DLEQ proof applications where the points are not even hashes. At minimum, we expect hashing the public key prevents malicious signers from choosing their key to cancel out the blinding of a particular point, which might become important in a some anonymity applications. In any case, there is no cost to hashing the public key for VRF applications, but important such an approach cannot yield a verifiable shuffle. TODO: Explain better!

We also implement verifier side batching analogous to batched verification of Schnorr signatures, but note this requires an extra curve point, which enlarges the VRF proofs from 64 bytes to 96 bytes. We provide shorten_* methods to produce the non-batchable proof from the batchable proof because doing so is an inherent part of the batch verification anyways. TODO: Security arguments!

We do not provide DLEQ proofs optimized for the same signer using multiple public keys because such constructions sound more the domain of zero-knowledge proof libraries.

Structs

• Malleable
  VRF SigningTranscript for malleable VRF outputs.
• VRFInOut
  VRF input and output paired together, possibly unverified.
• VRFPreOut
  VRF pre-output, possibly unverified.
• VRFProof
  Short proof of correctness for associated VRF output, for which no batched verification works.
• VRFProofBatchable
  Longer proof of correctness for associated VRF output, which supports batching.

Constants

• KUSAMA_VRF
  Value for kusama paramater to *dleq* methods that yields the VRF for kusama.
• VRF_PREOUT_LENGTH
  Length of VRF output.
• VRF_PROOF_BATCHABLE_LENGTH
  Length of the longer VRF proof which supports batch verification.
• VRF_PROOF_LENGTH
  Length of the short VRF proof which lacks support for batch verification.

Traits

• VRFSigningTranscript
  SigningTranscript helper trait that manages VRF output malleability.

Functions

• dleq_verify_batch
  Batch verify DLEQ proofs where the public keys were held by different parties.
• vrf_malleable_hash
  Create a malleable VRF input point by hashing a transcript to a point.
• vrf_verify_batch
  Batch verify VRFs by different signers

Type Aliases

• VRFOutputDeprecated
  VRF pre-output, possibly unverified.