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