<p>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.</p>

<p>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 <em>O(log n)</em> times faster than individual multiplications.</p>

<p>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):</p>

<ul>
<li>Start with a list of pairs <em>(a<sub>1</sub>, P<sub>1</sub>), (a<sub>2</sub>, P<sub>2</sub>), ..., (a<sub>n</sub>, P<sub>n</sub>)</em>.</li>
<li>Sort this list from large to small <em>a<sub>i</sub></em> (and renumber it so that <em>a<sub>1</sub></em> is now the largest number, ...).</li>
<li>While the list has length larger than 1:

<ul>
<li>Replace the top two elements <em>(a<sub>1</sub>, P<sub>1</sub>)</em> and <em>(a<sub>2</sub>, P<sub>2</sub>)</em> with the two elements <em>(a<sub>1</sub> - a<sub>2</sub>, P<sub>1</sub>)</em>, <em>(a<sub>2</sub>, P<sub>1</sub> + P<sub>2</sub>)</em>. Note that <em>a<sub>1</sub>P<sub>1</sub> + a<sub>2</sub>P<sub>2</sub> = (a<sub>1</sub> - a<sub>2</sub>)P<sub>1</sub> + a<sub>2</sub>(P<sub>1</sub> + P<sub>2</sub>)</em>.</li>
<li>If this results in an element with coefficient 0, remove it (this happens when <em>a<sub>1</sub> = a<sub>2</sub></em>).</li>
<li>Sort the list again.</li>
</ul></li>
<li>When only one element remains, it will be of the form <em>(a, P)</em>, where <em>a</em> is the <a href="https://en.wikipedia.org/wiki/Greatest_common_divisor" rel="nofollow noreferrer">GCD</a> of all inputs. For a sufficiently large <em>n</em>, that GCD will be almost certainly be <em>1</em>, in which case the solution is just <em>P</em>. Otherwise <em>a</em> will be a small number, and the solution is just <em>aP</em>.</li>
</ul>

<p>The intuition here is that when you have say 100 multiplications to perform, <em>a<sub>1</sub></em> - <em>a<sub>2</sub></em> will on average be 100 times smaller than the number it replaces (<em>a<sub>1</sub></em>), 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.</p>

CC BY-SA 4.0
2018-11-05T02:19:56.857Z
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
CC BY-SA 4.0
2018-11-04T23:46:39.163Z
2019-05-02T17:34:47.143Z
2019-05-02T17:34:47.143Z
Pieter Wuille
<p>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?</p>

<p>Thanks in advance for your answers!</p>

<security><validation><bip><schnorr-signatures>
Schnorr's batch validation
Jon
# Schnorr's batch validation

(Asked by: username_0 on 2018-11-04)

In the recent BIP about Schnorr's standardization, username_1 username_1 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!

**Tags:** security, validation, bip, schnorr-signatures


---

## 1 answers

### Answer by username_1 on 2018-11-04. Score: 15 | Accepted answer

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](https://en.wikipedia.org/wiki/Greatest_common_divisor) 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.

> **Comments:**
> **username_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.  

---

