Cryptology ePrint Archive: Report 2019/587

Polygraph: Accountable Byzantine Agreement

Pierre Civit and Seth Gilbert and Vincent Gramoli

Abstract: In this paper, we introduce \emph{Polygraph}, the first accountable Byzantine consensus algorithm for partially synchronous systems. If among $n$ users $t<\frac{n}{3}$ are malicious then it ensures consensus, otherwise it eventually detects malicious users that cause disagreement. Polygraph is appealing for blockchain applications as it allows them, if $t<\frac{n}{3}$, to totally order blocks in a chain, hence avoiding forks and double spending and, otherwise, to punish malicious users when a fork occurs. We first show that stronger forms of the problem including a fixed time detection are impossible to solve before proving our solution. We also show that Polygraph has a bounded justification size so that each of its asynchronous rounds exchanges only $O(n^2)$ messages. Finally, we use a blockchain application to evaluate Polygraph on a geodistributed system of 80 machines and show that accountability reduces the performance of the non-accountable baseline by about a third, still committing thousands of transactions per second.

Category / Keywords: cryptographic protocols / accountability, blockchain, red belly, DBFT

Date: received 29 May 2019, last revised 19 Jun 2019

Contact author: vincent gramoli at sydney edu au

Available format(s): PDF | BibTeX Citation

Version: 20190619:192718 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]