Project

Back to overview

Advanced Consensus Protocols

English title Advanced Consensus Protocols
Applicant Cachin Christian
Number 188443
Funding scheme Project funding (Div. I-III)
Research institution Institut für Informatik Universität Bern
Institution of higher education University of Berne - BE
Main discipline Information Technology
Start/End 01.01.2020 - 31.12.2023
Approved amount 724'027.00
Show all

Keywords (6)

Blockchain systems; Consensus; Cryptographic protocols; Distributed protocols; Byzantine agreement; Trust

Lay Summary (German)

Lead
Verteilte Computersysteme übernehmen heute viele Aufgaben, für welche zuverlässiges und sicheres Funktionieren zwingend ist. Dafür tolerieren sie Fehler oder auch Insider-Attacken autonom, unabhängig von zentralen Koordinatoren. Zur Synchronisation der Knoten in einem solchen System sind sichere verteilte Protokolle nötig, welche "Consensus" erreichen. Dies bedeutet, dass alle Teilnehmer dieselbe Sicht eines globalen Zustands haben. Obwohl Consensus-Protokolle schon länger erforscht wurden und auch praktisch im Einsatz sind, wurde das Interesse daran in den letzten Jahren neu erweckt, da sie ebenfalls die Grundlage von Blockchains und Kryptowährungen bilden.
Lay summary
Die Entwicklung von Blockchains hat dazu geführt, dass viele heuristische Consensus-Protokolle vorgeschlagen und neue Anforderungen aus der Praxis gestellt wurden. Consensus-Protokolle definieren algorithmisch und mittels kryptographischer Methoden, wie sich die Macht in einer Blockchain verteilt und welche Teilnehmer wie viel Einfluss haben. Manche neuartigen Protokolle stehen heute hinter Kryptowährungen, welche insgesamt Milliarden wert sind, ohne dass deren Sicherheit jemals analysiert oder formal bewiesen wurde.

Ziel dieses Projekts ist ein tieferes Verständnis von Consensus-Protokollen, welche sich an neuen Anwendungen orientieren, wie sie unter anderem bei Blockchains aufkamen. Insbesondere werden Protokolle mit nicht-symmetrischen Vertrauensmodellen untersucht, in denen die Teilnehmer subjektiv und unabhängig voneinander Annahmen über mögliche Fehler machen. Dazu werden auch nichtlineare Consensus-Protokolle entwickelt und analysiert, in denen ein azyklischer Graph mittels kryptographischer Hashfunktionen gebildet wird.

Die Resultate über sichere Consensus-Protokolle sind unmittelbar für die Praxis in verteilten Systemen von grossem Interesse, wie viele Startups in der Blockchain-Technologie zeigen. Die Schweiz nimmt in Blockchain und Fintech weltweit eine führende Rolle ein, und die Industrie profitiert deshalb direkt von vertieften Analysen der technischen Grundlagen. Das Projekt trägt andererseits auch zur gesellschaftlichen und rechtlichen Diskussion des Phänomens der Kryptowährungen bei, weil ein breites Verständnis der Entscheidungsmechanismen in diesem Gebiet bisher fehlt.
 
Direct link to Lay Summary Last update: 04.12.2019

Responsible applicant and co-applicants

Employees

Abstract

Protocols for reaching agreement among the nodes in a distributed network have received renewed interest in recent years due to their relevance for blockchain systems. In principle, every transaction executed on a blockchain requires a consensus decision from the participating nodes. Platforms like Bitcoin, Ethereum, Ripple, and many others have relaxed key assumptions made in earlier models and operate agreement protocols over the Internet today.Although research on distributed consensus has been a central and well-investigated problem in distributed computing, the resurging interest from practice has brought up new questions. At the same time, many blockchain consensus algorithms operating today lack formal analysis. This project addresses *advanced consensus protocols* on a fundamental level and aims at extending the understanding of protocols for distributing trust.In particular, the project will devise consensus protocols with *asymmetric quorums*, which allow the expression of flexible and subjective trust. Every participating node should freely choose which other nodes it trusts, unlike current approaches. The goal is to develop a range of agreement protocols with asymmetric trust and to show how existing Byzantine fault-tolerant (BFT) consensus methods with symmetric trust can be generalized to subjective assumptions.A second algorithmic approach concerns *scalable non-linear consensus protocols*. They allow for parallel execution and promise a large increase in transaction throughput. Instead of a hash chain of blocks, such protocols create a directed acyclic graph (DAG) through hash function applications (a hash DAG), which commits a partially ordered transaction history that may contain concurrent operations. This project aims at understanding the safety and liveness properties of hash-DAG consensus protocols formally and relating them to established notions in distributed computing.The third part of the project realizes a *toolkit for flexible consensus models*. Current implementations of BFT consensus protocols use threshold quorums as their trust model, where all N nodes are treated equally and some fraction F < N/3 of them may become faulty. However, general Byzantine quorum systems and asymmetric quorums as explored in this project show a way to implement consensus with flexible trust. This work develops practically useful instantiations of consensus with generalized and asymmetric trust models and demonstrates them in a toolkit for consensus.
-