Awesome Consensus Algorithms

Problems

• Byzantine generals problem, The real Byzantine Generals
• Fault tolerance

Limitations:

• A Simple Bivalency Proof that t-Resilient Consensus Requires t + 1 Rounds

Synchrony models

• Synchrony, Asynchrony and Partial synchrony

Algorithms

The Byzantine Generals Problem

• The Byzantine Generals Problem

Completely Asynchronous Agreement Protocols

• Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols

An Efficient Algorithm for Byzantine Agreement without Authentication

• An Efficient Algorithm for Byzantine Agreement without Authentication

The Part-Time Parliament

• The Part-Time Parliament

Raft

An Optimal Probabilistic Algorithm for Byzantine Agreement

• An Optimal Probabilistic Algorithm for Byzantine Agreement

PBFT

• PBFT
• Practical Byzantine Fault Tolerance and Proactive Recovery

Q/U protocol

• Fault-Scalable Byzantine Fault-Tolerant Services

Uniform consensus

• Uniform consensus is harder than consensus

Trusted Timely Computing Base

• The Design of a COTS Real-Time Distributed Security Kernel
• How to Tolerate Half Less One Byzantine Nodes in Practical Distributed Systems

On Expected Constant-Round Protocols for Byzantine Agreement

• On Expected Constant-Round Protocols for Byzantine Agreement

Efficient Synchronous Byzantine Consensus

• Efficient Synchronous Byzantine Consensus

Nakamoto Consensus

• Bitcoin: A Peer-to-Peer Electronic Cash System
• The Bitcoin Backbone Protocol: Analysis and Applications
• The Bitcoin Backbone Protocol with Chains of Variable Difficulty
• Analysis of Nakamoto Consensus
• But Why Does it Work? A Rational Protocol Design Treatment of Bitcoin
• Analysis of the Blockchain Protocol in Asynchronous Networks

Honey Badger BFT

• The Honey Badger of BFT Protocols

Byzantine Agreement, Made Trivial

• Byzantine Agreement, Made Trivial

BABE/GRANDPA

HotStuff and Libra

• HotStuff: BFT Consensus in the Lens of Blockchain
• State Machine Replication in the Libra Blockchain
• DiemBFT v4: State Machine Replication in the Diem Blockchain

Ouroboros family

• Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol
• Ouroboros-BFT: A Simple Byzantine Fault Tolerant Consensus Protocol
• Ouroboros Praos: An adaptively-secure, semi-synchronous proof-of-stake blockchain

Hashgraph

• The Swirlds hashgraph consensus algorithm: Fair, fast, byzantine tolerance
• Verifying the Hashgraph Consensus Algorithm

Avalanche

• Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies
• Scalable and Probabilistic Leaderless BFT Consensus through Metastability

DAGs

Distributed randomness

Classics

• Coin Flipping by Telephone
• An Optimally Fair Coin Toss

Commit reveal

• Randao
• Economically Viable Randomness

Shamir's Secret Sharing

Threshold cryptography

VRF:

• Wikipedia
• Micali, Rabin, Vadham (1999)
• A verifiable random function with short proofs and keys
• Verifiable Random Functions from Standard Assumptions
• Derandomization in Cryptography
• Verifiable Random Functions from Non-interactive Witness-Indistinguishable Proofs

VDF

• https://vdfresearch.org/

PoW

• http://hashcash.org/
• https://bitcoin.org/bitcoin.pdf
• (add diffreent hashes)

All possible selection approach

• PoW
• PoS
• DPoS
• Proof Of Space

Attacks

• Long range attacks: A Survey on Long-Range Attacks for Proof of Stake Protocols
• Selfish mining: Majority is not Enough: Bitcoin Mining is Vulnerable
• Why buy when you can rent? Bribery attacks on Bitcoin-style consensus
• On Stake and Consensus
• Distributed Consensus from Proof of Stake is Impossible