Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Directed acyclic graph of causal dependencies (partial packet ordering) #131

Open
cwgoes opened this issue Jun 25, 2019 · 3 comments

Comments

@cwgoes
Copy link
Collaborator

commented Jun 25, 2019

Split off from #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

This comment has been minimized.

Copy link
Collaborator Author

commented Jun 25, 2019

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 cwgoes self-assigned this Jun 25, 2019

@cwgoes cwgoes added this to the Specification Clarification milestone Jun 25, 2019

@cwgoes

This comment has been minimized.

Copy link
Collaborator Author

commented Jun 25, 2019

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

@cwgoes cwgoes added the ibc-v2 label Jun 25, 2019

@cwgoes

This comment has been minimized.

Copy link
Collaborator Author

commented Jun 25, 2019

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!

@cwgoes cwgoes removed this from the Specification Clarification milestone Jun 25, 2019

@cwgoes cwgoes removed their assignment Jun 25, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
1 participant
You can’t perform that action at this time.