BEP Idea: Better handling of consecutive transactions

[ttmc]

This idea was originally proposed by @TimDaub in issue bigchaindb/bigchaindb#1789

@TimDaub wrote:

FYI: I'm treating this as bug, as it's a blocker for us on another project.

To simplify our lives, we did not consider in-block ordering of dependent transactions.
We also do not allow two dependent transactions to be in the backlog at the same time (e.g. HTTP API blocks from submitting a TRANSFER where the CREATE doesn't exist yet).

This yields a frustrating problem that we have to patch in several libraries right now, a loop that waits for a transaction to be confirmed, see here or here (loop at bottom of section).

Instead, I'd like to propose fixing this issue with the following changes:

1. Any schema-valid transaction can pass from the HTTP API into the backlog
2. Either: The backlog's transactions are topologically ordered, such that when a new transaction gets inserted it gets automatically sorted into place
3. Or: The backlog is not topologically ordered, such that when a new transaction gets inserted it gets appended to the list of transactions to be processed
4. Upon block creation the node then:
5. Either: takes the first 1000 transactions (already topologically sorted) from the backlog and puts them into a block. Caution: This will yield unfair results, e.g. when one transaction DAG is very active
6. or: takes the first 1000 transactions and sorts them topologically and puts them into a blog

In both cases, this would mean that two (or more) dependent transactions can be in one block.
Bitcoin has this, I remember there was a BIP (can't find it right now). This link might be helpful.

FYI: Topological sorting isn't too difficult (meaning that this task shouldn't be too difficult). There are many ready-made algorithms (I use this one for JS).