*

On Fairness Concerns in the Blockchain Ecosystem

A dissertation submitted towards the degree
Doctor of Engineering
of the Faculty of Mathematics and Computer Science of
Saarland University

by
Johnnatan Messias Peixoto Afonso

Saarbrücken
2023

Date of Colloquium: April 25${}^{\textrm{th}}$, 2024 Dean of Faculty:
Univ.-Prof. Dr. Roland Speicher Chair of the Committee: Prof. Dr. Anja
Feldmann Reporters First Reviewer: Prof. Dr. Krishna P. Gummadi Second
Reviewer: Prof Dr. Ingmar Weber Third Reviewer: Prof. Dr. Balakrishnan
Chandrasekaran Fourth Reviewer: Prof. Dr. Patrick Loiseau Academic Assistant:
Dr. Abhisek Dash

©2023

Johnnatan Messias Peixoto Afonso

ALL RIGHTS RESERVED

## Abstract

Blockchains revolutionized centralized sectors like banking and finance by
promoting decentralization and transparency. In a blockchain, information is
transmitted through transactions issued by participants or applications.
Miners crucially select, order, and validate pending transactions for block
inclusion, prioritizing those with higher incentives or fees. The order in
which transactions are included can impact the blockchain final state.

Moreover, applications running on top of a blockchain often rely on governance
protocols to decentralize the decision-making power to make changes to their
core functionality. These changes can affect how participants interact with
these applications. Since one token equals one vote, participants holding
multiple tokens have a higher voting power to support or reject the proposed
changes. The extent to which this voting power is distributed is questionable
and if highly concentrated among a few holders can lead to governance attacks.

In this thesis, we audit the Bitcoin and Ethereum blockchains to investigate
the norms followed by miners in determining the transaction prioritization. We
also audit decentralized governance protocols such as Compound to evaluate
whether the voting power is fairly distributed among the participants. Our
findings have significant implications for future developments of blockchains
and decentralized applications.

## Zusammenfassung

Blockchain-Technologien revolutionierten zentralisierte Bereiche wie Bankwesen
und Finanzen, indem sie Dezentralisierung und Transparenz förderten. In einer
Blockchain wird Informationen durch Transaktionen übertragen, die von
Teilnehmern oder Anwendungen ausgestellt werden. Miner wählen Transaktionen
aus, ordnen sie an und validieren sie für die Aufnahme in einen Block. Dabei
priorisieren sie jene Transaktionen mit höheren Gebühren. Die Reihenfolge, in
der Transaktionen aufgenommen werden, kann den endgültigen Zustand der
Blockchain beeinflussen.

Anwendungen, die auf einer Blockchain laufen, oft auf Governance-Protokolle
angewiesen, um die Entscheidungsbefugnis zur Änderung ihrer Kernfunktionalität
zu dezentralisieren. Diese Änderungen können beeinflussen, wie Teilnehmer mit
diesen Anwendungen interagieren. Da ein Token einem Stimmrecht entspricht,
haben Teilnehmer mit mehreren Tokens eine höhere Abstimmungsbefugnis, um die
vorgeschlagenen Änderungen zu unterstützen oder abzulehnen. Fraglich ist,
inwieweit diese Abstimmungsbefugnis verteilt ist.

In dieser Arbeit prüfen wir die Bitcoin- und Ethereum-Blockchains, um die
Normen zu untersuchen, denen Miner folgen, um die Priorisierung von
Transaktionen festzulegen. Wir überprüfen dezentrale Governance-Protokolle wie
Compound, um festzustellen, ob die Abstimmungsbefugnis fair unter den
Teilnehmern verteilt ist. Unsere Ergebnisse haben wesentliche Auswirkungen auf
zukünftige Entwicklungen von Blockchains und dezentralen Anwendungen.

## Publications

Parts of this thesis have appeared in the following publications and technical
reports.

  * •

“Understanding Blockchain Governance: Analyzing Decentralized Voting to Amend
DeFi Smart Contracts”. J. Messias, V. Pahari, B. Chandrasekaran, K. P.
Gummadi, and P. Loiseau. This work has been submitted and we are currently
awaiting a decision.

  * •

“Dissecting Bitcoin and Ethereum Transactions: On the Lack of Transaction
Contention and Prioritization Transparency in Blockchains”. J. Messias, V.
Pahari, B. Chandrasekaran, K. P. Gummadi, and P. Loiseau. In Proceedings of
the 27${}^{\textrm{th}}$ Financial Cryptography and Data Security (FC), Bol,
Brač, Croatia, May 2023.

  * •

“Selfish & Opaque Transaction Ordering in the Bitcoin Blockchain: The Case for
Chain Neutrality”. J. Messias, M. Alzayat, B. Chandrasekaran, K. P. Gummadi,
P. Loiseau, and A. Mislove. In Proceedings of the 21${}^{\textrm{st}}$ ACM
SIGCOMM Internet Measurement Conference (IMC), Virtual Event, November 2021.

  * •

“On Blockchain Commit Times: An analysis of how miners choose Bitcoin
transactions”. J. Messias, M. Alzayat, B. Chandrasekaran, and K. P. Gummadi.
In 2${}^{\textrm{nd}}$ International KDD Workshop on Smart Data for Blockchain
and Distributed Ledger (SDBD), Virtual Event, August 2020.

Additional publications and technical reports while at MPI-SWS.

  * •

“Modeling Coordinated vs. P2P Mining: An Analysis of Inefficiency and
Inequality in Proof-of-Work Blockchains”. M. Alzayat, J. Messias, B.
Chandrasekaran, K. P. Gummadi, and P. Loiseau. June 2021. (Technical report)

  * •

“(Mis)Information Dissemination in WhatsApp: Gathering, Analyzing and
Countermeasures”. G. Resende, P. Melo, H. Sousa, J. Messias, M. Vasconcelos,
J. Almeida, and F. Benevenuto. In Proceedings of the 28${}^{\textrm{th}}$ Web
Conference (WWW), San Francisco, USA, May 2019.

  * •

“WhatsApp Monitor: A Fact-Checking System for WhatsApp”. P. Melo, J. Messias,
G. Resende, K. Garimella, J. Almeida, and F. Benevenuto. In Proceedings of the
13${}^{\textrm{th}}$ International AAAI Conference on Web and Social Media
(ICWSM), Munich, Germany, June 2019.

  * •

“Search Bias Quantification: Investigating Political Bias in Social Media and
Web Search”. J. Kulshrestha, M. Eslami, J. Messias, M. B. Zafar, S. Ghosh, K.
P. Gummadi, and K. Karahalios. In Information Retrieval Journal, Springer.
Volume 22, Issue 1-2, April 2019.

  * •

“On Microtargeting Socially Divisive Ads: A Case Study of Russia-Linked Ad
Campaigns on Facebook”. F. N. Ribeiro, K. Saha, M. Babaei, L. Henrique, J.
Messias, F. Benevenuto, O. Goga, K. P. Gummadi, and E. M. Redmiles. In
Proceedings of the Conference on Fairness, Accountability, and Transparency
(FAT*), Atlanta, Georgia. January 2019.

I dedicate my thesis to the following people who have played an important role
in my life: my wife Aline, my father J. Missias Jota Missias, (2021), my
mother Varlene, and my brothers Joarlens and Jeanderson.

## Acknowledgements

I would like to express my gratitude to my advisor, Krishna P. Gummadi, for
his invaluable feedback and unwavering support throughout my PhD journey. I am
also deeply thankful to Balakrishnan Chandrasekaran and Patrick Loiseau for
their constructive insights and encouragement in my studies. I must also
extend my appreciation to my previous advisor, Fabrício Benevenuto, whose
consistent guidance and support carried me through this PhD journey.

Working alongside remarkable individuals from our Networked Systems group has
been a privilege. I would like to thank Ayan Majumdar, Abhisek Dash, Camila
Kolling, David Miller, Junaid Ali, Sepehr Mousavi, Till Speicher, Vabuk
Pahari, Vedant Nanda, Nina Grgić-Hlača, and many others who have made an
impact in my PhD journey.

I extend my thanks to the exceptional research assistants at MPI-SWS, who
enthusiastically celebrated every milestone in my doctoral studies. A special
mention goes to Mohamed Alzayat, whose feedback and collaboration were
instrumental as I embarked on my research topics. I am also grateful to Ahana
Ghosh, Andi Nika, Andrea Borgarelli, Angelica Goetzen, Chao Wen, Debasmita
Lohar, George Tzannetos, Heiko Becker, Jan-Oliver Kaiser, Lennard Gäher,
Matheus Stolet, Michael Sammler, Mihir Vahanwala, Nils Müller, Oshrat Ayalon,
Pierfrancesco Ingo, Ralf Jung, Rati Devidze, Roberta De Viti, Victor Alexandru
Padurean, Vaastav Anand, and many others for their steadfast support.

I am grateful for the vibrant interactions I had with interns who shared and
discussed intriguing research ideas, with a special shoutout to Aleksa
Sukovic, Ani Saxena, Ana-Andreea Stoica, Baltasar Dinis, Barbara Gomes, Daniel
Kansaon, Diogo Antunues, Isadora Salles, Ignacio Tiraboschi, Lucas Costa De
Lima, Maria Petrisor, Pedro Las-Casas, Ruchit Rawal, Sapana Chaudhary, and
many others.

I am thankful to all MPI-SWS staff, in particular, Annika Meiser, Carina
Schmitt, Christian Klein, Claudia Richter, Gretchen Gravelle, Krista Ames,
Maria-Louise Albrecht, Rose Hoberman, and Sarah Naujoks for their sincere
efforts and help during my PhD studies.

My appreciation extends to my wife Aline for her unwavering love and support
throughout this journey. I also want to extend my thanks to my father, Jota
Missias, my mother, Varlene, and my brothers, Joarlens and Jeanderson, for
their unconditional support.

## Table of contents

######

  1. List of figures
  2. List of tables
  3. 1 Introduction
    1. 1.1 Overview of thesis contributions
      1. 1.1.1 Transaction prioritization norms Messias et al., (2021, 2020)
      2. 1.1.2 Transaction Prioritization and Contention Transparency Messias et al., 2023a
      3. 1.1.3 Decision-making power distribution for blockchain governance Messias et al., 2023b
    2. 1.2 Thesis outline
  4. 2 Background
    1. 2.1 Blockchains & smart contracts
    2. 2.2 Transaction prioritization norms
    3. 2.3 Transaction prioritization and contention transparency
    4. 2.4 Decentralized governance
      1. 2.4.1 Voting modalities
    5. 2.5 Blockchain Scalability with Layer 2.0 Solutions
  5. 3 Transaction Prioritization Norms
    1. 3.1 Methodology
      1. 3.1.1 Data set collection
      2. 3.1.2 Detecting accelerated transactions.
    2. 3.2 Analyzing norm adherence
      1. 3.2.1 Does transaction ordering matter?
      2. 3.2.2 Do miners follow the norms?
    3. 3.3 Investigating norm violations
      1. 3.3.1 Statistical test for differential prioritization
      2. 3.3.2 Self-interest transactions
      3. 3.3.3 Scam-payment transactions
    4. 3.4 Dark-fee transactions
      1. 3.4.1 Layer 2.0 transactions
    5. 3.5 Concluding remarks
  6. 4 Transaction Prioritization and Contention Transparency
    1. 4.1 Methodology
      1. 4.1.1 Data set collection
      2. 4.1.2 Bundling public transactions
      3. 4.1.3 Aggregated power of colluding miners
    2. 4.2 On contention transparency
      1. 4.2.1 The rise of private relay networks
      2. 4.2.2 Characterizing private relay networks
      3. 4.2.3 On preferential treatment of private transactions
    3. 4.3 On prioritization transparency
      1. 4.3.1 Prevalence of transaction bundling
      2. 4.3.2 Side channel (dark-fee) payments and transaction acceleration
    4. 4.4 Concluding remarks
  7. 5 Decentralized Governance
    1. 5.1 Methodology
      1. 5.1.1 Smart contract events.
      2. 5.1.2 Data set collection
      3. 5.1.3 Inferring wallet address ownership.
    2. 5.2 Attacks on governance
    3. 5.3 Compound’s governance
      1. 5.3.1 Control of governance tokens
      2. 5.3.2 Voting on governance proposals
      3. 5.3.3 Real-world decision-making using Compound governance
      4. 5.3.4 Voting patterns of delegates
    4. 5.4 Concluding remarks
  8. 6 Related Work
    1. 6.1 Transaction prioritization norms
    2. 6.2 Transaction prioritization and contention transparency
    3. 6.3 Decentralized governance
      1. 6.3.1 Decentralized governance and social contracts
      2. 6.3.2 Decentralized Autonomous Organizations (DAOs)
  9. 7 Discussion, Limitations & Future Work
    1. 7.1 Transaction ordering
    2. 7.2 Transaction transparency
    3. 7.3 Voting power distribution to amend smart contracts
  10. A Additional Analysis of Transactions Prioritization Norms
    1. A.1 Congestion in Mempool of data set $\mathcal{B}$
    2. A.2 Significance of transaction fees
    3. A.3 Transaction fee rates across mining pools
    4. A.4 On fee rates and congestion
    5. A.5 Child-Pays-For-Parent (CPFP) Transactions
    6. A.6 Miners’ behavior during the scam
    7. A.7 Transaction-acceleration fees
  11. B Additional analysis of transactions prioritization and contention transparency
    1. B.1 Ethereum private transaction experiment
    2. B.2 Liquidation with Chainlink oracle updates
    3. B.3 Hashing rates of mining pools
    4. B.4 Bitcoin transaction acceleration experiment
  12. C Additional Analysis of Distribution of Voting Power
    1. C.1 Compound proposals categorization
    2. C.2 Filtering events to construct our Compound data Set
    3. C.3 Inferring wallet addresses ownership
    4. C.4 Types of existing governance protocols
    5. C.5 How voters cast their votes
    6. C.6 Time until reaching the quorum in Compound

## List of figures

1.0in

