11

In the recent BIP about Schnorr's standardization, Pieter Wuille presents an algorithm for batch validation. In my understanding the most heavy operation is the multiplication by a scalar: to make batch validation secure we need to multiply each public nonce by a random factor, thus we get back to two multiplications per signature (plus one). I don't understand why there is the speed up presented in the figure at the beginning of the BIP. Could someone help?

Thanks in advance for your answers!

8

You're right that the elliptic curve multiplication is indeed the most expensive operation in the validation algorithm. And as both single signature validation and batch validation require two EC multiplication per signature, it would seem that no speedup can be gained from batching.

However, several algorithms are known for computing the sum of multiple EC multiplications faster than summing the individual multiplications. Straus's algorithm (also known as Shamir's trick), Bos-Coster's algorithm, and Pippenger's algorithm all provide speedups, and are applicable in different scenarios. In the graph in our BIP draft Straus and Pippenger are used (depending on the size of the batch; Pippenger only wins for batches over ~100 keys). For sufficiently large batches, Bos-Coster and Pippenger are O(log n) times faster than individual multiplications.

To give you an intuition for how this is possible, here is a summary of Bos-Coster's algorithm (while in practice it's not the fastest, it's the easiest to explain):

  • Start with a list of pairs (a1, P1), (a2, P2), ..., (an, Pn).
  • Sort this list from large to small ai (and renumber it so that a1 is now the largest number, ...).
  • While the list has length larger than 1:
    • Replace the top two elements (a1, P1) and (a2, P2) with the two elements (a1 - a2, P1), (a2, P1 + P2).
    • If this results in an element with coefficient 0, remove it (this happens when a1 = a2).
    • Sort the list again.
  • When only one element remains, it will be of the form (a, P), where a is the GCD of all inputs. For a sufficiently large n, that GCD will be almost certainly be 1, in which case the solution is just P. Otherwise a will be a small number, and the solution is just aP.

The intuition here is that when you have say 100 multiplications to perform, a1 - a2 will on average be 100 times smaller than the number it replaces (a1), so in every step we're dividing one of the coefficients by 100, while only doing a single EC addition. This is in contrast with naive EC multiplication where you generally need to perform one addition for each bit in the input.

  • 2
    It might be worth mentioning that the final value (a, P), a is the GCD of the inputs, which is why it's usually 1 or small. It's also the case that you can make an argument for security for randomizer values that are much smaller than the full range-- though this fact isn't necessary for there to be a speedup so maybe it would distract from understanding. – G. Maxwell Nov 5 '18 at 2:19

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.