Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id D4D90C0037; Thu, 28 Dec 2023 18:06:16 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp2.osuosl.org (Postfix) with ESMTP id 9AC5040A4A; Thu, 28 Dec 2023 18:06:16 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 9AC5040A4A Authentication-Results: smtp2.osuosl.org; dkim=pass (2048-bit key) header.d=protonmail.com header.i=@protonmail.com header.a=rsa-sha256 header.s=protonmail3 header.b=Qp6T1ylo X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.799 X-Spam-Level: X-Spam-Status: No, score=-2.799 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp2.osuosl.org ([127.0.0.1]) by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id BgI903319gna; Thu, 28 Dec 2023 18:06:13 +0000 (UTC) Received: from mail-0301.mail-europe.com (mail-0301.mail-europe.com [188.165.51.139]) by smtp2.osuosl.org (Postfix) with ESMTPS id 429EC40AA2; Thu, 28 Dec 2023 18:06:13 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 429EC40AA2 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail3; t=1703786765; x=1704045965; bh=J+6IueZ/YSGPoddB+ZK/yp/KRdH1hq1Ya9aQ3rCRX4U=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID: Message-ID:BIMI-Selector; b=Qp6T1yloW1GBZiQnj/AjmSrTNg5GYTYWkdpMMvMhK1j43Aj35r5BL9ctwUOirPhDf G6QWcM2jPZaRZ1Ar2IUUuNcXw94BxxLoqdJ7PMHqQamLa1pV39pP2Vlsgo2dLd2I47 wDSYohy6vGdtGNJ+UUeCL6IzBRpQ/zcDhZiolb6mrjzMjYhIMe8HQ9WEbkzJJTuWH8 fL96RdgQTISacvIjmR+CdXZYzkVsWPTbP4/PoTxoQdWiJR0Nsn3vTJ2dH3R+l9Hu9K H9L+QVYADC5U4bWZu5rfBBs+FAheQTYcdAcIAiehVY69t8ilTw9bTyNwaFsafCLsAI UhScA3iD4+yNQ== Date: Thu, 28 Dec 2023 18:06:00 +0000 To: Nagaev Boris From: jlspc Message-ID: In-Reply-To: References: Feedback-ID: 36436663:user:proton MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Mailman-Approved-At: Fri, 29 Dec 2023 16:32:18 +0000 Cc: Bitcoin Protocol Discussion , "lightning-dev@lists.linuxfoundation.org" Subject: Re: [bitcoin-dev] Scaling Lightning Safely With Feerate-Dependent Timelocks X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 28 Dec 2023 18:06:16 -0000 Hi Boris, Responses inline below: Sent with Proton Mail secure email. On Friday, December 22nd, 2023 at 8:36 AM, Nagaev Boris = 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