######

  1. 1.1  CDF of the error in predicting where a transaction would be positioned or ordered within a block according to the greedy fee-rate-based norm. Bitcoin Core code shifted completely to the fee-rate-based norm starting April 2016: Transaction ordering in Bitcoin closely tracks the fee-rate-based norm from April 2016, but differs significantly from it prior to April 2016 when a different norm was in place.
  2. 1.2  The lifecycle of a Compound proposal lasts 7 days. After a proposal is created, it waits for 2 days before the 3-day voting period begins. Once the outcome of the election is decided, it takes 2 more days for the proposal to be executed and become part of the Compound Governance protocol. Proposals can also be cancelled at any time before they are executed.
  3. 2.1  Illustration of a blockchain consisting of three blocks, with an extimation generation and inclusion time approximately 10 minutes. It is important to note that every block, except for the Genesis block which is the initial block in the blockchain, also uses the hash of its preceding block to compute its own hash.
  4. 2.2  Volume of transactions issued and blocks mined as a function of time, showing that transactions have been issued at high rates for both (a) Bitcoin and (b) Ethereum blockchains.
  5. 3.1  Distribution of blocks mined and transactions confirmed by the top-20 MPOs in data sets $\mathcal{A}$, $\mathcal{B}$, and $\mathcal{C}$. Their combined normalized hash-rates account for 94.97%, 93.52%, and 98.08% of all blocks mined in data set $\mathcal{A}$, $\mathcal{B}$, and $\mathcal{C}$, respectively.
  6. 3.2  (a) Distributions of Mempool size in both data sets $\mathcal{A}$ and $\mathcal{B}$; and (b) the size Mempool in $\mathcal{A}$ as a function of time, both indicating that congestion is typical in Bitcoin.
  7. 3.3  (a) Distributions of delays until transaction inclusion show that a significant fraction of Bitcoin transactions experience at least 3 blocks (or approximately 30 minutes) of delay; Distributions of fee rates for (b) all transactions and (c) transactions (in $\mathcal{A}$) issued at different congestion levels clearly indicate that users incentivize miners through transaction fees.
  8. 3.4  Distributions of transaction-commit delays for different fee rates for transactions in $\mathcal{A}$; incentivizing miners via fee rates works well in practice.
  9. 3.5  There exists a non-trivial fraction of transaction pairs violating the norm across all snapshots, clearly indicating that miners do not adhere to the norm.
  10. 3.6  Position prediction error (PPE). (a) There are 52,974 (99.55%) blocks with at least one non-CPFP txs. The mean PPE is 2.65%, with an std of 2.89. 80% of all blocks has PPE less than 4.03%. (b) The PPEs of blocks mined by the top-6 MPOs according to their normalized hash rate.
  11. 3.7  (a) Distribution of the number of wallet addresses in data set $\mathcal{C}$ used by each of the top-20 MPOs to receive its block rewards; SlushPool and Poolin, for instance, used 56 and 23 distinct wallet addresses, respectively. (b) The counts of inferred MPO transactions; in total, 12,121 transactions were inferred as MPOs’ transactions, which corresponds to 0.011% of the total issued transactions recorded in the Bitcoin blockchain. Poolin has the majority with 2232 (18.41%), followed by Okex with 2089 (17.24%) and Huobi with 1666 (13.74%) transactions. BitDeer and Buffett have the same wallet address as BTC.com and Lubian.com, respectively. We count the addresses of the former as belonging to the latter.
  12. 3.8  (a) Distribution of the number of reports per month. (b) USA is the country with more reports accounting for 27.6% of all reports available followed by UK and Canada.
  13. 3.9  Distribution of (a) blocks mined per each mining pool in comparison to the fraction of blocks that contains at least one scam transaction; and (b) transactions included by each mining pool in comparison to their share of scam transaction inclusion. BTC.com included 20.09% out of the 6511 scam transactions in 2018.
  14. 3.10  Cumulative distribution function for (a) transaction position percentile: 84.30% of Omni transactions were positioned right at the top of their respective blocks. This means they were the very first transactions to be included in those blocks; (b) comparison of Omni transfers and Bitcoin value transfers: The amount transferred in Omni to the corresponding value in Bitcoin for accelerated transactions was 259.97 times higher than the value announced in the Bitcoin blockchain.
  15. 3.11  Comparison between the value transferred (in USD) in accelerated Omni transactions (shown in the top red color) and the values from the Bitcoin blockchain (in the bottom black color) for transactions included in block 550,912. Each edge in the graph corresponds to a single BTC transaction. Transaction values available in the Bitcoin blockchain appear to be relatively low. However, in contrast, these transactions in the Omni Layer are notably high-value transactions. Nodes in blue indicate receivers, while nodes in red indicate senders.
  16. 4.1  Blocks mined and transactions confirmed in (a) Bitcoin and (b) Ethereum by the top-20 mining pools; “Others” consolidates the remaining mining pools.
  17. 4.2  Distribution of (a) blocks with at least one Flashbots bundle; and (b) bundle of transactions per block, per mining pool. Ethermine included 27.05% of all blocks with a Flashbot bundle and 26.63% of all Flashbots bundles, while mining around 28.05% and 31.11% of all blocks and transactions, respectively.
  18. 4.3  Difference between the actual max-priority fee of public transactions and Flashbots bundles; bundles typically offer a larger effective fee to the miners.
  19. 4.4  Profits of liquidators in (a) AAVE and in (b) Compound. Liquidations bundled with Chainlink updates generally provide higher profits.
  20. 4.5  Blocks with accelerated transactions (with SPPE $\geq 99\%$) are quite common among the top 15 mining pools. In Bitcoin, the mining pools with a high percentage of such blocks are ViaBTC (41.36%), 1THash & 58COIN (17.58%), SlushPool (11.58%), BTC.com (10.03%), and F2Pool (9.63%).
  21. 5.1  Overview of the data collection methodology and analysis.
  22. 5.2  Amount of COMP tokens (in millions) in circulation and delegated overtime. Compound tokens have been released to the public since June 15, 2020.
  23. 5.3  Distribution of the top 15 COMP tokens holders. Together, these accounts hold 56.02% (5.6 million) out of 10 million COMP tokens.
  24. 5.4  Distribution of the top 15 COMP tokens holders (in circulation). These accounts hold 43.83% (3.2 million) out of 7.3 million COMP tokens in circulation.
  25. 5.5  Cumulative distribution of the fraction of COMP tokens held per account. The 10 million tokens available are shared among 210,573 accounts (in grey). The dashed green line shows the distribution of the fraction of 7.3 million (73.57%) COMP tokens in circulation held by 210,570 accounts. The 2.6 million locked tokens are held by 3 accounts (in dotted red). Finally, the dash-dotted blue line shows the delegated tokens’ distribution where 10 out of 4186 accounts have 57.86% of all delegated COMP tokens available.
  26. 5.6  Distribution of the top 15 delegated COMP tokens per accounts on November 7, 2022. These addresses have 63.56% of all 2.7 million delegated tokens.
  27. 5.7  Monthly number of Compound proposals created overtime and their respective outcomes (executed, defeated, or cancelled). Proposals are created, on average, every 6.95 days.
  28. 5.8  Compound’s voting participation per proposal in terms of delegated tokens used from all delegated tokens available. Proposals are indicated either as executed (in green), defeated (in red), or cancelled (in blue).
  29. 5.9  Compound’s distribution of voting power by voter per proposal. For better illustration, we consider a cutoff of 0.001 votes.
  30. 5.10  Voting cost distribution per proposal. On average, casting a vote costs $7.88 with a std. of $22.29.
  31. 5.11  Voting cost distribution normalized per the voting power. We consider a cutoff of $10^{-6}$ votes for better illustration.
  32. 5.12  Percentage of in-favor (in green), against (in red), and abstain (in blue) votes for each proposal. A total of 15 (11.28%) proposals were defeated, and vertical lines represent 17 (12.78%) cancelled proposals.
  33. 5.13  Summary of the outcome of 133 Compound proposals at each stage of their lifecycle. There are 101 proposals executed (in green), 15 defeated (in red), and 17 cancelled (in blue).
  34. 5.14  Distribution of the number of days it takes voters to cast their votes.
  35. 5.15  Cumulative distribution function of the time it takes voters to cast their votes since the voting period began considering: (a) All proposals; (b) Executed proposals; (c) Defeated proposals; and (d) Cancelled proposals.
  36. 5.16  Votes cast by the top-15 voters. In-favor votes are in green, against in red, and abstain in blue color.
  37. 5.17  Cosine similarity of the top-15 voters voting in-favor a proposal.
  38. A.1  Mempool size from $\mathcal{B}$ as a function of time.
  39. A.2  Distributions of fee rates for transactions committed by the top-5 mining pools in data set $\mathcal{A}$.
  40. A.3  Distribution of fee rates for transactions in data set $\mathcal{B}$ issued at different congestion levels clearly indicate that users incentivize miners through transaction fees.
  41. A.4  Distributions of transaction-commit delays in data set $\mathcal{B}$ for different transaction fee rates.
  42. A.5  Distribution of blocks mined and transactions confirmed by different MPOs during the Twitter Scam attack from July 14${}^{\textrm{th}}$ to August 9${}^{\textrm{th}}$, 2020.
  43. A.6  Fee price comparison between the transaction fee and the acceleration services from an snapshot of our Mempool on November 24${}^{\textrm{th}}$, 2020. Acceleration service provided by BTC.com is on average 566.3 times higher (4734.67 of std.) and on median 116.64 times higher than the Bitcoin transaction fees. The minimum is 0.54, the 25-perc is 51.64, and the 75-perc and the maximum are 351.8 and 428,800, respectively.
  44. B.1  Monthly Bitcoin hash rate over the 3-year period.
  45. B.2  Weekly Ethereum hash rate from Sept $8^{\textrm{th}}$, 2021, to Jun $30^{\textrm{th}}$, 2022.
  46. B.3  Active vs. others experiment: Bitcoin mining pools in the active experiment (i.e., mining pools that included transactions accelerated by ourselves) increased their hash rate in 2020. Together, they accounted for more than $55\%$ of the overall hash rate. The plot shows the weekly average percentage of the mining pool’s hash-rate over 3 years.
  47. B.4  Passive + active vs. others experiment: Bitcoin mining pools in the active experiment (i.e., mining pools that included transactions accelerated by ourselves) and passive experiment (mining pools that included transactions inferred to be accelerated using the BTC.com API) increased their hash rate in 2020. The plot shows the weekly average percentage of the mining pool’s hash-rate over 3 years.
  48. B.5  The plot shows the monthly average percentage of accelerated Bitcoin transactions inclusion by each mining pool over 3 years. Transaction acceleration services or simply Front-running as a Services (FRaaS) are becoming popular across all mining pools.
  49. C.1  Categorization of executed proposals. Most of the proposals (60.4%) are related to “Parameter Change”. We also show the importance level (low in green, medium in blue, high in red, and very high in purple color) for each proposal according to Messari Messari, (2023).
  50. C.2  Compound proposals typically reach the quorum after 1.64 days on average.
  51. C.3  Cumulative voting power distribution of the top-10 Compound voters per proposal. On average, proposals required 2.84 voters (std. of 0.97) to reach at least 50% of their total votes. The median was 3 voters, with a range of 1 to 5 votes. This indicates a concentrated amount of voting power. The subtitles indicate the proposal ID and outcome (“E” for executed, “D” for defeated, and “C” for cancelled).
  52. C.4  Voting delays for all votes cast per proposal in chronological order of vote. On average, voters took 1.4 days (with a standard deviation of 0.95 and a median of 1.34 days) to cast their votes after the voting period began. The subtitles indicate the proposal ID and outcome (“E” for executed, “D” for defeated, and “C” for cancelled).

## List of tables

######

  1. 3.1 Bitcoin data sets ($\mathcal{A}$ and $\mathcal{B}$) used for testing miners’ adherence to transaction-prioritization norms and ($\mathcal{C}$) for investigating the behaviour of miners with respect to transaction acceleration. Child-pays-for-parent (CPFP) transactions are transactions that depend on other transactions to be included into a block.
  2. 3.2 Differential prioritization of self-interest transactions.
  3. 3.3 Differential prioritization of scam-payment transactions
  4. 3.4 Scam types and their occurrences in wallets and transactions.
  5. 3.5 Top-20 most used wallets for scam payments.
  6. 3.6 [Data set $\mathcal{C}$] For an SPPE $\geq$ 99%, we observe that 64.98% of BTC.com transactions were accelerated; the fourth column values are derived by dividing the values in the second with those in the third. The number of accelerated transactions decreases to 18.12% for an SPPE $\geq$ 90% and to 1.06% for an SPPE $\geq$ 50%.
  7. 4.1 Bitcoin and Ethereum data sets ($\mathcal{D}$ and $\mathcal{E}$) used to evaluate the lack of contention and prioritization transparency.
  8. 4.2 There are $2231051$ ($67.92$%) unique Flashbots bundles, and $3076760$ ($44.35$%) transactions, that called the following decentralized exchange contracts in Ethereum: 0x Protocol, Balancer, Bancor, Curve, SushiSwap, Uniswap V1, or V3. Note that a single transaction or bundle might call one or more contracts.
  9. 4.3 Accelerated transactions have fewer delays and are included at the top of the block, i.e., at higher positions compared to non-accelerated transactions.
  10. 4.4 If we rank the miners who confirmed the accelerated transactions based on their daily, weekly, and monthly hash rate power, at the time these experiments were conducted, the combined hash power of these mining pools exceeds 55% of the Bitcoin’s total hashing power.
  11. 5.1 Summary of events related to the Compound (COMP) token that we gathered from the Ethereum blockchain.
  12. 5.2 Summary of events related to the Compound Governor contracts recorded on the Ethereum blockchain.
  13. A.1 Miners’ relative revenue from transaction fees (expressed as a percentage of the total revenue) across all blocks mined from 2016 until the end of 2020.
  14. B.1 We conducted 4 active experiments in Ethereum by simultaneously accelerating transactions privately and publicly via Taichi Network. Private transactions were included only by Spark Pool and Babel Pool. If we rank these mining pools according to their hash-rate, they account for 27.72% of the total Ethereum hash-rate.
  15. B.2 We conduct 10 transaction acceleration experiments in Bitcoin. If we rank the miners whose included these transactions based on their daily hash-rate power as (D) and weekly hash-rate power as (W), together these mining pools corresponds to a hash-rate power of (D: 55.2%; W: 56%).
  16. C.1 A comparison of voting mechanisms in decentralized governance protocols such as AAVE AAVE, (2023), Balancer Balancer.fi, (2023), Compound Leshner and Hayes, (2019), Convex Finance Convex, 2023a , Curve Curve, (2023), Maker MakerDAO, (2023), and Uniswap Adams et al., (2021). SC stands for smart contract.

##  Chapter 1 Introduction

Blockchains have the potential to transform traditional and centralized
sectors of great societal importance, such as banking and finance Daian et
al., (2020); Adams et al., (2021); Qin et al., (2021); Perez et al., (2021).
They provide a secure means of ensuring compliance via contracts (i.e.,
established agreements) and tamper-proof mechanisms, especially in situations
where participants cannot trust each other Nakamoto, (2008); Wood et al.,
(2014); Van Saberhagen, (2013); Sasson et al., (2014). As a result, there are
many blockchains available such as Bitcoin Nakamoto, (2008), Ethereum Wood et
al., (2014), Polkadot Wood, (2016), Zcash Sasson et al., (2014), Monero Van
Saberhagen, (2013), among others. Bitcoin and Ethereum stand out as the most
widely used blockchains, with market capitalization surpassing $536.72B and
$228.57B as of May 2023 CoinMarketCap, (2023), respectively. In addition,
blockchains have not only been used to implement cryptocurrencies, but are
increasingly being adopted across a wide range of domains including insurance
Martin Ruubel, (2018), education Philipp Schmidt, (2015), healthcare Ekblaw
and Azaria, (2017), supply-chain management Provenance, (2015); Robert
Hackett, (2017), decentralized governance Leshner and Hayes, (2019); Adams et
al., (2021); MakerDAO, (2023), and decentralized finance (DeFi) applications
through smart contracts such as exchanges Daian et al., (2020); Uniswap,
(2023), lending Qin et al., (2021); Perez et al., (2021), and auctions
Ethereum Foundation, 2023c .

