[bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[jlspc]

[-- Attachment #1: Type: text/plain, Size: 16599 bytes --]

TL;DR
=====
* All known Lightning channel and factory protocols are susceptible to forced expiration spam attacks, in which an attacker floods the blockchain with transactions in order to prevent honest users from putting their transactions onchain before timelocks expire.
* Feerate-Dependent Timelocks (FDTs) are timelocks that automatically extend when blockchain feerates spike.
  - In the normal case, there's no spike in feerates and thus no tradeoff between capital efficiency and safety.
  - If a dishonest user attempts a forced expiration spam attack, feerates increase and FDTs are extended, thus penalizing the attacker by keeping their capital timelocked for longer.
  - FDTs are tunable and can be made to be highly resistant to attacks from dishonest miners.
* Of separate interest, an exact analysis of the risk of double spend attacks is presented that corrects an error in the original Bitcoin whitepaper.

Overview
========

Because the Lightning protocol relies on timelocks to establish the correct channel state, Lightning users could lose their funds if they're unable to put their transactions onchain quickly enough.
The original Lightning paper [1] states that "[f]orced expiration of many transactions may be the greatest systemic risk when using the Lightning Network" and it uses the term "forced expiration spam" for an attack in which a malicious party "creates many channels and forces them all to expire at once", thus allowing timelocked transactions to become valid.
That paper also says that the creation of a credible threat against "spamming the blockchain to encourage transactions to timeout" is "imperative" [1].

Channel factories that create multiple Lightning channels with a single onchain transaction [2][3][4][5] increase this risk in two ways.
First, factories allow more channels to be created, thus increasing the potential for many channels to require onchain transactions at the same time.
Second, channel factories themselves use timelocks, and thus are vulnerable to a "forced expiration spam" attack.

In fact, the timelocks in Lightning channels and factories are risky even without an attack from a malicious party.
Blockchain congestion is highly variable and new applications (such as ordinals) can cause a sudden spike in congestion at any time.
As a result, timelocks that were set when congestion was low can be too short when congestion spikes.
Even worse, a spike in congestion could be self-reinforcing if it causes malicious parties to attack opportunistically and honest parties to put their channels onchain due to the heightened risk.

One way to reduce the risk of a forced expiration spam attack is to use longer timelocks that give honest users more time to put their transactions onchain.
However, long timelocks limit the ability to dynamically reassign the channel's (or factory's) funds, thus creating a tradeoff between capital efficiency and safety [6].
While long timelocks could maintain safety for small numbers of channels, supporting billions (or tens of billions) of channels while maintaining safety is probably impossible [7].

Another way to reduce risk is to impose a penalty on an attacker.
Some channel protocols, such as the original Lightning protocol [1], a version of the two-party eltoo protocol [8], the fully-factory-optimized protocol [9], and the tunable-penalty channel protocol [10] include such penalties.
In addition, the tunable-penalty and single-commitment factory protocols [4] support penalties.
However, as was noted in the original Lightning paper [1], penalties don't eliminate the risk of a forced expiration spam attack.
Furthermore, existing penalty-based factory protocols [4] have limited scalability, as they depend on getting large numbers of casual users to coordinate and co-sign transactions [11][5].

In contrast, the timeout-tree protocol [5] scales via simple covenants (enabled by support for CheckTemplateVerify, AnyPrevOut, or a similar change to the Bitcoin consensus rules).
As a result, a single timeout-tree can support millions of channels and one small transaction per block can fund timeout-trees with tens of billions of offchain channels [5].
However, timeout-trees don't support penalties, and like all other known factory protocols [2][3][4], timeout-trees rely on timelocks.

Therefore, if the need to protect against forced expiration spam was already "imperative" for the original Lightning channel protocol [1], the use of scalable channel factories will make such protection indispensable.

This post proposes a change to Bitcoin's consensus rules that allows the length of a timelock to depend on the feerate being charged for putting transactions onchain.
Such Feerate-Dependent Timelocks (FDTs) can be used to make the above channel and factory protocols resistant to sudden spikes in blockchain congestion.
In the normal case, when there's no spike in congestion, FDTs don't extend the lengths of timelocks and thus don't create a tradeoff between capital efficiency and safety.
On the other hand, when congestion spikes, FDTs extend the lengths of timelocks and thus penalize the owner of the timelocked capital by reducing its efficiency.
Therefore, FDTs can be viewed as creating a penalty for spamming the blockchain, thus reducing the likelihood of such an attack even if the channel (or factory) protocol being used doesn't have an explicit penalty mechanism.

FDTs have other uses, including reducing the risk of having to pay unexpectedly high fees during a congestion spike, improving the accuracy of fee-penalties [5] and reducing the risk of one-shot receives [12].

Of separate interest, the analysis of FDTs given here leads to an exact analysis of the risk of double spend attacks that corrects an error in the original Bitcoin whitepaper [13].

A more complete description and analysis of FDTs is given in a paper [14].

Feerate-Dependent Timelock (FDT) Proposal
=========================================

A Feerate-Dependent Timelock (FDT) is created by encoding a feerate upper bound in a transaction's nSequence field.
A transaction with an FDT cannot be put onchain until:
  1) its absolute timelock encoded in its nLocktime field (and its relative timelock encoded in the same nSequence field, if present) has been satisfied, and
  2) the prevailing feerate has fallen below the FDT's feerate upper bound.
As a result, FDTs are automatically extended when the feerate for putting transactions onchain spikes (such as would occur during a forced expiration spam attack).

In order to determine the prevailing feerate, the median feerate of each block is calculated as the feerate (in satoshis/vbyte) that is paid for at least half of the block's vbytes.

If all miners were honest, a single block with a low median feerate would be enough to guarantee that congestion is low.
However, even a small fraction of dishonest miners would be able to occasionally mine a block with an artificially low feerate.
As a result, it isn't safe to wait for one block (or some other fixed number of blocks) with a low feerate in order to guarantee that honest users have had an opportunity to put their transactions onchain.

Instead, an FDT requires that some maximum number of blocks within an aligned window of consecutive blocks have a high median feerate.
The FDT proposal uses 14 currently masked-off bits in the nSequence field to express the FDT's three parameters:
  * feerate_value,
  * window_size, and
  * block_count.
An aligned window of window_size blocks satisfies the FDT's parameters if it has fewer than block_count blocks with median feerate above feerate_value.
A transaction with an FDT can only be put onchain after an aligned window that satisfies the FDT's parameters and starts no earlier than when the transaction's absolute timelock (and corresponding relative timelock, if present) is satisfied.

In addition, the CheckSequenceVerify (CSV) operator is extended to enforce the desired feerate_value, window_size and block_count.
The details are given in the paper [14].

Safe Lightning Channels And Factories
=====================================

In order to protect a channel or factory protocol against forced expiration spam attacks, the protocol's timelocks are made to be feerate-dependent.
This is done by selecting a feerate_value (such as 4 times the current feerate) that would be caused by a forced expiration spam attack, along with the desired window_size and block_count parameters.

It's also possible to create multiple conflicting transactions with different FDTs (with later timelocks allowing higher feerates) in order to avoid timelocks that will never expire if feerates remain high permanently.

Other Uses
==========

FDTs have uses in addition to protecting channel and factory protocols from forced expiration spam attacks.

For example, FDTs can protect users that are racing against timelocks from having to pay an unexpectedly high feerate due to temporary feerate fluctuations [14].
In addition, FDTs can be used to improve the accuracy of fee-penalties that are assessed when a casual user puts their timeout-tree leaf onchain [14](Section 4.10 of [5]).
Finally, FDTs can be used to allow a casual user to submit a transaction to the blockchain without having to then monitor the blockchain for a sudden spike in feerates, thus reducing the risk of one-shot receives [14][12].

Analysis
========

FDT Implementation Cost
-----------------------
In order to verify an FDT, nodes have to determine whether or not there is an aligned window with a sufficient number of low-feerate blocks after the FDT's absolute timelock (and corresponding relative timelock, if present) is satisfied.
Therefore, if a node knows the starting block of the most recent aligned window that satisfies the FDT's feerate_value, window_size, and block_count parameters, the node can compare that starting block with the FDT's timelocks to verify the FDT.
Because the FDT parameters can be expressed using 14 bits, nodes only have to keep track of the starting block for 2^14 = 16k different low-feerate windows.
The starting block for each such window can be stored in 4 bytes, so 16k * 4B = 64kB of memory allows a node to verify an FDT in constant time.
(In practice, slightly more memory could be used in order to accommodate a reordering of the most recent 1k blocks.)
Therefore, DRAM that costs less than one cent, plus a small constant number of computations, suffice to verify an FDT.

FDT Dishonest Miner Attacks
---------------------------
The window_size and block_count parameters can be selected to balance between:
  1) latency,
  2) the feerate paid by honest users, and
  3) security against dishonest miners.
At one extreme, if dishonest miners are of no concern, window_size and block_count can be set to 1, so the FDT can be satisfied when the first block with a sufficiently low feerate is mined.
At the other extreme, if dishonest miners are of great concern, window_size can be set to 16k and block_count can be set to 1024, in which case dishonest miners with 45% of the hashpower would have less than a 10^-33 chance of dishonestly mining enough blocks in a given window to satisfy the FDT prior to the honest users being able to get their transactions onchain [14].

Double Spend Attacks
--------------------
While it's unrelated to FDTs, the analysis of FDTs' resistance to dishonest miner attacks can also be used to analyze the risk of double spend attacks.

The original Bitcoin whitepaper [13] includes an analysis of the probability of a double spend attack in which a dishonest party colludes with dishonest miners in order to undo a bitcoin transaction and steal the goods purchased with that transaction.
That analysis correctly shows that the probability of success of a double spend attack falls exponentially with z, the depth of the transaction that's being double spent.
However, there are two problems with that analysis:
  1) it is approximate, and
  2) it ignores the possibility of the dishonest miners using pre-mining.

The first problem was addressed by Grunspan and Perez-Marco [15].
However, it doesn't appear that the second problem has been addressed previously.

Exact formulas for the risk of double spend attacks, including pre-mining, are given in the paper [14] and programs that implement those formulas are available on GitHub [16].

The effect of including pre-mining only becomes apparent when a large fraction of the miners are dishonest.
For example, Nakamoto estimates the required value of z to guarantee at most a 0.1% chance of a successful double spend, and Grunspan and Perez-Marco give exact values assuming no pre-mining.
Those results, plus exact results with pre-mining, are as follows:

% dishonest  Estimated z w/o      Exact z w/o       Exact z w/
     miners  pre-mining [13]  pre-mining [15]  pre-mining [14]
===========  ===============  ===============  ===============
         10                5                6                6
         15                8                9                9
         20               11               13               13
         25               15               20               20
         30               24               32               33
         35               41               58               62
         40               89              133              144
         45              340              539              589

It's important to note that the above results with pre-mining assume that the time of the double spend attack is not selected by the attacker.
If the attacker can select when to perform the attack, they are guaranteed to succeed given any value of z, but the expected time required to perform the attack grows exponentially with z [14].

Conclusions
===========

Securing Lightning channels and channel factories against forced expiration spam attacks is imperative.

Feerate-Dependent Timelocks (FDTs) provide this security without forcing the timelocks to be extended in the typical case, thus avoiding a capital efficiency vs. safety tradeoff.
Furthermore, a dishonest user who tries to use a forced expiration spam attack to steal funds is penalized by having their funds timelocked for a longer period, thus discouraging such attacks.
Finally, FDTs can be made to be highly resistant to attacks by dishonest miners.

FDTs have other uses, including the reduction of feerate risk and the calculation of fee-penalties.

While implementing FDTs requires some additional DRAM and computation, the costs are extremely small.
Given these advantages and their low costs, it's hoped that the Bitcoin consensus rules will be changed to support FDTs.

Regards,
John

[1] Poon and Dryja, The Bitcoin Lightning Network, https://lightning.network/lightning-network-paper.pdf
[2] Burchert, Decker and Wattenhofer, "Scalable Funding of Bitcoin Micropayment Channel Networks", http://dx.doi.org/10.1098/rsos.180089
[3] Decker, Russell and Osuntokun. "eltoo: A Simple Layer2 Protocol for Bitcoin", https://blockstream.com/eltoo.pdf
[4] Law, "Efficient Factories For Lightning Channels", https://github.com/JohnLaw2/ln-efficient-factories
[5] Law, "Scaling Lightning With Simple Covenants", https://github.com/JohnLaw2/ln-scaling-covenants
[6] Towns, "Re: Scaling Lightning With Simple Covenants", https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-September/021943.html
[7] Law, "Re: Scaling Lightning With Simple Covenants", https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-November/022175.html
[8] Towns, "Two-party eltoo w/ punishment", https://lists.linuxfoundation.org/pipermail/lightning-dev/2022-December/003788.html
[9] Law, "Factory-Optimized Channel Protocols For Lightning", https://github.com/JohnLaw2/ln-factory-optimized
[10] Law, "Lightning Channels With Tunable Penalties", https://github.com/JohnLaw2/ln-tunable-penalties
[11] Riard, "Solving CoinPool high-interactivity issue with cut-through update of Taproot leaves", https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-September/021969.html
[12] Law, "Watchtower-Free Lightning Channels For Casual Users", https://github.com/JohnLaw2/ln-watchtower-free
[13] Nakamoto. "Bitcoin: A Peer-to-Peer Electronic Cash System", http://bitcoin.org/bitcoin.pdf
[14] Law, "Scaling Lightning Safely With Feerate-Dependent Timelocks", https://github.com/JohnLaw2/ln-fdts
[15] Grunspan and Perez-Marco, "Double Spend Races", CoRR, vol. abs/1702.02867, http://arxiv.org/abs/1702.02867v3
[16] Law, https://github.com/JohnLaw2/ln-fdts

