11institutetext: TU Wien, Austria 22institutetext: University of Warsaw,
Poland 33institutetext: IDEAS NCBR, Poland

#  Bribe & Fork:
Cheap PCN Bribing Attacks via Forking Threat

Zeta Avarikioti 11 Pawel Kedzior 22 Tomasz Lizurej 2233 Tomasz Michalak 2233

###### Abstract

In this work, we reexamine the vulnerability of Payment Channel Networks
(PCNs) to bribing attacks, where an adversary incentivizes blockchain miners
to deliberately ignore a specific transaction to undermine the punishment
mechanism of PCNs. While previous studies have posited a prohibitive cost for
such attacks, we show that this cost may be dramatically reduced (to
approximately $125), thereby increasing the likelihood of these attacks. To
this end, we introduce Bribe & Fork, a modified bribing attack that leverages
the threat of a so-called feather fork which we analyze with a novel formal
model for the mining game with forking. We empirically analyze historical data
of some real-world blockchain implementations to evaluate the scale of this
cost reduction. Our findings shed more light on the potential vulnerability of
PCNs and highlight the need for robust solutions.

##  1 Introduction

The financial world was transformed by blockchains such as Bitcoin [27] and
Ethereum [35]. While blockchains offer a number of benefits, their scalability
remains a significant challenge when compared to traditional centralized
payment systems [15]. One promising solution to this issue is the so-called
_payment channel networks (PCNs)_ that move most of the transaction workload
off-chain [20].

Several PCN proposals [6, 7, 8, 9, 11, 16, 17, 18, 19, 21, 28, 31] have been
laid forward so far, each design offering some unique combination of features.
Nonetheless, the core idea behind payment channels remains the same, that is
to facilitate off-chain transactions among parties connected, either directly
or indirectly via a path, on a network operating on top of the blockchain
layer, the PCN.

To participate in a PCN, two parties can lock funds in a joint account on-
chain, thereby opening a payment channel. Subsequently, the parties can
transact off-chain by simply updating (and signing) the distribution of their
funds. When either party wants to settle the account, or in other words close
the payment channel with its counterparty, they can publish the last agreed
distribution of the channel’s funds. However, each update constitutes a valid
closure of the channel from the perspective of the blockchain miners. As a
result, a malicious party may publish an outdated update to close the channel
holding more than it currently owns. To secure the funds against such attacks,
payment channels enforce a _dispute period_. During this period, the funds
remain locked to allow the counterparty to punish any malicious behavior, and
if so, claim all the funds locked in the channel.

Hence, the security of PCNs, like the most widely deployed Bitcoin Lighting
Network [28], crucially relies on financial incentives. Specifically, during
the dispute period, the punishment mechanism should enforce that a malicious
party is always penalized and an honest party should never lose its funds.
Unfortunately, this is not always the case, as argued by Khabbazian et al.
[26] and Avarikioti et al. [10]. For instance, Lighting channels are
susceptible to the so-called _timelock bribing attacks_. In such an attack, a
malicious party posts an old update transaction on-chain, attempting to close
its channel with more funds than it presently possesses. Concurrently, the
party bribes the miners to ignore the punishment transaction of the
counterparty for the duration of the dispute period. This bribe is typically
offered to the miners in the form of high transaction fees.

Naturally, the success of this attack depends on the value of the bribe.
Avarikioti et al. [10] showed that a bribing attack will be successful if the
bribe is no smaller than: $\dfrac{f_{1}-f}{\lambda_{min}},$ where
$\lambda_{min}$ is the fraction of the mining power controlled by the least
significant miner in the underlying proof-of-work blockchain, $f_{1}$ is the
sum of the fees of a block containing the punishment transaction, and $f$ is
the sum of the fees of a block containing average transactions. We observe
however that as $\lambda_{min}$ may be arbitrarily small, the bribing amounts
required may significantly exceed the funds typically locked in PCNs,
rendering the bribing attack impractical. Moreover, even in blockchains with
rather concentrated mining power like in Bitcoin [22], the cost of a bribing
attack is very high. For example, conservatively assuming that the smallest
miner has $10^{-4}$ of the total mining power111In the Section 0.D.2, we
experimentally show, that the mining power of the weakest miner in the system
can be fairly assumed to be of magnitude $10^{-12}$., the cost of the attack
as analyzed in [10] would be at least $1$ BTC, for $f_{1}-f\approx 10^{-4}$
BTC. As a result, it would be irrational to perform a bribing attack of this
sort, as the average closing price for $1$ BTC between, for instance, 2019 and
2022 was $23,530.92$ USD222statmuse.com, which is more than 10-fold the
current total value locked on average in a Lighting
channel333https://1ml.com/statistics. This naturally leads to questioning
_whether there is potential to amplify such attacks to the extent they pose a
genuine threat to the security of PCNs._

####  1.0.1 Our Contribution.

In this work, we show that _bribing costs can be significantly reduced_ ,
thereby making timelock bribing attacks a realistic threat. We do so by
extending the bribing attack to leverage not only the structure of transaction
fees but also a threat to fork the blockchain, known as a _feather fork
attack_ [23, 30]. In our context, a given miner executes a feather fork attack
by announcing a self-penalty transaction $tx_{p}$. Whenever the self-penalty
transaction appears on the blockchain, the miner is incentivized to fork the
punishment transaction $tx_{1}$ on the blockchain, i.e., the miner will try to
extend the blockchain based on the predecessor of the block $tx_{1}$ including
some other block. Specifically, a feather-forking miner is bribed to commit
collateral, betting that their fork will win the race. As a consequence, their
threat of forking becomes considerably credible, incentivizing other miners to
follow their fork. The collateral is of a similar magnitude as the bribe in
[10], however, the miners only lock it _temporarily_. We call our attack Bribe
& Fork. With the feather fork at hand, the bribing cost may now be reduced
from $\frac{f_{1}-f}{\lambda_{min}}$ to approximately:

$\frac{2\overline{f}+2(f_{1}-f)}{\lambda_{s}},$

where $\overline{f}$ is the average fee of a single transaction, and
$\lambda_{s}$ is the mining fraction of the most significant miner. Recall
that $f_{1}$ and $f$ denote the sum of fees of a block containing the
punishment transaction and only average transactions respectively. To
demonstrate the cost reduction of Bribe & Fork, we reexamine the previous
example for Bitcoin, with $\overline{f}\approx 10^{-4}$ BTC,
$f_{1}-f\approx\overline{f}$, and $\lambda_{s}\approx 20\%$. Now,
$\lambda_{s}$ replaces in the denominator the previously presented
$\lambda_{min}<<10^{-4}$, thus _yielding a bribe at least 1000 times smaller
than the one in[10]_.

To derive this result, we present a formal model of mining games with forking,
extending the conditionally timelocked games introduced in [10]. In the game
with forks, miners may now choose, in each round, (a) which transactions to
mine, and (b) whether they want to continue one of the existing chains or they
intend to fork one of the chains. All miners know the choices of the winner of
each block, as a feather-forking miner locks collateral on-chain.

To empirically estimate the cost reduction of Bribe & Fork, we analyze the
historical data of real-world blockchain implementations. Among others, we
analyze the average block rewards and fees, as well as the hash power present
in the system and available to a single miner, primarily for Bitcoin in 2022.
Given the officially available data, we observe that _the cost of our attack
can be as cheap as $125_ (for 1 BTC $\approx$ $25.000). In general, the cost
of our attack can be up to $10^{10}$ times cheaper than the bribe required in
[10] according to our findings. Hence, even considering a collateral of around
$\$30,000$, Bribe & Fork is substantially more cost-efficient, and by
extension, more probable to occur.

##  2 The Bribe & Fork Attack

In this section, we first describe the necessary components of Bribe & Fork,
including feather fork attacks as well as timelock bribing attacks in the
setting of PCNs, and conclude with the description of the Bribe & Fork attack.

###  2.1 Necessary Components and Background

Timelocked Bribing Attack. Whenever miners decide to create a new block, they
select some set of transactions from all transactions posted on the mempool,
which is a database of all publicly visible transactions. Mining pools and
individual miners usually choose the transactions with the highest fees first,
as they are part of their reward for a successfully mined block. Miners are
aware that some transactions may be dependent on each other. For instance, two
transactions that spend the same Unspent Transaction Output (or UTXO) in
Bitcoin, cannot be both published on-chain; the transaction that is validated
first, i.e., is included on a block of the longest chain, immediately deems
invalid the other transaction. If from two interdependent transactions, only
one can be published directly, while the other is timelocked and thus can only
be published after some time elapses, we refer to this pair of transactions as
a _conditionally timelocked output_. This conditionally timelocked output is
the target of timelock bribing attacks: the owner of the coins of the
transaction that is valid only after the timelock expires attempts to bribe
the miners to ignore the currently valid competing transaction. Thus, for the
miners that observe transactions on the mempool, sometimes it may be
profitable to censor one transaction in order to mine another one that
provides a greater gain in the future.

Timelock Bribing in the Bitcoin Lightning Network. Next, we describe the
timelock bribing attack in the context of the most widely deployed payment
channel network, namely the Bitcoin Lightning Network (LN). In LN, a single
on-chain transaction called the funding transaction, opens a channel between
parties $\mathcal{P}_{1},\mathcal{P}_{2}$. Next, parties exchange with each
other signed messages off-chain which update the state of their accounts. If
the parties are honest and responsive, they may close the channel in
collaboration. To do so, the parties post a mutually signed transaction that
spends the output of the funding transaction and awards each party their fair
share of funds. However, if a dishonest party $\mathcal{P}_{2}$ attempts to
publish on-chain an old state that she profits from comparably to the latest
agreed state, her funds will remain locked for the so-called dispute period.
During this period, the other (rational) party $\mathcal{P}_{1}$ will try to
revoke the old state, by sending a transaction $tx_{1}$ to the mempool called
the revocation transaction (or breach remedy). Transaction $tx_{1}$ awards all
the channel funds to the cheated party $\mathcal{P}_{1}$. We denote by $f_{1}$
the miner’s fee to include a block with $tx_{1}$.

In this case, the malicious party $\mathcal{P}_{2}$ can launch a timelocked
bribing attack, attempting to bribe the miners to ignore $tx_{1}$ for the
dispute period $T$ such that $\mathcal{P}_{2}$ gains the additional funds.
Specifically, $\mathcal{P}_{2}$ may send in the mempool a block with fee
$f_{2}$ that includes transaction $tx_{2}$, with $f_{2}>f_{1}$, that is only
valid if no miner includes in their winning block containing $tx_{1}$ within
time $T$. Consequently, if the revocation transaction $tx_{1}$ is not
published on-chain within $T$, $\mathcal{P}_{2}$ can spend the funds of the
old state and the next winning miner will be awarded $f_{2}$. The pair of
transactions $tx_{1}$ and $tx_{2}$ is now a conditionally timelocked output.

Assuming that for an average block of transactions, the users get in total $f$
fees, the following holds [10]: if $f_{2}-f>\frac{f_{1}-f}{\lambda_{min}}$
then all rational miners will choose to wait for $T$ rounds and publish a
block containing $tx_{2}$.

Feather Fork Attack. A feather fork, as introduced in [24], is an attack on
Bitcoin wherein a miner threatens to fork the chain if selected transactions
are included. This intimidation mechanism aims to subtly alter the miners’
block acceptance policy: the threatened miners may exclude the selected
transactions in order to mitigate the risk of losing their mining reward [34].
As feather forking relies on economic incentives, the attacker may increase
their probability of success by bribing other miners to follow their short-
lived fork, e.g., committing to pay them the block rewards they may lose by
censoring the selected transactions.

Unlike a “hard” fork, where miners exclusively mine their own chain version
regardless of its length compared to other versions, a feather fork entails
mining on the longest chain that excludes selected transactions and does not
fall significantly behind its alternatives. A feather fork is thus less
disruptive and more likely to be adopted by the network, making it a
potentially powerful tool in the hands of a malicious actor. In this work, we
employ this tool to enhance the likelihood of a successful timelocked bribing
attack.

###  2.2 Bribe & Fork Attack

We now introduce our novel attack, termed Bribe & Fork, that combines the
timelock bribing attack in LN with the feather fork attack. We assume the
existence of a payment channel between parties $\mathcal{P}_{1}$ and
$\mathcal{P}_{2}$. Similarly to timelock bribing, we consider
$\mathcal{P}_{2}$ to be malicious and attempt to close the channel with
$\mathcal{P}_{1}$ in an old state using the transaction $tx_{2}$.
Consequently, $\mathcal{P}_{1}$ is expected to attempt to revoke the old
state. To prevent the inclusion of the revocation transaction,
$\mathcal{P}_{2}$ bribes the miner $N_{s}$ with the highest mining power
$\lambda_{s}$ to threaten others with a fork if they add the unwanted
transaction $txs_{1}$ on-chain. This action is implemented through a self-
penalty mechanism where the bribed miner temporarily locks collateral which
can only be reclaimed in case a block $txs_{2}$ containing $tx_{2}$ appears
on-chain (and thus any block $txs_{1}$ containing $tx_{1}$ is not included on-
chain). In essence, the bribed miner “bets” that the revocation transaction
will be censored, thus rendering the threat credible for the rest of the
miners.

To realize Bribe & Fork, there are two mechanisms that should be implementable
on-chain: a) the bribe transaction that should only be spendable if $txs_{2}$
is included on-chain, and b) the self-penalty mechanism that enables the
bribed miner $N_{s}$ to lock collateral $P$ (with transaction $tx_{p_{1}}$)
and then reclaim it only if $txs_{2}$ is included on-chain (with transaction
$tx_{p_{2}}$). We implement the bribing and self-penalty mechanisms in Bitcoin
script, using the conditioning enabled by the UTXO (Unspent Transaction
Output) structure. We note that in Ethereum, preparing a smart contract that
has access to the state of the closing channel suffices to implement the
bribing and self-penalty mechanisms.