In the blockchain space multiple parties interact with each other. These
include: (i) transaction issuers who are responsible for issuing transactions
via interactions with the blockchain and its applications through smart
contracts; (ii) miners or block validators who ensure the validity of
forthcoming information or blocks for inclusion within all its transactions;
and (iii) smart contract applications that are software programs running atop
a blockchain, capable of executing predetermined actions, creating or
transferring tokens, enabling voting for smart contract amendments, etc. In
any real-world scenario involving a diverse group of individuals with varying
roles, establishing a foundation of trust and fairness becomes paramount to
ensure that no one can take advantage of others.

Unlike the past, where interactions occurred mostly between individuals who
knew and trusted each other, the rise of blockchain has enabled interactions
within a decentralized system, devoid of inherent trust. However, in such a
trustless environment, the potential for unfairness arises. One of the
captivating aspects of blockchain systems is the interaction among
participants who are strangers to each other, lacking pre-established trust.
This raises questions about whether interactions are conducted fairly and what
fairness concerns exist. For instance, in this thesis we focus on three
primary unfairness issues: (i) Transaction ordering; (ii) Transaction
transparency; and (iii) Fair distribution of voting power for smart contract
amendments.

Fairness related to transaction ordering. The sequence in which transactions
are processed is crucial, as everyone seeks timely processing. Ensuring
fairness in this ordering presents challenges. For instance, how do we know
that the ordering is fair?

In other words, noticeably absent from Bitcoin, Ethereum, and other
decentralized blockchains is the requirement of any a priori trust between the
users issuing transactions (i.e., registers persisted in the blockchain), the
miners confirming transactions, and the peer-to-peer (P2P) nodes maintaining
the blockchain. Despite their widespread use in ordering critical applications
McCorry et al., (2017); Daian et al., (2020); Pilkington, (2016); Kharif,
(2017); Uniswap, (2023); Perez et al., (2021), blockchain protocols formally
specify neither the manner by which miners should select transactions for
inclusion in a new block from the set of all available transactions, nor the
order in which they should be included in the block. While informal
conventions or norms for prioritizing transactions exist, to our knowledge,
before us no one has systematically verified if these norms were being
followed by miners in practice Messias et al., (2020, 2021); Messias et al.,
2023a .

Studying this problem has significant implications for both blockchain users
and miners. Specifically, when setting fees for their transactions,
transaction issuers (i.e., through their wallet software) assume that the fees
offered by all their competing transactions are fully transparent—our findings
contradict this assumption. Similarly, when transactions offer different
confirmation fees to different miners, it raises significant unfairness
concerns with respect to the order in which these transactions are included.
We also show that mining pools collude when prioritizing self-interested
transactions for inclusion which can exacerbates the growing concerns about
the concentration of hash rates amongst a few miners in proof-of-work
blockchains (PoW) Gervais et al., (2016); Bahack, (2013).

Fairness related to transaction transparency. Assumptions dictate that all
participants can observe public transactions. This transparency impacts
transaction prioritization and fee-setting. However, reality often diverges,
leading to concerns about fairness in transaction transparency.

For instance, the lack of transparency in blockchains arises from genuine
concerns of transactions issuers, which cannot be overlooked. One significant
concern is the risk of transactions being front-run by bots Daian et al.,
(2020); Eskandari et al., (2020); Torres et al., (2021); Weintraub et al.,
(2022), which creates the need for transaction privacy. Mining pools that
address this need also facilitate, unsurprisingly, off-chain payments via
which transaction issuers can (privately) incentivize the miners BTC.com,
(2022); Messias et al., (2021); ViaBTC, (2022). We consider these developments
as natural and logical steps in the evolution of blockchains and back our
assertions with empirical observations. In contrast to prior research Daian et
al., (2020); Strehle and Ante, (2020), we argue that the fundamental threat to
blockchain stability lies in the opacity of the overall fees issued by
transaction issuers. Most wallet software and crypto-exchanges currently rely
on reconstructing the current public Mempool state to suggest an appropriate
fee to transaction issuers. As a result, transaction issuers cannot precisely
determine the fee required to ensure the inclusion of their transaction in the
next block. Consequently, miners can overcharge them, as the “real” fees are
opaque to the rest of the network Weintraub et al., (2022).

Fairness related to voting power to amend smart contracts. Smart contracts,
serving as trust-enforcing mechanisms, entail participants’ agreement with
stipulated rules. However, as these smart contracts can be upgraded (or
changed) it raises the question of who possesses the authority to modify them.

Put differently, blockchains face challenges related to decentralized
decision-making processes for amending smart contracts. For example,
blockchains have been explored by many prior works who studied different types
of security vulnerabilities that arise from incorrect implementations or
unintended (or undesired) executions of smart contracts over blockchains,
particularly in the context of DeFi applications Mike Dalton, (2022); Qin et
al., (2021); Weintraub et al., (2022); Torres et al., (2021); Daian et al.,
(2020). However, few studies, if any, focused, however, on vulnerabilities
that may originate in the design of the procedures to amend, i.e., change,
smart contracts through governance protocols, and/or stem from the execution
of these procedures in practice. These governance protocols intend to
eliminate (or at least minimize) centralized decision-making in blockchains.
Their effectiveness in achieving that goal can, however, be compromised
depending on how the tokens (i.e., voting power—typically one token equals one
vote) are distributed which can lead to voting concentration. Such
concentration poses a threat to the overall governance of smart contract
applications in blockchains leading, for example, to governance attacks Mike
Dalton, (2022).

Therefore, in this thesis, we also provide an in-depth analysis of the voting
patterns, delegation practices, and outcomes of proposals in one of the widely
used governance protocols: Compound Leshner and Hayes, (2019); Compound Labs,
Inc., 2022a . Since Compound records the votes cast transparently on a
blockchain (i.e., it uses on-chain voting), we conduct measurements studies to
analyze the extent to which this voting is decentralized, i.e., how small or
large are the set of voters that determine the outcomes for the amendments.

It is important to acknowledge that our focus on these fairness concerns does
not imply exclusivity. Additional concerns exist, such as fairness in
compensating miners proportionately to their contributions. Nonetheless, in
this thesis, we focus on the three aforementioned fairness concerns: (i)
Transaction ordering; (ii) Transaction transparency; and (iii) Fair
distribution of voting power for smart contract amendments.

###  1.1 Overview of thesis contributions

This thesis aims to address the fairness challenges mentioned above. We
outline our research contributions in pursuit of this objective below.

####  1.1.1 Transaction prioritization norms Messias et al., (2021, 2020)

The conventional wisdom today is that many miners follow the prioritization
norms, implicitly, by using widely shared blockchain software like the Bitcoin
Core bitcoin.org, (2023); Coin Dance, (2021). In Bitcoin, the presumed “norm”
is that miners prioritize a transaction for inclusion based on its offered fee
rate or fee-per-byte, which is the transaction’s fee divided by the
transaction’s size in bytes. We show evidence of this presumed norm in Figure
1.1. The norm is also justified as “incentive compatible” because miners
wanting to maximize their rewards, i.e., fees collected from all transactions
packed into a size-limited block, would be incentivized to include
preferentially transactions with higher fee rates. Assuming that miners follow
this norm, Bitcoin users are issued a crucial recommendation: To accelerate
the confirmation of a transaction, particularly during periods of congestion,
they should increase the transaction fees. We show that miners are, however,
free to deviate from this norm and such norm violations cause irreparable
economic harm to users.

Figure 1.1:  CDF of the error in predicting where a transaction would be
positioned or ordered within a block according to the greedy fee-rate-based
norm. Bitcoin Core code shifted completely to the fee-rate-based norm starting
April 2016: Transaction ordering in Bitcoin closely tracks the fee-rate-based
norm from April 2016, but differs significantly from it prior to April 2016
when a different norm was in place.

We summarize our contributions as follows.

$\blacktriangleright$ To quantify the deviation from the norm, we propose two
measures that we call signed position prediction error (SPPE) and position
prediction error (PPE). These measures allow us to quantify the transaction
deviation (or acceleration) for all transactions in block. It can also be
applied to any blockchain that order transactions based on fees-incentive.

$\blacktriangleright$ We perform an extensive empirical audit of the miners’
behavior to check whether they conform to the norms. At a high-level, we find
that transactions are indeed primarily prioritized according to the assumed
norms. We also, nevertheless, offer evidence of a non-trivial fraction of
priority-norm violations amongst confirmed transactions. An in-depth
investigation of these norm violations uncovered many highly troubling
misbehavior by miners.

$\blacktriangleright$ Multiple large mining pools tend to selfishly prioritize
transactions in which they have a vested interest; e.g., transactions in which
payments are made from or to wallets owned by the mining pool operators. Some
even collude with other large mining pools to prioritize their transactions.

$\blacktriangleright$ Many large mining pools accept additional dark (opaque)
fees to accelerate transactions via non-public side-channels (e.g., their
websites). Such dark-fee transactions violate an important, but unstated
assumption in blockchains that confirmation fees offered by transactions are
transparent and equal to all miners.

$\blacktriangleright$ We release the data sets and the scripts used in our
analyses to facilitate others to reproduce our results Messias, 2023b .

####  1.1.2 Transaction Prioritization and Contention Transparency Messias et
al., 2023a

In the context of the lack of contention transparency, not all transactions
are publicly broadcasted. Instead, users can submit transactions to a subset
of miners or mining pools through private channels or _relays_ that are not
visible to the public. In this case, transactions remain private to the relay
until they are committed into a block. Additionally, users may choose to
submit their transactions exclusively to a particular mining pool that
guarantees a fast commit time. This thesis aims to shed light on the growing
prevalence of private mining practices, where transactions are submitted to
only a subset of the miners. Furthermore, it analyzes the distinct
characteristics of these private transactions.

Moreover, with the lack of prioritization transparency, the fees offered by a
transaction can be significantly higher than what is publicly declared. For
example, a transaction can privately offer additional fees to a miner in order
to “accelerate” its inclusion in a block. Many such transaction-accelerator
(or _front-running as a service (FRaaS)_) platforms exist for Bitcoin BTC.com,
(2022); ViaBTC, (2022) and Ethereum Eskandari et al., (2020); Flashbots, 2022b
; SparkPool, (2021); Strehle and Ante, (2020). Furthermore, the same
transaction can offer different fees to different mining pools through their
relays. The existence of these hidden or dark-fees can undermine the
reliability of any fee prediction: Transaction issuers may end up paying
considerably higher fees without receiving proportional or any reduction in
commit delays. This thesis aims to characterize the prevalence of such dark-
fee transactions and analyze the most popular private relay network available
in Ethereum, Flashbots Flashbots, 2022b . We also conduct active experiments
in both Bitcoin and Ethereum to validate our assumptions regarding the
prioritization transparency.

In addition to demonstrating the non-uniformity of transaction fees across
miners, we argue that, given the lack of contention transparency, the lack of
prioritization transparency may become even more widespread in the future.

We summarize our contributions as follows.

$\blacktriangleright$ We provide a comprehensive characterization of the lack
of contention transparency in both Bitcoin and Ethereum. Our analysis reveals
the widespread use of private channels or relay networks to submit
transactions directly to a subset of miners. This practice has the potential
to undermine prioritization transparency, as transaction issuers may not be
able to estimate the appropriate fees once none of which is publicly visible.

$\blacktriangleright$ We investigate the prevalence of private transaction
fees, with a particular focus on Flashbots bundles in Ethereum. Our findings
indicate that Flashbots bundles represent a significant portion ($52.11$%) of
all Ethereum blocks. This lack of prioritization transparency may enable
miners to overcharge users when they send their transactions privately.

$\blacktriangleright$ We investigate whether public transactions are bundled
together with private transactions using the Flashbots private relay to
exploit arbitrage opportunities through Maximal Extractable Value (MEV).
Interestingly, we find that the public transactions within these bundles are,
for example, associated with oracle111Decentralized Oracle Networks facilitate
off-chain data access for blockchains, including exchanges prices, weather
forecast, and more Breidenbach et al., (2021). Typically, blockchain
applications rely on these oracles to gather information they need. updates,
specifically involving the adjustment of prices for particular token pairs.
This is made possible by the sequential execution of transactions within the
bundle by miners. Consequently, the transaction that is executed right after
the oracle update gain immediate access to the updated price information as
soon as it is recorded on the blockchain.

$\blacktriangleright$ We demonstrate evidence of collusion among Bitcoin
miners, collectively possessing more than $50$% of the network’s total hashing
power, particularly concerning the inclusion of dark-fees transactions.

$\blacktriangleright$ To promote transparency and facilitate the scientific
reproducibility of our results, we publicly release our data sets and scripts
used in our analysis Messias, 2023b .

####  1.1.3 Decision-making power distribution for blockchain governance
Messias et al., 2023b

This thesis also provides an in-depth analysis of the voting patterns,
delegation practices, and outcomes of proposals in one of the widely used
governance protocols: Compound Leshner and Hayes, (2019); Compound Labs, Inc.,
2022a . Since Compound records the votes cast transparently on a blockchain
(i.e., uses on-chain voting), we conducted measurements studies to analyze the
extent to which this voting is decentralized, i.e., how small or large are the
set of voters that determine the outcomes for the amendments. Our goal is to
thoroughly examine this protocol to better understand how its governance
mechanism operates and identify potential areas for improvement.

Figure 1.2:  The lifecycle of a Compound proposal lasts 7 days. After a
proposal is created, it waits for 2 days before the 3-day voting period
begins. Once the outcome of the election is decided, it takes 2 more days for
the proposal to be executed and become part of the Compound Governance
protocol. Proposals can also be cancelled at any time before they are
executed.