Sent with [Proton Mail](https://proton.me/) secure email.

[-- Attachment #2: Type: text/html, Size: 18575 bytes --]

Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[Antoine Riard]

[-- Attachment #1: Type: text/plain, Size: 22458 bytes --]

Hi John,

While the idea of using sliding reaction window for blockchain congestion
detection has been present in the "smart contract" space at large [0] and
this has been discussed informally among Lightning devs and covenant
designers few times [1] [2], this is the first and best formalization of
sliding-time-locks in function of block fee rates for Bitcoin I'm aware
off, to the best of my knowledge.

Here my understanding of the feerate-dependent timelock proposal.

A transaction cannot be included in a block:
- height-based or epoch-based absolute or relative timelocks are not
satisfied according to current consensus rules (bip68 and bip 113 and
implementation details)
- less than `block_count` has a block median-feerate above the
median-feerate of the `window_size` period

A median feerate is computed for each block.
(This is unclear to me if this is the feerate for half of the block's
weight or the median feerate with all weight units included in the
block as the sample)

From then, you have 3 parameters included in the nSequence field.
- feerate_value_bound
- window_size
- block_count

Those parameters can be selected by the transaction builder (and
committed with a signature or hash chain-based covenant).
As such, off-chain construction counterparties can select the
feerate_value_bound at which their time-sensitive transaction
confirmation will be delayed.

E.g let's say you have a LN-penalty Alice-Bob channel. Second-stage
HTLC transactions are pre-signed with feerate_value_bound at 100 sat /
vbytes.
The window_size selected is 100 blocks and the block_count is 70 (this
guarantees tampering-robustness of the feerate_value_bound in face of
miners coalitions).

There is 1 BTC offered HTLC pending with expiration time T, from Alice to Bob.

If at time T, the per-block median feerate of at least 70 blocks over
the latest 100 block is above 100 sat / vbytes, any Alice's
HTLC-timeout or Bob's HTLC-preimage cannot be included in the chain.

From my understanding, Feerate-Dependent Timelocks effectively
constitute the lineaments of a solution to the "Forced Expiration
Spam" as described in the LN paper.

I think you have few design caveats to be aware off:
- for current LN-penalty, the revokeable scripts should be modified to
ensure the CSV opcode inspect the enforcement of FDT's parameters, as
those revokeable scripts are committed by all parties
- there should be a delay period at the advantage of one party
otherwise you still a feerate-race if the revocation bip68 timelock
has expired during the FDT delay

As such, I believe the FDT parameters should be enriched with another
parameter : `claim_grace_period`, a new type of relative timelock of
which the endpoint should be the `feerate_value_bound` itself.

I think it works in terms of consensus chain state, validation
resources and reorg-safety are all the parameters that are
self-contained in the spent FDT-encumbered transaction itself.
If the per-block feerate fluctuates, the validity of the ulterior
FDT-locked transactions changes too, though this is already the case
with timelock-encumbered transactions.

(One corollary for Lightning, it sounds like all the channels carrying
on a HTLC along a payment path should have the same FDT-parameters to
avoid off-chain HTLC double-spend, a risk not clearly articulated in
the LN paper).

Given the one more additional parameter `claim_grace_period`, I think
it would be wiser design to move all the FDT parameters in the bip341
annex.
There is more free bits room there and additionally you can have
different FDT parameters for each of your HTLC outputs in a single LN
transaction, if combined with future covenant mechanisms like HTLC
aggregation [3].
(The current annex design draft has been designed among others to
enable such "block-feerate-lock-point" [4] [5])

I cannot assert that the FDT proposal makes the timeout-tree protocol
more efficient than state-of-the-art channel factories and payment
pool constructions.
Still from my understanding, all those constructions are sharing
frailties in face of blockchain congestion and they would need
something like FDT.

I'm truly rejoicing at the idea that we have now the start of a
proposal solving one of the most imperative issues of Lightning and
other time-sensitive use-cases.
(Note, I've not reviewed the analysis and game-theory in the face of
miners collusion / coalition, as I think the introduction of a
`claim_grace_period` is modifying the fundamentals).

Best,
Antoine

[0] https://fc22.ifca.ai/preproceedings/119.pdf
[1] https://github.com/ariard/bitcoin-contracting-primitives-wg/blob/main/meetings/meetings-18-04.md
[2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-November/022180.html
[3] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-October/022093.html
[4] https://github.com/bitcoin-inquisition/bitcoin/pull/9

[5] https://github.com/bitcoin/bips/pull/1381


Le ven. 15 déc. 2023 à 09:20, jlspc via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> a écrit :

> TL;DR
> =====
> * All known Lightning channel and factory protocols are susceptible to forced expiration spam attacks, in which an attacker floods the blockchain with transactions in order to prevent honest users from putting their transactions onchain before timelocks expire.
> * Feerate-Dependent Timelocks (FDTs) are timelocks that automatically extend when blockchain feerates spike.
>   - In the normal case, there's no spike in feerates and thus no tradeoff between capital efficiency and safety.
>   - If a dishonest user attempts a forced expiration spam attack, feerates increase and FDTs are extended, thus penalizing the attacker by keeping their capital timelocked for longer.
>   - FDTs are tunable and can be made to be highly resistant to attacks from dishonest miners.
> * Of separate interest, an exact analysis of the risk of double spend attacks is presented that corrects an error in the original Bitcoin whitepaper.
>
> Overview
> ========
>
> Because the Lightning protocol relies on timelocks to establish the correct channel state, Lightning users could lose their funds if they're unable to put their transactions onchain quickly enough.
> The original Lightning paper [1] states that "[f]orced expiration of many transactions may be the greatest systemic risk when using the Lightning Network" and it uses the term "forced expiration spam" for an attack in which a malicious party "creates many channels and forces them all to expire at once", thus allowing timelocked transactions to become valid.
> That paper also says that the creation of a credible threat against "spamming the blockchain to encourage transactions to timeout" is "imperative" [1].
>
> Channel factories that create multiple Lightning channels with a single onchain transaction [2][3][4][5] increase this risk in two ways.
> First, factories allow more channels to be created, thus increasing the potential for many channels to require onchain transactions at the same time.
> Second, channel factories themselves use timelocks, and thus are vulnerable to a "forced expiration spam" attack.
>
> In fact, the timelocks in Lightning channels and factories are risky even without an attack from a malicious party.
> Blockchain congestion is highly variable and new applications (such as ordinals) can cause a sudden spike in congestion at any time.
> As a result, timelocks that were set when congestion was low can be too short when congestion spikes.
> Even worse, a spike in congestion could be self-reinforcing if it causes malicious parties to attack opportunistically and honest parties to put their channels onchain due to the heightened risk.
>
> One way to reduce the risk of a forced expiration spam attack is to use longer timelocks that give honest users more time to put their transactions onchain.
> However, long timelocks limit the ability to dynamically reassign the channel's (or factory's) funds, thus creating a tradeoff between capital efficiency and safety [6].
> While long timelocks could maintain safety for small numbers of channels, supporting billions (or tens of billions) of channels while maintaining safety is probably impossible [7].
>
> Another way to reduce risk is to impose a penalty on an attacker.
> Some channel protocols, such as the original Lightning protocol [1], a version of the two-party eltoo protocol [8], the fully-factory-optimized protocol [9], and the tunable-penalty channel protocol [10] include such penalties.
> In addition, the tunable-penalty and single-commitment factory protocols [4] support penalties.
> However, as was noted in the original Lightning paper [1], penalties don't eliminate the risk of a forced expiration spam attack.
> Furthermore, existing penalty-based factory protocols [4] have limited scalability, as they depend on getting large numbers of casual users to coordinate and co-sign transactions [11][5].
>
> In contrast, the timeout-tree protocol [5] scales via simple covenants (enabled by support for CheckTemplateVerify, AnyPrevOut, or a similar change to the Bitcoin consensus rules).
> As a result, a single timeout-tree can support millions of channels and one small transaction per block can fund timeout-trees with tens of billions of offchain channels [5].
> However, timeout-trees don't support penalties, and like all other known factory protocols [2][3][4], timeout-trees rely on timelocks.
>
> Therefore, if the need to protect against forced expiration spam was already "imperative" for the original Lightning channel protocol [1], the use of scalable channel factories will make such protection indispensable.
>
> This post proposes a change to Bitcoin's consensus rules that allows the length of a timelock to depend on the feerate being charged for putting transactions onchain.
> Such Feerate-Dependent Timelocks (FDTs) can be used to make the above channel and factory protocols resistant to sudden spikes in blockchain congestion.
> In the normal case, when there's no spike in congestion, FDTs don't extend the lengths of timelocks and thus don't create a tradeoff between capital efficiency and safety.
> On the other hand, when congestion spikes, FDTs extend the lengths of timelocks and thus penalize the owner of the timelocked capital by reducing its efficiency.
> Therefore, FDTs can be viewed as creating a penalty for spamming the blockchain, thus reducing the likelihood of such an attack even if the channel (or factory) protocol being used doesn't have an explicit penalty mechanism.
>
> FDTs have other uses, including reducing the risk of having to pay unexpectedly high fees during a congestion spike, improving the accuracy of fee-penalties [5] and reducing the risk of one-shot receives [12].
>
> Of separate interest, the analysis of FDTs given here leads to an exact analysis of the risk of double spend attacks that corrects an error in the original Bitcoin whitepaper [13].
>
> A more complete description and analysis of FDTs is given in a paper [14].
>
> Feerate-Dependent Timelock (FDT) Proposal
> =========================================
>
> A Feerate-Dependent Timelock (FDT) is created by encoding a feerate upper bound in a transaction's nSequence field.
> A transaction with an FDT cannot be put onchain until:
>   1) its absolute timelock encoded in its nLocktime field (and its relative timelock encoded in the same nSequence field, if present) has been satisfied, and
>   2) the prevailing feerate has fallen below the FDT's feerate upper bound.
> As a result, FDTs are automatically extended when the feerate for putting transactions onchain spikes (such as would occur during a forced expiration spam attack).
>
> In order to determine the prevailing feerate, the median feerate of each block is calculated as the feerate (in satoshis/vbyte) that is paid for at least half of the block's vbytes.
>
> If all miners were honest, a single block with a low median feerate would be enough to guarantee that congestion is low.
> However, even a small fraction of dishonest miners would be able to occasionally mine a block with an artificially low feerate.
> As a result, it isn't safe to wait for one block (or some other fixed number of blocks) with a low feerate in order to guarantee that honest users have had an opportunity to put their transactions onchain.
>
> Instead, an FDT requires that some maximum number of blocks within an aligned window of consecutive blocks have a high median feerate.
> The FDT proposal uses 14 currently masked-off bits in the nSequence field to express the FDT's three parameters:
>   * feerate_value,
>   * window_size, and
>   * block_count.
> An aligned window of window_size blocks satisfies the FDT's parameters if it has fewer than block_count blocks with median feerate above feerate_value.
> A transaction with an FDT can only be put onchain after an aligned window that satisfies the FDT's parameters and starts no earlier than when the transaction's absolute timelock (and corresponding relative timelock, if present) is satisfied.
>
> In addition, the CheckSequenceVerify (CSV) operator is extended to enforce the desired feerate_value, window_size and block_count.
> The details are given in the paper [14].
>
> Safe Lightning Channels And Factories
> =====================================
>
> In order to protect a channel or factory protocol against forced expiration spam attacks, the protocol's timelocks are made to be feerate-dependent.
> This is done by selecting a feerate_value (such as 4 times the current feerate) that would be caused by a forced expiration spam attack, along with the desired window_size and block_count parameters.
>
> It's also possible to create multiple conflicting transactions with different FDTs (with later timelocks allowing higher feerates) in order to avoid timelocks that will never expire if feerates remain high permanently.
>
> Other Uses
> ==========
>
> FDTs have uses in addition to protecting channel and factory protocols from forced expiration spam attacks.
>
> For example, FDTs can protect users that are racing against timelocks from having to pay an unexpectedly high feerate due to temporary feerate fluctuations [14].
> In addition, FDTs can be used to improve the accuracy of fee-penalties that are assessed when a casual user puts their timeout-tree leaf onchain [14](Section 4.10 of [5]).
> Finally, FDTs can be used to allow a casual user to submit a transaction to the blockchain without having to then monitor the blockchain for a sudden spike in feerates, thus reducing the risk of one-shot receives [14][12].
>
> Analysis
> ========
>
> FDT Implementation Cost
> -----------------------
> In order to verify an FDT, nodes have to determine whether or not there is an aligned window with a sufficient number of low-feerate blocks after the FDT's absolute timelock (and corresponding relative timelock, if present) is satisfied.
> Therefore, if a node knows the starting block of the most recent aligned window that satisfies the FDT's feerate_value, window_size, and block_count parameters, the node can compare that starting block with the FDT's timelocks to verify the FDT.
> Because the FDT parameters can be expressed using 14 bits, nodes only have to keep track of the starting block for 2^14 = 16k different low-feerate windows.
> The starting block for each such window can be stored in 4 bytes, so 16k * 4B = 64kB of memory allows a node to verify an FDT in constant time.
> (In practice, slightly more memory could be used in order to accommodate a reordering of the most recent 1k blocks.)
> Therefore, DRAM that costs less than one cent, plus a small constant number of computations, suffice to verify an FDT.
>
> FDT Dishonest Miner Attacks
> ---------------------------
> The window_size and block_count parameters can be selected to balance between:
>   1) latency,
>   2) the feerate paid by honest users, and
>   3) security against dishonest miners.
> At one extreme, if dishonest miners are of no concern, window_size and block_count can be set to 1, so the FDT can be satisfied when the first block with a sufficiently low feerate is mined.
> At the other extreme, if dishonest miners are of great concern, window_size can be set to 16k and block_count can be set to 1024, in which case dishonest miners with 45% of the hashpower would have less than a 10^-33 chance of dishonestly mining enough blocks in a given window to satisfy the FDT prior to the honest users being able to get their transactions onchain [14].
>
> Double Spend Attacks
> --------------------
> While it's unrelated to FDTs, the analysis of FDTs' resistance to dishonest miner attacks can also be used to analyze the risk of double spend attacks.
>
> The original Bitcoin whitepaper [13] includes an analysis of the probability of a double spend attack in which a dishonest party colludes with dishonest miners in order to undo a bitcoin transaction and steal the goods purchased with that transaction.
> That analysis correctly shows that the probability of success of a double spend attack falls exponentially with z, the depth of the transaction that's being double spent.
> However, there are two problems with that analysis:
>   1) it is approximate, and
>   2) it ignores the possibility of the dishonest miners using pre-mining.
>
> The first problem was addressed by Grunspan and Perez-Marco [15].
> However, it doesn't appear that the second problem has been addressed previously.
>
> Exact formulas for the risk of double spend attacks, including pre-mining, are given in the paper [14] and programs that implement those formulas are available on GitHub [16].
>
> The effect of including pre-mining only becomes apparent when a large fraction of the miners are dishonest.
> For example, Nakamoto estimates the required value of z to guarantee at most a 0.1% chance of a successful double spend, and Grunspan and Perez-Marco give exact values assuming no pre-mining.
> Those results, plus exact results with pre-mining, are as follows:
>
> % dishonest  Estimated z w/o      Exact z w/o       Exact z w/
>      miners  pre-mining [13]  pre-mining [15]  pre-mining [14]
> ===========  ===============  ===============  ===============
>          10                5                6                6
>          15                8                9                9
>          20               11               13               13
>          25               15               20               20
>          30               24               32               33
>          35               41               58               62
>          40               89              133              144
>          45              340              539              589
>
> It's important to note that the above results with pre-mining assume that the time of the double spend attack is not selected by the attacker.
> If the attacker can select when to perform the attack, they are guaranteed to succeed given any value of z, but the expected time required to perform the attack grows exponentially with z [14].
>
> Conclusions
> ===========
>
> Securing Lightning channels and channel factories against forced expiration spam attacks is imperative.
>
> Feerate-Dependent Timelocks (FDTs) provide this security without forcing the timelocks to be extended in the typical case, thus avoiding a capital efficiency vs. safety tradeoff.
> Furthermore, a dishonest user who tries to use a forced expiration spam attack to steal funds is penalized by having their funds timelocked for a longer period, thus discouraging such attacks.
> Finally, FDTs can be made to be highly resistant to attacks by dishonest miners.
>
> FDTs have other uses, including the reduction of feerate risk and the calculation of fee-penalties.
>
> While implementing FDTs requires some additional DRAM and computation, the costs are extremely small.
> Given these advantages and their low costs, it's hoped that the Bitcoin consensus rules will be changed to support FDTs.
>
> Regards,
> John
>
> [1] Poon and Dryja, The Bitcoin Lightning Network, https://lightning.network/lightning-network-paper.pdf
> [2] Burchert, Decker and Wattenhofer, "Scalable Funding of Bitcoin Micropayment Channel Networks", http://dx.doi.org/10.1098/rsos.180089
> [3] Decker, Russell and Osuntokun. "eltoo: A Simple Layer2 Protocol for Bitcoin", https://blockstream.com/eltoo.pdf
> [4] Law, "Efficient Factories For Lightning Channels", https://github.com/JohnLaw2/ln-efficient-factories
> [5] Law, "Scaling Lightning With Simple Covenants", https://github.com/JohnLaw2/ln-scaling-covenants
> [6] Towns, "Re: Scaling Lightning With Simple Covenants", https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-September/021943.html
> [7] Law, "Re: Scaling Lightning With Simple Covenants", https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-November/022175.html
> [8] Towns, "Two-party eltoo w/ punishment", https://lists.linuxfoundation.org/pipermail/lightning-dev/2022-December/003788.html
> [9] Law, "Factory-Optimized Channel Protocols For Lightning", https://github.com/JohnLaw2/ln-factory-optimized
> [10] Law, "Lightning Channels With Tunable Penalties", https://github.com/JohnLaw2/ln-tunable-penalties
> [11] Riard, "Solving CoinPool high-interactivity issue with cut-through update of Taproot leaves", https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-September/021969.html
> [12] Law, "Watchtower-Free Lightning Channels For Casual Users", https://github.com/JohnLaw2/ln-watchtower-free
> [13] Nakamoto. "Bitcoin: A Peer-to-Peer Electronic Cash System", http://bitcoin.org/bitcoin.pdf
> [14] Law, "Scaling Lightning Safely With Feerate-Dependent Timelocks", https://github.com/JohnLaw2/ln-fdts
> [15] Grunspan and Perez-Marco, "Double Spend Races", CoRR, vol. abs/1702.02867, http://arxiv.org/abs/1702.02867v3
> [16] Law, https://github.com/JohnLaw2/ln-fdts
>
>
>
>
> Sent with Proton Mail <https://proton.me/> secure email.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 25962 bytes --]

Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[jlspc]

