<p>Yes, one <em>validation</em> per block, but not one <em>signature</em> per block.</p>
<p>To clear up confusion, there are 3 distinct technologies involved here:</p>
<ul>
<li>(1) <strong>non-interactive aggregation</strong> is the ability for a third party (who does not hold any private keys) to combine multiple signatures, each with their own message and public key, into a single signature that can be verified by someone who knows all messages and public keys.</li>
<li>(2) <strong>interactive aggregation</strong> is the same, but when the signers need to be aware of the aggregation, and communicate with each other to jointly produce a single signature.</li>
<li>(3) <strong>batch validation</strong> is the ability for a verifier to verify whether multiple (pubkey,message,signature) tuples are all valid or not, faster than verifying the individual signatures. If one or more of the tuples are invalid the verifier will not learn which ones, in this case.</li>
</ul>
<p>Schnorr signatures (and any other known discrete logarithm based signature schemes) support (2) and (3), but not (1).</p>
<p>The lack of (1) means there cannot be a single signature for an entire block (*), as the miner who constructs the block is a third party who isn't participating in signature creation.</p>
<p>Due to (2), the best we can hope for (as long as we're restricted to DL-based signatures), is one signature per transaction. Even that requires cross-input aggregation, which has complexities beyond just the implementation of on-chain Schnorr signatures (see <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015838.html" rel="nofollow noreferrer">this post</a> for example).</p>
<p>However, because of (3) it is correct that there can be a single <em>validation</em> per block, however not a single <em>signature</em> per block. The speedup that is possible through batch validation does become nontrivial, in fact. Each of the 4 lines is an optimization technique that is currently implemented in libsecp256k1, which will pick the best one based on the size of the problem and the memory constraints.</p>
<p><a href="https://i.sstatic.net/GndQm.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/GndQm.png" alt="Batch validation speedup" /></a></p>
<p>(*) There exists a form of non-interactive &quot;half aggregation&quot; for DL based signatures, where N signatures can be non-interactively combined into a single signature of size (1+N)/2 original signatures. This could be used for blocks, though the gains aren't that great, and there are complexities around block-wide aggregation that make it less interesting.</p>

CC BY-SA 4.0
2019-03-10T23:18:01.023Z
I guess I have to read up the details again but wasn't the idea of the plain public key model and the construction of musig exactly that non interactive aggregation would become possible? Or should I have asked for musig signatures? I thought musig is just the exact scheme that is currently aimed to be used when people talk about schnorr. Do not mark as correct yet as I still have open questions (which are probably my fault)
Rene Pickhardt
CC BY-SA 4.0
2019-03-10T23:21:36.413Z
MuSig allows non-interactive *setup* - signing is still interactive.
Pieter Wuille
CC BY-SA 4.0
2019-03-10T23:25:08.313Z
And MuSig is just one of the things wallet can choose to use when Schnorr validation on chain exist (because the signatures that come out of MuSig signing are compatible with a Schnorr verifier). There are (interactive setup) constructions that let you build k-of-n with a single key for example, or even arbitrary and/or-combinations of participants.
Pieter Wuille
CC BY-SA 4.0
2019-03-12T07:26:52.877Z
"There exists a form of non-interactive "half aggregation" for DL based signatures, where N signatures can be non-interactively combined into a single signature of size (1+N)/2 original signatures." -- 

Couldn't this be iterated for O(log(N)) iterations?
Martin Schwarz
CC BY-SA 4.0
2019-03-12T17:25:17.133Z
@Martin Schwarz What do you mean by iterated? The construction (for Schnorr) is that you combine (R1,s1), ..., (Rn,sn) into (R1,...,Rn,s) where s = H(L,1)*s1 + ... + H(L,n)*sn and L = H(R1,...Rn,P1,...,Pn,m1,...,mn), and Pi are the pubkeys and mi are the messages.
Pieter Wuille
CC BY-SA 4.0
2019-03-13T14:06:27.653Z
Oh, I see. OK, that doesn't work.
Martin Schwarz
CC BY-SA 4.0
2019-05-09T15:29:15.520Z
Just saw this today -- very nice figure, why not include into the bip-schnorr?
Mark Lundeberg
CC BY-SA 4.0
2019-03-10T22:24:53.747Z
2020-12-23T17:22:50.637Z
2020-12-23T17:22:50.637Z
Pieter Wuille
<p>In a recent talk Pieter Wuille <a href="https://www.youtube.com/watch?v=oTsjMz3DaLs&amp;t=1502s" rel="noreferrer">talked about speed up verification</a> when using Schnorr signatures and various algorithms for verifying multiple signatures. </p>

<p>Would it really be possible to verify one single block by aggregating the keys and signatures of all transactions? (In theory even more transactions over several blocks)</p>

<p>I assume this does imply that the old ECDSA scheme would not be used anymore. If we were backwards compatible we could probably only do this for transactions that used Schorr signatures where as the other ones would have to be verified one by one. </p>

<p>(Leaving aside politics of drastic protocol changes) Couldn't we even save more space if we adopt the block header to include one aggregate Schnorre signature for the block and leave out all the schnorr signatures of the single transactions within that block?</p>

<p>Did I miss anything? The talk did not give many details but just mentioned the idea.</p>

<validation><block-validity><schnorr-signatures>
When Schnorr signatures are part of Bitcoin will it be possible validate each block with only one signature validation?
Rene Pickhardt
# When Schnorr signatures are part of Bitcoin will it be possible validate each block with only one signature validation?

(Asked by: username_0 on 2019-03-10)

In a recent talk username_1 username_1 [talked about speed up verification](https://www.youtube.com/watch?v=oTsjMz3DaLs&t=1502s) when using Schnorr signatures and various algorithms for verifying multiple signatures.

Would it really be possible to verify one single block by aggregating the keys and signatures of all transactions? (In theory even more transactions over several blocks)

I assume this does imply that the old ECDSA scheme would not be used anymore. If we were backwards compatible we could probably only do this for transactions that used Schorr signatures where as the other ones would have to be verified one by one.

(Leaving aside politics of drastic protocol changes) Couldn't we even save more space if we adopt the block header to include one aggregate Schnorre signature for the block and leave out all the schnorr signatures of the single transactions within that block?

Did I miss anything? The talk did not give many details but just mentioned the idea.

**Tags:** validation, block-validity, schnorr-signatures


---

## 1 answers

### Answer by username_1 on 2019-03-10. Score: 17 | Accepted answer

Yes, one *validation* per block, but not one *signature* per block.

To clear up confusion, there are 3 distinct technologies involved here:

* (1) **non-interactive aggregation** is the ability for a third party (who does not hold any private keys) to combine multiple signatures, each with their own message and public key, into a single signature that can be verified by someone who knows all messages and public keys.
* (2) **interactive aggregation** is the same, but when the signers need to be aware of the aggregation, and communicate with each other to jointly produce a single signature.
* (3) **batch validation** is the ability for a verifier to verify whether multiple (pubkey,message,signature) tuples are all valid or not, faster than verifying the individual signatures. If one or more of the tuples are invalid the verifier will not learn which ones, in this case.

Schnorr signatures (and any other known discrete logarithm based signature schemes) support (2) and (3), but not (1).

The lack of (1) means there cannot be a single signature for an entire block (\*), as the miner who constructs the block is a third party who isn't participating in signature creation.

Due to (2), the best we can hope for (as long as we're restricted to DL-based signatures), is one signature per transaction. Even that requires cross-input aggregation, which has complexities beyond just the implementation of on-chain Schnorr signatures (see [this post](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-March/015838.html) for example).

However, because of (3) it is correct that there can be a single *validation* per block, however not a single *signature* per block. The speedup that is possible through batch validation does become nontrivial, in fact. Each of the 4 lines is an optimization technique that is currently implemented in libsecp256k1, which will pick the best one based on the size of the problem and the memory constraints.

[![Batch validation speedup](https://i.sstatic.net/GndQm.png)](https://i.sstatic.net/GndQm.png)

(\*) There exists a form of non-interactive "half aggregation" for DL based signatures, where N signatures can be non-interactively combined into a single signature of size (1+N)/2 original signatures. This could be used for blocks, though the gains aren't that great, and there are complexities around block-wide aggregation that make it less interesting.

> **Comments:**
> **username_0**: I guess I have to read up the details again but wasn't the idea of the plain public key model and the construction of musig exactly that non interactive aggregation would become possible? Or should I have asked for musig signatures? I thought musig is just the exact scheme that is currently aimed to be used when people talk about schnorr. Do not mark as correct yet as I still have open questions (which are probably my fault)  
> **username_1**: MuSig allows non-interactive *setup* - signing is still interactive.  
> **username_1**: And MuSig is just one of the things wallet can choose to use when Schnorr validation on chain exist (because the signatures that come out of MuSig signing are compatible with a Schnorr verifier). There are (interactive setup) constructions that let you build k-of-n with a single key for example, or even arbitrary and/or-combinations of participants.  
> **username_2**: "There exists a form of non-interactive "half aggregation" for DL based signatures, where N signatures can be non-interactively combined into a single signature of size (1+N)/2 original signatures." --   Couldn't this be iterated for O(log(N)) iterations?  
> **username_1**: @username_2 What do you mean by iterated? The construction (for Schnorr) is that you combine (R1,s1), ..., (Rn,sn) into (R1,...,Rn,s) where s = H(L,1)*s1 + ... + H(L,n)*sn and L = H(R1,...Rn,P1,...,Pn,m1,...,mn), and Pi are the pubkeys and mi are the messages.  
> **username_2**: Oh, I see. OK, that doesn't work.  
> **username_3**: Just saw this today -- very nice figure, why not include into the bip-schnorr?  

---

