### Polygraph: Accountable Byzantine Agreement

Pierre Civit, Seth Gilbert, and Vincent Gramoli

##### Abstract

In this paper, we introduce \emph{Polygraph}, the first accountable Byzantine consensus algorithm. If among $n$ users $t<n/3$ are malicious then it ensures consensus; otherwise (if $t \geq n/3$), it eventually detects malicious users that cause disagreement. Polygraph is appealing for blockchain applications as it allows them to totally order blocks in a chain whenever possible, hence avoiding forks and double spending and, otherwise, to punish (e.g., via slashing) at least $n/3$ malicious users when a fork occurs. This problem is more difficult than perhaps it first appears. One could try identifying malicious senders by extending classic Byzantine consensus algorithms to piggyback signed messages. We show however that to achieve accountability the resulting algorithms would then need to exchange $\Omega(\kappa \cdot n^2)$ more bits, where $\kappa$ is the security parameter of the signature scheme. By contrast, Polygraph has communication complexity $O(\kappa \cdot n^4)$. Finally, we implement Polygraph in a blockchain committing more than 10,000\,TPS when deployed on 80 geodistributed machines.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
accountabilityblockchainred bellyDBFT
Contact author(s)
vincent gramoli @ sydney edu au
History
2021-01-18: last of 3 revisions
See all versions
Short URL
https://ia.cr/2019/587

CC BY

BibTeX

@misc{cryptoeprint:2019/587,
author = {Pierre Civit and Seth Gilbert and Vincent Gramoli},
title = {Polygraph: Accountable Byzantine Agreement},
howpublished = {Cryptology ePrint Archive, Paper 2019/587},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/587}},
url = {https://eprint.iacr.org/2019/587}
}

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