The same order can be matched multiple times

[gnosis]

The same order can be matched multiple times

[fleupold]

One thing to keep in mind is that changing a storage value from 0 to non-zero costs 20k gas whereas overriding a non-zero storage value with another value costs only 5k gas (https://ethereum.github.io/yellowpaper/paper.pdf page 25).

Therefore, if we want to allow individual nonce invalidation, I think packing 256 bits into one word is crucial even if we only match a single order per batch.

[josojo]

Good catch!

Initially, I was running

for (uint256 i = 0; i < orders.length; i++) {
            require(
                nonces[orders[i].owner] < orders[i].nonce,
                "nonce already used"
            );
            nonces[orders[i].owner] = orders[i].nonce;
        }

that would not have these issues. But then, this is also far from optimal, as we some times want to include orders from the same user with different nonces, but we don't want to submit them in the order of the nonces.

Not sure, what to do here. Maybe we have to require users to have order nonces and limitprices aligned.

[fedgiac]

Another issue I noticed while working on this: If the users creates two orders with nonce 1 and 2 respectively but only the order with nonce 2 is executed, the order with nonce 1 is invalidated.

[fedgiac]

The solution I propose is to transform this:

    mapping(address => uint8) public nonces;

into this [0]:

    mapping(address => mapping(uint8 => bool)) public invalidatedOrders;

Every user-created order is linked to a nonce, like now.
When an order with nonce i is settled, the contract checks that invalidatedOrders[user][i] == false, else it fails. Then invalidatedOrders[user][i] is set to true.

The cost for the solver is 1 memory write per order, similar to the current mechanism.
This has the following benefits:

• easy to cancel any orders trustlessly (solves #20).
• easy to perform checks on whether any order is valid.
• the solution settlment cost of this solution is the same as the current one (assuming one order per user; on the other hand, the current implementation is broken for more than one order per user).
• assuming the user trusts the transaction creation service, the user never needs to recreate orders because previous orders were invalidated.
• there is the option of "soft invalidating" an unexecuted order by having the user create a different order with the same nonce. If the replacement order is ever executed, then the previous order is also safely cancelled.

The only disadvantage I can think of when compared to the current solution is that the cost of cancelling orders for a user is linear with the number of orders.

[0] I wrote uint8 and bool for clarity, but for gas efficiency we'd probably be better off with uint256 for both. If we think it's common for users to have multiple orders matched in the same batch, we could pack many consecutive bools in the same storage slot so that the price of settling up to 256 orders for the same users is at most 2 storage writes, compared to the naïve solution with 256 storage writes. Not sure this is a common enough occurrence to warrant the extra complexity.

[nlordell]

The current idea is to have a mapping from order hash to executed amount. Something like:

    /// @dev Bitmap to invalid the orders
    mapping(bytes32 => uint256) public executedAmounts;

Computing the key:

bytes32 orderKey = keccak(abi.encode(order.digest, order.validTo, order.owner));

Verifying the order has not been used:

uint256 previouslyExecutedAmount = executedAmounts[orderKey];
if (order.partiallyFillable) {
    uint256 orderTotalAmount = order.kind == OrderKind.SELL ? order.sellAmount : order.buyAmount;
    require(previouslyExecutedAmount.add(executedAmount) <= orderTotalAmount);
} else {
    require(previouslyExecutedAmount == 0);
}

And then do something like this to signal the order has been used:

executedAmounts[orderKey] = executedAmount;

Or, when doing a gas refund:

executedAmounts[orderKey] = 0;

[nlordell]

@fleupold also suggested using the nonce to compute the order key instead of the order digest. See the original discussion here #142 (comment)

[nlordell]

Closed by #213