Synchronous Byzantine Broadcast algorithms for a dishonest majority

Deterministic Byzantine Broadcast requires f+1 rounds for any f malicious processes, in the synchronous, authenticated setting. In the non-deterministic case, Katz and Koo [2] showed a lower-bound of [omega](2n=(n-f)) rounds, but it remains an open question whether the bound is tight, specically when f >/= n/2 (a dishonest majority). This thesis explores ways to improve the eciency of Byzantine Broadcast algorithms for a dishonest majority. In particular, we present an expected 10 round protocol for f = n/2, which works by constructing a hierarchy of quorums, to gather as many signatures as possible, before commitment. Finally, we offer brief commentary on how similar techniques could extend to f > n/2.

Name thesis:degree_name

Master

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2019

Author dc:creator

• Chan, Benjamin Yao.

Advisor dc:contributor.advisor

• Srini Devadas.

• Electrical Engineering and Computer Science.

Statement dc:rights

• MIT theses are protected by copyright. They may be viewed, downloaded, or printed from this source but further reproduction or distribution in any format is prohibited without written permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

https://hdl.handle.net/1721.1/121665

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/121665