On Fair Ordering and Differential Privacy

Lorenzo Alvisi; Neel Basu; Shir Cohen; Soumya Basu

REVIEW 4 major objections 6 minor 1 cited by

On Fair Ordering and Differential Privacy

T0 review · 4 major / 6 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Any differential-privacy noise mechanism can enforce fair ordering in blockchain systems.

desk verdict A promising DP-fairness link, but the main proof has an invalid step; not acceptable as is. read the letter →

arxiv 2501.05535 v1 pith:43XWYF7Q submitted 2025-01-09 cs.CR cs.DC

Shir Cohen , Neel Basu , Soumya Basu , Lorenzo Alvisi This is my paper · ORCID

classification cs.CRcs.DC

keywords BlockchainDifferentialPrivacyFairOrderingStateMachineReplicationEqualityGroupMinerExtractableValue

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper establishes that fair transaction ordering in blockchain-style state machine replication is the same mathematical problem as differential privacy. The authors define fairness as kε-Ordering Equality: any two requests r and r′ must satisfy Pr[r ≺ r′] ≤ $e^{{kε}}$ Pr[r′ ≺ r], where k is the normalized distance between their scores. They prove that if the ordering server scores a request as the sum of a relevant feature and an irrelevant noise term, then every additive-noise DP mechanism with sensitivity equal to the noise bound λ yields this property for identical features (ε-Ordering Equality) and, through group privacy, for similar features (kε-Ordering Equality). This matters because it lets protocol designers reuse mature DP mechanisms to suppress front-running, sandwich attacks, and fee/bribery manipulation, and it extends earlier equal-opportunity ordering from timestamps alone to arbitrary relevant features.

What carries the argument

The machinery is the additive score model score(r) = r.relev + r.η with the sensitivity bound λ = max_{r∼r′} ||r.η − r′.η||. This converts fairness into a sensitivity-calibrated DP question: changing a request's relevant feature changes the score by at most λ, so adding DP noise hides the irrelevant component exactly to the degree needed to equalize ordering chances. The derived parameter k = |score(r)−score(r′)|/λ then extends the guarantee to non-identical relevant features by invoking group privacy, which is the DP statement for databases at distance k.

What would settle it

A concrete way to test the claim is to build an ordering server with controlled noise, fix λ, emit pairs of requests with identical relevant features whose noise terms differ by more than λ, and measure whether the probability of one ordering exceeds e^ε times the reverse; a violation would show the assumed bound is broken, while no violation under the bound would support the reduction. Because the theorem is conditional on Assumption 1, the more direct falsifier is any real system where scores are non-additive or λ is unbounded, since the mapping from fairness to DP no longer applies.

Watch

Extended reading notes

Core claim

The central claim, stated as Theorem 1 and Theorem 2, is that privacy and fair ordering coincide under the additive score model. For any two requests with identical relevant features, ε-Ordering Equality is exactly the ε-DP inequality applied to the outputs of the ordering algorithm; for requests whose relevant features differ, the group-privacy version of DP gives the kε-Ordering Equality bound with k = |score(r)−score(r′)|/λ. The proof is a direct mapping: adjacent requests correspond to neighboring datasets, the sensitivity bound λ supplies the Δ(f) needed by additive-noise mechanisms, and the probability that one request is ordered before the other is a product of the mechanism's output distributions, so the DP ratio inequality transfers to the ordering probability ratio.

Load-bearing premise

The proof depends on every request's score being exactly the sum of a relevant feature and an irrelevant noise term, and on the maximum possible noise gap between adjacent requests being a known, finite value λ.

Editorial extensions

If this is right

