Generic Transaction Queue logic in runtime

[gavofyork]

The goal of this PR is to work towards a flexible transaction queue that relies only on runtime logic to provide comprehensive dependency and queuing management. In particular, the unified transaction queue integrated into substrate-node should not be aware of the concepts of accounts, signatures, indexes or nonces. Rather an alternative model of tags (a tag is an arbitrary Vec<u8>) is used with transactions requiring some set (possibly empty) of tags before they become valid and providing some other set of tags (though usually just one).

SRML runtime API should expose a function:

• enum TransactionValidity { Valid(u64, Vec<u8>, Vec<u8>), Invalid, Unknown }
• fn validate_transaction(transaction: Vec<u8>) -> TransactionValidity

Returns Valid if the transaction can be statically validated; in this case it returns a pair of tags and a block number; the first is the tags that including this provides, the second is the tags that must have been provided by transactions prior to this, the u64 is the priority used to determine which of a mutually exclusive set of transactions are better to include. The transaction queue should build a dependency graph using the tags in order to ensure transactions are included in blocks in the correct order. Any transactions that do get included in a block should be instantly discarded (and banned) if they result in a panic execution.

Unknown is returned if the transaction might yet become valid in the future. No further information is given and the transaction queue is free to disregard (and even temporarily ban) the transaction in expectation that once it becomes valid it will be rebroadcast.

Invalid is returned if the transaction is strictly malformed or contains data that imply it could never be valid for this chain. The transaction queue should disregard and ban it ASAP; it should also consider a small punishment to the peer that provided it.

Parts:

• Change to the runtime (Generalised Transaction Queue API #741)
• Change to the transaction queue.

[gavofyork]

CC @tomusdrw

[tomusdrw]

Any transactions that do get included in a block should be instantly discarded (and banned) if they result in a panic execution.

This should most likely invalidate the whole tree or move the rest of the chain to future queue (awaiting a transaction with prev-tag)

The transaction queue should build a dependency graph using the tags in order to ensure transactions are included in blocks in the correct order.

Do we consider multiple transactions with the same required tags to be valid? I.e. does including a transaction invalidate the tag (I suppose it should)? Is there any notion of priority (weight) of the transactions? i.e. consider this (A -> B means B requires one of the tags that A provides)

() -> A --> B
      |
      | --> C
            ^
() -> A'----|

To include B we need to include A first, to include C we need to include both A and A'. If B and C use the same tag and we are not allowed to include multiple transactions with the same required tag we need to decide if we want to include B or C, if there is no weighting we will choose arbitrarily depending on the order we push transactions to the block.

We should also be careful to prevent cycles in the graph, although that could possibly be ensured by reviewing the runtime code.

[gavofyork]

agree - cycles are problematic. some some runtimes cycles will be impossible. for others not necessarily, so we might want to a static analyser into the graph to ensure it's acyclic. i don't expect these graphs to be huge since we won't keep an unlimited number of tags around anyway and any tag too deeply nested would be a good candidate for removal if the txq gets too big.

i'll change the API to include the notion of "priority", which should be treated as additive.

we're not allowed to include transactions with the same tag. but two transactions may each be included that require the same tag.

so if you have this (we'll assume A and A' have the same tag):

() -> A --> B
      |
      | --> C
            ^
() -> A'----|
      |
      | --> D

then the decision on whether to include A or A' is:

priority(A) + priority(B) > priority(A') + priority(D)

(technically both sides also have priority(C) added on, but I left it out for brevity)

[tomusdrw]

then the decision on whether to include A or A' is:
priority(A) + priority(B) > priority(A') + priority(D)

Isn't that a bit tricky? I mean, we first include A and only then we include B/D, right? So what if priority(B) actually affects the decision, but B yields a panic? I guess if we don't have payments involved it should be fine, possibly additivity of priorities should be an option.

[gavofyork]

priority is a best-effort thing anyway.