If you find a transaction which invalidates the block, you have to back all that out. (It is a little simpler than what I stated though).
Sure, but isn't that just saying that 'validation can fail'? What is special about the order in that regard?
@deadalnix: Yes. But I still have to
do the ordering when creating a block and reordering (replacing it with the what-txn-builds-on-what-other-txn, let's call it "txnbuild" partial order) when validating a block.
Whereas currently, I have to only obey the "txnbuild" partial order for those transactions that I want to include in my block and don't have to do any reordering when receiving it. If we would follow
@Richy_T's idea of not even allowing interdependent txn in a single block, I wouldn't even have to care about the "txnbuild" partial order other than rejecting that don't fit it, it would simply become part of the txn validity rules. (I don't think that's a good path forward for other reasons, though)
This txnbuild partial order is also highly correlated to reception order of transactions and thus violations are unlikely (though not impossible) when building blocks.
You essentially argue that for network transmission, it makes it easier to sync two sorted sets and that this dwarfs all other concerns. And, yes, again, I can see your point. But also, again, I like to caution here: Are you sure we explored potential paths sufficiently yet?
And the other angle is that for building and validation, you can do with an O(n) instead of an O(n log n) step (modulo details of the current implementations, such as having uint256s in trees instead of hashtables).