Sliding Window Challenge Process for Congestion Detection
By Ayelet Lotem, Sarah Azouvi, Patrick McCorry, and Aviv Zohar
Sometimes, you really need to get a transaction published on the blockchain in time. Missing that deadline may cause you to lose some money. One such case is when you’re participating in an auction controlled by a smart contract. If you’re unlucky, that auction deadline may coincide with the latest hyped-up NFT launch, and you may have to compete with others who really need to get transactions out on time.
On March 12th, 2020 (Crypto Black Thursday) the price of Ethereum dropped by more than 50% in less than 24 hours triggering many MakerDAO auctions to liquidate collateral. Tokens were purchased at almost no cost because bidders couldn’t send transactions with a reasonable fee on time. This has, allegedly, been leveraged by one user to gain $8.3 million worth of ETH.
If there’s a lot of blockchain congestion, wouldn’t it be great if you could just get an extension on that deadline? The auctioneer would love to grant you an extension —congestion hurts his bottom line too. The problem is, that we want to give extensions only if congestion occurs.
In our most recent paper (see VIDEO), published in ‘Financial Cryptography and Data Security 2022’, we describe a mechanism that allows contracts to detect transaction congestion and provide such extensions.
Another example where deadlines play an important role is in payment channel networks (PCNs) like Lightning, where you have a fixed period of time to react in case another node in the network tries to steal your funds. To avoid losing funds, the implementation of payment channels tends to have long deadlines (of about 1 week) to avoid users having to pay significant fees to quickly resolve the dispute. This means that you have to wait longer when closing channels even if there is no congestion.
Our approach
Our goal is to eventually design a congestion “opcode” that will allow smart contracts to utilize congestion signals to extend deadlines. The main issue with blockchain congestion detection is that you’re only able to use information from the blockchain (so that all nodes can agree that congestion occurred). It’s impossible to use other sources of information that nodes don’t fully agree about like mempool data.
We start by defining what it means for a single block to be congested. If you think about it, then really, it is always possible to get a transaction accepted into a block if you’re willing to pay a high-enough fee. So the congestion signal is really just a price signal. Therefore, if most transactions are high-fee, we consider this block congested.
If we can say that a single block was congested, then we can then extend the notion to determine that multiple blocks are congested within a time period. Now, given a binary series of the blocks’ congestion signals we want to decide whether a recent time period is “uncongested enough” so that transactions have a fair chance to get in.
The most intuitive way to implement a protocol is to simply say, well if at least M blocks are not congested, then we should consider that good enough. In most execution environments, that would probably work as a good solution. However, the world of blockchains is an adversarial environment where bad actors may try to manipulate the congestion signal. We need to ensure that our solution is robust.
Here are the properties that we would like our definition to meet:
- Efficiency — we want to be able to obtain compact proofs for the lack of congestion with relative ease.
- Consistency — if a period is considered uncongested, we want any period that contains it to also be considered uncongested. This way, once we decided a period is uncongested and does not deserve a deadline extension we won’t be forced to change our minds.
- Robustness — we want to make sure that the congestion signal is reliable and cannot be manipulated easily by miners. We consider two types of attacks that we would like to defend against:
- A congestion attack in which the attacker tries to reverse the congestion signal of the period from uncongested to congested. This attack causes an unnecessary delay in the response deadline.
- An uncongestion attack, in which the attacker tries to reverse the congestion signal of the period from congested to uncongested. This might cause participants to miss the chance to respond on time.
The Sliding Window Protocol
We suggest the ‘Sliding Window (K-out-of-N)’ protocol which maintains all the properties mentioned above. The protocol defines uncongestion by the existence of a window of size N (of consecutive blocks) with K uncongested blocks among them.
This protocol is resilient to both of the attacks described above. We evaluated the attacks over Ethereum using short response deadlines as low as 3 hours, considering an attacker with 33% of the network's computational power, and found that attackers succeed with only negligible probability.
In the following table, we present upper bounds on the probabilities for an attacker to succeed in each of the attacks, using different parameters for N and K. The wider the sliding window is, the greater the protection we get from manipulating miners. Since the values of N and K are configurable, we can choose to increase the level of security from one attack at the expense of the other.
Implementation
At last, we provide an implementation in Solidity of the Sliding Window protocol as an Ethereum smart contract using the EIP 1559 base fee as a measure of 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 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. 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.
For more see the full paper, published in ‘Financial Cryptography and Data Security 2022’.
A video version of the paper is available on our YouTube channel.
