January 18, 2022
Pierre Civit
Consider a distributed protocol whose n processes ensure some (distributed) safety and liveness properties, communicating with each other without synchrony, despite a certain the number t of Byzantine processes. It has been known for decades that such distributed protocols cannot ensure safety as soon as more than a threshold of t_0 processes fail, typically one third of the processes.
By contrast, only recently did the community discover that some of these distributed protocols can be made accountable by ensuring that correct processes detect at least t_0 + 1 faulty processes responsible of any safety violation. This is particularly surprising (and positive) given that accountability is a powerful tool to mitigate safety violations in distributed protocols. Indeed, exposing crimes and punishments naturally incentivizes exemplarity.
We propose a generic transformation of any distributed protocol into an accountable version of this protocol. First, we partition the commission faults into two classes: the equivocation faults and the evasion faults and illustrate why the former are are easier and less cumbersome to detect than the latter. Our transformation builds upon the secure broadcast primitive in a way ensuring that every safety violation is necessarily a consequence of equivocation faults.
Due to the secure broadcast primitive, our transformation increases the communication and message complexities of the original distributed protocol by an O(n^2) multiplicative factor in the worst case.