In detail, a single bribing transaction $tx_{b}$ and two special transactions
$tx_{p_{1}},tx_{p_{2}}$ are introduced. Let us assume that the cheating party
$\mathcal{P}_{2}$ is bribing the miners to launch the attack conditioned on
the inclusion of its transaction $tx_{2}$. To do so, $\mathcal{P}_{2}$ creates
a bribe transaction $tx_{b}$ with input the party’s money from $tx_{2}$ and
outputs three UTXOs, one given to the miner that mines this transaction, one
dummy output owned by player $N_{s}$ (i.e., the miner bribed to perform
feather forking), and one that returns the rest of the money to
$\mathcal{P}_{2}$. Now, $N_{s}$ creates a transaction $tx_{p_{1}}$, locking a
deposit $P$, that is spendable via a multisignature of $m$-out-of-$n$ parties
(e.g., $m=n/2$), one of which is $N_{s}$’s signature. Then, $tx_{p_{2}}$ is
created with two inputs: the output of $tx_{p_{1}}$ and the dummy output of
$tx_{b}$. Consequently, $tx_{p_{2}}$ is spendable only if it is signed by at
least $m$ parties of the predefined set $n$ and $tx_{2}$ is validated on-
chain. Upon receiving $tx_{p_{2}}$ signed by at least $m-1$ parties, $N_{s}$
signs and posts it on-chain. Assuming that no subset of size $m-1$ of the rest
$n-1$ parties will collude with the miner to spend the deposit, the deposit
can be claimed by the miner only if transaction $tx_{2}$ is included on-chain.
The security of this scheme depends on the selection of the $n-1$ parties,
which can be in principle conditioned on the honest majority assumption of the
blockchain via subsampling.

Now, the malicious party $\mathcal{P}_{2}$ together with a selected miner
$N_{s}$ can launch the Bribe & Fork attack as follows: They can create special
transactions $tx_{b}$ (as a companion transaction for $tx_{2}$) and the self-
penalty transactions $tx_{p_{1}},tx_{p_{2}}$ to publicly announce a credible
threat that the transaction $tx_{1}$ will be forked once it appears on the
blockchain. They publish these special transactions in the mempool as
transaction sets $txs_{2}$ (that contains $tx_{2}$ and $tx_{b}$) and
$txs_{p_{1}},txs_{p_{2}}$ (that contain $tx_{p_{1}},tx_{p_{2}}$,
respectively).

We show later that this attack significantly reduces the cost of the required
bribe from $\frac{f_{1}-f}{\lambda_{min}}$ to approximately
$\frac{2\overline{f}+2(f_{1}-f)}{\lambda_{s}}$. The required collateral that
is eventually reclaimed by the bribed miner is expected to be
$\lambda_{s}\cdot B$ (where $B$ is a constant in Bitcoin block reward
independent of the user fees), which is comparable to the original bribe
needed in [10]. Figure 1 illustrates the comparison of Bribe & Fork with [10],
while a figure depicting the details of Bribe & Fork can be found in the
Appendix 0.A.

250pt][t].32

(a)

250pt][t].32

(b)

250pt][t].32

(c)

Figure 1: Comparison of the scenarios: (a) Honest execution: once an old state
appears on-chain (black rectangle), $\mathcal{P}_{1}$ gets an option to revoke
this state with a transaction $tx_{1}$ (included in the block $txs_{1}$ which
is published in the first round). (b) Attack in [10]: the bribing party
publishes $tx_{2}$ and $tx_{b}$ included in a single block $txs_{2}$, with a
large miner fee (reversely proportional to the fraction of the mining power
$\lambda_{min}$ of the least significant miner). The miners skip mining
$txs_{1}$ in the first round, and mine $txs_{2}$ in the last round. (c) Bribe
& Fork: the bribing party publishes $txs_{2}$ with a fee sufficient to bribe
only the strongest miner (with $f_{2}-f$ reversely proportional to
$\lambda_{s}$). The strongest miner publishes the self-penalty transactions
$tx_{p_{1}},tx_{p_{2}}$ that can be mined in transaction sets
$txs_{p_{1}},txs_{p_{2}}$. In the first round, the miner $N_{s}$ locks
$P\approx\lambda_{s}\cdot B$ to the deposit transaction $tx_{p_{1}}$, thus
threatening other miners that they will be forked once $txs_{1}$ is mined
before the deadline. After the deadline the transaction set $txs_{2}$ is
published and the miner $N_{s}$ may collect back the deposit using
$txs_{p_{2}}$.

##  3 Our Model

In this section, we introduce our model of PoW mining that takes into account
the forks. First, we present the assumptions of our model and then introduce a
set of new notions; a summary of our notation can be found in Table 1
(Appendix 0.B). Finally, we define the game that models the process of mining.

###  3.1 Assumptions

We introduce the assumptions that allow us to systematically study the
behavior of the players who take part in PoW mining process.

Average transactions. In Section 0.D.1, based on empirical data, we show how
block rewards fluctuate in the real-world. However, following [10], we assume
that standard transactions have a constant (average) reward and that all
blocks have a constant number of transactions. We refer to each standard
transaction as an average transaction.

Credible vs non-credible threats. In the mining process, players have the
ability to threaten other players that they will fork their blocks, once these
blocks appear on the blockchain, similar to the feather forking attacks.
However, we make the assumption that the players will not conduct the forking
action if it results in financial losses to them, i.e., we rule out _non-
credible_ threats. The acceptance of non-credible threats can lead to a
destabilization of the system, where multiple users try to threaten the other
players with the aim to control the order of the transactions. We thus stay
with the conservative assumption and accept only credible threats, i.e.
threats coming from a player that profits from forking a selected transaction.
In other words, we look only for the solutions that dominate other strategies
in every _subgame_ of the game.

Abandon rules for forked states. In general, miners have the option to fork a
chain or mine one of the existing chains from an arbitrary block of the chain.
However, forking that starts at some old block is unrealistic; hence, we
exclude this possibility from the game (following [24, 34, 29]). In other
words, miners in our model can fork only the last transaction on one of the
chains, and then either the original chain or the fork becomes stable whenever
it reaches a length equal to the length of the original chain plus one. The
forks can be modelled differently, e.g. assuming a longer fork length or using
a finite automaton definition. We expect our results to hold in the
alternative modelling as well, although the parameters of our solution could
change.

Fixed number of rounds or fixed number of blocks. In our model, we assume that
the game lasts for a fixed number of rounds. Alternatively, we could consider
a scenario where the game lasts until the main chain reaches a predefined
length. The first assumption is more suitable for the time periods when the
block rate is constant. On the other hand, the second modeling approach is
better for longer periods where the mining difficulty of blockchains is
adjusted to achieve a given number of blocks within a given time unit.

PoW Mining. We focus on proof-of-work blockchains that employ the so-called
Nakamoto consensus extending the longest chain, such as Bitcoin [27]. We
assume that in such environments miners (players) tend to form mining pools to
(a) bypass the task of verifying transactions – the pool’s manager dispatches
a list of valid transactions for inclusion – and more importantly, (b) to
guarantee a more stable income as individual mining carries substantial
deviation. Empirical evidence supporting this assumption, drawn from Bitcoin,
will be detailed in Section 0.D. For the rest of this work, each miner is
assumed to either mine independently or stick to a selected mining pool for
the whole course of the game, i.e., we will treat the mining pools as single
players in the game.

Furthermore, in our analysis, we assume that typically there exists a miner
that has a mining power of at least $20\%$ of the total hash power. This
assists the execution of the feather-fork attack that requires a credible
threat, i.e., a threat by a player with relatively strong mining power.
Moreover, we assume that there exists at least one other player in the game
that has a mining power slightly higher than $1\%$ and that no players with
overwhelmingly small mining power (less than a $10^{-100}$ fraction of the
total mining power) participate in the game. We back these assumptions with a
detailed analysis of the distribution of miners’ computing power on real-life
data in Section 0.D.2.

Preventing shallow forks. In Conjecture 1, we assume that players will have
the option to fork some transaction only when they see an explicit opportunity
of mining some transaction _in the future_ , initially blocked by the
currently forked transaction. In other words, we assume that players will fork
what we call “average” transactions. That is, we forbid shallow forks in the
model. This is because, in the real-world, excessive forking can trigger a
denial of service attack on the blockchain. Thus, it is very unlikely that
miners will follow the strategy of forking arbitrary transactions.

###  3.2 Preliminaries

Let us begin by recalling the conditionally-timelocked output definition from
[10].

######  Definition 1 (Conditionally timelocked output - quoted from [10])

A conditionally timelocked transaction output $txo(T_{0},T,cond_{1},cond_{2})$
is a transaction output of a transaction $tx$ with spending condition
$cond_{1}\lor cond_{2}$. Condition $cond_{1}$ is not encumbered with any
timelock and condition $cond_{2}$ is encumbered with a timelock that expires
$T$ blocks after the block with height $T_{0}$, where $tx$ was published.

The game will last $R$ rounds and will be defined for a fixed set of players
(miners) $N=\left\\{N_{1},\ldots,N_{n}\right\\}$ with a tuple of mining powers
$\boldsymbol{\lambda}=(\lambda_{1},\ldots,\lambda_{n})$.

Global State Object. We introduce a global state object
$\mathcal{S}=\\{S_{1},\ldots,S_{|S|}\\}$ that describes a set of currently
mined chains on the Blockchain. Each $S_{i}$ consists of a _list_ (chain) of
pairs
$S_{i}=\left[(\mathsf{block}_{1},W_{1}),\ldots,(\mathsf{block}_{|S_{i}|},W_{|S_{i}|})\right]$
describing successfully mined blocks. In each pair
$(\mathsf{block}_{j},W_{j})\in S_{i}$, $\mathsf{block}_{j}$ describes a set of
transactions included in the block and $W_{j}\in N$ indicates a player that
successfully mined the block.

The Set of Possible Actions. All chains in a state can be continued. When this
operation is successful, a new pair $(\mathsf{block},W)$ is appended to the
continued chain in the state. Chains of length at least $1$ in the state can
be forked. Whenever one of the players successfully forks, the new (duplicate)
chain is created in the following manner:

  * •

the source fork is duplicated; and

  * •

a new block replaces the latest block in the duplicate.

For instance, let $\mathcal{S}=\\{\
[(\mathsf{block}_{1},W_{1}),(\mathsf{block}_{2},W_{2})]\ \\}$ be a current
state with a single chain $S_{1}$. Then, after a successful fork of $S_{1}$
with $(B_{3},W_{3})$, one gets $\mathcal{S}=\\{\
[(\mathsf{block}_{1},W_{1}),(\mathsf{block}_{2},W_{2})],[(\mathsf{block}_{1},W_{1}),(\mathsf{block}_{3},W_{3})]\
\\}$.

Types of Transaction Sets. Each block mined in the game (denoted as
$\mathsf{block}$) includes only one of the transaction sets listed below.
Further, the block can be appended to the blockchain, whenever all of the
following conditions are met:

  * •

An unlimited amount of unrelated transaction sets $txs_{u}$ that contain
average transactions $tx_{u}$ unrelated to any special transactions listed
below. These transaction sets can be mined at any point in the game.

  * •

A transaction set $txs_{1}$ that contains the transaction $tx_{1}$ that spends
money of $txo$ under $cond_{1}$. As long as $txo$ is not spent, this
transaction set can be mined on a chain of any length. The rest of the
transactions in this transaction set are unrelated transactions $tx_{u}$.

  * •

A (bribing) transaction set $txs_{2}$ that contains the transaction $tx_{2}$
that spends money of $txo$ under $cond_{2}$ and a bribing transaction
$tx_{b}$. As long as $txo$ is not spent, this transaction set can be mined on
a chain of length $\geq T$. The rest of the transactions in this transaction
set are unrelated transactions $tx_{u}$.

  * •

A special transaction set $txs_{p_{1}}$. In the first round of the game, one
of the players (say $N_{1}$) might decide to create a transaction set
$txs_{p_{1}}$ with a self-punishment transaction $tx_{p_{1}}$ (see the
description of the penalty mechanism in the Section 3.1). The player chooses
amount $P$ which he deposits to the transaction. The rest of the transactions
in this transaction set are unrelated transactions $tx_{u}$.

  * •

A special transaction set $txs_{p_{2}}$ with transaction $tx_{p_{2}}$. The
transaction $tx_{p_{1}}$ assures that the player $N_{1}$ that created the
transaction $tx_{p_{1}}$ may collect back the deposit $P$ by publishing the
transaction $tx_{p_{2}}$, but only after the transaction set $txs_{2}$ is
published on the blockchain (see the Section 3.1). The rest of the
transactions in this transaction set are unrelated transactions $tx_{u}$.

Given the set of players $N$ and the set of transaction sets possible to mine,
one can define the set $\mathbb{S}$ of all states that may happen in the game.

Rewards. We assume that a miner, after successfully mining a transaction set
$txs_{i}$ on the main chain, gets a reward $\mathsf{reward}(txs_{i})$ equal to
$B+f_{i}+P$, where $B$ is a constant block reward and $f_{i}$ is a sum of user
fees input by users posting transactions in the transaction set $txs_{i}$.
Whenever $txs_{i}$ contains a transaction which locks C coins from miner’s
account, we set P to be equal to $-C$. Analogously, when a miner collects $C$
as one of the transactions from $txs_{i}$, we set the parameter $P$ to $C$.
The reward for mining a block depends on the number of transactions within the
block and their fees. The fee for a more complex transaction is typically
higher as it occupies more space in a block. In this respect, we make the
following assumptions that correspond to the current Bitcoin values (see
Section 0.D.1 for more details):

  * •

Each unrelated transaction set $txs_{u}$ has on average $m$ transactions, its
reward

$\mathsf{reward}(txs_{u})=B+f=B+m\cdot\overline{f},$

where $\overline{f}$ is an average user transaction fee. We also assume that
$\overline{f}<10^{-4}B$.

  * •

For other transaction sets with an uncommon functionality e.g., $txs_{j}$, we
assume it contains in total $m-c_{j}$ unrelated (average) transactions, a
special transaction $tx_{j}$ that takes space of $c_{j}$ average transactions,
where $c_{j}<m$. In total,

$\mathsf{reward}(txs_{j})=B+(m-c_{j})\overline{f}+c_{j}\overline{f_{j}}+P=B+f_{j}+P,$

where $f_{j}=(m-c_{j})\overline{f}+c_{j}\overline{f_{j}}$. The interpretation
of the parameter $c_{j}$ is that it describes the number of transactions
needed in a block to implement the uncommon functionality, each of them with
fee $\overline{f_{j}}$.

