VRF traits

[tarcieri]

This issue proposes to add traits for Verifiable Random Functions (VRFs) to the elliptic-curve crate.

RFC9831 describes various curve-specific VRF algorithms, including a generic implementation for all prime order curves, and e.g. Elligator2 for "Edwards25519", i.e. the twisted Edwards form of Curve25519.

We can add a generic implementation to the primeorder crate, and potentially add support to curve25519-dalek as well, if it ever adopts the elliptic-curve crate for providing cross-curve abstractions (see also: dalek-cryptography/curve25519-dalek#492)

[omibo]

I would like to take on this task and would greatly appreciate it if you could assign it to me.

As a starting point, I will review RFC9381, as well as the elliptic-curve and primeorder crates, to gain a deeper understanding of the requirements.

[burdges]

Anonymized signatures would liekly be out of scope here, but..

I've done some mid-level traits for EC VRFs in https://github.com/w3f/ring-vrf/blob/master/dleq_vrf/src/traits.rs which work around input-output pairs.

I designed those traits for anonymized VRFs like ring VRFs, including what the ETH people call semaphore. As such, they're designed to be chained, from a secret key or a secret key plus zero knowledge continuiation to a ring openning, or from a public key or a ring commitment.

You cannot capture all anonymous VRF like constructions, but the important points:

• An auxiliary signed message beside the VRF input -- EC VRFs supports this, although afaik not standardized. RSA FDH and BLS cannot support this, but BLS should basically never be used as a VRF, unless you're deploying a whole threshold signing infrastructure, and even then other schemes work better. RSA FDH variants can have faster verifiers.
• Multiple input-output pairs in the same VRF signature.

Anonymized VRFs [almost] always need one or both of these features, or else replay attacks exist. A regular non-anonymous VRF rarely needs multiple input-output pairs, but the auxiliary signed message turns out useful more broadly.

[omibo]

@tarcieri

This issue proposes to add traits for Verifiable Random Functions (VRFs) to the elliptic-curve crate.

Considering the various VRF constructions based on different cryptographic assumptions—such as RSA, elliptic curves, and post-quantum candidates like LaV (though not part of RFC 9381)—what are your thoughts on introducing a separate crate specifically for VRF schemes?
We could define traits that every VRF implementation should support and then provide concrete implementations based on RFC specification.

We can add a generic implementation to the primeorder crate, and potentially add support to curve25519-dalek as well, if it ever adopts the elliptic-curve crate for providing cross-curve abstractions (see also: dalek-cryptography/curve25519-dalek#492)

Having a dedicated crate for VRFs would be useful for several reasons:

• VRFs are cryptographic primitives with applications in key transparency and blockchain leader election.
• Different VRF constructions exist, not all of which rely on elliptic curves.
• A separate crate would make the project more accessible to both users and developers.
• It would allow for easier expansion to support additional VRF implementations in the future.

[tarcieri]

It's another possible option, yes

[carloskiki]

How about something like this for the VRF traits?

pub trait Proof<H>
where 
    H: OutputSizeUser,
{
    fn to_hash(&self) -> Output<H>;
}

pub trait Prover<P, H>
where
    P: Proof<H>,
    H: OutputSizeUser,
{
    fn prove(&self, alpha: &[u8]) -> P;
}

pub trait Verifier<P, H>
where
    P: Proof<H>,
    H: OutputSizeUser,
{
    fn verify(&self, alpha: &[u8], proof: P) -> bool;
}

This is based on the design of Signer and Verifier from the signature crate.

[tarcieri]

Do Provers need to support multiple different Proof types? If not Proof could be an associated type (likewise with Verifier)

[carloskiki]

I used type parameters because that's what signature uses. I believe they document the design decision here.

But yes, associated types make a lot of sense. Looking only at the algorithms in the RFC, there does not seem to be a use for the proof P being a type parameter, because each algorithm only has 1 specified proof format.

[tarcieri]

For signature, our downstream crates make extensive use of overlapping impls for different signature types. See the ecdsa crate as an example:

https://docs.rs/ecdsa/latest/ecdsa/struct.SigningKey.html#impl-PrehashSigner%3C(Signature%3CC%3E,+RecoveryId)%3E-for-SigningKey%3CC%3E

I don't foresee that being as much of an issue for VRFs but there could be something I'm overlooking.