Pixel: Multi-signatures for Consensus

Manu Drijvers, Sergey Gorbunov, Gregory Neven, and Hoeteck Wee

Abstract

In Proof-of-Stake (PoS) and permissioned blockchains, a committee of verifiers agrees and sign every new block of transactions. These blocks are validated, propagated, and stored by all users in the network. However, posterior corruptions pose a common threat to these designs, because the adversary can corrupt committee verifiers after they certified a block and use their signing keys to certify a different block. Designing efficient and secure digital signatures for use in PoS blockchains can substantially reduce bandwidth, storage and computing requirements from nodes, thereby enabling more efficient applications. 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, can be verified using three pairings and one exponentiation, and support non-interactive aggregation of individual signatures into a multi-signature. Pixel signatures are also forward-secure and let signers evolve their keys over time, such that new keys cannot be used to sign on old blocks, protecting against posterior corruptions attacks on blockchains. We show how to integrate Pixel into any PoS blockchain. Next, we evaluate Pixel in a real-world PoS blockchain implementation, showing that it yields notable savings in storage, bandwidth, and block verification time. In particular, Pixel signatures reduce the size of blocks with 1500 transactions by 35% and reduce block verification time by 38%.

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

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
multi-signatureforward securityblockchainaggregate signatureconsensusalgorand
Contact author(s)
manu @ dfinity org
sergey @ algorand com
hoeteck @ algorand com
gregory @ dfinity org
History
2019-12-03: revised
See all versions
Short URL
https://ia.cr/2019/514

CC BY

BibTeX

@misc{cryptoeprint:2019/514,
author = {Manu Drijvers and Sergey Gorbunov and Gregory Neven and Hoeteck Wee},
title = {Pixel: Multi-signatures for Consensus},
howpublished = {Cryptology ePrint Archive, Paper 2019/514},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/514}},
url = {https://eprint.iacr.org/2019/514}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.