Mining Power Distribution. We assume the following mining power allocation
among the players (see Section 0.D.2), denoted
$\lambda=(\lambda_{1},\ldots,\lambda_{n})$:

  * •

There exists a single ”strong” player (say player $s$) with mining power
$\lambda_{s}\geq 20\%$, all other players have mining power smaller than
$\lambda_{s}$.

  * •

There exists a ”relatively” strong player (say player $i$) with mining power
$1\%<\lambda_{i}<2\%$.

  * •

We assume that all players with mining power less than $1\%$ have collective
power at most $5\%$.

  * •

The smallest mining power is of any miner in the game is
$\lambda_{min}>10^{-100}$.

The Abandon Rule. Let us define the abandon rule
$\mathsf{abandon}:\mathbb{S}\rightarrow\mathbb{S}$ that makes a chain the only
chain in the game whenever it outruns the length of other chains in the game.
That is, for any $S_{i}\in\mathcal{S}$: $\exists_{S_{j}\in\mathcal{S}}\
len(S_{j})\geq len(S_{i})+1$ then the abandon rule removes $S_{i}$ from the
state $\mathcal{S}$.

No Shallow Forks Conjecture. We conjecture that players will not start shallow
forks in the game. Shallow forks occur whenever miners fork a transaction that
does not explicitly block an opportunity to mine some other transaction in the
future.

######  Conjecture 1 (No shallow forks)

At any point in the game $\Gamma_{F}$, the players will not start a fork of a
chain ending with a transaction set $txs_{a}$, unless they see an explicit
opportunity to mine a fork containing at some point $txs_{b}$, initially
blocked by $txs_{a}$ (e.g. by the conditionally timelocked output transaction
mechanism, or the self-penalty mechanism). What is more the players must be
aware that $\mathsf{reward}(txs_{b})>\mathsf{reward}(txs_{a})$.

Note that given the set of feasible transaction sets in the Section 1 and the
reward structure defined in the Section 3.2, whenever
$\mathsf{reward}(txs_{2})>\mathsf{reward}(txs_{1})$ and
$\mathsf{reward}(txs_{1})>\mathsf{reward}(txs_{p_{1}})$, according to the
Conjecture 1 the players in our game can make an attempt to fork only
$txs_{1}$ to get $txs_{2}$ or $txs_{p_{1}}$ to mine $txs_{1}$. In other words,
whenever $txs_{u},txs_{2},$ or $txs_{p_{2}}$ appear on one of the chains, they
will not be forked.

###  3.3 The Game

Finally, we describe a game that models the process of Proof-of-Work
blockchain mining taking into account the option to conduct a forking of a
block. The game proceeds in rounds, in each round the miners are able to
choose whether they want to continue mining one of the chains or they want to
fork one of the chains.

######  Definition 2 (Conditionally timelocked game with forks)

A _conditionally timelocked game with forks_ $\Gamma_{F}(N,R)$ is a game with
a finite set of players (miners) $N=\left\\{N_{1},\ldots,N_{n}\right\\}$,
where $n=|N|$, that lasts $R$ rounds. We define a tuple of mining powers
$\boldsymbol{\lambda}=(\lambda_{1},\ldots,\lambda_{n})$ associated with the
players, such that $\sum_{\lambda_{i}\in\lambda}=1$. In the following, we will
simply write $\Gamma_{F}$, instead of $\Gamma_{F}(N,R)$, when $N,R$ are
obvious from the context.

Given the global state object, the set of possible actions, the rewards
structure and the mining power distribution defined above, the game is played
as follows:

  1. 1.

The game starts with the state $\mathcal{S}=\\{[\ ]\\}$ which is updated
exactly $R$ times. All players are aware that this state is built upon a
blockchain of height $T_{0}$ which includes an unspent conditionally
timelocked transaction output $txo(T_{0},T,cond_{1},cond_{2})$, where $T<R$.

  2. 2.

At each round $1\leq r\leq R$, players $N_{i}\in N$ choose which of the
subchains $\mathcal{S}_{k}\in\mathcal{S}$ they build upon, whether whey will
_continue_ or _fork_ this chain and which of the feasible blocks (built upon
one of the transaction sets) they want to add in case they are declared as the
winner. Let $\Omega\left(S,r\right)$ denote the set of all feasible actions
for the state $(\mathcal{S},r)$ described as triplets
$(S,\mathsf{decision},\mathsf{transaction\\_set})$, where $S\in\mathcal{S}$,
and $\mathsf{decision}\in\\{\mathit{continue},\mathit{fork}\\}$. Based on
$\boldsymbol{\lambda}=(\lambda_{1},\ldots,\lambda_{n})$, one player is
declared as the winner in the round $r$, and the state object is modified
accordingly.

  3. 3.

After each round, the abandon rule $\mathsf{abandon}$ is run on the current
state.

When the final round $R$ of the game is over, it finishes in some state
$\mathcal{S}$ and rewards are given to the players. By $\mathcal{S}^{*}$ let
us denote the longest chain in the state $\mathcal{S}$. Whenever the state has
multiple longest chains, $\mathcal{S}^{*}$ denotes the oldest of the longest
chains of $\mathcal{S}$. After the final round $R$, in the state
$\mathcal{S}$, the reward given to a player $N_{i}$ is:
$\mathsf{reward}_{i}(\mathcal{S})=\sum_{(\mathsf{block},W)\in\mathcal{S}^{*}:W=i}\mathsf{reward}(\mathsf{block}).$

Strategies. A strategy $\sigma_{i}$ for a player $N_{i}$ is given by a
function mapping each pair $(\mathcal{S},r)\in\mathbb{S}\times[R]$ to a
triplet feasible for this pair
$(S,\mathsf{decision},\mathsf{transaction\\_set})$.
Let $\sigma$ denote a strategy profile of all players - a tuple of strategies
of all players - i.e. $\sigma=(\sigma_{1},\ldots,\sigma_{n})$.

The distribution of mining power among the players
$\boldsymbol{\lambda}=(\lambda_{1},\ldots,\lambda_{n})$, the strategy profile
$\sigma$, current state $\mathcal{S}\in\mathbb{S}$ and current round $r\in[R]$
define a probability distribution function
$\boldsymbol{p}_{\boldsymbol{\lambda},\sigma,\mathcal{S},r,r^{\prime}}:~{}\mathbb{S}~{}\rightarrow[0,1]$
that assigns a probability that a certain state
$\mathcal{S}^{\prime}\in\mathbb{S}$ is activated after round
$r^{\prime}\in[R]$, where $r^{\prime}>r$.

Given $\boldsymbol{p}_{\boldsymbol{\lambda},\sigma,\mathcal{S},r,r^{\prime}}$
and the $\mathsf{reward}$ function, we can define the utility (the expected
reward) $\boldsymbol{\mathbb{E}}_{i}(\sigma)$ of each player $i$, when
strategy $\sigma$ is played.

We denote by $\Gamma_{F}^{\mathcal{S},r}$ the subgame of the game $\Gamma_{F}$
in a round $r$, at a state $\mathcal{S}$. We denote by
$\boldsymbol{\mathbb{E}}_{i}(\sigma,\mathcal{S},r)$ the utility of a player
$N_{i}$ in this subgame which is the expected reward for this player, once the
game is over.

##  4 Analysis

Here, we present a summary of our analysis that can be found in Appendix 0.C.

We prove that the Bribe & Fork attack is effective in a sequence of steps. We
begin by showing that once the dispute period is over (miners mine on a chain
of length $\geq T$), then all the players will mine the transactions with
higher fees first (Lemmas 1 and 2, Appendix 0.C.1). Next, we analyze how the
miners behave when the self-penalty mechanism is not employed. Specifically,
in Section 0.C.2, we show that without the self-penalty mechanism, each miner
that already mined the block $txs_{1}$, will continue to mine this block even
when some other player starts to fork this block (Theorem 4). Equipped with
this knowledge, the rest of the miners will be discouraged to fork the block
$txs_{1}$. Leveraging this result, we then prove in Section 0.C.3, that the
majority of the miners will not fork the block $txs_{1}$ in the game without
the self-penalty mechanism (Theorem 4). Formally,

[]thmcontinuemining Let $\Gamma_{F}(\mathcal{S},r+1)$ be a subgame in a state
that contains a single chain of length $r\leq T$. The $txs_{p_{1}}$ was not
created and a player $N_{j}$ mined $txs_{1}$ in the last round. The player
$N_{j}$ will $\mathsf{continue}$ to mine this chain unless $f_{2}-f\geq
f_{1}+B$, even when other miners decide to fork the chain with $txs_{1}$ and
$\mathsf{continue}$ mining the new subchain created during the fork.

[]thmnoforks Let $\Gamma_{F}(\mathcal{S},r+1)$ be a subgame in a state
$\mathcal{S}$ that contains only a single chain of length $r$ consisting of
$r-1$ unrelated transaction sets $txs_{u}$ and one (just mined) $txs_{1}$
(mutually exclusive with $txs_{2}$ with
$\mathsf{reward}(txs_{2})>\mathsf{reward}(txs_{1})>\mathsf{reward}(txs_{u})$)
mined by some miner $N_{j}$. The $txs_{p_{1}}$ was not created and $r\leq T$.
Other miners will not fork $txs_{1}$, unless $f_{2}-f\geq\lambda_{j}(f+B)$,
where $\lambda_{j}$ is the mining power of the miner $N_{j}$. These two
results let us prove in Section 0.C.4 that in the game with forks where the
self-penalty mechanism is not used, the miners will choose to mine $txs_{1}$
in the first round if there exists a player (say player $N_{j}$) with
significantly big mining power $>0.01$ that is not encouraged to wait for
$txs_{2}$, i.e., $f_{2}-f<\frac{f_{1}-f}{\lambda_{j}}$. The result, formally
stated below, is analogous to the result from the game without forks defined
in [10]. []thmtxsone Let $\Gamma_{F}(\mathcal{S},1)$ be a subgame where none
of the miners decides to create $txs_{p_{1}}$ before the first round, and the
bribing fee is not too high, i.e. $f_{2}-f<10^{-2}(f+B)$. What is more
$f_{1}>f$, and if we define
$Y=\sum_{j=i:\lambda_{j}>0.01,f_{2}-f<\frac{f_{1}-f}{\lambda_{j}}}^{|N|}\lambda_{j}$,
then $T,Y$ are big enough, such that $(1-1.01(1-Y)^{T})>0$. Every miner with
$\lambda_{j}>0.01$ will decide to mine $f_{1}$ in the first round. After
determining the behaviour of miners when enabling forks (without the self-
penalty), we proceed to study the effect of the self-penalty mechanism. We
first define a penalty that (i) forces the selected miner $N_{s}$ with mining
power $\lambda_{s}$ to fork $txs_{1}$ once it appears on-chain, and (ii) poses
a threat strong enough that all the miners avoid mining $txs_{1}$ before the
chain length $T$ is reached (Theorem 4).

[]thmtxstwo Let $\Gamma_{F}(\mathcal{S},2)$ be a subgame where $txs_{p_{1}}$
defined by a player $N_{s}$ with mining power $\lambda_{s}$ was mined in the
first round with $P>\lambda_{s}(f+B)$. What is more
$f_{2}-f>\frac{f_{1}-f}{\lambda_{s}}$, and
$\frac{f+B}{f_{1}+B}>1-\lambda_{s}^{2}$. None of the miners will decide to
mine $txs_{1}$ in rounds $2,\ldots,T$. We conclude our analysis with the
following result, which states that, overall, using the self-penalty mechanism
and mining $txs_{2}$ is more profitable for all players than mining $txs_{1}$
in the first round. We prove Theorem 4 in Section 0.C.6.

