We continue our series of posts on State Machine Replication (SMR). In this post, we move from consensus under crash failures to consensus under omission failures. We still keep the synchrony assumption.
[Read More]

## What is a Cryptographic Hash Function?

If you ever tried to understand Bitcoin, you’ve probably banged your head against the wall trying to understand what is a cryptographic hash function?
The goal of this post is to:
[Read More]

## Private Set Intersection #2

In the first post on Private Set Intersection, I presented the problem of Private Set Intersection, its applications and the simple protocol of [KMRS14], that allows Alice and Bob to learn the intersection of their sets with the aid of an untrusted third party Steve who is assumed to not collude with Alice or with Bob.
[Read More]

## Polynomial Secret Sharing and the Lagrange Basis

In this post, we highlight an amazing result: Shamir’s secret sharing scheme. This is one of the most powerful uses of polynomials over a finite field in distributed computing. Intuitively, this scheme allows a $Dealer$ to commit to a secret $s$ by splitting it into shares distributed to $n$ parties. The secret is hidden and requires a threshold of $f+1$ parties in order to be reconstructed, where $f < n$....
[Read More]

## The Marvels of Polynomials over a Field

In this series of posts, we explore the mathematical foundations of polynomials over a field. These objects are at the heart of several results in computer science: secret sharing, Multi Party Computation, Complexity, and Zero Knowledge protocols.
[Read More]

## Asynchronous Fault Tolerant Computation with Optimal Resilience

A basic question of distributed computing:
Is there a fundamental limit to fault tolerant computation in the Asynchronous model?
[Read More]

## Encrypted Blockchain Databases (Part II)

In this second part of the series on Encrypted Blockchain Databases, we are going to describe three schemes to store dynamic encrypted multi-maps (EMMs) on blockchains, each of which achieves different tradeoffs between query, add and delete efficiency.
[Read More]

## Encrypted Blockchain Databases (Part I)

## The First Blockchain or How to Time-Stamp a Digital Document

This post is about the work of Stuart Haber and W. Scott Stornetta from 1991 on How to Time-Stamp a Digital Document and their followup paper Improving the Efficiency and Reliability of Digital Time-Stamping. In many ways, this work introduced the idea of a chain of hashes to create a total order of commitments to a dynamically growing set of documents. It’s no wonder these two papers are cited by...
[Read More]

## On the Optimality of Optimistic Responsiveness

Synchronous consensus protocols tolerating Byzantine failures depend on the maximum network delay $\Delta$ for their safety and progress. The delay, $\Delta$ is usually much larger than actual network delay $\delta$ since $\Delta$ is a pessimistic value. While synchronous protocols tolerating more than one-third will have executions with at least a $\Delta$ latency, recent synchronous protocols such as Sync HotStuff have been trying to reduce the reliance on $\Delta$ as much...
[Read More]

## Streamlet: A Simple Textbook Blockchain Protocol

Guest post by Benjamin Chan and Elaine Shi
[Read More]

## Bilinear Accumulators for Cryptocurrency Enthusiasts

Accumulator schemes are an alternative to Merkle Hash Trees (MHTs) for committing to sets of elements.
Their main advantages are:
[Read More]

## Private Set Intersection

Private Set Intersection (PSI) is a problem within the broader field of secure computation.
[Read More]

## Range Proofs from Polynomial Commitments, Re-explained

This is a re-exposition of a post here by Dan Boneh, Ben Fisch, Ariel Gabizon, and Zac Williamson, with a few more details on why the polynomial relations hold.
[Read More]

## Blockchain Selfish Mining

Proof of Work (PoW) Blockchains implement a form of State Machine Replication (SMR). Unlike classical SMR protocols, they are open, i.e., anyone can join the system, and the system incentivizes participants, called miners, to follow the protocol. Therefore, unlike classical SMR protocols, reasoning about blockchain security relies not only on bounding the number of malicious participants. One should crucially ask whether miners are indeed incentivized to follow the prescribed protocol....
[Read More]

## Dolev-Strong Authenticated Broadcast

This post is about the classic result from 1983 on authenticated broadcast against a Byzantine adversary:
[Read More]

## The FLP Impossibility, Asynchronous Consensus Lower Bound via Uncommitted Configurations

In this third post, we conclude with the celebrated Fischer, Lynch, and Paterson impossibility result from 1985. It is the fundamental lower bound for consensus in the asynchronous model.
[Read More]

## Synchronous Consensus Lower Bound via Uncommitted Configurations

In this second post, we show the fundamental lower bound on the number of rounds for consensus protocols in the synchronous model.
[Read More]

## Consensus Lower Bounds via Uncommitted Configurations

In this series of three posts, we discuss two of the most important consensus lower bounds: Lamport, Fischer [1982]: any protocol solving consensus in the synchronous model that is resilient to $t$ crash failures must have an execution with at least $t+1$ rounds. Fischer, Lynch, and Patterson [1983, 1985]: any protocol solving consensus in the asynchronous model that is resilient to even one crash failure must have an infinite execution....
[Read More]

## Data, Consensus, Execution: Three Scalability Bottlenecks for State Machine Replication

If anyone asks you: how can I scale my State Machine Replication (Blockchain) system?
[Read More]