PaperlayerView exact revision on arXiv

Source-linked AI summary

Wendy, the Good Little Fairness Widget

Klaus Kursawe

arXiv:2007.08303v1cs.CR

TL;DR

Decentralized trading markets make transaction-order manipulation a fairness concern, yet relative order fairness has received little attention. Wendy adds a modular fairness pre-protocol to existing blockchains and offers alternative definitions and protocols after showing that an intuitive definition is impossible. The protocols are described as having optimal resiliency in the asynchronous model and optimal message-passing-round latency within their architectural model.

  • Problem

    Consensus protocols have given little attention to transaction-order fairness, leaving decentralized markets exposed to transaction scheduling manipulation such as frontrunning and rushing attacks.

    Source: §1 · p. 1

  • Method

    Wendy adds a modular fairness pre-protocol to existing blockchains and provides alternative definitions and protocols for relative order fairness.

    Source: §1 · p. 2, §2 · p. 3

  • Results

    An intuitive relative-fairness definition is impossible, while the proposed protocols achieve optimal resiliency in the asynchronous model and optimal message-passing-round latency within their architectural model.

    Source: §1 · p. 2, §5 · p. 22

  • Takeaways & Limitations

    The modular protocols can provide different fairness levels for transaction sets on one blockchain and can be reconfigured without breaking the chain.

    Source: §1 · p. 2

    Optimizing latency by coordinating the fairness pre-protocol, atomic broadcast, and underlying gossip or multicast is outside the paper's scope.

    Source: §4.5.1 · p. 20

Abstract

from arXiv · show

