<p>I want to start by addressing a few misconceptions in your question:</p>
<ol>
<li><p><strong>&quot;Schnorr signatures&quot; aren't really a well-defined signature scheme.</strong> They're a class of digital signature schemes (with many possible instantiations, e.g. BIP340 and Ed25519), and in a wider sense even an abstract idea for building many types of signature schemes (including e.g. MuSig2, FROST, CoSi, BN06, ...). Historically, and in several answers on this site, I have not always made a clear distinction between them. In what follows, I'll call the latter &quot;Schnorr-based&quot;. While there are properties that apply to many Schnorr-based schemes in general, the details vary a lot.</p>
</li>
<li><p><strong>&quot;Adding signatures gives signature for sum of public keys&quot; is a simplification.</strong> It is an abstract mathematical property that applies to the verification equation of many Schnorr-based schemes (the fact that the equation is linear). This particular way of formulating it helps convey what it's useful for in an approximate way, but using it in practice in concrete schemes is not as simple. It's not just applying an addition function, and the co-signers need to be aware of each other, or the resulting sum won't be a valid signature. This is why the resulting signature aggregation schemes are said to be <em>interactive</em>, and don't lend themselves to block-wide aggregation for example. If it were possible to just hand the keys and signatures to a third party who could aggregate them, the result would be called non-interactive, but that's not the case here. There do exist other classes of signature schemes for which non-interactive aggregation is possible (notably, BLS), but for Schnorr-based schemes only interactive constructions are known.</p>
</li>
<li><p><strong>&quot;Adding signatures gives signature for sum of public keys&quot; is not on itself a scheme.</strong> It's only a principle upon which multisignature and other more advanced schemes can be built. Even taking point (2) above into account, applying this principle naively as a multisignature scheme is woefully insecure. Secure schemes are non-trivial to get right (several published ones, including the first version of MuSig, were later shown to be broken), and appear to involve at least 2 or 3 interaction rounds between the signers. So we can't just talk about this being sort-of an implicit possibility that's part of the &quot;Schnorr signature scheme&quot;; you need to specify exactly which scheme is being considered.</p>
</li>
</ol>
<p>Before continuing I also want to point out a few points of terminology:</p>
<ul>
<li><p><strong>The difference between <em>signature aggregation</em> and <em>multisignatures</em>.</strong> In a multisignature scheme, there are multiple participants which jointly sign a <em>single</em> message, resulting in a single signature. In a signature aggregation scheme, there are multiple participants that jointly sign <em>their own</em> message, resulting in a single signature.</p>
</li>
<li><p><strong>The difference between <em>key aggregation</em> and <em>multisignatures</em>.</strong> According to the typical academic definition, a multisignature scheme involves a verifier who receives <em>all</em> individual public keys (together with a message, and a multisignature). <em>Some</em> multisignature schemes (notably, the MuSig family ones) output a signature that can also be verified by a verifier who only knows an aggregate public key of all the co-signers (and thus being unaware what the individual public keys are, or even how many of them there are). We call those multisignature schemes, key aggregation schemes. That is what we want in Bitcoin, because (a) it doesn't require changing the consensus rules to accomodate and (b) is cheaper and more private as the individual keys do not need to be publicly revealed. So a key aggregation scheme is a special type of multisignature scheme. A key aggregation scheme is also <em>not</em> a signature aggregation scheme, as signature aggregation always requires the verifier to be aware of all signers, because they can all have different messages.</p>
</li>
<li><p><strong>In Bitcoin-speak, &quot;multisig&quot; refers to threshold signatures, not multisignatures.</strong> A threshold signature scheme is one where any subset of <em>k</em> out of <em>n</em> given public keys can sign (where multisignatures can be seen as a special case, with <em>k=n</em>).</p>
</li>
</ul>
<hr />
<p>So to answer your question, we need to talk about specific schemes. And schemes, as pointed out before, are a combination of key generation, signing, and verification algorithms.</p>
<ul>
<li><p><strong><a href="https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki" rel="noreferrer">BIP340</a></strong> defines key generation, signing, and verification, so it can be said to be a complete scheme. The verification side defines the consensus rules that apply to the spending of Taproot outputs in Bitcoin (see <a href="https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki" rel="noreferrer">BIP341</a> and <a href="https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki" rel="noreferrer">BIP342</a> for how). The signing algorithm is strictly for one signer though, so it is not a multisignature scheme or signature aggregation scheme at all.</p>
</li>
<li><p><strong>Naive (concatenation) multisignatures</strong> If we don't care that the multisignature is small, it's always possible to construct a multisignature scheme by just using a normal (non-multi) signature scheme, and concatenating all the signatures. Arguably, Bitcoin Scripts with multiple public keys can be seen as an instance of this (and even as a threshold signature scheme).</p>
<ul>
<li>Concatenation key generation: same as the underlying signature scheme.</li>
<li>Concatenation signing: same as the underlying signature scheme + concatenating the results.</li>
<li>Concatenation verification: splitting the resulting signature, and invoking the underlying signature verification for each</li>
</ul>
</li>
<li><p><strong><a href="https://eprint.iacr.org/2020/1261" rel="noreferrer">MuSig2</a></strong> defines a multisignature scheme, using the linearity property, which supports key aggregation. It needs two signing rounds, works with ordinary public keys (no special key generation algorithm is needed for the participants), and outputs a multisignature that can be verified against the aggregated key using the ordinary Schnorr (in the narrow sense) signature equation. <a href="https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki" rel="noreferrer">BIP327</a> defines a BIP340-compatible standard for MuSig2, which is thus usable on Bitcoin.</p>
<ul>
<li>MuSig2 key generation: identical to Schnorr, plus MuSig2 specific key aggregation.</li>
<li>MuSig2 signing: MuSig2-specific 2-round interactive protocol.</li>
<li>MuSig2 verification: Schnorr verification with aggregated key</li>
</ul>
</li>
<li><p><strong><a href="https://cseweb.ucsd.edu/%7Emihir/papers/multisignatures.pdf" rel="noreferrer">Bellare-Neven 2006</a></strong> defines a multisignature scheme, which does <em>not</em> support key aggregation. So while it permits multiple signers to cooperatively construct a single signature, verifying that signature requires knowledge of all individual public keys. And thus, while certainly Schnorr-based in its construction, the result is very much not a Schnorr signature, or even compatible with it.</p>
<ul>
<li>BN06 key generation: identical to Schnorr</li>
<li>BN06 signing: 3-round interactive BN06-specific protocol</li>
<li>BN06 verification: BN06-specific verification (using all keys).</li>
</ul>
</li>
<li><p><strong>Bellare-Neven 2006</strong> <em>also</em> explains how any multisignature scheme in general can be turned into an interactive aggregated signature scheme (IAS): just use the concatenation of all keys and messages as the multisignature message. Note however that that approach is not compatible with key aggregation, as the verifier inherently needs to be aware that there are multiple signers (each with their own message).</p>
<ul>
<li>BN06-IAS key generation: same as underlying multisignature scheme.</li>
<li>BN06-IAS signing: underlying multisignature on the concatenation of keys and messages as message.</li>
<li>BN06-IAS verification: underlying multisignature verification using the concatenation of keys and messages as message.</li>
</ul>
</li>
<li><p><strong><a href="https://eprint.iacr.org/2020/852" rel="noreferrer">FROST</a></strong> is a threshold signature scheme that is compatible with Schnorr signature verification. It can be seen as a generalization of MuSig2 in this regard, permitting only a subset of signers to produce a single signature that can be verified against a single aggregated public key. It does however have a far more complex setup; participants need to engage in an interactive protocol with each other to generate their keys, and can't just use ordinarily-generated public keys.</p>
<ul>
<li>FROST key generation: interactive key generation protocol</li>
<li>FROST signing: FROST-specific interactive signing protocol</li>
<li>FROST verification: Schnorr verification with aggregared key</li>
</ul>
</li>
</ul>
<p>There are <em>many</em> more schemes, with various levels of applicability to Bitcoin. I've listed just the above to give an idea of the level of variation that exists.</p>
<hr />
<p>Now to answer the question in the title:</p>
<blockquote>
<p>Is the Schnorr digital signature scheme a multisignature interactive scheme, and also not an aggregated non-interactive scheme?</p>
</blockquote>
<p>In the narrow sense, Schnorr digital signatures are not a multisignature or aggregated signature scheme at all.</p>
<p>In the wider sense, Schnorr-based schemes exist which are multisignature schemes (including key aggregation schemes), or signature aggregation schemes, or threshold schemes. They are however all interactive.</p>

