Boneh等人2018年论文《Compact Multi-Signatures for Smaller Blockchains》 在《Simple Schnorr Multi-Signatures with Applications to Bitcoin》论文的Musig方案的基础上，做了改进。（参见博客 Simple Schnorr Multi-Signatures with Applications to Bitcoin 学习笔记）
本论文的设计目标是： reduce the size of the Bitcoin blokchain。
- 支持signature compression。
- 支持public-key aggregation。
- multi-signature scheme：a number of parties signed a common message m m m。 满足completeness和unforgeability特性。
- 基于Schnorr signatures和BLS signatures。
- 支持plain public key model，即：users do not need to prove knowledge or possession of their secret key。
- 构建了第一个short accountable-subgroup multi-signature (ASM) scheme。
- ASM（Accountable-Subgroup Multi-signautres）的signature size 仅为 O ( k ) \mathcal{O}(\mathcal{k}) O(k) bits over the description of S S S，其中 k \mathcal{k} k为security parameter。
- aggregate public key 仅为 O ( k ) \mathcal{O}(\mathcal{k}) O(k) bits，与 n n n无关。
- 与Musig的基于Schnorr signature实现相比，本论文是基于BLS signature（即pairings）来实现的，提出了BLS-based multi-signature scheme MSP和AMSP。
- 有重点关注 t − o f − n t-of-n t−of−n Multisig address，不再像Musig方案那样受限于 ( n t ) \binom{n}{t} (tn)的组合数。【ASM特别适合 t − o f − n t-of-n t−of−n signatures when ( n t ) \binom{n}{t} (tn) is very large.】
- Aggregate signatures [12, 24, 1] are a closely related concept where signatures by different signers on different messages can be compressed together.
- Sequential aggregate signatures [33, 32, 41, 14, 23] are a variant where signers take turns adding their own signature onto the aggregate.
代码实现: https://github.com/lovesh/signature-schemes https://github.com/KZen-networks/multi-party-schnorr 【第5章实现，类似Musig方案】
1.1 ASM定义ASM (accountable-subgroup multi-signature)是指： enables any subset S S S of a set of n n n parties to sign a message m m m so that a valid signature discloses which subset generated the signature (hence the subset S S S is accountable for signing m m m)。
1.2 multi-signature scheme定义multi-signature 多重签名 scheme是指： a protocol that 允许 n n n 个签名者对消息 m m m 进行联合签名生产short signature σ \sigma σ， σ \sigma σ可让verifier相信所有的 n n n 个签名者均对消息 m m m 进行了签名。
相应的多重签名验签算法为：
- 输入为： n n n 个签名者的公钥，消息 m m m，多重签名 σ \sigma σ；
- 输出为：接受 σ \sigma σ为 n n n个签名者对消息 m m m的联合签名。
多重签名应具有的特性是：
- 多重签名 σ \sigma σ should be short；
- σ \sigma σ的长度应与签名者数量 n n n 无关。
多重签名可基于Schnorr signature以及BLS signature等构建。
1.3 aggregate signature scheme定义aggregate signature 聚合签名 scheme是指： 允许 n n n 个签名者对不同的消息进行签名，最终所有的签名将聚合为a single short signature σ \sigma σ。
相应的聚合签名验签算法为：
- 输入为： n n n 个签名者的公钥 ( P 1 , ⋯ , P n ) (P_1,\cdots,P_n) (P1,⋯,Pn)， n n n个消息 ( m 1 , ⋯ , m n ) (m_1,\cdots,m_n) (m1,⋯,mn)，聚合签名 σ \sigma σ；
- 输出为：接受 σ \sigma σ为 P 1 对 m 1 签 名 ， ⋯ ， P n 对 m n 签 名 P_1对m_1签名，\cdots，P_n对m_n签名 P1对m1签名，⋯，Pn对mn签名 的聚合签名。
multi-sgiantures和aggregate signatures可用于对Bitcoin blockchain的size进行瘦身。
- 在Blockstream 团队 Maxwell等人2018年论文《Simple schnorr multi-signatures with applications to bitcoin》（可参见博客 Simple Schnorr Multi-Signatures with Applications to Bitcoin 学习笔记）中提出了a Schnorr-based multi-sgnature scheme （Musig方案），可use multi-signatures to shrink the transaction data associated with Bitcoin Multisig addresses。 理论上，a Multisig address为：n个public keys p k 1 , ⋯ , p k n pk_1,\cdots,pk_n pk1,⋯,pkn和threshold t ∈ { 1 , ⋯ , n } t\in \{1,\cdots,n\} t∈{1,⋯,n}的hash值。 为了花费Multisig address上的资金，需要创建一个transaction，该transaction内包含：所有 n n n 个public keys （ p k 1 , ⋯ , p k n pk_1,\cdots,pk_n pk1,⋯,pkn） + t t t 个有效签名（from t t t of the n n n public keys）。然后将该transaction写入到区块链中。 这 t t t个签名签署的是相同的内容——即transaction data。 实际使用时，通常会取 t = n t=n t=n，即要求所有的签名者均签名后才可花费该地址的资金。将所有 n n n个签名通过multi-signature scheme压缩为a signle short signature，将有效缩减overall transaction size，从而减少写入到区块链中的数据量。 Maxwell的Musig方案也可用于 t < n tt ∣S∣>t，即可将ASM表示为threshold signature scheme whereby the signature also authenticates the set of signers that participated.】
所有签名者都有全局统一的index。 To participate in a group of signatures P K = { p k 1 , ⋯ , p k n } \mathcal{PK}=\{pk_1,\cdots,pk_n\} PK={pk1,⋯,pkn}, each signer in P K \mathcal{PK} PK runs the interactive algorithm G S e t u p ( s k , P K ) GSetup(sk,\mathcal{PK}) GSetup(sk,PK) to obtain a membership key m k mk mk。
ASM也应满足完备性和不可伪造性要求。
ASM构建过程中引入了3个hash函数
H
0
:
{
0
,
1
}
∗
→
G
1
,
H
1
:
{
0
,
1
}
∗
→
Z
q
,
H
2
:
{
0
,
1
}
∗
→
G
2
H_0:\{0,1\}^*\rightarrow\mathbb{G}_1,H_1:\{0,1\}^*\rightarrow\mathbb{Z}_q,H_2:\{0,1\}^*\rightarrow\mathbb{G}_2
H0:{0,1}∗→G1,H1:{0,1}∗→Zq,H2:{0,1}∗→G2，总的算法流程如下： 
针对Maxwell早期论文版本的改进。与最新的Musig方案一致。 
在第2节中提到，抵御rogue key attack的方式之一是：要求每个签名者证明其拥有与所声称公钥相应的私钥。 即对于不论是BLS-based还是Schnorr-based multi-signature，都可以要求所有的签名者provide a proof of possession (PoP) of their secret key。
Proofs of possession最主要的缺点是：将增加单个public key的size，但是对于不关注单个key size的情况下仍然有应用场景。如：Bitcoin的Multisig addresses，仅需在区块链上记录aggregate public key，而各个单独的public keys仅与签名者相关，可以kept off-chain 链下存储，或者仅需要验证一次就不再需要。以及other applications may involve a more or less static set of signing nodes whose keys can be verified once and used in arbitrary combinations thereafter.
4.1 Pairing-based schemes with PoPs
