You are here

Byzantine Fault Tolerant Set Consensus with Efficient Set Reconciliation

TitleByzantine Fault Tolerant Set Consensus with Efficient Set Reconciliation
Publication TypeThesis
Year of Publication2015
AuthorsDold, F
AdvisorGrothoff, C
Academic DepartmentComputer Science
Number of Pages69
Date Published12/2015
UniversityTechnische Universitaet Muenchen
Thesis TypeMaster’s
Keywordsbyzantine consensus, GNUnet, secure multiparty computation, set reconciliation, voting

Byzantine consensus is a fundamental and well-studied problem in the area of distributed system. It requires a group of peers to reach agreement on some value, even if a fraction of the peers is controlled by an adversary. This thesis proposes set union consensus, an efficient generalization of Byzantine consensus from single elements to sets. This is practically motivated by Secure Multiparty Computation protocols such as electronic voting, where a large set of elements must be collected and agreed upon. Existing practical implementations of Byzantine consensus are typically based on state machine replication and not well-suited for agreement on sets, since they must process individual agreements on all set elements in sequence. We describe and evaluate our implementation of set union consensus in GNUnet, which is based on a composition of Eppstein set reconciliation protocol with the simple gradecast consensus prococol described by Ben-Or.

PDF icon ma_dold_consensus_21dec2015.pdf902.42 KB