**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: **ia.cr/2019/587

[ Cryptology ePrint archive ]