Guest post by Zhuolun Xiang
[Read More]
Good-case Latency of Byzantine Broadcast: a Complete Categorization
Guest post by Zhuolun Xiang
[Read More]
What is a Merkle Tree?
In this post, we will demystify Merkle trees using three examples of problems they solve:
[Read More]
Raft does not Guarantee Liveness in the face of Network Faults
Last month, Cloudflare published a postmortem of a recent 6-hour outage caused by a partial switch failure which left etcd unavailable as it was unable to establish a stable leader. This outage has understandably led to discussion online about exactly what liveness guarantees are provided by the Raft consensus algorithm in the face of network failures.
[Read More]
A Simple and Succinct Zero Knowledge Proof
There is a popular belief that succinct proofs and zero-knowledge proofs are a type of moon math. In this post, our goal is to present a simple proof system that can provide an introduction and intuition to this space. Perhaps surprisingly, the only tool we will use is the Theorem that non-trivial degree-at-most-$d$ polynomials over a field have at most $d$ roots.
[Read More]
The Lock-Commit Paradigm: Multi-shot and Mixed Faults
In this follow to our Lock-Commit post, we show two important extensions. The first is how to extend from single-shot to multi-shot. Multi-shot is the bases of State Machine Replication. The second is how to tolerate mix faluts: both $f$ omission failures and $k$ crash failures given k+2f < n.
[Read More]
The Lock-Commit Paradigm
In this post, we explore one of the most celebrated and widely used techniques for reaching consensus: the Lock-Commit paradigm. This approach is a key technique of DLS88, Lamport’s Paxos, and many subsequent protocols. Protocols like Raft, PBFT, Tendermint, SBFT, Casper FFG, HotStuff, etc., are all based on this paradigm.
[Read More]
BFT Protocol Forensics
An important property satisfied by any Byzantine fault tolerant consensus protocol is agreement, which requires non-faulty replicas to not decide on conflicting values. Depending on the network model, typical consensus protocols tolerate only a fraction of Byzantine replicas. In particular, under partial synchrony or asynchrony, no consensus protocol with $n$ replicas can tolerate more than $n/3$ Byzantine faults. If the number of Byzantine replicas exceed this number, the protocols do...
[Read More]
Resolving the Availability-Finality Dilemma
Guest post by Joachim Neu, Ertem Nusret Tas, and David Tse
[Read More]
Living with Asynchrony: Bracha's Reliable Broadcast
In this series of posts, we explore what can be done in the Asynchronous model. This model seems challenging because the adversary can delay messages by any bounded time. By the end of this series, you will see that almost everything that can be done in synchrony can be obtained in asynchrony. The next posts in this series are about gather, round complexity, and finally our series on Asynchronous Agreement....
[Read More]
Broadcast from Agreement and Agreement from Broadcast
In this post, we highlight the connection between Broadcast and Agreement in the synchronous model.
Broadcast and Agreement: How can you implement one from the other?
[Read More]
Commit-Notify Paradigm for Synchronous Consensus with Omission Faults
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 (and see this post).
[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]