[-- Attachment #1: Type: text/plain, Size: 19900 bytes --]

Hi Antoine,

Thanks for your thoughtful response.

Comments inline below:

> Hi John,

> While the idea of using sliding reaction window for blockchain congestion
> detection has been present in the "smart contract" space at large [0] and
> this has been discussed informally among Lightning devs and covenant
> designers few times [1] [2], this is the first and best formalization of
> sliding-time-locks in function of block fee rates for Bitcoin I'm aware
> off, to the best of my knowledge.

Thanks!

> Here my understanding of the feerate-dependent timelock proposal.

> A transaction cannot be included in a block:
> - height-based or epoch-based absolute or relative timelocks are not
> satisfied according to current consensus rules (bip68 and bip 113 and
> implementation details)
> - less than `block_count` has a block median-feerate above the
> median-feerate of the `window_size` period

It's a little bit different from that.
The transaction cannot be included in the blockchain until after an aligned window W of window_size blocks where:
1) W starts no sooner than when the height-based or epoch-based absolute and/or relative timelocks have been satisfied, and
2) W contains fewer than block_count blocks with median feerate greater than feerate_value_bound.

Note that the aligned window cannot start until the absolute and/or relative timelocks have been satisfied and the transaction itself has to come after the aligned window.
However, once such an aligned window exists in the blockchain, the transaction can appear at any later time (and not just within a window that itself meets the block_count and feerate_value_bound limitations).

> A median feerate is computed for each block.
> (This is unclear to me if this is the feerate for half of the block's
> weight or the median feerate with all weight units included in the
> block as the sample)

A feerate F is the median feerate of a block B if F is the largest feerate such that the total size of the transactions in B with feerate greater or equal to F is at least 2 million vbytes.

> From then, you have 3 parameters included in the nSequence field.
> - feerate_value_bound
> - window_size
> - block_count

> Those parameters can be selected by the transaction builder (and
> committed with a signature or hash chain-based covenant).
> As such, off-chain construction counterparties can select the
> feerate_value_bound at which their time-sensitive transaction
> confirmation will be delayed.

> E.g let's say you have a LN-penalty Alice-Bob channel. Second-stage
> HTLC transactions are pre-signed with feerate_value_bound at 100 sat /
> vbytes.
> The window_size selected is 100 blocks and the block_count is 70 (this
> guarantees tampering-robustness of the feerate_value_bound in face of
> miners coalitions).

> There is 1 BTC offered HTLC pending with expiration time T, from Alice to Bob.

> If at time T, the per-block median feerate of at least 70 blocks over
> the latest 100 block is above 100 sat / vbytes, any Alice's
> HTLC-timeout or Bob's HTLC-preimage cannot be included in the chain.