[]thmmain Let $\Gamma_{F}$ be a game with forks that starts with an empty
state $\mathcal{S}$, where
$10^{-2}(f+B)>f_{2}-f>\frac{2\overline{f}+2(f_{1}-f)}{\lambda_{s}}+\overline{f}$,
$\frac{f+B}{f_{1}+B}>1-\lambda_{s}^{2}$, $f_{1}>f$, $f_{p_{2}}>f$,
$\lambda_{min}>0.05^{T/2}$ and given
$Y=\sum_{j=i:\lambda_{j}>0.01,f_{2}-f<\frac{f_{1}-f}{\lambda_{j}}}^{|N|}\lambda_{j}$,
it holds that $(1-1.01(1-(1-Y)^{T/2})>0$. The dominating strategy for all
players in the game $\Gamma_{F}$ is is to mine $txs_{p_{1}}$ with
$P>\lambda_{s}(f+B)$ created before the first round by the strongest player
$N_{s}$ with the mining power $\lambda_{s}$, then mine $txs_{u}$ until round
$T$, then $txs_{2}$, $txs_{p_{2}}$, and $txs_{u}$ until the end.

##  5 Example Evaluation

Using the real-world data analysis of Bitcoin fees and hashpower distribution
in major PoW blockchains (see Appendix 0.D), we visualize the improvement our
bound $f_{2}-f>\frac{2\overline{f}+2(f_{1}-f)}{\lambda_{s}}+\overline{f}$
brings compared to the previous result from [10], namely
$f_{2}-f\geq\frac{f_{1}-f}{\lambda_{min}}$. Additionally, the Theorem 4
requires that $f_{2}-f<10^{-2}(f+B)$ and there exists a player $N_{j}$ with
mining power $\lambda_{j}>0.01$ for which
$f_{2}-f<\frac{f_{1}-f}{\lambda_{j}}$.

For example, let us assume that $f_{1}-f\approx\overline{f}$, and set $T>110$.
Now, since $\lambda_{min}$ can be fairly estimated to be
$\lambda_{min}<10^{-12}$, we can see that the attack without forking threats
could cost in practice around $10^{12}\overline{f}$. On the other hand, the
new bound requires only
$f_{2}-f>\frac{2\overline{f}+2(f_{1}-f)}{\lambda_{s}}+\overline{f}$, for
$\lambda_{s}\approx 0.2$, this costs around $f_{2}-f>21\overline{f}$. The only
condition left is that for some miner with $\lambda_{j}>0.01$, the following
condition must hold $f_{2}-f<\frac{f_{1}-f}{\lambda_{j}}$, but the data shows
that miners that control approximately $1.5\%-2\%$ of the total mining power
usually exist, thus for a miner with mining power $1\%<\lambda_{j}<2\%$ it
holds that $f_{2}-f<50\cdot\overline{f}$. In summary, if we take any $f_{2}$
that is larger than $f$ by $21$ up to $50$ times, then the default strategy
for all miners is to wait for the bribing transaction.

##  6 Related Work and Countermeasures

In the landscape of constructing financially stable systems on blockchain [25,
12], our work falls into the class of incentive manipulation attacks.
Specifically, to the best of our knowledge, we are the first to combine
feather forking attacks [13] with timelock bribing attacks on payment channel
networks and to achieve a bribing cost that is approximately only constant
times larger than the cost of an average transaction fee.

Incentive manipulation attacks on timelocked puzzles were introduced with the
so-called timelock bribing attack [26]. Later, Avarikioti et al. [10] applied
timelock bribing attacks in payment channel networks, such as the Lightning
Network and Duplex Micropayment Channels, and proposed countermeasures. Our
work extends [10], modifying the timelock bribing attack for payment channels
to facilitate a miner bribing strategy that incorporates feather forking. As a
result, our work reduces the cost of bribing attacks significantly in
comparison to [10], i.e., the cost is now inversely proportional to the mining
power of the largest miner instead of the smallest miner which results in at
least 1000 times smaller bribes.

The bribing strategies for the payment channels are similar in their nature to
the bribing strategies for the HTLC mechanism. Perhaps the closest to our work
is [34], where the authors introduced a way to bribe HTLCs, leveraging the
power of smart contracts and feather forking. The cost of the attack in [34]
is, however, proportional to the sum of the fees
($\gtrsim\sum_{i=1}^{T}f\cdot\lambda_{max}$) of all blocks before the deadline
$T$. In contrast, we achieve a cost proportional to the cost of fees of a
single block ($\gtrsim\frac{f_{1}-f}{\lambda_{S}}$).

Furthermore, MAD-HTLC [32] underlined the vulnerability of HTLCs to bribing
attacks, achieving the same attack cost as [10], specifically
$\approx\frac{f_{1}-f}{\lambda_{min}}$. MAD-HTLC presupposes that the minimum
fraction of mining power controlled by a single user, $\lambda_{min}$, is at
least $0.01$, to achieve low bribing costs. This is however an impractical
assumption, as the data in Appendix 0.D.2 show that $\lambda_{min}$ can be
reasonably estimated to be less than $10^{-12}$, making the bribing attack
exceedingly expensive. The reduction of the bribing costs Bribe & Fork
achieves in comparison to MAD-HTLC is similar to that of [10] analyzed above.

MAD-HTLC additionally proposed a countermeasure for bribing attacks where
miners are allowed to claim the locked coins in the HLTC in case a party
misbehaves, similar to [10]. Later, He-HTLC [33] pointed out that MAD-HTLC is
susceptible to counter-bribing attacks. In particular, one party may
(proactively) collude with the miners to cooperatively steal the coins of the
counterparty in the MAD-HTLC construction. He-HTLC also proposed a
modification on MAD-HTLC to mitigate the counter-bribing attack: now the coins
are partially burned in case of fraud instead of being fully awarded to the
miners. Recently, Rapidash [14] revisited the counter-bribing attack and
proposed yet another improvement on He-HTLC. These works are orthogonal to
ours as the proposed attacks apply only to the specific MAD-HTLC construction
and not to Lighting Channels that are the focus of this work. Furthermore, our
focus is not on designing countermeasures against timelocked bribing attacks.
Instead, we demonstrate how employing feather forking can make timelocked
bribing attacks very cheap for the attacker, therefore highlighting the need
for robust mitigating strategies.

Nonetheless, it is crucial to acknowledge that the previously mentioned
countermeasures can be used to defend against Bribe & Fork– inheriting their
respective vulnerabilities. For example, one can employ the mitigation
technique for timelocked bribing on the Lighting Network proposed by
Avarikioti et al. [10]. In our model, this countermeasure ensures that
announcing $txs_{2}$ also involves revealing a secret that anyone can use to
claim the money before time $T$. This implies that if $txs_{2}$ is announced
in the mining pool before time $T$, all the money to be collected only after
time $T$ can be immediately claimed by another party. We assert, without
proof, that the same countermeasure mechanism remains effective even in a
model that considers forks. Intuitively, the “strong” miner in our analysis
does not benefit from waiting for the bribing transaction if it is not
announced, thus preventing the creation of the self-penalty transaction.
Conversely, if the transaction is announced and the secret is revealed, any
(winning) miner could claim the reward money.

## References

  * [1] Blocks list in btc 2022.  https://explorer.btc.com/btc/blocks.  Accessed: 2023-10-06.
  * [2] Blocks list in etc 2022.  https://explorer.btc.com/etc/insights-pools.  Accessed: 2023-10-06.
  * [3] Blocks list in ltc 2022.  https://explorer.btc.com/ltc/insights-pools.  Accessed: 2023-10-06.
  * [4] Live income estimation of all known asic miners.  https://www.asicminervalue.com.  Accessed: 2023-10-06.
  * [5] Total hash rate (th/s) for bitcoin.  https://www.blockchain.com/explorer/charts/hash-rate.  Accessed: 2023-10-06.
  * [6] Aumayr, L., Ersoy, O., Erwig, A., Faust, S., Hostakova, K., Maffei, M., Moreno-Sanchez, P., and Riahi, S. Generalized bitcoin-compatible channels.  Cryptology ePrint Archive 2020 (2020), 476.
  * [7] Aumayr, L., Ersoy, O., Erwig, A., Faust, S., Hostakova, K., Maffei, M., Moreno-Sanchez, P., and Riahi, S. Bitcoin-compatible virtual channels.  In IEEE Symposium on Security and Privacy (2021).
  * [8] Aumayr, L., Thyagarajan, S. A., Malavolta, G., Moreno-Sanchez, P., and Maffei, M. Sleepy channels: Bi-directional payment channels without watchtowers.  In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security (2022), pp. 179–192.
  * [9] Avarikioti, Z., Kogias, E. K., Wattenhofer, R., and Zindros, D. Brick: Asynchronous incentive-compatible payment channels.  In International Conference on Financial Cryptography and Data Security (2021).
  * [10] Avarikioti, Z., and Litos, O. S. T. Suborn channels: Incentives against timelock bribes.  In Financial Cryptography and Data Security - 26th International Conference, FC 2022, Grenada, May 2-6, 2022, Revised Selected Papers (2022), vol. 13411 of Lecture Notes in Computer Science, Springer, pp. 488–511.
  * [11] Avarikioti, Z., Litos, O. S. T., and Wattenhofer, R. Cerberus channels: Incentivizing watchtowers for bitcoin.  In International Conference on Financial Cryptography and Data Security (2020), Springer, pp. 346–366.
  * [12] Bentov, I., and Kumaresan, R. How to use bitcoin to design fair protocols.  In Advances in Cryptology - CRYPTO 2014 - 34th Annual Cryptology Conference (2014), vol. 8617 of Lecture Notes in Computer Science, Springer, pp. 421–439.
  * [13] Bonneau, J., Miller, A., Clark, J., Narayanan, A., Kroll, J. A., and Felten, E. W. Sok: Research perspectives and challenges for bitcoin and cryptocurrencies.  In 2015 IEEE Symposium on Security and Privacy (2015), pp. 104–121.
  * [14] Chung, H., Masserova, E., Shi, E., and Thyagarajan, S. A. Rapidash: Foundations of side-contract-resilient fair exchange.  Cryptology ePrint Archive, Paper 2022/1063, 2022.  https://eprint.iacr.org/2022/1063.
  * [15] Croman, K., Decker, C., Eyal, I., Gencer, A. E., Juels, A., Kosba, A., Miller, A., Saxena, P., Shi, E., Sirer, E. G., Song, D., and Wattenhofer, R. On scaling decentralized blockchains.  In International Conference on Financial Cryptography and Data Security (2016), Springer, pp. 106–125.
  * [16] Decker, C., Russell, R., and Osuntokun, O. eltoo: A simple layer2 protocol for bitcoin.  https://blockstream.com/eltoo.pdf, 2019.
  * [17] Decker, C., and Wattenhofer, R. A fast and scalable payment network with bitcoin duplex micropayment channels.  In Stabilization, Safety, and Security of Distributed Systems (2015), Springer, pp. 3–18.
  * [18] Dziembowski, S., Eckey, L., Faust, S., and Malinowski, D. Perun: Virtual payment hubs over cryptocurrencies.  In 2019 IEEE Symposium on Security and Privacy (SP) (2019), IEEE, pp. 344–361.
  * [19] Dziembowski, S., Faust, S., and Hostáková, K. General state channel networks.  In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (2018), ACM, pp. 949–966.
  * [20] Gudgeon, L., Moreno-Sanchez, P., Roos, S., McCorry, P., and Gervais, A. Sok: Layer-two blockchain protocols.  In Financial Cryptography and Data Security - 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10-14, 2020 Revised Selected Papers (2020), J. Bonneau and N. Heninger, Eds., vol. 12059 of Lecture Notes in Computer Science, Springer, pp. 201–226.
  * [21] Jourenko, M., Larangeira, N., and Tanaka, K. Lightweight virtual payment channels.  In Cryptology and Network Security (2020), Springer International Publishing, pp. 365–384.
  * [22] Long, S., Basu, S., and Sirer, E. G. Measuring miner decentralization in proof-of-work blockchains.  arXiv preprint arXiv:2203.16058 (2022).
  * [23] Magnani, A., Calderoni, L., and Palmieri, P. Feather forking as a positive force: incentivising green energy production in a blockchain-based smart grid.  In Proceedings of the 1st Workshop on Cryptocurrencies and Blockchains for Distributed Systems (2018), pp. 99–104.
  * [24] Miller, A. Feather-forks: enforcing a blacklist with sub-50% hash power.
  * [25] Miller, A., and Bentov, I. Zero-collateral lotteries in bitcoin and ethereum, 2017.
  * [26] Nadahalli, T., Khabbazian, M., and Wattenhofer, R. Timelocked bribing.  In Financial Cryptography and Data Security - 25th International Conference, FC (2021), vol. 12674 of Lecture Notes in Computer Science, Springer, pp. 53–72.
  * [27] Nakamoto, S. Bitcoin: A peer-to-peer electronic cash system, 2008.  http://bitcoin.org/bitcoin.pdf.
  * [28] Poon, J., and Dryja, T. The bitcoin lightning network: Scalable off-chain instant payments.  https://lightning.network/lightning-network-paper.pdf (1 2016).
  * [29] Shahsavari, Y., Zhang, K., and Talhi, C. A theoretical model for fork analysis in the bitcoin network.
  * [30] Shalini, S., and Santhi, H. A survey on various attacks in bitcoin and cryptocurrency.  In 2019 International Conference on Communication and Signal Processing (ICCSP) (2019), IEEE, pp. 0220–0224.
  * [31] Spilman, J. Anti dos for tx replacement.  https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-April/002433.html, 2013\.  Accessed: 2020-11-22.
  * [32] Tsabary, I., Yechieli, M., Manuskin, A., and Eyal, I. MAD-HTLC: because HTLC is crazy-cheap to attack.  In 42nd IEEE Symposium on Security and Privacy, SP (2021), IEEE, pp. 1230–1248.
  * [33] Wadhwa, S., Stoeter, J., Zhang, F., and Nayak, K. He-htlc: Revisiting incentives in HTLC.  In 30th Annual Network and Distributed System Security Symposium, NDSS (2023), The Internet Society.
  * [34] Winzer, F., Herd, B., and Faust, S. Temporary censorship attacks in the presence of rational miners.  In 2019 IEEE European Symposium on Security and Privacy Workshops, EuroS&P Workshops (2019), IEEE, pp. 357–366.
  * [35] Wood, G. Ethereum: A secure decentralised generalised transaction ledger.  Ethereum Project Yellow Paper (2014).

##  Appendix 0.A Details of Bribe & Fork

The Figure 2 contains a diagram depicting the details of our attack. At first,
a Lightning Channel is opened with a single Funding transaction, and allows
parties $\mathcal{P}_{1},\mathcal{P}_{2}$ to make unlimited number of off-
chain state transitions of their funds. Once one of the parties
($\mathcal{P}_{2}$ in our example) decides to publish an old state ($comm_{i}$
in our example), the Game with forks $\Gamma_{F}$ begins. Before round $1$ of
the Game, the transactions $tx_{1}$ and $tx_{2}$ are published. Transaction
$tx_{1}$ allows $\mathcal{P}_{1}$ to revoke dishonestly committed state.
Transaction $tx_{2}$ allows $\mathcal{P}_{2}$ to collect and manage dishonest
funds after $T$ rounds. Along with $tx_{1}$ and $tx_{2}$, the bribing
transaction $tx_{b}$ and self-penalty transactions $tx_{p_{1}},tx_{p_{2}}$ are
published. In round $1$the miners may decide to mine the transaction
$tx_{p_{1}}$ that would lock some amount of coins of one of the miners (say
$N_{s}$). If so, all miners are threatened that they will be forked once
$tx_{1}$ appears on the blockchain until round $T+1$. In round $T+1$, the
transaction $tx_{2}$ along with bribing transaction $tx_{b}$ may be published
and the selected miner $N_{s}$ may collect back the deposit with the
transaction $tx_{p_{2}}$.

Figure 2: The Bribe & Fork attack. The transactions appear on a mempool before
the round that they are first shown in the diagram. The green boxes indicate
the transactions that should be put on-chain to run a successful Bribe & Fork
attack. The grey boxes indicate the transactions that should be published on
the mempool before given round. For instance, Spend transaction $tx_{2}$ has
to be published on the mempool before round $1$, even though it can not be
published on the blockchain until round $T+1$. The arrows going into the boxes
indicate the spending conditions of the transactions and the arrows going out
of the boxes indicate how the funds of the boxes can be spent.

##  Appendix 0.B Notation Summary

The Table 1 contains summary of the notation used in the proofs of the
theorems.

Symbol | Meaning
---|---
$N=\\{N_{1},\ldots,N_{|N|}\\}$ | Set of players (miners).
$\boldsymbol{\lambda}=(\lambda_{1},\ldots,\lambda_{|N|})$ | Tuple of mining powers of the players.
$\Gamma_{F}$ | Conditionally timelocked game with forks.
$\mathcal{S}=\\{S_{1},\ldots,S_{|\mathcal{S}|}\\}$ | Current state in the game consisting of a set of chains.
$R,r$ | Number of rounds in the game, current round in the game.
$tx_{i}$ | Single transaction that may be included in a transactions set.
$txs_{i}$ | Transactions set that may be mined to create a single block.
$B,P$ | The base of a transaction reward, the punishment added to
| (collected from) a block.
$f,\overline{f}$ | Fees of an average transaction set, fee of an average transaction.
$f_{i},\overline{f}_{i}$ | Fees of a transaction set with a transaction $tx_{i}$,
| fee of the transaction named $i$.
$tx_{u},tx_{1},tx_{2},tx_{b},tx_{p_{1}},tx_{p_{2}}$ | Transactions used to construct Bribe & Fork
| (see the paragraph ”Types of transaction sets.”).
$txs_{u},txs_{1},txs_{2},txs_{p_{1}},txs_{p_{2}}$ | Transaction sets that include transactions
| used to construct Bribe & Fork (see the paragraph
| ”Types of transaction sets.”).
$\mathsf{reward}(txs_{i})$ | Total reward from a transaction set.
$\mathsf{reward}_{i}(\mathcal{S})$ | The reward collected by a player $i$ in the state $\mathcal{S}$.
$\sigma=(\sigma_{1},\ldots,\sigma_{n})$ | The strategy of the players.
$\boldsymbol{\mathbb{E}}_{i}(\sigma),\boldsymbol{\mathbb{E}}_{i}(\sigma,\mathcal{S},r)$ | Utility of a player $i$, when strategy $\sigma$ is played, utility of the
| player $i$ in a subgame starting in state $\mathcal{S}$, round $r$ and
strategy $\sigma$.
$C$ | A constant describing the utility of players not considered
| in current analysis (see the paragraph ”About the proofs.”).
Table 1: Notation summary

##  Appendix 0.C Analysis of Bribe & Fork

In this section we formally analyze Bribe & Fork where a bribe transaction
$tx_{2}$ is published, large enough to bribe a chosen miner with the highest
mining power, yet significantly smaller than the value required to directly
persuade all miners to skip mining the transaction $txs_{1}$. The selected
miner is then asked to threaten others with a fork if they add the unwanted
transaction $txs_{1}$ to the blockchain. To make these threats credible, we
implemented the self-penalty mechanism (see Section 2.2)

About the proofs. In the proofs presented in this section, we aim to find a
dominating strategy for every player $N_{i}$ in a given state $\mathcal{S}$
and a round $r$. Whenever needed, we use the mathematical induction technique
to show that some choice of strategy is optimal for a sequence of rounds.
Usually, the base case is the last round of the game and the induction step
proves that if a given strategy is dominating in a round $k+1$, then it is
also a dominating strategy in a round $k$.

When we compare how the the player $N_{i}$ benefits from taking two distinct
actions $A,B$ in a given state $\mathcal{S}$ and a round $r$, we often say
that there exists a constant $C$ common for these strategies. To this end, we
assume that action $A$ refers to some strategy $\sigma_{a}$ of the player
$N_{i}$, and action $B$ refers to some strategy $\sigma_{b}$ of the player
$N_{i}$, such that $\sigma_{a}$ differs only in its definition from
$\sigma_{b}$ on the selected state $\mathcal{S}$ and the selected round $r$.
The utility of the player $N_{i}$ is the same for both strategies whenever in
the state $\mathcal{S}$ and $r$ someone else than $N_{i}$ is selected as the
winner of the round. With $C$ we denote the utility of player $N_{i}$
multiplied by probability of this event, when player $N_{i}$ is not the winner
of the round. This reasoning gives us an easy-to-use method to compare utility
between the strategies $\sigma_{a},\sigma_{b}$. We can thus compare the
utilities of the player $N_{i}$ in the state $\mathcal{S}$ and round $r$ when
the two distinct strategies $\sigma_{a},\sigma_{b}$ are selected as:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{a},\mathcal{S},r)=\lambda_{i}(\text{utility
of the player }N_{i}\text{ when action A was taken})+C,$
$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{b},\mathcal{S},r)=\lambda_{i}(\text{utility
of the player }N_{i}\text{ when action B was taken})+C.$

