Date: Thu, 28 Dec 2023 18:06:00 +0000
To: Nagaev Boris <bnagaev@gmail.com>
From: jlspc <jlspc@protonmail.com>
Message-ID: <IhmJ-631z02S9ZjKb4VtaqVWa_W9U0s1Tnn2fhhGGMlXPUD4r5E08UX-N0iYaXTAk4s_90pemkdCRurPZIQjT9WE9gQSHPKbdpcn4aN_-Vs=@protonmail.com>
In-Reply-To: <CAFC_Vt7yJCN3a8d5dxmsbpz6i50pXAbSBhgA_HvBYifnoJxrQQ@mail.gmail.com>
References: <sJXy1yFGGxPpgtCexzW2WZhMMpJonGlOaT0Gb_eyQdUIOKPRXQ8tqrNvvunPF5E19kFEAeq5IHXx7Y7qkAFoEkGBS3JP5Tq3uFtSAVRg4NY=@protonmail.com>
 <CAFC_Vt7yJCN3a8d5dxmsbpz6i50pXAbSBhgA_HvBYifnoJxrQQ@mail.gmail.com>
Feedback-ID: 36436663:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
 "lightning-dev@lists.linuxfoundation.org"
 <lightning-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent
	Timelocks
Precedence: list

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!
>=20
> I have two questions regarding the window, which are related.
>=20
> 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 abs=
olute and relative timelocks were satisfied and the current block. The alig=
nment requirement allows one to prove tighter security bounds over a given =
time period. For example, 2 consecutive aligned 64-block windows give disho=
nest miners 2 chances to create artificial aligned low-feerate windows, but=
 65 chances to create such windows if alignment isn't required.

>=20
> 2. Does it make sense to have a global window_size? This would save
> space in FDT (=3D 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 <=3D y, using O(1) time per query.
>=20

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

> 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

>=20
> On Fri, Dec 15, 2023 at 6:20=E2=80=AFAM jlspc via bitcoin-dev
> bitcoin-dev@lists.linuxfoundation.org wrote:
>=20
> > TL;DR
> > =3D=3D=3D=3D=3D
> > * 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 trans=
actions onchain before timelocks expire.
> > * Feerate-Dependent Timelocks (FDTs) are timelocks that automatically e=
xtend 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, feerate=
s increase and FDTs are extended, thus penalizing the attacker by keeping t=
heir capital timelocked for longer.
> > - FDTs are tunable and can be made to be highly resistant to attacks fr=
om dishonest miners.
> > * Of separate interest, an exact analysis of the risk of double spend a=
ttacks is presented that corrects an error in the original Bitcoin whitepap=
er.
> >=20
> > Overview
> > =3D=3D=3D=3D=3D=3D=3D=3D
> >=20
> > Because the Lightning protocol relies on timelocks to establish the cor=
rect channel state, Lightning users could lose their funds if they're unabl=
e to put their transactions onchain quickly enough.
> > The original Lightning paper [1] states that "[f]orced expiration of ma=
ny transactions may be the greatest systemic risk when using the Lightning =
Network" and it uses the term "forced expiration spam" for an attack in whi=
ch a malicious party "creates many channels and forces them all to expire a=
t once", thus allowing timelocked transactions to become valid.
> > That paper also says that the creation of a credible threat against "sp=
amming the blockchain to encourage transactions to timeout" is "imperative"=
 [1].
> >=20
> > 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 ti=
me.
> > Second, channel factories themselves use timelocks, and thus are vulner=
able to a "forced expiration spam" attack.
> >=20
> > In fact, the timelocks in Lightning channels and factories are risky ev=
en 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 cause=
s malicious parties to attack opportunistically and honest parties to put t=
heir channels onchain due to the heightened risk.
> >=20
> > 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 transaction=
s onchain.
> > However, long timelocks limit the ability to dynamically reassign the c=
hannel's (or factory's) funds, thus creating a tradeoff between capital eff=
iciency and safety [6].
> > While long timelocks could maintain safety for small numbers of channel=
s, supporting billions (or tens of billions) of channels while maintaining =
safety is probably impossible [7].
> >=20
> > 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 pr=
otocol [9], and the tunable-penalty channel protocol [10] include such pena=
lties.
> > In addition, the tunable-penalty and single-commitment factory protocol=
s [4] support penalties.
> > However, as was noted in the original Lightning paper [1], penalties do=
n'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 coo=
rdinate and co-sign transactions [11][5].
> >=20
> > In contrast, the timeout-tree protocol [5] scales via simple covenants =
(enabled by support for CheckTemplateVerify, AnyPrevOut, or a similar chang=
e 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 billio=
ns of offchain channels [5].
> > However, timeout-trees don't support penalties, and like all other know=
n factory protocols [2][3][4], timeout-trees rely on timelocks.
> >=20
> > Therefore, if the need to protect against forced expiration spam was al=
ready "imperative" for the original Lightning channel protocol [1], the use=
 of scalable channel factories will make such protection indispensable.
> >=20
> > This post proposes a change to Bitcoin's consensus rules that allows th=
e length of a timelock to depend on the feerate being charged for putting t=
ransactions onchain.
> > Such Feerate-Dependent Timelocks (FDTs) can be used to make the above c=
hannel and factory protocols resistant to sudden spikes in blockchain conge=
stion.
> > In the normal case, when there's no spike in congestion, FDTs don't ext=
end the lengths of timelocks and thus don't create a tradeoff between capit=
al efficiency and safety.
> > On the other hand, when congestion spikes, FDTs extend the lengths of t=
imelocks 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 bl=
ockchain, thus reducing the likelihood of such an attack even if the channe=
l (or factory) protocol being used doesn't have an explicit penalty mechani=
sm.
> >=20
> > FDTs have other uses, including reducing the risk of having to pay unex=
pectedly high fees during a congestion spike, improving the accuracy of fee=
-penalties [5] and reducing the risk of one-shot receives [12].
> >=20
> > 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].
> >=20
> > A more complete description and analysis of FDTs is given in a paper [1=
4].
> >=20
> > Feerate-Dependent Timelock (FDT) Proposal
> > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> >=20
> > A Feerate-Dependent Timelock (FDT) is created by encoding a feerate upp=
er 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 relati=
ve timelock encoded in the same nSequence field, if present) has been satis=
fied, and
> > 2) the prevailing feerate has fallen below the FDT's feerate upper boun=
d.
> > As a result, FDTs are automatically extended when the feerate for putti=
ng transactions onchain spikes (such as would occur during a forced expirat=
ion spam attack).
> >=20
> > In order to determine the prevailing feerate, the median feerate of eac=
h block is calculated as the feerate (in satoshis/vbyte) that is paid for a=
t least half of the block's vbytes.
> >=20
> > If all miners were honest, a single block with a low median feerate wou=
ld be enough to guarantee that congestion is low.
> > However, even a small fraction of dishonest miners would be able to occ=
asionally mine a block with an artificially low feerate.
> > As a result, it isn't safe to wait for one block (or some other fixed n=
umber of blocks) with a low feerate in order to guarantee that honest users=
 have had an opportunity to put their transactions onchain.