The rules are actually:
1) wait until time T, then
2) wait until the start of a full aligned window W with 100 consecutive blocks that starts no earlier than T and that has fewer than 70 blocks with median feerate above 100 sats/vbyte.
(The values 100, 70, and 100 cannot actually be selected in the implementation in the paper, but that's a technical detail and could be changed if the FDT is specified in the annex, as you propose.)

> From my understanding, Feerate-Dependent Timelocks effectively
> constitute the lineaments of a solution to the "Forced Expiration
> Spam" as described in the LN paper.

Great!

> I think you have few design caveats to be aware off:
> - for current LN-penalty, the revokeable scripts should be modified to
> ensure the CSV opcode inspect the enforcement of FDT's parameters, as
> those revokeable scripts are committed by all parties

Yes, definitely.

> - there should be a delay period at the advantage of one party
> otherwise you still a feerate-race if the revocation bip68 timelock
> has expired during the FDT delay

> As such, I believe the FDT parameters should be enriched with another
> parameter : `claim_grace_period`, a new type of relative timelock of
> which the endpoint should be the `feerate_value_bound` itself.

I'm not sure I'm following your proposal.
Are you suggesting that the transaction with the FDT has to wait an additional claim_grace_period in order to allow conflicting transactions from the other party to win the race?
For example, assume the HTLC-success transaction has a higher feerate than the feerate_value_bound, and the conflicting HTLC-timeout transaction has an FDT with the feerate_value_bound (and suitable window_size and block_count parameters to defend against miner attacks).
In this case, is the worry that the HTLC-success and HTLC-timeout transactions could both be delayed until there is a window W that meets the FDT's feerate_value_bound, window_size and block_count parameters, at which point they would race against each other and either could win?
Is the reason to delay the HTLC-timeout by an additional claim_grace_period to guarantee that the HTLC-success transaction will win the race?
If so, I don't think it's needed, given the exact definition of the FDT proposal.
This is because *during* the window W that meets the FDT's requirements, the HTLC-success transaction should get mined into one of the blocks in W that has a median feerate no larger than feerate_value_bound, assuming honest miners.
The assumption of honest miners is resolved by setting the window_size and block_count parameters appropriately.
Does that make sense?

> I think it works in terms of consensus chain state, validation
> resources and reorg-safety are all the parameters that are
> self-contained in the spent FDT-encumbered transaction itself.
> If the per-block feerate fluctuates, the validity of the ulterior
> FDT-locked transactions changes too, though this is already the case
> with timelock-encumbered transactions.

> (One corollary for Lightning, it sounds like all the channels carrying
> on a HTLC along a payment path should have the same FDT-parameters to
> avoid off-chain HTLC double-spend, a risk not clearly articulated in
> the LN paper).

It's interesting that you focused on securing HTLCs, as I was focused on securing LN channel state (e.g., getting the right Commitment tx) and factory state.
The challenge with using FDTs to secure HTLCs is that you need a way to specify a sequence of FDTs (corresponding to the hops in a LN payment) that expire with enough time between them and with a low feerate period between them.
For example, consider a payment with n hops, where hop i has an HTLC that expires at time T_i, and where hop n is the last hop.
Without FDTs, one would select expiries such that T_i + cltv_expiry_delta_i < T_(i-1).
With FDTs, one can't just use the same T_i's and add an FDT that follows that T_i, because the feerate could be high until well after the first few T_i's are reached.
For example, assume T_n, T_(n-1) and T_(n-2) all occur before feerates fall below the feerate_value_bound.
In this case, the HTLC-timeout TXs for hops n, n-1 and n-2 would all be delayed until the feerates fell, and then they would all be able to be put onchain at the same time (without the required cltv_expiry_deltas between them).

One attempt to solve this would be to add another parameter that specifies how many blocks to wait after fees have falled below the feerate_value_bound (like the claim_grace_perid, if I understand it correctly).
However, that doesn't solve the problem because the congestion could start, and the feerate_value_bound could be exceeded, at any time.
For example, the feerate_value_bound could first be exceeded just after T_(n-1), in which case the fees would be too high to put the HTLC-success transaction onchain in hop T_(n-2).

What we really need is the ability to ensure that there have been enough low feerate expiries, each separated by the required cltv_expiry_delta.
This can be achieved by adding a new parameter, number_of_windows, that specifies how many low feerate windows W_1, W_2, etc., are required, all of which meet the feerate_value_bound, window_size and block_count parameters (and all of which start no later than when the standard absolute and relative timelocks have been satisfied).
With this new parameter, lower numbered hops (closer to the sender) can use larger values of number_of_windows in order to guarantee low feerate periods that meet the required cltv_expiry_deltas.

For example, assume feerate_value_bound is 256 sats/vbyte, window_size is 256, and block_count is 64.
Then, give the HTLC-timeout transaction in hop i an absolute timelock of T_n (the timelock for hop n) and an FDT with number_of_windows equal to (n-i+1) (and with feerate_value_bound, window_size and block_count as above).
In this case, as long as each cltv_expiry_delta is less than window_size - block_count = 192, then in each hop the party offered the HTLC can put their HTLC-success transaction onchain in a low feerate block after they have seen the hash preimage for at least cltv_expiry_delta blocks.
(In practice, the parameters could be tweaked a bit to break the association between hops, such as by using more restrictive feerate_value_bounds and/or block_counts as one gets closer to the source, and by increasing the number_of_windows parameter by more than one per hop as one gets closer to the source.)

> Given the one more additional parameter `claim_grace_period`, I think
> it would be wiser design to move all the FDT parameters in the bip341
> annex.
> There is more free bits room there and additionally you can have
> different FDT parameters for each of your HTLC outputs in a single LN
> transaction, if combined with future covenant mechanisms like HTLC
> aggregation [3].
> (The current annex design draft has been designed among others to
> enable such "block-feerate-lock-point" [4] [5])

I like your idea of putting the FDT parameters in the annex.
This is required if we add the number_of_windows parameter that I mentioned above.

In addition to finding enough bits in the transaction to hold the FDT parameters, there is a cost to increasing the parameters, namely the memory required to verify transactions with FDTs.
In the proposal in the paper, FDTs could be specified with 14 bits, so there were only 2^14 = 16k different values for which the starting block of the most recent aligned window satisfying those parameters has to be stored in order to quickly verify FDTs.
Assuming 4 bytes to store the starting block of a window, that's just 64k bytes of DRAM.
If we add a 6-bit number_of_windows parameter, that increases the storage by a factor of 64 to 4MB.
That's still pretty small, but we have to be careful to not make this too expensive.

> I cannot assert that the FDT proposal makes the timeout-tree protocol
> more efficient than state-of-the-art channel factories and payment
> pool constructions.
> Still from my understanding, all those constructions are sharing
> frailties in face of blockchain congestion and they would need
> something like FDT.

I agree that FDTs don't make timeout-trees more competitive against any other factory protoocol.
I also agree that FDTs can be used to make all of the LN channel and factory protocools safer.
If we extend the idea to include a number_of_windows parameter, then we should even be able to make HTLCs safer.

> I'm truly rejoicing at the idea that we have now the start of a
> proposal solving one of the most imperative issues of Lightning and
> other time-sensitive use-cases.

I'm very happy you see it that way.
Please let me know what you think of the number_of_windows idea, and if you have any other ideas for making HTLCs safer.

Regards,
John

Sent with [Proton Mail](https://proton.me/) secure email.

On Sunday, December 17th, 2023 at 3:01 PM, Antoine Riard <antoine.riard@gmail.com> wrote:

> Hi John,
>
> While the idea of using sliding reaction window for blockchain congestion detection has been present in the "smart contract" space at large [0] and this has been discussed informally among Lightning devs and covenant designers few times [1] [2], this is the first and best formalization of sliding-time-locks in function of block fee rates for Bitcoin I'm aware off, to the best of my knowledge.
>
> Here my understanding of the feerate-dependent timelock proposal.
>
> A transaction cannot be included in a block:
> - height-based or epoch-based absolute or relative timelocks are not satisfied according to current consensus rules (bip68 and bip 113 and implementation details)
> - less than `block_count` has a block median-feerate above the median-feerate of the `window_size` period
>
> A median feerate is computed for each block.
> (This is unclear to me if this is the feerate for half of the block's weight or the median feerate with all weight units included in the block as the sample)
>
> From then, you have 3 parameters included in the nSequence field.
> - feerate_value_bound
> - window_size
> - block_count
>
> Those parameters can be selected by the transaction builder (and committed with a signature or hash chain-based covenant).
> As such, off-chain construction counterparties can select the feerate_value_bound at which their time-sensitive transaction confirmation will be delayed.
>
> E.g let's say you have a LN-penalty Alice-Bob channel. Second-stage HTLC transactions are pre-signed with feerate_value_bound at 100 sat / vbytes.
> The window_size selected is 100 blocks and the block_count is 70 (this guarantees tampering-robustness of the feerate_value_bound in face of miners coalitions).
>
> There is 1 BTC offered HTLC pending with expiration time T, from Alice to Bob.
>
> If at time T, the per-block median feerate of at least 70 blocks over the latest 100 block is above 100 sat / vbytes, any Alice's HTLC-timeout or Bob's HTLC-preimage cannot be included in the chain.
>
> From my understanding, Feerate-Dependent Timelocks effectively constitute the lineaments of a solution to the "Forced Expiration Spam" as described in the LN paper.
>
> I think you have few design caveats to be aware off:
> - for current LN-penalty, the revokeable scripts should be modified to ensure the CSV opcode inspect the enforcement of FDT's parameters, as those revokeable scripts are committed by all parties
> - there should be a delay period at the advantage of one party otherwise you still a feerate-race if the revocation bip68 timelock has expired during the FDT delay
>
> As such, I believe the FDT parameters should be enriched with another parameter : `claim_grace_period`, a new type of relative timelock of which the endpoint should be the `feerate_value_bound` itself.
>
> I think it works in terms of consensus chain state, validation resources and reorg-safety are all the parameters that are self-contained in the spent FDT-encumbered transaction itself.
> If the per-block feerate fluctuates, the validity of the ulterior FDT-locked transactions changes too, though this is already the case with timelock-encumbered transactions.
>
> (One corollary for Lightning, it sounds like all the channels carrying on a HTLC along a payment path should have the same FDT-parameters to avoid off-chain HTLC double-spend, a risk not clearly articulated in the LN paper).
>
> Given the one more additional parameter `claim_grace_period`, I think it would be wiser design to move all the FDT parameters in the bip341 annex.
> There is more free bits room there and additionally you can have different FDT parameters for each of your HTLC outputs in a single LN transaction, if combined with future covenant mechanisms like HTLC aggregation [3].
> (The current annex design draft has been designed among others to enable such "block-feerate-lock-point" [4] [5])
>
> I cannot assert that the FDT proposal makes the timeout-tree protocol more efficient than state-of-the-art channel factories and payment pool constructions.
> Still from my understanding, all those constructions are sharing frailties in face of blockchain congestion and they would need something like FDT.
>
> I'm truly rejoicing at the idea that we have now the start of a proposal solving one of the most imperative issues of Lightning and other time-sensitive use-cases.
> (Note, I've not reviewed the analysis and game-theory in the face of miners collusion / coalition, as I think the introduction of a `claim_grace_period` is modifying the fundamentals).
>
> Best,
> Antoine
>
> [0]
> https://fc22.ifca.ai/preproceedings/119.pdf
> [1]
> https://github.com/ariard/bitcoin-contracting-primitives-wg/blob/main/meetings/meetings-18-04.md
> [2]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-November/022180.html
> [3]
> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-October/022093.html
> [4]
> https://github.com/bitcoin-inquisition/bitcoin/pull/9
>
> [5]
> https://github.com/bitcoin/bips/pull/1381
>
> Le ven. 15 déc. 2023 à 09:20, jlspc via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> a écrit :
>
>> TL;DR
>> =====
>> * All known Lightning channel and factory protocols are susceptible to forced expiration spam attacks, in which an attacker floods the blockchain with transactions in order to prevent honest users from putting their transactions onchain before timelocks expire.
>> * Feerate-Dependent Timelocks (FDTs) are timelocks that automatically extend when blockchain feerates spike.
>>   - In the normal case, there's no spike in feerates and thus no tradeoff between capital efficiency and safety.
>>   - If a dishonest user attempts a forced expiration spam attack, feerates increase and FDTs are extended, thus penalizing the attacker by keeping their capital timelocked for longer.
>>   - FDTs are tunable and can be made to be highly resistant to attacks from dishonest miners.
>> * Of separate interest, an exact analysis of the risk of double spend attacks is presented that corrects an error in the original Bitcoin whitepaper.
>>
>> Overview
>> ========
>>
>> Because the Lightning protocol relies on timelocks to establish the correct channel state, Lightning users could lose their funds if they're unable to put their transactions onchain quickly enough.
>> The original Lightning paper [1] states that "[f]orced expiration of many transactions may be the greatest systemic risk when using the Lightning Network" and it uses the term "forced expiration spam" for an attack in which a malicious party "creates many channels and forces them all to expire at once", thus allowing timelocked transactions to become valid.
>> That paper also says that the creation of a credible threat against "spamming the blockchain to encourage transactions to timeout" is "imperative" [1].
>>
>> Channel factories that create multiple Lightning channels with a single onchain transaction [2][3][4][5] increase this risk in two ways.
>> First, factories allow more channels to be created, thus increasing the potential for many channels to require onchain transactions at the same time.
>> Second, channel factories themselves use timelocks, and thus are vulnerable to a "forced expiration spam" attack.
>>
>> In fact, the timelocks in Lightning channels and factories are risky even without an attack from a malicious party.
>> Blockchain congestion is highly variable and new applications (such as ordinals) can cause a sudden spike in congestion at any time.
>> As a result, timelocks that were set when congestion was low can be too short when congestion spikes.
>> Even worse, a spike in congestion could be self-reinforcing if it causes malicious parties to attack opportunistically and honest parties to put their channels onchain due to the heightened risk.
>>
>> One way to reduce the risk of a

[-- Attachment #2: Type: text/html, Size: 22871 bytes --]

Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[Eric Voskuil]

[-- Attachment #1: Type: text/html, Size: 23748 bytes --]

Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[jlspc]

[-- Attachment #1: Type: text/plain, Size: 21536 bytes --]

Hi Eric,

I agree that users can pay miners offchain and miners can create blocks where the difference between inputs and outputs exceeds the fees paid (by mining their own transactions). I model that behavior as dishonest mining. Onchain fees seem to reflect congestion for now, but it's true that FDTs rely on having a sufficient fraction of honest miners.

Regards,
John

Sent with [Proton Mail](https://proton.me/) secure email.

On Friday, December 22nd, 2023 at 8:09 PM, Eric Voskuil <eric@voskuil.org> wrote:

> The fees paid to mine the set of transactions in a given block are known only to the miner that produced the block. Assuming that tx inputs less outputs represents an actual economic force is an error.
>
> e
>
>> On Dec 22, 2023, at 09:24, jlspc via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>> 
>>
>> Hi Antoine,
>>
>> Thanks for your thoughtful response.
>>
>> Comments inline below:
>>
>>> Hi John,
>>
>>> While the idea of using sliding reaction window for blockchain congestion
>>> detection has been present in the "smart contract" space at large [0] and
>>> this has been discussed informally among Lightning devs and covenant
>>> designers few times [1] [2], this is the first and best formalization of
>>> sliding-time-locks in function of block fee rates for Bitcoin I'm aware
>>> off, to the best of my knowledge.
>>
>> Thanks!
>>
>>> Here my understanding of the feerate-dependent timelock proposal.
>>
>>> A transaction cannot be included in a block:
>>> - height-based or epoch-based absolute or relative timelocks are not
>>> satisfied according to current consensus rules (bip68 and bip 113 and
>>> implementation details)
>>> - less than `block_count` has a block median-feerate above the
>>> median-feerate of the `window_size` period
>>
>> It's a little bit different from that.
>> The transaction cannot be included in the blockchain until after an aligned window W of window_size blocks where:
>> 1) W starts no sooner than when the height-based or epoch-based absolute and/or relative timelocks have been satisfied, and
>> 2) W contains fewer than block_count blocks with median feerate greater than feerate_value_bound.
>>
>> Note that the aligned window cannot start until the absolute and/or relative timelocks have been satisfied and the transaction itself has to come after the aligned window.
>> However, once such an aligned window exists in the blockchain, the transaction can appear at any later time (and not just within a window that itself meets the block_count and feerate_value_bound limitations).
>>
>>> A median feerate is computed for each block.
>>> (This is unclear to me if this is the feerate for half of the block's
>>> weight or the median feerate with all weight units included in the
>>> block as the sample)
>>
>> A feerate F is the median feerate of a block B if F is the largest feerate such that the total size of the transactions in B with feerate greater or equal to F is at least 2 million vbytes.
>>
>>> From then, you have 3 parameters included in the nSequence field.
>>> - feerate_value_bound
>>> - window_size
>>> - block_count
>>
>>> Those parameters can be selected by the transaction builder (and
>>> committed with a signature or hash chain-based covenant).
>>> As such, off-chain construction counterparties can select the
>>> feerate_value_bound at which their time-sensitive transaction
>>> confirmation will be delayed.
>>
>>> E.g let's say you have a LN-penalty Alice-Bob channel. Second-stage
>>> HTLC transactions are pre-signed with feerate_value_bound at 100 sat /
>>> vbytes.
>>> The window_size selected is 100 blocks and the block_count is 70 (this
>>> guarantees tampering-robustness of the feerate_value_bound in face of
>>> miners coalitions).
>>
>>> There is 1 BTC offered HTLC pending with expiration time T, from Alice to Bob.
>>
>>> If at time T, the per-block median feerate of at least 70 blocks over
>>> the latest 100 block is above 100 sat / vbytes, any Alice's
>>> HTLC-timeout or Bob's HTLC-preimage cannot be included in the chain.
>>
>> The rules are actually:
>> 1) wait until time T, then
>> 2) wait until the start of a full aligned window W with 100 consecutive blocks that starts no earlier than T and that has fewer than 70 blocks with median feerate above 100 sats/vbyte.
>> (The values 100, 70, and 100 cannot actually be selected in the implementation in the paper, but that's a technical detail and could be changed if the FDT is specified in the annex, as you propose.)
>>
>>> From my understanding, Feerate-Dependent Timelocks effectively
>>> constitute the lineaments of a solution to the "Forced Expiration
>>> Spam" as described in the LN paper.
>>
>> Great!
>>
>>> I think you have few design caveats to be aware off:
>>> - for current LN-penalty, the revokeable scripts should be modified to
>>> ensure the CSV opcode inspect the enforcement of FDT's parameters, as
>>> those revokeable scripts are committed by all parties
>>
>> Yes, definitely.
>>
>>> - there should be a delay period at the advantage of one party
>>> otherwise you still a feerate-race if the revocation bip68 timelock
>>> has expired during the FDT delay
>>
>>> As such, I believe the FDT parameters should be enriched with another
>>> parameter : `claim_grace_period`, a new type of relative timelock of
>>> which the endpoint should be the `feerate_value_bound` itself.
>>
>> I'm not sure I'm following your proposal.
>> Are you suggesting that the transaction with the FDT has to wait an additional claim_grace_period in order to allow conflicting transactions from the other party to win the race?
>> For example, assume the HTLC-success transaction has a higher feerate than the feerate_value_bound, and the conflicting HTLC-timeout transaction has an FDT with the feerate_value_bound (and suitable window_size and block_count parameters to defend against miner attacks).
>> In this case, is the worry that the HTLC-success and HTLC-timeout transactions could both be delayed until there is a window W that meets the FDT's feerate_value_bound, window_size and block_count parameters, at which point they would race against each other and either could win?
>> Is the reason to delay the HTLC-timeout by an additional claim_grace_period to guarantee that the HTLC-success transaction will win the race?
>> If so, I don't think it's needed, given the exact definition of the FDT proposal.
>> This is because *during* the window W that meets the FDT's requirements, the HTLC-success transaction should get mined into one of the blocks in W that has a median feerate no larger than feerate_value_bound, assuming honest miners.
>> The assumption of honest miners is resolved by setting the window_size and block_count parameters appropriately.
>> Does that make sense?
>>
>>> I think it works in terms of consensus chain state, validation
>>> resources and reorg-safety are all the parameters that are
>>> self-contained in the spent FDT-encumbered transaction itself.
>>> If the per-block feerate fluctuates, the validity of the ulterior
>>> FDT-locked transactions changes too, though this is already the case
>>> with timelock-encumbered transactions.
>>
>>> (One corollary for Lightning, it sounds like all the channels carrying
>>> on a HTLC along a payment path should have the same FDT-parameters to
>>> avoid off-chain HTLC double-spend, a risk not clearly articulated in
>>> the LN paper).
>>
>> It's interesting that you focused on securing HTLCs, as I was focused on securing LN channel state (e.g., getting the right Commitment tx) and factory state.
>> The challenge with using FDTs to secure HTLCs is that you need a way to specify a sequence of FDTs (corresponding to the hops in a LN payment) that expire with enough time between them and with a low feerate period between them.
>> For example, consider a payment with n hops, where hop i has an HTLC that expires at time T_i, and where hop n is the last hop.
>> Without FDTs, one would select expiries such that T_i + cltv_expiry_delta_i < T_(i-1).
>> With FDTs, one can't just use the same T_i's and add an FDT that follows that T_i, because the feerate could be high until well after the first few T_i's are reached.
>> For example, assume T_n, T_(n-1) and T_(n-2) all occur before feerates fall below the feerate_value_bound.
>> In this case, the HTLC-timeout TXs for hops n, n-1 and n-2 would all be delayed until the feerates fell, and then they would all be able to be put onchain at the same time (without the required cltv_expiry_deltas between them).
>>
>> One attempt to solve this would be to add another parameter that specifies how many blocks to wait after fees have falled below the feerate_value_bound (like the claim_grace_perid, if I understand it correctly).
>> However, that doesn't solve the problem because the congestion could start, and the feerate_value_bound could be exceeded, at any time.
>> For example, the feerate_value_bound could first be exceeded just after T_(n-1), in which case the fees would be too high to put the HTLC-success transaction onchain in hop T_(n-2).
>>
>> What we really need is the ability to ensure that there have been enough low feerate expiries, each separated by the required cltv_expiry_delta.
>> This can be achieved by adding a new parameter, number_of_windows, that specifies how many low feerate windows W_1, W_2, etc., are required, all of which meet the feerate_value_bound, window_size and block_count parameters (and all of which start no later than when the standard absolute and relative timelocks have been satisfied).
>> With this new parameter, lower numbered hops (closer to the sender) can use larger values of number_of_windows in order to guarantee low feerate periods that meet the required cltv_expiry_deltas.
>>
>> For example, assume feerate_value_bound is 256 sats/vbyte, window_size is 256, and block_count is 64.
>> Then, give the HTLC-timeout transaction in hop i an absolute timelock of T_n (the timelock for hop n) and an FDT with number_of_windows equal to (n-i+1) (and with feerate_value_bound, window_size and block_count as above).
>> In this case, as long as each cltv_expiry_delta is less than window_size - block_count = 192, then in each hop the party offered the HTLC can put their HTLC-success transaction onchain in a low feerate block after they have seen the hash preimage for at least cltv_expiry_delta blocks.
>> (In practice, the parameters could be tweaked a bit to break the association between hops, such as by using more restrictive feerate_value_bounds and/or block_counts as one gets closer to the source, and by increasing the number_of_windows parameter by more than one per hop as one gets closer to the source.)
>>
>>> Given the one more additional parameter `claim_grace_period`, I think
>>> it would be wiser design to move all the FDT parameters in the bip341
>>> annex.
>>> There is more free bits room there and additionally you can have
>>> different FDT parameters for each of your HTLC outputs in a single LN
>>> transaction, if combined with future covenant mechanisms like HTLC
>>> aggregation [3].
>>> (The current annex design draft has been designed among others to
>>> enable such "block-feerate-lock-point" [4] [5])
>>
>> I like your idea of putting the FDT parameters in the annex.
>> This is required if we add the number_of_windows parameter that I mentioned above.
>>
>> In addition to finding enough bits in the transaction to hold the FDT parameters, there is a cost to increasing the parameters, namely the memory required to verify transactions with FDTs.
>> In the proposal in the paper, FDTs could be specified with 14 bits, so there were only 2^14 = 16k different values for which the starting block of the most recent aligned window satisfying those parameters has to be stored in order to quickly verify FDTs.
>> Assuming 4 bytes to store the starting block of a window, that's just 64k bytes of DRAM.
>> If we add a 6-bit number_of_windows parameter, that increases the storage by a factor of 64 to 4MB.
>> That's still pretty small, but we have to be careful to not make this too expensive.
>>
>>> I cannot assert that the FDT proposal makes the timeout-tree protocol
>>> more efficient than state-of-the-art channel factories and payment
>>> pool constructions.
>>> Still from my understanding, all those constructions are sharing
>>> frailties in face of blockchain congestion and they would need
>>> something like FDT.
>>
>> I agree that FDTs don't make timeout-trees more competitive against any other factory protoocol.
>> I also agree that FDTs can be used to make all of the LN channel and factory protocools safer.
>> If we extend the idea to include a number_of_windows parameter, then we should even be able to make HTLCs safer.
>>
>>> I'm truly rejoicing at the idea that we have now the start of a
>>> proposal solving one of the most imperative issues of Lightning and
>>> other time-sensitive use-cases.
>>
>> I'm very happy you see it that way.
>> Please let me know what you think of the number_of_windows idea, and if you have any other ideas for making HTLCs safer.
>>
>> Regards,
>> John
>>
>> Sent with [Proton Mail](https://proton.me/) secure email.
>>
>> On Sunday, December 17th, 2023 at 3:01 PM, Antoine Riard <antoine.riard@gmail.com> wrote:
>>
>>> Hi John,
>>>
>>> While the idea of using sliding reaction window for blockchain congestion detection has been present in the "smart contract" space at large [0] and this has been discussed informally among Lightning devs and covenant designers few times [1] [2], this is the first and best formalization of sliding-time-locks in function of block fee rates for Bitcoin I'm aware off, to the best of my knowledge.
>>>
>>> Here my understanding of the feerate-dependent timelock proposal.
>>>
>>> A transaction cannot be included in a block:
>>> - height-based or epoch-based absolute or relative timelocks are not satisfied according to current consensus rules (bip68 and bip 113 and implementation details)
>>> - less than `block_count` has a block median-feerate above the median-feerate of the `window_size` period
>>>
>>> A median feerate is computed for each block.
>>> (This is unclear to me if this is the feerate for half of the block's weight or the median feerate with all weight units included in the block as the sample)
>>>
>>> From then, you have 3 parameters included in the nSequence field.
>>> - feerate_value_bound
>>> - window_size
>>> - block_count
>>>
>>> Those parameters can be selected by the transaction builder (and committed with a signature or hash chain-based covenant).
>>> As such, off-chain construction counterparties can select the feerate_value_bound at which their time-sensitive transaction confirmation will be delayed.
>>>
>>> E.g let's say you have a LN-penalty Alice-Bob channel. Second-stage HTLC transactions are pre-signed with feerate_value_bound at 100 sat / vbytes.
>>> The window_size selected is 100 blocks and the block_count is 70 (this guarantees tampering-robustness of the feerate_value_bound in face of miners coalitions).
>>>
>>> There is 1 BTC offered HTLC pending with expiration time T, from Alice to Bob.
>>>
>>> If at time T, the per-block median feerate of at least 70 blocks over the latest 100 block is above 100 sat / vbytes, any Alice's HTLC-timeout or Bob's HTLC-preimage cannot be included in the chain.
>>>
>>> From my understanding, Feerate-Dependent Timelocks effectively constitute the lineaments of a solution to the "Forced Expiration Spam" as described in the LN paper.
>>>
>>> I think you have few design caveats to be aware off:
>>> - for current LN-penalty, the revokeable scripts should be modified to ensure the CSV opcode inspect the enforcement of FDT's parameters, as those revokeable scripts are committed by all parties
>>> - there should be a delay period at the advantage of one party otherwise you still a feerate-race if the revocation bip68 timelock has expired during the FDT delay
>>>
>>> As such, I believe the FDT parameters should be enriched with another parameter : `claim_grace_period`, a new type of relative timelock of which the endpoint should be the `feerate_value_bound` itself.
>>>
>>> I think it works in terms of consensus chain state, validation resources and reorg-safety are all the parameters that are self-contained in the spent FDT-encumbered transaction itself.
>>> If the per-block feerate fluctuates, the validity of the ulterior FDT-locked transactions changes too, though this is already the case with timelock-encumbered transactions.
>>>
>>> (One corollary for Lightning, it sounds like all the channels carrying on a HTLC along a payment path should have the same FDT-parameters to avoid off-chain HTLC double-spend, a risk not clearly articulated in the LN paper).
>>>
>>> Given the one more additional parameter `claim_grace_period`, I think it would be wiser design to move all the FDT parameters in the bip341 annex.
>>> There is more free bits room there and additionally you can have different FDT parameters for each of your HTLC outputs in a single LN transaction, if combined with future covenant mechanisms like HTLC aggregation [3].
>>> (The current annex design draft has been designed among others to enable such "block-feerate-lock-point" [4] [5])
>>>
>>> I cannot assert that the FDT proposal makes the timeout-tree protocol more efficient than state-of-the-art channel factories and payment pool constructions.
>>> Still from my understanding, all those constructions are sharing frailties in face of blockchain congestion and they would need something like FDT.
>>>
>>> I'm truly rejoicing at the idea that we have now the start of a proposal solving one of the most imperative issues of Lightning and other time-sensitive use-cases.
>>> (Note, I've not reviewed the analysis and game-theory in the face of miners collusion / coalition, as I think the introduction of a `claim_grace_period` is modifying the fundamentals).
>>>
>>> Best,
>>> Antoine
>>>
>>> [0]
>>> https://fc22.ifca.ai/preproceedings/119.pdf
>>> [1]
>>> https://github.com/ariard/bitcoin-contracting-primitives-wg/blob/main/meetings/meetings-18-04.md
>>> [2]
>>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-November/022180.html
>>> [3]
>>> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-October/022093.html
>>> [4]
>>> https://github.com/bitcoin-inquisition/bitcoin/pull/9
>>>
>>> [5]
>>> https://github.com/bitcoin/bips/pull/1381
>>>
>>> Le ven. 15 déc. 2023 à 09:20, jlspc via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> a écrit :
>>>
>>>> TL;DR
>>>> =====
>>>> * All known Lightning channel and factory protocols are susceptible to forced expiration spam attacks, in which an attacker floods the blockchain with transactions in order to prevent honest users from putting their transactions onchain before timelocks expire.
>>>> * Feerate-Dependent Timelocks (FDTs) are timelocks that automatically extend when blockchain feerates spike.
>>>>   - In the normal case, there's no spike in feerates and thus no tradeoff between capital efficiency and safety.
>>>>   - If a dishonest user attempts a forced expiration spam attack, feerates increase and FDTs are extended, thus penalizing the attacker by keeping their capital timelocked for longer.
>>>>   - FDTs are tunable and can be made to be highly resistant to attacks from dishonest miners.
>>>> * Of separate interest, an exact analysis of the risk of double spend attacks is presented that corrects an error in the original Bitcoin whitepaper.
>>>>
>>>> Overview
>>>> ========
>>>>
>>>> Because the Lightning protocol relies on timelocks to establish the correct channel state, Lightning users could lose their funds if they're unable to put their transactions onchain quickly enough.
>>>> The original Lightning paper [1] states that "[f]orced expiration of many transactions may be the greatest systemic risk when using the Lightning Network" and it uses the term "forced expiration spam" for an attack in which a malicious party "creates many channels and forces them all to expire at once", thus allowing timelocked transactions to become valid.
>>>> That paper also says that the creation of a credible threat against "spamming the blockchain to encourage transactions to timeout" is "imperative" [1].
>>>>
>>>> Channel factories that create multiple Lightning channels with a single onchain transaction [2][3][4][5] increase this risk in two ways.
>>>> First, factories allow more channels to be created, thus increasing the potential for many channels to require onchain transactions at the same time.
>>>> Second, channel factories themselves use timelocks, and thus are vulnerable to a "forced expiration spam" attack.
>>>>
>>>> In fact, the timelocks in Lightning channels and factories are risky even without an attack from a malicious party.
>>>> Blockchain congestion is highly variable and new applications (such as ordinals) can cause a sudden spike in congestion at any time.
>>>> As a result, timelocks that were set when congestion was low can be too short when congestion spikes.
>>>> Even worse, a spike in congestion could be self-reinforcing if it causes malicious parties to attack opportunistically and honest parties to put their channels onchain due to the heightened risk.
>>>>
>>>> One way to reduce the risk of a
>>
>> _______________________________________________
>> bitcoin-dev mailing list
>> bitcoin-dev@lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev

[-- Attachment #2: Type: text/html, Size: 25225 bytes --]

Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[Eric Voskuil]

[-- Attachment #1: Type: text/html, Size: 26082 bytes --]

Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[David A. Harding]

On 2023-12-28 08:42, Eric Voskuil via bitcoin-dev wrote:
> Assuming a “sufficient fraction” of
> one of several economically rational behaviors is a design flaw.

The amount of effort it takes a user to pay additional miners out of
band is likely to increase much faster than probability that the user's
payment will confirm on time.  For example, offering payment to the set
of miners that controls 90% of hash rate will result in confirmation
within 6 blocks 99.9999% of the time, meaning it's probably not worth
putting any effort into offering payment to the other 10% of miners.  If
out of band payments become a significant portion of mining revenue via
a mechanism that results in small miners making significantly less
revenue than large miners, there will be an incentive to centralize
mining even more than it is today.  The more centralized mining is, the
less resistant Bitcoin is to transaction censorship.

We can't prevent people from paying out of band, but we can ensure that
the easiest and most effective way to pay for a transaction is through
in-band fees and transactions that are relayed to every miner who is
interested in them.  If we fail at that, I think Bitcoin losing its
censorship resistance will be inevitable.  LN, coinpools, and channel
factories all strongly depend on Bitcoin transactions not being
censored, so I don't think any security is lost by redesigning them to
additionally depend on reasonably accurate in-band fee statistics.

Miners mining their own transactions, accepting the occasional
out-of-band fee, or having varying local transaction selection policies
are situations that are easily addressed by the user of fee-dependent
timelocks choosing a long window and setting the dependent feerate well
below the maximum feerate they are willing to pay.

-Dave

Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[Nagaev Boris]

Hey David!

On Fri, Dec 29, 2023 at 9:37 PM David A. Harding via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> We can't prevent people from paying out of band, but we can ensure that
> the easiest and most effective way to pay for a transaction is through
> in-band fees and transactions that are relayed to every miner who is
> interested in them.  If we fail at that, I think Bitcoin losing its
> censorship resistance will be inevitable.  LN, coinpools, and channel
> factories all strongly depend on Bitcoin transactions not being
> censored, so I don't think any security is lost by redesigning them to
> additionally depend on reasonably accurate in-band fee statistics.

Feerate-Dependent Timelocks do create incentives to accept out-of-band
fees to decrease in-band fees and speed up mining of transactions
using FDT! Miners can make a 5% discount on fees paid out-of-band and
many people will use it. Observed fees decrease and FDT transactions
mature faster. It is beneficial for both parties involved: senders of
transactions save 5% on fees, miners get FDT transactions mined faster
and get more profits (for the sake of example more than 5%).

-- 
Best regards,
Boris Nagaev

Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[David A. Harding]

On 2023-12-29 15:17, Nagaev Boris wrote:
> Feerate-Dependent Timelocks do create incentives to accept out-of-band
> fees to decrease in-band fees and speed up mining of transactions
> using FDT! Miners can make a 5% discount on fees paid out-of-band and
> many people will use it. Observed fees decrease and FDT transactions
> mature faster. It is beneficial for both parties involved: senders of
> transactions save 5% on fees, miners get FDT transactions mined faster
> and get more profits (for the sake of example more than 5%).

Hi Nagaev,

That's an interesting idea, but I don't think that it works due to the 
free rider problem: miner Alice offers a 5% discount on fees paid out of 
band now in the hopes of collecting more than 5% in extra fees later due 
to increased urgency from users that depended on FDTs.  However, 
sometimes the person who actually collects extra fees is miner Bob who 
never offered a 5% discount.  By not offering a discount, Bob earns more 
money on average per block than Alice (all other things being equal), 
eventually forcing her to stop offering the discount or to leave the 
market.

Additionally, if nearly everyone was paying discounted fees out of band, 
participants in contract protocols using FDTs would know to use 
proportionally higher FDT amounts (e.g. 5% over their actual desired 
fee), negating the benefit to miners of offering discounted fees.

-Dave

Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[Nagaev Boris]

On Sat, Dec 30, 2023 at 12:11 AM David A. Harding <dave@dtrt.org> wrote:
>
> On 2023-12-29 15:17, Nagaev Boris wrote:
> > Feerate-Dependent Timelocks do create incentives to accept out-of-band
> > fees to decrease in-band fees and speed up mining of transactions
> > using FDT! Miners can make a 5% discount on fees paid out-of-band and
> > many people will use it. Observed fees decrease and FDT transactions
> > mature faster. It is beneficial for both parties involved: senders of
> > transactions save 5% on fees, miners get FDT transactions mined faster
> > and get more profits (for the sake of example more than 5%).
>
> Hi Nagaev,
>
> That's an interesting idea, but I don't think that it works due to the
> free rider problem: miner Alice offers a 5% discount on fees paid out of
> band now in the hopes of collecting more than 5% in extra fees later due
> to increased urgency from users that depended on FDTs.  However,
> sometimes the person who actually collects extra fees is miner Bob who
> never offered a 5% discount.  By not offering a discount, Bob earns more
> money on average per block than Alice (all other things being equal),
> eventually forcing her to stop offering the discount or to leave the
> market.
>
> Additionally, if nearly everyone was paying discounted fees out of band,
> participants in contract protocols using FDTs would know to use
> proportionally higher FDT amounts (e.g. 5% over their actual desired
> fee), negating the benefit to miners of offering discounted fees.
>
> -Dave

Good points. It makes sense!

-- 
Best regards,
Boris Nagaev

Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[Nagaev Boris]

Hi John!

I have two questions regarding the window, which are related.

1. Why is the window aligned? IIUC, this means that the blocks mined
since the latest block whose height is divisible by window_size do not
affect transaction's validity. So a recent change of fees does not
reflect if a transaction can be confirmed.

2. Does it make sense to have a global window_size? This would save
space in FDT (= in transaction) and simplify verification, especially
for a non-aligned window case (see 1). An array of integers of size
window_size would be sufficient to give answer to a question if there
were at least x blocks among window_size latest blocks with median fee
rate <= y, using O(1) time per query.

Moving on to another topic, what are the implications for light
clients? A light client can validate current timelocks without
downloading whole blocks, because they depend on timestamps and block
height only, the information from block headers. To validate a
transaction with FDT or to choose FDT parameters for its own
transaction, a light client would have to determine the median fee
rate of the recent blocks. To do that without involving trust, it has
to download the blocks. What do you think about including median
feerate as a required OP_RETURN output in coinbase transaction? A
block without it would be invalid (new consensus rule). A light client
can rely on median feerate value from coinbase transaction,
downloading only one tx instead of the whole block.

On Fri, Dec 15, 2023 at 6:20 AM jlspc via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
> TL;DR
> =====
> * All known Lightning channel and factory protocols are susceptible to forced expiration spam attacks, in which an attacker floods the blockchain with transactions in order to prevent honest users from putting their transactions onchain before timelocks expire.
> * Feerate-Dependent Timelocks (FDTs) are timelocks that automatically extend when blockchain feerates spike.
>   - In the normal case, there's no spike in feerates and thus no tradeoff between capital efficiency and safety.
>   - If a dishonest user attempts a forced expiration spam attack, feerates increase and FDTs are extended, thus penalizing the attacker by keeping their capital timelocked for longer.
>   - FDTs are tunable and can be made to be highly resistant to attacks from dishonest miners.
> * Of separate interest, an exact analysis of the risk of double spend attacks is presented that corrects an error in the original Bitcoin whitepaper.
>
> Overview
> ========
>
> Because the Lightning protocol relies on timelocks to establish the correct channel state, Lightning users could lose their funds if they're unable to put their transactions onchain quickly enough.
> The original Lightning paper [1] states that "[f]orced expiration of many transactions may be the greatest systemic risk when using the Lightning Network" and it uses the term "forced expiration spam" for an attack in which a malicious party "creates many channels and forces them all to expire at once", thus allowing timelocked transactions to become valid.
> That paper also says that the creation of a credible threat against "spamming the blockchain to encourage transactions to timeout" is "imperative" [1].
>
> Channel factories that create multiple Lightning channels with a single onchain transaction [2][3][4][5] increase this risk in two ways.
> First, factories allow more channels to be created, thus increasing the potential for many channels to require onchain transactions at the same time.
> Second, channel factories themselves use timelocks, and thus are vulnerable to a "forced expiration spam" attack.
>
> In fact, the timelocks in Lightning channels and factories are risky even without an attack from a malicious party.
> Blockchain congestion is highly variable and new applications (such as ordinals) can cause a sudden spike in congestion at any time.
> As a result, timelocks that were set when congestion was low can be too short when congestion spikes.
> Even worse, a spike in congestion could be self-reinforcing if it causes malicious parties to attack opportunistically and honest parties to put their channels onchain due to the heightened risk.
>
> One way to reduce the risk of a forced expiration spam attack is to use longer timelocks that give honest users more time to put their transactions onchain.
> However, long timelocks limit the ability to dynamically reassign the channel's (or factory's) funds, thus creating a tradeoff between capital efficiency and safety [6].
> While long timelocks could maintain safety for small numbers of channels, supporting billions (or tens of billions) of channels while maintaining safety is probably impossible [7].
>
> Another way to reduce risk is to impose a penalty on an attacker.
> Some channel protocols, such as the original Lightning protocol [1], a version of the two-party eltoo protocol [8], the fully-factory-optimized protocol [9], and the tunable-penalty channel protocol [10] include such penalties.
> In addition, the tunable-penalty and single-commitment factory protocols [4] support penalties.
> However, as was noted in the original Lightning paper [1], penalties don't eliminate the risk of a forced expiration spam attack.
> Furthermore, existing penalty-based factory protocols [4] have limited scalability, as they depend on getting large numbers of casual users to coordinate and co-sign transactions [11][5].
>
> In contrast, the timeout-tree protocol [5] scales via simple covenants (enabled by support for CheckTemplateVerify, AnyPrevOut, or a similar change to the Bitcoin consensus rules).
> As a result, a single timeout-tree can support millions of channels and one small transaction per block can fund timeout-trees with tens of billions of offchain channels [5].
> However, timeout-trees don't support penalties, and like all other known factory protocols [2][3][4], timeout-trees rely on timelocks.
>
> Therefore, if the need to protect against forced expiration spam was already "imperative" for the original Lightning channel protocol [1], the use of scalable channel factories will make such protection indispensable.
>
> This post proposes a change to Bitcoin's consensus rules that allows the length of a timelock to depend on the feerate being charged for putting transactions onchain.
> Such Feerate-Dependent Timelocks (FDTs) can be used to make the above channel and factory protocols resistant to sudden spikes in blockchain congestion.
> In the normal case, when there's no spike in congestion, FDTs don't extend the lengths of timelocks and thus don't create a tradeoff between capital efficiency and safety.
> On the other hand, when congestion spikes, FDTs extend the lengths of timelocks and thus penalize the owner of the timelocked capital by reducing its efficiency.
> Therefore, FDTs can be viewed as creating a penalty for spamming the blockchain, thus reducing the likelihood of such an attack even if the channel (or factory) protocol being used doesn't have an explicit penalty mechanism.
>
> FDTs have other uses, including reducing the risk of having to pay unexpectedly high fees during a congestion spike, improving the accuracy of fee-penalties [5] and reducing the risk of one-shot receives [12].
>
> Of separate interest, the analysis of FDTs given here leads to an exact analysis of the risk of double spend attacks that corrects an error in the original Bitcoin whitepaper [13].
>
> A more complete description and analysis of FDTs is given in a paper [14].
>
> Feerate-Dependent Timelock (FDT) Proposal
> =========================================
>
> A Feerate-Dependent Timelock (FDT) is created by encoding a feerate upper bound in a transaction's nSequence field.
> A transaction with an FDT cannot be put onchain until:
>   1) its absolute timelock encoded in its nLocktime field (and its relative timelock encoded in the same nSequence field, if present) has been satisfied, and
>   2) the prevailing feerate has fallen below the FDT's feerate upper bound.
> As a result, FDTs are automatically extended when the feerate for putting transactions onchain spikes (such as would occur during a forced expiration spam attack).
>
> In order to determine the prevailing feerate, the median feerate of each block is calculated as the feerate (in satoshis/vbyte) that is paid for at least half of the block's vbytes.
>
> If all miners were honest, a single block with a low median feerate would be enough to guarantee that congestion is low.
> However, even a small fraction of dishonest miners would be able to occasionally mine a block with an artificially low feerate.
> As a result, it isn't safe to wait for one block (or some other fixed number of blocks) with a low feerate in order to guarantee that honest users have had an opportunity to put their transactions onchain.
>
> Instead, an FDT requires that some maximum number of blocks within an aligned window of consecutive blocks have a high median feerate.
> The FDT proposal uses 14 currently masked-off bits in the nSequence field to express the FDT's three parameters:
>   * feerate_value,
>   * window_size, and
>   * block_count.
> An aligned window of window_size blocks satisfies the FDT's parameters if it has fewer than block_count blocks with median feerate above feerate_value.
> A transaction with an FDT can only be put onchain after an aligned window that satisfies the FDT's parameters and starts no earlier than when the transaction's absolute timelock (and corresponding relative timelock, if present) is satisfied.
>
> In addition, the CheckSequenceVerify (CSV) operator is extended to enforce the desired feerate_value, window_size and block_count.
> The details are given in the paper [14].
>
> Safe Lightning Channels And Factories
> =====================================
>
> In order to protect a channel or factory protocol against forced expiration spam attacks, the protocol's timelocks are made to be feerate-dependent.
> This is done by selecting a feerate_value (such as 4 times the current feerate) that would be caused by a forced expiration spam attack, along with the desired window_size and block_count parameters.
>
> It's also possible to create multiple conflicting transactions with different FDTs (with later timelocks allowing higher feerates) in order to avoid timelocks that will never expire if feerates remain high permanently.
>
> Other Uses
> ==========
>
> FDTs have uses in addition to protecting channel and factory protocols from forced expiration spam attacks.
>
> For example, FDTs can protect users that are racing against timelocks from having to pay an unexpectedly high feerate due to temporary feerate fluctuations [14].
> In addition, FDTs can be used to improve the accuracy of fee-penalties that are assessed when a casual user puts their timeout-tree leaf onchain [14](Section 4.10 of [5]).
> Finally, FDTs can be used to allow a casual user to submit a transaction to the blockchain without having to then monitor the blockchain for a sudden spike in feerates, thus reducing the risk of one-shot receives [14][12].
>
> Analysis
> ========
>
> FDT Implementation Cost
> -----------------------
> In order to verify an FDT, nodes have to determine whether or not there is an aligned window with a sufficient number of low-feerate blocks after the FDT's absolute timelock (and corresponding relative timelock, if present) is satisfied.
> Therefore, if a node knows the starting block of the most recent aligned window that satisfies the FDT's feerate_value, window_size, and block_count parameters, the node can compare that starting block with the FDT's timelocks to verify the FDT.
> Because the FDT parameters can be expressed using 14 bits, nodes only have to keep track of the starting block for 2^14 = 16k different low-feerate windows.
> The starting block for each such window can be stored in 4 bytes, so 16k * 4B = 64kB of memory allows a node to verify an FDT in constant time.
> (In practice, slightly more memory could be used in order to accommodate a reordering of the most recent 1k blocks.)
> Therefore, DRAM that costs less than one cent, plus a small constant number of computations, suffice to verify an FDT.
>
> FDT Dishonest Miner Attacks
> ---------------------------
> The window_size and block_count parameters can be selected to balance between:
>   1) latency,
>   2) the feerate paid by honest users, and
>   3) security against dishonest miners.
> At one extreme, if dishonest miners are of no concern, window_size and block_count can be set to 1, so the FDT can be satisfied when the first block with a sufficiently low feerate is mined.
> At the other extreme, if dishonest miners are of great concern, window_size can be set to 16k and block_count can be set to 1024, in which case dishonest miners with 45% of the hashpower would have less than a 10^-33 chance of dishonestly mining enough blocks in a given window to satisfy the FDT prior to the honest users being able to get their transactions onchain [14].
>
> Double Spend Attacks
> --------------------
> While it's unrelated to FDTs, the analysis of FDTs' resistance to dishonest miner attacks can also be used to analyze the risk of double spend attacks.
>
> The original Bitcoin whitepaper [13] includes an analysis of the probability of a double spend attack in which a dishonest party colludes with dishonest miners in order to undo a bitcoin transaction and steal the goods purchased with that transaction.
> That analysis correctly shows that the probability of success of a double spend attack falls exponentially with z, the depth of the transaction that's being double spent.
> However, there are two problems with that analysis:
>   1) it is approximate, and
>   2) it ignores the possibility of the dishonest miners using pre-mining.
>
> The first problem was addressed by Grunspan and Perez-Marco [15].
> However, it doesn't appear that the second problem has been addressed previously.
>
> Exact formulas for the risk of double spend attacks, including pre-mining, are given in the paper [14] and programs that implement those formulas are available on GitHub [16].
>
> The effect of including pre-mining only becomes apparent when a large fraction of the miners are dishonest.
> For example, Nakamoto estimates the required value of z to guarantee at most a 0.1% chance of a successful double spend, and Grunspan and Perez-Marco give exact values assuming no pre-mining.
> Those results, plus exact results with pre-mining, are as follows:
>
> % dishonest  Estimated z w/o      Exact z w/o       Exact z w/
>      miners  pre-mining [13]  pre-mining [15]  pre-mining [14]
> ===========  ===============  ===============  ===============
>          10                5                6                6
>          15                8                9                9
>          20               11               13               13
>          25               15               20               20
>          30               24               32               33
>          35               41               58               62
>          40               89              133              144
>          45              340              539              589
>
> It's important to note that the above results with pre-mining assume that the time of the double spend attack is not selected by the attacker.
> If the attacker can select when to perform the attack, they are guaranteed to succeed given any value of z, but the expected time required to perform the attack grows exponentially with z [14].
>
> Conclusions
> ===========
>
> Securing Lightning channels and channel factories against forced expiration spam attacks is imperative.
>
> Feerate-Dependent Timelocks (FDTs) provide this security without forcing the timelocks to be extended in the typical case, thus avoiding a capital efficiency vs. safety tradeoff.
> Furthermore, a dishonest user who tries to use a forced expiration spam attack to steal funds is penalized by having their funds timelocked for a longer period, thus discouraging such attacks.
> Finally, FDTs can be made to be highly resistant to attacks by dishonest miners.
>
> FDTs have other uses, including the reduction of feerate risk and the calculation of fee-penalties.
>
> While implementing FDTs requires some additional DRAM and computation, the costs are extremely small.
> Given these advantages and their low costs, it's hoped that the Bitcoin consensus rules will be changed to support FDTs.
>
> Regards,
> John
>
> [1] Poon and Dryja, The Bitcoin Lightning Network, https://lightning.network/lightning-network-paper.pdf
> [2] Burchert, Decker and Wattenhofer, "Scalable Funding of Bitcoin Micropayment Channel Networks", http://dx.doi.org/10.1098/rsos.180089
> [3] Decker, Russell and Osuntokun. "eltoo: A Simple Layer2 Protocol for Bitcoin", https://blockstream.com/eltoo.pdf
> [4] Law, "Efficient Factories For Lightning Channels", https://github.com/JohnLaw2/ln-efficient-factories
> [5] Law, "Scaling Lightning With Simple Covenants", https://github.com/JohnLaw2/ln-scaling-covenants
> [6] Towns, "Re: Scaling Lightning With Simple Covenants", https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-September/021943.html
> [7] Law, "Re: Scaling Lightning With Simple Covenants", https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-November/022175.html
> [8] Towns, "Two-party eltoo w/ punishment", https://lists.linuxfoundation.org/pipermail/lightning-dev/2022-December/003788.html
> [9] Law, "Factory-Optimized Channel Protocols For Lightning", https://github.com/JohnLaw2/ln-factory-optimized
> [10] Law, "Lightning Channels With Tunable Penalties", https://github.com/JohnLaw2/ln-tunable-penalties
> [11] Riard, "Solving CoinPool high-interactivity issue with cut-through update of Taproot leaves", https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-September/021969.html
> [12] Law, "Watchtower-Free Lightning Channels For Casual Users", https://github.com/JohnLaw2/ln-watchtower-free
> [13] Nakamoto. "Bitcoin: A Peer-to-Peer Electronic Cash System", http://bitcoin.org/bitcoin.pdf
> [14] Law, "Scaling Lightning Safely With Feerate-Dependent Timelocks", https://github.com/JohnLaw2/ln-fdts
> [15] Grunspan and Perez-Marco, "Double Spend Races", CoRR, vol. abs/1702.02867, http://arxiv.org/abs/1702.02867v3
> [16] Law, https://github.com/JohnLaw2/ln-fdts
>
>
>
>
> Sent with Proton Mail secure email.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev



-- 
Best regards,
Boris Nagaev

Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[jlspc]

Hi Boris,

Responses inline below:


Sent with Proton Mail secure email.

On Friday, December 22nd, 2023 at 8:36 AM, Nagaev Boris <bnagaev@gmail.com> wrote:


> Hi John!
> 
> I have two questions regarding the window, which are related.
> 
> 1. Why is the window aligned? IIUC, this means that the blocks mined
> since the latest block whose height is divisible by window_size do not
> affect transaction's validity. So a recent change of fees does not
> reflect if a transaction can be confirmed.

FDTs are not based on the most recent window; instead, an FDT requires that there exist *some* aligned window between when the child transaction's absolute and relative timelocks were satisfied and the current block. The alignment requirement allows one to prove tighter security bounds over a given time period. For example, 2 consecutive aligned 64-block windows give dishonest miners 2 chances to create artificial aligned low-feerate windows, but 65 chances to create such windows if alignment isn't required.

> 
> 2. Does it make sense to have a global window_size? This would save
> space in FDT (= in transaction) and simplify verification, especially
> for a non-aligned window case (see 1). An array of integers of size
> window_size would be sufficient to give answer to a question if there
> were at least x blocks among window_size latest blocks with median fee
> rate <= y, using O(1) time per query.
> 

The ability to tune the window size allows for a trade-off between latency and security (also, see my response above about alignment). 

> Moving on to another topic, what are the implications for light
> clients? A light client can validate current timelocks without
> downloading whole blocks, because they depend on timestamps and block
> height only, the information from block headers. To validate a
> transaction with FDT or to choose FDT parameters for its own
> transaction, a light client would have to determine the median fee
> rate of the recent blocks. To do that without involving trust, it has
> to download the blocks. What do you think about including median
> feerate as a required OP_RETURN output in coinbase transaction? A
> block without it would be invalid (new consensus rule). A light client
> can rely on median feerate value from coinbase transaction,
> downloading only one tx instead of the whole block.

Yes, I think that's a great idea!

Regards,
John

> 
> On Fri, Dec 15, 2023 at 6:20 AM jlspc via bitcoin-dev
> bitcoin-dev@lists.linuxfoundation.org wrote:
> 
> > TL;DR
> > =====
> > * All known Lightning channel and factory protocols are susceptible to forced expiration spam attacks, in which an attacker floods the blockchain with transactions in order to prevent honest users from putting their transactions onchain before timelocks expire.
> > * Feerate-Dependent Timelocks (FDTs) are timelocks that automatically extend when blockchain feerates spike.
> > - In the normal case, there's no spike in feerates and thus no tradeoff between capital efficiency and safety.
> > - If a dishonest user attempts a forced expiration spam attack, feerates increase and FDTs are extended, thus penalizing the attacker by keeping their capital timelocked for longer.
> > - FDTs are tunable and can be made to be highly resistant to attacks from dishonest miners.
> > * Of separate interest, an exact analysis of the risk of double spend attacks is presented that corrects an error in the original Bitcoin whitepaper.
> > 
> > Overview
> > ========
> > 
> > Because the Lightning protocol relies on timelocks to establish the correct channel state, Lightning users could lose their funds if they're unable to put their transactions onchain quickly enough.
> > The original Lightning paper [1] states that "[f]orced expiration of many transactions may be the greatest systemic risk when using the Lightning Network" and it uses the term "forced expiration spam" for an attack in which a malicious party "creates many channels and forces them all to expire at once", thus allowing timelocked transactions to become valid.
> > That paper also says that the creation of a credible threat against "spamming the blockchain to encourage transactions to timeout" is "imperative" [1].
> > 
> > Channel factories that create multiple Lightning channels with a single onchain transaction [2][3][4][5] increase this risk in two ways.
> > First, factories allow more channels to be created, thus increasing the potential for many channels to require onchain transactions at the same time.
> > Second, channel factories themselves use timelocks, and thus are vulnerable to a "forced expiration spam" attack.
> > 
> > In fact, the timelocks in Lightning channels and factories are risky even without an attack from a malicious party.
> > Blockchain congestion is highly variable and new applications (such as ordinals) can cause a sudden spike in congestion at any time.
> > As a result, timelocks that were set when congestion was low can be too short when congestion spikes.
> > Even worse, a spike in congestion could be self-reinforcing if it causes malicious parties to attack opportunistically and honest parties to put their channels onchain due to the heightened risk.
> > 
> > One way to reduce the risk of a forced expiration spam attack is to use longer timelocks that give honest users more time to put their transactions onchain.
> > However, long timelocks limit the ability to dynamically reassign the channel's (or factory's) funds, thus creating a tradeoff between capital efficiency and safety [6].
> > While long timelocks could maintain safety for small numbers of channels, supporting billions (or tens of billions) of channels while maintaining safety is probably impossible [7].
> > 
> > Another way to reduce risk is to impose a penalty on an attacker.
> > Some channel protocols, such as the original Lightning protocol [1], a version of the two-party eltoo protocol [8], the fully-factory-optimized protocol [9], and the tunable-penalty channel protocol [10] include such penalties.
> > In addition, the tunable-penalty and single-commitment factory protocols [4] support penalties.
> > However, as was noted in the original Lightning paper [1], penalties don't eliminate the risk of a forced expiration spam attack.
> > Furthermore, existing penalty-based factory protocols [4] have limited scalability, as they depend on getting large numbers of casual users to coordinate and co-sign transactions [11][5].
> > 
> > In contrast, the timeout-tree protocol [5] scales via simple covenants (enabled by support for CheckTemplateVerify, AnyPrevOut, or a similar change to the Bitcoin consensus rules).
> > As a result, a single timeout-tree can support millions of channels and one small transaction per block can fund timeout-trees with tens of billions of offchain channels [5].
> > However, timeout-trees don't support penalties, and like all other known factory protocols [2][3][4], timeout-trees rely on timelocks.
> > 
> > Therefore, if the need to protect against forced expiration spam was already "imperative" for the original Lightning channel protocol [1], the use of scalable channel factories will make such protection indispensable.
> > 
> > This post proposes a change to Bitcoin's consensus rules that allows the length of a timelock to depend on the feerate being charged for putting transactions onchain.
> > Such Feerate-Dependent Timelocks (FDTs) can be used to make the above channel and factory protocols resistant to sudden spikes in blockchain congestion.
> > In the normal case, when there's no spike in congestion, FDTs don't extend the lengths of timelocks and thus don't create a tradeoff between capital efficiency and safety.
> > On the other hand, when congestion spikes, FDTs extend the lengths of timelocks and thus penalize the owner of the timelocked capital by reducing its efficiency.
> > Therefore, FDTs can be viewed as creating a penalty for spamming the blockchain, thus reducing the likelihood of such an attack even if the channel (or factory) protocol being used doesn't have an explicit penalty mechanism.
> > 
> > FDTs have other uses, including reducing the risk of having to pay unexpectedly high fees during a congestion spike, improving the accuracy of fee-penalties [5] and reducing the risk of one-shot receives [12].
> > 
> > Of separate interest, the analysis of FDTs given here leads to an exact analysis of the risk of double spend attacks that corrects an error in the original Bitcoin whitepaper [13].
> > 
> > A more complete description and analysis of FDTs is given in a paper [14].
> > 
> > Feerate-Dependent Timelock (FDT) Proposal
> > =========================================
> > 
> > A Feerate-Dependent Timelock (FDT) is created by encoding a feerate upper bound in a transaction's nSequence field.
> > A transaction with an FDT cannot be put onchain until:
> > 1) its absolute timelock encoded in its nLocktime field (and its relative timelock encoded in the same nSequence field, if present) has been satisfied, and
> > 2) the prevailing feerate has fallen below the FDT's feerate upper bound.
> > As a result, FDTs are automatically extended when the feerate for putting transactions onchain spikes (such as would occur during a forced expiration spam attack).
> > 
> > In order to determine the prevailing feerate, the median feerate of each block is calculated as the feerate (in satoshis/vbyte) that is paid for at least half of the block's vbytes.
> > 
> > If all miners were honest, a single block with a low median feerate would be enough to guarantee that congestion is low.
> > However, even a small fraction of dishonest miners would be able to occasionally mine a block with an artificially low feerate.
> > As a result, it isn't safe to wait for one block (or some other fixed number of blocks) with a low feerate in order to guarantee that honest users have had an opportunity to put their transactions onchain.
> > 
> > Instead, an FDT requires that some maximum number of blocks within an aligned window of consecutive blocks have a high median feerate.
> > The FDT proposal uses 14 currently masked-off bits in the nSequence field to express the FDT's three parameters:
> > * feerate_value,
> > * window_size, and
> > * block_count.
> > An aligned window of window_size blocks satisfies the FDT's parameters if it has fewer than block_count blocks with median feerate above feerate_value.
> > A transaction with an FDT can only be put onchain after an aligned window that satisfies the FDT's parameters and starts no earlier than when the transaction's absolute timelock (and corresponding relative timelock, if present) is satisfied.
> > 
> > In addition, the CheckSequenceVerify (CSV) operator is extended to enforce the desired feerate_value, window_size and block_count.
> > The details are given in the paper [14].
> > 
> > Safe Lightning Channels And Factories
> > =====================================
> > 
> > In order to protect a channel or factory protocol against forced expiration spam attacks, the protocol's timelocks are made to be feerate-dependent.
> > This is done by selecting a feerate_value (such as 4 times the current feerate) that would be caused by a forced expiration spam attack, along with the desired window_size and block_count parameters.
> > 
> > It's also possible to create multiple conflicting transactions with different FDTs (with later timelocks allowing higher feerates) in order to avoid timelocks that will never expire if feerates remain high permanently.
> > 
> > Other Uses
> > ==========
> > 
> > FDTs have uses in addition to protecting channel and factory protocols from forced expiration spam attacks.
> > 
> > For example, FDTs can protect users that are racing against timelocks from having to pay an unexpectedly high feerate due to temporary feerate fluctuations [14].
> > In addition, FDTs can be used to improve the accuracy of fee-penalties that are assessed when a casual user puts their timeout-tree leaf onchain [14](Section 4.10 of [5]).
> > Finally, FDTs can be used to allow a casual user to submit a transaction to the blockchain without having to then monitor the blockchain for a sudden spike in feerates, thus reducing the risk of one-shot receives [14][12].
> > 
> > Analysis
> > ========
> > 
> > FDT Implementation Cost
> > -----------------------
> > In order to verify an FDT, nodes have to determine whether or not there is an aligned window with a sufficient number of low-feerate blocks after the FDT's absolute timelock (and corresponding relative timelock, if present) is satisfied.
> > Therefore, if a node knows the starting block of the most recent aligned window that satisfies the FDT's feerate_value, window_size, and block_count parameters, the node can compare that starting block with the FDT's timelocks to verify the FDT.
> > Because the FDT parameters can be expressed using 14 bits, nodes only have to keep track of the starting block for 2^14 = 16k different low-feerate windows.
> > The starting block for each such window can be stored in 4 bytes, so 16k * 4B = 64kB of memory allows a node to verify an FDT in constant time.
> > (In practice, slightly more memory could be used in order to accommodate a reordering of the most recent 1k blocks.)
> > Therefore, DRAM that costs less than one cent, plus a small constant number of computations, suffice to verify an FDT.
> > 
> > FDT Dishonest Miner Attacks
> > ---------------------------
> > The window_size and block_count parameters can be selected to balance between:
> > 1) latency,
> > 2) the feerate paid by honest users, and
> > 3) security against dishonest miners.
> > At one extreme, if dishonest miners are of no concern, window_size and block_count can be set to 1, so the FDT can be satisfied when the first block with a sufficiently low feerate is mined.
> > At the other extreme, if dishonest miners are of great concern, window_size can be set to 16k and block_count can be set to 1024, in which case dishonest miners with 45% of the hashpower would have less than a 10^-33 chance of dishonestly mining enough blocks in a given window to satisfy the FDT prior to the honest users being able to get their transactions onchain [14].
> > 
> > Double Spend Attacks
> > --------------------
> > While it's unrelated to FDTs, the analysis of FDTs' resistance to dishonest miner attacks can also be used to analyze the risk of double spend attacks.
> > 
> > The original Bitcoin whitepaper [13] includes an analysis of the probability of a double spend attack in which a dishonest party colludes with dishonest miners in order to undo a bitcoin transaction and steal the goods purchased with that transaction.
> > That analysis correctly shows that the probability of success of a double spend attack falls exponentially with z, the depth of the transaction that's being double spent.
> > However, there are two problems with that analysis:
> > 1) it is approximate, and
> > 2) it ignores the possibility of the dishonest miners using pre-mining.
> > 
> > The first problem was addressed by Grunspan and Perez-Marco [15].
> > However, it doesn't appear that the second problem has been addressed previously.
> > 
> > Exact formulas for the risk of double spend attacks, including pre-mining, are given in the paper [14] and programs that implement those formulas are available on GitHub [16].
> > 
> > The effect of including pre-mining only becomes apparent when a large fraction of the miners are dishonest.
> > For example, Nakamoto estimates the required value of z to guarantee at most a 0.1% chance of a successful double spend, and Grunspan and Perez-Marco give exact values assuming no pre-mining.
> > Those results, plus exact results with pre-mining, are as follows:
> > 
> > % dishonest Estimated z w/o Exact z w/o Exact z w/
> > miners pre-mining [13] pre-mining [15] pre-mining [14]
> > =========== =============== =============== ===============
> > 10 5 6 6
> > 15 8 9 9
> > 20 11 13 13
> > 25 15 20 20
> > 30 24 32 33
> > 35 41 58 62
> > 40 89 133 144
> > 45 340 539 589
> > 
> > It's important to note that the above results with pre-mining assume that the time of the double spend attack is not selected by the attacker.
> > If the attacker can select when to perform the attack, they are guaranteed to succeed given any value of z, but the expected time required to perform the attack grows exponentially with z [14].
> > 
> > Conclusions
> > ===========
> > 
> > Securing Lightning channels and channel factories against forced expiration spam attacks is imperative.
> > 
> > Feerate-Dependent Timelocks (FDTs) provide this security without forcing the timelocks to be extended in the typical case, thus avoiding a capital efficiency vs. safety tradeoff.
> > Furthermore, a dishonest user who tries to use a forced expiration spam attack to steal funds is penalized by having their funds timelocked for a longer period, thus discouraging such attacks.
> > Finally, FDTs can be made to be highly resistant to attacks by dishonest miners.
> > 
> > FDTs have other uses, including the reduction of feerate risk and the calculation of fee-penalties.
> > 
> > While implementing FDTs requires some additional DRAM and computation, the costs are extremely small.
> > Given these advantages and their low costs, it's hoped that the Bitcoin consensus rules will be changed to support FDTs.
> > 
> > Regards,
> > John
> > 
> > [1] Poon and Dryja, The Bitcoin Lightning Network, https://lightning.network/lightning-network-paper.pdf
> > [2] Burchert, Decker and Wattenhofer, "Scalable Funding of Bitcoin Micropayment Channel Networks", http://dx.doi.org/10.1098/rsos.180089
> > [3] Decker, Russell and Osuntokun. "eltoo: A Simple Layer2 Protocol for Bitcoin", https://blockstream.com/eltoo.pdf
> > [4] Law, "Efficient Factories For Lightning Channels", https://github.com/JohnLaw2/ln-efficient-factories
> > [5] Law, "Scaling Lightning With Simple Covenants", https://github.com/JohnLaw2/ln-scaling-covenants
> > [6] Towns, "Re: Scaling Lightning With Simple Covenants", https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-September/021943.html
> > [7] Law, "Re: Scaling Lightning With Simple Covenants", https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-November/022175.html
> > [8] Towns, "Two-party eltoo w/ punishment", https://lists.linuxfoundation.org/pipermail/lightning-dev/2022-December/003788.html
> > [9] Law, "Factory-Optimized Channel Protocols For Lightning", https://github.com/JohnLaw2/ln-factory-optimized
> > [10] Law, "Lightning Channels With Tunable Penalties", https://github.com/JohnLaw2/ln-tunable-penalties
> > [11] Riard, "Solving CoinPool high-interactivity issue with cut-through update of Taproot leaves", https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-September/021969.html
> > [12] Law, "Watchtower-Free Lightning Channels For Casual Users", https://github.com/JohnLaw2/ln-watchtower-free
> > [13] Nakamoto. "Bitcoin: A Peer-to-Peer Electronic Cash System", http://bitcoin.org/bitcoin.pdf
> > [14] Law, "Scaling Lightning Safely With Feerate-Dependent Timelocks", https://github.com/JohnLaw2/ln-fdts
> > [15] Grunspan and Perez-Marco, "Double Spend Races", CoRR, vol. abs/1702.02867, http://arxiv.org/abs/1702.02867v3
> > [16] Law, https://github.com/JohnLaw2/ln-fdts
> > 
> > Sent with Proton Mail secure email.
> > 
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
> 
> 
> 
> 
> --
> Best regards,
> Boris Nagaev

Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks

