Back to search

Cornell University

Ordered Consensus with Equal Opportunity

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2024

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zhang, Yunhao
Chair dc:contributor.chair
  • Alvisi, Lorenzo
Committee members dc:contributor.committeemember
  • Yu, Xingzhong
  • Halpern, Joseph

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16575545
Dc Identifier Other
ProQuest Submission ID: 14282
ProQuest Publication ID: 31242934

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Zhang, Yunhao. Ordered Consensus with Equal Opportunity. Doctor of Philosophy thesis, Cornell University, 2024. https://hdl.handle.net/1813/116050