Compound regulates its voting process via the Compound (COMP) token, an ERC-20
asset, as follows. First, it allows token holders to participate in governance
by proposing and voting on changes to the protocol through an on-chain voting
mechanism where voting power of a user is proportional to the amount of
delegated tokens held by them—one token equals one vote. Second, it permits
its holders to delegate their tokens to other users, enabling users (who do
not wish to exercise their voting rights) to delegate their voting power to
others. The protocol essentially supports a form of liquid democracy that
combines direct democracy and representative democracy, where voters can
delegate their voting power to trusted representatives Behrens, (2017);
Carroll, (1884); Blum and Zuber, (2016). Some protocol changes that token
holders can propose and vote on include adjustments to the borrowing and
lending rates, changes to how new tokens are distributed, and changes to the
parameters of the voting process. They can also change the duration of the
proposal’s life cycle (per Figure 1.2, currently taking on average 7 days) and
other aspects of the protocol. To incentivize participation in token lending
and borrowing through the protocol, Compound distributes $1234$ COMP tokens
daily to users and applications in various markets (e.g., ETH, DAI, and USDC),
in proportion to the amount that they lend or borrow Compound Labs, Inc.,
2022c .

We summarize our contributions as follows.

$\blacktriangleright$ We characterize the Compound protocol’s on-chain voting
process, showing that it is active and regularly used, with a steady flow of
proposals. The majority of the proposals receive significant support: on
average, $89.39$% of votes are in favor.

$\blacktriangleright$ We reveal a substantial variation in voting costs, from
$$0.03$ to $$294.02$, with an average of $$7.88$.222All costs are in US
dollars, taking into account the exchange rate at the time of casting the
vote. If we normalize the costs per vote by the count of tokens held by users,
we obtain an average cost per vote unit of $$358.54$. Voting costs on Compound
can, hence, be unfairly expensive for small token holders, which has fairness
implications for the decision-making process.

$\blacktriangleright$ We show that a small group of 10 voters holds a
significant amount of voting power (57.86% of all tokens) and that proposals
only required an average of $2.84$ voters to obtain at least $50$% of the
votes. These observations strongly suggest that the voting outcomes in
Compound may not reflect the preferences of the broader community.

$\blacktriangleright$ We also discover potential voting coalitions among the
top voters, which could further exacerbate concerns of voting concentration.

$\blacktriangleright$ To foster reproducible research and inspire
investigations into other aspects of governance protocols, we share our
scripts and data sets in a GitHub repository Messias, 2023a .

###  1.2 Thesis outline

In summary, this thesis addresses three important fairness concerns. First is
the transaction ordering where we examine the prioritization of transactions
by auditing the order in which they are included by miners. We investigate
whether miners adhere to the existing norms or widely accepted practices in
this regard. Second, is the transaction transparency where we explore whether
miners ensure transparency in terms of transaction prioritization and
transaction contention (i.e., the transaction and its content is accessible by
all miners), ensuring equal access for all participants. Finally, is the fair
distribution of voting power for smart contract amendments where we delve into
the distribution of voting power in decentralized governance protocols, with a
particular focus on Compound. Both of these concerns are crucial for
establishing a fair blockchain ecosystem.

Specifically, this thesis is organized as follows:

$\blacktriangleright$ In Chapter 2, we begin by presenting the background of
blockchains and smart contracts. Next, we delve into the background of
transaction prioritization norms. Then, we discuss the background of
transaction prioritization and contention transparency. Finally, we explore
the background of decentralized governance protocols used for amending smart
contracts.

$\blacktriangleright$ In Chapter 3, we perform an audit of miners’
prioritization norms and evaluate the degree to which they comply with
commonly accepted prioritization assumptions. Our findings reveal that miners
tend to prioritize transactions based on self-interest, including their own
transactions or those from friendly mining pools. Additionally, we highlight
the presence of acceleration services provided by miners, enabling off-chain
payments to expedite transactions. Unfortunately, the fees associated with
these services are dark or opaque to other participants, making it challenging
for them to estimate appropriate fees for timely transaction inclusion.
Finally, we propose two metrics for verifying transaction ordering misposition
within a block. These metrics play a crucial role in determining whether
miners adhere to the assumed norms and can be generalized to other
blockchains.

$\blacktriangleright$ In Chapter 4, we conduct a data-driven analysis focused
on the prioritization of dark-fees payments by miners. Our results reveal the
existence and prevalence of private relay networks (e.g., Flashbots), which
allow transaction issuers to privately send their transactions to miners,
keeping them hidden from other participants. To assess the level of
prioritization provided by miners, we performed two active experiments, where
we accelerated the inclusion of transactions by offering dark-fee payments to
miners. We discovered evidence of potential collusion among mining pools,
where their combined hash rate accounted for over $50$% of the network’s hash
rate.

$\blacktriangleright$ In Chapter 5, we conduct an in-depth audit of governance
protocols, with a specific focus on Compound, to evaluate the extent to which
they have succeeded in achieving their primary goal of decentralizing the
decision-making process for amending smart contracts. Our analysis reveals
that this goal may not have been fully achieved, as we observe a concerning
concentration of voting power among a small number of participants, along with
the existence of voting coalitions formed by powerful voters. This
concentration stands in contrast to the fundamental objective of decentralized
governance protocols, which aims to mitigate centralization in the decision-
making process.

$\blacktriangleright$ In Chapter 6, we review the works in the literature that
are relevant to this thesis.

$\blacktriangleright$ In Chapter 7, we present a detailed discussion of our
work and its limitations. Additionally, we explore potential directions for
future work.

##  Chapter 2 Background

In this chapter, we provide the necessary background on blockchains and smart
contracts. We then present the context for transaction prioritization norms,
followed by transaction prioritization and contention transparency. Next, we
present the background information on decentralized governance. Lastly, we
introduce the background details concerning Layer 2.0 solutions aimed at
enhancing the scalability of blockchains.

###  2.1 Blockchains & smart contracts

A blockchain is a decentralized and distributed ledger of cryptographically
linked records of transactions stored in blocks. A block is a set of zero333As
miners can also mine a block without including any transaction on it, we refer
to those blocks as empty blocks. or more transactions. In the case of Bitcoin,
a block also includes a Coinbase transaction, responsible for transferring
rewards (or compensation for the miner’ efforts) to the miner’s wallet. These
blocks are interconnected, tracing back to the original (or “Genesis”) block.
Figure 2.1 presents an illustration of a blockchain with a block inclusion
rate of 10 minutes. The ledger is maintained and continually extended by the
blockchain participants by carrying out various functions. Transaction
issuers, for instance, issue transactions and share it with other participants
through a peer-to-peer (P2P) network. Such transactions are deemed unconfirmed
until they are added permanently to the blockchain. Some others, called
miners444Throughout this thesis, we use the terms miner, mining pool, mining
pool operator (MPO), and block proposer interchangeably. (in proof-of-work
blockchains) or block proposers (in proof-of-stake blockchains), bundle the
transactions into blocks for confirmation. They propose the new block over the
P2P network where others can verify it and, if successful, add to their copy
of the blockchain—thereby extending the ledger or chain of blocks. The miner
typically collects a reward in the form of newly minted coins as an incentive
for their contribution to the network along with the transactions fees
provided by the issuers. We use the term “fee” to refer generally to the
incentive offered by a user to miners for prioritizing the inclusion of their
transaction in a block, albeit its exact form may vary, e.g., fee rate (or
fee-per-byte) in Bitcoin and gas price in Ethereum555Ethereum recently
switched its consensus mechanism from proof-of-work to proof-of-stake with The
Merge hard fork deployed on September 15, 2022, at block number 15537394
Ethereum Foundation, 2022a ; Ethereum Foundation, 2022b .. To join a
blockchain, miners use a software implementation (along with the hardware)
which we refer as a _node_. A node allows a miner to receive broadcasts of
transactions and blocks from their peers, validate the data, and mine a block.
Nodes queue the unconfirmed transactions received via broadcasts in an in-
memory buffer, called the _Mempool_ , from where they are dequeued for
inclusion in a size-limited block. One can also configure the node to skip
mining and simply use it as an observer.

Figure 2.1:  Illustration of a blockchain consisting of three blocks, with an
extimation generation and inclusion time approximately 10 minutes. It is
important to note that every block, except for the Genesis block which is the
initial block in the blockchain, also uses the hash of its preceding block to
compute its own hash.

Some blockchains, such as Ethereum, allow for the execution of smart
contracts—contractual agreements encoded in software programs that run atop
the blockchain. Smart contracts are typically developed using Solidity, a
domain-specific programming language Solidity Team, (2023), and they can be
executed in the Ethereum Virtual Machine (EVM). Their implementations abide by
standards such as ERC-20 Ethereum Foundation, 2023a  and ERC-721 Ethereum
Foundation, 2023b  to ensure compatibility and interoperability among them.
These standards define, for instance, the key functions for creating and
implementing smart contracts for fungible tokens (e.g., Compound’s COMP token
Leshner and Hayes, (2019)) in the case of ERC-20 or non-fungible tokens (NFTs)
in the case of ERC-721.

###  2.2 Transaction prioritization norms

A crucial detail absent in the design of a blockchain per Nakamoto, (2008) is
any notion of a formal specification of transaction prioritization. Said
differently, Nakamoto’s design does not formally specify how miners should
select a set of candidate transactions for confirmation from all available
unconfirmed transactions. Notwithstanding this shortcoming, “norms” have
originated from miners’ use of a shared software implementation: For example,
in Bitcoin, miners predominantly use the Bitcoin Core bitcoin.org, (2023)
software for communicating with their peers (e.g., to advertise blocks and
learn about new unconfirmed transactions) and reaching a consensus regarding
the chain.

Of particular note in the popular Bitcoin core’s implementation is the
GetBlockTemplate (GBT) mining protocol, implemented by the Bitcoin community
around February 2012.666Even within mining pools, the widely used Stratum
protocol internally uses the GetBlockTemplate mechanism Braiins, 2021a .
GetBlockTemplate rank orders transactions based on the fee-per-byte (i.e.,
transaction fees normalized by the transaction’s size) metric Bitcoin Wiki,
2023a .

In Bitcoin, the term size, refers to _virtual_ size, each unit of which
corresponds to four _weight units_ as defined in the Bitcoin improvement
proposal BIP-141 Lombrozo et al., (2015). The size (or maximum capacity) of a
block is also limited to $1\text{\,}\mathrm{M}\mathrm{B}$ virtual size. The
predominant use of GBT (through the use of Bitcoin core) by miners coupled
with the fact that GBT is maintained by the Bitcoin community implicitly
establishes two norms. A third norm stems from a configuration parameter of
the Bitcoin core implementation. We now elucidate these three norms.

I. When mining a new block, miners select transactions for inclusion, from the
Mempool, based solely on their fee rates.

II. When constructing a block, miners order (place) higher fee rate
transactions before lower fee rate transactions.

III. Transactions with fee rate below a minimum threshold are ignored and
never committed to the blockchain.

The GBT protocol implementation in Bitcoin core is the source of the first two
norms. GBT’s rank ordering determines both which set of transactions are
selected for inclusion (from the Mempool) and in what order they are placed
within a block. GBT dictates that a transaction with higher fee-per-byte will
be selected before all other transactions with a lower fee-per-byte. It also
stipulates that within a block a transaction with the highest fee-per-byte
appears first, followed by next highest fee-per-byte, and so on.

The third norm stems from the fee-per-byte threshold configuration parameter.
Bitcoin core, by design, will not accept any transaction with fee rate below
this threshold, essentially filtering out low-fee-rate transactions from even
being accepted into the Mempool. The default (and recommended) value for this
configurable threshold is set to
$1\text{\,}\mathrm{s}\mathrm{a}\mathrm{t}{\mathrm{/}}\mathrm{B}$.777One
Bitcoin (BTC) is equal to $10^{8}$ satoshi (sat).

###  2.3 Transaction prioritization and contention transparency

(a) Bitcoin blockchain (b) Ethereum blockchain

Figure 2.2:  Volume of transactions issued and blocks mined as a function of
time, showing that transactions have been issued at high rates for both (a)
Bitcoin and (b) Ethereum blockchains.

The rate at which users issue transactions in permissionless blockchains,
e.g., Bitcoin Nakamoto, (2008) and Ethereum Wood et al., (2014), is often much
higher than the rate at which miners can include them in a block Easley et
al., (2019); Huberman et al., (2021); Lavi et al., (2019); Messias et al.,
(2020, 2021). Figure 2.2 shows that $50$% of all Bitcoin transactions were
added to the blockchain in just 3 years. Similarly, in Ethereum, $80$% of the
transactions were added in just 1.5 years. Users typically issue transactions
using a wallet software, whose primary functionality is determining an
“appropriate” fee for a given transaction. This (prioritization) fee varies,
unsurprisingly, as a function of the level of congestion in the blockchain
Messias et al., (2021) as well as the distribution of fees across available
transactions. Inferring either of these is, however, deceptively complicated.

At first glance, these tasks appear straightforward, since every transaction
is broadcast to all miners in the blockchain. A user could simply gather all
transactions broadcast over time and reconstruct the set of uncommitted
transactions available to a miner (i.e., contents of the miner’s Mempool) at
any point of time Messias et al., (2020). We refer to this assumption of a
public and uniform view (across miners) of all available transactions as
_contention transparency_. If contention transparency exists, a user could
rank order available transactions by their fee (based on which miners should
select transactions for inclusion) and estimate the commit delay of any
transaction Messias et al., (2021). Consequently, they could determine the fee
that they must pay to guarantee inclusion of their transaction in a given
block. We label this assumption that the (prioritization) fee offered by a
transaction is only that publicly declared by that transaction as
_prioritization transparency_. Neither the contention transparency nor the
prioritization transparency, however, holds today in permissionless
blockchains.

###  2.4 Decentralized governance

Smart contracts underpin many DeFi applications today Daian et al., (2020);
Adams et al., (2021); Ethereum Foundation, 2023c ; Qin et al., (2021); Perez
et al., (2021), and it is only natural to have a mechanism for updating these
(software) contracts to fix bugs or evolve them over time to cater for new use
cases Liu et al., (2018); David Siegel, (2013); Zhou et al., (2023). If
decisions concerning such updates are made in a centralized manner, e.g., by a
regulatory body, or a cabal of developers or miners, it undermines users’
trust in the applications that these contracts support. The updates could, for
instance, be tailored to benefit the centralized regulatory body at the
expense of others. Governance protocols address this issue by distributing the
decision-making power among all the users of the application or smart contract
being updated.

A governance protocol establishes rules and (transparent) mechanisms for
changing smart contracts. It defines the required procedures for creating,
voting on, and executing proposals to amend smart contracts. It facilitates
users of a protocol (or, more aptly, token holders who hold one or more tokens
of the protocol) to propose changes. The changes are then vetted by and voted
by other users, and implemented only if the proposals receive the majority of
favorable votes. The protocols also grant voting power to a user based on the
number of tokens held by them—typically one token equals one vote, essentially
capturing the user’s stake and/or participation in the protocol. Some
protocols such as Compound Leshner and Hayes, (2019) and Uniswap Adams et al.,
(2021) allow token holders who do not wish to exercise their voting power to
delegate their voting power (i.e., tokens) to others. This delegation is a
form of liquid democracy, where voters can participate in decision-making
either directly by voting or indirectly by delegating their voting rights to
trusted representatives Behrens, (2017); Carroll, (1884); Blum and Zuber,
(2016). Governance protocols give every participant the right to propose,
support, or oppose any proposal. They are, hence, crucial for ensuring
absolute decentralization of applications running atop blockchains.

