Discussion:
eltoo: A Simplified update Mechanism for Lightning and Off-Chain Contracts
(too old to reply)
Christian Decker via bitcoin-dev
2018-04-30 15:41:38 UTC
Permalink
Raw Message
(cross-posting to bitcoin-dev since this serves as motivation behind the
sighash_noinput proposal)
TL;DR: we announce a new, simple, update mechanism for off-chain protocols,
see the announcement [1] and the paper [2] :-)
A little over a year ago, the three Lightning Network implementation
teams joined forces to work on a common specification for the protocol
stack. Now that both that specification and our three implementations
are becoming stable and usable, it is time to look forward: to further
improve the protocol, to add new features, to simplify, and to fix
downsides.

One of the core innovations that enabled Lightning in the first place was an
off-chain update mechanism to renegotiate a new state and ensure that the old
state can not be settled on-chain. Today, we're excited to release our latest
research paper on a new, simplified, update mechanism for layer 2 protocols,
called eltoo.

eltoo is a drop-in replacement for the penalty based invalidation
mechanism that is used today in the Lightning specification. It is
similar in many ways to the sequence number mechanism that was already
present in the original Bitcoin implementation. But, while sequence
numbers were unenforceable on the blockchain, eltoo is enforceable by
overriding subsequent states on-chain.

Unlike the current mechanism used in Lightning so far, it is not penalty
based, i.e., publishing an old state does not result in the faulty node
to automatically lose funds, and is most similar to the duplex
micropayment channels construction. It is a symmetric scheme, i.e., all
participants share an identical set of transactions, and it ensures that the
last agreed upon state is settled on-chain, with similar tradeoffs as
today's Lightning (timelock vs. online requirement).

eltoo addresses some of the issues we encountered while speficying and
implementing the Lightning Network. For example outsourcing becomes very
simple since old states becoming public can't hurt us anymore. We
completely remove the need to estimate fees ahead of time. The
construction allows us to attach fees when settling, and even allows for
fees to be bumped using CPFP or RBF.

Beyond Lightning, eltoo can be used as a generic update mechanism for an
off-chain contract, for a larger number of participants. This was not
possible in the current update mechanism since reactions to a
misbehaving participant needed to be tailore to that participant. This
enables other protocols such as the channel factories, and in
combination with Schnorr signatures allows for very large off-chain
contracts with minimal on-chain footprint.

Before we can implement eltoo, we need a minor change to Bitcoin: the
introduction of the SIGHASH_NOINPUT flag for signatures. This was first
discussed a few months ago in the context of watchtowers to help secure
Lightning channels, but was not formally proposed. A formal proposal may
now be found in the eltoo paper.

We invite the community to consider our proposal and to participate in
its discussion. We hope to arrive at a consensus for the usage of
SIGHASH_NOINPUT, so that it can be accepted and included in a future
soft fork of Bitcoin Script. Doing so will put us on the road to a more
reliable and simpler Lightning Network, incorporating a new update
mechanism that can also be used for many other applications.

The full official announcement can be found at [1] and the paper with the full
details can be found at [2].

Looking forward to the communities feedback,
Christian

[1] https://blockstream.com/2018/04/30/eltoo-next-lightning.html
[2] https://blockstream.com/eltoo.pdf
Jim Posen via bitcoin-dev
2018-04-30 23:00:55 UTC
Permalink
Raw Message
This construction is pretty neat and seems to solve a lot of problems. I
find the use of CLTV with past timestamps to provide ordering in particular
to be quite clever.

If my understanding is correct though, this construction would
significantly increase the safe CLTV delta requirements because HTLCs
cannot be timed out immediately on the settlement transaction. Consider a
case where node B receives an HTLC from A and forwards to C. If the HTLC
offered to C times out and C does not fail the HTLC off-chain, Lightning
currently guarantees that the CLTV delta is sufficient that I may close the
channel to C on-chain and claim the timed-out HTLC before my upstream HTLC
to A times out. If the CLTV delta is too small, I may fail the upstream
HTLC as soon as it times out, and then C may still claim the downstream
HTLC with the preimage on-chain. With eltoo, when B closes the downstream
channel on-chain, it must wait the CSV timeout on the update transaction
before locking in the timed-out HTLC. This effectively means the CLTV delta
has to be greater than the CSV timeout, plus some extra (whereas it is
currently safe to make it significantly shorter). Is that true or am I
missing something?

