Sliding Window Challenge Process for Congestion Detection

Ayelet Lotem¹, Sarah Azouvi², Patrick McCorry³ and Aviv Zohar¹

¹ The Hebrew University of Jerusalem, fayelem02,avivzg@cs.huji.ac.il ² Protocol Labs, sarah.azouvi@protocol.ai ³ Infura, stonecoldpat@gmail.com

Abstract. Many prominent smart contract applications such as payment channels, auctions, and voting systems often involve a mechanism in which some party must respond to a challenge or appeal some action within a xed time limit. This pattern of challenge-response mechanisms poses great risks if, during periods of high transaction volume, the network becomes congested. In this case, fee market competition can prevent the inclusion of the response in blocks, causing great harm. As a result, responders are allowed long periods to submit their response and overpay in fees. To overcome these problems and improve challenge-response protocols, we suggest a secure mechanism that detects congestion in blocks and adjusts the deadline of the response accordingly. The responder is thus guaranteed a deadline extension should congestion arise. We lay theoretical foundations for congestion signals in blockchains and then proceed to analyze and discuss possible attacks on the mechanism and evaluate its robustness. Our results show that in Ethereum, using short response deadlines as low as 3 hours, the protocol has > 99% defense rate from attacks even by miners with up to 33% of the computational power. Using shorter deadlines such as one hour is also possible with a similar defense rate for attackers with up to 27% of the power.

Keywords: Congestion, Challenge-Response

1 Introduction

DeFi platforms constructed over blockchains such as Ethereum have seen a recent boom of activity and interest. Their growing ecosystem allows for increasingly complex nancial interactions executed in a fully decentralized manner. The main building blocks used to construct these platforms are the smart contracts that dene the rules of interaction in code.

Smart contracts enable a wide range of applications, such as auctions, voting systems, and second layer protocols (e.g., payment channels) that operate above the blockchain layer. They typically provide rules that allow them to act as an automated adjudicator in case conicts between participants arise.

For many applications, interactions with smart contracts are time dependent and are even subject to deadlines, meaning that in some cases, transactions added after a specic moment will eectively be rejected. For example in the case of auctions, a bid must be received before the end of the auction otherwise it is not valid. Another example appears in the context of payment channels [12] where participants have a limited interval of time to dispute the division of funds if they disagree with their peers.

A major weakness of such deadlines is that in cases where the blockchain is congested, users that submit transactions will not have them included in blocks in time. In fact, several attacks and failures can be attributed directly to this weakness (we provide some examples below). One mitigation often employed by participants is to oer higher fees for transactions with deadlines which means users are usually overpaying. Another is to extend the deadlines which greatly delays processing and settlement within the context of the relevant smart contract. In many cases, transaction fees and deadlines are decided upon in advance, before the exact conditions that will prevail when the transaction is actually transmitted are known, which causes participants to take wider safety margins and increases costs further. Due to the well-known scalability issues of blockchains [1], we expect congested periods to become increasingly more common, which will directly impact the design of time-sensitive smart contracts.

Our Contributions. In this work we present a mechanism aimed at solving these issues. We propose to set short deadlines that are automatically extended if congestion occurs. We lay the theoretical foundations of congestion monitoring in blockchains and formalize the notion of challenge-response protocols in this context. We then propose two dierent protocols to detect congestion over multiple blocks: the ‘L Consecutive Blocks’ protocol denes uncongestion by the existence of L consecutive uncongested blocks; its generalization, the ‘Sliding Window (K-out-of-N)’ protocol, denes uncongestion by the existence of N consecutive uncongested blocks with K uncongested blocks among them. We show that the Sliding Window protocol is more resilient to attacks than the L Consecutive Blocks protocol when attacked by miners. Furthermore, we propose a new opcode for Ethereum that will provide the required functionality; we also provide an implementation (not requiring new opcodes) in Solidity, using opcodes introduced by Ethereum Improvement Proposal 1559 (EIP 1559) [5].

Examples of Congestion Attacks and Related Failures. A recent well-known example of congestion-related failure took place on Crypto Black Thursday (March 12th, 2020) when the price of Ethereum dropped by more than 50% in less than 24 hours [11]. This led to a panic-sale of coins and increased congestion. At the peak, during a 2-3 hour window, the Ethereum blockchain’s fees climbed to $1.65 on average, more than 10 times their cost on previous days.

The drop in ETH price triggered many MakerDAO auctions to liquidate collateral (typically collateral on short positions must be sold if prices uctuate too much). The tokens to be sold were purchased at almost no cost due to the inability of many bidders to send transactions and participate. This has, allegedly, been leveraged by one user to gain $8.3 million worth of ETH [3].

Several studies [10,13] deal with dierent types of attacks designed to prevent a party from responding on time to a challenge [10]. Harris and Zohar [13] present an attack where the attacker forces many victims at once to ood the blockchain with claims for their funds. The ensuing congestion allows the attacker to steal the funds that cannot be claimed before the deadline. Our protocol will prevent these issues by extending the deadlines until the congestion passes.

2 Related Work

Congestion is a real-world problem faced by the most prominent cryptocurrencies. In addition to the popular examples of Crypto Black Thursday or Cryptokitties, widely discussed online [3,11,6], Sokolov [17] examined periods of congestion caused by ransomware.

One way to deal with congestion is to improve the scalability of the underlying consensus protocol [19,20,18,7,9] or to introduce higher-level layers that help to scale. Solutions ranging from sharding [22], o-chain payment channels [12] or layer-zero optimization [21] (i.e., network-level optimization) have been considered. All these solutions improve the number of transactions per second that the network can process, but congestion may still occur even at higher rates.

Other methods that help to ensure that time-sensitive transactions are processed are rather ad-hoc. For example, the replace by fee [4] and child pays for parent [2] mechanisms allow users to add or change the fees of their transactions. Bitcoin’s fee mechanism|equivalent to a rst-price auction|is sub-optimal and often results in users paying more than what is necessary. EIP 1559 was made to change this mechanism in Ethereum [16,5]. EIP 1559 implements a base fee that is burned. This base fee can be seen as an indication of the level of congestion in recent blocks, and we utilize this in our implementation.

Another line of research that could potentially prevent transaction fees from spiking considers order-fairness consensus protocols [14,15]. The idea is to ensure that transactions are ordered in the blockchain in the same order they arrived in. This also helps to avoid problems such as front-running [8].

3 Preliminaries and Denitions

3.1 Challenge-Response Protocols

A challenge-response protocol is an implementation of a pattern in which some party must respond to a challenge within a xed time limit. This pattern consists of a challenge that takes eect at time T_cand a response deadline T_rdwhich is the latest time by which response to the challenge will be accepted. We call the time period between T_cand T_rdthe challenge window. Responding to the challenge during the challenge window yields dierent results compared to responding after the deadline. The protocol we propose inspects the challenge window period and extends it (by extending T_rd) as long as the blockchain stays congested.

$$ T_{c} $$

$$ T_{r d} $$

$$ T_{c} $$

$$ T_{r d} $$

$$ T_{r d}) $$

3.2 Blockchain Congestion

Our protocol has two components. First it relies on a mechanism to dene what it means for a block to be congested. We then use this denition to dene an uncongested period. Intuitively, a period will be (un)congested if some threshold of blocks is (un)congested. We start by dening block congestion before moving on to presenting dierent period congestion denitions and choosing one that meets our requirements.

Blocks and Transactions. A block B = ftx₁*;;*tx_ng is as a set of transactions (we ignore the order of transactions in the block as well as other data|such as nonce|as they are irrelevant to our problem). Transactions pending to be included in a block are kept locally by each node in their mempool until they are included in the chain. Each transaction tx has a size w(tx), and a fee density (tx). The fee paid by the transaction is therefore w(tx) (tx). We dene the total weight of transactions in a block B with a fee density above as WB( ) := P _{tx2B: (tx)}w(tx).

$$ \mathbf{B}=\left{\mathsf{t x}{1},\cdots,\mathsf{t x}{n}\right} $$

$$ w(t x) $$

$$ \phi(t x) $$

