Paper 2018/414

Aggregation of Gamma-Signatures and Applications to Bitcoin

Yunlei Zhao

Abstract

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.