Multi-hop virtual channels

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 | Destination means x is 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 that action is applied against a given network state state and results in network state nextState.

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.

  1. Put a source of a at A . Find a flow from A to B in the ledger graph. Topologically sort the (directed) edges in the flow.
  2. For each edge e in the flow edges put (in order) (e.end, e.flow) into an outcome called flowOutcome. Construct a joint channel J with outcome flowOutcome.
  3. For each edge e from A, construct a guarantor G_e with guarantee [A, e.end]
  4. For each other edge e in the flow, construct a guarantor G_e with 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_0 has a guarantee [H_1, A]
  • then H_1 gets everything deposited against G_0 if claim(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.

Hi Andrew,
still interested in a discussion?
I worked on the exact same problems the last days before discovering your post here.

My conclusion was that it is not safe in the sense that not everybody has an unbeatable strategy ( I will explain this below; possibly, I misunderstood who can claim the guarantees, so my conclusion might be wrong).
First: given all Guarantees are finally claimed, I also conclude that its safe (<->your result).

However following the nitro paper (i did not yet have a look at the code), you need to annotate who has an unbeatable strategy (who can e.g. claim G).
I use a notation even more close to Toms paper in the following and for simplicity only 2 Hubs, which can easily be generalized to i hubs:

J(A:a, H1:x, H2:x, B:b)_A,H1,H2,B
[L0->(G0:x)]_A,H1
[L1->(G1:x)]_H1,H2
[L2->(G2:x)]_H2,B
[G0->(J|A,H1)]_A,H1
[G1->(J|H2,H1)]_H1,H2
[G2->(J|B,H2)]_H2,B

My line of thought first, followed by the exact notation below.
The questions are: can e.g. H1 claim G2? Is ist safe for H1 to depend on G2?

In my understanding H1 can not claim G2 (directly) as it is a guarantor channel set-up among the participants H2,B.
What is not clear to me: can H1 have a strategy (using his influence on J), such that G2 is claimed?

Even if so, at any point in time H2,B could decide to de-fund G2 - without any influence of H1 on this decision! -> a situation in which H1 would depend on G2 to be claimed is not safe for H1 (as he can not prevent de-fundung of G2).

Explicit example (for simplicity I drop out Lx and Gx, once Gx was ‘claimed’ which means the respective value has been brought via J to the recipient):
We start in the above state.

H2 claims G1
(means apply a strategy to bring the fund from L1 to G1 and via J to the respective recipient).
H2 can do this as he is participant in L1 and G1.
The result is H2 receives x:

J(A:a, H1:x, H2:0, B:b)_A,H1,H2,B
[L0->(G0:x)]_A,H1
[L2->(G2:x)]_H2,B
[G0->(J|A,H1)]_A,H1
[G2->(J|B,H2)]_H2,B
sloppily noted: H2:x

Does H2 playing a strategy to do so also mean that all other G are claimed? If not:
H2 and B could, at any point in time refuse to claim G2 / de-fund G2.

But first let H1 do what he can:
H1 (in my understanding) can claim G0 which leads to:
J(A:0, H1:a, H2:0, B:b)_A,H1,H2,B
[L2->(G2:x)]_H2,B
[G2->(J|B,H2)]_H2,B
sloppily noted: H2:x, A:a, H1:b

H1 now depends on G2 to be claimed by H2 or B, however, B could collaborate with H2 and defund G2
J(A:0, H1:a, H2:0, B:b)_A,H1,H2,B
[L2->(H2:a, B:b]_H2,B
[G2->(J|B,H2)]_H2,B
sloppily noted: H2:x, A:a, H1:b

which provides H1’s a to H2.

So my basic possible misunderstanding lies in the effect of H2 playing his strategy at first place…
I would be grateful for any hint / discussion!

Alex

P.S.:
I, once again, had a careful read of the Nitro paper.
The above problem seems to be an instance of the guarantee ordering problem (discussed in 6.3 around Fig.23).

To me, the sections about finalization and redistribution state that only a participant of a channel can finalize it.
This interpretation is also supported by the text after eq. (23) in the paper, where in that example, A on the one hand has the power to finalize L, G and J, but NOT L’, G’.
In the ‘one hub’ example this does not hurt; however, as soon as there are more than 1 hub the guarantee ordering problem occurs.

To use Tom’s terms, H1 at best has an enabled outcome (which is a possible outcome, neither guaranteed to be the actual outcome, nor enforcable by H1).

Claims
As far as I see the claim operator does NOT allow an non-participant to call it, in the case above
C(G2,J,x) can not be called by H1 - right?
This can not be as H1 can not finalize L2 and G2, so how should he call that claim?
Even if so, he would never be sure to have the possibility to do so, because he is no participant and therefore it is not guaranteed that is is always informed about the state of G2 and has the means to call the claim (prove the state)…

Solution? Not really:
The only solution i can come up with would be to have H_i-1 also being a participant of Li and Gi, in our example above resulting in:

[L2->(G2:x)]_H2,B,*H1*
[G2->(J|B,H2)]_H2,B,*H1*

This however would require consensus with H1 in the subsequent steps when closing the channels (section 6.5.2, eq. (40 ff) to switch the ledger channels to absorb the outcome of J.
This is not what we want! (as the B and H2 depend on the willingness of H1)

If H1 would be only added to G2, H2 and B however could, at any time, de-fund G2, which would render the possibility to claim it useless for H2.

So after all these considerations, the only ‘secure’ solution is to hierarchically stack ‘usual’ virtual channels, in the case above:

  1. establish a virtual channel V1=A-H2 via H1
  2. establish a virtual channel between A and B based on V1 and L2

What do you think?

@alexp I think you’re right that the original approach doesn’t work. I think it’s possible to construct an argument that any approach which involves a single joint channel and a chain of two party guarantees can’t work in the general case.

Take a virtually funded setup between n parties, with a single joint channel J, that virtually funds a channel \chi between A and B with 10 coins. We restrict to the case where the setup is linear i.e. each party shares an on-chain deposit of size 10 with two other parties, apart from A and B, who share a deposit with one other party.

Consider the case where we need to payout to the channel \chi between A and B on-chain i.e. J has finalized with an outcome with \chi : 10, A: 0, B: 0 (and some other entries, whose format we won’t specify, to keep the argument general).

How does this situation play out? Here are a few constraints:

  1. In order to be able to have the property that funds aren’t locked indefinitely, any party needs to be able to trigger the first payout.
  2. Parties can only trigger payouts from channels that they’re part of.
  3. No funds should be paid out to the parties until \chi is fully funded.
  4. Once \chi is fully funded, there is a unique solution to where the coins in each link should be sent.

Here are two possibilities for the first payout, along with the unique resolution in the case of that payout:

Notice that, under the rules of Nitro, the initial payout would leave the J entry on-chain in exactly the same state. That’s a problem, because if 3 or 4 wanted to act next to withdraw their funds, the correct payout can’t be determined by looking at J. For example, in the case where channel 5-6 payed out to \chi, if the money from 4-5 goes to 4, then 5 no-longer has the ability to ensure they’re payed out.

So it looks like there’s no setup that would make the current approach work, as there simply isn’t enough information stored on-chain. It seems like for this to work, the rule for updating J after a guarantee payout would have to in some way depend on which guarantee paid out, or otherwise the above scenario will always be a problem.

It also shows how this is possible with the standard “triangle” geometry - in that case more J s go to chain, so more information ends up being stored about who has paid out where.

1 Like

@tom, thank you for your comprehensive answer, fully agreed!

Regarding rules for updating J; I’m currently undecided about if it would be good to extend the ‘basic constructs’ (e.g. like you did by splitting destinations and priority order by introducing the guarantee channel concept) or not and use the standard approach.

The latter requires are more complex scheme/sequence to be followed; on the other hand, in more dense networks, the chance to depend on longer chains over several intermediaries in order to find a route from A to B gets small. And for the seldom cases the overhead is tolerable, especially because the characteristic that ‘channels update independently’ can be kept intact.

I think it’s definitely worth trying to see if there’s a nice way to do it. While the guarantee channel construction does the job, it feels a bit ad-hoc. It’s possible that we’re currently missing a nicer construction that would also cover the case above.

Yes, it would be nice, but I’m a bit skeptical if it would be securely possible.
Perun also does it in a comparable way, see e.g. [1], Fig.1 and related text, as well as the finally extended version [2], Fig.2 and Fig.5 (right hand side) and related text.

[1]
@InProceedings{Dziembowski2018,
author = {Dziembowski, Stefan and Faust, Sebastian and Host{'a}kov{'a}, Kristina},
title = {General state channel networks},
booktitle = {Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security},
year = {2018},
pages = {949–966},
file = {:Dziembowski2018 - General State Channel Networks.pdf:PDF},
groups = {stateChannels},
}

[2]
@InProceedings{Dziembowski2019,
author = {Dziembowski, Stefan and Eckey, Lisa and Faust, Sebastian and Hesse, Julia and Host{'a}kov{'a}, Kristina},
title = {Multi-party virtual state channels},
booktitle = {Annual International Conference on the Theory and Applications of Cryptographic Techniques},
year = {2019},
pages = {625–656},
organization = {Springer},
groups = {stateChannels},
}