Implement Groth16 batch verification optimizations

[dconnolly]

https://zips.z.cash/protocol/protocol.pdf#grothbatchverify

This impl can be swapped out for calling out directly to Bellman when complete.

[dconnolly]

Part of #196

[str4d]

zkcrypto/bellman#31 is the upstream issue for this in bellman.

[hdevalence]

@str4d do you think it would make sense to have the upstream bellman api provide a conventional, synchronous batch verification API, and for us to create a bellman-async crate in our workspace that provides the async tower-based API with tower, tokio dependencies etc.?

It could of course be upstreamed later, but the advantage is that it decouples the Zebra work from the Bellman work, since the rest of Zebra can be written against a generic Service (using singleton verification initially, then dropping in the batch verification when upstream changes land).

[daira]

Well, we should probably decide first how we want the work split up. As described in the spec, batch validation uses a set of accumulator variables that are updated for each batch entry, and a final check. The batch entries can presumably be submitted from multiple threads. Do we want most of the work for each batch entry update –i.e. the Miller Loop and multiplications by z_i– to be done on the thread that submits it (locking for a short time to do just the multiplication of Accum_AB and the additions for the other accumulator variables), or do we want to submit the batch entry to a queue and have the batch verification abstraction handle that work? These options have different implications for parallelism, complexity, and potentially DoS-resistance.

[daira]

The simplest API that is compatible with any approach to concurrency in the code that uses it, is that you have a method to submit a batch entry and a method to finish the batch. These are allowed to be called from multiple threads; attempting to submit a new entry after the batch has been finished will fail. The finish method synchronously returns the verification result. You can easily wrap this in something that can provide a Future for the result, or similar.

Another alternative is to provide a mutable object that can only be used by a single thread, but to split up the operation that submits a batch entry into a function that is independent of the mutable state (which does the Miller Loop and multiplications by z_i), and a state update method. That enables providing a thread-safe wrapper that does the same thing I described in the paragraph above. If the batch submission operation were not split up then it would be impossible to obtain the same parallelism.

(The function that is independent of the mutable state could be done as part of the construction of a batch entry object, maybe.)

[daira]

Yeah the more I think about this, the more I like the completely synchronous option but with the Miller Loop etc. done when constructing a batch entry, rather than by the batch accumulator itself. For a start it's easier to test.

[hdevalence]

@daira What's the benefit to being able to update batch entries from multiple threads, rather than letting the API user compose the batch structure with their choice of synchronization primitive? For instance, for our application, we would get no benefit from internal synchronization, because we're already using message-passing to the wrapper Service. I think this points towards the second alternative you mention.

[hdevalence]

@daira Do you have a ballpark estimate (<1ms? 2-5ms? >10ms?) of how much work is involved in the Miller loop etc. required to construct a batch entry?

[hdevalence]

Underway in #830

[yaahc]

After discussion with @hdevalence we're splitting this into two separate issues.

1. Implementing the batch verification in bellman
2. Implementing an async batch verification API ontop of bellman

The former task will be handled by @oxarbitrage while I'll continue working on the async API that abstracts over it. The initial implementation will just repeatedly call the non batch verification API in bellman until the working batch API is available.

[dconnolly]

After discussion with @hdevalence we're splitting this into two separate issues.

1. Implementing the batch verification in bellman
2. Implementing an async batch verification API ontop of bellman

The former task will be handled by @oxarbitrage while I'll continue working on the async API that abstracts over it. The initial implementation will just repeatedly call the non batch verification API in bellman until the working batch API is available.

Remind me if the batch proof verification (the math) has been implemented in a fork of bellman (@hdevalence's or in the zfnd org fork) or just the async batch API, both calling and exposing in the bellman fork? I think the latter is true and is the part we strictly need first to complete transaction validation.

[yaahc]

Remind me if the batch proof verification (the math) has been implemented in a fork of bellman (@hdevalence's or in the zfnd org fork) or just the async batch API, both calling and exposing in the bellman fork? I think the latter is true and is the part we strictly need first to complete transaction validation.

We implemented the API on both sides, so henry setup a batch verification module in bellman but didn't do the math, and he setup an async batch Service in zebra which called the incomplete batch API from his branch of bellman. I ported his branch from librustzcash to bellman's new repo here. I've also updated the async API in this PR to call the non batch API in bellman for now so we can plug it into the rest of the system while the rest of the math is finished.

[dconnolly]

FYI @oxarbitrage I'm taking a stab at finishing the batch arithmetic in the bellman branch so

[dconnolly]

Implemented in zkcrypto/bellman#59

[dconnolly]

zkcrypto/bellman#59