In 1999, Fox and Brewer published a paper on the CAP principle, where they wrote:
[Read More]
$3f+1$ is needed in Partial Synchrony even against a Rollback adversary
We covered the classic DLS88 split brain impossibility result against a Byzantine adversary in a previous post:
[Read More]
Blockchains + TEEs Day 2 Summary
This is the second of the two part post on the workshop on Blockchains + TEEs that concluded last week. Here are the key ideas from Day 2. You can find the post summarizing Day 1 here.
[Read More]
Blockchains + TEEs Day 1 Summary
Our workshop on Blockchains + TEEs concluded last week. We had a fantastic series of talks and discussions on both days of the workshop. In this two part post, we highlight some key takeaways from each of the days.
[Read More]
What is the difference between PBFT, Tendermint, HotStuff, and HotStuff-2?
We recently published our work HotStuff-2 on eprint, introducing a two-phase HotStuff variant which simultaneously achieves $O(n^2)$ worst-case communication, optimistically linear communication, a two-phase commit regime within a view, and optimistic responsiveness in partially-synchronous BFT.
[Read More]
Randomization and Consensus - synchronous binary agreement for minority omission failures
Continuing the series on simple ways where randomization can help solve consensus. The model is lock-step (synchrony) with $f<n/2$ omission failures. We know that in the worst case reaching agreement takes at least $f+1$ rounds. Can randomization help reduce the expected number of rounds? In the post, we show a simple randomized consensus algorithm including a simple weak coin protocol that works against a weak adaptive adversary.
[Read More]
Randomization and Consensus - synchronous binary agreement for crash failures with a perfect common coin
What is the simplest setting where randomization can help solve consensus? Assume lock-step (synchrony) with $f<n$ crash failures. We know that in the worst case reaching agreement takes at least $f+1$ rounds. This lower bound holds even if the protocol is randomized so the natural question is:
[Read More]
Can we Obtain Player Replaceability and Forensic Support Simultaneously?
Forensic support is an important property of BFT protocols that addresses the other side of security: what happens when the number of malicious parties exceeds the allowable threshold? In a previous post, we systematically studied different BFT protocols to assess their ability to detect and prove malicious behavior when safety is violated. We learned that protocols such as PBFT and HotStuff with ${\sf poly}(n)$ communication have strong forensic support, meaning...
[Read More]
What are Blockchains Useful for, Really?
Blockchains, or the decentralized ledger, are touted as the next big disruptive technology, as big as the Internet was in the 90s. What are these blockchains useful for, really? While there are relevant use cases, many examples people use that are either far too academic to be useful or are scenarios where blockchains are not the right solution in the first place. Thus, in this post, I am trying to...
[Read More]
Pairing-based Anonymous Credentials and the Power of Re-randomization
David Chaum wrote in 1985:
Large-scale automated transaction systems are imminent. The architecture chosen for these systems may have a long-term impact on the centralization of our economic system, on some of our basic liberties, and even on our democracy. The initial choice of direction will gather economic and societal momentum, making reversal increasingly less likely.
[Read More]
Player Replaceability - Towards Adaptive Security and Sub-quadratic Communication Simultaneously (Part II)
This is part II of a two-part post on player-replaceability. Part I can be found here.
[Read More]
Player Replaceability - Towards Adaptive Security and Sub-quadratic Communication Simultaneously (Part I)
This is part I of a two-part post on the concept of player-replaceability.
[Read More]
Responsiveness under omission failures
In this post, we discuss log replication responsiveness in the context of omission failures. We show how to transform the protocol in our previous post to a multi-shot version of Paxos for omission faults. The Byzantine failure case uses similar ideas and is covered in the next post of this series.
[Read More]
Set Replication - fault tolerance without total ordering
State machine replication is the gold standard for implementing any (public) ideal functionality. It totally orders all transactions and as a consequence solves (Byzantine) agreement. By Agreement in the worst case is quadratic and not constant time. In some cases this overhead is unnecessary because there is no need to totally order all transactions.
[Read More]
What is Responsiveness?
In asynchronous protocols, latency to commit is a function of the actual maximum network delay $\delta$. In synchronous protocols, message delay is bounded by $\Delta$, and for $n/3 \leq f < n/2$, the $\Delta$ bound is used to obtain both safety and liveness. In partial synchrony, message delay is bounded by $\Delta$ after GST, and the $\Delta$ bound is used to obtain liveness.
[Read More]
What about Validity?
Perhaps the archetypical trilemma is consensus - it requires three properties: agreement, liveness, and validity. Getting any two is easy, but all three together is what makes consensus such a facinating problem that continues to create new challenges even after 40 years of research.
[Read More]
Two Round HotStuff
In the first part of this post we describe a single-shot variation of Two Round HotStuff (see HotStuff v1 paper, march 2018 and this march 2018 post) using Locked Broadcast that follows a similar path as our previous posts on Paxos and Linear PBFT.
[Read More]
Linear PBFT: a gentle introduction to Practical Byzantine Fault Tolerance
PBFT is a foundational multi-year project led by Barbara Liskov and her students, obtaining major advances in both the theory and practice of Byzantine Fault Tolerance. The PBFT conference version, journal version, Castro’s thesis, Liskov’s talk, and follow-up work on BASE are all required reading for anyone who wants to deeply understand BFT systems.
[Read More]
From Single-Shot Agreement to State Machine Replication
In this post we explore the path from Single-Shot Agreement, via Write-Once Registers, to Log Replication, and finally to State Machine Replication. We begin by defining all four problems assuming minority omission failures and partial synchrony. This post continues our previous posts on Paxos from Recoverable Broadcast and on State Machine Replication.
[Read More]
On Paxos from Recoverable Broadcast
There are many ways to learn about the Paxos protocol (see Lampson, Cachin, Howard, Howard 2, Guerraoui, Kladov, Krzyzanowski, Lamport, Wikipedia and many more). The emphasis of this post is on a decomposition of Paxos for omission failures that will later help when we do a similar decomposition for Byzantine failures (for PBFT and HotStuff).
[Read More]