[−][src]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 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
| KUSAMA_VRF | Value for |
| VRF_OUTPUT_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 |
|
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 |