An ordering server that implements any ε-differentially private additive-noise mechanism (for example, Laplace or bounded Laplace) with sensitivity λ satisfies ε-Ordering Equality for arbitrary relevant features, not just timestamps.
For requests with similar but non-identical relevant features, the guarantee degrades smoothly as e^{kε}, so small measurement differences cannot be exploited to bypass fairness entirely.
Treating miner fees as the relevant feature and out-of-band bribes as bounded noise deters fee-driven reordering and reduces miner extractable value.
Treating the time of transaction issuance as the relevant feature and network delay as noise mitigates front-running and sandwich attacks.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The paper leaves implicit that the reduction also suggests a converse: if fair ordering under the additive-score model is equivalent to DP, then any impossibility or lower bound for DP noise calibration transfers to fair ordering, which could guide protocol design.
A practical consequence the authors do not develop is that λ must be set by the protocol designer; if λ is estimated from observed delays or bribes rather than guaranteed, the fairness bound becomes probabilistic rather than absolute.
A natural testable extension is to instantiate the Laplace mechanism in a small ordering service and empirically measure the ordering probability ratio for controlled synthetic requests to verify the e^{kε} bound holds in practice.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

The paper's core claim—that differential privacy mechanisms guarantee fair ordering—is not established by the text. Theorem 1's proof (Section 5.1) has an invalid inequality: for each pair of scores, it replaces both probability factors using the DP bound but multiplies by only one e^ε. The stress-test counterexample shows why this matters: DP closeness alone only gives e^{2ε} between the two ordering probabilities, not e^ε, and the proof never uses the additive-noise structure it claims to rely on. The abstract's 'any DP mechanism' is also an overstatement—the theorem is limited to additive noise.

What's genuinely new: the paper extends Zhang et al.'s ε-Ordering Equality to arbitrary relevant features and a multiplicative bound, introduces kε-Ordering Equality for non-identical features, and frames the whole thing as a privacy problem. Those definitions are clean and the motivation is clear. The writing is honest about the prior work, and the connection to group privacy for the kε case is a nice observation. The related work section is accurate.

The soft spots are concentrated in the proof. Theorem 2 is stated without a proof, which matters because it's half the claimed contribution. The applications section (MEV, fees) is speculative and adds little. Assumption 1, bounding the noise, may be hard to verify in practice, but that's not a fatal issue for a theory paper.

If the proof can be repaired, this could be a decent short paper: the definitional work is useful, and the DP connection is worth stating carefully. But as written, the central result doesn't hold up. I'd send it to review anyway—the idea is novel enough, and the error is the kind that might be fixable—but the reviewers should be instructed to scrutinize the proof. Credit to the authors for a well-written paper, but the main theorem needs real work before it's citable.

Referee Report

4 major / 6 minor

Summary. The paper proposes a generalization of Zhang et al.'s epsilon-Ordering Equality, called k-epsilon-Ordering Equality, which is intended to apply to arbitrary relevant features and to degrade gracefully as relevant features diverge. The central technical claim is a connection to differential privacy: the authors state that any additive-noise differential privacy mechanism, applied to a score of the form score(r) = r.relev + r.eta with sensitivity lambda, guarantees the fairness property. Theorem 1 (Section 5.1) asserts this for adjacent requests, and Theorem 2 (Section 5.2) asserts an analogous k-epsilon bound for non-identical relevant features, invoking group privacy. The paper also sketches applications to miner fees and transaction issuance time. The main formal contribution, however, is not established: the proof of Theorem 1 is invalid, and Theorem 2 is stated without proof.

Significance. If the central theorem were correct, the paper would offer an interesting bridge between differential privacy and fair transaction ordering, and the proposed k-epsilon-Ordering Equality could be a useful refinement of prior fairness notions. The paper also has the merit of making its assumptions explicit (Assumption 1), and the application discussion identifies concrete scenarios with additive scores. However, because the main proof fails and the second theorem is unproved, the paper's principal claim is currently unsupported. The 'surprising link' is also weakened by the fact that the fairness definition is intentionally modeled on the DP inequality, so the resemblance is in part a matter of definitional choice rather than an independent discovery.

major comments (4)