On Mon, Apr 30, 2018 at 8:41 AM, Christian Decker via bitcoin-dev <
Post by Christian Decker via bitcoin-dev
(cross-posting to bitcoin-dev since this serves as motivation behind the
sighash_noinput proposal)
TL;DR: we announce a new, simple, update mechanism for off-chain
protocols,
see the announcement [1] and the paper [2] :-)
A little over a year ago, the three Lightning Network implementation
teams joined forces to work on a common specification for the protocol
stack. Now that both that specification and our three implementations
are becoming stable and usable, it is time to look forward: to further
improve the protocol, to add new features, to simplify, and to fix
downsides.
One of the core innovations that enabled Lightning in the first place was an
off-chain update mechanism to renegotiate a new state and ensure that the old
state can not be settled on-chain. Today, we're excited to release our latest
research paper on a new, simplified, update mechanism for layer 2 protocols,
called eltoo.
eltoo is a drop-in replacement for the penalty based invalidation
mechanism that is used today in the Lightning specification. It is
similar in many ways to the sequence number mechanism that was already
present in the original Bitcoin implementation. But, while sequence
numbers were unenforceable on the blockchain, eltoo is enforceable by
overriding subsequent states on-chain.
Unlike the current mechanism used in Lightning so far, it is not penalty
based, i.e., publishing an old state does not result in the faulty node
to automatically lose funds, and is most similar to the duplex
micropayment channels construction. It is a symmetric scheme, i.e., all
participants share an identical set of transactions, and it ensures that the
last agreed upon state is settled on-chain, with similar tradeoffs as
today's Lightning (timelock vs. online requirement).
eltoo addresses some of the issues we encountered while speficying and
implementing the Lightning Network. For example outsourcing becomes very
simple since old states becoming public can't hurt us anymore. We
completely remove the need to estimate fees ahead of time. The
construction allows us to attach fees when settling, and even allows for
fees to be bumped using CPFP or RBF.
Beyond Lightning, eltoo can be used as a generic update mechanism for an
off-chain contract, for a larger number of participants. This was not
possible in the current update mechanism since reactions to a
misbehaving participant needed to be tailore to that participant. This
enables other protocols such as the channel factories, and in
combination with Schnorr signatures allows for very large off-chain
contracts with minimal on-chain footprint.
Before we can implement eltoo, we need a minor change to Bitcoin: the
introduction of the SIGHASH_NOINPUT flag for signatures. This was first
discussed a few months ago in the context of watchtowers to help secure
Lightning channels, but was not formally proposed. A formal proposal may
now be found in the eltoo paper.
We invite the community to consider our proposal and to participate in
its discussion. We hope to arrive at a consensus for the usage of
SIGHASH_NOINPUT, so that it can be accepted and included in a future
soft fork of Bitcoin Script. Doing so will put us on the road to a more
reliable and simpler Lightning Network, incorporating a new update
mechanism that can also be used for many other applications.
The full official announcement can be found at [1] and the paper with the full
details can be found at [2].
Looking forward to the communities feedback,
Christian
[1] https://blockstream.com/2018/04/30/eltoo-next-lightning.html
[2] https://blockstream.com/eltoo.pdf
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
ZmnSCPxj via bitcoin-dev
2018-05-01 05:01:52 UTC
Permalink
Raw Message
Good morning Jim,
If my understanding is correct though, this construction would significantly increase the safe CLTV delta requirements because HTLCs cannot be timed out immediately on the settlement transaction. Consider a case where node B receives an HTLC from A and forwards to C. If the HTLC offered to C times out and C does not fail the HTLC off-chain, Lightning currently guarantees that the CLTV delta is sufficient that I may close the channel to C on-chain and claim the timed-out HTLC before my upstream HTLC to A times out. If the CLTV delta is too small, I may fail the upstream HTLC as soon as it times out, and then C may still claim the downstream HTLC with the preimage on-chain. With eltoo, when B closes the downstream channel on-chain, it must wait the CSV timeout on the update transaction before locking in the timed-out HTLC. This effectively means the CLTV delta has to be greater than the CSV timeout, plus some extra (whereas it is currently safe to make it significantly shorter). Is that true or am I missing something?
I believe this is quite true; indeed only the LN-penalty/Poon-Dryja channels do not have this drawback, as Decker-Wattenhofer invalidation trees also have the same drawback that the CSV and CLTV add up.

However the worst-case invalidation tree total CSV timeouts under Decker-Wattenhofer can grow quite massive; it seems the new eltoo Decker-Russell-Osuntokun CSV timeouts can be shorter.

