Security proof for Nakamoto Consensus

Bitcoin’s underlying consensus protocol, now known as Nakamoto consensus, is an extremely simple and elegant solution to the Byzantine consensus problem. One may expect this simple protocol to come with a simple security proof. But that turns out not to be the case. The Bitcoin white paper did not provide a proof. Several academic papers (e.g. Garay, Kiayias, Leonardos, and Pass, Seeman, shelat and Kiffer, Rajaraman, shelat) later presented rigorous... [Read More]

Authenticated Synchronous BFT

Different modeling assumptions under which we construct BFT protocols often make it hard to compare two protocols and understand their relative contributions. In this post we discuss synchronous protocols in the authenticated model (assuming a PKI). [Read More]

Primary-Backup State Machine Replication for Crash Failures

We continue our series of posts on State Machine Replication (SMR). In this post we discuss the most simple form of SMR: Primary-Backup for crash failures. We will assume synchronous communication. For simplicity, we will consider the case with two replicas, out of which one can crash. Recall that when a party crashes, it irrevocably terminates. [Read More]
Tags: dist101 SMR

Flavours of State Machine Replication

State Machine Replication is a fundamental approach in distributed computing for building fault tolerant systems. This post is a followup to our basic post on Fault Tolerant State Machine Replication. [Read More]
Tags: dist101

Flavours of Broadcast

What is the difference between broadcast, crusader broadcast, gradecast, weak broadcast, detectable broadcast, and broadcast with abort? This post is a follow up to our basic post on: What is Broadcast? [Read More]

Consensus for State Machine Replication

We introduced definitions for consensus, Byzantine Broadcast (BB) and Byzantine Agreement (BA), in an earlier post. In this post, we will discuss how consensus protocols are used in State Machine Replication (SMR). We will compare and contrast this setting to that of traditional BB and BA. [Read More]
Tags: dist101

Flavours of Partial Synchrony

This is a follow up post to the post on Synchrony, Asynchrony and Partial synchrony. The partial synchrony model of DLS88 comes in two flavours: GST and Unknown Latency. In this post we discuss: [Read More]
Tags: dist101

Dont Trust. Verify. and Checkpoint?

Imagine that that Aliens land on earth with a new superfast SHA256 machine. Imagine this machine always gives them more than 51% of the current world Bitcoin hash power (but not enough hash power to completely break SHA256). Suppose they decide to build a chain from the Bitcoin Genesis block that is longer than any other chain on earth and put only empty blocks on it. Could they erase all... [Read More]