bellman: Batch verification API

[hdevalence]

We'd like there to be a batch verification API in bellman that provides batch verification of Groth16 proofs, as described in §B.2 of the protocol spec. For bellman, it makes sense for the batch verification API to be synchronous, but we'd like the API to be compatible with an asynchronous wrapper using tower-batch, which we designed for this use-case. Based on our experience with writing asynchronous wrappers for Ed25519 and Redjubjub verification, I think that an IUF-style API would work well.

Here is a more concrete proposal. Inside bellman::verifier, add a mod batch with the following contents:

#[derive(Clone, Debug)]
pub struct Item<E: MultiMillerLoop> {
    proof: Proof<E>,
    public_inputs: Vec<E::Fr>,
}

impl<E: MultiMillerLoop> From<(Proof<E>, Vec<E::Fr>)> for Item<E> {
    fn from((proof, public_inputs): (Proof<E>, Vec<E::Fr>)) -> Self {
        Self {
            proof,
            public_inputs,
        }
    }
}

#[derive(Default, Debug)]
pub struct Verifier<E: MultiMillerLoop> {
    items: Vec<Item<E>>,
}

impl<E: MultiMillerLoop> Verifier<E> {
    pub fn new() -> Self {
        Default::default()
    }

    pub fn queue<I: Into<Item<E>>>(&mut self, item: I) {
        self.items.push(item.into())
    }

    pub fn verify<R: RngCore + CryptoRng>(
        self,
        rng: R,
        pvk: &PreparedVerifyingKey<E>,
    ) -> Result<(), Error> {
        unimplemented!()
    }
}

impl<E: MultiMillerLoop> Item<E> {
    pub fn verify_single(self, pvk: &PreparedVerifyingKey<E>) -> Result<(), Error> {
        verify_proof(pvk, &self.proof, &self.public_inputs)
    }
}

Some design choices made here:

1. We take ownership of the public inputs in the Item struct. This ensures that Item: 'static, which is important because it means that we can send verification items between threads or tasks without having to manage lifetime bounds.

2. The PreparedVerifyingKey is passed in as a parameter to verify, so that we don't need to prove relationships about the lifetime of the Verifier and the pvk.

3. Because queue takes impl Into<Item<E>>, it can be called as verifier.queue((proof, inputs)). However, because the Item is a single type, it's easy to work with in a generic context (like Tower).

4. The Item exposes a verify_single method that allows unbatched verification. In combination with the Clone impl, this allows implementing fallback logic for handling batch failures.

5. Unlike the existing verify_proof function, the verification functions return Result<(), Error> (error type tbd) rather than Result<bool, SynthesisError>. I don't think that the current return type is good, because it mixes failure modes across the Ok/Err variants. Checking verify_proof.is_ok(), for instance, will happily typecheck and be subtly wrong. Instead I think that verify_proof should return Ok(()) on successful verification and Err(SomeError) on failure. I would be happy to make this change together with or separate from batch verification.

[str4d]

I agree with using an IUF-style API, and it fits nicely with how I plan to use the batch API from zcashd across FFI.

1️⃣ Taking ownership will work fine for zcashd, as we need to reconstruct (proof, inputs) from their encodings once we cross the FFI. Note that since both Proof<E> and E::Fr implement Clone, Item could also implement From<(&Proof<E>, &[E::Fr])> rather than having the caller write verifier.queue((proof.clone(), inputs.iter().cloned().collect())).

5️⃣ I personally think that refactoring from Result<bool, SynthesisError> to Result<(), Error> is a good refactor.

[hdevalence]

Having an additional From impl for slices and borrows is a good idea for convenience. Callers who already have a Vec should be able to hand it over, but forcing them to build one is awkward.

[hdevalence]

I created #254 for (5) to do the error change separately.

[hdevalence]

One issue with this design is that it's not possible to batch together proofs created with different verification keys, even though there's no (theoretical) obstacle to doing so. I tried to think of some alternatives that would allow this but they all run into problems related to how to specify which pvk is associated with each item. Maybe there is some solution involving accumulating items into distinct batch accumulators, and then combining batch accumulators with each other. But this seems very complicated, in comparison to the simpler API above.

[str4d]

Closed by zkcrypto/bellman#59.