Regards,
ZmnSCPxj
Christian Decker via bitcoin-dev
2018-05-01 11:36:32 UTC
Permalink
Raw Message
Post by Jim Posen via bitcoin-dev
If my understanding is correct though, this construction would
significantly increase the safe CLTV delta requirements because HTLCs
cannot be timed out immediately on the settlement transaction. Consider a
case where node B receives an HTLC from A and forwards to C. If the HTLC
offered to C times out and C does not fail the HTLC off-chain, Lightning
currently guarantees that the CLTV delta is sufficient that I may close the
channel to C on-chain and claim the timed-out HTLC before my upstream HTLC
to A times out. If the CLTV delta is too small, I may fail the upstream
HTLC as soon as it times out, and then C may still claim the downstream
HTLC with the preimage on-chain. With eltoo, when B closes the downstream
channel on-chain, it must wait the CSV timeout on the update transaction
before locking in the timed-out HTLC. This effectively means the CLTV delta
has to be greater than the CSV timeout, plus some extra (whereas it is
currently safe to make it significantly shorter). Is that true or am I
missing something?
That's a good point Jim. We need to make sure that the CLTVs are far
enough in the future for the CSV timeout to expire and to grab any
preimage downstream and insert it upstream. Overall this results in an
offset of all the CLTVs to (less than) the maximum CSV timeout along the
path. This would be a fixed offset for each channel and can be announced
using the gossip protocol, so senders can take it into consideration
when computing the routes. Notice that this is not really the CLTV
delta, which would accumulate along the path, but an offset on which the
CLTV deltas build on.

In today's network we have many nodes that have a CLTV delta of 144
blocks, which quickly results in HTLC funds unavailable for several days
depending on the route length, so I don't think that adding a fixed
offset is much worse. Once we have watch-towers we can reduce both the
offset as well as the CLTV deltas. Since eltoo makes watch-towers less
expensive, given the reduced storage costs, I'd argue that it's a net
positive for the Lightning network (but then again I'm biased) :-)
Jim Posen via bitcoin-dev
2018-05-01 15:50:27 UTC
Permalink
Raw Message
Can you explain why a fixed offset along the whole circuit is enough to
ensure safely as opposed to an increased delta at each hop?
Post by Christian Decker via bitcoin-dev
Post by Jim Posen via bitcoin-dev
If my understanding is correct though, this construction would
significantly increase the safe CLTV delta requirements because HTLCs
cannot be timed out immediately on the settlement transaction. Consider a
case where node B receives an HTLC from A and forwards to C. If the HTLC
offered to C times out and C does not fail the HTLC off-chain, Lightning
currently guarantees that the CLTV delta is sufficient that I may close
the
Post by Jim Posen via bitcoin-dev
channel to C on-chain and claim the timed-out HTLC before my upstream
HTLC
Post by Jim Posen via bitcoin-dev
to A times out. If the CLTV delta is too small, I may fail the upstream
HTLC as soon as it times out, and then C may still claim the downstream
HTLC with the preimage on-chain. With eltoo, when B closes the downstream
channel on-chain, it must wait the CSV timeout on the update transaction
before locking in the timed-out HTLC. This effectively means the CLTV
delta
Post by Jim Posen via bitcoin-dev
has to be greater than the CSV timeout, plus some extra (whereas it is
currently safe to make it significantly shorter). Is that true or am I
missing something?
That's a good point Jim. We need to make sure that the CLTVs are far
enough in the future for the CSV timeout to expire and to grab any
preimage downstream and insert it upstream. Overall this results in an
offset of all the CLTVs to (less than) the maximum CSV timeout along the
path. This would be a fixed offset for each channel and can be announced
using the gossip protocol, so senders can take it into consideration
when computing the routes. Notice that this is not really the CLTV
delta, which would accumulate along the path, but an offset on which the
CLTV deltas build on.
In today's network we have many nodes that have a CLTV delta of 144
blocks, which quickly results in HTLC funds unavailable for several days
depending on the route length, so I don't think that adding a fixed
offset is much worse. Once we have watch-towers we can reduce both the
offset as well as the CLTV deltas. Since eltoo makes watch-towers less
expensive, given the reduced storage costs, I'd argue that it's a net
positive for the Lightning network (but then again I'm biased) :-)
Christian Decker via bitcoin-dev
2018-05-01 16:29:09 UTC
Permalink
Raw Message
Post by Jim Posen via bitcoin-dev
Can you explain why a fixed offset along the whole circuit is enough to
ensure safely as opposed to an increased delta at each hop?
Sure. Let's assume we have chosen a path `A->B->C->D->E`. For simplicity
let's assume they all have a CLTV delta of 144 blocks (lnd's default
setting). Furthermore let's assume that the CSV timeout for the channels
is also 144.

This means that with the current LN-penalty mechanism you'd have the
following CLTV deltas in the HTLC:

```
A -(576)-> B -(432)-> C -(288)-> D -(144)-> E
```

Meaning that if the current time is approaching the absolute CLTV we
need initiate a channel closure to safely fetch the preimage on-chain,
and be able to turn around and send it on the upstream channel.

This is minimal, but can be arbitrarily higher, if you follow the best
practice of obfuscating the final destination by building a shadow route
behind the real recipient, and add it's CLTV deltas and fees to your
route.

With eltoo you'd need to make sure that you have the settlement
transaction confirmed before your desired CLTV timeout delta begins to
count down. So if the CLTV of the HTLC is `now + CSV timeout + CLTV
delta` you need to initiate a close, whereas Lightning allows you to
wait for time `now + CLTV delta`. Effectively this results in the
following time deltas:

```
A -(576+144)-> B -(432+144)-> C -(288+144)-> D -(144+144)-> E
```

Taking the last hop for example, if we had a CLTV of 1000 with eltoo
we'd need to start closing at height 712, instead of 856 with
LN-penalty. However, this increased delta does not accumulate along the
path, it's just a fixed offset. The longer the route, the smaller the
actual impact of this offset.
Christian Decker via bitcoin-dev
2018-05-01 17:31:28 UTC
Permalink
Raw Message
I'm still not following why this doesn't accumulate.
In the example route, let's look at it from the point of view of C. C sees
the following regardless of whether D or E or someone behind E is the last
B -> HTLC(expire = X + delta) -> C -> HTLC(expire = X) -> D
So D is not required to reveal the preimage before time X, and in the case
of an on-chain settle, C needs to be able to redeem the HTLC output through
the timeout clause before time X + delta. C can't redeem the HTLC (with
sufficient confirmations) at least until the settlement transaction is
confirmed. So it seems to me that regardless of the overall route and the
maximum CSV on it, the delta for the C hop has to be greater than the CSV
delay on the update transaction. And that this must be true at every hop
for the same reason.
That'd be a purely reactionary behavior, i.e., chosing the delta in such
a way that I can both settle the channel and have enough time to react
to turn around and reveal the preimage. So with the assumptions we had
before (CSV = 144 and CLTV delta = 144) you'd have an effective delta of
288 on each hop, yes. That's basically the case in which each channel
reacts serially.

