Redesign: What interface do we want?

[burdges]

1. How do we handle input and outputs?

Initially, I based this code off schnorrkel, which provides sign-verify methods for many usage patterns.

Ideally, schnorrkel should encapsulate the VRFOutput inside a more user-friendly VRFSignature type, but does not do so. I believed the vrfs_merge tricks mattered so I exposed it even for simple use cases, but.. Actually usages never definitively materialized even in AnV so we'll consider this choice a mistake for the user-friendly interface. We thus could encapsulate VRFOutput inside a more user-friendly VRFSignature type.

We need a VRFInOut based approach for the experts interface regardless, which then support vrfs_merge and others. I'd begun twisting ring-vrf towards using VRFInOut for the "most user-friendly" interface too. We could keep this path, rip out the current "inconvenience" methods, and plan to write actual convenience methods later.

2. How should we handle malleability?

We could ignore malleability except for writing big warnings all over, but doing so kinda kills any user friendlyness. In schnorrkel, I forced the non-malleabile version for most use cases by using traits to simulate defaults, but this looks impossible now.

We should probably keep the current new_* methods for the experts interface, but then force the minimal malleability inside the users friendly interface. I held off doing this because then outputs of ring vrf and non-ring vrfs differ, but oh well..

As an alternative, we could provide a malleability: MalleabilityMode type that propagates from more user-friendly layers, but this looks unnecessarily complex.

3. How do we handle public key blinding?

We should enforce that blinding factors only get used once, which seemingly requires creating them inside vrf_sign methods. We could make them an argument to dleq_prove, but not sure if doing this benefits anyone.

4. Do we need batchable schnorr proofs provided by NewChallengeOrWitness?

There is a simple version of the DLEQ proof given by

In = H_1(msg)
Out = sk In

Non-anonymous VRF:
R := r (G + In)
c := H(In, Out, PK, R)
s := c sk + r

We verify by recomputing c and checking
s (G + In) = c (PK + Out) + R
which looks batchable.

Anonymized Ring VRF:
APK := PK + b_pk B
R' := r (G + In) - b_R B
c := H(In, Out, PK, R')
delta := c b_pk + b_R
s := c sk + r

We again verify by recomputing c and checking
s (G + In) = c (PK + Out) + R'
which again looks batchable.

SNARK { APK : exists scalar b_pk and copath rho from root to PK = APK - b_pk B }

This speeds things up a tiny bit and avoids this complexity.

[burdges]

https://hdevalence.ca/blog/2020-10-04-its-25519am