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]

## He-HTLC - Revisiting Incentives in HTLC

Hashed Time-locked Contracts (HTLC) find many useful applications in the L2 Layer such as the lightning network and atomic swaps. In this post, we will focus on discussing protocols for implementing HTLC when taking into consideration incentives for parties in the system. We will discuss a line of work — WHF’19, MAD-HTLC, He-HTLC — towards developing an HTLC protocol secure in the presence of rational parties. [Read More]

## DAG Meets BFT - The Next Generation of BFT Consensus

This post explains in simple words a recent development in the theory and practice of directed acyclic graph-based (DAG-based) Byzantine Fault Tolerance (BFT) consensus, published in three prestigious peer-reviewed conferences, and currently being implemented by several Blockchain companies, e.g., Aptos, Celo, Mysten Labs, and Somelier. [Read More]
Tags: consensus

## Safe Permissionless Consensus

Nakamoto’s consensus protocol works in a permissionless model, where nodes can join and leave without notice. However, it guarantees agreement only probabilistically. Is this weaker guarantee a necessary concession to the severe demands of supporting a permissionless model? [Read More]

In previous posts we showed that the classic Dolev-Strong broadcast protocol takes $O(n^3)$ words and $t+1$ rounds and that Dolev Reischuk show that $\Omega(n^2)$ is needed and it is also known that $t+1$ rounds are needed. So while the number of rounds is optimal, to this day it remains an open question of obtaining $O(n^2)$ broadcast against a strongly adaptive adversary (see post for recent progress). [Read More]