Schnorr's batch validation

Question

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!

Answer 1

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 (a₁, P₁), (a₂, P₂), ..., (a_n, P_n).
• Sort this list from large to small a_i (and renumber it so that a₁ is now the largest number, ...).
• While the list has length larger than 1:
  • Replace the top two elements (a₁, P₁) and (a₂, P₂) with the two elements (a₁ - a₂, P₁), (a₂, P₁ + P₂). Note that a₁P₁ + a₂P₂ = (a₁ - a₂)P₁ + a₂(P₁ + P₂).
  • If this results in an element with coefficient 0, remove it (this happens when a₁ = a₂).
  • 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, a₁ - a₂ will on average be 100 times smaller than the number it replaces (a₁), 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.