$$ w(t x)\cdot\phi(t x) $$

$$ {textstyle\sum_{t x\in B:\ \phi(t x)\geq\theta}w(t x)} $$

$$ \mathcal{W}_{\mathbf{B}}(\theta):= $$

Blocks can contain transactions with total size bounded by B, i.e., W_B(0) B. For simplicity, we treat every block as full, i.e., for any block W_B(0) = B (if necessary, we ll them articially with transactions with a fee of 0).

$$ \mathcal{B},\mathrm{i.e.,,},\mathcal{W}_{\mathbf{B}}(0)\leq $$

$$ \mathcal{W}_{\mathbf{B}}(0)=\mathcal{B};\mathrm{(i f} $$

total amount of fees collected from a block by the miner is UB:= P The _tx2Bw(tx) (tx). If the size of the mempool is bigger than the maximum block size W_B(0), we assume that honest miners choose the transactions in a way to maximize the fees they get.

$$ {mathcal U_{{\mathrm{B}}}}:= $$

$$ \textstyle\sum_{t x\in B}w(t x)\cdot\phi(t x) $$

$$ \mathcal{W}_{\mathbf{B}}(0) $$

Period. A period Pe = (b₁;b₂;:::;b_n) in the blockchain is a non-empty sequence of consecutive blocks. We denote the length (number of blocks) of the period by jPej = n, and write for i 2f1*;:::;ng*: Pe[i] = b_i2 Pe. For a period P₂, we say that period P₁ is included in P₂ and note P₁ P₂ if every block in P₁ is included in P₂.

$$ P e=(b_{1},b_{2},...,b_{n}) $$

$$ |P e|=n $$

$$ i\in{1,...,n};P e|i|=b_{i}\in P e $$

$$ P_{2} $$

$$ P_{1} $$

$$ P_{2} $$

$$ P_{1}\subseteq P_{2} $$

$$ P_{1} $$

$$ P_{2} $$

In this work, we want to capture the notion of congestion: a phenomenon where there’s a spike in the number of transactions waiting in the mempool. Since the mempool is not part of the blockchain, we instead rely on the data in the blocks in order to dene congestion. We propose the following denition for block congestion.

Denition 1((;)-congestion). We say that a single block B is (;)-conges- ted if W_B( ) B and denote C_;(B) = 1*, where C*_;is the corresponding indicator function.

$$ ((\theta,\gamma) $$

$$ \mathcal{W}_{\mathbf{B}}(\theta)\geq\gamma\cdot\mathcal{B} $$

$$ (\theta,\gamma) $$

$$ \mathcal{C}_{\theta,\gamma}(\mathbf{B})=1 $$

$$ \mathcal{C}_{\theta,\gamma} $$

Per this denition, all transactions above fee density are examined and required to make up at least a-fraction of the block in terms of size. Intuitively, for = 1 the denition captures that if a block is (*;*1)-congested, a transaction needs to have a fee density that is at least in order to have a better chance of being included. In other words, we use the price of entering a transaction to the blockchain as a reliable signal for congestion.

$$ \gamma=1 $$

For a block B and a fee density 0, we dene the*-weight threshold* B( ) as the maximum fraction of the block weight under which the block is WB() (;)-congested. From denition1it is clear that^{B( )} =. Similarly, for B a block B and a fraction 0, we dene the*-fee density threshold*_B() as the maximum fee density under which the block is (;)-congested (_B() := maxf jC_;(B) = 1g).

$$ \theta,\geq,0 $$

$$ \gamma_{\mathbf{B}}(\theta) $$

$$ (\theta,\gamma) $$

$$ \mathbf{\bar{\gamma}}{\mathbf{B}}(\theta)=\frac{\mathcal{W}{\mathbf{B}}(\theta)}{\mathcal{B}} $$

$$ \gamma-f e e $$

$$ \gamma\geq0 $$

$$ \theta_{\mathbf{B}}(\gamma) $$

$$ (\theta_{\mathbf{B}}(\gamma):= $$

$$ {\theta\mid\mathcal{C}_{\theta,\gamma}(\mathbf{B})=1}) $$

Block Manipulation. One of the key measures we are interested in is when is an adversary able to manipulate blocks’ congestion signals. When a miner mines a block, they can choose to include transactions from their mempool or to add dummy transactions that move money between their accounts and pay a fee (to themselves), making the fees appear dierent than they ought to be. However, miners cannot manipulate blocks at arbitrary heights, and doing so would incur a cost. The miner’s chance of mining a new block depends on its relative computational power. Therefore, as is standard, we denote the computational power of an adversary by. Each block has a probability to be mined by the adversary, and 1 to be mined by the other miners. Furthermore, giving up mempool transactions means missing out their fees and hence induces a loss that we compute in the next two propositions.

$$ 1-\alpha $$

Proposition 1. An adversary manipulating a block B to make it (1*;1)-conges-* R₁ ted when it is not, will lose a potential prot of at-least B_B()d. _{1 ( 1 B( 1))}

$$ (\theta_{1},\gamma_{1}) $$

$$ \ \mathcal{B}{\cdot}{\textstyle\int}{1-(\gamma{1}-\gamma_{\mathbf{B}}(\theta_{1}))}^{1}{\theta_{\mathbf{B}}}(\gamma),d\gamma $$

Proposition 2. An adversary manipulating a block B to reverse its signal from (₁;₁)-congested to not congested will lose a potential prot of at-least B R() _{B 1} (B()₁)d. 1

$$ (\theta_{1},\gamma_{1}) $$

$$ \textstyle{\int_{\gamma_{1}}^{\gamma_{\mathbf{B}}(\theta_{1})}(\theta_{\mathbf{B}}(\gamma)-\theta_{1})d\gamma} $$

The proofs for both propositions can be found in AppendixA.1.

Before moving on to dene period congestion, we note that there exist other ways in which block congestion could be dened. For example, in Section5, we take the EIP 1559 base fee as a measure of congestion and use it to implement our suggested protocol. We include several other examples that are less ecient in AppendixB.

Congestion Vector of a Period. To determine whether a period Pe is uncongested c n n we will refer to the congestion ve^ctor Pe := (C(Pe[i]))ⁱ⁼¹2 f0*;* 1g which consists of the congestion signal of its blocks. Intuitively, if most of the blocks in the period are congested then the period is congested and vice-versa. However, we must also account for the fact that an adversary may be able to change the congestion signal of some of the blocks, as already discussed. We will consider dierent protocols to dene period uncongestion, a situation in which the period is considered not congested. An uncongestion period protocol is a function that we denote by UCP: f0*;* 1g!f0*;* 1g. This function takes as input a binary series representing the congestion signal of the blocks in the examined time period. It will return 0 if the period is congested and 1 otherwise. This function can furthermore be extended to also provide auxiliary information such as a proof

$$ P e^{c},:=,({\mathcal{L}}\ P e[i])_{i=1}^{n},\in,{0,1}^{n} $$

$$ \mathrm {U C P}: {0, 1 } ^ {*} \rightarrow {0, 1 } $$ in the case where the period is uncongested. For the eciency of the protocol, we will strive for a denition that can provide a compact and easy-to-verify proof. Throughout the rest of the paper, we use B(n;p) to denote the binomial distribution with parameters n and p.

$$ B(n,p) $$

Denition 2(Period Manipulation). For a period Pe and an adversary with a fraction of the total computational power, we associate a manipulated period Pe^ dened as follows. For i 2f1*;:::; jPejg the adversary can replace Pe*[i] with probability, with a block that has a congestion signal of their choice. We denote by m = m_jPej() B(jPej;) the vector that indicates which of the blocks in the given period the adversary controls, meaning the adversary can replace the Pe[i] block’s congestion signal i m[i] = 1*. We then dene the adversary’s* ^ c jPej manipulation set S_m;Pe:= fPe 2 f0; 1g j 81 i jPej : m[i]=0*)* ^ _{c c} Pe [i] = Pe [i]g. Intuitively, S_m;Pecorresponds to the set of possible congestion vectors that the adversary could create by changing the signal of the blocks that it controls.

$$ \hat{P}e $$

$$ i\in{1,\ldots,|P e|} $$

$$ P e[i] $$

$$ \overline {{m}} = m _ {| P e |} (\alpha) \sim B (| P e |, \alpha) $$

$$ P e[i] $$

$$ {\mathit{i f f}},{\overline{{m}}}[i]=1 $$

$$ S_{\overline{{m}},P e};:=;{\hat{P e^{c}};\in;{0,1}^{|P e|};;|;;\forall1;\leq;i;\leq;|P e|;:;\overline{{m}}[i];=;0;\Rightarrow $$

$$ \hat{P e}^{c}[i]=P e^{c}[i]} $$

$$ S_{\overline{{m,P e}}} $$

In a real world setting, even if there is a long period of uncongestion, it could be the case that one or more of the blocks are fuller than the others due to some randomness in the transactions’ arrival time (e.g., there was a temporary high transaction volume). To account for this randomness, we make a simplifying assumption that blocks are congested independently with probability p and say that the blockchain is p congested. We note that, in reality, congestion is often changing and is usually correlated when considering several consecutive blocks. We leave more complex models of congestion for future work. In our case, the congestion vector of a period Pe chosen at random has a binomial distribution: ^c Pe B(n;p). When studying attacks where the adversary tries to convert a congested period to an uncongested one, we will assume that p is close to one (i.e., most of the blocks are congested), whereas when studying the opposite case, we will consider p to be close to zero.

$$ P e $$

$$ P e^{c},\sim,B(n,p) $$

Our protocol consists in extending the deadline of challenge-response in the event of a congestion period. However, to avoid an edge case where the deadline is extended indenitely, we dene M^, an upper bound on the total length of the extended period.

Denition 3(M^ -maximum Extension). Given a challenge-response proto- col in a p congested blockchain where the challenge starts at block height h, we say that M^ is the maximum extension of the challenge if the deadline cannot be extended further than height h + M^.

3.3 Desirable Properties of Protocols

In this section, we dene some properties that we aim for our protocol to achieve.

In the rest of the paper we use the notation D s to denote that s was selected randomly from the distribution D. We start by describing the two types of attack that we will consider|a congestion attack and an uncongestion attack| before dening the robustness of the protocol, which captures the security of the protocol against either attack.

Denition 4(Congestion/Uncongestion Attack on Pe). Given a period Pe, chosen at random in a p-congested blockchain, we say that the adversary wins a congestion, resp. uncongestion, attack on Pe if it can manipulate Pe into an uncongested, resp. congested, period.

$$ P e) $$

