Skip to content

Instantly share code, notes, and snippets.

@antiochp antiochp/elder_channels_4.md Secret
Last active Feb 3, 2020

Embed
What would you like to do?
Efficient (NSKR) relative locks, excess revelation and transaction folding

Model the initial channel state as a single multisig output.

outstate_0

Alice and Bob collaborate to fund the channel by spending individual outputs to this multisig channel output.

Model each subsequent channel state as a single multisig output.

outstate_1, outstate_2, ..., outstate_n

Naively model a state transition as a transaction spending one multisig output to the next multisig output. Notation here for the kernel excess commitment is xnG for state n (omitting 0H and associated signature). Note: We do not actually require a full transaction here as discussed later.

[instate_0] -> [outstate_1], x1G

For each channel state there is an associated "close" transaction, spending the channel output to a new "close" multisig output.

[instate_1] -> [outclose_1], xclose_1G

For each "close" channel state there is an associated "settle" transaction, spending the "close" multisig output to two individual outputs owned by Alice and Bob respectively.

[inclose_1] -> [outsettle_A, outsettle_B], xsettle_1G

To close the channel at any given state we can simply aggregate all state transitions together with the appropriate close transaction.

[instate_0] -> [outstate_1], x1G
[instate_1] -> [outstate_2], x2G
[instate_2] -> [outclose_2], xclose_2G
=> [instate_0] -> [outclose_2], [x1G, x2G, xclose_2G]

Observation 1: Intermediate state outputs are always cut-through and never need to appear on-chain. The rangeproof is not required. The aggregated "close" tx spends the initial state output to the final "close" output and includes a transaction kernel for each intermediate state transition. We do not need to build a full transaction for each state transition. We just need the transaction kernel with excess commitment xnG and associated signature.

Problem 1: This obviously does not scale as we need to include a transaction kernel for every state transition in the resulting aggregate close transaction. Here n state transitions would result in n+1 transaction kernels in the aggregate transaction.

Problem 2: It is possible to "close" an old invalid channel state and immediately "settle", distributing the funds out incorrectly to Alice and Bob. The current state may be 60/40 but closing and settling an old invalid state may distribute funds 70/30, for example. So we need a way to "revoke" an old invalid closed state.

We will return to (1) later. To solve (2) we need the combination of a "revoke" transaction and a delay between "close" and "settle" to provide an opportunity for "revoke" to occur.

Revoke Transaction

For each "close" state there is a corresponding "revoke" transaction that spends the "close" multisig output forward to the next channel state multisig output.

[inclose_1] -> [outstate_2], xrevoke_1G

This can be aggregated along with subsequent state transitions to revoke and (re)close the channel at the most recent state.

[inclose_1] -> [outstate_2], xrevoke_1G
[instate_2] -> [outstate_3], x3G
[instate_3] -> [outclose_3], xclose_3G
=> [inclose_1] -> [outclose_3], [xrevoke_1G, x3G, xclose_3G]

Note: The most recent channel state does not yet have a "revoke" transaction. Each state transition involves building a "revoke" transaction for the previous state.

We can introduce the necessary delay between "close" and "settle" by leveraging a "No Such Kernel Recently" (NSKR) relative lock.

Relative lockheight via NSKR Lock

We can force the "settle" transaction to wait for a certain number of blocks after the associated "close" transaction while allowing the "revoke" transaction to be valid immediately. In this way any previous, old invalid state can be immediately revoked before it can be settled.

[inclose_1] -> [outsettle_A, outsettle_B], xsettle_1(close_1, 1440)G

Note: The "settle" transaction kernel has an NSKR lock relative to the "close" kernel excess commitment. The example here is for a relative lockheight of 1440 blocks. The "settle" transaction is not valid within 1440 blocks of the previous "close" transaction and cannot be settled earlier than this. Once 1440 blocks have elapsed the lock will expire and the "settle" transaction will become valid.

Eliminate Previous Kernels by Revealing Excess

Let us now return to the problem (1), the multitude of kernels. We want to avoid requiring a kernel for each individual state transition. On each state transition, let us reveal the excess of the previous state transition. We can compensate for the sum of the state transition excess values by adjusting the kernel offset. This is "transaction folding" as described elsewhere.

