# Signature Aggregation / Multi-Signature

I want to save the space signatures take up in a block of Bitcoin transactions. To simplify it, here is the general transaction structure in a block:

• message
• public key
• signature of the message

There are many transactions in one block and I want to save the space the signature takes by using signature aggregation. The signatures in one block are under many different public keys and on distinct messages.

I found these interesting articles about it, but I am not sure that they solve my exact problem. Please tell me if the solution to my problem can be found in one of those articles or point me in a new direction or explain to me why this is not possible.

• You ask for a solution to your "exact problem" but you do not exactly specify what your problem is. Are we talking about mutliple signatures under the same key o different messages? Diferent keys but same message? Different keys and different messages? Can the signers communicate during signing? Must aggregation take place sequentially? – Maeher Jan 30 '18 at 18:55
• Different keys and different messages, signers cannot communicate during signing, the aggregation does not have to take place sequentially but it could – Ilya Gazman Jan 30 '18 at 19:02
• In that case, what you are looking for is an aggregate signature scheme such as the construction in Section 3.1 of this paper. – Maeher Jan 30 '18 at 19:17
• It is not the only scheme. There many different aggregate signature schemes with different properties and based on different assumptions. I'm pretty sure that someone at some point must have implemented at least some of those schemes. But I'm very much a theorist and don't know too much about implementation stuff. So sadly I can't point you anywhere. – Maeher Jan 30 '18 at 21:41
• – Maeher Jan 31 '18 at 7:45

A multisignature scheme would be a signature scheme where several parties all sign the same message. So this is not what we are looking for.

What we are looking for is called an aggregate signature scheme. In such a scheme, we have $\ell$ distinct users, each with their own public key $\mathsf{pk}_i$. Each of those users has a distinct message $m_i$ that they would like to sign. The goal of the aggregate signature scheme is to create a single short signature that convinces any verifier that each user $i$ did indeed sign their respective message $m_i$.

To do so, there in general exist five algorithms:

• $\mathsf{KGen}(1^n)$: outputs a keypair $(\mathsf{sk_i},\mathsf{pk_i})$.
• $\mathsf{Sign}(\mathsf{sk_i},m_i)$: outputs a signature $\sigma_i$.
• $\mathsf{Vfy}(\mathsf{pk_i},m_i,\sigma_i)$: outputs $1$ if the signature is valid and $0$ otherwise.
• $\mathsf{Agg}((\mathsf{pk_1},\dots,\mathsf{pk_\ell}),(m_1,\dots,m_\ell),(\sigma_1,\dots,\sigma_\ell))$: outputs an aggregate signature $\sigma$.
• $\mathsf{AggVfy}((\mathsf{pk_1},\dots,\mathsf{pk_\ell}),(m_1,\dots,m_\ell),\sigma)$: outputs $1$ if the aggregate signature is valid for all messages and $0$ otherwise.

Standard Correctness applies, i.e. for all messages $m_i$ and all key pairs $(\mathsf{sk}_i,\mathsf{pk}_i) \gets \mathsf{KGen}(1^n)$ it holds that $$\mathsf{Vfy}(\mathsf{pk_i},m_i,\mathsf{Sign}(\mathsf{sk_i},m_i)) = 1$$ and $$\mathsf{AggVfy}\left((\mathsf{pk_1},\dots,\mathsf{pk_\ell}),(m_1,\dots,m_\ell),\mathsf{Agg}\left(\begin{array}{c}(\mathsf{pk_1},\dots,\mathsf{pk_\ell}),(m_1,\dots,m_\ell),\\(\mathsf{Sign}(\mathsf{sk_1},m_1),\dots,\mathsf{Sign}(\mathsf{sk_\ell},m_\ell)\end{array}\right)\right) = 1$$

In addition to standard unforgeability we also require unforgeability of aggregated signatures. I.e. we require that for all polynomial time adversaries $\mathcal{A}$ there exists a negligible function $\epsilon(n)$ such that $$\Pr_{(\mathsf{sk}_1,\mathsf{pk}_1) \gets \mathsf{KGen}(1^n)}\left[\mathsf{AggVfy}\left(\begin{array}{c}(\mathsf{pk_1},\dots,\mathsf{pk_\ell}),\\(m_1,\dots,m_\ell),\sigma\end{array}\right) :\left(\begin{array}{c}\mathsf{pk}_2,\dots,\mathsf{pk}_\ell,\\m_1,\dotsm_\ell,\sigma\end{array}\right)\gets\mathcal{A}^{\mathsf{Sign}(\mathsf{sk}_1,\cdot)}(\mathsf{pk}_1)\right] \leq \epsilon(n)$$

The first instantiation of such a signature scheme is due to Boneh, Gentry, Lynn, and Shacham in their paper Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. (See specifically Section 3.1.) In their scheme an arbitrary number of signatures can be aggregated in an aggregate signature that consists only of a single group element.

There are many other instantiations of this primitive from different assumptions and with special properties such as the ability to do sequential aggregation.

While some of those schemes have probably been implemented at least benchmarking purposes, I'm not aware of any crypto library implementing aggregate signatures.