Département Informatique

Computer Science Department of Telecom SudParis

Polygraph: Accountable Byzantine Agreement

Reading group: Luciano Freitas De Souza presented "Polygraph: Accountable Byzantine Agreement" (Research report) in visio the 11/12/2020 at 10h00.

You can find the video of the presentation here.


In this paper, we introduce Polygraph, the first accountable Byzantine consensus algorithm for partially synchronous systems. If among n users t < 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 < 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.