Disallow transactions with note cycles in batches

[PhilippGackstatter]

Following from 0xMiden/node#1112, we should probably disallow transactions with note cycles at the batch level.

Consider a batch with:

• TX A: Inputs [Y] -> Outputs [X]
• TX B: Inputs [X] -> Outputs [Y]

or a batch with:

• TX C: Inputs [X] -> Outputs [Y]
• TX D: Inputs [Y] -> Outputs [Z]
• TX E: Inputs [Z] -> Outputs [X]

In both cases, there is a cycle of dependencies due to the notes these transactions produce, e.g. A depends on B and B depends on A. Similarly, C depends on E and E depends on C (with an indirection through D).

We should be able to detect this as suggested here, by erasing notes on the fly. Specifically, the current approach is to build the full input and output note set based on all transaction's inputs and outputs first, then erase notes.

We have to change this to iterate transactions one by one and add the transaction's notes to the respective input and output note set. If a consumed note exists in the output note set, erase it; if a created note exists in the input note set, erase it. If at the end these sets have a non-empty intersection, there is a cycle.

One thing to think through is the best way to do the implementation, i.e. whether we use two dedicated BTreeSets to implement this (so we could conveniently use BTreeSet::intersection) and once we got past note erasure, collect these sets into vectors. This would change the order of input and output notes of the batch (since it would order notes by their NoteId) compared to what we have currently (which follows the ordering of the input notes of the underlying transactions). I recall this being convenient in tests, but that can be adapted. Is there otherwise a reason why we'd want to retain that underlying order?

cc @Mirko-von-Leipzig, @bobbinth

[bobbinth]

I actually think this could be a cool feature - i.e., we have transactions which are "atomic" - i.e., either both make it into a block or non makes it in. We don't have to support this at the node level (at least in the near future) but I don't know if we should disallow this at the protocol level.

So, I guess the main question is whether disallowing transaction cycles within batches let's us simplify something significantly.

Separately, I do think that cycles across batches are probably less useful - and so, there could be a good argument to make sure there are no batch cycles within a block.