###  0.C.1 Transaction Order in a Single Chain

Although, due to the definition of the player’s utility function, the bribing
transaction ($txs_{2}$) may encourage the players not to skip mining
transactions with high rewards during the dispute period (e.g. $txs_{1}$), we
first show that once timelock is over and $txs_{1}$ was not mined, the players
will follow the default strategy to mine transactions with highest rewards
first.

###### Lemma 1

Let $\Gamma_{F}(\mathcal{S},T+1)$ be a subgame in a state
$\mathcal{S}=\\{S\\}$, where the state $\mathcal{S}$ contains a single chain
$S$ and the transaction set $txs_{p_{1}}$ was mined in the first round. In the
next $T-1$ rounds miners mined unrelated transactions sets $txs_{u}$.
Furthermore, it holds that

$\mathsf{reward}(txs_{2})>\mathsf{reward}(txs_{1})>\mathsf{reward}(txs_{u})\textit{
and }\mathsf{reward}(txs_{p_{2}})>\mathsf{reward}(txs_{u}).$

Then the dominating strategy for all players in the subgame
$\Gamma_{F}(\mathcal{S},T+1)$ is to mine transaction sets in the following
order: $txs_{2},txs_{p_{2}}$, and for the rest of rounds $txs_{u}$.

###### Proof

As $txs_{p_{1}}$ was mined in the first round, then in any round after the
round $T+1$ there are available to mine the following transaction sets:

  * •

mutually exclusive $txs_{1}$ and $txs_{2}$ with expired timelock,

  * •

one $txs_{p_{2}}$ that can be mined only after $txs_{2}$ appears on
blockchain,

  * •

and an unlimited amount of unrelated transaction sets $txs_{u}$.

Since only $txs_{1}$ and $txs_{2}$ are mutually exclusive and
$\mathsf{reward}(txs_{1})<\mathsf{reward}(txs_{2})$, then by Conjecture 1,
whenever $txs_{2}$, $txs_{p_{2}}$ or $txs_{u}$ appear on the blockchain, they
will not be forked. Thus only $txs_{1}$ may be forked in the subgame.

Once both $txs_{2},txs_{p_{2}}$ are on the chain, miners can not mine any
special transaction sets, and all of the miners will mine $txs_{u}$ till the
end of the game.

Next we show that for any round $r\in\\{T+2,\ldots,R\\}$, in a state
$\mathcal{S}^{\prime}$ created by extending the chain in $\mathcal{S}$ with
$txs_{u}$ and one $txs_{2}$ at any point in this chain, the dominating
strategy for all players is to mine $txs_{p_{2}}$ first if it was not mined
until this point. We will prove it by induction. The statement trivially holds
in the last round $R$, because $txs_{p_{2}}>txs_{u}$. Now, assuming that it
holds in round $R-k$, we prove that it also holds in round $R-k-1$. Any player
$N_{i}$ will be chosen with probability $\lambda_{i}$ as the winner of the
round. The utility of the player $N_{i}$ following a strategy $\sigma_{p_{2}}$
that first mines $txs_{p_{2}}$ in the state $\mathcal{S}^{\prime}$ is:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{p_{2}},\mathcal{S}^{\prime},R-k-1)=\lambda_{i}(\mathsf{reward}(\mathcal{S}^{\prime})+f_{p_{2}}+B+\lambda_{i}k(f+B))+C,$

for some constant $C$ that describes the expected reward of $N_{i}$ in case
he/she is not chosen as the winner of this round.

The utility of the player $N_{i}$ following a strategy $\sigma_{u}$ that first
mines $txs_{u}$ in the state $\mathcal{S}^{\prime}$ is:

$\boldsymbol{\mathbb{E}}_{i}(\sigma_{u},\mathcal{S}^{\prime},R-k-1)=\begin{cases}\lambda_{i}(\mathsf{reward}(\mathcal{S}^{\prime})+f_{u}+B)+C&\text{when
$k=0$}\\\
\lambda_{i}(\mathsf{reward}(\mathcal{S}^{\prime})+f_{u}+B+\lambda_{i}(f_{p_{2}}+B)+\lambda_{i}(k-1)(f+B))+C&\text{when
$k\geq 1$}\end{cases}$

From the above it follows that

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{p_{2}},\mathcal{S}^{\prime},R-k-1)>\boldsymbol{\mathbb{E}}_{i}(\sigma_{u},\mathcal{S}^{\prime},R-k-1).$

Next we show that for any $r\in\\{R,\ldots,T+1\\}$, in a state
$\mathcal{S}^{\prime\prime}$ created by extending the chain in $\mathcal{S}$
with $txs_{u}$, the dominating strategy for all players is to mine $txs_{2}$
first if it was not mined until this point. Observe that in the state
$\mathcal{S}^{\prime\prime}$ the miners can only mine $txs_{u},txs_{1}$ or
$txs_{2}$. The statement trivially holds in the last round. Now, assuming that
it holds in round $R-k$, we prove that it also holds in round $R-k+1$. Any
player $N_{i}$ will be chosen with probability $\lambda_{i}$ as the winner of
the round, and with probability $1-\lambda_{i}$ someone else will be selected
as the winner of the round. Then for some constant $C$, the utility of the
player $N_{i}$ in a strategy $\sigma_{2}$ that first mines $txs_{2}$ is

$\boldsymbol{\mathbb{E}}_{i}(\sigma_{2},\mathcal{S}^{\prime},R-k+1)=\begin{cases}\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}^{\prime\prime})+f_{2}+B)+C&\text{when
$k=0$}\\\
\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}^{\prime\prime})+f_{2}+B+\lambda_{i}(f_{p_{2}}+B))+C&\text{when
$k=1$}\\\
\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}^{\prime\prime})+f_{2}+B+\lambda_{i}(f_{p_{2}}+B)+(k-2)\lambda_{i}(f+B))+C&\text{when
$k\geq 2$}\end{cases}$

Whereas the utility of the player $N_{i}$ in a strategy $\sigma_{1}$ that
first mines $txs_{1}$ is

$\boldsymbol{\mathbb{E}}_{i}(\sigma_{1},\mathcal{S}^{\prime\prime},R-K+1)\leq\begin{cases}\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}^{\prime\prime})+f_{1}+B)+C&\text{when
$k=0$}\\\
\max\\{\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}^{\prime\prime})+f_{1}+B+\lambda_{i}(f+B))+C,&\text{when
$k=1$}\\\ \textit{
}\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}^{\prime\prime})+f_{2}+B)+C\\}&\\\
\max\\{\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}^{\prime\prime})+f_{1}+B+2\lambda_{i}(f+B))+C,&\text{when
$k=2$}\\\ \textit{
}\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}^{\prime\prime})+f_{2}+B+\lambda_{i}(f_{p_{2}}+B))+C\\}&\\\
\max\\{\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}^{\prime\prime})+f_{1}+B+k\lambda_{i}(f+B))+C,&\text{when
$k\geq 3$}\\\ \textit{
}\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}^{\prime\prime})+f_{2}+B+\lambda_{i}(f_{p_{2}}+B))+(k-3)\lambda_{i}(f+B))C\\}&\\\
\end{cases}$

It is again easy to see that
$\boldsymbol{\mathbb{E}}_{i}(\sigma_{2},\mathcal{S}^{\prime\prime},R-k+1)>\boldsymbol{\mathbb{E}}_{i}(\sigma_{1},\mathcal{S}^{\prime\prime},R-K+1)$.

The proof of the above Lemma implies the following result.

###### Lemma 2

Let $\Gamma_{F}(\mathcal{S},T+1)$ be a subgame in a state
$\mathcal{S}=\\{S\\}$, where the state contains a single chain $S$ where in
$T$ rounds miners mined unrelated transaction sets $txs_{u}$. Furthermore, for
all miners

$\mathsf{reward}(txs_{2})>\mathsf{reward}(txs_{1})>\mathsf{reward}(txs_{u}).$

Then the dominating strategy for all players in the subgame
$\Gamma_{F}(\mathcal{S},T+1)$ will result in the following transactions order:
$txs_{2}$, and for the rest of rounds $txs_{u}$.

###  0.C.2 Decisions of an Individual Miner are Consistent

In this section we show that without a high-cost reward $f_{2}$, once someone
is successful with mining $txs_{1}$, the miner will continue mining this
chain, as it might be too costly for the miner to lose the block reward that
he already mined. As $txs_{1}$, $txs_{2}$ is the only pair of conflicting
transactions in the game whenever $txs_{p_{1}}$ was not created, it follows
from Conjecture 1 that the forks may occur only when one miner successfully
mines $txs_{1}$, and the other player wants to profit from mining $txs_{2}$.
Thus, in the following, we study the behaviour of the players whenever one of
the players decides to mine $txs_{1}$.

###### Proof

At every point of the game, each player $N_{i}$ can choose a strategy for the
remaining $M$ rounds to collect at least $M\lambda_{i}(f+B)$ if he simply
always chooses to mine $txs_{u}$ from this point. Thus, whenever $txs_{1}$ was
just mined by $N_{j}$ and $R-r$ rounds are left till the end of the game, then
for some $C$:

  * •

$N_{j}$ chooses a strategy $\sigma_{1}$ where he continues the current chain
of the state $\mathcal{S}$, thus:

$\displaystyle\boldsymbol{\mathbb{E}}_{j}(\sigma_{1},\mathcal{S},r+1)\geq\lambda_{j}(\mathsf{reward}_{j}(\mathcal{S})+f+B+(R-r-1)\lambda_{j}(f+B))+C.$

  * •

when the $N_{j}$ ”forks” himself, then at least one of the blocks $txs_{1}$ or
$txs_{u}$ will be canceled out in the final chain, therefore for any strategy
$\sigma_{2}$ that involves forking $txs_{1}$:

$\displaystyle\boldsymbol{\mathbb{E}}_{j}(\sigma_{2},\mathcal{S},r+1)\leq\lambda_{j}(\mathsf{reward}_{j}(\mathcal{S})-(f_{1}+B)+f_{2}+B+(R-r-1)\lambda_{j}(f+B))+C.$