####  2.4.1 Voting modalities

Proposals to change a governance protocol takes birth in the protocol’s
community forum. Community members suggest and discuss potential changes to
the protocol in the forum and may even conduct an informal poll to gauge the
community’s support for a proposal. The proposer then either amends the
proposal to incorporate the community’s feedback and submit it for a formal
vote, or simply abandon it. The formal voting on the proposal has two modes:
on-chain and off-chain voting.

On-chain voting In this voting system, participants make all governance
decisions via smart contracts on a blockchain. Under this system, participants
cast a vote by issuing a transaction (and paying a fee for committing it) to
the blockchain. The system allows only participants with at least a threshold
amount of (governance) tokens to create a proposal, albeit any token holding
participant can vote on that proposal. It executes the proposal on the
blockchain only if it receives a significant number of votes in favor and
reaches a quorum.888 In Compound, in order for a proposal to be executed, it
needs to meet two requirements. First, it must receive a minimum of $400000$
votes in favor of the proposal. This number corresponds to $4$% of the total
supply and is known as the quorum. Second, the majority of the votes cast must
be in favor of the proposal.  This voting system thus facilitates making
transparent and tamper-proof changes to the protocol. Decentralized governance
protocols such as AAVE AAVE, (2023), Compound Compound Labs, Inc., 2022a , and
Uniswap Uniswap Labs, (2023) use on-chain voting.

Off-Chain Voting This system conducts voting on an off-chain third-party
platform and, as a consequence, also establishes the rules for voting,
aggregating votes, and determining the results off-chain. Protocols such as
Balancer Balancer.fi, (2023) and Convex Finance Convex, 2023a , for instance,
use Snapshot Labs, 2023b  for off-chain voting. Snapshot stores the voting
data on a P2P network called InterPlanetary File System (IPFS) Labs, 2023a .
The voting process does not require voters to pay any fees and (unlike on-
chain voting) promotes participation across all participants, regardless of
their level of participation or investment in the protocol. After the voting,
this system uses a multi-signature contract to enact the off-chain voting
outcome on the blockchain. Typically, an n-of-m multisig contract requires the
transaction to be signed by at least n out of the m “admins” to be executed
on-chain. The system trusts the multisig “admins”, who are well-known in the
community, to implement the voting outcome on the blockchain truthfully. The
admins can also, however, refuse the proposal. In Convex Finance, for
instance, the admins can choose not to execute a proposal if they deem it
harmful, even if it had received the majority of votes and reached a quorum
Convex, 2023b . On-chain voting systems, in contrast, prevent such
manipulation of voting outcomes by one or more individuals (after the voting
process), since all governance decisions (e.g., voting and execution) happen
on the chain.

Token delegations Some governance protocols (e.g., Compound, Uniswap, and
AAVE) require a user to own a certain amount of governance tokens for casting
a vote. Users must delegate their tokens either to themselves or, if they do
not wish to vote, delegate them to others. The ability to delegate voting
power to others facilitates a form of liquid democracy; the token holder who
delegates or sells their tokens to another loses their voting power.
Delegations allow anyone to buy (or sell) tokens and gain (or lose) voting
power instantly. Justin Sun, the founder of (stablecoin) TrueUSD TrueUSD,
(2023), for instance, allegedly borrowed COMP tokens to create and vote for
Compound proposal #84 team, (2022), resulting in a governance attack Thurman,
(2022); this proposal was, however, defeated.

Token “locking” Protocols such as Balancer and Curve Curve, (2023) mandate
that a user “lock” their tokens into a smart contract for a specified period
of time to gain their right to vote. The user cannot withdraw the locked
tokens until the lock-up period expires. The voting power of a user in this
system is proportional to the amount of tokens locked as well as the lock-up
period. In Balancer, for instance, a user receives $1$ unit of voting power if
they lock $1$ token into the contract for $1$ year, and only half that voting
power if they lock it instead for $6$ months.

Continuous voting A few protocols (e.g., MakerDAO MakerDAO, (2023)) allow
voters to change their votes at any time during the voting period. Users
propose a protocol change by developing a new implementation via a smart
contract. The new implementation is accepted if it receives more votes than
the current one, i.e., the winning implementation must always receive the
majority of the votes (or tokens). MakerDAO requires a user to deposit their
(MKR) tokens into the (Maker) Governance contract for casting a vote. The more
tokens they deposit, the more voting power they obtain, and they vote for
their desired implementation by specifying it as a protocol parameter in the
smart contract. Since the voting process is continuous, if a user withdraws
their MKR tokens from the governance contract, their vote will no longer count
towards the implementations for which they previously voted.

We refer the reader to §C.4 (particularly Tab. C.1) for a characterization of
the voting methods, delegation approaches, and proposal executions in various
other governance protocols. Understanding how voting is conducted (i.e.,
whether it is on-chain or off-chain) and proposals are executed is fundamental
for analyzing how voters, proposers, and others interact with these governance
protocols.

###  2.5 Blockchain Scalability with Layer 2.0 Solutions

As observed in Figure 2.2, $50$% of all Bitcoin transactions were added to the
blockchain in just 3 years. Meanwhile, in Ethereum, $80$% of the transactions
were added in just 1.5 years. This highlights a crucial scalability challenge
inherent in blockchains: blocks will not be able to accommodate all
transaction available. Unfortunately, this issue is projected to aggravate
each year. Consequently, the need for Layer 2.0 solutions has arisen to
mitigate the escalating blockchain scalability dilemma.

Layer 2.0 consists of an off-chain network, system, or technology that is
built on top of a blockchain Chainlink Foundation, (2023). In other words,
this approach execute transactions in batches, together, and off-chain. This
process helps accelerate the execution of the transactions leaving the main
blockchain for persisting the validity (or proofs) that the transactions were
correctly executed. As a result, this method accelerates both transaction
execution and confirmation processes.

There are two most popular types of Layer 2.0 solutions: Zero Knowledge (ZK)
Goldwasser et al., (2019); Goldreich and Oren, (1994) and Optimistic Ethereum
Foundation, 2023d  rollups.

Within the Zero Knowledge (ZK) rollup, transactions are grouped into batches
for execution, leading to a reduction in execution costs. The outcome, which
is a proof of transaction validity, gets stored back on the main blockchain
(or Layer 1.0). Therefore, rather than persisting the complete transaction
data for each individual transaction on the blockchain, this approach
conserves space by storing only a proof that verifies the validity of an
entire batch of transactions executed on Layer 2.0. Example of ZK rollup is
ZKSync Matter Labs, (2023).

On the other hand, within the Optimistic rollup, it operates under the
assumption that all transactions are valid by default, unless certain
participants provide evidence to the contrary. Therefore, it is an optimistic
approach. Examples of Layer 2.0 using Optimistic rollups are Optimism Optimism
Foundation, (2023) and Arbitrum Offchain Labs, (2023).

In this thesis, we delve into a Layer 2.0 solution designed for Bitcoin, known
as Omni Layer Omni Layer, (2023). This aims to shed light on off-chain
transaction acceleration facilitated by miners. Unlike the batch approach used
in both ZK and Optimistic rollups, Omni Layer does not batch transactions.
Instead, it creates a Bitcoin transaction for every transaction issued on its
layer. This enables us to analysis the extent to which miners accelerate the
inclusion of these individual transactions.

##  Chapter 3 Transaction Prioritization Norms

In this chapter, we delve into the research questions, methodology, and the
implications of analyzing and comprehending the norms employed by miners when
prioritizing transactions for inclusion. Understanding these prioritization
norms is key to enable transaction issuers to determine the appropriate fees
for their transactions to be included within an expected number of blocks.

The order in which miners select transactions for inclusion have significant
implications for the ultimate outcome of the transaction execution. As a
result, we aim to audit the Bitcoin blockchain to address the following
research questions.

$\blacktriangleright$ RQ 1: Which transactions are allowed or transmitted over
the public P2P network? This research question pertains to the norm III, as
described in §2.2. It assumes that transactions with fee rate below a minimum
threshold are discarded and never committed to the blockchain. If miners are
considering transactions with incentives below the established threshold,
their view of available transactions for inclusion may differ.

$\blacktriangleright$ RQ 2: How do miners select transactions for inclusion in
a block once they enter the miners’ Mempool? This research question pertains
to norm I, which states that miners select transactions for inclusion, from
the Mempool, based solely on their fee rates. However, if some miners accept
additional incentives to accelerate the transaction confirmation such as dark
or opaque fees, the miners’ view of the offered fees may vary. As a result,
transaction issuers may struggle to estimate the appropriate fees needed for
their transaction to be prioritized, as the fees’ distribution may differ
based on individual miner’s view of the system.

$\blacktriangleright$ RQ 3: In what order do miners include transactions
within a block? This question aligns with norm II, where higher fee rate
transactions are prioritized and placed before lower fee rate transactions
during the block construction. If miners misplace transactions within a block,
it can result in different outcomes for those transactions when the miner’s
block is selected as the next block. Transaction issuers may be susceptible to
well-known attacks such as front-running Daian et al., (2020); Torres et al.,
(2021) or even sandwich attacks Qin et al., (2021); Zhou et al., (2023).

Addressing these research questions is crucial for understanding how miners
actually prioritize transactions for inclusion. Hence, accurate knowledge of
the order in which miners include transactions can assist in estimating
appropriate fees that issuers need to offer to prioritize their transactions.
Next, we discuss our methodology for gathering the necessary data sets and
detecting accelerated or highly prioritized transactions.

##### Relevant publication

The results presented in this chapter have been published in Messias et al.,
(2021, 2020).

###  3.1 Methodology

To understand the importance of transaction ordering to issuers and to
investigate when and how miners violate the transaction prioritization
“norms,” we resort to an empirical, data-driven approach. Below, we briefly
describe three different data sets that we curated from Bitcoin and highlight
how we use the data sets in different analyses in the rest of this thesis.
Furthermore, we present our methodology for detecting transaction
acceleration, which can be applied to any fee-based incentive blockchains.

Table 3.1: Bitcoin data sets ($\mathcal{A}$ and $\mathcal{B}$) used for testing miners’ adherence to transaction-prioritization norms and ($\mathcal{C}$) for investigating the behaviour of miners with respect to transaction acceleration. Child-pays-for-parent (CPFP) transactions are transactions that depend on other transactions to be included into a block. Attributes | Data set $\mathcal{A}$ | Data set $\mathcal{B}$ | Data set $\mathcal{C}$
---|---|---|---
Time span |  Feb. $20^{\textrm{th}}$ – Mar. $13^{\textrm{th}}$, 2019 |  Jun. $1^{\textrm{st}}$ – $30^{\textrm{th}}$, 2019 |  Jan. $1^{\textrm{st}}$ – Dec. $31^{\textrm{st}}$, 2020
Block height |  $563833$ – $566951$ |  $578717$ – $583236$ |  $610691$ – $663904$
Number of blocks | $3119$ | $4520$ | $53214$
# of txs. issued | $6816375$ | $10484201$ | $112489054$
% of CPFP-txs. | $26.45\%$ | $23.17\%$ | $19.11\%$
# of empty-blocks | $38$ | $18$ | $240$

(a) Data set $\mathcal{A}$ (b) Data set $\mathcal{B}$

(c) Data set $\mathcal{C}$

Figure 3.1:  Distribution of blocks mined and transactions confirmed by the
top-20 MPOs in data sets $\mathcal{A}$, $\mathcal{B}$, and $\mathcal{C}$.
Their combined normalized hash-rates account for 94.97%, 93.52%, and 98.08% of
all blocks mined in data set $\mathcal{A}$, $\mathcal{B}$, and $\mathcal{C}$,
respectively.

####  3.1.1 Data set collection

Data set $\mathcal{A}$. To check miners’ compliance to prioritization norms in
Bitcoin, we analyzed all transactions and blocks issued in Bitcoin over a
three-week time frame from February 20 through March 13, 2019 (see Table 3.1).
We obtained the data by running a _full_ node, a Bitcoin software that
performs nearly all operations of a miner (e.g., receiving broadcasts of
transactions and blocks, validating the data, and re-broadcasting them to
peers) except for mining. The data set also contains a set of periodic
_snapshots_ , recorded once per $15$ seconds for the entire three-week period,
where each snapshot captures the state of the full node’s Mempool. We plot the
distribution of the count of blocks and transactions mined by the top-20 MPOs
for data set $\mathcal{A}$ in Figure 3.1a. If we rank the MPOs in data set
$\mathcal{A}$ by the number of blocks ($B$) mined (or, essentially, the
approximate hashing capacity $h$), the top five MPOs turn out to be BTC.com
($B$: $536$; $h$: $17.18\%$), AntPool ($B$: $399$; $h$: $12.79\%$), F2Pool
($B$: $352$; $h$: $11.29\%$), Poolin ($B$: $344$; $h$: $11.03\%$), and
SlushPool ($B$: $279$; $h$: $8.94\%$). We use this data for checking whether
miners adhere to prioritization norms when selecting transactions for
confirmation or inclusion in a block.

Data set $\mathcal{B}$. Differences in configuration of the Bitcoin software
may subtly affect the inferences drawn from data set $\mathcal{A}$. A full
node connects to $8$ peers, for instance, in the default configuration, and
increasing this number may reduce the likelihood of missing a transaction due
to a “slow” peer. The default configuration also imposes a minimum fee rate
threshold of $1\text{\,}\mathrm{s}\mathrm{a}\mathrm{t}{\mathrm{/}}\mathrm{B}$
(or 1 satoshi-per-byte) for accepting a transaction. We instantiated, hence,
another full node to expand the scope of our data collection. We configured
this second node, for instance, to connect to as many as $125$ peers. We also
removed the fee rate threshold to accept even zero-fee transactions.
$\mathcal{B}$ contains Mempool snapshots of this full node, also recorded once
per $15\text{\,}\mathrm{s}\text{/}$, for the entire month of June 2019 (refer
Table 3.1). We notice that $99.7\%$ of the transactions received by our
Mempool were included by miners. Figure 3.1b shows the distribution of the
count of blocks and transactions mined by the top-20 MPOs for data set
$\mathcal{B}$. The top five MPOs are BTC.com ($B$: $889$; $h$: $19.67\%$),
AntPool ($B$: $577$; $h$: $12.77\%$), F2Pool ($B$: $523$; $h$: $11.57\%$),
SlushPool ($B$: $438$; $h$: $9.69\%$), and Poolin ($B$: $433$; $h$: $9.58\%$).