The advent of decentralized trading markets introduces a number of new challenges for consensus protocols. In addition to the `usual' attacks -- a subset of the validators trying to prevent disagreement -- there is now the possibility of financial fraud, which can abuse properties not normally considered critical in consensus protocols. We investigate the issues of attackers manipulating or exploiting the order in which transactions are scheduled in the blockchain. More concretely, we look into relative order fairness, i.e., ways we can assure that the relative order of transactions is fair. We show that one of the more intuitive definitions of fairness is impossible to achieve. We then present Wendy, a group of low overhead protocols that can implement different concepts of fairness. Wendy acts as an additional widget for an existing blockchain, and is largely agnostic to the underlying blockchain and its security assumptions. Furthermore, it is possible to apply a the protocol only for a subset of the transactions, and thus run several independent fair markets on the same chain.

1 Introduction

Decentralized trading makes transaction order a fairness concern for consensus protocols, but order fairness has received little attention despite its relevance to frontrunning and rushing attacks. The paper examines relative order fairness, shows an intuitive definition is impossible, and presents alternative protocols designed to integrate with existing blockchains.

1 Introduction

  • Decentralized markets expose consensus protocols to transaction-order manipulation that can enable frontrunning or rushing attacks and may raise regulatory concerns.Some chains make such attacks harder, while others may be manipulated by one corrupt validator or a targeted denial-of-service attack.Source: §1 · p. 1
  • The paper investigates attackers manipulating transaction scheduling and asks how to make the relative order of transactions fair.Source: §1 · pp. 1–2
  • One intuitive definition of relative fairness is impossible to achieve, so the paper presents alternative fairness definitions.Source: §1 · p. 2
  • The proposed approach integrates with existing blockchains and can support different fairness levels for transaction sets on the same chain.The configuration can also change without breaking the chain.Source: §1 · p. 2

2 Model and Architecture

The architecture adds a fairness pre-protocol to an existing blockchain, with known validators and validity checks enforcing fairness for selected transactions. The related work distinguishes relative order fairness from delivery, causality, and validator fairness, and notes that common mitigation strategies do not guarantee relative fairness.

2 Model and Architecture

  • Fairness can be restricted to selected transactions: matching fairness labels or market identifiers determine which transactions must be fair relative to one another.Different markets may use different fairness pre-protocols, and a request may belong to several markets.Source: §2 · pp. 2, 4
  • The fairness pre-protocol assumes n = 3t+1 parties in a fully asynchronous model, authenticated messages, and known validators able to receive broadcasts.The underlying blockchain needs a validity function and known validators that can propose blocks containing fairness-relevant transactions.Source: §2 · pp. 2–3
  • A parallel pre-protocol generates blocks subject to fairness checks in the validity function, while leaving the underlying atomic-broadcast implementation unspecified.The fairness protocol participants must recognize one another; the approach can add relative fairness to some Bitcoin transactions if the chain enforces its validity condition and generated block order.Source: §2 · pp. 3–4
  • Combining different fairness protocols across markets is excluded from this paper because it adds complexity, despite no fundamental obstacle being identified.Source: §2 · p. 4

2.1 Related Work

  • Causality-based ordering fixes a message's position before participants learn its content, but commit-and-reveal alone does not prevent faster traders gaining an advantage.The cited discussion traces causality in state machine replication to Birman and Reiter and notes later refinements.Source: §2.1 · pp. 4–5
  • Delivery fairness bounds delay after enough honest parties see a request, whereas relative order fairness bounds how many requests can rush ahead of it.Validator-to-validator fairness is distinct from fairness for transactions from external participants.Source: §2.1 · p. 5
  • In proof-of-work chains, paying miners for preferred treatment makes relative unfairness an explicit design feature.Source: §2.1 · p. 5
  • Leader rotation and random selection make adversarial control of scheduling harder, but do not ensure that requests are delivered in their arrival order.Source: §2.1 · pp. 5–6

3 Relative Fairness

Relative order fairness asks that transaction arrival order be respected, but both the strict definition and a same-block relaxation are impossible. The section also describes block fairness and a simple validator-list procedure for implementing it.

3 Relative Fairness

  • Block fairness schedules a request in the next block after n−t honest parties have seen it, and validators exchange request lists to validate proposals.A valid proposal contains transactions from n−t lists that received t+1 votes.Source: §3 · p. 6
  • Strict relative fairness requires r1 to be delivered before r2 whenever all honest parties receive r1 first, but a cyclic schedule makes that requirement contradictory.Because honest parties cannot identify the faulty party, the ordering must satisfy incompatible requirements for each possible faulty party.Source: §3 · p. 7
  • Allowing r1 in the same block as r2 or earlier remains impossible: chained schedules can force arbitrarily many requests into one block.The construction joins message groups across interleaved schedules, then repeats the pattern to produce an infinite sequence requiring one block.Source: §3 · pp. 7–9
  • The impossibility does not require a designated corrupt party to behave maliciously; asynchronous liveness on n−t inputs can omit information relevant to a valid order.The authors prefer weaker fairness that remains robust against a Byzantine adversary.Source: §3 · p. 9
  • With bounded incoming requests, fairness may be achieved only by delivering all requests in the protocol’s sole block just before termination, without meaningful efficiency guarantees.For infinite protocol runs, the construction instead prevents the protocol from guaranteeing delivery of anything.Source: §3 · p. 9
  • The construction can also work under partial synchrony when the adversary can access enough requests and control the order of any 3n consecutive requests.Fewer than 3n other requests need to be processed between the first honest party seeing a request and the last honest party seeing it.Source: §3 · p. 10
  • Relative block fairness can force every request seen by any honest party into one block, so no block can be delivered while new requests continue arriving.The construction also works in a partially synchronous model when fewer than 3n other requests are processed before the last honest party sees a request.Source: §3 · p. 10

4 Circumventing the impossibility

The section presents a fairness pre-protocol for atomic broadcast, with validity information to check proposed blocks. Its safety follows from relative block fairness, but termination is not guaranteed and delivery has no absolute time bound.

4 Circumventing the impossibility

  • Wendy runs as a pre-protocol to atomic broadcast, producing a block proposal with validation information; one atomic-broadcast protocol can use different pre-protocols for different markets.The design assumes undelivered requests are replayed to the next pre-protocol instance in the same order.Source: §4 · pp. 10–11
  • Eventual delivery under relative fairness depends on the combined protocol terminating with nonempty blocks and replaying undelivered messages to later instances.Each terminating instance makes progress by placing at least one request in a block; only finitely many requests can precede a request seen by all honest parties.Source: §4 · p. 11
  • A request blocks another when their market identifiers match and current reports cannot exclude that the two must share a block or be ordered to preserve relative fairness.The supplied conditions distinguish reports that at least t + 1 parties saw the first request before the second from reports of the reverse order.Source: §4 · p. 11
  • The protocol guarantees safety: if all honest parties saw r′ before r, r′ is in the same or an earlier block than r.The validity proof carries the block's history, while the atomic-broadcast protocol catches conflicting valid-block proposals or contradictory signatures.Source: §4 · p. 12
  • An adversary can force arbitrarily many messages into one block and thereby keep the protocol processing that block indefinitely.The stated termination theorem is explicitly withdrawn: its proof is “Void, because the theorem is wrong.”Source: §4 · p. 13
  • Relative fairness gives no absolute bound on when a request is delivered or on the communication effort required before its block is delivered.The block depends on the number of undelivered earlier requests.Source: §4 · p. 13

4.1 Armageddon

The Armageddon discussion narrows the impossibility result to a protocol that remains in operation. Its liveness claim changes when validators opt out while the protocol is still active.

4.1 Armageddon

  • If usage ends and the protocol terminates, the impossibility result no longer applies; in the worst case, one block after genesis contains all transactions.This scenario assumes the adversary cannot keep the protocol running forever by generating its own transactions, which would require unlimited spending when transactions cost money.Source: §4.1 · p. 13
  • When validators opt out while the protocol is still operating, the required liveness guarantee is weaker than delivery of every request.The protocol should create all blocks it could before termination, but need not deliver every request in that setting.Source: §4.1 · p. 13
  • The paper does not quantify which messages may be lost when validators opt out during operation.It points to for a formalism to define such end-time scenarios.Source: §4.1 · p. 13

4.2 Relative Synchrony Assumption

The paper weakens the adversary’s complete control over message schedules by allowing honest messages to be delivered probabilistically. This avoids the impossibility result, but leaves practical performance bounds and the needed synchrony assumptions unresolved.

4.2 Relative Synchrony Assumption

  • The impossibility construction assumes the adversary completely controls the schedule; the alternative model gives each undelivered honest message probability p of delivery after an adversary delivery.Messages generated by an honest party in response enter the pool with probability p at a random position.Source: §4.2 · p. 14
  • This probabilistic model invalidates the impossibility result and permits an algorithm to achieve relative fairness, but unknown p leaves block size and latency without known upper bounds.Even with known p, the maximum possible block size may be prohibitively large; interweaving schedules can also make adversarial resilience arbitrarily high given enough messages.Source: §4.2 · p. 14
  • The model adds enough synchrony for deterministic Byzantine agreement because the adversary eventually fails to prevent termination.Source: §4.2 · p. 14
  • The authors leave open how much limited message delay suffices to circumvent impossibility, and say known timeouts alone may not suffice.They also note that p is hard to determine and may vary across messages, so expected block sizes and latency need further analysis.Source: §4.2 · pp. 14–15

4.3 Probabilistic Relative Block Fairness

The paper defines probabilistic relative block fairness and describes threshold-based ways to terminate the protocol. These approaches trade fairness guarantees against termination and potential block size.

4.3 Probabilistic Relative Block Fairness

  • Probabilistic relative block fairness requires that when all honest parties receive r1 before r2, r1 is delivered in the same or an earlier block with probability at least p.Source: §4.3 · p. 15
  • A request-count threshold rmax can force termination, but an adversary with sufficient network control can cause limited unfair scheduling.The cutoff could instead use a timeout or queue size; the paper says most requests will be scheduled fairly.Source: §4.3 · p. 15
  • After rmax, a common coin can make the stopping point unpredictable even to the leader, while smaller p requires capacity for correspondingly larger blocks.Coin shares can be piggybacked on voting messages.Source: §4.3 · p. 15

4.4 Fairness using Local Clocks

The section defines timed relative fairness using parties’ local clocks and presents a protocol that uses timestamped votes to produce blocks. It argues that the protocol preserves the stated ordering condition and terminates when an honest leader exists.

4.4 Fairness using Local Clocks

  • The proposed clock-based definition is weaker than the preceding fairness definition, but allows stronger liveness guarantees.Source: §4.4 · p. 15
  • Timed Relative Fairness requires r to be scheduled before r′ when all honest parties see r before a time τ and r′ after it.The definition does not require synchronized clocks; each clock must count forward and produce unique timestamps.Source: §4.4 · p. 16
  • The protocol can order requests within a delivered block locally, because timestamps are included in the block.It requires a request that must precede another to appear in an earlier or the same block.Source: §4.4 · p. 16
  • Timestamped vote validity requires sequence numbers to match timestamp order, while block validity requires n − t valid votes for each included request.A request with t + 1 lower-sequence votes must also be included with n − t validation votes.Source: §4.4 · pp. 16–17
  • The safety theorem states that if all honest parties see r′ before a time τ and r after it, r′ must be in r’s block or an earlier block.The proof derives a contradiction if r′ is omitted from those positions.Source: §4.4 · p. 17
  • If an honest party sees a request, an honest leader eventually terminates with a proposal; successful termination is required only when an honest leader exists.The termination argument relies on honest parties forwarding requests and eventually receiving n − t votes.Source: §4.4 · pp. 17–18

4.5 Optimizations

The section explores ways to reduce latency while maintaining fairness, including a fallback that switches to a weaker fair condition. It also describes the combined protocol as a service that supplies blocks to atomic broadcast.

4.5 Optimizations

  • When the neverending protocol exceeds r_max, the combined protocol switches to timed fairness instead of falling back to plain unfairness.This fair fallback permits more aggressive thresholds, with a slightly weaker fairness definition.Source: §4.5 · p. 18

4.5.1 Latency and performance impact

  • Relative fairness adds latency because leaders must wait to determine whether higher-priority requests exist.The mostly fair protocol trades latency against unfairness through its cutoff parameter; lower cutoffs speed up the worst case but make unfairness easier for an adversary to cause.Source: §4.5.1 · p. 18
  • Running the leader protocol in parallel for sufficiently reported requests lets the first instance to finish determine the next block.The neverending protocol’s threshold can also be reduced to t + 1 with a more sophisticated blocking function.Source: §4.5.1 · p. 18
  • Permanently running the voting phase can let the fairness pre-protocol finish quickly once atomic broadcast starts processing a block.This changes the design from a simple pre-protocol API to background work, which could be piggybacked on gossip to save overhead.Source: §4.5.1 · pp. 18–19
  • In the neverending protocol, later votes can unblock a request and remove it, along with requests blocked by it, from B, potentially releasing a block earlier.Source: §4.5.1 · p. 19
  • For the timed protocol, a blocker is resolved when t + 1 timestamps precede the median or n − t timestamps arrive with at most t below it.Further latency optimization requires rechecking whether incoming votes raise the median of an n − t vote subset.Source: §4.5.1 · p. 19
  • The authors believe the modified protocols have optimal latency within their modular architecture, meaning blocks cannot be handed to atomic broadcast earlier.For block fairness, the argument is that candidate blocks contain only requests that must or might share a block, given current information.Source: §4.5.1 · p. 19

4.5.2 The combined protocol

  • The combined protocol is a permanent service that takes requests and outputs blocks for atomic broadcast.The stated setup assumes a ready-request set D and a queue Q through which atomic broadcast consumes requests.Source: §4.5.2 · p. 20

4.6 Fairness and Advanced Staking

The section extends the fairness protocols to hybrid adversary structures, which can represent weighted voting and other staking configurations. It notes that adapting to randomly selected validator subsets requires further interface work.

4.6 Fairness and Advanced Staking

  • The hybrid-adversary-structure model generalizes the classical committee model to weighted votes and constraints such as geographic honesty requirements.The described committee setting has n parties, one vote each, and tolerates up to t Byzantine corruptions with n ≥ 3t + 1.Source: §4.6 · p. 20
  • Any staking model expressible with hybrid adversary structures is compatible with the protocols, though generalizing the proofs remains future work.The authors expect that proof generalization to be relatively straightforward.Source: §4.6 · p. 22
  • Random validator subsets require care so the fairness pre-protocol and atomic broadcast use somewhat synchronized subsets; this interface question is left for future work.The paper names Algorand as an example of random-subset selection.Source: §4.6 · p. 22

5 Conclusion

The conclusion frames strict relative fairness as impossible in Byzantine fault-tolerant settings and presents weaker fairness definitions and protocols as alternatives. It also claims optimal resiliency and latency within the stated models.

5 Conclusion

  • Relative fairness is impossible to achieve in a Byzantine fault-tolerant setting under the paper’s stronger definition.Source: §5 · p. 22
  • The paper presents protocols for weaker relative-order fairness definitions, including a hybrid that switches between two fairness levels to avoid the impossibility result.Source: §5 · p. 22
  • The protocols are largely blockchain-agnostic and claim optimal asynchronous resiliency and message-passing-round latency within the architectural model.Source: §5 · p. 22

Related papers

Loading 2007.08303v1…