CC BY-SA 4.0
2023-11-11T16:47:31.163Z
**Comments have been [moved to chat](https://chat.stackexchange.com/rooms/149649/discussion-on-answer-by-pieter-wuille-is-the-schnorr-digital-signature-scheme-a); please do not continue the discussion here.** Before posting a comment below this one, please review the [purposes of comments](/help/privileges/comment). Comments that do not request clarification or suggest improvements usually belong as an [answer](/help/how-to-answer), on [meta], or in [chat]. Comments continuing discussion may be removed.
Hannah Vernon
CC BY-SA 4.0
2023-11-10T15:33:51.930Z
2023-11-10T23:10:11.870Z
2023-11-10T23:10:11.870Z
Pieter Wuille
<p>In <a href="https://bitcoin.stackexchange.com/a/107200/145749">his answer</a> <em>Pieter Wuille</em> defined a concepts of <strong>multisignature scheme</strong> and <strong>aggregated signature scheme</strong> as follows:</p>
<blockquote>
<ul>
<li>A <strong>multisignature</strong> scheme is a scheme where multiple parties jointly produce a signature on a single message, which can be verified against the set of all participating public keys.</li>
<li>A <strong>aggregated signature</strong> scheme is a scheme where multiple parties jointly produce a signature, each on their own message, which can be verified against the set of all (pubkey,message) pairs.</li>
</ul>
</blockquote>
<p>Also, in <a href="https://bitcoin.stackexchange.com/a/85215/145749">another answer</a> he defined a concepts of <strong>non-interactive aggregation</strong> and <strong>interactive aggregation</strong> as follows:</p>
<blockquote>
<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>
</ul>
</blockquote>
<p>Since the Schnorr scheme provides the possibility for multiple parties to combine (merge) their public keys and also combine (merge) their signatures made over the <strong>SAME</strong> message, it is a <strong>multisignature scheme</strong>. Also, it is an <strong>interactive scheme</strong>, since the interaction between the participants is necessary in order to realize the given mergers (although this could also be done by a third party to which they would provide their individual public keys and individual signatures). On the other hand, the Schnorr scheme does not support the possibility of merging signatures created over <strong>DIFFERENT</strong> messages, so it is NOT <strong>an aggregation and non-interactive scheme</strong> (honestly, the description of these two concepts seems exactly the same to me, that is, they mean the same thing).</p>
<ol>
<li>Are these the correct properties of the Schnorr scheme?</li>
</ol>
<p>In <a href="https://bitcoin.stackexchange.com/a/85215/145749">the second linked answer</a> <em>Pieter Wuille</em> said that we cannot have one Schnorr signature on the block level since the Schnorr is interactive (we will ignore the fact that such a signature is certainly not possible because the signatures are <strong>over different content</strong>, but the focus is not on that). However, I would say that there does not need to be any interaction between the transaction creators in this case. The miner (third-party) can only collect all the signatures and merge them into one, while all the public keys are found in the referenced outputs, which can then also be taken and merged into one.</p>
<ol start="2">
<li>Since this is done by a third party, could we say that Schnorr is still in some way a non-interactive aggregation scheme if <strong>we look at the concept of interaction only through whether there is interaction between the signatories and not whether all the signatures are over the same message</strong>?</li>
</ol>
<p>Thanks in advance to all!</p>

<multi-signature><schnorr-signatures>
Is the Schnorr digital signature scheme a multisignature interactive scheme, and also not an aggregated non-interactive scheme?
LeaBit
# Is the Schnorr digital signature scheme a multisignature interactive scheme, and also not an aggregated non-interactive scheme?

(Asked by: username_0 on 2023-11-10)

In [his answer](https://bitcoin.stackexchange.com/a/107200/145749) *username_1 username_1* defined a concepts of **multisignature scheme** and **aggregated signature scheme** as follows:

> * A **multisignature** scheme is a scheme where multiple parties jointly produce a signature on a single message, which can be verified against the set of all participating public keys.
> * A **aggregated signature** scheme is a scheme where multiple parties jointly produce a signature, each on their own message, which can be verified against the set of all (pubkey,message) pairs.

Also, in [another answer](https://bitcoin.stackexchange.com/a/85215/145749) he defined a concepts of **non-interactive aggregation** and **interactive aggregation** as follows:

> * (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.

Since the Schnorr scheme provides the possibility for multiple parties to combine (merge) their public keys and also combine (merge) their signatures made over the **SAME** message, it is a **multisignature scheme**. Also, it is an **interactive scheme**, since the interaction between the participants is necessary in order to realize the given mergers (although this could also be done by a third party to which they would provide their individual public keys and individual signatures). On the other hand, the Schnorr scheme does not support the possibility of merging signatures created over **DIFFERENT** messages, so it is NOT **an aggregation and non-interactive scheme** (honestly, the description of these two concepts seems exactly the same to me, that is, they mean the same thing).

1. Are these the correct properties of the Schnorr scheme?

In [the second linked answer](https://bitcoin.stackexchange.com/a/85215/145749) *username_1 username_1* said that we cannot have one Schnorr signature on the block level since the Schnorr is interactive (we will ignore the fact that such a signature is certainly not possible because the signatures are **over different content**, but the focus is not on that). However, I would say that there does not need to be any interaction between the transaction creators in this case. The miner (third-party) can only collect all the signatures and merge them into one, while all the public keys are found in the referenced outputs, which can then also be taken and merged into one.

2. Since this is done by a third party, could we say that Schnorr is still in some way a non-interactive aggregation scheme if **we look at the concept of interaction only through whether there is interaction between the signatories and not whether all the signatures are over the same message**?

Thanks in advance to all!

**Tags:** multi-signature, schnorr-signatures


---

## 1 answers

### Answer by username_1 on 2023-11-10. Score: 8 | Accepted answer

I want to start by addressing a few misconceptions in your question:

1. **"Schnorr signatures" aren't really a well-defined signature scheme.** They're a class of digital signature schemes (with many possible instantiations, e.g. BIP340 and Ed25519), and in a wider sense even an abstract idea for building many types of signature schemes (including e.g. MuSig2, FROST, CoSi, BN06, ...). Historically, and in several answers on this site, I have not always made a clear distinction between them. In what follows, I'll call the latter "Schnorr-based". While there are properties that apply to many Schnorr-based schemes in general, the details vary a lot.
2. **"Adding signatures gives signature for sum of public keys" is a simplification.** It is an abstract mathematical property that applies to the verification equation of many Schnorr-based schemes (the fact that the equation is linear). This particular way of formulating it helps convey what it's useful for in an approximate way, but using it in practice in concrete schemes is not as simple. It's not just applying an addition function, and the co-signers need to be aware of each other, or the resulting sum won't be a valid signature. This is why the resulting signature aggregation schemes are said to be *interactive*, and don't lend themselves to block-wide aggregation for example. If it were possible to just hand the keys and signatures to a third party who could aggregate them, the result would be called non-interactive, but that's not the case here. There do exist other classes of signature schemes for which non-interactive aggregation is possible (notably, BLS), but for Schnorr-based schemes only interactive constructions are known.
3. **"Adding signatures gives signature for sum of public keys" is not on itself a scheme.** It's only a principle upon which multisignature and other more advanced schemes can be built. Even taking point (2) above into account, applying this principle naively as a multisignature scheme is woefully insecure. Secure schemes are non-trivial to get right (several published ones, including the first version of MuSig, were later shown to be broken), and appear to involve at least 2 or 3 interaction rounds between the signers. So we can't just talk about this being sort-of an implicit possibility that's part of the "Schnorr signature scheme"; you need to specify exactly which scheme is being considered.

Before continuing I also want to point out a few points of terminology:

* **The difference between *signature aggregation* and *multisignatures*.** In a multisignature scheme, there are multiple participants which jointly sign a *single* message, resulting in a single signature. In a signature aggregation scheme, there are multiple participants that jointly sign *their own* message, resulting in a single signature.
* **The difference between *key aggregation* and *multisignatures*.** According to the typical academic definition, a multisignature scheme involves a verifier who receives *all* individual public keys (together with a message, and a multisignature). *Some* multisignature schemes (notably, the MuSig family ones) output a signature that can also be verified by a verifier who only knows an aggregate public key of all the co-signers (and thus being unaware what the individual public keys are, or even how many of them there are). We call those multisignature schemes, key aggregation schemes. That is what we want in Bitcoin, because (a) it doesn't require changing the consensus rules to accomodate and (b) is cheaper and more private as the individual keys do not need to be publicly revealed. So a key aggregation scheme is a special type of multisignature scheme. A key aggregation scheme is also *not* a signature aggregation scheme, as signature aggregation always requires the verifier to be aware of all signers, because they can all have different messages.
* **In Bitcoin-speak, "multisig" refers to threshold signatures, not multisignatures.** A threshold signature scheme is one where any subset of *k* out of *n* given public keys can sign (where multisignatures can be seen as a special case, with *k=n*).

---

So to answer your question, we need to talk about specific schemes. And schemes, as pointed out before, are a combination of key generation, signing, and verification algorithms.

* **[BIP340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki)** defines key generation, signing, and verification, so it can be said to be a complete scheme. The verification side defines the consensus rules that apply to the spending of Taproot outputs in Bitcoin (see [BIP341](https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki) and [BIP342](https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki) for how). The signing algorithm is strictly for one signer though, so it is not a multisignature scheme or signature aggregation scheme at all.
* **Naive (concatenation) multisignatures** If we don't care that the multisignature is small, it's always possible to construct a multisignature scheme by just using a normal (non-multi) signature scheme, and concatenating all the signatures. Arguably, Bitcoin Scripts with multiple public keys can be seen as an instance of this (and even as a threshold signature scheme).

  + Concatenation key generation: same as the underlying signature scheme.
  + Concatenation signing: same as the underlying signature scheme + concatenating the results.
  + Concatenation verification: splitting the resulting signature, and invoking the underlying signature verification for each
* **[MuSig2](https://eprint.iacr.org/2020/1261)** defines a multisignature scheme, using the linearity property, which supports key aggregation. It needs two signing rounds, works with ordinary public keys (no special key generation algorithm is needed for the participants), and outputs a multisignature that can be verified against the aggregated key using the ordinary Schnorr (in the narrow sense) signature equation. [BIP327](https://github.com/bitcoin/bips/blob/master/bip-0327.mediawiki) defines a BIP340-compatible standard for MuSig2, which is thus usable on Bitcoin.

  + MuSig2 key generation: identical to Schnorr, plus MuSig2 specific key aggregation.
  + MuSig2 signing: MuSig2-specific 2-round interactive protocol.
  + MuSig2 verification: Schnorr verification with aggregated key
* **[Bellare-Neven 2006](https://cseweb.ucsd.edu/%7Emihir/papers/multisignatures.pdf)** defines a multisignature scheme, which does *not* support key aggregation. So while it permits multiple signers to cooperatively construct a single signature, verifying that signature requires knowledge of all individual public keys. And thus, while certainly Schnorr-based in its construction, the result is very much not a Schnorr signature, or even compatible with it.

  + BN06 key generation: identical to Schnorr
  + BN06 signing: 3-round interactive BN06-specific protocol
  + BN06 verification: BN06-specific verification (using all keys).
* **Bellare-Neven 2006** *also* explains how any multisignature scheme in general can be turned into an interactive aggregated signature scheme (IAS): just use the concatenation of all keys and messages as the multisignature message. Note however that that approach is not compatible with key aggregation, as the verifier inherently needs to be aware that there are multiple signers (each with their own message).

  + BN06-IAS key generation: same as underlying multisignature scheme.
  + BN06-IAS signing: underlying multisignature on the concatenation of keys and messages as message.
  + BN06-IAS verification: underlying multisignature verification using the concatenation of keys and messages as message.
* **[FROST](https://eprint.iacr.org/2020/852)** is a threshold signature scheme that is compatible with Schnorr signature verification. It can be seen as a generalization of MuSig2 in this regard, permitting only a subset of signers to produce a single signature that can be verified against a single aggregated public key. It does however have a far more complex setup; participants need to engage in an interactive protocol with each other to generate their keys, and can't just use ordinarily-generated public keys.

  + FROST key generation: interactive key generation protocol
  + FROST signing: FROST-specific interactive signing protocol
  + FROST verification: Schnorr verification with aggregared key

There are *many* more schemes, with various levels of applicability to Bitcoin. I've listed just the above to give an idea of the level of variation that exists.

---

Now to answer the question in the title:

> Is the Schnorr digital signature scheme a multisignature interactive scheme, and also not an aggregated non-interactive scheme?

In the narrow sense, Schnorr digital signatures are not a multisignature or aggregated signature scheme at all.

In the wider sense, Schnorr-based schemes exist which are multisignature schemes (including key aggregation schemes), or signature aggregation schemes, or threshold schemes. They are however all interactive.

> **Comments:**
> **username_2**: **Comments have been [moved to chat](https://chat.stackexchange.com/rooms/149649/discussion-on-answer-by-username_1-username_1-is-the-schnorr-digital-signature-scheme-a); please do not continue the discussion here.** Before posting a comment below this one, please review the [purposes of comments](/help/privileges/comment). Comments that do not request clarification or suggest improvements usually belong as an [answer](/help/how-to-answer), on [meta], or in [chat]. Comments continuing discussion may be removed.  

---

