Directed acyclic graph of causal dependencies (partial packet ordering)

[cwgoes]

Split off from https://github.com/cosmos/ics/issues/126.

Desiderata

• Packets can specify a set of ancestor identifiers which must be received prior to receiving the packet
• Super-set of:
  • Ordered channels: one ancestor per packet that is the direct predecessor
  • Unordered channels: no ancestors
• Ancestor identifiers can refer to packets sent on other channels from other chains / modules

Implementation

• Ancestor identifier represented as hash of (source connection || source channel || packet sequence || packet data)
• Accumulator in receiving IBC handler adds identifiers of all received packets (and stores forever?) - shared across all channels and connections
• Proof of inclusion of ancestor packets required to receive
• Proof of non-inclusion of particular identifier for timeouts (a bit different than proof of receive sequence number currently), can batch timeouts safely if a packet upon which other packets depended times out

Questions

• How to deal with timeouts? Should they still close channels? (could be an option)
• Does the accumulator have to store received packet identifiers forever?

[cwgoes]

Do we care about the "multi-chain execute or rollback" case or is that out of scope?

Chain A executes state transition 1, chain B executes state transition 2, either:

• Chain C executes state transition 3, which is dependent on 1 and 2, or
• Chain C does not execute state transition 3, chain A and chain B rollback 1 & 2

Right now this would need to be done at the application layer, since A and B would have independent channels to C.

With acyclic ordering, this would be possible if a packet receive on C were dependent on a send on A and a send on B, and the timeout of that packet could rollback both A & B - I think it breaks the channel abstraction though, so perhaps not worth it for now.

Alternatively we could implement atomic co-dependencies:

• A executes 1, sends packet x to C which depends on y
• B executes 2, sends packet y to C which depends on x
• C executes x and y atomically or executes neither
• Timeouts of x or y work to rollback on A or B

What about that? Not too complex, and I think it does the trick...

[cwgoes]

Note that validity predicates can be used across connections so new connections are not needed.

[cwgoes]

Decided not to put this in IBC v1.

Partial cross-chain ordering is a very interesting research topic and should be planned for IBC v2!

[ethanfrey]

Very cool idea here. And I definitely agree to keep this as a 2.0 feature.

Let's get the basic ordered/unordered channels implemented, and deployed and then have some real use cases where this will be a useful optimizations.

I :heart: DAG, vector clocks, and CRDTs... it would be awesome to enable some advance distributed system techniques on top of IBC.

[colin-axner]

Interchain Accounts would benefit greatly from this (it would order based on account sequences). See discussion

I think this would be a great feature to add to TAO v1.1.0