Decentralized Thoughts is a group blog on decentralization, by decentralized thinkers, for decentralized thoughts, of decentralized matters. Decentralized Thoughts is a group blog on decentralization, by decentralized thinkers, for decentralized thoughts, of decentralized matters.

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. [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]
Tags: blockchain

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]

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

While state machine replication is the gold standard for implementing any (public) ideal functionality, its power comes at the cost of needing to totally order all transactions and as a consequence solve (Byzantine) agreement. In some cases this overhead is unnecessary. [Read More]
Tags: dist101

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]
Tags: dist101

What about Validity?

Perhaps the architipical 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. In the second part, we describe a fully pipelined multi-shot State Machine Replication version of Two Round HotStuff that is similar to Casper FFG and Streamlet.... [Read More]
Tags: dist101

On PBFT from Locked Broadcast

PBFT is a foundational multi-year project lead 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]
Tags: dist101

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 so many ways to learn about the Paxos protocol (see Lampson, Cachin, Howard Howard 2, Guerraoui, Kladov, Krzyzanowski, Lamport, Wikipedia and many more), this post is one more way. The emphasis of this post is on a decomposition of Paxos for omission failures that will later help when we do a similar decomposition in the Byzantine failure case (for PBFT and HotStuff). [Read More]

Provable Broadcast

We explore a family of broadcast protocols in the authenticated setting in which a designated sender wants to create a delivery-certificate of its input value. After describing the base protocol we call Provable Broadcast ($PB$), we explore the surprising power of simply running $PB$ two times in a row, then three times, and finally four times in a row. [Read More]
Tags: dist101

Dining Cryptographers and the additivity of polynomial secret sharing

David Chaum’s dining cryptographer problem is a pioneering work on the foundations of privacy. It shows the amazing power of information-theoretic Secure Multi Party Computation. The original paper from 1988 is super accessible and fun to read. Many systems in the last 20 years for anonymity and privacy-preserving communication are based on the Dining Cryptographers problem. Herbivore, Dissent, Riposte, Blinder, and many others. [Read More]

The BGW Verifiable Secret Sharing Protocol

In this post, we present the classic Ben-or, Goldwasser, and Wigderson, 1988 (BGW) Verifiable Secret Sharing protocol (VSS) with the simplifications of Feldman, 1988. The analysis and notation in this post are based on the full proof of the BGW MPC protocol of Asharov and Lindell. This post is a continuation of our previous posts on secret sharing for passive and crash failures. [Read More]

Polynomial Secret Sharing with crash failures

We continue our series on polynomial secret sharing. In the previous post of this series we discussed secret sharing with a passive adversary. In this post we assume crash failures and in later posts we will extend to malicious failures. As before, we must assume parties have private channels: the adversary cannot see the content of messages sent between two non-faulty parties. [Read More]