Achieving Fairness in Byzantine Consensus through Order-Fairness Protocol

Order Order- -Fairness Fairness for for Byzantine Consensus Byzantine Consensus Zhitong Su Some pages adapted from Mahimna Kelkar s presentation at Crypto 2020

Roadmap 1. What is order-fairness 2. Why is order-fairness important 3. How to define order-fairness and impossibility to achieve 4. A new protocol Aequitas that achieves order-fairness 5. Some caveats about Aequitas

Consensus Properties Consistency (Safety) Liveness Validity

Are these all all we should care about? 5

Order-Fairness Almost all classical consensus protocols are leader-based E.g., PBFT , Paxos, Hotstuff, etc. Leader node can propose anyordering A malicious leader can arbitrarily manipulate theordering A fair ordering should reflect the initial orderings as much as possible. 4

Why is fair orderingimportant? 5

Why is fair orderingimportant? Bob has $0 Reverse Order Tx1: Bob sends $5 to Carol Tx0: Alice sends $5 to Bob Tx0: Alice sends $5 to Bob Tx1: Bob sends $5 to Carol Tx1 invalid Both tx valid The execution order can determine the validity of a given transaction 6

Why is fair orderingimportant? Ordering matters in trading, e.g. frontrunning in Wall Street Manipulation of tx ordering in Ethereum by bots extracts 6M in revenue from unsophisticated users Daianet al.(IEEES&P2020) 7

How to d defin efine efair ordering? 10

Comparison to validity If all honest nodes input ?'before ?, then all honest nodeswill agree on ?'before ?. Order-Fairness If all honest nodes input value?, then all honest nodeswill agree on?. Validity 8

A strong notion of order-fairness Definition (informal):Receive-Order-Fairness If sufficiently many (at least ?-fraction) nodes are input ?'before?, thenthe final ordering should deliver ?'before ?. *1/2 < ? <= 1 is the order-fairness parameter 14

Unfortunately, impossible Theorem(informal): Impossibility ofReceive-Fairness No protocol can always output a final ordering that achieves receive-order-fairness. 20

CondorcetParadox Global ordering can be non-transitive evenwhen local orderings are transitive Alice Carol Bob 1. 1. 1. ? ? ? 2. 2. 2. ? ? ? 3. 3. 3. ? ? ? 15

CondorcetParadox Global ordering can be non-transitive evenwhen individual orderings aretransitive Alice Carol Bob ? ? 1. 1. 1. ? ? ? 2. 2. 2. ? ? ? 3. 3. 3. ? ? ? 16

CondorcetParadox Global ordering can be non-transitive evenwhen local orderings aretransitive Alice Carol Bob ? ? ? ? 1. 1. 1. ? ? ? 2. 2. 2. ? ? ? 3. 3. 3. ? ? ? 17

CondorcetParadox Global ordering can be non-transitive evenwhen local orderings aretransitive Alice Carol Bob ? ? ? ? ? ? 1. 1. 1. ? ? ? 2. 2. 2. ? ? ? 3. 3. 3. ? ? ? 18

CondorcetParadox Global ordering can be non-transitive evenwhen local orderings aretransitive Alice Carol Bob ? ? ? ? X ? ? 1. 1. 1. ? ? ? Z y 2. 2. 2. ? ? ? CyclicOrdering! 3. 3. 3. ? ? ? 19

What shall we do now? Relaxing the Definition! 10

A weak notion of order-fairness Definition (informal):Block-Order-Fairness If a majority of nodes are input ?'before?, thenthe final ordering will not deliver ? in a later block than ?. Key Idea: Deliver transactions with non-transitive ordering in the same block 21

Minimal use of this relaxation When there is an non-transitive global ordering, the protocol guarantees to achieve the weak notion of order-fairness When there is not an non-transitive global ordering, the protocol guarantees to achieve the strong notion of order-fairness

Model Setups 26

Adversarial Model Permissioned systemwith? nodes,? of which maybe malicious The adversary ? can corrupt any node at any time (Adaptive Adversary) 11

Network Model ExternalNetwork Communication between clients and protocol nodes Clients send transactionsto allnodes Adversary ? notin charge of messagedelivery InternalNetwork Communication amongst protocolnodes Adversary ? can reorder or delay messages 12

Four Constructions Synchronous Network, leaderless protocol (today s focus) Synchronous Network, leader-based protocol Asynchronous Network, leaderless protocol Asynchronous Network, leader-based protocol

Aequitas: Order-Fairness Protocols 26

A general order-fairness compiler Two basic primitives: FIFO-broadcast and Set-BA They can be realized from any consensus protocol General compiler thattakesanyconsensus protocol and transformsitinto one thatalso provides order-fairness 39

Aequitas: A Fair-Ordering Protocol Inputs GossipStage ??% ??# ?& AgreementStage ??$ ?# Output FinalizationStage ?' 27

GossipStage Honest nodes broadcast transactions to all nodes in the order they arereceived Honest nodes storebroadcasts received from other nodes ?contains ? s view of broadcasts by ? in local logs ????????? - Goal: Guaranteesthathonest nodes have consistentlocal logs 28

GossipStage FIFO(First-In-First-Out)Broadcast Messages broadcast by anhonest sender aredelivered in the same order as they werebroadcast Messages broadcast by an adversarial sender are delivered in a consistent order by all honest nodes Can be realized from standard reliable broadcast [HDvR07] 29

AgreementStage For a particular transaction, different nodes might have different sets of local orderings that contains it Agree on a single set of nodes whose local orderings should be considered for deciding on the global ordering of a particular transaction Can be done using standard Byzantine agreement Goal: Guaranteesthathonest nodes usethesamelocal logs to finalize atransaction 30

FinalizationStage Finalize the global ordering of a transaction using the set of local orderings decided Leaderless No extracommunication 31

FinalizationStage Ordering twotransactions Ifmany(e.g.,?? ?)local logs contain ?? before ??,then?? is said to waitfor ?? Relations between transactions areviewed in a dependency or waitinggraph. Vertices representtransactions Edge (?,?)represents? waiting for ? 32

LeaderlessFinalization What if thereis no clear winner in the two transactions? Two problems tosolve 1. Graph maynot be complete or evenconnected Some transactions may not becomparable 2. Graph may have cycles 33

LeaderlessFinalization Solution to problem 1 (No Edges) Wait for common descendant for transactions without anedge in the graph ??1 ??0 ??2 ??3 ??4 Orderusing maximum number of dependents (max first, tie break) tx0 -> tx2 -> tx1 -> tx3 -> tx4 34

LeaderlessFinalization Solution to problem 2 (Cycles) To get a total ordering, compute the condensation graph by collapsingthe strongly-connected components Delivertransactionsin the samecomponent into the sameblock. ??3 ??1 ??0 ??2 ??4 35

?? Synchronous protocol requires ? > ??-? i.e., ? > 2? even when ? =1 ?? Asynchronous protocol requires ? > ??-? 36

SomeCaveats Only AchievesWeak-Liveness New transactionsmustbe input sufficiently late in order to deliver current transactions Conventional Liveness achieved when externalnetwork hassmall synchronybound 37

SomeCaveats Adversary can unfairly order if it controls the entireInternet, i.e.if it can also control aclient s connection to the consensus protocolnodes Inour modeling, thisis handled by assuming adversary does not control the externalnetwork 38

Final Questions?