Shipwright: Proving liveness of distributed systems with Byzantine participants
Derek Leung, Nickolai Zeldovich, Frans Kaashoek · 2025
Read Shipwright: Proving liveness of distributed systems with Byzantine participants by Derek Leung, Nickolai Zeldovich, Frans Kaashoek (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-14080.txt.
Introduction
Derek Leung, Nickolai Zeldovich, and Frans Kaashoek present Shipwright in a 2025 paper, a framework for proving that a distributed system keeps making progress even when some of its members act maliciously. Systems like PBFT, which let many machines agree on a shared log, have no single operator who can restart them, so a hidden stall bug can freeze them for good. Until now, no one had verified both correctness and this forward-progress property, called liveness, for a runnable version.
Shipwright adds three techniques. One supports reasoning about dishonest participants. Another splits systems and proofs into matching modular parts. A third handles digital signatures inside messages in a sound way. The team used it to build and verify a starter version of single-entry agreement in PBFT. They turned it into a working Go program and showed it running through normal operation and failure cases.
Catalog record
| CREATOR | Derek Leung, Nickolai Zeldovich, Frans Kaashoek |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 65 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-14080
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Shipwright: Proving liveness of distributed systems with Byzantine participants Derek Leung, Nickolai Zeldovich, Frans Kaashoek Abstract Ensuring liveness in a decentralized system, such as PBFT, is critical, because there may not be any single administrator that can restart the system if it encounters a liveness bug. At the same time, liveness is challenging to achieve because any single participant could be malicious, and yet the overall system must make forward progress. While verification is a promising approach for ensuring the absence of bugs, no prior work has been able to verify liveness for an executable implementation of PBFT. Shipwright is a verification framework for proving correctness and liveness of distributed systems where some participants might be malicious. Shipwright introduces three techniques that enable formal reasoning about decentralized settings with malicious participants, allow developers to decompose their system and proof in a modular fashion into sub-protocols and sub-proofs, and support sound reasoning about cryptographic signatures that may be embedded in messages. We used Shipwright to implement and verify an initial prototype of agreement on a single log entry in PBFT (with a few limitations) and translate it to an executable implementation in Go. We experimentally demonstrate its operation and liveness both in the common case and in several failure scenarios. 1 Introduction Decentralized distributed systems operate in a challenging environment where not all participants might behave correctly. For example, Byzantine fault tolerant protocols are designed to tolerate arbitrary misbehavior from some fraction of participating nodes, such as in blockchains and key-transparency systems. In this setting, developers must ensure their system achieves not just safety but also liveness —that is, that the overall system keeps making progress. Ensuring liveness in the presence of Byzantine participants is hard, because malicious participants can endlessly delay messages, retransmit the same messages over and over, cause restarts, etc. Moreover, many systems that worry about Byzantine participants are open systems , meaning there is no single administrator in charge. As a result, if a liveness bug were to happen in a blockchain system or a key transparency system, there would be no administrator that could restart all of the servers and get the system running again. Thus, for open distributed systems, liveness becomes a critical concern at the same level as functional correctness (safety). This paper introduces Shipwright, a new framework for machine-checked verification of distributed systems, which enables developers to prove both safety and liveness properties of their implementation. Using Shipwright, we verify an implementation of the core PBFT [ 4 ] protocol. The formal proof ensures that, regardless of what the adversarial Byzantine participants do, the PBFT system with nodes running our verified implementation will be correct (safety) and will make progress (liveness) in all possible cases. Consider an example mistake that we inadvertently made in our PBFT implementation and caught with Shipwright. When one view of PBFT fails to reach consensus, a node can send a view-change message to other participants in an attempt to make progress in the next view of the protocol. View-change messages in PBFT must prove that the sender has seen enough messages from other participants to merit switching to a new view. This is done by including signed messages from other participants as part of a view-change message. Our implementation had a bug where, in some situations, a node would include signatures from the wrong previous view as part of a view-change message. Other participants would check the signatures in this view-change message, discover that the signed message is not what they were expecting, and then reject it. This would not lead to a safety violation—no invalid signatures would have been accepted, and no incorrect outcome would be produced—but it would lead to a liveness violation because the system might never move on to the next view. More precisely, the bug is triggered following a series of events. First, the network drops all commit messages for some number of views k but permits prepare and view-change messages to propagate. This prevents termination but causes some value v to become \emph{prepared} , which means it must show up in all subsequent view changes. Next, the network drops all prepare messages from view k+1 . Then, the network fully recovers for all messages in subsequent views k^{\prime}>k+1 . All nodes sign off on the view-change for value v having prepared at view k , which an honest primary attaches to the new-view message kicking off view k+2 —only for the nodes to reject the signatures of the view-change messages (that they just created), due to a bug in the byte-level re-encoding of the view-change message plaintext within the new-view message. In fact, this holds for all future k^{\prime}>k+1 , so the protocol never terminates. As described in §2 , Shipwright is the first framework that can verify liveness of distributed system implementations and ensure the absence of bugs such as the one described above. Shipwright’s design addresses two key challenges. First, Shipwright must enable modular verification of liveness. This means that developers can use Shipwright to decompose overall protocols into smaller sub-protocols that logically execute in parallel, such as the proposal, voting, and view-change sub-protocols in PBFT [ 4 ] . This reduces the amount of state that the developer has to reason about at one time, enables proof automation, and allows reuse of components (such as reusing the same broadcast primitive for both the prepare and commit steps in PBFT). Achieving this sort of modularity is a challenging problem because liveness is a global property. For example, classical horizontal composition (combining two independent sub-protocols) does not work well in the presence of a global clock that all sub-protocols use for their timeouts, which in turn impacts liveness. Similarly, vertical layering of refinement proofs requires care in ensuring that liveness properties are preserved, and, in particular, that there are no infinite stuttering steps in a refinement proof. Second, Shipwright must formally reason about Byzantine nodes. To be sound, Shipwright’s model must allow Byzantine participants to send arbitrary messages over the network. However, simply assuming that network messages are untrustworthy is too strong because real systems rely on some fraction of honest nodes to achieve safety and liveness. Similarly, Byzantine nodes cannot send an infinite number of messages that effectively stop the system’s progress by flooding the network. Moreover, Byzantine nodes cannot produce fake cryptographic signatures, which are often necessary in these protocols for both safety and liveness; at the same time, we do not want to explicitly model the details and probabilistic definitions of signature scheme security, as this would substantially complicate verification. To address these challenges, Shipwright introduces several key techniques. The first is an encoding of liveness conditions in terms of tasks that correspond to local completion measures , which enables Shipwright to translate liveness statements about infinite executions into proof obligations about pairs of states. These statements are more amenable to automated verification. The second is a liveness-preserving composition operator , which enables developers to decompose complex protocols into simpler components, such as composing the prepare and commit sub-protocols of a single PBFT view, or composing an unbounded number of views to agree on a single value in PBFT. Finally, to soundly reason about Byzantine nodes, Shipwright introduces