I realized yesterday that it’s pretty simple to construct multi-hop virtual channels in a “flat” scheme, with one virtually-funded ledger between every participant, and one guarantor channel for each connection.
I think @tom already knew about this, but it was much less appealing with ConsensusApp.sol, since updates in a turn-based joint channel seemed to require a lot more coordination. With the null app, everyone can sign off on updates in J in any order. (1)
Notation
I wrote this a bit hastily, so I hope it’s understandable.
- (x) means there’s a remark down below.
This notation is loosely based on the nitro paper:
-
x -> Outcome | Destinationmeansxis deposited either against a channel with that outcome, or against a destination -
J: x -> OorD means the outcome or destination explicitly belongs to channel
J -
action << state = nextState(from our still-unpublished force-move-verification blog post) indicates thatactionis applied against a given network statestateand results in network statenextState.
EG.
deposit(C2, b) << a -> C1 = (a -> C1, b -> C2)
transferAll(J) << J: 3 -> [(A, 1), (B, 3)]
Given
J: [(A, a), (H1: x), (H2, x), ..., (Hn, x), (B, b)]
x = a + b
G_0: x -> { target: J, guarantee: [A, H_1] }
G_i: x -> { target: J, guarantee: [H_{i+1}, H_i] } i = 1,...,n-1
G_n: x -> { target: J, guarantee: [B, H_n] }
Claim
J is safely, virtually funded.
Proof (sketch)
Case n=1
This is the current virtual funding protocol, except (B, b) is placed last in J, making the allocation in J more (less?) symmetric. You can check by hand that it’s safe.
Case n>1
Applying any claim yields the same type of joint channel, with fewer intermediaries. In other words, calling Claim(G_i) is a way to remove yourself from the funding situation.
Claim(G_0) << [(A, a), (B, b), (H1: x), (H2, x), ..., (H_n, x)]
= (a -> A, b -> H1, [(H1: a), (H2, x), ..., (H_{i+1}, x), ..., (H_n, x), (B, b)])
Ie. A gets a, H1 gets b and is still owed a. Apply induction with A <- H1, n <- n-1
Let i \in {1,...,n-1}.
Claim(G_i) << [(A, a), (H1: x), (H2, x), ..., (H_i, x), (H_{i+1}, x), ..., (H_n, x), (B, b)]
= (x -> H_{i+1}, [(A, a), (H1: x), (H2, x), ..., (H_i, x), ..., (H_n, x), (B, b)])
Straightforward induction (n <- n-1)
Claim(G_n) << [(A, a), (H1: x), (H2, x), ..., (H_n, x), (B, b)]
= (b -> B, a -> H_n, [(A, a), (H1: x), (H2, x), ..., (H_{i+1}, x), ..., (H_n, b)])
Ie. B gets b, H_n gets a and is still owed b. Apply induction with B <- H_n, n <- n-1
Generalization (2)
Construct the “ledger graph” by connecting two peers if they have a directly-funded ledger channel. Label that edge with the minimum of their capacity in that channel. (I’m not sure if this labeling is optimal.)
Suppose some hubs don’t have sufficient capital on-chain for whatever reason. We can use the following construction to virtually fund through any sufficiently-funded, connected subgraph of the ledger graph.
- Put a source of
aatA. Find a flow from A to B in the ledger graph. Topologically sort the (directed) edges in the flow. - For each edge
ein the flow edges put (in order)(e.end, e.flow)into an outcome calledflowOutcome. Construct a joint channelJwith outcomeflowOutcome. - For each edge
efromA, construct a guarantorG_ewith guarantee[A, e.end] - For each other edge
ein the flow, construct a guarantorG_ewith guarantee[e.end, e.start]
I think the above proof also works for this construction. I don’t fully understand the special case needed in 3 (3), but there’s some (arbitrary) asymmetry introduced by constructing the flow from A to B, so perhaps it’s not so surprising that there’s some asymmetry in the construction.
Remarks
(1) I think you can write some bespoke validTransition rules that’s “in between” the null app and the ConsensusApp so that A & B can collaborate to update the outcome of J without the support of others, but it would require changing the definition of when a state is supported, which seems dangerous.
(2) It’s incredibly unlikely that this general case would ever be used in practice: we tend to believe that arbitrary funding networks converge towards low-diameters, since the above construction requires (n+1)*x funds to be locked up while J is being funded. Thus, it’s mostly a theoretical interest. (The neat thing is that claim(G_i) can be used by H_i or H_{i+1} to unilaterally extricate themselves from the funding scheme. They could, as a courtesy, “sign out” of J at the same time.)
(3) From what I can understand, A needs priority in G_0 because
- if
G_0has a guarantee[H_1, A] - then
H_1gets everything deposited againstG_0ifclaim(G_0)is recorded first
On reflection, with the current implementation of claimAll, A will eventually get a if all claims are called, and all guarantors are sufficiently funded. However, A does not control whether the other claims are made; they don’t even know if the other guarantees are covered. Thus, it’s not safe for A.
In the base case, once the outcome of J only has two participants, the last remaining guarantee is “backwards”. But at that point, it doesn’t matter.
