Batchable VRF design

[burdges]

There is now a basic VRF in https://github.com/w3f/schnorr-dalek/blob/master/src/dleq.rs but I wrote it without clearly thinking through batching, so all the types need reworking. We could simply wait for davros for batching, but if we want it sooner then the design might look like:

/// Represents the VRF proof type and stage.
pub trait VRFStage {
    /// Identifies if this VRF proof is batchable.
    ///
    /// Always `()` for unbatched, but CompressedRistretto for batched.
    type Batch; 
    /// Identifies how evaluations get stored.
    ///
    /// Ideally `[..; 1]` for unbatched by signer, but always `Box<[..]>` for batched by the signer.
    type Evals: Borrow<[VRFEval<Self>]>+BorrowMut<[VRFEval<Self>]>;
    /// Identifies how inputs get collected.
    ///
    /// Ideally `[..; 1]` for unbatched by signer, but always `Box<[..]>` for batched by the signer.
    type Inputs: Borrow<[VRFEval<Self>]>+BorrowMut<[VRFEval<Self>]>;
}
pub struct Batchable;
impl VRFStage for Batchable {
    type Batch = CompressedRistretto;
    type Evals = Box<[VRFEval<Self>]>;
    type Inputs = Box<[VRFEval<Self>]>;
}
pub struct Unbatchable;
impl VRFStage for Nonbatchable<I> {
    type Batch = ();
    type Evals = [VRFEval<Self>; 1];
    type Inputs = [RisttrettoBoth; 1];
}

pub struct VRFEval<S: VRFStage> {
    /// Our input times the signer's private key.
    output: CompressedRistretto,
    /// Our input time the witness scalar r.
    input_x_r: S::Batch,
}
pub struct VRFProof<S: VRFStage> {
    c: Scalar,
    s: Scalar,
    R: S::Batch,  // Always () for unbatched, but CompressedRistretto for batched
    evals: S::Evals,  // [VRFEval<S>; 1] for singletons or Vec<VRFEval<S>> for signer batched
}
pub struct VRFProofAttached<S: VRFStage> {
    proof: VRFProof<S>,
    inputs: S::Inputs,
}

So the verification workflow goes: deserialize a VRFProof, attach the inputs, and run the appropriate verifier. It's possible the inputs can be managed detached everywhere because we've only three steps that use them, committing to the transcript in the beginning, which needs CompressedRistretto and either recomputing input_x_r in the non-batched case, or else verifying the delinerized sum of input_x_rs in the batched case, which both take RistrettoPoints.

[burdges]

This is fixed in 0.1 now. I took an approach much more similar to the old design but used a much better strategy for merging the proofs, well better assuming you want a VRF and not a tool for more general zk proofs. lol