Paper 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.