You can trivially parallelize these closures by looking ahead and
noticing that each hop really just cares about its own closure deadline,
i.e., each node just cares to close 288 blocks before the CLTV expires,
not that its delta w.r.t. to the downstream channel is that far in the
future. So all we care about is that once we are due to give the
upstream hop the preimage we've already closed the downstream channel
and can now read the HTLC preimage from that channel.

The CSV timeout isn't part of the delta on each hop, but we need to
implement the deadline computation as:

```
CLTV - CLTV delta - CSV
```

instead of LN-penaltiy's

```
CLTV - CLTV delta
```
Jim Posen via bitcoin-dev
2018-05-02 01:15:10 UTC
Permalink
Raw Message
OK, I see what you are saying. You are effectively suggesting pipelining
the broadcasts of the update transactions. I think this introduces a
problem that a node in the circuit that withholds the preimage for too long
can force all upstream channels to be closed, at only the expense of their
one upstream channel being closed. I believe such an attack could
significantly disrupt the network.

Let me elaborate on the way I'm thinking about this:

So say I'm a routing node with an upstream HTLC with CLTV = X. I need to
ensure that if I learn the preimage, that I have time to broadcast and
confirm an HTLC-success transaction before height X. We'll call this number
of blocks D_success. So if I know the preimage, let's say X - D_success is
the latest height that I can safely broadcast the HTLC-success transaction,
assuming the settlement transaction is already final (ie. the update
transaction is confirmed and the CSV delay has passed). So now I also need
to know when to close the channel with the update transaction. I'll assume
it will take at most D_update blocks from the time I broadcast the update
transaction for it to be mined. So unless the downstream HTLC is already
failed, I should always close the upstream channel at height X - D_success
- CSV_update - D_update.

