Decentralization is a core underpinning of blockchains. Is today’s blockchain really decentralized?
[Read More]
Consensus with One Mobile Crash in Synchrony or One Crash in Asynchrony Must Have Infinite Executions
In a consensus protocol, parties have an input (with at least two possible values, such as 0 or 1) and must output a decision value that satisfies the following properties:
[Read More]
In between Crash and Omission failures
In this post we explore adversary failure models that are in between crash and omission:
[Read More]
Early Stopping is same but different: two rounds are needed even in failure free executions
Many systems try to optimize executions that are failure free. If we absolutely knew that there will be no failures, parties could simply send each other messages with our inputs and reach consensus by outputting, say, the majority value. Thus completing the protocol after one round. What happens if there may be a crash failure? Say you have 100 servers and at most one can crash, can you devise a...
[Read More]
Gather with Binding and Verifiability
We extend the Gather protocol with two important properties: Binding and Verifiability. This post is based on and somewhat simplifies the information theoretic gather protocol in our recent ACS work with Gilad Asharov and Arpita Patra.
[Read More]
Simpler Security proof for Nakamoto Consensus
Four years ago (time flies!), I made a post on a simple security proof for Nakamoto consensus. While the proof intuition, as outlined in that post, is still reasonably simple, the actual proof has become quite delicate and crafty over the years. What happened was that some colleagues – Chen Feng at UBC and Dongning Guo at Northwestern – identified very subtle flaws in the proof, and clever mathematical maneuvers...
[Read More]
Scaling Blockchains: the Power of Batching
A few years ago if you asked “Can blockchains scale?” most people would give three reasons why, fundamentally, the answer is “No!”
[Read More]
The Fast Fourier Transform over finite fields
The Fast Fourier Transform (FFT) developed by Cooley and Tukey in 1965 has its origins in the work of Gauss. The FFT, its variants and extensions to finite fields, are a fundamental algorithmic tool and a beautiful example of interplay between algebra and combinatorics. There are many great resources on FFT, see ingopedia’s curated list.
[Read More]
Asynchronous Agreement on a Core Set
A challenging step in many asynchronous protocols is agreeing on a set of parties that completed some task. For example, an asynchronous protocol might start off with parties reliably broadcasting a value. Due to asynchrony and having $\leq f$ corruptions, honest parties can only wait for $n-f$ parties to complete the task. Parties may need to agree on a core set of $n-f$ such broadcasts and use them in the...
[Read More]
Can we Obtain Privacy in a Private Proof-of-Stake Blockchain? Part-II
This is Part-II of a two-part post on privacy in private proof-of-stake blockchains. In Part-I, we explored attacks on existing private PoS approaches. In this post, we will discuss some ways to obtain privacy (at the expense of safety and/or liveness).
[Read More]
Can we Obtain Privacy in a Private Proof-of-Stake Blockchain? Part-I
In this two-part post, we focus on the challenges and subtleties involved in obtaining privacy in private proof-of-stake (PoS) blockchains. For instance, designs that attempt to obtain privacy for transaction details while still relying on PoS, such as Ouroboros Crypsinous. The first part explains attacks on existing approaches, and the second part focuses on potential workarounds using differential privacy. These posts explain the intuitive ideas behind the works of Madathil...
[Read More]
The CAP Theorem and why State Machine Replication for Two Servers and One Crash Failure is Impossible in Partial Synchrony
In 1999, Fox and Brewer published a paper on the CAP principle, where they wrote:
[Read More]
$3f+1$ is needed in Partial Synchrony even against a Rollback adversary
In this post we show that trusted execution environments (TEEs) don’t help against the classic $3f$ lower bound for partial synchrony, when these TEEs have no persistent storage, against a rollback adversary.
[Read More]
Blockchains + TEEs Day 2 Summary
This is the second of the two part post on the workshop on Blockchains + TEEs that concluded last week. Here are the key ideas from Day 2. You can find the post summarizing Day 1 here.
[Read More]
Blockchains + TEEs Day 1 Summary
Our workshop on Blockchains + TEEs concluded last week. We had a fantastic series of talks and discussions on both days of the workshop. In this two part post, we highlight some key takeaways from each of the days.
[Read More]
What is the difference between PBFT, Tendermint, HotStuff, and HotStuff-2?
We recently published our work HotStuff-2 on eprint, introducing a two-phase HotStuff variant which simultaneously achieves $O(n^2)$ worst-case communication, optimistically linear communication, a two-phase commit regime within a view, and optimistic responsiveness in partially-synchronous BFT.
[Read More]
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 that works against a weak adaptive adversary.
[Read More]
Randomization and Consensus - synchronous binary agreement for crash failures with a perfect common coin
What is the simplest setting where randomization can help solve consensus? Assume lock-step (synchrony) with $f<n$ crash failures. We know that in the worst case reaching agreement takes at least $f+1$ rounds. This lower bound holds even if the protocol is randomized so the natural question is:
[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]