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). Note that a1P1 + a2P2 = (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.