In conclusion
$\boldsymbol{\mathbb{E}}_{j}(\sigma_{1},\mathcal{S},r+1)>\boldsymbol{\mathbb{E}}_{j}(\sigma_{2},\mathcal{S},r+1)$,
unless $f_{2}-f\geq f_{1}+B$.

Now, since $N_{j}$ that already mined $txs_{1}$ will not fork himself in the
first round, it is easy to see that the same follows in the next round.

###  0.C.3 Only a High-Cost Reward May Encourage Miners to Fork

The next result shows that it is not possible to credibly threaten with forks
without high fees. In particular, we show that for any miner with mining power
$\lambda_{j}$ that _considers_ mining the block $txs_{1}$, any forking threat
in the game where $txs_{p_{1}}$ was not created, will not be credible unless
$f_{2}-f\geq\lambda_{j}(f+B)$, as the miner that mined the transaction will
continue to mine his transaction.

###### Proof

First, we introduce a notation of the states which are relevant for the
analysis of the above subgame. We say that a game is in the state
$\mathcal{S}_{0,-1}$ when $txs_{1}$ was just mined, and no-one forked the
chain with $txs_{1}$ yet. Let’s observe, that in this notation the state
$\mathcal{S}_{0,-1}$ is equal to the initial state $\mathcal{S}$. We say that
a game is in a state $\mathcal{S}_{k,l}$ ($k\geq 0,l\geq 0$), whenever the
chain defined in $\mathcal{S}$ reaches length $k$ compared to the initial
state and the chain from $\mathcal{S}$ is forked and the fork reaches length
$l$ compared to the initial state.

As $txs_{1}$ may be forked only if there does not exist any other chain where
it can be mined (Conjecture 1), at most $2$ chains may be formed in the game.
Whenever $k$ or $l$ reach length $1$, one of these chains will be closed. For
any player $N_{i}$ that we currently consider, we say that in the game is in
the state $\mathcal{S}_{k,l}^{i,u,d}$, if the player already mined $u$ blocks
in the chain with $txs_{1}$ and $d$ blocks in the fork chain ($k,l$ describe
length of the chains as above).

First, we analyze the behaviour of some other player $N_{i}\neq N_{j}$.
$N_{i}$ will be chosen with probability $\lambda_{i}$ as the winner of the
round, and with probability $1-\lambda_{i}$ someone else will be selected as
the winner of the round. Then for some constant $C$, the utility of the player
$i$ in all strategies $\sigma_{1}$ that continue mining $txs_{1}$ in
$\mathcal{S}$ can be described as:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{1},\mathcal{S},r)=\lambda_{i}\boldsymbol{\mathbb{E}}_{i}(\sigma_{1},\mathcal{S}_{1,-1}^{i,1,0},r+1)+C.$

And the utility of the player $i$ in all strategies $\sigma_{2}$ that fork
$txs_{1}$ in $\mathcal{S}$ can be described as:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{2},\mathcal{S},r)=u_{i,0,-1}^{0,0}[\sigma_{1}]=\lambda_{i}\boldsymbol{\mathbb{E}}_{i}(\sigma_{2},\mathcal{S}_{0,0}^{i,0,1},r+1)+C.$

By Theorem 4, the player $N_{j}$ that mined $txs_{1}$, will continue to mine
the chain with $txs_{1}$ in the next two rounds. Furthermore, as already
mentioned, any miner $N_{i}$ that decides to continue the chain with
$txs_{1}$, can profit at least $\lambda_{i}(f+B)$ in each round till the end
of the game, by simply mining $txs_{u}$. From the above it follows that.

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{1},\mathcal{S}_{1,-1}^{i,1,0},r+1)\geq\mathsf{reward}_{i}(\mathcal{S})+f+B+(R-r)\lambda_{i}(f+B),$

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{2},\mathcal{S}_{0,0}^{i,0,1},r+1)\leq\mathsf{reward}_{i}(\mathcal{S})+\max\\{(f_{2}+B)(1-\lambda_{j})+(M-1)\lambda_{i}(f+B)$
$\displaystyle(f+B)(1-\lambda_{j})+\lambda_{i}(f_{2}+B)+(R-r-1)\lambda_{i}(f+B)\\}.$

In conclusion
$\boldsymbol{\mathbb{E}}_{i}(\sigma_{1},\mathcal{S}_{1,-1}^{i,1,0},r+1)>\boldsymbol{\mathbb{E}}_{i}(\sigma_{2},\mathcal{S}_{0,0}^{i,0,1},r+1)$
unless $f_{2}-f\geq\lambda_{j}(f+B)$.

###  0.C.4 Without a High-Cost Reward, All Players Mine $txs_{1}$

As we already observed, once $txs_{1}$ is mined, it will not be forked unless
the bribing fee is sufficient. We will show that for a sufficiently large
number of rounds $T$, all of the players will mine transaction set $txs_{1}$
in the first round. A similar result was introduced in [26], but we prove that
this result still holds in the game with forks.

###### Proof

In the game where none of the miners decides to create the transaction set
$txs_{p_{1}}$, miners may choose to mine $txs_{u}$ and $txs_{1}$ in all
rounds, or $txs_{2}$ only after round $T$. Now, since the game contains only
one pair of mutually exclusive transactions $txs_{1},txs_{2}$ with
$\mathsf{reward}(txs_{2})>\mathsf{reward}(txs_{1})$, then by Conjecture 1
players can start to fork only when $txs_{1}$ appears on the blockchain. What
is more, since $f_{2}-f<10^{-2}(f+B)$, by Theorem 4, whenever some player with
$\lambda_{j}>10^{-2}$ successfully mines $txs_{1}$ in a chain of length $\leq
T$, none of the players will decide to fork his block.

We prove that in the above game miners with collective mining power at least
$Y$ will decide to mine $txs_{1}$ in rounds $\\{T,T-1,\ldots,1\\}$ if it was
not mined up to this point.

Let’s take any miner with $\lambda_{i}>10^{-2}$ that makes a decision in round
$T-k$, for $k\in\\{0,\ldots,T-1\\}$. As already mentioned, once he
successfully mines the block $txs_{1}$, it will not be forked. In round $T$,
whenever the block $txs_{1}$ was not mined, then the miners had only mined
$txs_{u}$ so far ending up in a state $\mathcal{S}_{T}$. Then for some
constant $C$, the utility of the player $N_{i}$ in all strategies $\sigma_{1}$
that choose to mine $txs_{1}$ in $\mathcal{S}_{T}$, and all strategies that
choose to mine $txs_{u}$ in $\mathcal{S}_{T}$:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{1},\mathcal{S}_{T},T)\geq\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}_{T})+f_{1}+B+\lambda_{i}(R-T-1)(f+B))+C,$
$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{2},\mathcal{S}_{T},T)\geq\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}_{T})+f+B+\lambda_{i}(f_{2}+B)+(R-T-2)\lambda_{i}(f+B))+C.$

Now,
$\boldsymbol{\mathbb{E}}_{i}(\sigma_{2},\mathcal{S}_{T},T)<\boldsymbol{\mathbb{E}}_{i}(\sigma_{1},\mathcal{S}_{T},T)$
only if $(*)f_{2}-f\geq\frac{f_{1}-f}{\lambda_{i}}$. This implies that miners
with collective mining power at least $Y$ will prefer to mine $txs_{1}$ in
this round.

In round $T-k$, where $k>0$, whenever the block $txs_{1}$ was not mined, then
the miners had only mined $txs_{u}$ so far, ending up in a state
$\mathcal{S}_{T-k}$. Then for some constant $C$, the utility of the player $i$
in all strategies $\sigma_{1}$ that choose to mine $txs_{1}$ in
$\mathcal{S}_{T}$, and all strategies that choose to mine $txs_{u}$ in
$\mathcal{S}_{T}$:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{1},\mathcal{S}_{T-k},T-k)=\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}_{T-k})+f_{1}+B+\lambda_{i}(k-1)(f+B)+$
$\displaystyle\lambda_{i}(R-T+k-1)(f+B))+C,$
$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{2},\mathcal{S}_{T-k},T-k)\leq\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}_{T-k})+f+B+\lambda_{i}(k-1)(f+B)+\lambda_{i}(f_{2}+B)+$
$\displaystyle(R-T+k-2)\lambda_{i}(f+B))+C.$

Similiary, the above equation implies that at least $Y$ miners will prefer to
mine $txs_{1}$ in this round.

Now, after the first round there are $T$ rounds till the moment of mining
$txs_{2}$, player’s $N_{i}$ benefit from mining $txs_{1}$ (with
$\lambda_{i}>0.01$) and not waiting for $txs_{2}$ is at least
$benefit=\lambda_{i}(f_{1}+B)-\lambda_{i}(1-Y)^{T}(f_{2}+B)$, and since
$f_{2}-f<10^{-2}(f+B)$, then
$benefit\geq\lambda_{i}(f_{1}+B-(1-Y)^{T})(1.01f+1.01B)$. Now, assuming that
$f_{1}>f$ we have
$benefit\geq\lambda_{i}(f(1-1.01(1-Y)^{T}))+B(1-1.01(1-Y)^{T})$. This implies
that whenever $(1-1.01(1-Y)^{T})>0$, then all miners with $\lambda_{i}>0.01$
will mine $txs_{1}$ in the first round.

A similar results holds in any state where sufficiently large number of
$T-r+1$ rounds are left till the round $T$, $txs_{p_{1}}$ was not created in
the game (or $txs_{u}$ was mined in the first round), and $txs_{1}$ was not
mined yet. We leave it as a lemma without a proof.

###### Lemma 3

Given a game with forks $\Gamma_{F}(\mathcal{S},r)$ with $r<T$, where none of
the miners decides to create $txs_{p_{1}}$ before the first round (or
$txs_{u}$ is mined in the first round), and the bribing fee is not too high,
i.e. $f_{2}-f<10^{-2}(f+B)$ and given
$Y=\sum_{j=i:\lambda_{j}>0.01,f_{2}-f<\frac{f_{1}-f}{\lambda_{j}}}^{|N|}\lambda_{j}$;
$T-r+1,Y$ are big enough, such that $(1-1.01(1-Y)^{T-r+1})>0$, every miner
with $\lambda_{j}>0.01$ will decide to mine $f_{1}$ in this round.

###  0.C.5 Discouraging Miners to Mine $txs_{1}$

In the previous sections, we have shown that it is rather expensive to force
the players not to mine $txs_{1}$ in the first round, even when the players
can fork this transaction. In this section, we leverage the self-penalty
mechanism introduced in Section 2.2. The proof is inductive, and its base case
starts in round $T$. For each round, we first show that the miner $N_{s}$ with
the highest mining power $\lambda_{s}$ will not mine $txs_{1}$, as we assume
that $f_{2}-f>\frac{f_{1}-f}{\lambda_{s}}$. Next, given a sufficiently large
penalty $P>\lambda_{s}(f+B)$, we show that the selected player $N_{s}$ will
fork the transaction $txs_{1}$, once it appears on the blockchain, even though
it poses a risk of loosing the block reward. Finally, we show that in this
round all players other than the player $N_{s}$ are afraid to mine $txs_{1}$,
when the self-penalty transaction is on the chain.

###### Proof

Let us denote with $\mathcal{S}_{p_{1}}^{T}$ a state containing a chain of
length $T-1$, where $txs_{p_{1}}$ was created by $N_{s}$ with mining power
$\lambda_{s}$ and with the deposit parameter
$P~{}\geq~{}f+B-\lambda_{s}(f_{2}+B)$. All other mined transaction sets in
$\mathcal{S}_{p_{1}}^{T}$ are $txs_{u}$. With $\mathcal{S}_{p_{1},f_{1}}^{T}$
we denote a state $\mathcal{S}_{p_{1}}^{T}$ with transaction set $txs_{1}$
added at the top of the chain in the state $\mathcal{S}_{p_{1}}^{T}$.

Let us denote with $\sigma_{1}$ all strategies where player $N_{s}$ continues
to mine the chain with $txs_{1}$ in $\mathcal{S}_{p_{1},f_{1}}^{T}$, and let
$\sigma_{2}$ denote all strategies, where he forks $txs_{1}$ in
$\mathcal{S}_{p_{1},f_{1}}^{T}$ and then continues to mine the newly created
chain (we assume that the transaction $txs_{1}$ was not mined by the miner
$N_{s}$, as when $f_{2}-f>\frac{f_{1}-f}{\lambda_{s}}$, then as shown in the
proof of the Theorem 4, the player $N_{s}$ will choose to mine $txs_{u}$ in
$\mathcal{S}_{p_{1}}^{T}$). It is easy to see that once the player $N_{s}$
successfully forks $txs_{1}$ and creates a new chain, all miners other than
the miner that mined $txs_{1}$ will prefer to mine the newly created chain. As
the miner who mined the transaction $txs_{1}$ has the mining power less than
$\lambda_{s}$, we can say that once $txs_{1}$ is forked, the miners with the
mining power at least $1-\lambda_{s}$ will continue mining the new chain. In
summary, for some constant $C$, given similar arguments as in the previous
proofs:

$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{1},\mathcal{S}_{p_{1},f_{1}}^{T},T+1)\leq\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1},f_{1}}^{T})+f+B+(R-T-1)\lambda_{s}(f+B)-P)+C,$
$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{2},\mathcal{S}_{p_{1},f_{1}}^{T},T+1)\geq\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1},f_{1}}^{T})+(1-\lambda_{s})(f+B)+\lambda_{s}(f_{2}+B)+$
$\displaystyle(R-T-2)\lambda_{s}(f+B))+C,$

as after two rounds, the player may at least mine $txs_{u}$ in each round.
This implies that for $P>\lambda_{s}(f+B)$ the committed player prefers to
choose strategy $\sigma_{2}$ and fork in $\mathcal{S}_{p_{1},f_{1}}^{T}$.

