Paper 2018/414

Aggregation of Gamma-Signatures and Applications to Bitcoin

Yunlei Zhao

Abstract

Aggregate signature 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. For example, aggregate signature can mitigate some bottlenecks emerged with the Bitcoin systems (and actually almost all blockchain-based systems): low throughput, capacity, scalability, high transaction fee, etc. Unfortunately, achieving aggregate signature from general elliptic curve group (without bilinear maps) is a long-standing open question. Recently, there is also renewed interest in deploying Schnorr's signature in Bitcoin, for its efficiency and flexibility. In this work, we investigate the applicability of the Gamma-signature scheme proposed by Yao and Zhao. Akin to Schnorr's, Gamma-signature is generated with linear combination of ephemeral secret-key and static secret-key, and enjoys almost all the advantages of Schnorr's signature. Besides, Gamma-signature has salient features in online/offline performance, stronger provable security, and deployment flexibility with interactive protocols like IKE. In this work, we identify one more key advantage of Gamma-signature in signature aggregation, which is particularly crucial for applications to blockchain and cryptocurrency. Specifically, we first observe the incapability of Schnorr's for aggregating signatures in the Bitcoin system. This is demonstrated by concrete attacks. Then, we show that aggregate signature can be derived from the Gamma-signature scheme. To the best of our knowledge, this is the first aggregate signature scheme from general groups without bilinear maps. The security of aggregate Gamma-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 Gamma-signature to Bitcoin, the storage volume of signatures reduces about 50%, and the signature verification time can even reduce about 80%. Finally, we specify in detail the implementation of aggregate Gamma-signature in Bitcoin, with minimal modifications that are in turn more friendly to segregated witness (SegWit) and provide better protection against transaction malleability attacks.