[§5.1, Theorem 1 proof] The proof of Theorem 1 is invalid. The summation over s,s' introduces an undefined constant k, and the inequality step replaces Pr[A(score(r))=s] with Pr[A(score(r'))=s] and Pr[A(score(r'))=s'] with e^epsilon Pr[A(score(r))=s'] in a manner that requires the pointwise assumption Pr[A(score(r))=s] <= Pr[A(score(r'))=s] to hold for every output s. But if that inequality holds for all s, then both distributions must be identical, since both sum to 1; conversely, if it holds only for a single s, it cannot be used in the summation over all s,s'. Thus the derivation of Pr[r ≺ r'] <= e^epsilon Pr[r' ≺ r] is not justified, and the 'by symmetry' remark does not repair the gap.
[§5.1, Theorem 1 assumptions] The proof uses only the pointwise epsilon-DP closeness of the two marginal distributions Pr[A(score(r))] and Pr[A(score(r'))]; it never uses the additive-noise structure or the independence of the noise draws for the two requests. The theorem statement specifically assumes an additive-noise DP mechanism, but the argument would apply equally to any mechanism whose output distributions on adjacent inputs are epsilon-DP. This is a load-bearing omission: if the intended result relies on properties of additive noise (e.g., independent, identically distributed noise), those properties must appear explicitly in the proof. As written, the theorem is not established.
[§5.2, Theorem 2] Theorem 2 is stated without proof. The sentence 'Using similar proof techniques as in §5.1, we prove that group privacy ensures the preservation of order fairness' is not a proof, and given the defect in Theorem 1's proof, the claimed implication is unsupported. In addition, the parameter k = |score(r)-score(r')|/lambda in Definition 5 does not correspond to the group size in group privacy: lambda is the maximum noise difference between adjacent requests, not a scale for differences in relevant features between non-adjacent requests. Therefore the asserted correspondence with group privacy is not justified.
[Abstract and Theorem 1 statement] The abstract and introduction claim that 'any DP mechanism can be used to ensure fairness in SMR,' but the formal theorem is restricted to additive-noise DP mechanisms applied to an additive score with a known sensitivity lambda. This overstates the formal result. The authors should either prove the general claim or revise the abstract to match the theorem's actual assumptions.

minor comments (6)

[§2/§4] The symbol r ∼ r' is used for both adjacent requests in fair ordering and neighboring datasets in differential privacy; this overloaded notation is confusing and should use distinct symbols.
[Definition 1] Definition 1 quotes Zhang et al.'s property with an unspecified function f(epsilon); since f is never defined, the definition is incomplete as presented.
[§5.1] The phrase 'for some fixed s ∈ A(score(r))' is imprecise: A(score(r)) is a distribution, not a set of outputs, and the DP inequality applies to every output s in the range of A, not to a single fixed element.
[§5.3] The claim that 'Companies like Google and Apple use epsilon ≈ 2 in DP' lacks a citation; please provide a reference.
[§6] In the miner-fee application, the assumption that client fees are significantly higher than bribes is informal; it is unclear how this assumption instantiates the bounded-noise parameter lambda in Assumption 1.
[Theorem 1 statement] The wording 'D is applied to A' is ambiguous; the paper should state explicitly how the order is produced from the noisy scores and whether the two requests' noise draws are independent.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the fairness definition and DP are distinct, and the theorem's failure is a proof gap, not a definitional reduction.

full rationale

The paper's central claim is Theorem 1: an additive-noise DP mechanism applied to an additive score guarantees the revised ε-Ordering Equality. The fairness property (Definition 2) is not literally the DP inequality: DP compares the probability of the same output event under two neighboring inputs, while ε-Ordering Equality compares the complementary ordering events Pr[r≺r′] and Pr[r′≺r] for one pair of requests. The proof attempts to derive the latter from pointwise DP closeness of the two marginal score distributions, and the step where one DP term is replaced without a matching bound is an algebraic gap. An invalid derivation is a correctness problem, not circularity: the conclusion is not true by construction, and no fitted parameter is later renamed as a prediction. The paper explicitly says its definitions resemble DP 'by design,' but resemblance is not equivalence; the theorem still requires a nontrivial argument. Theorem 2 is stated without proof, but an unproved theorem is also a completeness concern rather than a circular reduction. The only overlapping-author citation, Pompe [20], appears in related work and is not load-bearing for the main reduction. The derivation therefore does not reduce, by the paper's own equations, to its inputs.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

The paper rests on a restrictive additive noise model and a known bound on irrelevant noise (Assumption 1). It introduces no new mathematical entities; its free parameters are system design choices (epsilon, lambda), not fitted to data.

assumptions (4)

domain assumption The score of a request is the sum of its relevant feature and an irrelevant noise term: score(r) = r.relev + r.eta.
Stated in Section 3 as the focus of the paper. The entire framework depends on this additive form.
domain assumption There exists a known bound lambda = max_{r ~ r'} ||r.eta - r'.eta|| on the noise difference between adjacent requests.
Assumption 1, Section 3. This bound is used as the DP sensitivity; if it is unknown or infinite, the reduction fails.
domain assumption A reliable ordering server S exists and can compute scores and apply a DP mechanism.
Model in Section 2. The paper assumes a trusted S, abstracting away Byzantine faults in the ordering service.
standard math Standard differential privacy definitions and the Laplace mechanism's sensitivity guarantee are taken as background.
Section 4 reviews standard DP concepts. The proof relies on the DP inequality and sensitivity calibration without re-deriving them.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Fair Ordering and Differential Privacy." pith.science (2026). https://pith.science/paper/43XWYF7Q

@misc{pith2026250105535,
  author       = {Pith},
  title        = {Pith review of: On Fair Ordering and Differential Privacy},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/43XWYF7Q}},
  note         = {Machine review of arXiv:2501.05535}
}

read the original abstract

In blockchain systems, fair transaction ordering is crucial for a trusted and regulation-compliant economic ecosystem. Unlike traditional State Machine Replication (SMR) systems, which focus solely on liveness and safety, blockchain systems also require a fairness property. This paper examines these properties and aims to eliminate algorithmic bias in transaction ordering services. We build on the notion of equal opportunity. We characterize transactions in terms of relevant and irrelevant features, requiring that the order be determined solely by the relevant ones. Specifically, transactions with identical relevant features should have an equal chance of being ordered before one another. We extend this framework to define a property where the greater the distance in relevant features between transactions, the higher the probability of prioritizing one over the other. We reveal a surprising link between equal opportunity in SMR and Differential Privacy (DP), showing that any DP mechanism can be used to ensure fairness in SMR. This connection not only enhances our understanding of the interplay between privacy and fairness in distributed computing but also opens up new opportunities for designing fair distributed protocols using well-established DP techniques.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Time Is Money: Incentivized Causal Transaction Ordering
cs.CR 2026-07 conditional novelty 7.0 of 10

A power-weighted randomized lottery with superlinear bid weights lets a user deter front-runners with a single bid that forms a subgame-perfect equilibrium.

Reference graph

Works this paper leans on

21 extracted references · 17 canonical work pages · cited by 1 Pith paper

[1]

Prof: Pro tected order ﬂow in a proﬁt-seeking world

Kushal Babel, Nerla Jean-Louis, Yan Ji, Ujval Misra, Mahi mna Kelkar, Kosala Yapa Mudiyanselage, Andrew Miller, and Ari Juels. Prof: Pro tected order ﬂow in a proﬁt-seeking world. arXiv preprint arXiv:2408.02303 , 2024

arXiv 2024
[2]

Quick order fairness

Christian Cachin, Jovana Mićić, Nathalie Steinhauer, an d Luca Zanolini. Quick order fairness. In International Conference on Financial Cryptography and Da ta Security, pages 316–333. Springer, 2022

work page 2022
[3]

Practical byzantin e fault tolerance

Miguel Castro, Barbara Liskov, et al. Practical byzantin e fault tolerance. In OsDI, volume 99, pages 173–186, 1999

work page 1999
[4]

Flash boys 2.0: Frontrun ning in decentralized exchanges, miner extractable value, and consensus instabi lity

Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xue yuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. Flash boys 2.0: Frontrun ning in decentralized exchanges, miner extractable value, and consensus instabi lity. In 2020 IEEE sym- posium on security and privacy (SP) , pages 910–927. IEEE, 2020

work page 2020
[5]

Diﬀerential privacy

Cynthia Dwork. Diﬀerential privacy. In International colloquium on automata, languages, and programming , pages 1–12. Springer, 2006. 10 S. Cohen et al

work page 2006
[6]

Overview, 2021

Flashbots. Overview, 2021. URL: https://docs.flashbots.net/flashbots- auction/overview

work page 2021
[7]

Ethereum’s proposer-builder separation: Promises and realities

Lioba Heimbach, Lucianna Kiﬀer, Christof Ferreira Torre s, and Roger Watten- hofer. Ethereum’s proposer-builder separation: Promises and realities. In Proceed- ings of the 2023 ACM on Internet Measurement Conference , page 406–420, 2023. doi:10.1145/3618257.3624824

arXiv 2023
[8]

The bounded laplace mechanism in diﬀerential privacy

Naoise Holohan, Spiros Antonatos, Stefano Braghin, and P ól Mac Aonghusa. The bounded laplace mechanism in diﬀerential privacy. arXiv preprint arXiv:1808.10410, 2018

arXiv 2018

Show all 21 references

[9]

Themis: Fast, strong order-fairness in byzantine consensu s

Mahimna Kelkar, Soubhik Deb, Sishan Long, Ari Juels, and S reeram Kannan. Themis: Fast, strong order-fairness in byzantine consensu s. In Proceedings of the 2023 ACM SIGSAC Conference on Computer and Communications S ecurity, pages 475–489, 2023

2023
[10]

Order-fairness for byzantine consensus

Mahimna Kelkar, Fan Zhang, Steven Goldfeder, and Ari Jue ls. Order-fairness for byzantine consensus. In Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa B arbara, CA, USA, August 17–21, 2020, Proceedings, Part III 40 , pag...

2020
[11]

Wendy, the good little fairness widget: A chieving order fairness for blockchains

Klaus Kursawe. Wendy, the good little fairness widget: A chieving order fairness for blockchains. In Proceedings of the 2nd ACM Conference on Advances in Financi al Technologies, pages 25–36, 2020

2020
[12]

Time, clocks, and the ordering of events in a distributed system

Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM , 21(7):558–565, 1978

1978
[13]

Paxos made simple

Leslie Lamport. Paxos made simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) , pages 51–58, 2001

2001
[14]

Diﬀere ntial privacy: The future of work and open challenges

National Institute of Standards and Technology. Diﬀere ntial privacy: The future of work and open challenges. Cybersecurity Insig hts Blog, June 2023. URL: https://www.nist.gov/blogs/cybersecurity-insights/ differential-privacy-future-work-open-challenges

2023
[15]

Brief announcement: F air ordering via stream- ing social choice theory

Geoﬀrey Ramseyer and Ashish Goel. Brief announcement: F air ordering via stream- ing social choice theory. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing , pages 279–282, 2024

2024
[16]

Implementing fault-tolerant service s using the state machine approach: A tutorial

Fred B Schneider. Implementing fault-tolerant service s using the state machine approach: A tutorial. ACM Computing Surveys (CSUR) , 22(4):299–319, 1990

1990
[17]

Frontru nner jones and the raiders of the dark forest: An empirical study of frontrunning on the ethereum blockchain

Christof Ferreira Torres, Ramiro Camino, et al. Frontru nner jones and the raiders of the dark forest: An empirical study of frontrunning on the ethereum blockchain. In 30th USENIX Security Symposium (USENIX Security 21) , pages 1343–1359, 2021

2021
[18]

Hotstuﬀ: Bft consensus with linearity and responsiven ess

Maofan Yin, Dahlia Malkhi, Michael K Reiter, Guy Golan Gu eta, and Ittai Abra- ham. Hotstuﬀ: Bft consensus with linearity and responsiven ess. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computi ng, pages 347–356, 2019

2019
[19]

Ordered Consensus With Equal Opportunity

Yunhao Zhang. Ordered Consensus With Equal Opportunity . PhD thesis,
[20]

image.png

Yunhao Zhang, Srinath Setty, Qi Chen, Lidong Zhou, and Lo renzo Alvisi. Byzan- tine ordered consensus without byzantine oligarchy. In 14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20) , pages 633–649, 2020. This figure "image.png" is available in "...

