[Lightning-dev] An Idea to Improve Connectivity of the Graph

Christian Decker decker.christian at gmail.com
Wed Apr 11 20:15:41 UTC 2018


ZmnSCPxj via Lightning-dev <lightning-dev at lists.linuxfoundation.org>
writes:

> Good morning Alejandro,
>
> I was about to ask Christian this myself.
>
> There is another technique:
>
> Use a sequence of `nSequence`d transactions off-chain.  For example,
> to get an 2-bit counter, you would have:
>
> funding -> kickoff -> bit1 -> bit0
>
> Only funding is onchain.  kickoff, bit1, and bit0 transactions are all
> kept offchain.  We start a unilateral close by broadcasting kickoff,
> then wait for bit1 to become valid and broadcast then, then wait for
> bit0 to become valid and broadcast then.

Yes, this is exactly the way we would create a shared output that has an
indefinite lifetime, but would still be protected against the
counterparty becoming unresponsive. I usually call the `kickoff`
transaction the `trigger` transaction because it triggers the countdown
on the CSV encumbered scripts.

> There are two versions of the bit1 and bit0 transactions.  Each bit
> position, you have a high `nSequence` to represent the binary 0, and a
> low `nSequence` value to represent the binary 1.
>
> Then to increment your counter, you replace bit0.  If it has a high
> `nSequence` you replace it with a new bit0 transaction with the low
> `nSequence` (equivalent to flipping the bit).  If it is already the
> low `nSequence` (i.e. logically it is value 1) then we "carry" it by
> replacing the next higher bit, then replacing the current bit with the
> high `nSequence` (equivalent to propagating the carry and flipping the
> bit).  Thus it is equivalent to binary incrementation.
>
> It is safe to re-use the high `nSequence` on a lower bit if some
> higher bit in the offchain transactions uses the low `nSequence`
> value, since that higher bit dominates over the rest of the chain.
>
> This is basically just the "invalidation tree" concept brought to its
> logical conclusion.  We could use trinary or quaternary or more, but
> that limits the `nSequence` we can use (we do not want to use too
> large a high `nSequence` value as that increases wait times), so there
> is some balancing involved in the various parameters (number of
> digits, radix of counter).

Well, what you just described is a branching factor of 2, while in the
paper we usually used a branching factor of 48 (1 hour deltas, for 2
days total wait time). Unlike the Locktime based timeouts the deltas
along a branch in the tree are now cumulative so you'd probably want to
make sure that they sum up to a reasonable max timeout, i.e., all sum of
timeouts along a branch <= 2 days total.

> To get a 32-bit counter for a maximum of 4,294,967,296 updates
> transactions in sequence, we need 33 transactions in sequence kept
> off-chain.  When one party disappears, we are forced to feed the 33
> transactions one-by-one into the blockchain.  If we use 4 blocks for
> high `nSequence` (bit 0) and 0 blocks for low `nSequence` (bit 1) then
> at worst case lockup time for unilateral close is 128 blocks.

That is mostly due to the selection of 1 bit sequence diffs, the
branching gives us a huge increase in the number of invalidations. The
paper has the example of branching factor of 46, and a tree depth of 11,
which results in 1.48e11 updates.

> Note that all transactions are kept offchain: we never re-point a
> refund transaction as you describe in your "(b)".  Thus we only waste
> blockchain space if we are forced into a unilateral close.  Normal
> operation, we simply keep all transactions offchain and only touch the
> chain on unilateral or bilateral close.
>
> The big drawback is the large number of transactions in sequence in a
> unilateral close.  In a bilateral close we collapse all transactions
> into a single bilateral refund.  I suppose it is hopeful to consider
> that unilateral closes should be very rare.
>
> So, Christian, it still seems that techniques that reduce total wait
> times in a unilateral close have the drawback of increasing the number
> of transactions in sequence in a unilateral close.  It still seems
> Poon-Dryja, is superior in that total wait time is easily
> user-selectable and unilateral closes only have two transactions in
> sequence.  For low number of updates, we can consider having a tiny
> "counter" (possibly a quaternary counter) that itself terminates in
> multiple Poon-Dryja channels, which I believe is what the
> Burchert-Decker-Wattenhofer channel factories do.

Yes, I agree that DMCs have a much wider on-chain footprint for the
non-cooperative close scenario. I do prefer DMC style updates for some
use-cases though, since they do not have the issue with more than 2
parties, they have no toxic material that can result in your funds being
grabbed, just because you were out of date, and because it means that we
can totally forget old HTLCs since there is no way for them to ever
become relevant again (in LN, if an old commitment gets confirmed we
need to scramble to recover the preimage so the rightful owner can claim
it).

I guess it's another tool in our toolbox :-)

Cheers,
Christian


More information about the Lightning-dev mailing list