Data set $\mathcal{C}$. The insights derived from the above data motivated us
to shed light on the aberrant behavior of mining pool operators (MPOs). To
this end, we gathered all ($53214$) Bitcoin blocks mined and their $112542268$
transactions from January 1${}^{\textrm{st}}$ to December 31${}^{\textrm{st}}$
2020\. These blocks also contain one Coinbase transaction per block, which the
MPO creates to receive the block and the fee rewards. This data set, labeled
$\mathcal{C}$, contains $112489054$ issued transactions (see Table 3.1). MPOs
typically include a signature or marker in the Coinbase transaction, probably
to claim their ownership of the block. Following prior work (e.g., Judmayer et
al., (2017); Romiti et al., (2019)), we use such markers for identifying the
MPO (owner) of each block. We failed to identify the owners of $703$ blocks
(or approximately $1.32\%$ of the total), albeit we inferred $30$ MPOs in our
data set. In this thesis, we consider only the top-20 MPOs whose combined
normalized hash-rates account for $98.08\%$ of all blocks mined. Figure 3.1c
shows the count of blocks mined by the top-20 MPOs according to $\mathcal{C}$.
The top five MPOs in terms of the number of blocks ($B$) mined are F2Pool
($B$: $9326$; $h$: $17.53\%$), Poolin ($B$: $7876$; $h$: $14.80\%$), BTC.com
($B$: $6381$; $h$: $11.99\%$), AntPool ($B$: $5832$; $h$: $10.96\%$), and
Huobi ($B$: $3990$; $h$: $7.5\%$).

####  3.1.2 Detecting accelerated transactions.

Given the high fees demanded by acceleration services, we anticipate that
accelerated transactions would be included in the blockchain with the highest
priority, i.e., in the first few blocks mined by the accelerating miner and
amongst the first few positions within the block. We would also anticipate
that without the acceleration fee, the transaction would not stand a chance of
being included in the block based on its publicly offered transaction fee. The
above two observations suggest a potential method for detecting accelerated
transactions in the Bitcoin blockchain: An accelerated transaction would have
a very high signed position prediction error (SPPE) (refer to §3.3.1), as its
predicted position based on its public fee would be towards the bottom of the
block it is included in, while its actual position would be towards the very
top of the block.

To test the effectiveness of our method, we analyzed all $6381$ blocks and
$13395079$ transactions mined by BTC.com mining pool in data set
$\mathcal{C}$. We then extracted all transactions with SPPE greater or equal
than $100\%$, $99\%$, $90\%$, $50\%$, $1\%$ and checked what fraction of such
transactions were accelerated, according to the BTC.com transaction
accelerator API BTC.com, (2022).

###  3.2 Analyzing norm adherence

In this section, we analyze whether Bitcoin miners adhere to prioritization
norms, when selecting transactions for confirmation. To this end, we first
investigate whether transaction ordering matters to Bitcoin users in practice,
i.e., are there times when transactions suffer extreme delays and do users
offer high transaction fees in such times to confirm their transactions
faster? We then conduct a progressively deeper investigation of the norm
violations, including potential underlying causes, which we investigate in
greater detail in the subsequent sections.

####  3.2.1 Does transaction ordering matter?

(a)  (b)

Figure 3.2:  (a) Distributions of Mempool size in both data sets $\mathcal{A}$
and $\mathcal{B}$; and (b) the size Mempool in $\mathcal{A}$ as a function of
time, both indicating that congestion is typical in Bitcoin.

(a)  (b)

(c)

Figure 3.3:  (a) Distributions of delays until transaction inclusion show that
a significant fraction of Bitcoin transactions experience at least 3 blocks
(or approximately 30 minutes) of delay; Distributions of fee rates for (b) all
transactions and (c) transactions (in $\mathcal{A}$) issued at different
congestion levels clearly indicate that users incentivize miners through
transaction fees.

A congestion in the Mempool leads to contention among transactions for
inclusion in a block. Transactions that fail to contend with others (i.e., win
a spot for inclusion) experience inevitable delays in commit times.
Transaction ordering, hence, has crucial implications for users when the
Mempool experiences congestion. For instance, the Bitcoin Core code and most
of the wallet software rely on the distribution of transactions’ fee rates
included in previous blocks to suggest to users the fees that they should
include in their transactions bitcoin.org, (2023); Coinbase, (2021); Lavi et
al., (2019). Such transaction-fee predictions from any predictor, which assume
that miners follow the norm, will be misleading.999Coinbase, one of the top
cryptocurrency exchanges, does not allow users to set transaction fees
manually. Instead, it charges a fee based on how much they expect to pay for
the concerned transaction, which in turn relies on miners following the norm
Coinbase, (2021). Below, we examine whether Mempool in a real-world blockchain
deployment experiences congestion and its impact on transaction-commit delays.
We then analyze whether, and how, users adjust transaction fees to cope with
congestion, and the effect of these fee adjustments on commit delays.

##### Congestion and delays

Bitcoin’s design—specifically, the adjustment of hashing difficulty to enforce
a constant mining rate—ensures that there is a steady flow of currency
generation in the network. The aggregate number of size-limited blocks mined
in Bitcoin, consequently, increases linearly over time (Figure 2.2a).
Transactions, however, are not subject to such constraints and have been
issued at much higher rates, particularly, according to Figure 2.2a, since
mid-2017: $60\%$ of all transactions ever introduced were added in only in the
last 3.5 years of the nearly decade-long life of the cryptocurrency. Should
this growth in transaction issued continue to hold, transactions will
increasingly have to contend with one another for inclusion within the limited
space (of $1\text{\,}\mathrm{M}\mathrm{B}$) in a block. Below, we empirically
show that this contention among transactions is already common in the Bitcoin
network.

Using the data sets $\mathcal{A}$ and $\mathcal{B}$ (refer §3.1.1), we
measured the number of unconfirmed transactions in the Mempool, at the
granularity of $15\text{\,}\mathrm{s}\text{/}$. Per Figure 3.2a, congestion in
Mempool is typical in Bitcoin: During the three-week period of $\mathcal{A}$,
the aggregate size of all unconfirmed transactions was above the maximum block
size (of $1\text{\,}\mathrm{M}\mathrm{B}$) for nearly $75\%$ of the time; per
data set $\mathcal{B}$ the Mempool was congested for nearly $92\%$ of the time
period. Figure 3.2b provides a complementary view of the Mempool congestion in
$\mathcal{A}$, by plotting the Mempool size as a function of time. The
measurements reveal a huge variance in Mempool congestion, with size of
unconfirmed transactions at times exceeding 15-times the maximum size of a
block. Transactions queued up during such periods of high congestion will have
to contend with one another until the Mempool size drains below
$1\text{\,}\mathrm{M}\mathrm{B}$. These observations also hold in data set
$\mathcal{B}$, the details of which are in §A.1.

The Mempool congestion, which in turns leads to the contention among
transactions for inclusion in a block, has one serious implication for users:
delays in transaction-commit times. While $65\%$ ($60\%$) of all transactions
in data set $\mathcal{A}$ ($\mathcal{B}$) get committed in the next block
(i.e., in the block immediately following their arrival in the Mempool),
Figure 3.3a shows that nearly $15\%$ ($20\%$) of them wait for at least $3$
blocks (i.e., $30$ minutes on average). Moreover, $5\%$ ($10\%$) of the
transactions wait for $10$ or more blocks, or $100$ minutes on average, in
data set $\mathcal{A}$ ($\mathcal{B}$). While no transaction waited for more
than a day in data set $\mathcal{A}$, a small percentage of transactions
waited for up to five days (because of the high levels of congestion in June
2019) in data set $\mathcal{B}$.

Takeaways. Mempool is typically congested in Bitcoin. Transactions, hence,
typically contend with one another for inclusion in a block. The Mempool
congestion has non-trivial implications for transaction-commit times.

##### Transaction fee rates and delays

To combat the delays and ensure that a transaction is committed “on time”
(i.e., selected for inclusion in the earliest block), users may include a
transaction fee for incentivizing the miner. While the block reward from May
$11$, 2020 is $6.25\text{\,}\mathrm{B}\mathrm{T}\mathrm{C}$, the aggregate
fees accrued per block is becoming considerable (i.e., $6.29\%$ of the total
miner revenue in 2020 per Table A.1 in §A.2). Prior work also show that
revenue from transaction fees is clearly increasing Easley et al., (2017).
With the volume of transactions growing aggressively (Figure 2.2a) over time
and the block rewards, in Bitcoin, halving every four years, it is inevitable
that transaction fees will be an important, if not the only, criterion for
including a transaction, leading possibly to undercutting attacks Carlsten et
al., (2016). Below, we analyze whether Bitcoin users incentivize miners via
transaction fees and if such incentives are effective today.

Per Figure 3.3b the transaction fee rate of committed transactions in both
data sets $\mathcal{A}$ and $\mathcal{B}$ exhibits a wide range, from
$10^{-6}$ to beyond
$1\text{\,}\mathrm{B}\mathrm{T}\mathrm{C}{\mathrm{/}}\mathrm{k}\mathrm{B}$.
The fee rate distributions of committed transactions also do not vary much
between different mining pool operators (refer Figure A.2 in §A.3). A few
transactions ($0.001\%$ in $\mathcal{A}$ and $0.07\%$ in $\mathcal{B}$) were
committed, despite offering fee rates less than the recommended minimum of
$10^{-5}$ BTC/kB. A non-trivial percentage of transactions offered fee rates
that are two orders of magnitude higher than the recommended value;
particularly, in data set $\mathcal{B}$, perhaps due to the comparatively high
levels of congestion (cf. Figure 3.2b and Figure A.1), $34.7\%$ of
transactions offered fee rates higher than $10^{-3}$ BTC/kB. Approximately
$70\%$ ($51.3\%$) of the transactions in data set $\mathcal{A}$
($\mathcal{B}$) offer fee rates between $10^{-4}$ and $10^{-3}$ BTC/kB, i.e.,
between one and two orders of magnitude more than the recommended minimum.
Such high fee rates clearly capture the users’ intents to incentivize the
miners.

Our premise is that the (high) fee rates correlate with the level of Mempool
congestion. Said differently, we hypothesize that users increase the fee rates
to curb the delays induced by congestion. To test this hypothesis, we separate
the Mempool snapshots (cf. §3.2.1) into $4$ different bins. Each bin
corresponds to a specific level of congestion identified by the Mempool size
as follows: lower than $1\text{\,}\mathrm{M}\mathrm{B}$ (no congestion), in
$(1,2]$ MB (lowest congestion), in $(2,4]$ MB, and higher than
$4\text{\,}\mathrm{M}\mathrm{B}$ (highest congestion). The fee rates of
transactions observed in the different bins or congestion levels, in Figure
3.3c, then validates our hypothesis: Fee rates are strictly higher (in
distribution, and hence also on average) for higher congestion levels.

Figure 3.4:  Distributions of transaction-commit delays for different fee
rates for transactions in $\mathcal{A}$; incentivizing miners via fee rates
works well in practice.

Figure 3.4 shows that users’ strategy of increasing fee rates to combat
congestion seems to work well in practice. Here, we compare the CDF of commit
delays of transactions with low (i.e., less than $10^{-4}$ BTC/kB), high
(i.e., between $10^{-4}$ and $10^{-3}$ BTC/kB), and exorbitant (i.e., more
than $10^{-3}$) fee rates, in data set $\mathcal{A}$. Similar analysis with
data set $\mathcal{B}$ is provided in §A.4. We observe that an increase in the
transaction fee rates is consistently rewarded (by miners) with a decrease in
the commit delays. This observation suggests that, at least to some extent,
miners prioritize transactions for inclusion based on fee rates or the fee-
per-byte metric.

Takeaways. A significant fraction of transactions offers fee rates that are
well above the recommended minimum (i.e., $10^{-5}$ BTC/kB or simply
$1\text{\,}\mathrm{s}\mathrm{a}\mathrm{t}{\mathrm{/}}\mathrm{B}$). Fee rates
are typically higher at higher congestion levels, and reduce the commit
delays. These observations suggest that users are indeed willing to spend
money to decrease commit delays for their transactions during periods of
congestion.

####  3.2.2 Do miners follow the norms?

Whether miners follow the transaction prioritization norms (as widely assumed)
has implications for both Bitcoin and its users: The software used by users,
for instance, assumes an adherence to these norms when suggesting a
transaction fee to the user bitcoin.org, (2023); Coinbase, (2021); Lavi et
al., (2019). Deviations from these norms, hence, have far-reaching
implications for both the blockchain and crucially for Bitcoin users.

##### Fee rate based selection when mining new blocks

Our finding above show that transactions offering higher fee rates experience
lower confirmation delays suggests that miners tend to account for transaction
fee rates when choosing transactions for new blocks. We now want to check,
however, if transaction fee rate is the primary or the sole determining factor
in transaction selection. To this end, we check our data sets for transaction
pairs, where one transaction was issued earlier and has a higher fee rate than
the other, but was committed later than the other. The existence of such
transaction pairs would unequivocally show that fee rate alone does not
explain the order in which they are selected.

We sampled $30$ Mempool snapshots, uniformly at random, from the set of all
available snapshots in data set $\mathcal{A}$. Suppose that, in each snapshot,
we denote, for any transaction $i$, the time at which it was received in the
Mempool by $t_{i}$, its fee rate by $f_{i}$, and the block in which it was
committed by $b_{i}$. We then selected, from each snapshot, all pairs of
transactions $(i,j)$ such that $t_{i}<t_{j}$ and $f_{i}>f_{j}$, but
$b_{i}>b_{j}$. Such pairs clearly constitute a violation of the fee-rate-based
transaction-selection norm.

(a) All transactions (b) Only Non-CPFP transactions

Figure 3.5:  There exists a non-trivial fraction of transaction pairs
violating the norm across all snapshots, clearly indicating that miners do not
adhere to the norm.

Figure 3.5a shows a cumulative distribution of the fraction of all transaction
pairs (line labeled “$\star$”) violating the norm over all sampled snapshots.
Across all snapshots, a small but non-trivial fraction of all transaction
pairs violate the norm. One potential explanation for violations might be that
the transactions are received by the mining pools in different order than the
one in which our Mempool receives. To account for such differences, we tighten
the time constraint as $t_{i}+\epsilon<t_{j}$ and use an $\epsilon$ of either
$10$ seconds or $10$ minutes. Even with the tightened time constraints, Figure
3.5a shows that a non-trivial fraction of all transaction pairs violate the
norm.

Another potential source of violations is Bitcoin’s dependent (or, parent and
child) transactions, where the child pays a high fee to incentivize miners to
also confirm the parent from which it draws its inputs. This mechanism enables
users to “accelerate” a transaction that has been “stuck” because of low fee
CoinStaker, (2018). As the existence of such _child-pays-for-parent (CPFP)_
transactions (formally defined in §A.5) would introduce false positives in our
analysis we decided to discard them. Figure 3.5b shows that the violations
exist even after discarding all such dependent transaction pairs.

