Giuliano Losa

Nibesh Shrestha, Qianyu Yu, Aniket Kate et al.

Reliable broadcast (RBC) is a key primitive in fault-tolerant distributed systems, and improving its efficiency can benefit a wide range of applications. This work focuses on signature-free RBC protocols, which are particularly attractive due to their computational efficiency. Existing protocols in this setting incur an optimal 3 steps to reach a decision while tolerating up to $f < n/3$ Byzantine faults, where $n$ is the number of parties. In this work, we propose an optimistic RBC protocol that maintains the $f < n/3$ fault tolerance but achieves termination in just 2 steps under certain optimistic conditions--when at least $\lceil \frac{n+2f-2}{2} \rceil$ non-broadcaster parties behave honestly. We also prove a matching lower bound on the number of honest parties required for 2-step termination. We show that our latency-reduction technique generalizes beyond RBC and applies to other primitives such as asynchronous verifiable secret sharing (AVSS) and asynchronous verifiable information dispersal (AVID), enabling them to complete in 2 steps under similar optimistic conditions. To highlight the practical impact of our RBC protocol, we integrate it into Sailfish++, a new signature-free, post-quantum secure DAG-based Byzantine fault-tolerant (BFT) consensus protocol. Under optimistic conditions, this protocol achieves a commit latency of 3 steps--matching the performance of the best signature-based protocols. Our experimental evaluation shows that our protocol significantly outperforms existing post-quantum secure and signature-based protocols, even on machines with limited CPU resources. In contrast, signature-based protocols require high CPU capacity to achieve comparable performance. We have open-sourced our Rust implementation of Sailfish++ to facilitate reproducible results.

Ali Farahbakhsh, Giuliano Losa, Youer Pu et al.

Permissionless blockchains achieve consensus while allowing unknown nodes to join and leave the system at any time. They typically come in two flavors: proof of work (PoW) and proof of stake (PoS), and both are vulnerable to attacks. PoS protocols suffer from long-range attacks, wherein attackers alter execution history at little cost, and PoW protocols are vulnerable to attackers with enough computational power to subvert execution history. PoS protocols respond by relying on external mechanisms like social consensus; PoW protocols either fall back to probabilistic guarantees, or are slow. We present Sieve-MMR, the first fully-permissionless protocol with deterministic security and constant expected latency that does not rely on external mechanisms. We obtain Sieve-MMR by porting a PoS protocol (MMR) to the PoW setting. From MMR we inherit constant expected latency and deterministic security, and proof-of-work gives us resilience against long-range attacks. The main challenge to porting MMR to the PoW setting is what we call time-travel attacks, where attackers use PoWs generated in the distant past to increase their perceived PoW power in the present. We respond by proposing Sieve, a novel algorithm that implements a new broadcast primitive we dub time-travel-resilient broadcast (TTRB). Sieve relies on a black-box, deterministic PoW primitive to implement TTRB, which we use as the messaging layer for MMR.

Qianyu Yu, Giuliano Losa, Nibesh Shrestha et al.

To maximize performance, many modern blockchain systems rely on eventually-synchronous, Byzantine fault-tolerant (BFT) consensus protocols. Two protocol designs have emerged in this space: protocols that minimize latency using a leader that drives both data dissemination and consensus, and protocols that maximize throughput using a separate, asynchronous data dissemination layer. Recent protocols such as Partially-Synchronous Bullshark and Sailfish combine elements of both approaches by using a DAG to enable parallel data dissemination and a leader that paces DAG formation. This improves latency while achieving state-of-the-art throughput. Yet the latency of leader-based protocols is still better under moderate loads, which are common in practice. We present Angelfish, a hybrid protocol that adapts smoothly across this design space, from leader-based to Sailfish-like DAG-based consensus. Angelfish lets a dynamically adjusted subset of parties use best-effort broadcast to issue lightweight votes instead of reliably broadcasting costlier DAG vertices. This reduces communication, helps lagging nodes catch up, and lowers latency in practice compared to prior DAG-based protocols. Our empirical evaluation shows that Angelfish attains state-of-the-art peak throughput while significantly lowering latency under moderate throughput, delivering the best of both worlds.

Qianyu Yu, Giuliano Losa, Xuechao Wang

This paper presents TetraBFT, a novel unauthenticated Byzantine fault tolerant protocol for solving consensus in partial synchrony, eliminating the need for public key cryptography and ensuring resilience against computationally unbounded adversaries. TetraBFT has several compelling features: it necessitates only constant local storage, has optimal communication complexity, satisfies optimistic responsiveness -- allowing the protocol to operate at actual network speeds under ideal conditions -- and can achieve consensus in just 5 message delays, which outperforms all known unauthenticated protocols achieving the other properties listed. We validate the correctness of TetraBFT through rigorous security analysis and formal verification. Furthermore, we extend TetraBFT into a multi-shot, chained consensus protocol, making a pioneering effort in applying pipelining techniques to unauthenticated protocols. This positions TetraBFT as a practical and deployable solution for blockchain systems aiming for high efficiency.

Vivien Bammert, Annalisa Cimatti, Orestis Alpos et al.

Erasure codes are a critical component in reliable storage systems today, and many blockchain systems use consensus protocols that involve erasure codes to reduce their communication cost. Existing erasure codes rely on a threshold failure assumption, but recent blockchain systems have departed from this simple model and use generalized failure assumptions. This paper introduces monotone erasure codes that respect arbitrary trust assumptions on a set of nodes. The paper first describes a method for constructing a monotone erasure code from any access structure given by a monotone Boolean formula. Next, the relevant notion of a linear monotone erasure code is introduced, which works on vectors over a finite field and where the encoding is a linear operation. We then focus on constructing linear monotone erasure codes: We give an efficient algorithm to construct linear monotone erasure codes for any access structure, and we show how to efficiently construct linear monotone erasure codes for the special case of partitioned access structures with minimal storage overhead. Last but not least, this work also shows how to use monotone erasure codes to obtain a communication-efficient, generalized version of the well-known asynchronous verifiable information dispersal (AVID) primitive, which is a key building block for developing efficient reliable broadcast and consensus protocols.