Investigate (and/or confirm) the feasibility of countering an exit queue spam attack

[pdobacz]

Following discussions with @achiurizo @pik694:

The attack (grieving) vector is that the attacker produces multiple UTXOs on the child chain and later uses them to open a huge amount of standard exits, in an attempt to clog the exit queue.

The counter-measure here is that the operator, who is doing processExits, takes extra care to effectively unclog the exit queue.

As the malicious exits are becoming mature (can be processed), the operator would wait till:

• there is >N mature exits in the queue or
• the top of the queue is mature for >T

and only then call processExits with a large batch N of exits to process. The reason for this is to only pay the marginal cost of processing an exit, and save on the constant cost of intrinsic gas (which startExit can't do)

The questions to investigate are:

1. how much more expensive it is to attack than to counter, i.e. for every $1 spent on attacking, how much does the operator need to pay to just unclog (considering the exit queue is already clogged, so the push/pop operations are getting expensive)
2. is the counter-measure enough (that is, is it enough for the operator to not be too eager in unclogging, so that the unclogging is cost effective (process many at one tx))

[boolafish]

1. Assuming our fee is using some percentage of the ERC20 gas, eg. 1/10.
2. An average ERC20 seems to be using around 50k gas, an OMG tx example: here. So with the previous 1/10 assumption, the fee would be charging around the cost to cover 5k of gas. However, since the payment tx can have 4 inputs and outputs, one can generate 4 UTXOs at once if optimizing the attack.
3. startSE cost 350k gas
4. processExits costs 140k gas (per output)

So the cost to start an attack for an output is mostly on the cost of startSE which is 350k. Luckily, the cost to processExits is around half of the price to startSE. So it cost more for the attacker than to the operator to clean up the queue. As an operator, it is kind of okay to claim it safe to operate as the cost of attack is higher than the cost of cleaning up.

BUT, for an user that does not want to trust operator, with the assumption of block gas limit 10,000,000 (current ETH block gas limit is around 9,700,000, for convenience, round it up), the cost to spam the block for an week (assuming 20 Gwei gas price) is around 10000000 * 20 * ((60/15) * 60 * 24 * 7) * (10**-9) = 8064 ether. (blockGasLimit * gasPrice * numberOfBlocksWithinAWeek * GweiToEther)

With current price of $165, it would be $1,330,560

[pdobacz]

startSE cost 350k gas

worth noting that luckily, this is "(per output)" too. At first I thought, "ouch, 140k*4>350k"

processExits costs 140k gas (per output)

@boolafish is this the marginal processExit cost per output, assuming that multiple outputs are processed in one go? The advantage of 140k over 350k is quite slim

[boolafish]

is this the marginal processExit cost per output, assuming that multiple outputs are processed in one go?

Yes, I am assuming this is per output. Or per exit at one processExits call. Well... I get the data from the gas report of CI and our tests are mostly simple so just one exit usually.

[pdobacz]

Hm, I think we should investigate this issue taking the cost-effective processExit calling routine (so trying to avoid processExit for a single exit). Otherwise, for every $1 spent on attacking the operator seems to need $0.40 to counter it.

If that was the case, I'd advocate adding a process_exit_reimbursement mechanism, which would essentially aim at repaying the processExit's msg.sender with some eth, stashed away from startExit's msg.sender's input (alongside the refundable bond).