Paper 2019/514

Pixel: Multi-signatures for Consensus

Manu Drijvers and Sergey Gorbunov and Gregory Neven and Hoeteck Wee

Abstract

Multi-signatures enable a group of signers to jointly generate a short and efficiently verifiable signature on a common message. They are commonly used in proof-of-stake and permissioned blockchains, where reaching consensus usually involves a committee of nodes signing the next block. Adaptive corruptions, however, pose a common threat to such designs, because the adversary can corrupt committee members after they certified a block (and possibly after they sold their stake) and use their signing keys to fork the chain by certifying a different block, thereby undermining the main security goal of a blockchain. Forward-secure signatures protect against such attacks by letting signers evolve their keys over time, while keeping the verification key constant. We present Pixel, a pairing-based forward-secure multi-signature scheme optimized for use in blockchains, that achieves substantial savings in bandwidth, storage requirements, and verification effort. Pixel signatures consist of two group elements, regardless of the number of signers, and can be verified using three pairings and one exponentiation; they also support non-interactive aggregation of individual signatures into a multi-signature. We prove our scheme secure in the random-oracle model under a suitable variant of the bilinear Diffie-Hellman inversion problem.

Note: Merge of ePrint reports 2019/261 and 2019/269