"Instant" Collator based finality

[eskimor]

To improve reliability even more than possible with #5544 we could pick up an idea by @bkchr : Collator based "instant" finality.

What does this mean: We could make it so that a block is only considered valid if it contains signatures from 2/3rds of the collators attesting to the transaction ordering in the block. Then, even if the block gets retracted a new block would need to put in transactions in the same order for the block to be considered valid (and thus signed) by other collators again.

This would increase latency slightly, but hardly if we build this on top of transaction streaming transaction streaming as then all collators build the same block concurrently and only need to send approving signatures at the end to "finalize".

The collators will only approve a para block if it honors any pre-determined (by previously built blocks) transaction ordering: All still live transactions are put in the block again in the same order.

Worth mentioning: We don't need a proof. It is enough if collators can agree on the validity off-chain and just sign it off so relay chain validators will reject the block if not enough collators approved.

• Transactions could still theoretically turn out invalid due to received messages: Ideally we would also process the exact same messages as the last time. The collator could tell the parachain runtime via an inherent to stop processing messages at the same point as last time. This is getting nasty though and likely not worth the trouble.
• Obviously clients relying on this collator based finality, operate on a different threat model: They now assume 2/3 honest collators instead of just 1.
• This improves reliability of transactions going through, but at the cost of reduced liveness. To mitigate this, we could make it so that the approving signatures are not required if X number of block production opportunities have been missed.

[bkchr]

Worth mentioning: We don't need a proof. It is enough if collators can agree on the validity off-chain and just sign it off so relay chain validators will reject the block if not enough collators approved.

The relay chain should not care about this. This protocol is parachain only. The collator could include the signature of the other 2/3 at the end of the block to make the runtime accept the ordering.

BTW, this needs to take panicking transactions into account. As we can not recover from a panic, these transactions can not be included in a block. Also transactions may get invalidated by runtime updates. So, there are some edge cases that need to be thought of.

[burdges]

As an aside, there is a fairly large design space of similar ideas, so in part our goals should be a minimal example showing others they can tweak finality entirely within their parachain, and this scheme sounds like the right level of complexity for that.

Actual parachain teams might develop more, like blocks output by DAG schemes. As a more interesting example, if some randomness beacon produces BLS sigantures on slot numbers, like drand now or maybe polkadot in future, then these signatures could mean only in-parachain-availability of ciphertext parablock of transactions encrypted to some future BLS signature, and then actual blocks must contain IBE decryptions of already approved ciphertexts.

[eskimor]

The relay chain should not care about this. This protocol is parachain only. The collator could include the signature of the other 2/3 at the end of the block to make the runtime accept the ordering.

That's what I meant, with relay chain validators I mean PVF execution/proper validation.

Also an even simpler intermediate step would be to just have honest collators preserve order as much as they can and no confirmation by other collators: Just make it a best effort property, any dishonest collator could screw it up, but might still be good enough. If you really want 6s and below latency you are trusting a particular collator already.

On the other hand, if we put in those signatures, we are kind of improving low latency security in general as then a single collator can no longer mess with you.