Here an excess value is represented as x and a kernel excess commitment as xG. We can sum multiple excess values and adjust the kernel offset to compensate for this.

[instate_0] -> [outstate_1], x1
[instate_1] -> [outstate_2], x2
[instate_2] -> [outstate_3], x3G
[instate_3] -> [outclose_3], xclose_3G
=> [instate_0] -> [outclose_3], [x3G, xclose_3G], (x1 + x2)

The aggregate transaction for any number of intermediate state transitions now contains only two kernels for the final state transition and the associated close transaction. All previous state transitions collapse into a single excess value.

The same approach can be used if we "revoke" and "close" an old invalid state.

[inclose_1] -> [outstate_2], xrevoke_1G
[instate_2] -> [outstate_3], x3
[instate_3] -> [outstate_4], x4
[instate_4] -> [outstate_5], x5G
[instate_5] -> [outclose_5], xclose_5G
=> [inclose_1] -> [outclose_5], [xrevoke_1G, x5G, xclose_5G], (x3 + x4)

Here the "revoke and close" aggregate transaction contains three kernels (revoke, final state, close) and all intermediate state transitions are represented with a single excess value.

Problem 3: Revealing the excess for a state transition allows a previous state transition to be trivially reversed.

It is possible for Alice to "close" an old invalid state and then immediately "revoke and close" to another old invalid state. Alice can continue to do this repreatedly, potentially preventing Bob from closing to the latest state, effectively locking fund up in the channel.

Note: The "close" and "revoke" transactions are full transactions. The excess for these are never revealed and these cannot be reversed without explicitly revoking a previous close. The excess is only ever revealed for previous intermediate state transitions.

What we want is a way to prevent Alice from revoking if Alice closes. If only Bob could revoke after Alice closes then Alice could not lock funds up in this way. Bob would be free to respond, closing to the latest state.

Possible solution: [need to think this through fully]: "Attribution" via endpoint specific close and revoke transactions, with an NSKR relative lock between "close_A" and "revoke_A", delaying Alice from revoking, while still allowing Bob to immediately revoke.

If Alice cannot revoke for 1440 blocks while Bob can revoke immediately then I think we can solve this problem. After "close_A", Bob can "revoke_B" immediately, either party can "settle" after 1440 blocks, or Alice can eventually "revoke_A" after 1440 blocks.

@tromp

This comment has been minimized.

Copy link

tromp commented Jan 31, 2020

I don't see the need for separate states S0 -> S1 -> S2 -> ...
They can all be joined into a single S0?!
To deal with problem 3, you do need to duplicate all close states.
So there will be A1, A2, A3, ... for Alice closing, and B1, B2, B3, ... for Bob closing.
Then there are revoke txs from all but the last Ai -> S0 which are signed by Alice but not yet by Bob.
And revoke txs from all but the last Bi -> S0 signed by Bob but not yet by Alice.

@antiochp

This comment has been minimized.

Copy link
Owner Author

antiochp commented Feb 1, 2020

I don't see the need for separate states S0 -> S1 -> S2 -> ...

Yeah. Woke up this morning and realized that was what felt wrong here... If the excess is revealed then there is effectively no separate state each time.
So we are back to something closer to V3 I think.

@tromp

This comment has been minimized.

Copy link

tromp commented Feb 1, 2020

This is different from V3 which had only one close output for Alice closing, and one for Bob closing.
Which relied on each settle tx referencing a specific close tx.
The use of sequences of close outputs Ai/Bi allows for the simpler NSKR settling txs.

@antiochp

This comment has been minimized.

Copy link
Owner Author

antiochp commented Feb 1, 2020

This is different from V3 which had only one close output for Alice closing, and one for Bob closing.

Yes agreed. The more limited NSKR locks (only looking back 1 week) means we cannot safely reuse the close outputs and we need new ones for each channel state. So we're basically trading a more efficient lock structure (no need to retain full kernel history) for an increase in the data required to handle channel close txs.

@tromp

This comment has been minimized.

Copy link

tromp commented Feb 1, 2020

