CAN'T WE JUST AGREE?CAN'T WE JUST AGREE?       ONDŘEJ CHALOUPKA, VOJTĚCH JURÁNEKONDŘEJ CHALOUPKA, VOJTĚCH JURÁNEK FI MUNI 14. 11. 2019 WHO WE AREWHO WE ARE WORKING AS ENGINEERS AT RED HAT DISTRIBUTED SYSTEMS ENTHUSIASTS MEET US AT BRNO DISTRIBUTED SYSTEMS MEET-UP  https://www.meetup.com/Brno-Distributed-Systems-Meetup-Group WHAT IS THIS TALK ABOUTWHAT IS THIS TALK ABOUT WHY CONSENSUS ALGORITHM IS AN ESSENTIAL PART  IN DISTRIBUTED LEDGER SYSTEMS A BRIEF OVERVIEW OF CONSENSUS ALGORITHMS  IN DISTRIBUTED LEDGER SYSTEMS HOW THE CHOICE OF CONSENSUS ALGORITHM IMPACTS CAPABILITIES OF DISTRIBUTED SYSTEM AGENDAAGENDA MOTIVATION FOR CONSENSUS IN DISTRIBUTED LEDGER SYSTEM NON-BYZANTINE FAULT TOLERANT CONSENSUS FOR BLOCKCHAIN BYZANTINE FAULT TOLERANT CONSENSUS FOR BLOCKCHAIN BITCOIN CONSENSUS CONSENSUS ALGORITHMS ON TOP OF DIRECTED ACYCLIC GRAPHS (DAG) TRANSFER OF THE MONEYTRANSFER OF THE MONEY Beware: distributed ledgers are not limited only to cryptocurrencies, there are lots of other applications! CENTRAL AUTHORITYCENTRAL AUTHORITY DOUBLE SPEND PROBLEMDOUBLE SPEND PROBLEM In distributed systems, we need agreement between participants, which transaction is valid. CONSENSUSCONSENSUS Agreement between nodes on something, e.g. some value Another example: whether to commit a (distributed ) transaction to a database Hard, network is unreliable delays or failures in communication Consensus has to have two properties: safety and liveness CONSENSUSCONSENSUS https://twitter.com/el33th4xor/status/1006931658338177024 NON-BYZANTINENON-BYZANTINE FAULT TOLERANT CONSENSUSFAULT TOLERANT CONSENSUS can withstand failures but not a cheating participant trust in all involved parties protocols like Paxos (Google Spanner), Raft (etcd), Zab (Zookeeper) consensus is affirmed when majority of nodes agrees withstand crashes or connection issues RAFT ALGORITHMRAFT ALGORITHM https://raft.github.io/#raftscope PRIVATE BLOCKCHAINSPRIVATE BLOCKCHAINS all nodes are under control of a single organization number of participant is small, they know about each other and trust each other Raft in Hyperledger (Sawtooth, Fabric) Permissioned : nodes needs some permission to join the network Permissionless : nodes can join the network without any permission (public blockchains) NON-BYZANTINE CONSENS.NON-BYZANTINE CONSENS. SUMMARYSUMMARY usually used in distributed database systems trust in all involved parties used in private permissioned blockchains BYZANTINE FAILUREBYZANTINE FAILURE besides delays and failures in communication over network, the situation can be even worse - there can be malicious participants! a byzantine failure is any fault presenting different symptoms to different observers. e.g. attempt to double spend money.   PBFT, Tendermint, Stellar ... Agreement can be imaged like a three-phase commit (propose a value, pre-prepare commit, prepare, commit).. BFT ALGORITHMSBFT ALGORITHMS BYZANTINE FAULT TOLERANTBYZANTINE FAULT TOLERANT http://pmg.csail.mit.edu/papers/osdi99.pdf Still to some extend centralized. Usually to some extend permissioned or have to be combined e.g. with PoS (Tendermint). FEDERATED DISTRIBUTEDFEDERATED DISTRIBUTED LEDGERSLEDGERS   https://mc.ai/whats-new-in-deep-learning-research-understanding-federated-learning/ BYZANTINE CONSENSUSBYZANTINE CONSENSUS SUMMARYSUMMARY usually slow a lot of messages exchanged parties don't (fully) trust each other usually used in semi-public and public blockchains PUBLIC BLOCKCHAINSPUBLIC BLOCKCHAINS any party may connect nobody trusts nobody some new challenges evolve SIBYLS ATTACKSIBYLS ATTACK Forging the identity to subverted the result PROOF-OF-WORKPROOF-OF-WORK A valid block starts with prefix 0x00 BLOCKCHAIN FORKBLOCKCHAIN FORK BLOCKCHAIN FORKBLOCKCHAIN FORK NAKAMOTO CONSENSUSNAKAMOTO CONSENSUS Bitcoin is (almost) Byzantine fault tolerant (BFT) and also resistant to Sybil attack Proof-of-Work (PoW) is mechanism how to prevents Sybil attacks The truth (agreement) is determined by the longest chain (created by Proof-of-Work)  usually called Nakamoto consensus algorithm Probabilistic: probability of consensus is less than 1 Proof-of-Work finding a new block is stable to 10 minutes Bitcoin network is essentially synchronous BITCOIN CONSENSUSBITCOIN CONSENSUS SUMMARYSUMMARY proof-of-work solves sibyls attack + leader election consensus is nakamoto consensus which adds "a static rule" on top of PoW and declares that the right chain is the longest chain WHAT ABOUT POSWHAT ABOUT POS PROOF-OF-STAKEPROOF-OF-STAKE Proof-of-Stake (PoS) is per se not a consensus algorithm Proof-of-Stake solves Sybil attack Two major types Chain-based PBFT-style Consensus algorithm is completed with additional flavor as a separate rule of the longest chain wins (chain-based) as a consensus running among all validator to determine the final valid block (PBFT)   Blockchain DAG Hashgraph, Avalanche, Tangle… Usually are not resistant to Sibyl attack (needs PoS or something else) https://en.wikipedia.org/wiki/Blockchain#/media/File:Blockchain.svg https://ministryofblockchain.io/is-directed-acyclic-graph-dag-blockchains-new-competitor/ CONSENSUS ALGORITHMSCONSENSUS ALGORITHMS ON TOP OF DIRECTED ACYCLIC GRAPHSON TOP OF DIRECTED ACYCLIC GRAPHS Gossip about gossip Virtual voting https://swirlds.com/downloads/SWIRLDS-TR-2016-01.pdf HASHGRAPHHASHGRAPH Gossip protocol Metastability https://www.youtube.com/watch?v=AXrrqtFlGow AVALANCHEAVALANCHE DAG BASED CONSENSUSDAG BASED CONSENSUS SUMMARYSUMMARY different data structure for storing transaction data not resistant to sibyls attack - PoS is usually involved CHALOUPKA-JURÁNEK TAXONOMYCHALOUPKA-JURÁNEK TAXONOMY TAKE-OFFSTAKE-OFFS Consensus protocol is a crucial part of any distributed ledger. Choice of consensus protocol influences heavily many characteristic of distributed ledger (including performance and security). There are several types of distributed ledgers, several families of consensus algorithms and not every consensus algorithm is suitable for every distributed ledger. QUESTIONSQUESTIONS S. Nakamoto, Bitcoin: A Peer-to-Peer Electronic Cash System D. Ongaro, J. Ousterhout, In Search of an Understandable Consensus Algorithm M. Castro, B Liskov, Practical Byzantine Fault Tolerance D. Mazieres, The Stellar Consensus Protocol The latest gossip on BFT consensus - Tendermint consensus algorithm L. Baird, The Swirlds Hashgraph Consensus Algorithm Team Rocket, Snowflake to Avalanche A Survey on Consensus Mechanisms and Mining Strategy Management  in Blockchain Networks LINKSLINKS Thank you for your attention! BACKUP SLIDES BITCOIN 51% ATTACKBITCOIN 51% ATTACK POS: NOTHING AT STAKEPOS: NOTHING AT STAKE Text https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQs   There are many: Proof of Capacity Proof of Elapsed Time (PoET) Proof of Authority Proof of Activity Proof of Burn Proof of Weight …   Beware: Proof-of-X doesn’t mean it’s similar to PoW, actually in many cases it’s quite different (e.g. centralized). PROOF-OF-XPROOF-OF-X TAXONOMY TABLETAXONOMY TABLE Proof-of- Work Bitcoin Public Permissionless Byzantine tolerant Probabilistic   Proof-of- Stake Ethereum 2.0 Public Permissionless Byzantine tolerant Finite   Delegated PoS Stellar Permissioned public Byzantine tolerant Finite   Raft Hyperledger Permissioned private non-Byzantine tolerant Finite   Tendermint Cosmos Permissionless public Byzantine tolerant Finite   Swirlds Hedera Hashgraph Permissionless public Byzantine tolerant Finite   Avalanche Ava Permissionless public Byzantine tolerant Probabilistic     BLOCKCHAIN NETWORK IMPL.BLOCKCHAIN NETWORK IMPL.