##### Fee rate based ordering within blocks

We now turn our attention to transaction ordering within individual (mined)
blocks in Bitcoin. If a miner followed GBT, transactions would be ordered
based on their fee rate. In this case, given the set of non-CPFP transactions
$T=\\{T_{1},T_{2},....T_{n}\\}$ included in a block $B$, we should be able to
predict their position in the block by simply ordering the transactions based
on their fee rate (as specified in the GBT implementation in Bitcoin Core). To
quantify the deviation from the norm, we compute a measure that we call
position prediction error (PPE): PPE of a block $B$ is the average absolute
difference between the predicted and the observed (actual) positions for all
transactions in block $B$, normalized by the size of the block ($n$) and
expressed as a percentage. More precisely,

$\displaystyle PPE(B)=\sum_{i=1}^{n}\dfrac{(|T^{p}_{i}-T^{o}_{i})|)\cdot
100}{n}$

where $T^{p}_{i}$ and $T^{o}_{i}$ are the predicted and observed positions of
a transaction, respectively.

(a) Overall position prediction error (b) Position prediction error of the
top-6 MPOs

Figure 3.6:  Position prediction error (PPE). (a) There are 52,974 (99.55%)
blocks with at least one non-CPFP txs. The mean PPE is 2.65%, with an std of
2.89. 80% of all blocks has PPE less than 4.03%. (b) The PPEs of blocks mined
by the top-6 MPOs according to their normalized hash rate.

Figure 3.6a shows the cumulative distribution of PPE values for each block in
our data set $\mathcal{C}$, containing $53214$ blocks. $80\%$ of the blocks
have PPE values less than $4.03\%$. The mean PPE across all blocks is
$2.65\%$, with a standard deviation of $2.89$. Per this plot the position of a
transaction within a block can be predicted with very high accuracy (within a
few percentile position error), suggesting that transactions are by and large
ordered within a block based on their fee rate. Figure 3.6b shows PPE values
separately for each of the $6$ largest mining pools in data set $\mathcal{C}$.
The plots show that all mining pools by and large follow the norm, though some
like ViaBTC seems to deviate slightly more from the norm compared to the other
mining pools.

##### Fee rate threshold for excluding transactions

In their default configuration, many nodes in the Bitcoin P2P network drop
(i.e., ignore) transactions that offer less than a threshold fee rate
(typically, $10^{-5}$ BTC/kB). As miners select transactions for inclusion
from their local Bitcoin P2P node, this (default) norm would result in such
low-fee transactions never being included in the blockchain, even during
periods of non-congestion (when blocks have spare capacity to accommodate
additional transactions).

We collected data set $\mathcal{A}$ using a default Bitcoin node, and our
node, hence, did not accept or record low-fee transactions. When gathering
data set $\mathcal{B}$, however, we configured our Bitcoin node to accept all
transactions, irrespective of their fee rates. In data set $\mathcal{B}$, our
node, consequently, received $1084$ transactions that offered less than the
recommended fee rate and $489$ ($45.11\%$) of them were zero-fee transactions.
From these low fee rate transactions, only $53$ ($4.89\%$) were confirmed in
the Bitcoin blockchain; $9$ ($16.98\%$) were confirmed months after they were
observed in our data set. In contrast, the vast majority ($99.7\%$) of the
transactions that offered greater than or equal to the recommended fee rate
were all (eventually) confirmed. Interestingly, the low-fee transactions were
confirmed by just three mining pools: F2Pool, ViaBTC, and BTC.com included
$38$, $14$, and $1$ low-fee transactions, respectively. Our findings suggest
that while the norm of ignoring transactions offering less than the
recommended fee rate is being by and large followed by all miners, a few
occasionally deviate from the norm.

###  3.3 Investigating norm violations

Our analysis so far showed that while Bitcoin miners by and large follow
transaction-prioritization norms, there are many clear instances of norm
violations. Our next goal is to develop a deeper understanding of the
underlying reasons or motivations for miners to deviate from the fee rate
based norms, at least for some subset of all transactions. To this end, we
focus our investigation on the following three types of transactions, where we
hypothesize miners might have an incentive to deviate from the current norms,
which are well-aligned towards maximizing their rewards for mining.

  1. 1.

Self-interest Transactions: Miners have a vested interest in a transaction,
where the miners themselves are a party to the transaction, i.e., a sender or
a receiver of bitcoins. Miners may have an incentive to selfishly accelerate
the commitment of such transactions in the blocks mined by themselves.

  2. 2.

Scam-payment Transactions: Bitcoins are increasingly being used to launch a
variety of ransomware and scam attacks Sheera Frenkel, Mark Scott and Paul
Mozur, (2017); Lee Mathews, (2017); Sheera Frenkel and Nathaniel Popper and
Kate Conger and David E. Sanger, (2020). A scam attack involved using hijacked
Twitter accounts of celebrities to encourage their followers to send bitcoins
to a specific Bitcoin wallet address Sheera Frenkel and Nathaniel Popper and
Kate Conger and David E. Sanger, (2020). Given the timely and widespread
coverage of this attack in popular press and other similar attacks on
crowdsourced websites for reporting scam transactions BitcoinAbuse, (2021);
Whale Alert, (2021), and with governments trying to blacklist wallet addresses
of entities suspected of illegal activities Nikhilesh De, (2021); Andrew
Hinkes and Joe Ciccolo, (2021), we hypothesize that some miners might
decelerate or even absolutely exclude the commitment of scam-payment
transactions out of fear or ethical concerns.

  3. 3.

Dark-fee Transactions: Recently, some mining pool operators have started
offering transaction acceleration services BTC.com, (2022); ViaBTC, (2022);
Poolin, (2022); F2Pool, (2022); AntPool, (2022), where anyone wanting to
prioritize their transactions can pay an additional fee to a specific mining
pool via a side-channel (often, the MPO’s website or via a private-channel
Strehle and Ante, (2020)). Such transaction fees are “dark” or opaque to other
mining pools and the public, and we hypothesize that some committed low-fee
transactions might have been accelerated by using such services.

To detect whether a mining pool has accelerated or decelerated the above types
of transactions, we first design a robust statistical test. Later, we report
our findings from applying the test on the three types of transactions.

####  3.3.1 Statistical test for differential prioritization

Our goal here is to propose a robust statistical test for detecting whether a
given mining pool $m$ is prioritizing a given set of committed transactions
$c$ differently than all other miners. The basic idea behind the statistical
test is as follows. Suppose a mining pool is accelerating (decelerating)
transactions in set $c$. In that case, these transactions will have a
disproportionately high (low) chance of being included in blocks mined by this
mining pool compared to the mining pool’s hashing power (or rate).

##### Test for differential transaction acceleration

Consider a miner $m$ with normalized hash rate $h=\theta_{0}$ (estimated as
fraction of blocks mined by $m$). Assume that we are given a set of
transactions, denoted as $c$-transactions (for committed transactions), for
which we wish to test whether miner $m$ is treating them preferentially.

To test whether $m$ is prioritizing $c$-transactions, we look at all blocks
that include at least one $c$-transaction, call them $c$-blocks. Suppose that
there are $y$ such blocks. If $m$ is not prioritizing $c$-transactions, then a
fraction $\theta_{0}$ of all $c$-blocks should be $m$-blocks (i.e., mined by
$m$); if $m$ is prioritizing $c$-transactions (compared to other miners) then
the fraction will be higher. We want to test whether the true fraction
$\theta$ is indeed $\theta_{0}$ or is higher. We formalize this as follows: We
assume that each $c$-block has a probability $\theta$ to be an $m$-block and
do the following test.

$\displaystyle H_{0}:\theta=\theta_{0}$ $\displaystyle
H_{1}:\theta>\theta_{0}.$

Assuming that the observed number of $c$-blocks that are mined by $m$ is $x$,
the $p$-value of the test is

$\displaystyle p=Pr(B\geq x),$

where $B$ is a binomial distribution of parameter $\theta_{0}$ and $y$, that
is

$\displaystyle
p=\sum_{k=x}^{y}\binom{y}{k}\theta_{0}^{k}(1-\theta_{0})^{(y-k)}.$

We may fix the size of the test (i.e., the maximal probability of type I error
that corresponds to rejecting $H_{0}$ when $H_{0}$ is true) to $\alpha=0.01$.
Then $H_{0}$ should be rejected whenever $p<\alpha$. The smaller $p$, the
higher the confidence in rejecting $H_{0}$, that is declaring that $m$
prioritizes c-transactions.

The above test is relative in the sense that we can only detect if a miner
treats $c$-transactions more preferentially than the rest of the miners. This
test cannot conclude on whether it is the miner accelerating the
$c$-transactions (relative to their deserved, i.e., fee rate based, priority)
or the rest of the miners are decelerating them. So, we look at additional
empirical evidence from the position of the $c$-transactions within the
$c$-blocks that include them. Specifically, given the set of $c$-transactions
$\\{c_{1},c_{2},....c_{n}\\}$ committed by a miner $m$, we compute a measure
that we call signed position prediction error (SPPE) as the average signed
difference between the predicted and observed positions (measured as
percentile rank) for all $c$-transactions within the blocks committed by $m$.
More precisely,

$\displaystyle SPPE(m)=\dfrac{\sum_{i=1}^{n}(c^{p}_{i}-c^{o}_{i})\cdot
100}{n}$

where $c^{p}_{i}$ and $c^{o}_{i}$ are the predicted and the observed
(percentile rank) positions, respectively, of transaction $c_{i}$ within the
blocks committed by $m$.

##### Test for differential transaction deceleration

While the previous test checks for prioritization (or acceleration), one may
also want to test for deceleration. To that end, a symmetric test can be used.
Specifically, with the previous notation, the test would be

$\displaystyle H_{0}:\theta=\theta_{0}$ $\displaystyle
H_{1}:\theta<\theta_{0};$

and its $p$-value would be

$\displaystyle p=Pr(B\leq x),$

where $B$ is a binomial distribution of parameter $\theta_{0}$ and $y$, that
is

$\displaystyle
p=\sum_{k=0}^{x}\binom{y}{k}\theta_{0}^{k}(1-\theta_{0})^{(y-k)}.$

(a) Number of MPOs’ wallet addresses (b) Number of MPOs’ transactions

Figure 3.7:  (a) Distribution of the number of wallet addresses in data set
$\mathcal{C}$ used by each of the top-20 MPOs to receive its block rewards;
SlushPool and Poolin, for instance, used 56 and 23 distinct wallet addresses,
respectively. (b) The counts of inferred MPO transactions; in total, 12,121
transactions were inferred as MPOs’ transactions, which corresponds to 0.011%
of the total issued transactions recorded in the Bitcoin blockchain. Poolin
has the majority with 2232 (18.41%), followed by Okex with 2089 (17.24%) and
Huobi with 1666 (13.74%) transactions. BitDeer and Buffett have the same
wallet address as BTC.com and Lubian.com, respectively. We count the addresses
of the former as belonging to the latter.

##### Scaling the tests

While we did not face them in this thesis, our test may have two limitations
when scaling to large time windows and/or large numbers of transactions.

First, it may become difficult to compute the $p$-value from the binomial
distribution for large values of $y$. In such cases, we can use the following
approximation for our analysis: If $y$ is large enough and $\theta_{0}$ is not
close to zero or one (i.e., $x$ and $y-x$ are large enough), the binomial
distribution of parameters $\theta_{0}$ and $y$ is well approximated by the
normal distribution with mean $y\theta_{0}$ and variance
$y\theta_{0}(1-\theta_{0})$. Hence, the $p$-value for the acceleration test
can be computed as,

$\displaystyle
p\simeq\Phi\left(\frac{x-y\theta_{0}}{\sqrt{y\theta_{0}(1-\theta_{0})}}\right),$

where $\Phi$ is the CDF of a standard normal random variable. A similar
approximation can be done for the deceleration test.

Second, the hash rates of miners in our $p$-value test are assumed to be more
or less constant (i.e., $\theta_{0}$ is a constant), which is not the case
(per Figure B.1 and Figure B.2 in §B.3). This assumption is a limitation of
our test as, in reality, hash rates of miners may vary over time, particularly
over large time windows. In such situations, our test results may be affected,
particularly when the arrival times of transactions are not regularly spread
over the time window of our analysis. We address this issue by confirming the
results of the $p$-value test through the SPPE-test, which is not affected by
variable hash rates. It is possible, however, to alleviate this limitation of
our analysis. One natural way is to divide the total time window into multiple
windows such that the hash rate is more or less constant in those shorter time
windows; and compute $p$-values in each time window. We can then combine the
obtained $p$-values using Fisher’s method Fisher, (1992); Mosteller and
Fisher, (1948). We leave the investigation of such extended test procedures to
future work, when they might be needed.

####  3.3.2 Self-interest transactions

To identify transactions where a mining pool is a sender or receiver of
transactions, we first need to identify Bitcoin wallets (addresses) that
belong to mining pools. In Bitcoin, whenever a mining pool discovers a new
block, it specifies a wallet address to receive the mining rewards. This
mining pool address is included in the Coinbase transaction (refer §2.1) that
appears at the start of every block. In our data set $\mathcal{C}$, we
gathered all the wallet addresses used by the top-$20$ mining pools to receive
their rewards. For each mining pool, we then retrieved all committed
transactions, in which coins were sent from the mining pool’s wallet. Figure
3.7 shows the statistics for the mining pool wallets and the transactions
spending (sending) coins from (to) the wallets, for each of the top-$20$
mining pools in data set $\mathcal{C}$. We found hundreds or thousands of
self-interest transactions for most of the mining pools.

##### Acceleration of self-interest transactions

Table 3.2: Differential prioritization of self-interest transactions.

Transactions | mining pool | norm. hash rate | x | y | p-value | % SPPE
---|---|---|---|---|---|---
of … | (m) | ($\theta_{0}$) | (accel.) | (decel.) | (m)
F2Pool | F2Pool | 0.1753 | 466 | 839 | 0.0000 | 1.0000 | 78.5494
ViaBTC | ViaBTC | 0.0676 | 412 | 720 | 0.0000 | 1.0000 | 98.9175
1THash & 58Coin | ViaBTC | 0.0676 | 34 | 201 | 0.0000 | 1.0000 | 81.4516
1THash & 58Coin | 0.0611 | 39 | 201 | 0.0000 | 1.0000 | 96.9143
SlushPool | SlushPool | 0.0375 | 214 | 1343 | 0.0000 | 1.0000 | 88.3082
ViaBTC | 0.0676 | 140 | 1343 | 0.0000 | 1.0000 | 45.1523

