Ethereum network-level transaction spamming attack against honest participants

[lungj]

I only read the text description of the RANDAO protocol, but there appears to be a bug that enables attacking both the random number produced and honest participants.

In the protocol, pledges must be larger than any possible payout in order to be effective. In the case of a lottery such as this one, the sum of the pledge basically needs to exceed the amount of the lottery jackpot. Similarly, there may be other situations where large pledges are required.

In the RANDAO FAQ, this question appears (in relation to the corresponding part of the protocol):

Q: the miners can ignore certain transactions that contain random number they dislike, how to deal with that? A: That's why we need a time window period. A reasonable period should be greater than 6 blocks, we believe that nobody can produce 6 blocks in succession. So if the participant is honest, and he send numbers immediately as long as each time window open, he doesn't need to worry about being excluded.

However, there is another attack that can be executed. Instead of mining six blocks in succession, the attacker merely has to clog up six consecutive blocks: by constantly outbidding an honest participant in terms of gas price and filling the block, the attacker can prevent another participant's revealing transaction from being included. The cost of this attack is (slightly more than) the cost of gas required to fill the blocks. We can see that the average transaction fees per block on the main net at the time of this writing is about 0.6 ether. To fill the block, the malicious user Mal thus has to spend ~0.6 ether to block a transaction for a block. For six blocks, that's ~3.6 ether. For a random number protected with a pledge of 2000 ether, 3.6 ether is a very cheap attack. It's made even cheaper if Mal is also a miner and can mine some of those six blocks and can outright censor the honest participants' transactions on blocks OR include the spam transactions and collect the fees (which is the more surreptitious way of doing it). Mal can thus manipulate the outcome of the random number generation. Furthermore, if the censored participant(s)'s ether is divided amongst the other participants, Mal gets a cut if she is participating -- and can increase her cut by censoring more people. Indeed, Mal can make a profit simply on the RANDAO protocol without even having a stake in the outcome of the random number, even after including the transaction fees!

Lastly, Mal can be malicious in another way: suppose a particular RANDAO contract is only open approved participants. If Alice is one of those approved participants and Mal does not like Alice, Mal can force Alice to forfeit her pledge by spamming the network. This can be done purely out of spite or to make Alice relatively poorer than Mal. (Even if it makes Mal poorer, if Mal and Alice both want a particular Picasso painting more than anyone else and have more money than anyone else cares to bid, Mal might now be able to out-bid Alice on this painting by becoming relatively richer to Alice.)

This attack cannot be patched by putting a maximum gas price on the transaction to make the attack have the same priority for transaction queuing as the honest participant(s). Indeed, this makes the attack cheaper. If Mal manages to reveal block her secret during block 1 of the reveal period, then she can flood the remaining n blocks of the reveal window with non-RANDAO related transactions. If there is a cap, then the attacker knows that other participants' valid revelation transactions have a maximum price and can set her spam transactions to have a gas price of 1 gwei/gas more than this maximum.

The situation improves when Ethereum protocol scaling options are adopted.

[lungj]

I just realized this is a partial duplicate of #17 except that I show that the total pledge amount rises at least linearly with the value of the outcome of the contract and with the number of participants. OTOH, in a lottery-type situation, the value of the lottery increases linearly with the number of participants; this means that the combined rise in value is the square of the number of participants. Meanwhile, the cost to the attacker increases only linearly with number of blocks. If the contract has network effects (value of contract increases with square of participants), we have a cubic.

In any case, this demonstrates that RANDAO costs more to scale than an attacker's benefit to attacking.

Edit: the confiscating-pledge clause described in README.md clause reduces the value of blocking transactions in order to steal ether from other participants. OTOH, the pledge amount quickly spirals out of control if a large number of individuals wish to prove to themselves the randomness of the number by joining the contract under certain uses of this contract.

[wanghs09]

Nice observation. the claim “nobody can produce 6 blocks in succession” is unclear about the probability of occurrence, which is the risk the participants will take.
Besides, to safely reveal the committed random number, the participants need to raise the gas above average, which will be the fee for the random number users.