Module schnorrkel::vrf

source ·
Expand description

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 ouputs.
  • VRFInOut
    VRF input and output paired together, possibly unverified.
  • VRFOutput
    VRF 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

Traits

Functions