$$ P e. $$

Denition 5((;p;q;n)-congestion Robustness). We say an uncongestion period protocol UCP:f0*;* 1g!f0*;* 1g is (;p;q;n)-congestion robust if, given an adversary with a relative computational power, his probability of winning a congestion attack, i.e., of successfully manipulating a period Pe of n blocks into a congested period Pe^, is less than q.

$$ ((\alpha,p,q,n) $$

$$ \mathcal{U}C P\ :{0,1}^{*}\rightarrow{0,1} $$

$$ (\alpha,p,q,n) $$

$$ i!, $$

$$ i.e. $$

$$ \hat{P}e. $$

$$ B(n,p)\leftarrow P e\ :\ P_{r}(\exists\hat{P e}\in S_{\overline{{m}},P e}\mathrm{}{s.t.}\hat{U C P}(\hat{P e})=0)\leq q. $$

Denition 6((;p;q;n)-uncongestion Robustness). We say an unconges- tion period protocol UCP:f0*;* 1g!f0*;* 1g is (;p;q;n)-uncongestion robust if, given an adversary with a relative computational power, his probability of winning an uncongestion attack, i.e., of successfully manipulating a period Pe of n blocks into an uncongested period Pe^, is less than q.

$$ ((\alpha,p,q,n) $$

$$ \mathcal{U}\mathcal{C}!{:{\ {0,1}}^{*}}\rightarrow{{0,1}} $$

$$ (\alpha,p,q,n) $$

$$ i{f,} $$

$$ {\hat{P}}{e,} $$

$$ P e $$

$$ q $$

$$ B(n,p)\xleftarrow{}\ P e\ :\ P_{r}(\exists\hat{P e\ \in\ }S_{\overline{{m}},P emathit{\ s.t.\ }\mathit{U C P}(\hat{P e})}=1)\leq q. $$

Denition 7(Monotonicity). A congestion protocol is monotone if for ev- ery two periods Pe₁ and Pe₂, if Pe₁ Pe₂ and Pe₁ is considered uncongested, c c then so is Pe₂, i.e., 8Pe₁ Pe₂ : UCP(Pe₁) = 1*! UCP(Pe*₂) = 1*.*

$$ P e_{1} $$

$$ P e_{2} $$

$$ P e_{1}\subseteq P e_{2} $$

$$ P e_{1} $$

$$ \mathit{P e}{2},\ \mathit{i.e.},\ \forall\mathit{P e}{1}\subseteq\mathit{P e}{2}:\mathit{U C P}(\mathit{P e}{1}^{c})=1\to\mathit{U C P}(\mathit{P e}_{2}^{c})=1 $$

A monotone protocol is easier to verify as the prover only needs to select a portion of blocks from the time period Pe in order to prove uncongestion. Furthermore, a monotone protocol requires only sporadic access to the blockchain. A prover can go oine and prove uncongestion when they come back online by choosing any uncongested period from the time they were oine. In the case of a non-monotonic protocol, if the prover is oine during an uncongested period, they cannot prove the uncongestion of the longer period, after they came back online, they missed the uncongested period.

$$ P e $$

Eciency Properties. We dene two properties that capture the eciency of the protocol.

{Concise proof size The evidence needed to prove uncongestion of a period should be as concise as possible.

{Concise refresh information The extra information needed to be kept when checking the congestion signal of a period that has already been extended due to congestion should be as concise as possible. Ideally, when we extend a period from Pe₁ to Pe₂ in order to check Pe₂ for congestion, we should not have to recheck every block in Pe₁ but, rather, aggregate this information.

$$ P e_{1} $$

$$ P e_{2} $$

$$ P e_{2} $$

$$ P e_{1} $$

In the next section we will discuss dierent period congestion protocols with the goal of nding one that will be proof ecient and robust against an attacker with reasonable hash rate with high probability.

4 Uncongested Period Protocols

In this section, we examine dierent protocols that t the denition of congestion of a period Pe. We start by presenting \naive" protocols and discuss why they are not good enough, i.e., why they lack the desirable properties dened in Section3.3.

4.1 Strawman Protocols

Denition 8(Cumulative M). Period Pe is uncongested if there exists M P c blocks which are uncongested: UCP_CM(Pe) = 1 $_b2Pe(1 C(b)) M.

$$ U C P _ {C M} \left(P e ^ {c}\right) = 1 \Leftrightarrow \left(\sum_ {b \in P e} \left(1 - \mathcal {C} (b)\right) \geq M\right) $$

This protocol is monotonic but is not suciently robust to adversarial attacks: if we wait long enough, the probability of the adversary controlling M blocks becomes overwhelming (even if is small). We solve this in the next strawman by considering the percentage of blocks instead of a xed number.

Denition 9(Percentage). A period Pe is uncongested if x% of its blocks are P c x not congested: UCP_PC(Pe) = 1 $_b2Pe(1 C(b)) jPej . ₁₀₀

$$ \textstyle\ {C{\mathsf P}{P C}(P e^{\bar{c}})}stackrel!==1\leftrightarrow(\sum_{b\in P{}e}(1-\mathcal{C}(b))\geq\frac{x}{100}\cdot|P e|) $$

This protocol is much more robust but has the drawback of not being monotonic. For example, if all blocks are uncongested during the rst part of the period and congestion begins in the second part, then the beginning of the period is uncongested while the whole period may not be.

We now suggest the following monotonic rule:

Denition 10(L Consecutive Blocks). A period Pe is uncongested if there exists at least L consecutive uncongested blocks included in it: c ^c UCPL(Pe) = 1 $ (9 1 i jPej L + 1 s:t: 8 0 j L 1 : Pe [i + j] = 0).

$$ \ {it U{\ C P P}}_{L}(P e^{e})=1\leftrightarrow(\exists\ 1\leq i\leq|P e|-L+1\ s.t.\ \forall\ 0\leq j\leq L-1:P{}it e^{c}[i+j]=0) $$

We show that this protocol is monotonic and inspect its eciency in AppendixA.2. We now evaluate its robustness.

Evaluation of the Robustness of the L Consecutive Blocks protocol. We examine situations where the adversary attempts to manipulate the congestion signal for a given period. We separate this into two attacks: uncongestion and congestion attacks (as in Denition4). We strive to achieve a high defense rate against both attacks, meaning nding a value L that will give a low probability for an adversary to succeed in each of the attacks separately.

Evaluation of the Uncongestion Attack. In order to compute the probability of an attacker to successfully manipulate Pe into an uncongested period, we dene the following matrix T_{(L+1) (L+1)}: 8

$$ T_{(L+1)\times(L+1)}\colon $$

$$ \forall\ 0\leq i,j\leq L:\ \ T_{i,j}=\begin{cases}{(1-\alpha)\cdot p}&{\mathrm{i f}j=0\wedge i\neq l}\ {\alpha+(1-\alpha)\cdot(1-p)}&{\mathrm{i f}j=i+1}\ {1}&{\mathrm{i f~}i=j=L}\ {0}&{\mathrm{o t h e r w i s e}}\ \end{cases} $$

(1)

th and denote by e_i^the i unit vector of dimension L+1 (i.e., e_ihas a 1 in the ^th i coordinate and 0’s elsewhere).

$$ i^{t h} $$

$$ e_{i} $$

$$ L\mathrm+1\ (\mathrm{i.e.},,e_{i} $$

$$ i^{t h} $$

Theorem 1. The probability of an attacker with a relative computational power to successfully manipulate Pe into an uncongested period in a p-congested n tL network equals e₁ T e₊₁.

$$ P e $$

$$ e_{1}\cdot T^{n}\cdot e_{L+1}^{t} $$

Proof. We note that, at each block, the attacker has a probability to mine the next block, which allows them to decide its congestion level. In this context, this means setting the block to be uncongested. In addition, the congestion signal of a block not mined by the attacker depends on the prevailing congestion state which is expressed by p. The probability of an honest block being congested, resp. uncongested, is hence equal to (1) p, resp. + (1) (1 p). We dene the following Markov chain that describes a random walk on Pe’s blocks and whose states represent the number of consecutive blocks that are uncongested at a point in time.

$$ (1-\alpha)\cdot p. $$

$$ \alpha+\left(1-\alpha\right)\cdot\left(1-p\right) $$

$$ P e^{\flat} $$

The initial state is 0 since it corresponds to the 0 consecutive uncongested blocks at the beginning of the walk. With each step, we move from state i to state i + 1, for i < L, if the block is uncongested, and return to state 0 if it is not. If we reach state L, we stay there since it means the adversary has reached the goal of L consecutive uncongested blocks in Pe and can manipulate it to an uncongested period.

$$ i+1 $$

$$ i<L $$

$$ P e $$

T is the corresponding transition matrix; hence the probability of reaching n tL state L in jPej = n steps is expressed by e₁ T e₊₁.

$$ e_{1}\cdot T^{n}\cdot e_{L+1}^{t}. $$

$$ |P e|=n $$

Evaluation of the Congestion Attack. For the attack in the opposite direction we dene T^ as follows: (L+1) (L+1)

$$ T_{(L+1)\times(L+1)} $$

$$ \forall 0 \leq i, j \leq L: \hat {T} _ {i, j} = \left{ \begin{array}{l l} \alpha + (1 - \alpha) \cdot p & \text {if} j = 0 \wedge i \neq L \ (1 - \alpha) \cdot (1 - p) & \text {if} j = i + 1 \ 1 & \text {if} i = j = L \ 0 & \text {o t h e r w i s e} \end{array} \right. $$

(2)

Theorem 2. The probability of an attacker with a relative computational power to successfully manipulate Pe into a congested period, in a p-congested network ^n tL equals 1 e₁ T e₊₁.

$$ 1-e_{1}\cdot\dot{T^{n}}\cdot e_{L+1}^{t} $$

Proof. This time, if the attacker succeeds in mining a block, they will make it congested. Therefore the probability for a block to be uncongested is (1) (1 p). As before, we dene the following Markov chain whose states represent the number of consecutive blocks that are uncongested at a point in time in Pe:

T^ is the corresponding transition matrix. Therefore, the probability for the adversary to succeed in the congestion attack is equivalent to the probability that the rest of the miners will not reach the L state in n steps, which is expressed ^n tL by: 1 e₁ T e₊₁.

$$ 1-e_{1}\cdot\hat{T^{n}}\cdot e_{L+1}^{t} $$

Now that we have the attacks’ success rates, we examine the robustness of the protocol against both attacks for dierent values of L.

Although attacks are potentially expensive for the adversary (who needs to change the contents of its block and, hence, loses transaction fees), we still desire a low success probability for the attack even for strong attackers. We assume in the following evaluations that the attacker controls 33% of the computational power.

Given that congestion may cause period extension, we need a value for L that gives protection also against attacks over longer periods. We examine the behavior of the protocol for periods as long as M^ using dierent values for L.

The value p should represent realistic network conditions. For our analysis we pick p = 0*:* 85 when studying the congestion attack, to simulate more congested settings, or p = 0*:* 15 when studying the uncongestion attack, to simulate relatively uncongested settings. Other values can be plugged in, if needed, for other conditions. We start by examining the robustness of the protocol for a period of 1 day.

$$ p=0.85 $$

$$ p=0.15 $$

Figures1a-1bpresent the probability of success in both attacks for two dierent period lengths: 6450 blocks in Figure1aand 144 blocks in Figure1b. These periods correspond, roughly, to a single day in Ethereum and a single day in Bitcoin. The red curves correspond to the congestion attack and the blue curves to the uncongestion attack. We compute these probabilities for dierent values of L.

$$ L. $$

The results in both gures show there is no value L that gives a probability of success less than 1% for both attacks. Formally, it shows that the L Consecutive Blocks protocol cannot be simultaneously (0*:* 33*;* 0*:* 15*;* 0*:* 01*;* 1 day)-congestion robust and (0*:* 33*;* 0*:* 85*;* 0*:* 01*;* 1 day)-uncongestion robust. Therefore, we nd the L Consecutive Blocks protocol not suciently secure. Intuitively, this is because more robust estimates of congestion are typically obtained over longer observa-

(a) jPej = 6450 1 day in Ethereum

$$ |P e|=6450\sim1 $$

(b) jPej = 144 1 day in Bitcoin

$$ |P e|=144\sim1 $$

Fig. 1: Attack success rate as a function of L, for = 0*:* 33

$$ \alpha=0.33 $$

tion windows. The L Consecutive Blocks protocol obtains longer observations if L is increased, but then the requirement for consecutive blocks to be uncongested is too strict and is not robust. As a result of this insight, we propose a new protocol that generalizes the L Consecutive Blocks protocol and allows for longer observation windows with a relaxed condition for uncongestion.

4.2 Sliding Window (K-out-of-N) Protocol

Denition 11(K-out-of-N Sliding Window). A period Pe is uncongested if there exists a period Pe^ of length N included in it in which at least K blocks are uncongested.

$$ \hat{P}e $$

$$ \mathsf{U C P}{S W}(P e^{c})=1\leftrightarrow\left(\ \exists\ \hat{P e}\subseteq P e:|\hat{P e}|=N\wedge\left(\sum{b\in\hat{P e}}(1-\mathcal{C}(b))\geq K\right)\right) $$

We note that the L Consecutive Blocks protocol is a special case in which L = N = K.

$$ L=N=K $$

Proposition 4. The Sliding Window protocol is monotonic.

Proof. Given an uncongested period Pe₁, according to the Sliding Window protocol, which is included in period Pe₂: 0 0 11

$$ P e_{1} $$

$$ P e_{2} $$

$$ \begin{aligned}{}&{{}\mathsf{U C P}{S W}(P e{1}^{c})=1\Rightarrow\left(\exists\ \hat{P e}\subseteq P e_{1}:|\hat{P e}|=N\land\left(\sum_{b\in\hat{P e}}\mathcal{C}(b)\geq K\right)\right)}\ {}&{{}P e_{1}\subseteq P e_{2}\Rightarrow\left(\hat{P e}\subseteq P e_{2}\right)\land\left(\sum_{b\in\hat{P e}}\mathcal{C}(b)\geq K\right)}\ {}&{{}\Rightarrow\mathsf{U C P}{S W}(P e{2}^{c})=1}\ \end{aligned} $$

We now evaluate its eciency.

Proof Size. In order to provide evidence for the uncongestion of a period Pe of size n, it is enough to point to a window in which uncongestion occurs. Formally, Pi+N to present = i 2f1*;:::;n K* + 1g s.t._l=i(1 C(Pe[l])) K.

$$ P e $$

$$ n, $$

$$ \mathrm {e n t} \pi = i \in {1, \dots , n - K + 1 } \mathrm {s . t .} \sum_ {l = i} ^ {i + N} (1 - \mathcal {C} (P e [ l ])) \geq K. $$

Refresh Information. Given a congested period Pe, and Pe^ that extends it, in order to determine the congestion level of the extended period UCP (Pe^ c), it SW is enough to check only windows that overlap blocks in Pe^ n Pe.

$$ P e, $$

$$ \hat{P},e\ {\hat{}} $$

$$ \mathsf{U C P}_{S W}(\hat{P e}^{c}) $$

$$ \hat{P e}\setminus P e $$

Evaluation of the Sliding Window Protocol’s Robustness. We consider the two attacks in Denition4. We rst note that the two attacks may dier in their consequences. While the congestion attack can cause a delay in the response deadline (i.e., a deadline will be extended even if it is not really needed), the uncongestion attack might lead participants to miss the chance to respond on time, as the deadline will not be extended even if the network is congested. The damage in each case depends on the particular use case. For example, in the case of payment channels, not responding in time is more severe and may lead to nancial losses. We strive to achieve a high level of security against both types of attack, i.e., to nd values for parameters (N;K) that will yield a low probability of success for both.

We begin by presenting upper bounds on the probabilities of success in each of the attacks.

Theorem 3. The probability of an attacker with a relative computational power to successfully manipulate Pe into an uncongested period, in a p-congested PN N j N j network, is bounded above by (n N + 1)_j=Kq (1 q), for _j q = + (1 p) (1).

$$ P e $$

$$ (n,-,N,+,\mathbf{1}),\cdot,\sum_{j=K}^{N}\ \textstyle{\binom{N}{j}},\cdot,q^{j},\cdot,(\mathbf{1},-,q)^{N-j} $$

$$ q=\alpha+\left(1-p\right)\cdot\left(1-\alpha\right) $$

Proof. The probability for a block to be uncongested during this attack is q =

• (1 p) (1). In a period of size n, there are n N + 1 dierent sliding windows. We denote by A_ithe event in which there are K out of N uncongested th blocks in ^the i sliding window. Therefore, the probability of a single sliding PN N j N j window being uncongested is P (A_i) =_j=Kq (1 q). To succeed in the j uncongestion attack, at least one of the sliding windows has to be uncongested, n N+1 which is expressed by P ([_i=1A_i). We use the union bound to bound this probability a_nd get: P_{n N+1}P_N n _N+1 N _{j N j} P ([ A) P (A) = (n N + 1) q (1 q)

$$ \alpha+\left(1-p\right)\cdot\left(1-\alpha\right) $$

$$ q= $$

$$ n. $$

$$ n-N+1 $$

$$ A_{i} $$

$$ i^{t h} $$

$$ P(A_{i})=\sum_{j=K}^{N}\binom{N}{j}{\cdot}q^{j}{\cdot}(1{-}q)^{N-j} $$

$$ P\bigl(\cup_{i=1}^{n-N+1}A_{i}\bigr) $$

$$ \dot{P}(\cup_{i=1}^{n-N+1}A_{i})\stackrel{\v ri{\ \ }}{\sum}{i=1}^{n-N+1}P\big(A{i}\big)=(n-N+1\ \big)\cdot\sum_{j=K}^{N}\binom{N}{j}\cdot q^{j}\cdot\big(1-q\big)^{N-j}\quad\square $$

Theorem 4. The probability of an attacker with a relative computational power to successfully manipulate Pe into a congested period, in a p-congested network PK 1n N j N j b c is bounded above by ( q (₁ q))_N, for q = (1 p) (1). j=0 j

$$

$$

$$ q=\left(1-p\right)\cdot\left(1-\alpha\right) $$

Proof. The probability for a block to be uncongested is q = (1 p) (1). We denote by B_ithe event in which there are less than K uncongested blocks th in ^the i sliding window. The probability of a single sliding window being con- PK 1 N j N j gested is P (B_i) =_j=0q (₁ q). To succeed in the congestion j attack, all sliding windows in the period must be congested, which is expressed bnc n N+1 N by P (*ⁱ⁼¹Bⁱ). We bound this probability by P (*ⁱ⁼¹B^{N (i 1)+1}), i.e., we consider a subset of events B_ithat are independent from each other (removing overlapping windows). We compute the intersection of the pairwise independent bncQbnc n N+1 N N events and get: P (*_i=1Bi) P (*_i=1B_N (_i 1)+1) =i=1P (B_{N (i 1)+1}) = PK 1_{n N} j N j b c ( q ₍₁ q))_N. _j=0 j

$$ q=\left(1-p\right)\cdot\left(1-\alpha\right) $$

$$ B_{i} $$

$$ i^{t h} $$

$$ P(B_{i})\tilde{} $$

$$ P(\cap_{i=1}^{n-N+1}B_{i}) $$

$$ P(\cap_{i=1}^{\left\lfloor{frac{n}{N}}\right\rfloor}B_{N\cdot(i-1)+1}) $$

$$ B_{i} $$

$$ P(\cap_{i=1}^{n-N+1}B_{i})\leq P(\cap_{i=1}^{\lfloor\frac{n}{N}\rfloor}B_{N\cdot(i-1)+1})=\prod_{i=1}^{\lfloor\frac{n}{N}\rfloor}P(B_{N\cdot(i-1)+1})= $$

$$ \left(\sum_ {j = 0} ^ {K - 1} \binom {N}{j}\right) \cdot q ^ {j} \cdot (1 - q) ^ {N - j}) ^ {\lfloor \frac {n}{N} \rfloor} $$

We would like to compute the robustness of the protocol for 1 day to 1 hour sliding windows. We examine the situation where a period Pe of size n is chosen at random and the blockchain is p congested for values of p = 0*:* 85 (relatively congested) and p = 0*:* 15 (relatively uncongested) against an attacker with computational power 0*:* 33. In the evaluation, we allow periods to be extended up to two weeks, a reasonable time for congestion to pass. We set the M^ -maximum extension (see Denition3) accordingly (90300 blocks in Ethereum and 2016 blocks in Bitcoin).

$$ P e $$

$$ p-c o n g e s t e $$

$$ p=0.85 $$

$$ p=0.15 $$

$$ \alpha\leq0.33 $$

We rst evaluate the attack over Ethereum, computing the above bounds for dierent sliding window sizes. We begin with a sliding window of 1 day N (N = 6450), setting K = = 3²25. Figure2presents the two upper bounds 2 for the dierent possible period lengths N n M^. For the protocol to be considered secure, we need low values in both curves for the dierent period lengths (since periods might be extended). As can be seen, the probabilities in the graph are extremely low, showing the protocol to be very secure. We emphasize that the blue curve is not horizontal, as shown in the graph; all of 323 its values are smaller than 10. Note that these are only upper bounds; the actual probabilities are even lower.

$$ (N=6450) $$

$$ K=\frac{N}{2}=3225 $$

$$ N,\leq,n,\leq,\hat{M} $$

$$ 10^{-323} $$

Fig. 2: Upper bounds on the attacks’ success rates as a function of the period length, for M^ = 90300*;N* = 6450*;K* = 3225*;* = 0*:* 33

$$ \hat{M}=90300,N=6450,K=3225,\alpha=0.33 $$

We evaluate the attack for smaller sliding windows. The following table summarizes our results:

$$ \ overlineoverline\ {{<10^{-323}}} $$

$$ \overline{{1.44\times10^{-29}}} $$

$$ 1.26\times10^{-10} $$

$$ 8.06\times10^{-16} $$

$$ 7.14\times10^{-5} $$

$$ 1.08\times10^{-7} $$

$$ 8.87\times10^{-3} $$

$$ 3.16\times10^{-3} $$

The wider the sliding window is, the greater the protection. For smaller sliding windows, such as 1 hour (N = 269), we can achieve a 99% defense rate against each attack if we lower the attackers’ computation power to 0*:* 27 (instead of 0.33). We provide examples of N;K values and the level of protection they provide (an upper bound), but these are congurable and subject to the user’s discretion. One can choose to increase the level of protection from one attack at the expense of the other, or to set a larger initial period length (> N) to increase the protection.

$$ \alpha\leq0.27 $$

Next, we want to know what happens with smaller periods such as in Bitcoin, which has longer block intervals. To do so, we set M^ = 2016 and begin with a sliding window of 1 day (N = 144).

c^ We use a simulation to draw 100,000 samples Pe B(M;p) of congestion vectors and to compute the success rates of both attacks among the samples (Figures3a,c,d). We use error plots to plot the standard error of the data; however, the errors are very small and therefore are almost invisible in the graphs.

$$ P e^{c}\sim B(\hat{M},p) $$

Figure3apresents the probability of success in each of the attacks for different K values. As the graph shows, choosing K = 89 gives protection against both attacks. We compute the upper bounds (from Theorems3-4) for this value of K in Figure3b. The presented bounds as they appear in the graph are loose compared to the simulation results and aord a low level of defense, especially against the congestion attack. These bounds give us useful, but non-tight, upper bounds on the results for periods that are of longer length, for which the probability is extremely small. To get more precise results, we use more simulations to compute the congestion attacks’ success rate for dierent period lengths and present the results in Figure3c. Each curve corresponds to a dierent value of, the computational power of the attacker. The defense rate against congestion attacks is extremely low for short periods. For = 0*:* 33, we reach a > 99% defense rate only for periods of 11 days or more. Lowering the computational power of the adversary naturally improves these results. For example, considering an attacker with computational power = 0*:* 2 results in an above 0*:* 9995 defense rate for period lengths starting from 2 days.

Finally, in Figure3dwe consider an attacker with a computational power = 0*:* 2 and show the congestion attack success rate for dierent choices of N;K correspondig to sliding windows of lengths 24/12/6/3 hours. We do not present the uncongestion attack results which had above 99% defense rate for any N n M^ = 2016.

$$ N\leq n\leq\hat{M}=2016 $$

We conclude that the longer the periods are, the higher and more eective the protection against attacks is. In Ethereum, we obtained very high defense rates

(a) Attack success rate as a function of K, for n = 2016*;N* = 144*;* = 0*:* 33

$$ n=2016,N=144,\alpha=0.33 $$

(b) Upper bounds on the attacks’ success rates as a function of the period length, for N = 144*;K* = 89*;* = 0*:* 33

(c) Congestion attack success rate as a function of the period length, for N = 144*;K* = 89

$$ N=144,K= $$

(d) Congestion attack success rate as a function of the period length, for = 0*:* 2

$$ \alpha=0.2 $$

Fig. 3: Evaluation of the attacks’ success rates for M^ = 2016 (2 weeks in Bitcoin)

$$ \hat{M}=2016 $$

even when choosing short sliding window sizes and against strong attackers. In Bitcoin, on the other hand, we need to compromise on the window size and on the attackers’ power to achieve higher defense.

We dened uncongested period protocols and suggested a concrete one, the Sliding Window protocol, which meets our requirements (as dened in Section3.3). In the next section, we will describe how to use an uncongested period protocol to adjust the challenge-response protocol to deal with congested periods.

4.3 Application to Challenge-Response Protocols

A challenge-response protocol consists of a challenge that takes eect at time T_cand a response deadline T_rd(see section3.1). We link T_cand T_rdto their corresponding block height and denote by b(T) the block at height T.

$$ T_{c} $$

$$ T_{r d} $$

$$ T_{c} $$

$$ T_{r d} $$

$$ T $$

The parties involved in the challenge decide in advance on an uncongestion period protocol UCP to use. We recall that UCP: f0*;* 1g! f0*;* 1g accepts a congestion vector (a binary series representing the congestion signal of blocks in a period) and returns 1 if the period is congested and 0 otherwise. To apply the uncongestion period protocol, the parties adjust T_rdto a short deadline that gives them a reasonable time to respond to the challenge assuming an optimal case with no congestion.

$$ \mathsf{U C P}!:{0,1}^{*},\to,{0,1} $$

$$ T_{r d} $$

The response deadline T_rdis applied only in the event that the challenge window Pe = (b(T_c);b(T_c+ 1);:::;b(T_rd)) is uncongested. In the case where the challenge window is congested, we repeatedly extend T_rd, 1 block at a time, as long as it remains congested. To avoid an edge case where the deadline is extended indenitely, we dene T^ = T + M^, an upper bound on the deadline rd c (see Denition3). The challenge-response protocol adjustment is summarized in the algorithm below.

$$ T_{r d} $$

$$ P e=(b(T_{c}),b(T_{c}+1),...,b(T_{r d})) $$

$$ T_{r d} $$

$$ \hat{T}{r d}=T{c}+\hat{M} $$

$$ T_{c}\leftarrow i n i t $$

$$ T_{r d}\leftarrow i n i t $$

$$ P e=(b(T_{c}),b(T_{c}+1),...,b(T_{r d})) $$

$$ P e^{c}\gets c o n g e s t i o n.v e c t o n(P e) $$

$$ \mathbf{w h i l e}:\mathit{U C P}(\mathit{P e}^{c})=0::\mathrm{}{a n d}:\mathit{T}{r d}<\hat{T}{r d}\ \mathbf{d o} $$

$$ T_{r d}\leftarrow T_{r d}+1 $$

$$ P e=(b(T_{c}),b(T_{c}+1),...,b(T_{r d})) $$

We emphasize that the extension of the deadline is not necessarily carried out at the exact moment of the deadline (since smart contract actions need to be triggered by a transaction to the contract). Instead, a transaction that is submitted afterwards is determined to be either before or after the deadline given any possible extensions that are due. The uncongestion period protocol is specied in advance in the smart contract, and the deadline calculation is triggered either by a late response to the challenge or by the challenger that claims that a response did not arrive in time.

5 Implementation

We provide an implementation of the Sliding Window protocol as an Ethereum smart contract using the EIP 1559 base fee to determine block congestion. EIP 1559 implements a base fee that is adjusted up and down by the protocol according to how congested the network is. The EVM supports fetching the base fee of the highest (current) block. We suggest extending this to fetch the base fee of any block, and to add an opcode that checks whether a block is congested (without such opcodes, it is not possible to fully implement the mechanisms put forward in this paper). This opcode will receive as inputs a block and a maximum base fee (chosen by a user) and will return whether the maximum base fee exceeds the block’s base fee.

In the implementation, we set the sliding window size equal to the initial deadline of the examined period (before being granted any extension).

The fullgithub¹ repository includes the smart contracts, the new opcode, and the tests. In addition, we include the Solidity code of the contracts in AppendixC.

6 Conclusion

In this paper, we tackled a problem that arises when challenge-response protocols face congested periods. When the network experiences congestion, users will often miss the response deadline, which can lead to serious issues including nancial loss. We formalized the problem and proposed a new protocol called the Sliding Window as a solution. Our protocol denes a reliable way to detect congested periods by looking only at the data available on-chain. We then used this to extend the challenge-response deadline when congestion occurs. We studied the security of the protocol for dierent parameters. Our results showed that it is possible to decrease the time settlement (deadline) of challenge-response protocols signicantly, while expanding the security of the protocol to deal with cases of congestion.

For future work, it would be interesting to evaluate and optimize this protocol and its security analysis for more realistic congestion settings|in particular, settings in which congestion is correlated between consecutive blocks|and to provide more experimental analysis of these settings. Is is also of interest to explore whether Ethereum’s proposed base fee can be used as a suciently robust congestion signal.

7 Acknowledgments

Ayelet Lotem and Aviv Zohar are partially supported by grants from the Israel Science Foundation (grants 1504/17 & 1443/21) and by a grant from the HUJI Cyber Security Research Center in conjunction with the Israel National Cyber Bureau.

References

1.Bano, S., Sonnino, A., Al-Bassam, M., Azouvi, S., McCorry, P., Meiklejohn, S., Danezis, G.: SoK: Consensus in the age of blockchains. In: AFT ’19: Proceedings of the 1st ACM Conference on Advances in Financial Technologies. pp. 183{198 (2019) 2.Bitcoin Optech: Child pays for parent (CPFP), https://bitcoinops: org/en/ topics/cpfp

¹ https://github.com/stonecoldpat/slidingwindow

3.Mempool manipulation enabled theft of $8m in MakerDAO collateral on Black Thursday: Report, https://www: coindesk*:* com/tech/2020/07/22/mempoolmanipulation-enabled-theft-of-8m-in-makerdao-collateral-on-blackthursday-report/ 4.Bitcoin wiki: Replace by fee, https://en: bitcoin*:* it/wiki/Replace by fee 5.Buterin, V., Conner, E., Dudley, R., Slipper, M., Norden, I., Bakhta, A.: EIP-1559: Fee market change for ETH 1.0 chain. https://eips. ethereum. org/EIPS/eip-1559 (2019) 6.ConsenSys: The inside story of the CryptoKitties congestion crisis (Feb 2018), https://consensys: net/blog/news/the-inside-story-of-thecryptokitties-congestion-crisis/ 7.Croman, K., Decker, C., Eyal, I., Gencer, A.E., Juels, A., Kosba, A., Miller, A., Saxena, P., Shi, E., Sirer, E.G., et al.: On scaling decentralized blockchains. In: International conference on nancial cryptography and data security. pp. 106{125. Springer (2016) 8.Daian, P., Goldfeder, S., Kell, T., Li, Y., Zhao, X., Bentov, I., Breidenbach, L., Juels, A.: Flash boys 2.0: Frontrunning, transaction reordering, and consensus instability in decentralized exchanges. arXiv preprint arXiv:1904.05234 (2019) 9.Eyal, I., Gencer, A.E., Sirer, E.G., Van Renesse, R.: Bitcoin-NG: A scalable blockchain protocol. In: 13th fUSENIXg symposium on networked systems design and implementation (fNSDIg 16). pp. 45{59 (2016) 10.Felten, E.: Fighting censorship attacks on smart contracts. https: //medium*:* com/offchainlabs/fighting-censorship-attacks-on-smartcontracts-c026a7c0ff02 (2020) 11.Frangella, E.: Crypto Black Thursday: The good, the bad, and the ugly, https://medium: com/aave/crypto-black-thursday-the-good-the-bad-andthe-ugly-7f2acebf2b83, accessed: 2021-08-31 12.Gudgeon, L., Moreno-Sanchez, P., Roos, S., McCorry, P., Gervais, A.: SoK: Layertwo blockchain protocols. In: International Conference on Financial Cryptography and Data Security. pp. 201{226. Springer (2020) 13.Harris, J., Zohar, A.: Flood & loot: A systemic attack on the lightning network. In: AFT ’20: Proceedings of the 2nd ACM Conference on Advances in Financial Technologies. pp. 202{213 (2020) 14.Kelkar, M., Zhang, F., Goldfeder, S., Juels, A.: Order-fairness for byzantine consensus. In: Annual International Cryptology Conference. pp. 451{480. Springer (2020) 15.Kursawe, K.: Wendy, the good little fairness widget: Achieving order fairness for blockchains. In: AFT ’20: Proceedings of the 2nd ACM Conference on Advances in Financial Technologies. pp. 25{36 (2020) 16.Roughgarden, T.: Transaction fee mechanism design for the Ethereum blockchain: An economic analysis of EIP-1559. Tech. rep., Department of Computer Science, Columbia University (2020) 17.Sokolov, K.: Ransomware activity and blockchain congestion. Journal of Financial Economics (2021) 18.Sompolinsky, Y., Lewenberg, Y., Zohar, A.: SPECTRE: A fast and scalable cryptocurrency protocol. IACR Cryptology ePrint Archive, Report 2016/1159 (2016) 19.Sompolinsky, Y., Wyborski, S., Zohar, A.: PHANTOM and GHOSTDAG: A scalable generalization of Nakamoto consensus. IACR Cryptology ePrint Archive, Report 2018/104 (2018)

20.Sompolinsky, Y., Zohar, A.: Secure high-rate transaction processing in bitcoin. In: International Conference on Financial Cryptography and Data Security. pp. 507{527. Springer (2015) 21.Tanana, D.: Avalanche blockchain protocol for distributed computing security. In: 2019 IEEE International Black Sea Conference on Communications and Networking (BlackSeaCom). pp. 1{3. IEEE, New York (2019) 22.Wang, G., Shi, Z.J., Nixon, M., Han, S.: SoK: Sharding on Blockchain. In: AFT ’19: Proceedings of the 1st ACM Conference on Advances in Financial Technologies. pp. 41{61 (2019)

A Proofs

A.1 Proofs of Section3.2

Proof of Proposition1.

Proposition 1. A miner manipulating a block B to make it (1*;1)-congested* R₁ when it is not will lose a potential prot of at least B_B()d. _{1 ( 1 B( 1))}

$$ (\theta_{1},\gamma_{1}) $$

$$ \textstyle\mathcal{B}\cdot\int_{1-(\gamma_{1}-\gamma_{\mathbf{B}}(\theta_{1}))}^{1}\theta_{\mathbf{B}}(\gamma),d\gamma $$

$$ \gamma_{B}(\theta_{1}) $$

$$ \gamma_{1}-\gamma_{B}(\theta_{1}) $$

$$ \ \geq theta{{}_{{1}}} $$

Fig. 4: Cumulative function of the-weight threshold of a block B before and after miner manipulation

Proof. Given a block B which is not (₁;₁)-congested (C_1;1(B) = 0), it is possible to manipulate it into a block B which is (₁;₁)-congested (C_1;1(B) =

1. by replacing some of its transactions with dummy transactions that have fee density₁. In order to maximize its revenue, the adversary will remove the transactions with the lowest fee density. The minimum portion of transactions that the adversary needs to remove is_{1 B}(₁) (by the denition of_B), and by doing so the miner misses the rewards associated with removing these legitimate transactions.

$$ \left(\mathcal {C} _ {\theta_ {1}, \gamma_ {1}} (\mathbf {B}) = 0\right) $$

$$ (\theta_{1},\gamma_{1}) $$

$$ (\mathcal{C}{\theta{\mathfrak{l_{1}}},\gamma_{\mathfrak{l_{1}}}}(\overline{{\mathbf{B}}})= $$

$$ \geq\theta_{1} $$

$$ \gamma_{1}\mathrm{-}\gamma_{\mathbf{B}}(\theta_{1}) $$

$$ \gamma_{\mathbf{B}}) $$

Using the notations from above, we compute a lower bound on the miner’s R1 loss, which can be expressed by U UB_BB₍) d ₍see _B 1 ( 1 B( 1)) Figure4). Note this is only a lower bound since a miner can remove transactions only in their entirety and not parts of them.

$$ \mathcal{U}{\overline{{\mathbf{B}}}},\leq,\mathcal{U}{\mathbf{B}}-\mathcal{B}\cdot,\int_{1-(\gamma_{1}-\gamma_{\mathbf{B}}(\theta_{1}))}^{1}\theta_{\mathbf{B}}(\gamma),d\gamma $$

Proof of Proposition2.

Proposition 2. A miner manipulating a block B to reverse its signal from (₁;₁)-congested to not congested will lose a potential prot of at least B R() _{B 1} (B()₁)d. 1

$$ (\theta_{1},\gamma_{1}) $$

$$ \int_{\gamma_{1}}^{\gamma_{\mathbf{B}}(\theta_{1})}(\theta_{\mathbf{B}}(\gamma)-\theta_{1}),d\gamma $$

$$ \geq\theta_{1} $$

$$ \theta_{1}. $$

Fig. 5: Cumulative function of the-weight threshold of a block B before and after miner manipulation

$$ \theta - $$

Proof. The cost of reverting a block signal to uncongested depends on the state of the mempool. It is likely that transactions with fee density slightly lower than₁will be available in the miner’s mempool allowing him to substitute the original transactions with fee density₁for these and lose the fee dierence. This allows us to give a bottom bound on the loss which can be expressed by R() 1 U UBB (_B()₁) d (see Figure5). B1B

$$ \theta_{1} $$

$$ \geq\theta_{1} $$

$$ \mathcal{U}{\overline{{\mathbf{B}}}}\leq\mathcal{U}{\mathbf{B}}-\mathcal{B}\cdot\int_{\gamma_{1}}^{\gamma_{\mathbf{B}}(\theta_{1})}!\left(\theta_{\mathbf{B}}(\gamma)-\theta_{1}\right)d\gamma $$

A.2 Proof of Section4

Proposition 3. The L Consecutive Blocks protocol is monotonic.

Proof. Given a period Pe₁, uncongested according to the L Consecutive Blocks protocol, which is included in period Pe₂:

$$ P e_{1} $$

$$ {mathrm{P{P e}}_{2}}{} $$

$$ \begin{array}{l} \mathrm {U C P} _ {L} \left(P e _ {1} ^ {c}\right) = 1 \Rightarrow \ \exists 1 \leq i _ {1} \leq | P e _ {1} | - L + 1 s. t. \forall 0 \leq j \leq L - 1: P e _ {1} ^ {c} [ i _ {1} + j ] = 0 \ P e _ {1} \subseteq P e _ {2} \Rightarrow \ \exists 1 \leq k \leq | P e _ {2} | - | P e _ {1} | + 1 s. t. \forall 1 \leq d \leq | P e _ {1} |: P e _ {1} ^ {c} [ d ] = P e _ {2} ^ {c} [ k + d - 1 ] \ \Rightarrow f o r i _ {2} = k + i _ {1} - 1, \forall 0 \leq j \leq L - 1: P e _ {2} ^ {c} [ i _ {2} + j ] = 0 \ \Rightarrow \mathrm {U C P} _ {L} \left(P e _ {2} ^ {c}\right) = 1 \ \end{array} $$

We now evaluate its eciency.

Proof size. In order to provide evidence for the uncongestion of period Pe of size n, it is enough to point to the location of the rst block in a series of L consecutive uncongested blocks, given formally by = minfi 2f1*;:::;n L*+ 1gj8 0 j c L 1 : Pe [i + j] = 0g.

$$ P e $$

$$ n, $$

$$ L-1:P e^{c}[i+j]=0} $$

$$ \pi=\operatorname*{m i n}{i\in{1,...,n-L+1}\mid\forall;0\leq j\leq $$

Refresh Information. Given a congested period Pe, and Pe^ that extends it, in order to determine the congestion level of the extended period UCP (Pe^ c), it L is enough to check only Pe^ n (Pe[: (L 1)]), the period beginning L-1 blocks before Pe ends.

$$ P e, $$

$$ \hat{P}e $$

$$ \mathsf{U C P}_{L}(\hat{P e^{c}}) $$

$$ \hat {P e} \backslash (P e [: - (L - 1) ]) $$

$$ P e $$

B Block Congestion Denition: Examples

In Denition1, we oered to dene the congestion of a block based on the fee densities. Other, less eective, ways in which block congestion could be dened are listed below:

{ By transaction with lowest fee density: A block is-congested if the lowest fee density for a transaction in it is bigger than : min_tx2B(tx). However, a miner could decide to always enter a single transaction with a very low fee density (less than) and easily change a block from congested to not congested; hence this scheme is easily manipulable.

$$ \ \theta{\mathrm{:}}\ \theta{\mathrm{:}}\operatorname*{m m n}_{t x\in\mathbf{B}}\phi(big x)big\geq\theta $$

{ By transaction with highest fee density: A block is-congested if the highest fee density of its transactions is bigger than : max_tx2B(tx). A miner could decide to always enter a single (dummy) transaction with a high fee density (higher than) and easily change a block from not congested to congested; hence this scheme is also easily manipulable.

$$ \operatorname{m a x}_{t x\in\mathbf{B}}\phi(t x)\geq\theta. $$

{ By non-zero-fee transaction occupancy ("block size"): A block is-congested if-fraction of its occupancy with non-zero-fee transactions: Pit is full at _{tx2B: (tx)>0}w(tx) B. A miner could articially add transactions with positive fee density to ll the block at no cost.

$$ \textstyle\sum_{t x\in B:\ phi t t x>0}w(t x),\geq,\gamma\cdot{\mathcal{B}} $$

{ By transaction fees (instead of fee density): A block is (f,)-congested if at least a fraction of it is lled with transactions with fees above some value P f :_{tx2B: (tx)} w⁽tx_{) f}w(tx) B. A miner could prioritize transactions by their size in order to decide the congestion signal, without lowering his prot from the fees (U_B).

$$ (f,\gamma) $$

$$ \gamma $$

$$ f\colon\textstyle\sum_{t x\in\mathbf{B}:\phi(t x)\cdot w(t x)>f}w(t x)\ \geq\ \gamma\cdot\mathcal{B} $$

$$ (\mathcal{U}_{\mathbf{B}}) $$

C Code

contractBlockchainMock f // Simulate block.basefee(). EVM only fetches the current basefee. structBlock f uintbaseFee; g Block[]publicblocks; // Should the caller consider this block congested? functionisCongested(uintblockNumber, uintmaximumBaseFee) publicviewreturns (bool) f if(blocks[blockNumber].baseFee > maximumBaseFee) f returntrue; g returnfalse; g g contractAuctionisSlidingWindow f boolstart =false; uintstartBlock; uintk; uintn; uintgasPriceCeiling; functionstartAuction(uint startBlock, uint k, uint n, uint gasPriceCeiling) public f startBlock = startBlock; k = k; n = n; gasPriceCeiling = gasPriceCeiling; start =true; // Kick-start the auction! g functionfinaliseAuction()publicreturns(bool) f if(isPeriodCongested(startBlock, k, n, gasPriceCeiling)) f returnfalse; g returntrue; g g

A. Lotem et al.

contractSlidingWindowisBlockchainMock f functionisPeriodCongested(uintstartBlock, uintk, uintn, uintmaximumBaseFee) publicviewreturns (bool) f require(n*>=k, ‘N should be greater than or equal to K.’); require(blocks.length>=n, ‘Total should be greater than or equal to N.’); uinttotalCongested = 0; bool[] memoryrecordCongestion = newbool; for(uinti=startBlock; i < startBlock+n; i++) f // Keep a record of this block’s congestion. recordCongestion[i] = isCongested(i, maximumBaseFee); // Sum of congestion (so far). if(recordCongestion[i]) *f* totalCongested = totalCongested + 1; *g* if(totalCongested*>=k) f returntrue; g g // Activate the sliding window. for(uinti=startBlock+n; i<blocks.length; i++) // Remove start of the window. if(recordCongestion[i-n] f* totalCongested = totalCongested-1; g Keep a record of this block’s congestion. recordCongestion[i] = isCongested(i, maximumBaseFee); // Add to the end of the window. if(recordCongestion[i]) f totalCongested = totalCongested + 1; g if(totalCongested*>=k) f returntrue; g // Not congested. returnfalse; g g