Crime and Punishment in Distributed Byzantine Decision Tasks

Pierre Civit, Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic, Zarko Milosevic, Adi Seredinschi

TL;DR

This paper introduces a generic transformation, Tscr, that makes any non-synchronous distributed protocol "accountable." This means that if a protocol fails to maintain its safety guarantees (e.g., in a blockchain, preventing double-spending), correct processes can definitively identify the faulty participants and obtain irrefutable proof of their misbehavior. This is crucial for building more robust and trustworthy distributed systems.

What Problem Does This Paper Address?

Distributed systems often rely on decision tasks, like reaching consensus or broadcasting information reliably, where multiple processes must agree on an outcome. However, in the presence of "Byzantine" failures (where processes can act arbitrarily and maliciously), achieving guaranteed safety (preventing incorrect outcomes) is impossible if too many processes fail. For decades, this has been a fundamental limitation.

While protocols can be designed to tolerate a certain number of Byzantine failures, they often fail in "unlucky scenarios." The challenge this paper addresses is how to go beyond just tolerating failures to actively punishing those responsible when safety is violated. This "accountability" is a powerful deterrent and helps in debugging and understanding system failures. Existing solutions for accountability are often specific to particular protocols and settings, and a generic approach for non-synchronous systems was missing.

Methods

The core contribution is a generic transformation called Tscr. This transformation takes any existing non-synchronous distributed protocol that solves a decision task and turns it into an "accountable" version. The key ideas behind Tscr are:

  • Simulating Crash Failures: Tscr leverages a well-studied technique of simulating crash failures on top of Byzantine failures. This is achieved by using a secure broadcast primitive. Messages are not immediately delivered; instead, they are first "secure-broadcast" and then "valid-delivered" only after a verification process confirms their legitimacy and causal history.
  • Masking Evasion Faults: A crucial insight is that "evasion faults" (where a process fails to send a message it should have, or sends one without proper prerequisites) are hard to detect directly. Tscr effectively masks these faults, ensuring that only "commission faults" (specifically, "equivocation faults" where a process sends conflicting messages) can lead to safety violations.
  • Hierarchical Composition: The Tscr transformation is built by composing several modules: a state-machine layer, a verification layer, a secure broadcast layer, and a network layer. The verification layer is central to ensuring that only "benign" executions reach the state-machine layer.
  • Proof of Culpability: The transformation ensures that when safety is violated, correct processes can gather irrefutable evidence (proof of culpability) against the faulty processes. This evidence is derived from the conflicting messages (equivocations) that are allowed to manifest as safety violations.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Accountability as a Deterrent: The paper argues that accountability (identifying culprits and providing proof) is a powerful incentive for processes to behave correctly, mitigating safety violations.
  • Commission Faults are Key: For accountability in non-synchronous systems, it's essential to detect "commission faults." The paper proves that irrevocable detections must be based on detected commission faults, and that safety violations imply that "enough" processes have committed them.
  • Equivocation vs. Evasion: Equivocation faults (conflicting messages) are easier to detect and prove than evasion faults. Tscr cleverly masks evasion faults, focusing detection on equivocations.
  • Generic Solution: The Tscr transformation provides a general method to add accountability to any non-synchronous distributed protocol, rather than requiring protocol-specific redesigns.

Key Results

  • The paper introduces the Tscr transformation, which makes any non-synchronous distributed protocol accountable.
  • Tscr achieves accountability with a factor of f = min([n/3] – 1, to), where n is the total number of processes and to is the original protocol's resiliency.
  • The transformation increases communication and message complexity by an O(n²) multiplicative factor in the worst case.
  • The paper formally proves that Tscr preserves the original protocol's safety and liveness properties and provides accountability.
  • The theoretical framework is extended to cover randomized distributed protocols and committee-based blockchains.

Limitations and Future Work

  • Complexity Overhead: The O(n²) communication complexity overhead of Tscr is a significant drawback. Future work aims to reduce this by focusing on specific distributed protocols.
  • Permissionless Blockchains: While Tscr is adapted for committee-based blockchains, achieving sub-quadratic communication complexity remains an area of active research.
  • Randomized Protocols: The application to randomized protocols relies on specific assumptions about safety being deterministically ensured and liveness not requiring private channels.
  • Practical Implementation: The paper focuses on theoretical guarantees. Practical implementation details and performance tuning for real-world systems would be a valuable next step.

Summary updated

Abstract

A decision task is a distributed input-output problem in which each process starts with its input value and eventually produces its output value. Examples of such decision tasks are broad and range from consensus to reliable broadcast to lattice agreement. A distributed protocol solves a decision task if it enables processes to produce admissible output values despite arbitrary (Byzantine) failures. Unfortunately, it has been known for decades that many decision tasks cannot be solved if the system is overly corrupted, i.e., safety of distributed protocols solving such tasks can be violated in unlucky scenarios.By contrast, only recently did the community discover that some of these distributed protocols can be made accountable by ensuring that correct processes irrevocably detect some faulty processes responsible for any safety violation. This realization is particularly surprising (and positive) given that accountability is a powerful tool to mitigate safety violations in distributed protocols. Indeed, exposing crimes and introducing punishments naturally incentivize exemplarity.In this paper, we propose a generic transformation, called τ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">scr</inf> , of any non-synchronous distributed protocol solving a decision task into its accountable version. Our τ <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">scr</inf> transformation is built upon the well-studied simulation of crash failures on top of Byzantine failures and increases the communication complexity by a quadratic multiplicative factor in the worst case.
BibTeX
@article{civit2022crime,
  author = {Pierre Civit and Seth Gilbert and Vincent Gramoli and Rachid Guerraoui and Jovan Komatovic and Zarko Milosevic and Adi Seredinschi},
  title = {{Crime and Punishment in Distributed Byzantine Decision Tasks}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2022},
}

Loading related content...

Figure