2020 arXiv
[2024]

URL: https://www.proquest.com/dissertations-theses/ordered-consensus- with-equal-opportunity/docview/3069188897/se-2

Copyright - Database copyright ProQuest LLC; ProQues t does not claim copyright in the individual underlying works; Last up dated - 2024-08-20. URL: https://www.proquest.com/dissertations-theses/ordered-consensus- with-equal-opportunity/docview/3069188897/se-2

2024

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [1]

Prof: Pro tected order ﬂow in a proﬁt-seeking world

Kushal Babel, Nerla Jean-Louis, Yan Ji, Ujval Misra, Mahi mna Kelkar, Kosala Yapa Mudiyanselage, Andrew Miller, and Ari Juels. Prof: Pro tected order ﬂow in a proﬁt-seeking world. arXiv preprint arXiv:2408.02303 , 2024

arXiv 2024

[2] [2]

Quick order fairness

Christian Cachin, Jovana Mićić, Nathalie Steinhauer, an d Luca Zanolini. Quick order fairness. In International Conference on Financial Cryptography and Da ta Security, pages 316–333. Springer, 2022

work page 2022

[3] [3]

Practical byzantin e fault tolerance

Miguel Castro, Barbara Liskov, et al. Practical byzantin e fault tolerance. In OsDI, volume 99, pages 173–186, 1999