The largest communication expense in each channel update is the 4 rangeproofs, 2 for the new A and B close outputs, and 2 for the new payouts. The former can perhaps be avoided, if we allow a rangeproof to be a a pair of (references to) a rangeproof and a kernel, which suffice for 1-input 1-output transactions.

@antiochp

This comment has been minimized.

Copy link
Owner Author

antiochp commented Feb 3, 2020

In the middle of writing up v5 (which is basically v3 but with a new output/rangeproof for each state update)

I think A and B can actually share the same close outputs for each new state. They have different versions of the close tx, but they can differ by kernel excess commitment (and kernel offset) while keeping the same outputs.
A and B then have different versions of the settle tx, which themselves differ only in terms of their NSKR lock configuration (settleA is locked against closeA and settleB is locked against closeB).
So Alice cannot settle immediately after closing, but must wait 1440 blocks.

Interesting side-effect is Bob could immediately settle after Alice closes. In the same way as Bob could immediately revoke if Alice attempts to close an old invalid state.

Scenario 1:
Alice closes current state
Bob settles current state immediately (or Alice settles after NSKR lock expires)

Scenario 2:
Alice closes old invalid state
Bob revokes and (re)closes current state immediately (Alice can only revoke after NSKR lock expires)
Bob settles current state after NSKR lock expires (or Alice can settle current state immediately)


Two versions of each close transaction, each with a different kernel excess commitment (for attribution) but same outputs.
Two versions of each revoke transaction, each locked against the associated close kernel (A must wait to revoke if A closes).
Two versions of each settle transaction, each locked against the associated close kernel (A must wait to settle if A closes).

But in each case the transactions only differ in their kernels. Inputs and outputs are shared/reused (per state update).
Differentiate between channel states with different outputs (state1 vs. state2)
Differentiate between endpoints with different kernels (Alice vs. Bob)
Combinations of the above to close then settle (or close, revoke, (re)close, settle)

@tromp

This comment has been minimized.

Copy link

tromp commented Feb 3, 2020

You can't have multiple NSKR references leading to the same output.
If both closeA1 and closeA2 transactions lead to the same CloseA output,
with corresponding settle transactions settleA1 and settleA2,
then closeA1 could be cut-through with settleA2 and vice-versa,
since the NSKR constraints are trivially satisfied.

@antiochp

This comment has been minimized.

Copy link
Owner Author

antiochp commented Feb 3, 2020

I agree that closeA1 and closeA2 cannot lead to the same output (not what I was suggesting).
You need a unique output per channel state update.
But I think closeA1 and closeB1 can lead to the same output, reducing the size of the per round requirements.

@tromp

This comment has been minimized.

Copy link

tromp commented Feb 3, 2020

Sorry for mis-interpreting:-(

Yes, that seems to all work. Nice optimization.

Note that a cooperative close to the latest state can be done by either party sending the signature on their settle tx to the other,
so that the close and settle can be cut-through, requiring only one on-chain transaction.
If that party shares not only the signature, but also their private excess on the close, then the two kernels can be folded into one.

@antiochp

This comment has been minimized.

Copy link
Owner Author

antiochp commented Feb 3, 2020

then the two kernels can be folded into one.

Oh that's nice as well. So they have already basically built the majority of the tx necessary for a cooperative close (by reusing the non-cooperative stuff built for each state transition).

@tromp

This comment has been minimized.

Copy link

tromp commented Feb 3, 2020

Except that such a cooperative close leaks some privacy in exposing the use of NSKR, a strong hint of channel use.
In the interest of making channel use look indistinguishable from other one, the parties may still want to construct a lock-less settlement.

@antiochp

This comment has been minimized.

Copy link
Owner Author

antiochp commented Feb 3, 2020

And in eltoo/lightning terminology we have "toxic" data (each party needs to maintain endpoint specific txs etc.) but there is no "penalty" if this is forgotten or misused. The worst thing that can happen is the channel ends up getting closed - nobody is at risk of being penalized for misuse by losing all their funds. So the "toxic" data is necessary but not as serious a problem as it is in lightning.

(Just posting this here to remind me to include this in the writeup.)

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