Paper 2018/414

Aggregation of Gamma-Signatures and Applications to Bitcoin

Yunlei Zhao


Aggregate signature (AS) allows non-interactively condensing multiple individual signatures into a compact one. Besides the faster verification, it is useful to reduce storage and bandwidth, and is especially attractive for blockchain and cryptocurrency. In this work, we first demonstrate the subtlety of achieving AS from general groups, by a concrete attack that actually works against the natural implementations of AS based on almost all the variants of DSA and Schnorr’s. Then, we show that aggregate signature can be derived from the Γ-signature scheme proposed by Yao, et al. To the best of our knowledge, this is the first aggregate signature scheme from general elliptic curves without bilinear maps (in particular, the secp256k1 curve used by Bitcoin). The security of aggregate Γ-signature is proved based on a new assumption proposed and justified in this work, referred to as non-malleable discrete-logarithm (NMDL), which might be of independent interest and could find more cryptographic applications in the future. When applying the resultant aggregate Γ-signature to Bitcoin, the storage volume of signatures reduces about 49.8%, and the signature verification time can evenreduce about 72%. Finally, we specify in detail the application of the proposed AS scheme to Bitcoin, with the goal of maximizing performance and compatibility. We adopt a Merkle-Patricia tree based implementation, and the resulting system is also more friendly to segregated witness and provides better protection against transaction malleability attacks.

Note: Made the following major modificaitons: (1) Add a proof of the NMDL assumption in the generic group model. (2) The performance improvement is calculated in a more precise way.

Available format(s)
Publication info
Preprint. MINOR revision.
Contact author(s)
ylzhao @ fudan edu cn
2018-12-05: revised
2018-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yunlei Zhao},
      title = {Aggregation  of Gamma-Signatures and  Applications to Bitcoin},
      howpublished = {Cryptology ePrint Archive, Paper 2018/414},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.