Efficient and egalitarian consensus

Consensus is a classic problem in distributed computing. Research on consensus has traditionally focused on the permissioned setting where participants are fixed and know each other beforehand. Recently, the digital currency Bitcoin has popularized a new line of research on consensus in a permissionless environment, where participants may join or leave at any time and need not know how many other participants exist or who they are. Bitcoin's solution, now known as the Nakamoto consensus, is to build a proof-of-work chain and treat the longest proof-of-work chain as consensus decisions. However, this elegant solution does have limitations. First, it has long latency: under current parameters, it can take hours for a Bitcoin transaction to go through. Second, its use of hash-based proof-of-work has raised concerns about fairness and energy consumption. This thesis presents distributed algorithms and cryptographic primitives to address these limitations. I will first describe Solida, a permissionless consensus protocol with low latency. It has been observed that traditional Byzantine consensus protocols have much lower latency than Nakamoto consensus. Following this observation, Solida adapts traditional Byzantine consensus protocols from the permissioned setting to the permissionless setting by combining them with proof-of-work. I also design improved protocols for permissioned synchronous Byzantine consensus. I then turn to potential replacements for hash-based proof-of-work. I construct a proof-of-space protocol with tight security bounds as an energy-efficient alternative. Finally, I revisit the concept of memory-hard functions, the standard approach to improve fairness in proof-of-work. I argue that the memory-hardness approach overlooks energy efficiency fairness and suggest bandwidth-hard functions as egalitarian alternatives.

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

2018

Author dc:creator

• Ren, Ling, Ph. D. Massachusetts Institute of Technology

Advisor dc:contributor.advisor

• Srinivas 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

http://hdl.handle.net/1721.1/120372

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/120372