work page 1999

[4] [4]

Flash boys 2.0: Frontrun ning in decentralized exchanges, miner extractable value, and consensus instabi lity

Philip Daian, Steven Goldfeder, Tyler Kell, Yunqi Li, Xue yuan Zhao, Iddo Bentov, Lorenz Breidenbach, and Ari Juels. Flash boys 2.0: Frontrun ning in decentralized exchanges, miner extractable value, and consensus instabi lity. In 2020 IEEE sym- posium on security and privacy (SP) , pages 910–927. IEEE, 2020

work page 2020

[5] [5]

Diﬀerential privacy

Cynthia Dwork. Diﬀerential privacy. In International colloquium on automata, languages, and programming , pages 1–12. Springer, 2006. 10 S. Cohen et al

work page 2006

[6] [6]

Overview, 2021

Flashbots. Overview, 2021. URL: https://docs.flashbots.net/flashbots- auction/overview

work page 2021

[7] [7]

Ethereum’s proposer-builder separation: Promises and realities

Lioba Heimbach, Lucianna Kiﬀer, Christof Ferreira Torre s, and Roger Watten- hofer. Ethereum’s proposer-builder separation: Promises and realities. In Proceed- ings of the 2023 ACM on Internet Measurement Conference , page 406–420, 2023. doi:10.1145/3618257.3624824

arXiv 2023

[8] [8]

The bounded laplace mechanism in diﬀerential privacy

Naoise Holohan, Spiros Antonatos, Stefano Braghin, and P ól Mac Aonghusa. The bounded laplace mechanism in diﬀerential privacy. arXiv preprint arXiv:1808.10410, 2018

arXiv 2018