eCommons

 

Ordered Consensus with Equal Opportunity

Other Titles

Abstract

The specific total order of commands agreed upon when running state machine replication (SMR) is immaterial to fault tolerance: all that is required is for all correct nodes to follow the same order. In SMR-based blockchains, however, correct nodes should be responsible for being unbiased when choosing the total order, and for preventing malicious parties from manipulating the order to their advantage. The traditional specification of SMR correctness, however, has no language to express such responsibilities. This dissertation thus extends SMR as ordered consensus by introducing the language of ordering preferences and relevant features, which lead to the following contributions. With ordering preferences, the two notions of Byzantine democracy and Byzantine oligarchy are specified, which capture the minimum and maximum degree of power that Byzantine (e.g., malicious) nodes would have over the order. We prove that the minimum degree of Byzantine power is in general inevitable, but the maximum degree, a Byzantine oligarchy, can be avoided. To remove Byzantine oligarchies, this dissertation introduces Pompē, an SMR protocol that is guaranteed to order commands in a way analogous to linearizability. The evaluation shows that Pompē can achieve competitive performance compared to state-of-the-art SMR protocols in which Byzantine nodes dictate the total order. With relevant features, two principles are specified capturing the notion of equal opportunity, i.e., how correct nodes should treat clients equally instead of being biased toward certain clients. These principles are inspired by social sciences and law, leading to the notion of a point system. In a point system, system designers specify a set of relevant features and a function that maps a vector of feature values into a score. The total order is thus decided by scores and ties are broken randomly. To achieve equal opportunity, this dissertation introduces a secret random oracle (SRO), a system component that generates random numbers in a fault-tolerant manner, and Pompē-SRO, an extension of Pompē that is guaranteed to order commands in a way analogous to a point system. The evaluation shows that Pompē-SRO could mitigate real-world concerns about ordering in blockchains, including front-running and sandwich attacks.

Journal / Series

Volume & Issue

Description

117 pages

Sponsorship

Date Issued

2024-05

Publisher

Keywords

blockchain; equal opportunity; state machine replication

Location

Effective Date

Expiration Date

Sector

Employer

Union

Union Local

NAICS

Number of Workers

Committee Chair

Alvisi, Lorenzo

Committee Co-Chair

Committee Member

Yu, Xingzhong
Halpern, Joseph

Degree Discipline

Computer Science

Degree Name

Ph. D., Computer Science

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)

References

Link(s) to Reference(s)

Previously Published As

Government Document

ISBN

ISMN

ISSN

Other Identifiers

Rights

Rights URI

Types

dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record