Now we'll look at the downstream HTLC with CLTV = Y. In order to minimize
the safe delta between the upstream and downstream CLTVs, I will want to
broadcast and confirm an HTLC-timeout transaction as soon after height Y as
possible. So assuming that the downstream settlement transaction is final
at height Y and it takes at most D_timeout blocks for the HTLC timeout
transaction to confirm once it is final assuming no double spends, then Y +
D_timeout is very latest I might learn the payment preimage from the
downstream channel on-chain. So I should be safe as long as X - D_success >
Y + D_timeout. This assumes that the update transaction for the downstream
channel is already mined and the CSV has passed. However, we know from
above that I had to close the upstream channel at time X - D_success -
CSV_update - D_update, which may very well be before Y. So if the
downstream hop waits until just before Y to publish the preimage, they can
force me to close my upstream channel. This applies transitively for
further upstream hops, assuming a large enough CSV value.

Granted, upstream hops can watch the blockchain for preimage reveals in
other closings transaction and perhaps fulfill off-chain if there is
sufficient time. This would not be possible with payment decorrelation
through scriptless scripts or the like.

Does that logic sound right to you?

On Tue, May 1, 2018 at 10:31 AM, Christian Decker <
Post by ZmnSCPxj via bitcoin-dev
I'm still not following why this doesn't accumulate.
In the example route, let's look at it from the point of view of C. C
sees
the following regardless of whether D or E or someone behind E is the
last
B -> HTLC(expire = X + delta) -> C -> HTLC(expire = X) -> D
So D is not required to reveal the preimage before time X, and in the
case
of an on-chain settle, C needs to be able to redeem the HTLC output
through
the timeout clause before time X + delta. C can't redeem the HTLC (with
sufficient confirmations) at least until the settlement transaction is
confirmed. So it seems to me that regardless of the overall route and the
maximum CSV on it, the delta for the C hop has to be greater than the CSV
delay on the update transaction. And that this must be true at every hop
for the same reason.
That'd be a purely reactionary behavior, i.e., chosing the delta in such
a way that I can both settle the channel and have enough time to react
to turn around and reveal the preimage. So with the assumptions we had
before (CSV = 144 and CLTV delta = 144) you'd have an effective delta of
288 on each hop, yes. That's basically the case in which each channel
reacts serially.
You can trivially parallelize these closures by looking ahead and
noticing that each hop really just cares about its own closure deadline,
i.e., each node just cares to close 288 blocks before the CLTV expires,
not that its delta w.r.t. to the downstream channel is that far in the
future. So all we care about is that once we are due to give the
upstream hop the preimage we've already closed the downstream channel
and can now read the HTLC preimage from that channel.
The CSV timeout isn't part of the delta on each hop, but we need to
```
CLTV - CLTV delta - CSV
```
instead of LN-penaltiy's
```
CLTV - CLTV delta
```
ZmnSCPxj via bitcoin-dev
2018-05-01 05:07:54 UTC
Permalink
Raw Message
Good morning Christian,

This is very interesting indeed!

I have started skimming through the paper.

I am uncertain if the below text is correct?
Throughout this paper we will use the terms *input script* to refer to `witnessProgram` and `scriptPubKey`, and *output script* to refer to the `witness` or `scriptSig`.
OP_IF
10 OP_CSV
2 As Bs 2 OP_CHECKMULTISIGVERIFY
OP_ELSE
2 Au Bu 2 OP_CHECKMULTISIGVERIFY
OP_ENDIF
Figure 2: The output script used by the on-chain update transactions.
Regards,
ZmnSCPxj
Christian Decker via bitcoin-dev
2018-05-01 11:38:12 UTC
Permalink
Raw Message
Post by ZmnSCPxj via bitcoin-dev
Good morning Christian,
This is very interesting indeed!
I have started skimming through the paper.
I am uncertain if the below text is correct?
Throughout this paper we will use the terms *input script* to refer to `witnessProgram` and `scriptPubKey`, and *output script* to refer to the `witness` or `scriptSig`.
OP_IF
10 OP_CSV
2 As Bs 2 OP_CHECKMULTISIGVERIFY
OP_ELSE
2 Au Bu 2 OP_CHECKMULTISIGVERIFY
OP_ENDIF
Figure 2: The output script used by the on-chain update transactions.
Regards,
ZmnSCPxj
Darn last minute changes! Yes, you are right, I seem to have flipped the
two definitions. I'll fix that up and push a new version.
Loading...