For self-interest transactions belonging to each of the top-20 mining pools,
we separately applied our statistical test to check whether any of the top-10
mining pools (that mined at least $4\%$ of all mined blocks in data set
$\mathcal{C}$) are preferentially accelerating or decelerating the
transactions. In Table 3.2, we report the statistics from our test for mining
pools that were found to preferentially treat transactions belonging to their
own or other mining pools. Strikingly, Table 3.2 shows that 4 out of the
top-10 mining pools namely, F2Pool, ViaBTC, 1THash & 58Coin, and SlushPool
selfishly accelerated their own transactions, i.e., coin transfers from or to
their own accounts (p-value for acceleration test is less than $0.001$).
Equally, if not more interestingly, Table 3.2 shows collusive behavior among
mining pools. Specifically, it shows that transactions issued by 1THash &
58Coin and SlushPool were collusively accelerated by ViaBTC (p-value for
acceleration test is less than $0.001$). That these mining pools were
accelerating the transactions is further confirmed by the SPPE measure, which
clearly shows that in each of the above cases, the self-interest transactions
were also being included within the blocks ahead of other higher fee rate
transactions.

####  3.3.3 Scam-payment transactions

Table 3.3: Differential prioritization of scam-payment transactions

mining pool | norm. hash rate | x | y | p-value | % SPPE
---|---|---|---|---|---
(m) | ($\theta_{0}$) | (accel.) | (decel.) | (m)
Poolin | 0.1528 | 10 | 53 | 0.2856 | 0.8227 | $-3.9787$
F2Pool | 0.1450 | 10 | 53 | 0.2323 | 0.8629 | $0.8735$
BTC.com | 0.1147 | 9 | 53 | 0.1483 | 0.9233 | $-2.8333$
AntPool | 0.1093 | 4 | 53 | 0.8450 | 0.2989 | $31.5000$
Huobi | 0.0955 | 1 | 53 | 0.9951 | 0.0323 | $-1.6428$
Okex | 0.0698 | 3 | 53 | 0.7248 | 0.4890 | $-5.0000$
1THash & 58COIN | 0.0684 | 8 | 53 | 0.0268 | 0.9907 | $-0.5000$
Binance Pool | 0.0590 | 3 | 53 | 0.6120 | 0.6180 | $-2.6000$
ViaBTC | 0.0552 | 1 | 53 | 0.9507 | 0.2020 | $-4.0000$

Next, we investigate whether any mining pool attempted to decelerate or
exclude scam-payment transactions.

On July 15, 2020, multiple celebrities’ accounts on Twitter fell prey to a
scam attack. The scammers posted the message that anyone who transferred
bitcoins to a specific wallet will receive twice the amount in return Sheera
Frenkel and Nathaniel Popper and Kate Conger and David E. Sanger, (2020). In
response, several people sent, in total, $12.87051731$ bitcoins—then worth
nearly $142000$ (USD)—to the attacker’s wallet via $386$ transactions, which
were confirmed across $53$ blocks by $12$ miners.

To examine the miners’ behavior during this scam attack, we selected all
blocks mined from July 14 to August 9, 2020 (i.e., $3697$ blocks in total,
containing $8318621$ issued transactions as described in §A.6) from our data
set $\mathcal{C}$. Once again, we applied our statistical test to check
whether any of the top-$9$ mining pools (that mined at least $5\%$ of all
mined blocks from this data) are preferentially accelerating or decelerating
the transactions. Table 3.3 shows the test statistics. Interestingly, we find
no statistically significant evidence (i.e., p-value less than $0.001$) of
scam-payment acceleration or deceleration across all top mining pools. Looking
at SPPE measure across the mining pools, we find no evidence of mining pools
(other than AntPool) preferentially ordering the scam-payment transactions
within blocks. In short, our findings show that most mining pool operators
today do not distinguish between normal and scam-payment transactions.

##### Inferring other scam payment transactions from crowded source data

(a) Monthly reports (b) Reports per country

Figure 3.8:  (a) Distribution of the number of reports per month. (b) USA is
the country with more reports accounting for 27.6% of all reports available
followed by UK and Canada.

We also want to investigate whether other types of scams payments have been
recorded on the Bitcoin blockchain.

To conduct this experiment, we gathered data from the Bitcoin Abuse Bitcoin
Abuse, (2020) crowdsource platform. This platform allows users to report
Bitcoin wallet addresses that they suspect are associated with scams. From May
16, 2017, to October 15, 2020, we gathered a total of $186731$ reports from
users. These reports identified $54032$ unique wallet addresses that could
potentially be linked to scams. The monthly trend of scam reports is
illustrated in Figure 3.8a. Notably, there is an increase in the number of
reports starting from July 2018. The reports predominantly originated from
users in the US, followed by users in the UK (refer Figure 3.8b).

To simplify our analysis, we focused on transactions that occurred during the
year 2018.101010Due to limitations in data gathering, we considered
transactions issued in 2018. This forms a subset of our data set $\mathcal{D}$
introduced in §4.1. However, out of the total reported wallets, only a small
portion, $1169$ (2.16%) wallets, were found in our Bitcoin 2018 data set. On
average, each wallet address was reported $3.46$ times, with a std. of
$14.41$. Both the minimum and the median number of reports for a wallet
address were 1, while the maximum number of reports reached 950.

Table 3.4: Scam types and their occurrences in wallets and transactions.

Scam type | # of txs. | % of txs. | # of wallets | % of wallets
---|---|---|---|---
Sextortion | 2,656 | 40.79 | 478 | 86.59
Terrorism | 1,093 | 16.79 | 1 | 0.18
Dark Web Shop | 1,019 | 15.65 | 8 | 1.45
Fake Giveaway | 739 | 11.35 | 18 | 3.26
Fake Exchange | 235 | 3.61 | 3 | 0.55
Other | 218 | 3.35 | 16 | 2.90
Malware | 195 | 2.99 | 4 | 0.72
Fake Investment | 164 | 2.52 | 6 | 1.09
Ransomware | 139 | 2.13 | 17 | 3.08
Ponzi Scheme | 53 | 0.82 | 1 | 0.18
Total | 6,511 | 100 | 552 | 100

To ensure accuracy in our analysis, we complemented the data from Bitcoin
Abuse with information from another platform called Scam Alert Scam Alert,
(2020). Scam Alert verifies the wallet addresses reported by users to
determine if they are indeed associated with scams. Initially, we had a set of
$1169$ identified wallets reported by Bitcoin Abuse. Upon cross-checking with
Scam Alert, we discovered that $100$ were not involved with scams. Out of the
remaining $1069$ wallet addresses, $473$ were confirmed to be scams, $79$ were
labeled as probable scams, and $517$ were pending review at the time of our
analysis. Thus, for our analysis, we only considered wallet addresses
confirmed or labeled as probable scams by Scam Alert. This resulted in a final
scam wallet data set containing $552$ unique wallet addresses.

Table 3.4 provides information about the number of wallet addresses and the
number of transactions that sent coins to at least one of the scam wallets
during 2018. We identified several types of scams using the Scam Alert data
set, with Sextortion comprising $40.79$% of the total, followed by Terrorism
at $16.79$%, and Dark Web Shop at $15.65$%. Together, these three types of
scams accounted for $73.23$% of the total scams identified in our study.
Additionally, Table 3.5 shows the top-20 most frequently used wallet addresses
for scam payments. Notably, the wallet 1LaN$\cdots$Qctq has been associated
with a terrorist organization using it to collect donations Huillet, (2020).
This specific wallet address was involved in a total of by $1093$
transactions.

Moreover, we observed that despite these scam wallets being publicly
available, most of the mining pools still included them in their blocks.
Figure 3.9 shows the distribution of blocks and transactions associated with
scam payments that were included by each of the mining pools. BTC.com included
alone $20.09$% out of the $6511$ scam transactions in 2018.

Table 3.5: Top-20 most used wallets for scam payments.

Wallet address | Scam type | # of txs.
---|---|---
1LaNXgq2ctDEa4fTha6PTo8sucqzieQctq | Terrorism | 1,093
167uU5Q3cCPijsfwmmH6ZAQj8yYxQdmzoN | Dark Web Shop | 359
17v1cviCPNuGY73wNGvatS3CEZzrcPnXPy | Fake Giveaway | 254
1Gs7Aztizk2rNNSE6AbpK4K7yAFTCZKV9a | Dark Web Shop | 251
1EU1Ly84tYpTCcjWtvF4tYosRNN2xYYSGF | Dark Web Shop | 207
15ESgUNQ9Hgn2h2FDMJi9NwE4g7ZWRAGJE | Fake Giveaway | 170
3Lo4nDzH7Bi572T7t8pQGU2Ax9jVymHeC6 | Fake Exchange | 137
13hjTSbwVJfsDgL3qaQSu3fs2qmHQCHRXT | Sextortion | 131
1Hy6BcTtNwrCLQK8ViEP742jRgx8Zpfoja | Dark Web Shop | 115
343CXYVBKXT2VgELCdjEeMyPpfiKwkzUNg | Other | 103
3L5o1AHLTKUeJDF8U2s5dgQCwoGknVyycn | Fake Giveaway | 98
16EegrNMdZ9Rxku6Za5neEFjMW57wkQr1S | Malware | 89
1C4SvJQexhAEZzm3f6E6PMQT2xWtJdKKvp | Fake Exchange | 80
1HYoMM6mfFiDvkRe5z9RsSo3sugnqaDps3 | Fake Investment | 77
1B7aczSxaMbRsPJXx22TP1foaHQ6FENwTA | Fake Giveaway | 62
3NYKHbX3zRbcZeASxjZmb4bpF8kZytnuvi | Malware | 54
1JTtwbvmM7ymByxPYCByVYCwasjH49J3Vj | Sextortion | 54
16JL8g7QQthYorTCkjJNE7Yhm7M3DyVyNZ | Ponzi Scheme | 53
1GL9JtXPRTPetxgiJ8UcgrEECp12spD4tt | Sextortion | 52
122wvcbWhBux5jcf2iyzFLmW7Jex7iSpef | Sextortion | 49

(a) Distribution of blocks (b) Distribution of transactions

Figure 3.9:  Distribution of (a) blocks mined per each mining pool in
comparison to the fraction of blocks that contains at least one scam
transaction; and (b) transactions included by each mining pool in comparison
to their share of scam transaction inclusion. BTC.com included 20.09% out of
the 6511 scam transactions in 2018.

###  3.4 Dark-fee transactions

We refer to transactions that offer additional fees to specific mining pools
through an opaque and non-public side-channel payment as dark-fee
transactions. Many large mining pool operators allow such side-channel
payments on their websites for users wanting to “accelerate” the confirmation
of their transactions, especially during periods of congestion. Such private
side-channel payments that hide the fees a user pays to miners from others
have other benefits for the users BTC.com, (2022); SparkPool, (2021); F2Pool,
(2022); Poolin, (2022); AntPool, (2022). One well-known advantage is, for
instance, avoiding the fee rate competition in transaction inclusion,
particularly during periods of high Mempool congestion; private side-channel
payments would reduce a user’s transaction cost volatility and curb front-
running risks Daian et al., (2020); Strehle and Ante, (2020); Eskandari et
al., (2020). We use the data set $\mathcal{C}$ to first investigate how such
transaction acceleration services work and later propose a simple test for
detecting accelerated transactions in the Bitcoin blockchain.

##### Investigating transaction acceleration services

We examined transaction acceleration services offered by $5$ large Bitcoin
mining pools namely, BTC.com BTC.com, (2022), AntPool AntPool, (2022), ViaBTC
ViaBTC, (2022), F2Pool F2Pool, (2022), and Poolin Poolin, (2022).
Specifically, we queried BTC.com for the prices of accelerating all
transactions in a real-time snapshot of the Mempool in data set $\mathcal{C}$
(see §A.7). We found that the dark fee requested by BTC.com to accelerate each
transaction is so high that if it was added to the publicly offered
transaction fee, the resulting total fee rate would be higher than the fee
rate offered by any other transaction in the Mempool snapshot. Put
differently, had users included the requested acceleration fees in the
publicly offered fee when issuing the transaction, every miner would have
included the transaction with the highest priority.

The above observation raises the following question: why would rational users
offer a dark fee to incentivize a subset of miners to prioritize their
transaction rather than publicly announce the fee to incentivize all miners to
prioritize their transaction? One potential explanation could be that as
payment senders determine the publicly offered transaction fees, payment
receivers might wish to accelerate the transaction confirmation by offering an
acceleration fee. Another explanation could be that the user issuing the
transaction might want to avoid revealing the true fees they are willing to
offer publicly, to avoid a fee rate battle with transactions competing for
inclusion in the chain during congestion. Opaque transaction fees can reduce
transaction cost volatility, but they may also unfairly bias the level playing
field amongst user transactions attempting to front-run one another Strehle
and Ante, (2020); Daian et al., (2020).

On the other hand, every rational mining pool has clear incentives to offer
such acceleration services. They receive a very high fee by mining the
accelerated transaction. Better still, they keep the offered fee, even if the
accelerated transaction were mined by some other miners.

##### Detecting accelerated transactions

Table 3.6: [Data set $\mathcal{C}$] For an SPPE $\geq$ 99%, we observe that
64.98% of BTC.com transactions were accelerated; the fourth column values are
derived by dividing the values in the second with those in the third. The
number of accelerated transactions decreases to 18.12% for an SPPE $\geq$ 90%
and to 1.06% for an SPPE $\geq$ 50%.

SPPE ($\geq$) | # txs | # acc. txs | % acc. txs
---|---|---|---
$100\%$ | $628$ | $464$ | $73.89$
$99\%$ | $1108$ | $720$ | $64.98$
$90\%$ | $5365$ | $972$ | $18.12$
$50\%$ | $95282$ | $1007$ | $1.06$
$1\%$ | $657423$ | $1029$ | $0.16$

Given the high fees demanded by acceleration services, we anticipate that
accelerated transactions would be included in the blockchain with the highest
priority, i.e., in the first few blocks mined by the accelerating miner and
amongst the first few positions within the block. We would also anticipate
that without the acceleration fee, the transaction would not stand a chance of
being included in the block based on its publicly offered transaction fee. The
above two observations suggest a potential method for detecting accelerated
transactions in the Bitcoin blockchain: An accelerated transaction would have
a very high signed position prediction error (SPPE), as its predicted position
based on its public fee would be towards the bottom of the block it is
included in, while its actual position would be towards the very top of the
block.

To test the effectiveness of our method, we analyzed all $6381$ blocks and
$13395079$ transactions mined by BTC.com mining pool in data set
$\mathcal{C}$. We then extracted all transactions with SPPE greater or equal
than $100\%$, $99\%$, $90\%$, $50\%$, $1\%$ and checked what fraction of such
transactions were accelerated. Given a transaction identifier, BTC.com’s
acceleration service BTC.com, (2022) allows anyone to verify whether the