[David A. Harding]

On 2023-12-28 08:06, jlspc via bitcoin-dev wrote:
> On Friday, December 22nd, 2023 at 8:36 AM, Nagaev Boris
> <bnagaev@gmail.com> wrote:
>> To validate a transaction with FDT [...]
>> a light client would have to determine the median fee
>> rate of the recent blocks. To do that without involving trust, it has
>> to download the blocks. What do you think about including median
>> feerate as a required OP_RETURN output in coinbase transaction?
> 
> Yes, I think that's a great idea!

I think this points to a small challenge of implementing this soft fork 
for pruned full nodes.  Let's say a fee-dependent timelock (FDT) soft 
fork goes into effect at time/block _t_.  Both before and for a while 
after _t_, Alice is running an older pruned full node that did not 
contain any FDT-aware code, so it prunes blocks after _t_ without 
storing any median feerate information about them (not even commitments 
in the coinbase transaction).  Later, well after _t_, Alice upgrades her 
node to one that is aware of FDTs.  Unfortunately, as a pruned node, it 
doesn't have earlier blocks, so it can't validate FDTs without 
downloading those earlier blocks.

I think the simplest solution would be for a recently-upgrade node to 
begin collecting median feerates for new blocks going forward and to 
only enforce FDTs for which it has the data.  That would mean anyone 
depending on FDTs should be a little more careful about them near 
activation time, as even some node versions that nominally enforced FDT 
consensus rules might not actually be enforcing them yet.

Of course, if the above solution isn't satisfactory, upgraded pruned 
nodes could simply redownload old blocks or, with extensions to the P2P 
protocol, just the relevant parts of them (i.e., coinbase transactions 
or, with a soft fork, even just commitments made in coinbase 
transactions[1]).

-Dave

[1] An idea discussed for the segwit soft fork was requiring the witness 
merkle root OP_RETURN to be the final output of the coinbase transaction 
so that all chunks of the coinbase transaction before it could be 
"compressed" into a SHA midstate and then the midstate could be extended 
with the bytes of the OP_RETURN commitment to produce the coinbase 
transaction's txid, which could then be connected to the block header 
using the standard Bitcoin-style merkle inclusion proof.  This would 
allow trailing commitments in even a very large coinbase transaction to 
be communicated in just a few hundred bytes (not including the size of 
the commitments themselves).  This idea was left out of segwit because 
at least one contemporary model of ASIC miner had a hardware-enforced 
requirement to put a mining reward payout in the final output.