Now, we consider the strategy for every player $N_{i}$ such that $i\neq s$ and
$\lambda_{i}<\lambda_{s}$ in state $\mathcal{S}_{p_{1}}^{T}$. Let us denote
strategies where player $N_{i}$ chooses to mine $txs_{1}$ in
$\mathcal{S}_{p_{1}}^{T}$ with $\sigma_{1}$ and when he mines $txs_{u}$ in
$\mathcal{S}_{p_{1}}^{T}$ with $\sigma_{u}$. Then for some $C$ following
inequalities are satisfied:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{u},\mathcal{S}_{p_{1}}^{T},T)\geq\lambda_{i}[\mathsf{reward}_{i}(\mathcal{S}_{p_{1}}^{T})+(f+B)+(R-T-2)\lambda_{i}*(f+B)+$
$\displaystyle\lambda_{i}*(f_{2}+B)]+C,$
$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{1},\mathcal{S}_{p_{1}}^{T},T)\leq\lambda_{i}[\mathsf{reward}_{i}(\mathcal{S}_{p_{1}}^{T})+(f_{1}+B)\mathbb{P}^{survive}[\mathcal{S}_{p_{1},f_{1}}^{T}]+(R-T-1)\lambda_{i}*(f+B)]]+C.$

Where $\mathbb{P}^{survive}[\mathcal{S}]$ is the probability that the last
block of the single chain in the state $\mathcal{S}$ remains a part of the
chain in the last round $R$. Since in $\mathcal{S}_{p_{1},f_{1}}^{T}$ player
$N_{s}$ will prefer to fork the transaction set $txs_{1}$, then
$\mathbb{P}^{survive}[\mathcal{S}_{p_{1},f_{1}}^{T}]\leq 1-\lambda_{s}^{2}$.

Now, whenever
$1-\lambda_{s}^{2}<\frac{f+B+\lambda_{i}(f_{2}+B)+\lambda_{i}(f+B)}{f_{1}+B}$,
then all players prefer to mine $txs_{u}$.

However
$\frac{f+B+\lambda_{i}(f_{2}+B)+\lambda_{i}(f+B)}{f_{1}+B}>\frac{f+B}{f_{1}+B}$,
and $\frac{f+B}{f_{1}+B}>1-\lambda_{s}^{2}$ by the assumption. The above
implies that on a chain of length $T$, every player mines $txs_{u}$.

For any chain of length $k=3,\ldots,T-1$ we prove that if everyone mines only
$txs_{u}$ on chain of length $k+1$ (i.e. strategy for every miner on
$\mathcal{S}_{p_{1}}^{k+1}$ is to mine $txs_{u}$) or everyone forks on chain
of length $k+1$ with $txs_{1}$ then the same assumptions hold for chains of
length $k$.

First we prove that on a chain of length $k$ player $N_{s}$ will fork
$txs_{1}$, once it appears on the blockchain. We inductively assume that the
assumptions hold for chains of length $k+1,\ldots,T$.

Again, once the player $N_{s}$ successfully forks $txs_{1}$ and creates a new
chain, all miners other than the miner that mined $txs_{1}$ will continue
mining the new chain. Let us denote with $\sigma_{1}$ all strategies where
player $N_{s}$ continues to mine $txs_{1}$ in $\mathcal{S}_{p_{1},f_{1}}^{k}$,
and with $\sigma_{2}$ all strategies, where he forks $txs_{1}$ in
$\mathcal{S}_{p_{1},f_{1}}^{k}$. Then for some constant $C$:

$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{1},\mathcal{S}_{p_{1},f_{1}}^{k},k+1)\leq\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1},f_{1}}^{k})+f+B+(T-k)\lambda_{s}(f+B)-P)+C,$
$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{2},\mathcal{S}_{p_{1},f_{1}}^{k},k+1)\geq\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1},f_{1}}^{k})+(1-\lambda_{s})(f+B)+$
$\displaystyle\lambda_{s}(f_{2}+B)+(T-k-1)\lambda_{s}(f+B))+C.$

as after two rounds, the player may always mine $txs_{u}$ in each round. This
implies that for $P>\lambda_{s}(f+B)$ the committed player prefers to choose
strategy $\sigma_{2}$ and fork in $\mathcal{S}_{p_{1},f_{1}}^{k}$.

Next, we analyse the optimal strategy for any player $N_{i}$ such that $i\neq
s$, in $\mathcal{S}_{p_{1}}^{k}$. Let us denote strategies where player
$N_{i}$ chooses to mine $txs_{1}$ in $\mathcal{S}_{p_{1}}^{k}$ with
$\sigma_{1}$ and with $\sigma_{u}$ when he wants to mine $txs_{u}$ in
$\mathcal{S}_{p_{1}}^{k}$. It holds for some $C$, that:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{u},\mathcal{S}_{p_{1}}^{k},k)\geq\lambda_{i}[\mathsf{reward}_{i}(\mathcal{S}_{p_{1}}^{k})+(f+B)\cdot
1+(T-k-2)\lambda_{i}*(f+B)+\lambda_{i}*(f_{2}+B)]+C,$
$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{1},\mathcal{S}_{p_{1}}^{k},k)\leq\lambda_{i}[\mathsf{reward}_{i}(\mathcal{S}_{p_{1}}^{k})+(f_{1}+B)\mathbb{P}^{survive}[\mathcal{S}_{p_{1},f_{1}}^{k}]+(T-k-1)\lambda_{i}*(f+B)]]+C.$

As discussed previously, whenever
$1-\lambda_{s}^{2}<\frac{f+B+\lambda_{i}(f_{2}+B)+\lambda_{i}(f+B)}{f_{1}+B}<\frac{f+B}{f_{1}+B}$
is satisfied, then all players prefer to mine $txs_{u}$.

Now, for the chain of length $2$, whenever $txs_{1}$ is mined it will be
forked by a similar argument as discussed above, as once $txs_{1}$ appears on
blockchain, $txs_{p_{1}}$ cannot be forked. The analysis of the following case
is conducted to asses the behaviour of players in the second round of the
game.

Case 1. Player $N_{s}$ mined $txs_{p_{1}}$ in the state $\mathcal{S}_{p_{1}}$.

Case 1.A. When $txs_{1}$ was just mined by the player $N_{s}$ and $R-1$ rounds
are left till the end of the game, then for some $C$:

  * •

by $\sigma_{1}$ we denote strategies where player $N_{s}$ decides to continue
the current chain of the state, adding $txs_{1}$:

$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{1},\mathcal{S}_{p_{1}},2)\leq\max\\{\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1}})+f_{1}+B+(R-2)\lambda_{s}(f+B))+C,$
$\displaystyle\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1}})+(R-3)\lambda_{s}(f+B)+\lambda_{s}(f_{2}+B)+P)+C\\}$

  * •

by $\sigma_{2}$ we denote strategies where player $N_{s}$ decides to continue
the current chain of the state, adding $txs_{u}$:

$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{2},\mathcal{S}_{p_{1}},2)\geq\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1}})+f+B+(R-3)\lambda_{s}(f+B)+\lambda_{s}(f_{2}+B)+P)+C$

  * •

by $\sigma_{f_{1}}$ \- we denote a strategy that chooses to fork $txs_{p_{1}}$
and mine $txs_{1}$ -

$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{f_{1}},\mathcal{S}_{p_{1}},2)\leq\max\\{\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1}})+(f_{1}+B)+(R-2)\lambda_{s}(f+B)-B)+C,$
$\displaystyle\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1}})+(R-2)\lambda_{s}(f+B)+\lambda_{s}(f_{2}+B)+P-B)+C\\}$

  * •

by $\sigma_{f_{u}}$ \- we denote a strategy that chooses to fork $txs_{p_{1}}$
and mine $txs_{u}$

$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{f_{u}},\mathcal{S}_{p_{1}},2)\leq\max\\{\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1}})+f+B+(R-3)\lambda_{s}(f+B)+\lambda_{s}(f_{2}+B)-B),$
$\displaystyle\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1}})+\lambda_{s}(f_{1}+B)+(R-3)\lambda_{s}(f+B)-B)\\}$

In summary, the strategy $\sigma_{2}$ is dominating and player $N_{s}$ who
mined $txs_{p_{1}}$, will prefer to continue mining $txs_{p_{1}}$. Note that
the above analysis will be similar, even if some player other than the $N_{s}$
successfully starts a fork of $txs_{p_{1}}$.

Case 1.B. Further, for any player $N_{i}$, where $i\neq s$, for some constant
$C$:

  * •

by $\sigma_{1}$ we denote strategies where $N_{i}$ decides to continue the
current chain of the state, adding $txs_{1}$:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{1},\mathcal{S}_{p_{1}},2)\leq\max\\{\lambda_{i}((f_{1}+B)(1-\lambda_{s})+(R-2)\lambda_{i}(f+B))+C,$
$\displaystyle\lambda_{i}((R-3)\lambda_{i}(f+B)+\lambda_{i}(f_{2}+B))+C\\}$

  * •

by $\sigma_{2}$ we denote strategies where $N_{i}$ decides to continue the
current chain of the state, adding $txs_{u}$:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{2},\mathcal{S}_{p_{1}},2)\geq\lambda_{i}(f+B+(R-3)\lambda_{i}(f+B)+\lambda_{i}(f_{2}+B))+C$

  * •

by $\sigma_{f_{1}}$ we denote a strategy that chooses to fork $txs_{p_{1}}$
and mine $txs_{1}$ -

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{f_{1}},\mathcal{S}_{p_{1}},2)\leq\max\\{\lambda_{i}((f_{1}+B)(1-\lambda_{s})+(R-2)\lambda_{i}(f+B))+C,$
$\displaystyle\lambda_{j}((R-2)\lambda_{i}(f+B)+\lambda_{i}(f_{2}+B))+C\\}$

  * •

by $\sigma_{f_{u}}$ we denote a strategy that chooses to fork $txs_{p_{1}}$
and mine $txs_{u}$

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{f_{u}},\mathcal{S}_{p_{1}},2)\leq\max\\{\lambda_{i}((f+B)(1-\lambda_{s})+(R-3)\lambda_{i}(f+B)+\lambda_{i}(f_{2}+B))+C,$
$\displaystyle\lambda_{i}(\lambda_{i}(f_{1}+B)+(R-3)\lambda_{i}(f+B))+C\\}$

Similarly, $\sigma_{2}$ is the dominating strategy for every player $N_{i}\neq
N_{s}$, unless $(f_{1}+B)(1-\lambda_{s})\geq(f+B)$ (which does not hold for
$f_{1}-f\geq 0.05$, and $B\approx 6$).

Case 2. Player $N_{i}$ (where $i\neq s$) mined $txs_{p_{1}}$ in the state
$\mathcal{S}_{p_{1}}$.

Case 2.A. The analysis for the player $N_{i}$, for some constant $C$:

  * •

by $\sigma_{1}$ we denote strategies where the player $N_{i}$ decides to
continue the current chain of the state, adding $txs_{1}$:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{1},\mathcal{S}_{p_{1}},2)\leq\max\\{\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}_{p_{1}})+(f_{1}+B)(1-\lambda_{j})+(R-2)\lambda_{i}(f+B))+C,$
$\displaystyle\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}_{p_{1}})+(R-3)\lambda_{i}(f+B)+\lambda_{i}(f_{2}+B))+C\\}$

  * •

by $\sigma_{2}$ we denote strategies where the $N_{i}$ decides to continue the
current chain of the state, adding $txs_{u}$:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{2},\mathcal{S}_{p_{1}},2)\geq\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}_{p_{1}})+f+B+(R-3)\lambda_{i}(f+B)+\lambda_{i}(f_{2}+B))+C$

  * •

by $\sigma_{f_{1}}$ we denote a strategy that chooses fork $txs_{p_{1}}$ and
mine $txs_{1}$ -

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{f_{1}},\mathcal{S}_{p_{1}},2)\leq\max\\{\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}_{p_{1}})+(f_{1}+B)+(R-2)\lambda_{i}(f+B)-B)+C,$
$\displaystyle\lambda_{j}(\mathsf{reward}_{i}(\mathcal{S}_{p_{1}})+(R-2)\lambda_{i}(f+B)+\lambda_{i}(f_{2}+B)-B)+C\\}$

  * •

by $\sigma_{f_{u}}$ we denote a strategy that chooses to fork $txs_{p_{1}}$
and mine $txs_{u}$

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{f_{u}},\mathcal{S}_{p_{1}},2)\leq\max\\{\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}_{p_{1}})+f+B+(R-3)\lambda_{i}(f+B)+\lambda_{i}(f_{2}+B)-B)+C,$
$\displaystyle\lambda_{i}(\mathsf{reward}_{i}(\mathcal{S}_{p_{1}})+\lambda_{i}(f_{1}+B)+(R-3)\lambda_{i}(f+B)-B)+C\\}$

Similarly to previous case, the strategy $\sigma_{2}$ dominates all other
strategies. Again, the above analysis will be similar, even if some player
other than the $N_{i}$ successfully starts a fork of $txs_{p_{1}}$.

Case 2.B. Next, we analyze the cases for the player $N_{s}$ who did not mine
$txs_{p_{1}}$. For some constant $C$:

  * •

by $\sigma_{1}$ we denote strategies where player $N_{s}$ decides to continue
the current chain of the state, adding $txs_{1}$:

$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{1},\mathcal{S}_{p_{1}},2)\leq\max\\{\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1}}+f_{1}+B+(R-2)\lambda_{s}(f+B))+C,$
$\displaystyle\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1}}+(R-3)\lambda_{s}(f+B)+\lambda_{s}(f_{2}+B)+P)+C\\}$

  * •

by $\sigma_{2}$ we denote strategies where player $N_{s}$ decides to continue
the current chain of the state, adding $txs_{u}$:

$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{2},\mathcal{S}_{p_{1}},2)\geq\lambda_{j}(f+B+(R-3)\lambda_{s}(f+B)+\lambda_{s}(f_{2}+B)+P)+C$

  * •

by $\sigma_{f_{1}}$ we denote a strategy that chooses to fork $txs_{p_{1}}$
and mine $txs_{1}$:

$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{f_{1}},\mathcal{S}_{p_{1}},2)\leq\max\\{\lambda_{j}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1}}+(f_{1}+B)(1-\lambda_{i})+(R-2)\lambda_{s}(f+B)+P)+C,$
$\displaystyle\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1}}+(R-2)\lambda_{s}(f+B)+\lambda_{s}(f_{2}+B)+P)+C\\}$

  * •

by $\sigma_{f_{u}}$ we denote a strategy that chooses fork $txs_{p_{1}}$ and
mine $txs_{u}$:

