Module schnorrkel::vrf

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

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.

We support individual signers merging numerous VRF outputs created with the same keypair as described in the DLEQ Proofs and Batching the proofs sections of "Privacy Pass - The Math" by Alex Davidson, https://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 Ryqan 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 blionding of a particular point, which might become important in a verifiable shuffle or other anonymity applications. In any case, there is no cost to hashing the public key for VRF applications. 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 inhrent part of the batch verification anyways. TODO: Security arguments!

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

Structs

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 verfication works.
VRFProofBatchable	Longer proof of correctness for associated VRF output, which supports batching.

Functions

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