use of priority for exits mapping can create collisions

[johannbarbie]

the priority variable in startExit function is prone to collisions. hence, its use in a mapping can lead to takeover of exit slots.

here a unit test that demos the problem:

https://github.com/johannbarbie/plasma/blob/test/weekOldBlockExit/test/RootChain2.js

[johannbarbie]

i'd submit a similar fix like here: https://github.com/voltairelabs/plasma/pull/20 but i'm horrible with python :)

[smartcontracts]

Yep, problem is here:

https://github.com/omisego/plasma-mvp/blob/207fdac2e6d384a53748b1102e0480cd33f0e2e8/plasma/root_chain/contracts/RootChain/RootChain.sol#L139-L141

Explanation for those reading - exit tx priority is determined by the formula (1000000000 + txindex * 10000 + oindex) * blknum, where blknum is the greater of the number of the block in which the tx was included or the number of the oldest Plasma block less than 7 days old.

The test case provided by @johannbarbie demonstrates a collision where both txs were included in blocks > 7 days old with the same txindex and oindex in their respective blocks, so their priority is the same.

I think the solution of using exitId as an identifier for the exit tx makes sense, it's a little less intuitive to make priority the ID anyway, and we don't really care if priority has collisions. This is better than using priority for the ID because exitId is easy to calculate but priority requires a user remember what the week-old block was at the time of their exiting.

The only "serious" change that needs to be made (thanks to @johannbarbie for this) is to insert (something like) (priority << 128) | exitId into the priority queue instead of just the priority. This has the interesting effect of not creating a collision in the priority queue, so an older transaction will always be processed before a newer one, but we're still bound to that 7 day time period.

We'll also have to change:

https://github.com/omisego/plasma-mvp/blob/207fdac2e6d384a53748b1102e0480cd33f0e2e8/plasma/root_chain/contracts/RootChain/RootChain.sol#L177

to:

exit memory currentExit = exits[uint128(exitsQueue.getMin())];

in order to retrieve the most significant 128 bits (aka the exitId).

Changes are solid, make sense, necessary. @DavidKnott?

[smartcontracts]

Edit: As an update to this comment, any exits made after 7 days should already assume that their funds are lost because their exit priority will be less than the attacker's. This grieving attack still exists, but it's not really that important if the attacker can just steal funds anyway.

I'd like to add an update to the above comment because I think it actually fails to address the problem with how we're handling priority. The solution proposed in this issue is actually no different than uncapped priority after a certain point because it's taking the age of the output into account.

The actual reason why priority needs to be capped to a specific value can be illustrated by the following grieving example:

1. Alice creates many small outputs very early in the history of the chain, but never spends them.
2. The operator withholds, and the users on the chain begin to exit.
3. Alice waits > 7 days so that weekOldBlock is equal to the very last available Plasma block.
4. Alice's old exits will be placed before any newer exits. Alice can make one exit every two weeks and effectively stop anyone else from ever exiting.

This is only a problem because our current implementation makes priority unique.

[smartcontracts]

Even the priority blknum * 1000000000 + txindex * 10000 + oindex where blknum is the last child block suffers from this issue if you can manage to get lots of outputs with a low txindex, although this is less easily exploitable.

[boolafish]

We have similar issue before and we chose to use an second layer array for collision. So for each exits[priority] would be an array rather than an object, and we will clear all objects in with same priority at once. @bun919tw should know detail implementation better than me

[smartcontracts]

@boolafish that works as long as you can assert that all exits of the same priority can be finalized at the same time. I'd love to see how you're actually implementing it because I might be wrong about certain aspects of this.

[smartcontracts]

Now that I think about it, all valid exits must be submitted within 7 days or they might as well be thrown away. I think the above solution is fine for that.

[bun919tw]

Hi all, I submitted a PR #71 to solve this issue. :)

[smartcontracts]

@johannbarbie Thanks for this issue, fixed in #72