$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{f_{u}},\mathcal{S}_{p_{1}},2)\leq\max\\{\lambda_{j}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1}}+(f+B)(1-\lambda_{i})+(R-3)\lambda_{s}(f+B)+\lambda_{s}(f_{2}+B)+P)+C,$
$\displaystyle\lambda_{s}(\mathsf{reward}_{s}(\mathcal{S}_{p_{1}}+\lambda_{s}(f_{1}+B)+(R-3)\lambda_{s}(f+B))+C\\}$

The strategy $\sigma_{2}$ is dominating for the player $N_{s}$ who did not
mine $txs_{p_{1}}$, and he will prefer to continue mining $txs_{p_{1}}$
whenever $f_{2}-f>\frac{2\overline{f}+2(f_{1}-f)}{\lambda_{s}}$. Note that the
above analysis will be similar, even if some player other than the $N_{s}$
successfully starts a fork of $txs_{p_{1}}$.

Case 2.C. Finally, we analyze the case for any player $N_{i^{\prime}}\neq
N_{s}$ different than the player $N_{i}$ who mined $txs_{p_{1}}$. The argument
follows similarly as in the Case 1.B. that the strategy that chooses to
continue the current chain of the state and adding $txs_{u}$ is dominating,
given that both the player $N_{i}$ and the player $N_{s}$ will choose to
continue mining the transaction $txs_{p_{1}}$, even if someone else forks it.

###  0.C.6 Encouraging the Strongest Miner to Use the Penalty Mechanism

Finally, we observe the benefit that comes from using the penalty mechanism.
First for the miner with the strongest mining power $\lambda_{s}$, we observe
that using the self-penalty mechanism and threatening others to mine the
transaction $txs_{1}$, once it appears on the blockchain is beneficial for him
whenever $f_{2}-f>\frac{2\overline{f}+2(f_{1}-f)}{\lambda_{s}}+\overline{f}$.
Next, for any miner with a smaller mining power, we show that merely the fact
that he is threatened to mine $txs_{1}$ can force them to skip mining this
transaction.

###### Proof

By Theorems 4 and 4, utility of the player $N_{s}$ that chooses to create
$txs_{p_{1}},txs_{p_{2}}$ and mine $txs_{p_{1}}$ in the first round444In the
analysis we omit the strategy where the player $N_{s}$ creates
$txs_{p_{1}},txs_{p_{2}}$ and does not decide to mine $txs_{p_{1}}$. (strategy
$\sigma_{p}$) is at least:

$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{p},\mathcal{S},1)\geq-\lambda_{p_{1}}c_{p_{1}}\overline{f_{p_{1}}}+\lambda_{s}((m-c_{p_{1}})\overline{f}+B)+(\lambda_{p_{1}}+\lambda_{s})F^{\prime}_{2}+(1-\lambda_{s}-\lambda_{p_{1}})F^{\prime}_{1},$

where $F^{\prime}_{1}=(\lambda_{s}(T-1)(f+B)+\lambda_{s}(R-T)(f+B)),$

$\displaystyle
F^{\prime}_{2}=(\lambda_{s}((T-1)(f+B))+\lambda_{s}(f_{2}+B)-\lambda_{p_{2}}c_{p_{2}}\overline{f}_{p_{2}}+\lambda_{s}((m-c_{p_{2}})\overline{f}+B)+\lambda_{i}(R-T-2)(f+B)).$

Recall that we assume that all players with mining power less than $1\%$ have
collective power at most $5\%$. As the players with mining power more than
$0.01$ will prefer to mine $txs_{1}$ in the first place when $txs_{p_{1}}$ is
not created, the utility of the player $N_{s}$ that does not decide to create
$txs_{p_{1}}$ (strategy $\sigma_{1}$) is at most (by Lemma 3 and the Theorem
4):

$\displaystyle\boldsymbol{\mathbb{E}}_{s}(\sigma_{1},\mathcal{S},1)\leq((1-0.05^{T/2})F_{1}+0.05^{T/2}F_{2}),$

where $F_{1}=F^{\prime}_{1}+\lambda_{s}(f_{1}+B)$,
$F_{2}=F^{\prime}_{2}+\lambda_{s}(f+B)$. Further, if
$\lambda_{p_{1}}c_{p_{1}}\overline{f}_{p_{1}}+\lambda_{s}(f+B)-\lambda_{s}c_{p_{1}}\overline{f}+F^{\prime}_{1}+(\lambda_{p_{1}}+\lambda_{s})(F^{\prime}_{2}-F^{\prime}_{1})>F_{1}+0.05^{T/2}(F_{2}-F_{1}),$
then
$\boldsymbol{\mathbb{E}}_{s}(\sigma_{p},\mathcal{S},1)>\boldsymbol{\mathbb{E}}_{s}(\sigma_{1},\mathcal{S},1).$
This condition holds whenever:

$(\lambda_{p_{1}}+\lambda_{s})[\lambda_{s}f_{2}-\lambda_{s}f_{1}]>0.05^{T/2}[\lambda_{s}f_{2}-\lambda_{s}f_{1}]+\lambda_{p_{1}}c_{p_{1}}\overline{f}_{p_{1}}+\lambda_{s}c_{p_{1}}\overline{f}+(\lambda_{p_{1}}+\lambda_{s})(\lambda_{p_{2}}c_{p_{2}}\overline{f}_{p_{2}}+\lambda_{s}c_{p_{2}}\overline{f})+\lambda_{s}(f_{1}-f).$

What concludes that the following bribe is enough to encourage the strong
miner to wait for $txs_{2}$:

$\displaystyle
f_{2}-f>\frac{c_{p_{1}}\overline{f}_{p_{1}}+c_{p_{1}}\overline{f}+c_{p_{2}}\overline{f}_{p_{2}}+f_{1}-f}{\lambda_{s}-0.05^{T/2}}+c_{p_{2}}\overline{f}.$

Now, if the $txs_{p_{1}},txs_{p_{2}}$ are created then every player $N_{i}$
other than the player $N_{s}$ may mine $txs_{p_{1}}$, once it is published
(strategy $\sigma_{p_{1}^{*}}$). When $txs_{p_{1}}$ is successfully mined in
the first round, then all miners will be encouraged to wait until $txs_{2}$
may be mined after the $T$’th round. $1-\lambda_{p_{1}}-\lambda_{i}$ miners
may decide to mine $txs_{u}$ (or $txs_{1}$) in the first round. In this case,
when the $txs_{u}$ is mined, all other players will be able to mine at least
$f+B$ for the rest of the rounds:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{p_{1}^{*}},\mathcal{S},1)\geq\lambda_{i}(f_{p_{1}}+B)+(\lambda_{p_{1}}+\lambda_{i})F_{2}+(1-\lambda_{p_{1}}-\lambda_{i})F,$

where
$F_{2}=(T-1)\lambda_{i}(f+B)+\lambda_{i}(f_{2}+B)+\lambda_{i}(f_{p_{2}}+B)+(R-T-2)\lambda_{i}(f+B)$
and $F=(R-1)\lambda_{i}(f+B)$.

On other hand the players may first decide to mine either $txs_{u}$ or
$txs_{1}$ in the first round (strategy $\sigma_{1*}$). In the worst case
scenario the block with $txs_{1}$ is not forked. What is more, whenever
$1-\lambda_{p_{1}}$ miners decide to mine $txs_{u}$ in the first round, then
all miners with mining power more than $0.01$ will make an attempt to mine
$txs_{1}$. In conclusion, by Lemma 3 and the Theorem 4:

$\displaystyle\boldsymbol{\mathbb{E}}_{i}(\sigma_{1*},\mathcal{S},1)\leq\lambda_{i}(f_{1}+B)+$
$\displaystyle\lambda_{p_{1}}F_{2}+(1-\lambda_{p_{1}}-\lambda_{1})((1-0.05^{T/2})F+0.05^{T/2}F_{2}),$

where $F$ and $F_{2}$ are defined as previously.
$\boldsymbol{\mathbb{E}}_{i}(\sigma_{p_{1}*},\mathcal{S},1)>\boldsymbol{\mathbb{E}}_{i}(\sigma_{1*},\mathcal{S},1)$
holds whenever:

$\displaystyle\lambda_{i}(f_{p_{1}}+B)+\lambda_{i}(F_{2}-F)>\lambda_{i}(f_{1}+B)+(1-\lambda_{p_{1}})0.05^{T/2}(F_{2}-F)$

Which holds for any $f_{p_{1}}\geq f_{1}$ and $\lambda_{i}>0.05^{T/2}$.

Now, by setting $c_{p_{1}}=1,c_{p_{2}}=1$, $\overline{f_{p_{1}}}=f_{1}-f$,
$\overline{f_{p_{2}}}=\overline{f}$, we get a condition:

$\displaystyle
f_{2}-f>\frac{2\overline{f}+2(f_{1}-f)}{\lambda_{s}-0.05^{T/2}}+\overline{f},$

what for $\lambda_{s}\approx 20\%$ and sufficiently large $T/2$ concludes
$f_{2}-f\gtrsim\frac{2\overline{f}+2(f_{1}-f)}{\lambda_{s}}+\overline{f}$.

##  Appendix 0.D Experimental Analysis

In this section we conduct the analysis of the fee structures on the the real-
world data.

###  0.D.1 Fee Structure

We analyze the real-world data on fees earned by miners on Bitcoin. In
particular, we explore the Bitcoin historical data from 2022 ([1]). In this
period, the block reward was the sum of the block reward base, 6.25 BTC, and
the fees for including transactions. The weekly average sum of the block fees
ranged between 0.05 and 0.225 BTC as shown in Figure 3. The average fee of a
single transaction fluctuated proportionally between $0.00004$ and $0.00016$
BTC as shown in Figure 4. We can thus fairly assume that any block typically
contains on average $1500$ transactions, the sum of fees of an average block
of transactions is around $0.15$ BTC and the average fee of a single
transaction is approximately $10^{-4}$ BTC.

Figure 3: Average amount of fees aggregated in a block for each week in 2022
([1]). Figure 4: Average transaction fee of a single transaction for each week
in 2022 ([1]).

###  0.D.2 Hash Power Analysis

Figure 5: Average mining hashrate week by week of the most significant Bitcoin
miners in 2022 [1].

In this Section we present the analysis of hashpower distribution of mining
pools in selected popular Proof-of-Work blockchains: Bitcoin, Litecoin and
Ethereum Classic. Even though all three blockchains are built upon the PoW
concept, they differ in the cryptographic primitive (hash function) that they
use: Bitcoin uses SHA-256, Litecoin uses Scrypt and Ethereum Classic uses
ETChash. As the speed of Bitcoin mining relies solely on the amount of hashes
that a device is able to compute in a time unit, miners developed a market for
Application-Specific Integrated Circuits (so-called ASICs) that are designed
to calculate hashes specifically for the purpose of Bitcoin mining. This can
be considered a rather undesirable phenomenon, as it causes significant
environmental losses, thus both Scrypt and ETCHash were designed to lower the
advantage of mining blocks with ASICs. Both Scrypt and ETCHash, in contrast to
SHA-256, require hardware that has relatively fast access to large amounts of
memory, that makes current Bitcoin ASICs unusable in the context of Scrypt and
ETCHash mining.

Device | Hashrate (Hashes/second)
---|---
Nvidia GeForce RTX 4090 | $2.75\cdot 10^{8}$
Nvidia GeForce RTX 3090 | $9.4\cdot 10^{7}$
Bitmain Antminer S19 XP Hyd | $2.55\cdot 10^{14}$
Baikal BK-G28 | $2.8\cdot 10^{10}$
Table 2: Hash rates of commonly used Bitcoin mining devices [4].

The weakest miner. In the previous work [10], the authors assumed that the
fraction of the mining power held by the weakest miners is approximately
$10^{-3}$. The data depicted in the Table 2 and in the Figure $2(b)$ shows
that it is a highly unrealistic assumption for Bitcoin. A very strong GPU
which is often used by individual miners for mining has hashrate of around
$3\cdot 10^{8}$ (Table 2), whereas the collective mining power in Bitcoin can
be estimated to $2\cdot 10^{20}$ (Figure $2(b)$). In conclusion, we cannot
expect that every individual miner has more than $10^{-12}$ probability of
mining a block.

Fraction of the weak miners. In this work we assume that there exists a single
player that has mining power slightly more than $1\%$, but the collective
mining power of weak miners that have mining power less than some $1\%$ is not
more than $5\%$. This phenomenon is quite realistic, as observed in Table 3.

Strong miners. On the other side of the spectrum, top mining pools
continuously maintain over $20\%$ of total hashpower. To calculate the share
of the hashpower of a big mining pool in a given period, we count the number
of the blocks mined by it. Then we divide this number by the total number of
mined blocks in the period. Figure 6(a) and Figure 5 show that, in the most
popular blockchains, most of the time, one of the miners (mining pools) has
the collective power higher than $20\%$.

Pool | Number of mined blocks | Percentage of total mined blocks
---|---|---
Foundry USA | $11851$ | $22.281\%$
AntPool | $8670$ | $16.301\%$
F2Pool | $7848$ | $14.755\%$
Binance Pool | $6164$ | $11.589\%$
ViaBTC | $5162$ | $9.705\%$
Poolin | $4438$ | $8.344\%$
BTC.com | $2252$ | $4.234\%$
SlushPool | $2142$ | $4.027\%$
Luxor | $1362$ | $2.561\%$
SBI Crypto | $963$ | $1.811\%$
Braiins Pool | $715$ | $1.344\%$
unknown | $698$ | $1.312\%$
MARA Pool | $307$ | $0.577\%$
Terra Pool | $149$ | $0.280\%$
ULTIMUS POOL | $147$ | $0.276\%$
KuCoinPool | $101$ | $0.190\%$
EMCDPool | $80$ | $0.150\%$
PEGA Pool | $76$ | $0.143\%$
Table 3: The scale of mining hashrates of the most significant mining pools
and independent miners of Bitcoin in 2022. Data sources: [1].

(a)

(b)

Figure 6: (a) Collective power of top mining pools in 2022 for selected
Blockchains, monthly data [1], [3], [2]. (b) Collective number of hashes per
second calculated by all miners in 2022 [$10^{20}$ hashes/second], weekly data
[5].