Currently musig::DeferredVerification and zkvm::PointOp perform allocations per each operation, and then we have to "unzip" a collection of these operation objects into two iterators: scalars and points.
A better approach would be a trait for an "accumulator" of batched operations verify_batch(..., &mut BatchTrait) that lets user choose their own implementation for batched verification. Internally, it will use a single storage for all the elements, reducing allocations to O(1) per batch (or at worst O(log(n)) if not pre-allocated with capacity).
Different crates may use slightly different traits. E.g. schnorr/musig crates use one static point B, and therefore can have an API that treats it special and pre-multiplies and pre-adds scalar weights for that point. At the same time, zkvm::Predicate uses two static generators: B and B_blinding, so its trait may have separate API for specifying weights for these points. The end user (zkvm::Verifier) could use a single batch computation object that implements both traits (for signatures and predicates) and stores all points and scalars in the unified, yet efficient, form.
oleganza
commented
5 years ago
Currently
musig::DeferredVerificationandzkvm::PointOpperform allocations per each operation, and then we have to "unzip" a collection of these operation objects into two iterators: scalars and points.A better approach would be a trait for an "accumulator" of batched operations
verify_batch(..., &mut BatchTrait)that lets user choose their own implementation for batched verification. Internally, it will use a single storage for all the elements, reducing allocations to O(1) per batch (or at worst O(log(n)) if not pre-allocated with capacity).Different crates may use slightly different traits. E.g.
schnorr/musigcrates use one static pointB, and therefore can have an API that treats it special and pre-multiplies and pre-adds scalar weights for that point. At the same time,zkvm::Predicateuses two static generators:BandB_blinding, so its trait may have separate API for specifying weights for these points. The end user (zkvm::Verifier) could use a single batch computation object that implements both traits (for signatures and predicates) and stores all points and scalars in the unified, yet efficient, form.