> >=20
> > Instead, an FDT requires that some maximum number of blocks within an a=
ligned window of consecutive blocks have a high median feerate.
> > The FDT proposal uses 14 currently masked-off bits in the nSequence fie=
ld 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_v=
alue.
> > A transaction with an FDT can only be put onchain after an aligned wind=
ow that satisfies the FDT's parameters and starts no earlier than when the =
transaction's absolute timelock (and corresponding relative timelock, if pr=
esent) is satisfied.
> >=20
> > In addition, the CheckSequenceVerify (CSV) operator is extended to enfo=
rce the desired feerate_value, window_size and block_count.
> > The details are given in the paper [14].
> >=20
> > Safe Lightning Channels And Factories
> > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> >=20
> > In order to protect a channel or factory protocol against forced expira=
tion spam attacks, the protocol's timelocks are made to be feerate-dependen=
t.
> > 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 wit=
h the desired window_size and block_count parameters.
> >=20
> > It's also possible to create multiple conflicting transactions with dif=
ferent FDTs (with later timelocks allowing higher feerates) in order to avo=
id timelocks that will never expire if feerates remain high permanently.
> >=20
> > Other Uses
> > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> >=20
> > FDTs have uses in addition to protecting channel and factory protocols =
from forced expiration spam attacks.
> >=20
> > For example, FDTs can protect users that are racing against timelocks f=
rom having to pay an unexpectedly high feerate due to temporary feerate flu=
ctuations [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 transactio=
n to the blockchain without having to then monitor the blockchain for a sud=
den spike in feerates, thus reducing the risk of one-shot receives [14][12]=
.
> >=20
> > Analysis
> > =3D=3D=3D=3D=3D=3D=3D=3D
> >=20
> > 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 presen=
t) is satisfied.
> > Therefore, if a node knows the starting block of the most recent aligne=
d window that satisfies the FDT's feerate_value, window_size, and block_cou=
nt parameters, the node can compare that starting block with the FDT's time=
locks to verify the FDT.
> > Because the FDT parameters can be expressed using 14 bits, nodes only h=
ave to keep track of the starting block for 2^14 =3D 16k different low-feer=
ate windows.
> > The starting block for each such window can be stored in 4 bytes, so 16=
k * 4B =3D 64kB of memory allows a node to verify an FDT in constant time.
> > (In practice, slightly more memory could be used in order to accommodat=
e a reordering of the most recent 1k blocks.)
> > Therefore, DRAM that costs less than one cent, plus a small constant nu=
mber of computations, suffice to verify an FDT.
> >=20
> > FDT Dishonest Miner Attacks
> > ---------------------------
> > The window_size and block_count parameters can be selected to balance b=
etween:
> > 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 blo=
ck 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 di=
shonest miners with 45% of the hashpower would have less than a 10^-33 chan=
ce 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=
].
> >=20
> > Double Spend Attacks
> > --------------------
> > While it's unrelated to FDTs, the analysis of FDTs' resistance to disho=
nest miner attacks can also be used to analyze the risk of double spend att=
acks.
> >=20
> > The original Bitcoin whitepaper [13] includes an analysis of the probab=
ility of a double spend attack in which a dishonest party colludes with dis=
honest miners in order to undo a bitcoin transaction and steal the goods pu=
rchased with that transaction.
> > That analysis correctly shows that the probability of success of a doub=
le spend attack falls exponentially with z, the depth of the transaction th=
at'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.
> >=20
> > The first problem was addressed by Grunspan and Perez-Marco [15].
> > However, it doesn't appear that the second problem has been addressed p=
reviously.
> >=20
> > Exact formulas for the risk of double spend attacks, including pre-mini=
ng, are given in the paper [14] and programs that implement those formulas =
are available on GitHub [16].
> >=20
> > The effect of including pre-mining only becomes apparent when a large f=
raction 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-Ma=
rco give exact values assuming no pre-mining.
> > Those results, plus exact results with pre-mining, are as follows:
> >=20
> > % dishonest Estimated z w/o Exact z w/o Exact z w/
> > miners pre-mining [13] pre-mining [15] pre-mining [14]
> > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=
=3D=3D=3D =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D =3D=3D=3D=3D=3D=3D=
=3D=3D=3D=3D=3D=3D=3D=3D=3D
> > 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
> >=20
> > It's important to note that the above results with pre-mining assume th=
at 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 guarant=
eed to succeed given any value of z, but the expected time required to perf=
orm the attack grows exponentially with z [14].
> >=20
> > Conclusions
> > =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> >=20
> > Securing Lightning channels and channel factories against forced expira=
tion spam attacks is imperative.
> >=20
> > Feerate-Dependent Timelocks (FDTs) provide this security without forcin=
g 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 dishones=
t miners.
> >=20
> > FDTs have other uses, including the reduction of feerate risk and the c=
alculation of fee-penalties.
> >=20
> > 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.
> >=20
> > Regards,
> > John
> >=20
> > [1] Poon and Dryja, The Bitcoin Lightning Network, https://lightning.ne=
twork/lightning-network-paper.pdf
> > [2] Burchert, Decker and Wattenhofer, "Scalable Funding of Bitcoin Micr=
opayment 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.c=
om/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.l=
inuxfoundation.org/pipermail/bitcoin-dev/2023-November/022175.html
> > [8] Towns, "Two-party eltoo w/ punishment", https://lists.linuxfoundati=
on.org/pipermail/lightning-dev/2022-December/003788.html
> > [9] Law, "Factory-Optimized Channel Protocols For Lightning", https://g=
ithub.com/JohnLaw2/ln-factory-optimized
> > [10] Law, "Lightning Channels With Tunable Penalties", https://github.c=
om/JohnLaw2/ln-tunable-penalties
> > [11] Riard, "Solving CoinPool high-interactivity issue with cut-through=
 update of Taproot leaves", https://lists.linuxfoundation.org/pipermail/bit=
coin-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/170=
2.02867, http://arxiv.org/abs/1702.02867v3
> > [16] Law, https://github.com/JohnLaw2/ln-fdts
> >=20
> > Sent with Proton Mail secure email.
> >=20
> > _______________________________________________
> > bitcoin-dev mailing list
> > bitcoin-dev@lists.linuxfoundation.org
> > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>=20
>=20
>=20
>=20
> --
> Best regards,
> Boris Nagaev