Currently, cancelling an order (and thus voiding the current auction) costs some gas and is thus something that doesn't make sense to do at scale.
However, if by simply signing an off-chain message any participant in the auction can invalidate their order I'm worried this will happen much more frequently.

This, plus the fact that we cannot fully prevent the race condition as you describe make this solution in my opinion inferior to simply not including a replacement order in the auction if the original order has been traded already.

To implement your suggestion we could add a new column to the orders table like replaced_by that holds a single uid. Then when indexing trade events for orders we could recursively walk the list of replaced_by orders and cancel them. That seems not too complicated and should be safe to do since replacing orders happens atomically. The only case where this is not sufficient is if there is an open order that is older than a replacement order that got settled (i.e. some order is open in the earlier part of the linked list of replacements). But because replacements happen in a single DB transaction this can not happen. So at least in the mostly centralized case we have at the moment that solution seems sufficient to avoid double spending of replacement orders.
To catch the case where solvers try to use a previously cancelled order as a JIT order we would still have to check the cancellation state of the JIT orders before picking a winner. Discarding a solution because they used an existing cow swap order that was not part of the auction as a JIT order (cancelled or not) does seem reasonable to me since this is not really intended IMO.

I think this scheme would also work for partially executed cancelled orders. Although there is an argument to be made that the user might need to be informed that the remaining unfilled amount will not be filled anymore because of this scheme.
WDYT?

For the recursive case I think we should ask the frontend to send us a list of all order uids which should be mutually exclusive (for this order to make it into the batch).

This way wo don't have weird edge cases with expired orders but only include an order if none of the "replaced" orders are either still part of the auction or have a trade.

Thanks @MartinquaXD for putting this together. I also did a writeup explaining the issue, and the potential mitigation that in our opinion would be good enough: https://www.notion.so/cownation/Canceling-Replace-Orders-Edge-Case-5f1d0d38e3f541e7b454f8e7faa7fee1?pvs=4

Basically, agree with most of the comments above:

• Discarding a solution because it was canceled AFTER the competition started, I don't think is a good option. The only exception we could potentially do as a good to have, is to discard if the only order in the batch is canceled or replaced
• Discarding a solution because it was canceled BEFORE the competition started is reasonable in my opinion. In the future could be part of the slashable behaviour (if we can't guarantee it with coolocation)
• We are happy to provide as Felix says a list of mutually exclusive order. For example If we cancel A with B and B with C, we will send:
  • A = {appData ={}, ...}
  • B = {appData ={metadata: {replacedOreders: [A] }}, ...}
  • C = {appData ={metadata: {replacedOreders: [A, B]}}, ...}

This issue has been marked as stale because it has been inactive a while. Please update this issue or it will be automatically closed.

No need to fix this now, but let's not close it Mr. Stale bot

You need to remove the stale label on the issue in that case...

This issue has been marked as stale because it has been inactive a while. Please update this issue or it will be automatically closed.