Signature Aggregation / Multi-Signature

Question

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.

• Signature Aggregation
• Multi-Signatures in the Plain Public-Key Model and a General Forking Lemma
• Signature aggregation for improved scalability

Answer 1

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.