* [bitcoin-dev] Scaling Lightning With Simple Covenants
@ 2023-09-08 18:54 jlspc
2023-09-11 0:56 ` [bitcoin-dev] [Lightning-dev] " Anthony Towns
` (3 more replies)
0 siblings, 4 replies; 14+ messages in thread
From: jlspc @ 2023-09-08 18:54 UTC (permalink / raw)
To: Bitcoin Protocol Discussion, lightning-dev
[-- Attachment #1: Type: text/plain, Size: 19542 bytes --]
TL;DR
=====
* The key challenge in scaling Lightning in a trust-free manner is the creation of Lightning channels for casual users.
- It appears that signature-based factories are inherently limited to creating at most tens or hundreds of Lightning channels per UTXO.
- In contrast, simple covenants (including those enabled by CTV [1] or APO [2]) would allow a single UTXO to create Lightning channels for millions of casual users.
* The resulting covenant-based protocols also:
- support resizing channels off-chain,
- use the same capital to simultaneously provide in-bound liquidity to casual users and route unrelated payments for other users,
- charge casual users tunable penalties for attempting to put an old state on-chain, and
- allow casual users to monitor the blockchain for just a few minutes every few months without employing a watchtower service.
* As a result, adding CTV and/or APO to Bitcoin's consensus rules would go a long way toward making Lightning a widely-used means of payment.
Overview
========
Many proposed changes to the Bitcoin consensus rules, including CheckTemplateVerify (CTV) [1] and AnyPrevOut (APO) [2], would support covenants.
While covenants have been shown to improve Bitcoin in a number of ways, scalability of Lightning is not typically listed as one of them.
This post argues that any change (including CTV and/or APO) that enables even simple covenants greatly improves Lightning's scalability, while meeting the usability requirements of casual users.
A more complete description, including figures, is given in a paper [3].
The Scalability Problem
=======================
If Bitcoin and Lightning are to become widely-used, they will have to be adopted by casual users who want to send and receive bitcoin, but who do not want to go to any effort in order to provide the infrastructure for making payments.
Instead, it's reasonable to expect that the Lightning infrastructure will be provided by dedicated users who are far less numerous than the casual users.
In fact, there are likely to be tens-of-thousands to millions of casual users per dedicated user.
This difference in numbers implies that the key challenge in scaling Bitcoin and Lightning is providing bitcoin and Lightning to casual users.
As a result, the rest of this post will focus on this challenge.
Known Lightning protocols allow casual users to perform Lightning payments without:
* maintaining high-availability,
* performing actions at specific times in the future, or
* having to trust a third-party (such as a watchtower service) [5][6].
In addition, they support tunable penalties for casual users who attempt to put an old channel state on-chain (for example, due to a crash that causes a loss of state).
As a result, these protocols meet casual users' needs and could become widely-used for payments if they were sufficiently scalable.
The Lightning Network lets users send and receive bitcoin off-chain in a trust-free manner [4].
Furthermore, there are Lightning protocols that allow Lightning channels to be resized off-chain [7].
Therefore, making Lightning payments and resizing Lightning channels are highly scalable operations.
However, providing Lightning channels to casual users is not scalable.
In particular, no known protocol that uses the current Bitcoin consensus rules allows a large number (e.g., tens-of-thousands to millions) of Lightning channels, each co-owned by a casual user, to be created from a single on-chain unspent transaction output (UTXO).
As a result, being able to create (and close) casual users' Lightning channels remains the key bottleneck in scaling Lightning.
Casual Users And Signatures
===========================
Unfortunately, there are good reasons to believe this bottleneck is unavoidable given the current Bitcoin consensus rules.
The problem is that in order for a casual user to co-own a Lightning channel, they must co-own an on-chain UTXO [8].
Therefore, if a large number of casual users are to each co-own a Lightning channel, all of which are funded by a single UTXO, that UTXO must require signatures from all of those casual users.
In practice, the problem is much harder than just getting signatures from a large number of casual users, as the signatures themselves depend on the exact set of casual users whose signatures are required.
For example, if a UTXO requires signatures from a set of 1,000 casual users and if 999 of them sign but one does not, the 999 signatures that were obtained can't be used.
Instead, one has to start all over again, say with a new UTXO that requires signatures from the 999 users that signed the previous time.
However, if not all of those 999 sign, the signatures that were obtained in the second try are also unusable.
The requirement for casual users to sign transactions that specify the exact set of casual users whose signatures are required creates a very difficult group coordination problem that's not well-suited to the behavior of casual users [9, Section 2.2].
As a result, while a channel factory could be used to fund channels for perhaps 10 or even 100 casual users, it's very unlikely that any protocol using the current Bitcoin consensus rules can fund tens-of-thousands to millions of channels from a single UTXO.
Simple Covenants And Timeout-Trees
==================================
On the other hand, if the consensus rules are changed to allow even simple covenants, this scaling bottleneck is eliminated.
The key observation is that with covenants, a casual user can co-own an off-chain Lightning channel without having to sign all (or any) of the transactions on which it depends.
Instead, a UTXO can have a covenant that guarantees the creation of the casual user's channel.
The simplest way to have a single UTXO create channels for a large number of casual users is to put a covenant on the UTXO that forces the creation of a tree of transactions, the leaves of which are the casual users' channels.
While such a covenant tree can create channels for millions of casual users without requiring signatures or solving a difficult group coordination problem, it's not sufficient for scaling.
The problem is that each channel created by a covenant tree has a fixed set of owners, and changing the ownership of a channel created by a covenant tree requires putting the channel on-chain.
Therefore, assuming that all casual users will eventually want to pair with different dedicated users (and vice-versa), the covenant tree doesn't actually provide any long-term scaling benefit.
Fortunately, real long-term scaling can be achieved by adding a deadline after which all non-leaf outputs in the covenant tree can be spent without having to meet the conditions of the covenant.
The resulting covenant tree is called a "timeout-tree" [9, Section 5.3].
Let A_1 ... A_n denote a large number of casual users, let B be a dedicated user, and let E denote some fixed time in the future.
User B creates a timeout-tree with expiry E where:
* leaf i has an output that funds a Lightning channel owned by A_i and B, and
* after time E, each non-leaf output in the covenant tree can also be spent by user B without having to meet the conditions of the covenant.
Thus, any time before E, casual user A_i can put the Lightning channel (A_i, B) on-chain by putting all of its ancestors in the timeout-tree on-chain.
Once (A_i, B) is on-chain, the expiry E has no effect so A_i and B can continue to use the Lightning channel to send and receive payments from and to A_i.
On the other hand, sometime shortly before E, casual user A_i can use the Lightning Network to send all of their balance in the channel (A_i, B) to themselves in some other Lightning channel that is the leaf of some other timeout-tree.
More precisely, casual user A_i should rollover their balance by sending it from a given timeout-tree between time E - to_self_delay_i and time E, where E is the timeout-tree's expiry and to_self_delay_i is A_i's Lightning channel safety parameter.
Note that to_self_delay_i can be in the range of 1 to 3 months if a watchtower-free channel protocol is used [5][6], so performing the drain within this time window does not put an unreasonable availability requirement on A_i.
If all casual users drain their balances from the timeout-tree before E, then after E dedicated user B can create a new timeout-tree, with leaves that create Lightning channels for a new set of casual users, by putting a single transaction on-chain that spends the UTXO which created the expired timeout-tree.
In this case, all n of the old Lightning channels are closed and n new channels are created with a single on-chain transaction.
Of course, it's possible that some casual users will put their Lightning channel in the old timeout-tree on-chain, while others will drain their balance from the timeout-tree before E.
In this case, user B can create a new timeout-tree that's funded by the non-leaf outputs of the old timeout-tree that have been put on-chain.
While this results in a larger on-chain footprint than the case in which all casual users drain their balances from the old timeout-tree, it can still provide substantial scaling as long as the number of leaves put on-chain is small (in particular, well below n/(log n)).
By creating incentives that reward users who drain their balances from the timeout-tree rather than putting their channels on-chain, almost all leaves will stay off-chain and good scalability will be achieved.
Passive Rollovers For Casual Users
==================================
The timeout-trees defined above don't place unreasonable availability requirements on casual users and they allow a very large number of casual users to obtain a Lightning channel with a single on-chain transaction.
However, there are two problems with forcing casual users to drain their balances from an old timeout-tree to a new timeout-tree before the old timeout-tree's expiry:
1) if a casual user fails to perform the required drain before the old timeout-tree's expiry (due to unexpected unavailability), they lose all of their funds in the timeout-tree, and
2) if the dedicated user B is unavailable when a casual user attempts to drain their funds prior to the timeout-tree's expiry, the casual user will put their timeout-tree leaf on-chain (thus increasing the on-chain footprint and limiting scalability).
This second problem matters, as a casual user should only have to devote a short period (e.g., 10 minutes) every few months to performing the drain, so even a short period of unavailability by the dedicated user could force the casual user to go on-chain.
Instead, it would be preferable if the dedicated user could facilitate the rollover of the casual user's funds from a timeout-tree that's about to expire to another one without requiring input from the casual user.
This can be achieved by using a variation of the FFO-WF Lightning channel protocol [6].
The FFO-WF protocol uses control transactions to determine the current state of the Lightning channel and the resolution of any outstanding HTLCs, and these control transactions determine how the channel's value transactions disperse the channel's funds.
As a result, just prior to E - to_self_delay_i, B can create a new timeout-tree that funds a new Lightning channel with casual user A_i where the new channel is controlled by A_i's *same* control transactions (thus allowing A_i to obtain their funds from either the old or new Lightning channel, but not from both).
Therefore, once the old timeout-tree expires, A_i can still access their funds in the new timeout-tree's Lightning channel without having to perform any actions.
Of course, sometime between E - to_self_delay_i and E, A_i should verify that B has created such a new timeout-tree.
In addition, HTLCs can be handled so that rolling over the casual user's funds from one timeout-tree to another does not require any actions from the casual user.
The details are given in the paper [3].
Off-Chain bitcoin
=================
The Lightning Network lets casual users send and receive bitcoin entirely off-chain
However, the casual user has to wait (for a period of time specified by their Lightning partner's to_self_delay parameter) before they can access their Lightning funds on-chain.
This is problematic, as accessing one's Lightning funds on-chain requires paying fees to put transactions on-chain, and those fees cannot be paid using one's Lightning funds (due to the delay mentioned above).
Thus, while Lightning can be used for most of a user's funds, the user must also be able to access some bitcoin (enough to pay transaction fees) without any delays.
Fortunately, timeout-trees can be used to provide casual users with immediately-accessible off-chain bitcoin in addition to bitcoin in Lightning channels.
Furthermore, it's possible to use a control output owned by a casual user to rollover the casual user's immediately-accessible bitcoin from one timeout-tree to the next along with their Lightning funds [3].
In fact, this rollover can also be done without requiring any actions from the casual user and it can be used to rebalance the fraction of the user's funds that are immediately-accessible versus within Lightning [3].
Control UTXOs
=============
The FFO-WF protocol (as adapted for timeout-trees) requires that each casual user own an independent UTXO that is spent by that user's control transactions.
Creating an on-chain UTXO for every casual user could require a significant on-chain footprint, thus limiting scalability.
Instead, each casual user can be given an off-chain UTXO that is created by a leaf of a tree of off-chain transactions defined by covenants [3].
Improving Capital Efficiency
============================
In order to rollover funds from one timeout-tree to another, the dedicated user creating those timeout-trees must fund both the old and new timeout-trees simultaneously, even though they only create one timeout-tree's worth of Lightning channel capacity.
Fortunately, this overhead can be made very small by funding multiple timeout-trees in a staggered fashion, where only one has to be rolled-over at a time [3].
Also, because casual users may send and receive payments infrequently, the dedicated user's capital devoted to timeout-trees may generate few routing fees.
As a result, casual users may have to pay significant fees for the creation of their Lightning channels (and/or for payments to or from those channels).
However, the fees that casual users have to pay could be reduced if the capital in their channels could also be used for routing payments between other users.
This can be accomplished by having the timeout-trees create hierarchical channels, each of which is owned by a single casual user and a pair of dedicated users [7].
By using an idea created by Towns [10][11][3], a single unit of capital in each hierarchical channel can be used to route two independent payments of one unit each.
Scalability
===========
The above protocols can perform the following actions completely off-chain:
* Lightning sends and receives, and
* resizing of Lightning channels.
Assuming:
* 1 million hierarchical Lightning channels per timeout-tree,
* a 1,000-block (about a week) to_self_delay parameter for dedicated users, and
* a 10,000-block (about 69 days) to_self_delay parameter for casual users, and
* 121,000 blocks (about 2.3 years) from the creation of each timeout-tree to its expiry,
a single 1-input/2-output transaction per block provides:
* 11 Lightning channels per casual user to each of 10 billion casual users [3].
Furthermore, given the above assumptions, a single 1-input/2-output transaction per block allows each casual user to:
* close an existing Lightning channel,
* open a new Lightning channel with a new partner, and
* rebalance funds between Lightning and immediately-accessible off-chain bitcoin
once every 10,000 blocks (about 69 days) [3].
Of course, the above calculations don't mean that 10 billion casual Lightning users would create only 1 on-chain transaction per block.
In reality, their on-chain footprint would be dominated by users who don't follow the protocol due to errors, unavailability, or malicious intent.
The rate of such protocol violations is hard to predict, but it's likely that casual users' unavailability would be the most significant problem.
Usability
=========
The above protocols have the following properties for casual users:
* watchtower-freedom (that is, they accommodate months-long unavailability without requiring a watchtower service to secure the user's funds) ([5] Section 3.1),
* one-shot receives (that is, receiving a payment does not require performing actions at multiple blockheights) ([5] Section 3.4),
* asynchronous receives (that is, it's possible to receive a payment when the sender is offline) ([5] Section 3.6), and
* tunable penalties for attempting to put an old state on-chain ([12]).
Limitations
===========
Finally, the above results depend on the following assumptions:
1) the cost of resolving an HTLC on-chain is less than the value of the HTLC,
2) transaction packages are relayed reliably from users to miners, and
3) there is a known upper bound on the delay from when a package is submitted to when it is included in the blockchain.
These limitations, and ideas for how they can be addressed, are discussed further in the paper [3].
Conclusions
===========
With the current Bitcoin consensus rules, there are reasons to believe that the scalability of Lightning is inherently limited.
However, simple covenants and timeout-trees can overcome these scalability limitations.
In particular, CheckTemplateVerify (CTV) and/or AnyPrevOut (APO) could be used to dramatically increase the number of casual users who send and receive bitcoin in a trust-free manner.
As a result, it's hoped that CTV, APO or a similar mechanism that enables simple covenants will be added to Bitcoin's consensus rules in order to allow Lightning to become a widely-used means of payment.
Regards,
John
[1] BIP 119 CHECKTEMPLATEVERIFY, https://github.com/bitcoin/bips/blob/master/bip-0119.mediawiki
[2] BIP 118 SIGHASH_ANYPREVOUT, https://anyprevout.xyz/
[3] Law, "Scaling Lightning With Simple Covenants", https://github.com/JohnLaw2/ln-scaling-covenants
[4] "BOLT (Basis Of Lightning Technology) specifications", https://github.com/lightningnetwork/lightning-rfc
[5] Law, "Watchtower-Free Lightning Channels For Casual Users", https://github.com/JohnLaw2/ln-watchtower-free
[6] Law, "Factory-Optimized Channel Protocols For Lightning", available at https://github.com/JohnLaw2/ln-factory-optimized.
[7] Law, "Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://github.com/JohnLaw2/ln-hierarchical-channels
[8] Burchert, Decker and Wattenhofer, "Scalable Funding of Bitcoin Micropayment Channel Networks", http://dx.doi.org/10.1098/rsos.180089
[9] Law, "Scaling Bitcoin With Inherited IDs", https://github.com/JohnLaw2/btc-iids
[10] Towns, "Re: Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-April/003913.html
[11] Law, "Re: Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-April/003917.html
[12] Law, "Lightning Channels With Tunable Penalties", https://github.com/JohnLaw2/ln-tunable-penalties
Sent with [Proton Mail](https://proton.me/) secure email.
[-- Attachment #2: Type: text/html, Size: 20479 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] [Lightning-dev] Scaling Lightning With Simple Covenants
2023-09-08 18:54 [bitcoin-dev] Scaling Lightning With Simple Covenants jlspc
@ 2023-09-11 0:56 ` Anthony Towns
2023-09-17 0:52 ` jlspc
2023-11-15 19:59 ` jlspc
2023-09-11 2:13 ` [bitcoin-dev] " Rusty Russell
` (2 subsequent siblings)
3 siblings, 2 replies; 14+ messages in thread
From: Anthony Towns @ 2023-09-11 0:56 UTC (permalink / raw)
To: jlspc; +Cc: Bitcoin Protocol Discussion, lightning-dev
On Fri, Sep 08, 2023 at 06:54:46PM +0000, jlspc via Lightning-dev wrote:
> TL;DR
> =====
I haven't really digested this, but I think there's a trust vs
capital-efficiency tradeoff here that's worth extracting.
Suppose you have a single UTXO, that's claimable by "B" at time T+L,
but at time T that UTXO holds funds belonging not only to B, but also
millions of casual users, C_1..C_1000000. If B cheats (eg by not signing
any further lightning updates between now and time T+L), then each
casual user needs to drop their channel to the chain, or else lose all
their funds. (Passive rollovers doesn't change this -- it just moves the
responsibility for dropping the channel to the chain to some other
participant)
That then faces the "thundering herd" problem -- instead of the single
one-in/one-out tx that we expected when B is doing the right thing,
we're instead seeing between 1M and 2M on-chain txs as everyone recovers
their funds (the number of casual users multiplied by some factor that
depends on how many outputs each internal tx has).
But whether an additional couple of million txs is a problem depends
on how long a timeframe they're spread over -- if it's a day or two,
then it might simply be impossible; if it's over a year or more, it
may not even be noticable; if it's somewhere in between, it might just
mean you're paying a modest amount in additional fees than you'd have
normally expected.
Suppose that casual users have a factor in mind, eg "If worst comes to
worst, and everyone decides to exit at the same time I do, I want to be
sure that only generates 100 extra transactions per block if everyone
wants to recover their funds prior to B being able to steal everything".
Then in that case, they can calculate along the following lines: 1M users
with 2-outputs per internal tx means 2M transactions, divide that by 100
gives 20k blocks, at 144 blocks per day, that's 5 months. Therefore,
I'm going to ensure all my funds are rolled over to a new utxo while
there's at least 5 months left on the timeout.
That lowers B's capital efficiency -- if all the causal users follow
that policy, then B is going to own all the funds in Fx for five whole
months before it can access them. So each utxo here has its total
lifetime (L) actually split into two phases: an active lifetime LA of
some period, and an inactive lifetime of LI=5 months, which would have
been used by everyone to recover their funds if B had attempted to block
normal rollover. The capital efficiency is then reduced by a factor of
1/(1+LA/LI). (LI is dependent on the number of users, their willingness
to pay high fees to recover their funds, and global blockchain capacity,
LA is L-LI, L is your choice)
Note that casual users can't easily reduce their LI timeout just by
having the provider split them into different utxos -- if the provider
cheats/fails, that's almost certainly a correlated across all their
utxos, and all the participants across each of those utxos will need
to drop to the chain to preserve their funds, each competing with each
other for confirmation.
Also, if different providers collude, they can cause problems: if you
expected 2M transactions over five months due to one provider failing,
that's one thing; but if a dozen providers fail simultaneously, then that
balloons up to perhaps 24M txs over the same five months, or perhaps 25%
of every block, which may be quite a different matter.
Ignoring that caveat, what do numbers here look like? If you're a provider
who issues a new utxo every week (so new customers can join without too
much delay), have a million casual users as customers, and target LA=16
weeks (~3.5 months), so users don't need to rollover too frequently,
and each user has a balanced channel with $2000 of their own funds,
and $2000 of your funds, so they can both pay and be paid, then your
utxos might look like:
active_1 through active_16: 62,500 users each; $250M balance each
inactive_17 through inactive_35: $250M balance each, all your funds,
waiting for timeout to be usable
That's:
* $2B of user funds
* $2B of your funds in active channels
* $4.5B of your funds locked up, waiting for timeout
In that case, only 30% of the $6.5B worth of working capital that you've
dedicated to lightning is actually available for routing.
Optimising that formula by making LA as large as possible doesn't
necessarily work -- if a casual user spends all their funds and
disappears prior to the active lifetime running out, then those
funds can't be easily spent by B until the total lifetime runs out,
so depending on how persistent your casual users are, I think that's
another way of ending up with your capital locked up unproductively.
(There are probably ways around this with additional complexity: eg,
you could peer with a dedicated node, and have the timeout path be
"you+them+timeout", so that while you could steal from casual users who
don't rollover, you can't steal from your dedicated peer, so that $4.5B
could be rolled into a channel with them, and used for routing)
You could perhaps also vary the timeout at different layers of the
internal tree -- if you have 500k users with a $10 balance, and give them
a timeout of 16 weeks, and give the remaining 500k with an average $2000
balance a timeout of 26 weeks, then each will calculate LI=10 weeks,
and the $10 folks will rollover at 1.5 months, and the remainder will
rollover at about 4 months; but your idle balance will be $5M for 20
weeks plus $1B for 10 weeks, rather than $1.005B for 20 weeks.
Anyway, I think that's an interesting way of capturing a big concern
with this sort of approach (namely, "what happens if the nice, scalable
path doesn't work, and we have to dump *LOTS* of stuff onchain") in a
measurable way.
Cheers,
aj
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] Scaling Lightning With Simple Covenants
2023-09-08 18:54 [bitcoin-dev] Scaling Lightning With Simple Covenants jlspc
2023-09-11 0:56 ` [bitcoin-dev] [Lightning-dev] " Anthony Towns
@ 2023-09-11 2:13 ` Rusty Russell
2023-09-17 0:56 ` jlspc
2023-09-11 5:27 ` Antoine Riard
2023-09-18 4:14 ` ZmnSCPxj
3 siblings, 1 reply; 14+ messages in thread
From: Rusty Russell @ 2023-09-11 2:13 UTC (permalink / raw)
To: jlspc, Bitcoin Protocol Discussion, Bitcoin Protocol Discussion,
lightning-dev
Hi!
I've read the start of the paper on my vacation, and am still
digesting it. But even so far, it presents some delightful
possibilities.
As with some other proposals, it's worth noting that the cost of
enforcement is dramatically increased. It's no longer one or two txs,
it's 10+. If the "dedicated user" contributes some part of the expected
fee, the capital efficiency is reduced (and we're back to "how much is
enough?").
But worst case (dramatic dedicated user failure) it's only a 2x penalty
on number of onchain txs, which seems acceptable if the network is
sufficiently mature that these failure events are rare.
Note also that the (surprisingly common!) "user goes away" case where
the casual user fails to rollover only returns funds to the dedicated
user; relying on legal and normal custody policies in this case may be
preferable to an eternal burden on the UTXO set with the current
approach!
Thankyou!
Rusty.
jlspc via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> writes:
> TL;DR
> =====
> * The key challenge in scaling Lightning in a trust-free manner is the creation of Lightning channels for casual users.
> - It appears that signature-based factories are inherently limited to creating at most tens or hundreds of Lightning channels per UTXO.
> - In contrast, simple covenants (including those enabled by CTV [1] or APO [2]) would allow a single UTXO to create Lightning channels for millions of casual users.
> * The resulting covenant-based protocols also:
> - support resizing channels off-chain,
> - use the same capital to simultaneously provide in-bound liquidity to casual users and route unrelated payments for other users,
> - charge casual users tunable penalties for attempting to put an old state on-chain, and
> - allow casual users to monitor the blockchain for just a few minutes every few months without employing a watchtower service.
> * As a result, adding CTV and/or APO to Bitcoin's consensus rules would go a long way toward making Lightning a widely-used means of payment.
>
> Overview
> ========
>
> Many proposed changes to the Bitcoin consensus rules, including CheckTemplateVerify (CTV) [1] and AnyPrevOut (APO) [2], would support covenants.
> While covenants have been shown to improve Bitcoin in a number of ways, scalability of Lightning is not typically listed as one of them.
> This post argues that any change (including CTV and/or APO) that enables even simple covenants greatly improves Lightning's scalability, while meeting the usability requirements of casual users.
> A more complete description, including figures, is given in a paper [3].
>
> The Scalability Problem
> =======================
>
> If Bitcoin and Lightning are to become widely-used, they will have to be adopted by casual users who want to send and receive bitcoin, but who do not want to go to any effort in order to provide the infrastructure for making payments.
> Instead, it's reasonable to expect that the Lightning infrastructure will be provided by dedicated users who are far less numerous than the casual users.
> In fact, there are likely to be tens-of-thousands to millions of casual users per dedicated user.
> This difference in numbers implies that the key challenge in scaling Bitcoin and Lightning is providing bitcoin and Lightning to casual users.
> As a result, the rest of this post will focus on this challenge.
>
> Known Lightning protocols allow casual users to perform Lightning payments without:
> * maintaining high-availability,
> * performing actions at specific times in the future, or
> * having to trust a third-party (such as a watchtower service) [5][6].
>
> In addition, they support tunable penalties for casual users who attempt to put an old channel state on-chain (for example, due to a crash that causes a loss of state).
> As a result, these protocols meet casual users' needs and could become widely-used for payments if they were sufficiently scalable.
>
> The Lightning Network lets users send and receive bitcoin off-chain in a trust-free manner [4].
> Furthermore, there are Lightning protocols that allow Lightning channels to be resized off-chain [7].
> Therefore, making Lightning payments and resizing Lightning channels are highly scalable operations.
>
> However, providing Lightning channels to casual users is not scalable.
> In particular, no known protocol that uses the current Bitcoin consensus rules allows a large number (e.g., tens-of-thousands to millions) of Lightning channels, each co-owned by a casual user, to be created from a single on-chain unspent transaction output (UTXO).
> As a result, being able to create (and close) casual users' Lightning channels remains the key bottleneck in scaling Lightning.
>
> Casual Users And Signatures
> ===========================
>
> Unfortunately, there are good reasons to believe this bottleneck is unavoidable given the current Bitcoin consensus rules.
> The problem is that in order for a casual user to co-own a Lightning channel, they must co-own an on-chain UTXO [8].
> Therefore, if a large number of casual users are to each co-own a Lightning channel, all of which are funded by a single UTXO, that UTXO must require signatures from all of those casual users.
>
> In practice, the problem is much harder than just getting signatures from a large number of casual users, as the signatures themselves depend on the exact set of casual users whose signatures are required.
> For example, if a UTXO requires signatures from a set of 1,000 casual users and if 999 of them sign but one does not, the 999 signatures that were obtained can't be used.
> Instead, one has to start all over again, say with a new UTXO that requires signatures from the 999 users that signed the previous time.
> However, if not all of those 999 sign, the signatures that were obtained in the second try are also unusable.
>
> The requirement for casual users to sign transactions that specify the exact set of casual users whose signatures are required creates a very difficult group coordination problem that's not well-suited to the behavior of casual users [9, Section 2.2].
> As a result, while a channel factory could be used to fund channels for perhaps 10 or even 100 casual users, it's very unlikely that any protocol using the current Bitcoin consensus rules can fund tens-of-thousands to millions of channels from a single UTXO.
>
> Simple Covenants And Timeout-Trees
> ==================================
>
> On the other hand, if the consensus rules are changed to allow even simple covenants, this scaling bottleneck is eliminated.
> The key observation is that with covenants, a casual user can co-own an off-chain Lightning channel without having to sign all (or any) of the transactions on which it depends.
> Instead, a UTXO can have a covenant that guarantees the creation of the casual user's channel.
> The simplest way to have a single UTXO create channels for a large number of casual users is to put a covenant on the UTXO that forces the creation of a tree of transactions, the leaves of which are the casual users' channels.
>
> While such a covenant tree can create channels for millions of casual users without requiring signatures or solving a difficult group coordination problem, it's not sufficient for scaling.
> The problem is that each channel created by a covenant tree has a fixed set of owners, and changing the ownership of a channel created by a covenant tree requires putting the channel on-chain.
> Therefore, assuming that all casual users will eventually want to pair with different dedicated users (and vice-versa), the covenant tree doesn't actually provide any long-term scaling benefit.
>
> Fortunately, real long-term scaling can be achieved by adding a deadline after which all non-leaf outputs in the covenant tree can be spent without having to meet the conditions of the covenant.
> The resulting covenant tree is called a "timeout-tree" [9, Section 5.3].
>
> Let A_1 ... A_n denote a large number of casual users, let B be a dedicated user, and let E denote some fixed time in the future.
> User B creates a timeout-tree with expiry E where:
> * leaf i has an output that funds a Lightning channel owned by A_i and B, and
> * after time E, each non-leaf output in the covenant tree can also be spent by user B without having to meet the conditions of the covenant.
>
> Thus, any time before E, casual user A_i can put the Lightning channel (A_i, B) on-chain by putting all of its ancestors in the timeout-tree on-chain.
> Once (A_i, B) is on-chain, the expiry E has no effect so A_i and B can continue to use the Lightning channel to send and receive payments from and to A_i.
>
> On the other hand, sometime shortly before E, casual user A_i can use the Lightning Network to send all of their balance in the channel (A_i, B) to themselves in some other Lightning channel that is the leaf of some other timeout-tree.
> More precisely, casual user A_i should rollover their balance by sending it from a given timeout-tree between time E - to_self_delay_i and time E, where E is the timeout-tree's expiry and to_self_delay_i is A_i's Lightning channel safety parameter.
> Note that to_self_delay_i can be in the range of 1 to 3 months if a watchtower-free channel protocol is used [5][6], so performing the drain within this time window does not put an unreasonable availability requirement on A_i.
>
> If all casual users drain their balances from the timeout-tree before E, then after E dedicated user B can create a new timeout-tree, with leaves that create Lightning channels for a new set of casual users, by putting a single transaction on-chain that spends the UTXO which created the expired timeout-tree.
> In this case, all n of the old Lightning channels are closed and n new channels are created with a single on-chain transaction.
>
> Of course, it's possible that some casual users will put their Lightning channel in the old timeout-tree on-chain, while others will drain their balance from the timeout-tree before E.
> In this case, user B can create a new timeout-tree that's funded by the non-leaf outputs of the old timeout-tree that have been put on-chain.
> While this results in a larger on-chain footprint than the case in which all casual users drain their balances from the old timeout-tree, it can still provide substantial scaling as long as the number of leaves put on-chain is small (in particular, well below n/(log n)).
> By creating incentives that reward users who drain their balances from the timeout-tree rather than putting their channels on-chain, almost all leaves will stay off-chain and good scalability will be achieved.
>
> Passive Rollovers For Casual Users
> ==================================
>
> The timeout-trees defined above don't place unreasonable availability requirements on casual users and they allow a very large number of casual users to obtain a Lightning channel with a single on-chain transaction.
> However, there are two problems with forcing casual users to drain their balances from an old timeout-tree to a new timeout-tree before the old timeout-tree's expiry:
> 1) if a casual user fails to perform the required drain before the old timeout-tree's expiry (due to unexpected unavailability), they lose all of their funds in the timeout-tree, and
> 2) if the dedicated user B is unavailable when a casual user attempts to drain their funds prior to the timeout-tree's expiry, the casual user will put their timeout-tree leaf on-chain (thus increasing the on-chain footprint and limiting scalability).
> This second problem matters, as a casual user should only have to devote a short period (e.g., 10 minutes) every few months to performing the drain, so even a short period of unavailability by the dedicated user could force the casual user to go on-chain.
>
> Instead, it would be preferable if the dedicated user could facilitate the rollover of the casual user's funds from a timeout-tree that's about to expire to another one without requiring input from the casual user.
> This can be achieved by using a variation of the FFO-WF Lightning channel protocol [6].
> The FFO-WF protocol uses control transactions to determine the current state of the Lightning channel and the resolution of any outstanding HTLCs, and these control transactions determine how the channel's value transactions disperse the channel's funds.
>
> As a result, just prior to E - to_self_delay_i, B can create a new timeout-tree that funds a new Lightning channel with casual user A_i where the new channel is controlled by A_i's *same* control transactions (thus allowing A_i to obtain their funds from either the old or new Lightning channel, but not from both).
> Therefore, once the old timeout-tree expires, A_i can still access their funds in the new timeout-tree's Lightning channel without having to perform any actions.
> Of course, sometime between E - to_self_delay_i and E, A_i should verify that B has created such a new timeout-tree.
>
> In addition, HTLCs can be handled so that rolling over the casual user's funds from one timeout-tree to another does not require any actions from the casual user.
> The details are given in the paper [3].
>
> Off-Chain bitcoin
> =================
>
> The Lightning Network lets casual users send and receive bitcoin entirely off-chain
> However, the casual user has to wait (for a period of time specified by their Lightning partner's to_self_delay parameter) before they can access their Lightning funds on-chain.
> This is problematic, as accessing one's Lightning funds on-chain requires paying fees to put transactions on-chain, and those fees cannot be paid using one's Lightning funds (due to the delay mentioned above).
> Thus, while Lightning can be used for most of a user's funds, the user must also be able to access some bitcoin (enough to pay transaction fees) without any delays.
>
> Fortunately, timeout-trees can be used to provide casual users with immediately-accessible off-chain bitcoin in addition to bitcoin in Lightning channels.
> Furthermore, it's possible to use a control output owned by a casual user to rollover the casual user's immediately-accessible bitcoin from one timeout-tree to the next along with their Lightning funds [3].
> In fact, this rollover can also be done without requiring any actions from the casual user and it can be used to rebalance the fraction of the user's funds that are immediately-accessible versus within Lightning [3].
>
> Control UTXOs
> =============
>
> The FFO-WF protocol (as adapted for timeout-trees) requires that each casual user own an independent UTXO that is spent by that user's control transactions.
> Creating an on-chain UTXO for every casual user could require a significant on-chain footprint, thus limiting scalability.
> Instead, each casual user can be given an off-chain UTXO that is created by a leaf of a tree of off-chain transactions defined by covenants [3].
>
> Improving Capital Efficiency
> ============================
>
> In order to rollover funds from one timeout-tree to another, the dedicated user creating those timeout-trees must fund both the old and new timeout-trees simultaneously, even though they only create one timeout-tree's worth of Lightning channel capacity.
> Fortunately, this overhead can be made very small by funding multiple timeout-trees in a staggered fashion, where only one has to be rolled-over at a time [3].
>
> Also, because casual users may send and receive payments infrequently, the dedicated user's capital devoted to timeout-trees may generate few routing fees.
> As a result, casual users may have to pay significant fees for the creation of their Lightning channels (and/or for payments to or from those channels).
>
> However, the fees that casual users have to pay could be reduced if the capital in their channels could also be used for routing payments between other users.
> This can be accomplished by having the timeout-trees create hierarchical channels, each of which is owned by a single casual user and a pair of dedicated users [7].
> By using an idea created by Towns [10][11][3], a single unit of capital in each hierarchical channel can be used to route two independent payments of one unit each.
>
> Scalability
> ===========
>
> The above protocols can perform the following actions completely off-chain:
> * Lightning sends and receives, and
> * resizing of Lightning channels.
>
> Assuming:
> * 1 million hierarchical Lightning channels per timeout-tree,
> * a 1,000-block (about a week) to_self_delay parameter for dedicated users, and
> * a 10,000-block (about 69 days) to_self_delay parameter for casual users, and
> * 121,000 blocks (about 2.3 years) from the creation of each timeout-tree to its expiry,
>
> a single 1-input/2-output transaction per block provides:
> * 11 Lightning channels per casual user to each of 10 billion casual users [3].
>
> Furthermore, given the above assumptions, a single 1-input/2-output transaction per block allows each casual user to:
> * close an existing Lightning channel,
> * open a new Lightning channel with a new partner, and
> * rebalance funds between Lightning and immediately-accessible off-chain bitcoin
> once every 10,000 blocks (about 69 days) [3].
>
> Of course, the above calculations don't mean that 10 billion casual Lightning users would create only 1 on-chain transaction per block.
> In reality, their on-chain footprint would be dominated by users who don't follow the protocol due to errors, unavailability, or malicious intent.
> The rate of such protocol violations is hard to predict, but it's likely that casual users' unavailability would be the most significant problem.
>
> Usability
> =========
>
> The above protocols have the following properties for casual users:
> * watchtower-freedom (that is, they accommodate months-long unavailability without requiring a watchtower service to secure the user's funds) ([5] Section 3.1),
> * one-shot receives (that is, receiving a payment does not require performing actions at multiple blockheights) ([5] Section 3.4),
> * asynchronous receives (that is, it's possible to receive a payment when the sender is offline) ([5] Section 3.6), and
> * tunable penalties for attempting to put an old state on-chain ([12]).
>
> Limitations
> ===========
>
> Finally, the above results depend on the following assumptions:
> 1) the cost of resolving an HTLC on-chain is less than the value of the HTLC,
> 2) transaction packages are relayed reliably from users to miners, and
> 3) there is a known upper bound on the delay from when a package is submitted to when it is included in the blockchain.
>
> These limitations, and ideas for how they can be addressed, are discussed further in the paper [3].
>
> Conclusions
> ===========
>
> With the current Bitcoin consensus rules, there are reasons to believe that the scalability of Lightning is inherently limited.
> However, simple covenants and timeout-trees can overcome these scalability limitations.
> In particular, CheckTemplateVerify (CTV) and/or AnyPrevOut (APO) could be used to dramatically increase the number of casual users who send and receive bitcoin in a trust-free manner.
> As a result, it's hoped that CTV, APO or a similar mechanism that enables simple covenants will be added to Bitcoin's consensus rules in order to allow Lightning to become a widely-used means of payment.
>
> Regards,
> John
>
> [1] BIP 119 CHECKTEMPLATEVERIFY, https://github.com/bitcoin/bips/blob/master/bip-0119.mediawiki
> [2] BIP 118 SIGHASH_ANYPREVOUT, https://anyprevout.xyz/
> [3] Law, "Scaling Lightning With Simple Covenants", https://github.com/JohnLaw2/ln-scaling-covenants
> [4] "BOLT (Basis Of Lightning Technology) specifications", https://github.com/lightningnetwork/lightning-rfc
> [5] Law, "Watchtower-Free Lightning Channels For Casual Users", https://github.com/JohnLaw2/ln-watchtower-free
> [6] Law, "Factory-Optimized Channel Protocols For Lightning", available at https://github.com/JohnLaw2/ln-factory-optimized.
> [7] Law, "Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://github.com/JohnLaw2/ln-hierarchical-channels
> [8] Burchert, Decker and Wattenhofer, "Scalable Funding of Bitcoin Micropayment Channel Networks", http://dx.doi.org/10.1098/rsos.180089
> [9] Law, "Scaling Bitcoin With Inherited IDs", https://github.com/JohnLaw2/btc-iids
> [10] Towns, "Re: Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-April/003913.html
> [11] Law, "Re: Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-April/003917.html
> [12] Law, "Lightning Channels With Tunable Penalties", https://github.com/JohnLaw2/ln-tunable-penalties
>
> 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
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] Scaling Lightning With Simple Covenants
2023-09-08 18:54 [bitcoin-dev] Scaling Lightning With Simple Covenants jlspc
2023-09-11 0:56 ` [bitcoin-dev] [Lightning-dev] " Anthony Towns
2023-09-11 2:13 ` [bitcoin-dev] " Rusty Russell
@ 2023-09-11 5:27 ` Antoine Riard
2023-09-17 0:59 ` jlspc
2023-09-17 11:32 ` Erik Aronesty
2023-09-18 4:14 ` ZmnSCPxj
3 siblings, 2 replies; 14+ messages in thread
From: Antoine Riard @ 2023-09-11 5:27 UTC (permalink / raw)
To: jlspc, Bitcoin Protocol Discussion; +Cc: lightning-dev
[-- Attachment #1: Type: text/plain, Size: 26666 bytes --]
Hi John,
Thanks for the proposal, few feedback after a first look.
> If Bitcoin and Lightning are to become widely-used, they will have to be adopted by casual users who want to send and receive bitcoin, but > who do not want to go to any effort in order to provide the infrastructure for making payments.
> Instead, it's reasonable to expect that the Lightning infrastructure will be provided by dedicated users who are far less numerous than
I don't know if it is that simple to classify expected users in
"casual"-vs"dedicated" and then design protocols accordingly. In
practice, if you take today Lightning as an example the trust
assumptions is more a matrix than a dichotomie, e.g you have the
choice between full-node vs light client to get block-relay,
large-sized mempool vs small mempool or no mempool at all for fee
estimations, routing HTLCs or not, running local watchtower or not...
without all those choices being necessarily interdependent. Generally,
I would say "tell me your IO disk/bandwidth/CPU performance/fees
ressources and level of technical knowledge and I'll tell you what
level of trust-minimization you can afford".
> This difference in numbers implies that the key challenge in scaling Bitcoin and Lightning is providing bitcoin and Lightning to casual
> users.
> As a result, the rest of this post will focus on this challenge.
I think few different scaling notions can be introduced to measure the
performance of an off-chain construction. Onboarding scaling defining
how many users can co-exist off-chain, considering throughput limits
(e.g blocksize, average block interval). Transactional scaling
defining how many transfers can be performed off-chain per on-chain
transaction, considering the properties of the off-chain system. Users
resource scaling defining how much resource a user should mobilize /
consume (e.g average weight cost for cooperative / non-cooperative
close) to make a trust-minimized usage of the off-chain construction.
I think the proposal is mainly considering onboarding scalability, i.e
maxing out the number of channels that can be owned by a user though
it is unclear if other scalability dimensions are weighted in.
In particular, no known protocol that uses the current Bitcoin
consensus rules allows a large number (e.g., tens-of-thousands to
millions) of Lightning channels, each co-owned by a casual user, to be
created from a single on-chain unspent transaction output (UTXO).
I’m not sure if this statement is 100% accurate. One could create a
radixpool with replacing CTV usage with Musig2 where the end
transactions outputs bear Lightning channel:
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-June/017968.html.
Of course there is no N-party update mechanism to rebalance the
channel internally and it’s a nightmare if a subranch of transactions
with some depth hit the chain, though I think it works with today
Bitcoin consensus rules.
The requirement for casual users to sign transactions that specify the
exact set of casual users whose signatures are required creates a very
difficult group coordination problem that's not well-suited to the
behavior of casual users [9, Section 2.2].
I think you have two more precise problems designated under this group
coordination problem. One is the dynamic novation of this group, i.e
how you add / remove user, if possible in a compact fashion. The
second the dynamic update of the “account” / channels owned by the
users of this group, if possible with minimal interactivity.
> On the other hand, sometime shortly before E, casual user A_i can use the Lightning Network to send all of their balance in the channel > > (A_i, B) to themselves in some other Lightning channel that is the leaf of some other timeout-tree.
I think there is an uncertainty in this model as there is no guarantee
that you have a dedicated user ready to be the gateway to route the
balance, neither the dedicated user have adequate channel topology
allowing to send the funds in the part of the network you wish to do
so. And this is unclear what the casual user is left to do if an
intermediate hop withhold the HTLC in-flight until the timeout-tree
mature in favor of the dedicated user, iiuc.
So I think draining is uncertain in a world where jamming is possible,
even assuming economic mitigation as one might earn more to jam a
casual user draining than loosing in jamming upfront fees.
> Of course, sometime between E - to_self_delay_i and E, A_i should verify that B has created such a new timeout-tree.
I think this requirement is altering the design goal introduced at
first on casual users “performing actions at specific times in the
future” as from my understanding there is no guarantee B broadcast an
on-chain transaction triggering the move of A funds to the new
timeout-tree. This becomes unclear when A should take correction
actions like broadcasting its own control transaction (?) when B fails
to dos, especially in a world where you have mempool congestion, and
earlier you’re better it might in term of fee risk.
> Fortunately, timeout-trees can be used to provide casual users with immediately-accessible off-chain bitcoin in addition to bitcoin in
I think this is unclear what is meant by “immediately-accessible”
here, if they’re confirmed or not. Pre-signed / pre-committed
transactions at a fixed feerate might still not propagate on the
network, due to mempool min fee, and the user might have to take
actions in consequence like access hot wallet and sign a CPFP.
> In reality, their on-chain footprint would be dominated by users who don't follow the protocol due to errors, unavailability, or malicious > intent.
The fault-tolerance of such off-chain construction is very unclear i.e
if for any unavailable or erring user the whole off-chain construction
ends up on-chain. This is one significant defect in my opinion of the
radixpool or old school apo channel factory (or even coinpool if no
time-locked kick-out transaction is used), if one user becomes
unresponsive after a while.
Best,
Antoine
Le ven. 8 sept. 2023 à 20:18, jlspc via bitcoin-dev <
bitcoin-dev@lists•linuxfoundation.org> a écrit :
> TL;DR
> =====
> * The key challenge in scaling Lightning in a trust-free manner is the creation of Lightning channels for casual users.
> - It appears that signature-based factories are inherently limited to creating at most tens or hundreds of Lightning channels per UTXO.
> - In contrast, simple covenants (including those enabled by CTV [1] or APO [2]) would allow a single UTXO to create Lightning channels for millions of casual users.
> * The resulting covenant-based protocols also:
> - support resizing channels off-chain,
> - use the same capital to simultaneously provide in-bound liquidity to casual users and route unrelated payments for other users,
> - charge casual users tunable penalties for attempting to put an old state on-chain, and
> - allow casual users to monitor the blockchain for just a few minutes every few months without employing a watchtower service.
> * As a result, adding CTV and/or APO to Bitcoin's consensus rules would go a long way toward making Lightning a widely-used means of payment.
>
> Overview
> ========
>
> Many proposed changes to the Bitcoin consensus rules, including CheckTemplateVerify (CTV) [1] and AnyPrevOut (APO) [2], would support covenants.
> While covenants have been shown to improve Bitcoin in a number of ways, scalability of Lightning is not typically listed as one of them.
> This post argues that any change (including CTV and/or APO) that enables even simple covenants greatly improves Lightning's scalability, while meeting the usability requirements of casual users.
> A more complete description, including figures, is given in a paper [3].
>
> The Scalability Problem
> =======================
>
> If Bitcoin and Lightning are to become widely-used, they will have to be adopted by casual users who want to send and receive bitcoin, but who do not want to go to any effort in order to provide the infrastructure for making payments.
> Instead, it's reasonable to expect that the Lightning infrastructure will be provided by dedicated users who are far less numerous than the casual users.
> In fact, there are likely to be tens-of-thousands to millions of casual users per dedicated user.
> This difference in numbers implies that the key challenge in scaling Bitcoin and Lightning is providing bitcoin and Lightning to casual users.
> As a result, the rest of this post will focus on this challenge.
>
> Known Lightning protocols allow casual users to perform Lightning payments without:
> * maintaining high-availability,
> * performing actions at specific times in the future, or
> * having to trust a third-party (such as a watchtower service) [5][6].
>
> In addition, they support tunable penalties for casual users who attempt to put an old channel state on-chain (for example, due to a crash that causes a loss of state).
> As a result, these protocols meet casual users' needs and could become widely-used for payments if they were sufficiently scalable.
>
> The Lightning Network lets users send and receive bitcoin off-chain in a trust-free manner [4].
> Furthermore, there are Lightning protocols that allow Lightning channels to be resized off-chain [7].
> Therefore, making Lightning payments and resizing Lightning channels are highly scalable operations.
>
> However, providing Lightning channels to casual users is not scalable.
> In particular, no known protocol that uses the current Bitcoin consensus rules allows a large number (e.g., tens-of-thousands to millions) of Lightning channels, each co-owned by a casual user, to be created from a single on-chain unspent transaction output (UTXO).
> As a result, being able to create (and close) casual users' Lightning channels remains the key bottleneck in scaling Lightning.
>
> Casual Users And Signatures
> ===========================
>
> Unfortunately, there are good reasons to believe this bottleneck is unavoidable given the current Bitcoin consensus rules.
> The problem is that in order for a casual user to co-own a Lightning channel, they must co-own an on-chain UTXO [8].
> Therefore, if a large number of casual users are to each co-own a Lightning channel, all of which are funded by a single UTXO, that UTXO must require signatures from all of those casual users.
>
> In practice, the problem is much harder than just getting signatures from a large number of casual users, as the signatures themselves depend on the exact set of casual users whose signatures are required.
> For example, if a UTXO requires signatures from a set of 1,000 casual users and if 999 of them sign but one does not, the 999 signatures that were obtained can't be used.
> Instead, one has to start all over again, say with a new UTXO that requires signatures from the 999 users that signed the previous time.
> However, if not all of those 999 sign, the signatures that were obtained in the second try are also unusable.
>
> The requirement for casual users to sign transactions that specify the exact set of casual users whose signatures are required creates a very difficult group coordination problem that's not well-suited to the behavior of casual users [9, Section 2.2].
> As a result, while a channel factory could be used to fund channels for perhaps 10 or even 100 casual users, it's very unlikely that any protocol using the current Bitcoin consensus rules can fund tens-of-thousands to millions of channels from a single UTXO.
>
> Simple Covenants And Timeout-Trees
> ==================================
>
> On the other hand, if the consensus rules are changed to allow even simple covenants, this scaling bottleneck is eliminated.
> The key observation is that with covenants, a casual user can co-own an off-chain Lightning channel without having to sign all (or any) of the transactions on which it depends.
> Instead, a UTXO can have a covenant that guarantees the creation of the casual user's channel.
> The simplest way to have a single UTXO create channels for a large number of casual users is to put a covenant on the UTXO that forces the creation of a tree of transactions, the leaves of which are the casual users' channels.
>
> While such a covenant tree can create channels for millions of casual users without requiring signatures or solving a difficult group coordination problem, it's not sufficient for scaling.
> The problem is that each channel created by a covenant tree has a fixed set of owners, and changing the ownership of a channel created by a covenant tree requires putting the channel on-chain.
> Therefore, assuming that all casual users will eventually want to pair with different dedicated users (and vice-versa), the covenant tree doesn't actually provide any long-term scaling benefit.
>
> Fortunately, real long-term scaling can be achieved by adding a deadline after which all non-leaf outputs in the covenant tree can be spent without having to meet the conditions of the covenant.
> The resulting covenant tree is called a "timeout-tree" [9, Section 5.3].
>
> Let A_1 ... A_n denote a large number of casual users, let B be a dedicated user, and let E denote some fixed time in the future.
> User B creates a timeout-tree with expiry E where:
> * leaf i has an output that funds a Lightning channel owned by A_i and B, and
> * after time E, each non-leaf output in the covenant tree can also be spent by user B without having to meet the conditions of the covenant.
>
> Thus, any time before E, casual user A_i can put the Lightning channel (A_i, B) on-chain by putting all of its ancestors in the timeout-tree on-chain.
> Once (A_i, B) is on-chain, the expiry E has no effect so A_i and B can continue to use the Lightning channel to send and receive payments from and to A_i.
>
> On the other hand, sometime shortly before E, casual user A_i can use the Lightning Network to send all of their balance in the channel (A_i, B) to themselves in some other Lightning channel that is the leaf of some other timeout-tree.
> More precisely, casual user A_i should rollover their balance by sending it from a given timeout-tree between time E - to_self_delay_i and time E, where E is the timeout-tree's expiry and to_self_delay_i is A_i's Lightning channel safety parameter.
> Note that to_self_delay_i can be in the range of 1 to 3 months if a watchtower-free channel protocol is used [5][6], so performing the drain within this time window does not put an unreasonable availability requirement on A_i.
>
> If all casual users drain their balances from the timeout-tree before E, then after E dedicated user B can create a new timeout-tree, with leaves that create Lightning channels for a new set of casual users, by putting a single transaction on-chain that spends the UTXO which created the expired timeout-tree.
> In this case, all n of the old Lightning channels are closed and n new channels are created with a single on-chain transaction.
>
> Of course, it's possible that some casual users will put their Lightning channel in the old timeout-tree on-chain, while others will drain their balance from the timeout-tree before E.
> In this case, user B can create a new timeout-tree that's funded by the non-leaf outputs of the old timeout-tree that have been put on-chain.
> While this results in a larger on-chain footprint than the case in which all casual users drain their balances from the old timeout-tree, it can still provide substantial scaling as long as the number of leaves put on-chain is small (in particular, well below n/(log n)).
> By creating incentives that reward users who drain their balances from the timeout-tree rather than putting their channels on-chain, almost all leaves will stay off-chain and good scalability will be achieved.
>
> Passive Rollovers For Casual Users
> ==================================
>
> The timeout-trees defined above don't place unreasonable availability requirements on casual users and they allow a very large number of casual users to obtain a Lightning channel with a single on-chain transaction.
> However, there are two problems with forcing casual users to drain their balances from an old timeout-tree to a new timeout-tree before the old timeout-tree's expiry:
> 1) if a casual user fails to perform the required drain before the old timeout-tree's expiry (due to unexpected unavailability), they lose all of their funds in the timeout-tree, and
> 2) if the dedicated user B is unavailable when a casual user attempts to drain their funds prior to the timeout-tree's expiry, the casual user will put their timeout-tree leaf on-chain (thus increasing the on-chain footprint and limiting scalability).
> This second problem matters, as a casual user should only have to devote a short period (e.g., 10 minutes) every few months to performing the drain, so even a short period of unavailability by the dedicated user could force the casual user to go on-chain.
>
> Instead, it would be preferable if the dedicated user could facilitate the rollover of the casual user's funds from a timeout-tree that's about to expire to another one without requiring input from the casual user.
> This can be achieved by using a variation of the FFO-WF Lightning channel protocol [6].
> The FFO-WF protocol uses control transactions to determine the current state of the Lightning channel and the resolution of any outstanding HTLCs, and these control transactions determine how the channel's value transactions disperse the channel's funds.
>
> As a result, just prior to E - to_self_delay_i, B can create a new timeout-tree that funds a new Lightning channel with casual user A_i where the new channel is controlled by A_i's *same* control transactions (thus allowing A_i to obtain their funds from either the old or new Lightning channel, but not from both).
> Therefore, once the old timeout-tree expires, A_i can still access their funds in the new timeout-tree's Lightning channel without having to perform any actions.
> Of course, sometime between E - to_self_delay_i and E, A_i should verify that B has created such a new timeout-tree.
>
> In addition, HTLCs can be handled so that rolling over the casual user's funds from one timeout-tree to another does not require any actions from the casual user.
> The details are given in the paper [3].
>
> Off-Chain bitcoin
> =================
>
> The Lightning Network lets casual users send and receive bitcoin entirely off-chain
> However, the casual user has to wait (for a period of time specified by their Lightning partner's to_self_delay parameter) before they can access their Lightning funds on-chain.
> This is problematic, as accessing one's Lightning funds on-chain requires paying fees to put transactions on-chain, and those fees cannot be paid using one's Lightning funds (due to the delay mentioned above).
> Thus, while Lightning can be used for most of a user's funds, the user must also be able to access some bitcoin (enough to pay transaction fees) without any delays.
>
> Fortunately, timeout-trees can be used to provide casual users with immediately-accessible off-chain bitcoin in addition to bitcoin in Lightning channels.
> Furthermore, it's possible to use a control output owned by a casual user to rollover the casual user's immediately-accessible bitcoin from one timeout-tree to the next along with their Lightning funds [3].
> In fact, this rollover can also be done without requiring any actions from the casual user and it can be used to rebalance the fraction of the user's funds that are immediately-accessible versus within Lightning [3].
>
> Control UTXOs
> =============
>
> The FFO-WF protocol (as adapted for timeout-trees) requires that each casual user own an independent UTXO that is spent by that user's control transactions.
> Creating an on-chain UTXO for every casual user could require a significant on-chain footprint, thus limiting scalability.
> Instead, each casual user can be given an off-chain UTXO that is created by a leaf of a tree of off-chain transactions defined by covenants [3].
>
> Improving Capital Efficiency
> ============================
>
> In order to rollover funds from one timeout-tree to another, the dedicated user creating those timeout-trees must fund both the old and new timeout-trees simultaneously, even though they only create one timeout-tree's worth of Lightning channel capacity.
> Fortunately, this overhead can be made very small by funding multiple timeout-trees in a staggered fashion, where only one has to be rolled-over at a time [3].
>
> Also, because casual users may send and receive payments infrequently, the dedicated user's capital devoted to timeout-trees may generate few routing fees.
> As a result, casual users may have to pay significant fees for the creation of their Lightning channels (and/or for payments to or from those channels).
>
> However, the fees that casual users have to pay could be reduced if the capital in their channels could also be used for routing payments between other users.
> This can be accomplished by having the timeout-trees create hierarchical channels, each of which is owned by a single casual user and a pair of dedicated users [7].
> By using an idea created by Towns [10][11][3], a single unit of capital in each hierarchical channel can be used to route two independent payments of one unit each.
>
> Scalability
> ===========
>
> The above protocols can perform the following actions completely off-chain:
> * Lightning sends and receives, and
> * resizing of Lightning channels.
>
> Assuming:
> * 1 million hierarchical Lightning channels per timeout-tree,
> * a 1,000-block (about a week) to_self_delay parameter for dedicated users, and
> * a 10,000-block (about 69 days) to_self_delay parameter for casual users, and
> * 121,000 blocks (about 2.3 years) from the creation of each timeout-tree to its expiry,
>
> a single 1-input/2-output transaction per block provides:
> * 11 Lightning channels per casual user to each of 10 billion casual users [3].
>
> Furthermore, given the above assumptions, a single 1-input/2-output transaction per block allows each casual user to:
> * close an existing Lightning channel,
> * open a new Lightning channel with a new partner, and
> * rebalance funds between Lightning and immediately-accessible off-chain bitcoin
> once every 10,000 blocks (about 69 days) [3].
>
> Of course, the above calculations don't mean that 10 billion casual Lightning users would create only 1 on-chain transaction per block.
> In reality, their on-chain footprint would be dominated by users who don't follow the protocol due to errors, unavailability, or malicious intent.
> The rate of such protocol violations is hard to predict, but it's likely that casual users' unavailability would be the most significant problem.
>
> Usability
> =========
>
> The above protocols have the following properties for casual users:
> * watchtower-freedom (that is, they accommodate months-long unavailability without requiring a watchtower service to secure the user's funds) ([5] Section 3.1),
> * one-shot receives (that is, receiving a payment does not require performing actions at multiple blockheights) ([5] Section 3.4),
> * asynchronous receives (that is, it's possible to receive a payment when the sender is offline) ([5] Section 3.6), and
> * tunable penalties for attempting to put an old state on-chain ([12]).
>
> Limitations
> ===========
>
> Finally, the above results depend on the following assumptions:
> 1) the cost of resolving an HTLC on-chain is less than the value of the HTLC,
> 2) transaction packages are relayed reliably from users to miners, and
> 3) there is a known upper bound on the delay from when a package is submitted to when it is included in the blockchain.
>
> These limitations, and ideas for how they can be addressed, are discussed further in the paper [3].
>
> Conclusions
> ===========
>
> With the current Bitcoin consensus rules, there are reasons to believe that the scalability of Lightning is inherently limited.
> However, simple covenants and timeout-trees can overcome these scalability limitations.
> In particular, CheckTemplateVerify (CTV) and/or AnyPrevOut (APO) could be used to dramatically increase the number of casual users who send and receive bitcoin in a trust-free manner.
> As a result, it's hoped that CTV, APO or a similar mechanism that enables simple covenants will be added to Bitcoin's consensus rules in order to allow Lightning to become a widely-used means of payment.
>
> Regards,
> John
>
> [1] BIP 119 CHECKTEMPLATEVERIFY, https://github.com/bitcoin/bips/blob/master/bip-0119.mediawiki
> [2] BIP 118 SIGHASH_ANYPREVOUT, https://anyprevout.xyz/
> [3] Law, "Scaling Lightning With Simple Covenants", https://github.com/JohnLaw2/ln-scaling-covenants
> [4] "BOLT (Basis Of Lightning Technology) specifications", https://github.com/lightningnetwork/lightning-rfc
> [5] Law, "Watchtower-Free Lightning Channels For Casual Users", https://github.com/JohnLaw2/ln-watchtower-free
> [6] Law, "Factory-Optimized Channel Protocols For Lightning", available at https://github.com/JohnLaw2/ln-factory-optimized.
> [7] Law, "Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://github.com/JohnLaw2/ln-hierarchical-channels
> [8] Burchert, Decker and Wattenhofer, "Scalable Funding of Bitcoin Micropayment Channel Networks", http://dx.doi.org/10.1098/rsos.180089
> [9] Law, "Scaling Bitcoin With Inherited IDs", https://github.com/JohnLaw2/btc-iids
> [10] Towns, "Re: Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-April/003913.html
> [11] Law, "Re: Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-April/003917.html
> [12] Law, "Lightning Channels With Tunable Penalties", https://github.com/JohnLaw2/ln-tunable-penalties
>
>
>
> 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: 31337 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] [Lightning-dev] Scaling Lightning With Simple Covenants
2023-09-11 0:56 ` [bitcoin-dev] [Lightning-dev] " Anthony Towns
@ 2023-09-17 0:52 ` jlspc
2023-11-15 19:59 ` jlspc
1 sibling, 0 replies; 14+ messages in thread
From: jlspc @ 2023-09-17 0:52 UTC (permalink / raw)
To: Anthony Towns; +Cc: Bitcoin Protocol Discussion, lightning-dev
Hi aj,
I completely agree with your observation that there's an important trust/safety vs. capital-efficiency tradeoff, and I almost completely agree with your analysis.
> (There are probably ways around this with additional complexity: eg,
> you could peer with a dedicated node, and have the timeout path be
> "you+them+timeout", so that while you could steal from casual users who
> don't rollover, you can't steal from your dedicated peer, so that $4.5B
> could be rolled into a channel with them, and used for routing)
Yes, that would work, but I think it's better to have dedicated user B pair with another dedicated user C such that each leaf of the timeout-tree funds a hierarchical channel [1] of the
form (A_i, (B, C)), where A_i is a casual user.
If A_i performs an active rollover, all funds not owned by A_i can *always* be used by B and C to route payments that are unrelated to the casual users in the timeout-tree (including both before and after A_i's funds are drained).
This idea was described in the "Improving Capital Efficiency" section of the post.
Passive rollovers complicate this, as A_i's funds are neither definitely in the old timeout-tree or in the new timeout-tree during the rollover.
However, if one is willing to take on the complexity, it's possible to use *your* (very cool!) idea of funding an HTLC from one of two possible sources, where one of those sources is guaranteed to eventually be available (but the offerer and offeree of the HTLC don't know which one will be available to them) [2][3].
In this case, B and C could use the funds from the old and the new timeout-trees that are not owned by A_i to route payments.
If A_i puts the leaf in the old timeout-tree on-chain, B and C use funds from the new timeout-tree to fund their HTLC (and vice-versa).
Even if hierarchical channels are used to improve the capital efficiency, I think the "thundering herd" problem is a big concern.
This could play out very poorly in practice, as casual users would gain experience with ever larger timeout-trees and not have any problems.
Then, suddenly, a large number of dedicated users collude by failing to roll-over timeout-trees at the same time, and they create enough congestion on the blockchain that they're able to steal a large fraction of the casual users' funds.
I have a proposed change to the Bitcoin consensus rules that I think could address this problem.
Basically, rather than have timeout-trees expire at a given block height, they should expire only after a sufficient number of low-fee blocks have been added to the blockchain after some given block height.
As a result, if dedicated users colluded and tried to steal funds by not rolling-over a group of timeout-trees, the thundering herd of transactions from casual users would push up the fees enough to prevent the timeout-trees from expiring, thus safeguarding the casual user's funds.
In fact, the impact to the dedicated users (in addition to their loss of reputation) would be that their capital would be unavailable to them for a longer period of time.
Thus, this should be effective in deterring dedicated users from attempting such a theft.
On the other hand, when the dedicated users do roll-over funds correctly, there is no delay in the old timeout-trees' expiries, and thus better capital efficiency.
There are lots of details to the idea and I'm currently in the process of writing a paper and post describing it.
A couple more quick details:
* rather than counting low-fee blocks, time is measured in low-fee windows, where the size of the window is programmable (this makes it much harder for dishonest miners to collude with the dedicated users by creating enough fake low-fee blocks, not containing the casual users' higher-fee timeout-tree transactions, to enabe the theft; it also reduces the compute cost for counting the low-fee windows),
* the threshold for a "low-fee" block is programmable,
* there is a bound on how long one keeps waiting for low-fee windows (in order to bound the storage and compute overheads), and
* a similar technique supports relative, rather than absolute, delays.
I think such a mechanism is likely to be useful in many areas, including HTLCs, but that timeout-trees really highlight the need for something like this.
Regards,
John
[1] Law, "Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://github.com/JohnLaw2/ln-hierarchical-channels
[2] Towns, "Re: Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-April/003913.html
[3] Law, "Re: Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-April/003917.html
Sent with Proton Mail secure email.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] Scaling Lightning With Simple Covenants
2023-09-11 2:13 ` [bitcoin-dev] " Rusty Russell
@ 2023-09-17 0:56 ` jlspc
0 siblings, 0 replies; 14+ messages in thread
From: jlspc @ 2023-09-17 0:56 UTC (permalink / raw)
To: Rusty Russell; +Cc: Bitcoin Protocol Discussion, lightning-dev
Hi Rusty,
> I've read the start of the paper on my vacation, and am still
> digesting it. But even so far, it presents some delightful
> possibilities.
Great!
> As with some other proposals, it's worth noting that the cost of
> enforcement is dramatically increased. It's no longer one or two txs,
> it's 10+. If the "dedicated user" contributes some part of the expected
> fee, the capital efficiency is reduced (and we're back to "how much is
> enough?").
Yes, this is certainly an issue, and it affects both settling the channel on-chain and resolving HTLCS on-chain.
The paper has a few ideas about how "short-cut" transactions could be used to address the cost of enforcing HTLCs on-chain.
It may be possible to do something similar for the channel itself, but that's more complex because of the value included in the channel and the potential for channels with different capacities in a single timeout-tree.
> But worst case (dramatic dedicated user failure) it's only a 2x penalty
> on number of onchain txs, which seems acceptable if the network is
> sufficiently mature that these failure events are rare.
> Note also that the (surprisingly common!) "user goes away" case where
> the casual user fails to rollover only returns funds to the dedicated
> user; relying on legal and normal custody policies in this case may be
> preferable to an eternal burden on the UTXO set with the current
> approach!
Agreed.
Thanks,
John
> Thankyou!
> Rusty.
Sent with Proton Mail secure email.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] Scaling Lightning With Simple Covenants
2023-09-11 5:27 ` Antoine Riard
@ 2023-09-17 0:59 ` jlspc
2023-09-26 16:42 ` Antoine Riard
2023-09-17 11:32 ` Erik Aronesty
1 sibling, 1 reply; 14+ messages in thread
From: jlspc @ 2023-09-17 0:59 UTC (permalink / raw)
To: Antoine Riard; +Cc: Bitcoin Protocol Discussion, lightning-dev
[-- Attachment #1: Type: text/plain, Size: 11829 bytes --]
Hi Antoine,
Thanks for your note. Responses are in-line below:
> Hi John,
> Thanks for the proposal, few feedback after a first look.
> ><i> If Bitcoin and Lightning are to become widely-used, they will have to be adopted by casual users who want to send and receive bitcoin, but > who do not want to go to any effort in order to provide the infrastructure for making payments.
> </i>><i> Instead, it's reasonable to expect that the Lightning infrastructure will be provided by dedicated users who are far less numerous than
> </i>
> I don't know if it is that simple to classify expected users in
> "casual"-vs"dedicated" and then design protocols accordingly. In
> practice, if you take today Lightning as an example the trust
> assumptions is more a matrix than a dichotomie, e.g you have the
> choice between full-node vs light client to get block-relay,
> large-sized mempool vs small mempool or no mempool at all for fee
> estimations, routing HTLCs or not, running local watchtower or not...
> without all those choices being necessarily interdependent. Generally,
> I would say "tell me your IO disk/bandwidth/CPU performance/fees
> ressources and level of technical knowledge and I'll tell you what
> level of trust-minimization you can afford".
Fair enough.
I'm sure there are users with a wide range of expertise, resources, and interest in supporting Bitcoin.
My main point is that there's a huge pool of potential users that just want payments to work, and they don't want to devote time or hardware resources to making them work (if they can get away with that).
I also think we should do whatever we can to meet their needs.
> ><i> This difference in numbers implies that the key challenge in scaling Bitcoin and Lightning is providing bitcoin and Lightning to casual
> </i>
> ><i> users.
> </i>><i> As a result, the rest of this post will focus on this challenge.
> </i>
> I think few different scaling notions can be introduced to measure the
> performance of an off-chain construction. Onboarding scaling defining
> how many users can co-exist off-chain, considering throughput limits
> (e.g blocksize, average block interval). Transactional scaling
> defining how many transfers can be performed off-chain per on-chain
> transaction, considering the properties of the off-chain system. Users
> resource scaling defining how much resource a user should mobilize /
> consume (e.g average weight cost for cooperative / non-cooperative
> close) to make a trust-minimized usage of the off-chain construction.
> I think the proposal is mainly considering onboarding scalability, i.e
> maxing out the number of channels that can be owned by a user though
> it is unclear if other scalability dimensions are weighted in.
Yes, exactly.
I've focused on providing multiple channels to as many casual users as possible.
In terms of other scalability dimensions, I think Lightning does a great job of providing a nearly unbounded number of payments per channel, without requiring on-chain transactions (once the channel is created).
I also think resizing channels can be done fairly effectively off-chain with hierarchical channels [1] (and even better with hierarchical channels within timeout-trees).
> In particular, no known protocol that uses the current Bitcoin
> consensus rules allows a large number (e.g., tens-of-thousands to
> millions) of Lightning channels, each co-owned by a casual user, to be
> created from a single on-chain unspent transaction output (UTXO).
> I’m not sure if this statement is 100% accurate. One could create a
> radixpool with replacing CTV usage with Musig2 where the end
> transactions outputs bear Lightning channel:
> <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-June/017968.html.">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-June/017968.html.</a>
> Of course there is no N-party update mechanism to rebalance the
> channel internally and it’s a nightmare if a subranch of transactions
> with some depth hit the chain, though I think it works with today
> Bitcoin consensus rules.
I agree that it's theoretically possible to use signatures to create Lightning channels for a million casual users that are funded by a single UTXO.
I just don't believe that that is possible in practice, due to the need to get a million casual users to sign a transaction where the transaction specifies the casual users that need to sign it.
> The requirement for casual users to sign transactions that specify the
> exact set of casual users whose signatures are required creates a very
> difficult group coordination problem that's not well-suited to the
> behavior of casual users [9, Section 2.2].
> I think you have two more precise problems designated under this group
> coordination problem. One is the dynamic novation of this group, i.e
> how you add / remove user, if possible in a compact fashion. The
> second the dynamic update of the “account” / channels owned by the
> users of this group, if possible with minimal interactivity.
Yes, changing who pairs with whom and resizing channels are both important problems.
I propose that changing pairings be done only via the creation and expiry of timeout-trees (with users that want to keep pairing with the same dedicated user(s) doing so via passive rollovers).
I propose that channel resizing is mainly done via hierarchical channels, with any resizing that's not possible to do off-chain in that manner being done via creation and expiry of timeout-trees.
With these proposals, it's possible to dramatically limit the interactivity.
For example, if every channel created by a timeout-tree is a hierarchical channel of the form:
* (casual user, (dedicated user, dedicated user)), or
* (dedicated user, (dedicated user, dedicated user)), or
* ((dedicated user, dedicated user), (dedicated user, dedicated user)),
then at most four users ever have to coordinate to update any channel, and at most one of those users is ever a casual user.
> ><i> On the other hand, sometime shortly before E, casual user A_i can use the Lightning Network to send all of their balance in the channel > > (A_i, B) to themselves in some other Lightning channel that is the leaf of some other timeout-tree.
> </i>
> I think there is an uncertainty in this model as there is no guarantee
> that you have a dedicated user ready to be the gateway to route the
> balance, neither the dedicated user have adequate channel topology
> allowing to send the funds in the part of the network you wish to do
> so. And this is unclear what the casual user is left to do if an
> intermediate hop withhold the HTLC in-flight until the timeout-tree
> mature in favor of the dedicated user, iiuc.
> So I think draining is uncertain in a world where jamming is possible,
> even assuming economic mitigation as one might earn more to jam a
> casual user draining than loosing in jamming upfront fees.
I agree that active draining by the casual user is uncertain.
I propose that if the active drain fails, the casual user should put their channel in the old timeout-tree on-chain (so that it won't timeout on them).
Sorry that wasn't clear.
> ><i> Of course, sometime between E - to_self_delay_i and E, A_i should verify that B has created such a new timeout-tree.
> </i>
> I think this requirement is altering the design goal introduced at
> first on casual users “performing actions at specific times in the
> future” as from my understanding there is no guarantee B broadcast an
> on-chain transaction triggering the move of A funds to the new
> timeout-tree. This becomes unclear when A should take correction
> actions like broadcasting its own control transaction (?) when B fails
> to dos, especially in a world where you have mempool congestion, and
> earlier you’re better it might in term of fee risk.
Ideally, I'd like casual users to only perform actions when they want to send or receive a payment.
Unfortunately, I don't know how to do that.
As a result, I've been forced to add a requirement that each casual user turns on their wallet software for a few minutes (but at a time of their choosing!) every few months (with the exact number of months being selected by the user) [2].
I agree this isn't ideal, but I think it's much better than having them have to perform some action at a specific time or within a very limited time window (such as a day or a week).
> ><i> Fortunately, timeout-trees can be used to provide casual users with immediately-accessible off-chain bitcoin in addition to bitcoin in
> </i>
> I think this is unclear what is meant by “immediately-accessible”
> here, if they’re confirmed or not. Pre-signed / pre-committed
> transactions at a fixed feerate might still not propagate on the
> network, due to mempool min fee, and the user might have to take
> actions in consequence like access hot wallet and sign a CPFP.
I agree that the bitcoin may not be obtained if the user hasn't signed and submitted a transaction with sufficient fees.
I tried to address this issue in the "Limitations" section of the post (specifically, Limitationss 2 and 3).
I think that getting a reliable transport mechanism for packages is critical.
Getting fees right could be particularly challenging due to the "thundering herd" problem, as _aj_ pointed out.
As I noted in my response to him, I think an additional change to Bitcoin that allows timing based on fee levels could be very helpful.
I'll try to write up the details and get that out as soon as possible.
> ><i> In reality, their on-chain footprint would be dominated by users who don't follow the protocol due to errors, unavailability, or malicious > intent.
> </i>
> The fault-tolerance of such off-chain construction is very unclear i.e
> if for any unavailable or erring user the whole off-chain construction
> ends up on-chain. This is one significant defect in my opinion of the
> radixpool or old school apo channel factory (or even coinpool if no
> time-locked kick-out transaction is used), if one user becomes
> unresponsive after a while.
With a timeout-tree, if the dedicated user(s) funding the tree is unavailable (or makes an error) and fails to rollover a given casual user, that casual user should put their channel in the old timeout-tree on-chain.
If the failure applies to all channels in the timeout-tree, the entire timeout-tree will be forced to go on-chain (thus doubling the number of on-chain transactions as compared to just putting the channels on-chain directly, without a timeout-tree).
Sorry this wasn't made clear.
These costs could be large, but hopefully they're rare as they are failures by dedicated users that can afford to have highly-available hardware and who want to maintain a good reputation.
Separately, HTLCs that are not resolved off-chain have to be put on-chain, but doing so does not force the timeout-tree itself to go on-chain.
If the HTLC control transactions are funded via zero-valued covenant trees (as proposed in the post and paper), putting an HTLC transaction on-chain can also require putting its ancestors in the covenant tree on-chain (thus creating a blow-up that is logarithmic in the number of leaves in the covenant tree).
However, the paper has a proposal for the use of "short-cut" transactions that may be able to eliminate this logarithmic blow-up.
Thanks for your thoughtful comments and please let me know if there's anything else that wasn't clear.
Regards,
John
> Best,
> Antoine
[1] Law, "Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://github.com/JohnLaw2/ln-hierarchical-channels
[2] Law, "Watchtower-Free Lightning Channels For Casual Users", https://github.com/JohnLaw2/ln-watchtower-free
Sent with [Proton Mail](https://proton.me/) secure email.
>>
[-- Attachment #2: Type: text/html, Size: 13449 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] Scaling Lightning With Simple Covenants
2023-09-11 5:27 ` Antoine Riard
2023-09-17 0:59 ` jlspc
@ 2023-09-17 11:32 ` Erik Aronesty
2023-09-19 7:44 ` ZmnSCPxj
1 sibling, 1 reply; 14+ messages in thread
From: Erik Aronesty @ 2023-09-17 11:32 UTC (permalink / raw)
To: Antoine Riard, Bitcoin Protocol Discussion; +Cc: lightning-dev
[-- Attachment #1: Type: text/plain, Size: 167 bytes --]
>
> replacing CTV usage with Musig2
>
>
this changes the trust model to a federated one vs trustless and also
increases the on-chain footprint of failure, correct?
>
[-- Attachment #2: Type: text/html, Size: 631 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] Scaling Lightning With Simple Covenants
2023-09-08 18:54 [bitcoin-dev] Scaling Lightning With Simple Covenants jlspc
` (2 preceding siblings ...)
2023-09-11 5:27 ` Antoine Riard
@ 2023-09-18 4:14 ` ZmnSCPxj
2023-09-28 15:56 ` jlspc
3 siblings, 1 reply; 14+ messages in thread
From: ZmnSCPxj @ 2023-09-18 4:14 UTC (permalink / raw)
To: jlspc; +Cc: Bitcoin Protocol Discussion, lightning-dev
Good morning John,
> On the other hand, if the consensus rules are changed to allow even simple covenants, this scaling bottleneck is eliminated.
> The key observation is that with covenants, a casual user can co-own an off-chain Lightning channel without having to sign all (or any) of the transactions on which it depends.
> Instead, a UTXO can have a covenant that guarantees the creation of the casual user's channel.
> The simplest way to have a single UTXO create channels for a large number of casual users is to put a covenant on the UTXO that forces the creation of a tree of transactions, the leaves of which are the casual users' channels.
>
> While such a covenant tree can create channels for millions of casual users without requiring signatures or solving a difficult group coordination problem, it's not sufficient for scaling.
> The problem is that each channel created by a covenant tree has a fixed set of owners, and changing the ownership of a channel created by a covenant tree requires putting the channel on-chain.
> Therefore, assuming that all casual users will eventually want to pair with different dedicated users (and vice-versa), the covenant tree doesn't actually provide any long-term scaling benefit.
>
> Fortunately, real long-term scaling can be achieved by adding a deadline after which all non-leaf outputs in the covenant tree can be spent without having to meet the conditions of the covenant.
> The resulting covenant tree is called a "timeout-tree" [9, Section 5.3].
>
> Let A_1 ... A_n denote a large number of casual users, let B be a dedicated user, and let E denote some fixed time in the future.
> User B creates a timeout-tree with expiry E where:
> * leaf i has an output that funds a Lightning channel owned by A_i and B, and
> * after time E, each non-leaf output in the covenant tree can also be spent by user B without having to meet the conditions of the covenant.
I think, based solely on the description above, that it is not safe for dedicated user `B` to create this, unless it gets a signature from `A_i`.
Basically, suppose the entire thing is single-funded from `B`.
(Funding from `A_i` requires that each `A_i` that wants to contribute be online at the time, at which point you might as well just use signatures instead of `OP_CHECKTEMPLATEVERIFY`.)
If a particular `A_i` never contacts `B` but *does* get the entire path from the funding TXO to the `A_i && B` output confirmed, then the funds that `B` allocated are locked, ***unless*** `B` got a unilateral close signature from `A_i` to spend from `A_i && B`.
Thus, `A_i` still needs to be online at the time `B` signs the funding transaction that anchors the entire tree.
(This is why many people lost funds when they went and implemented `multifundchannel` by themselves --- you need to ensure that all the counterparties in the same batch of openingshave given you unilateral close signatures ***before*** you broadcast the funding transaction.
And in principle, whether the channels are represented onchain by a single transaction output, or multiple separate ones on the same transaction, is immaterial --- the funder still needs a unilateral close signature from the fundee.)
The alternative is to also infect the leaf itself with a lifetime `(A_i && B) || (B && CLTV)`.
This is essentially a Spilman channel variant, which is what we use in swap-in-potentiam, BTW.
If so, then `B` can dedicate that leaf output to a separate 1-input 1-output transaction that takes the `(A_i && B)` branch and spends to a plain `A && B` Lightning channel.
`B` can fund the tree, then when `A_i` comes online and is wiling to accept the channel from `B`, that is when `A_i` creates two signatures:
* For the transaction spending `(A_i && B) || (B && CLTV)` (taking the `A_i && B` branch) to spend to the `A && B`.
* For the unilateral close transaction from the above output.
Regards,
ZmnSCPxj
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] Scaling Lightning With Simple Covenants
2023-09-17 11:32 ` Erik Aronesty
@ 2023-09-19 7:44 ` ZmnSCPxj
0 siblings, 0 replies; 14+ messages in thread
From: ZmnSCPxj @ 2023-09-19 7:44 UTC (permalink / raw)
To: Erik Aronesty; +Cc: Bitcoin Protocol Discussion, lightning-dev
Good morning Erik,
> > replacing CTV usage with Musig2
>
>
> this changes the trust model to a federated one vs trustless and also increases the on-chain footprint of failure, correct?
As I understand it, no.
MuSig and MuSig2 are n-of-n signing algorithms.
The implied usage is that all entities `A_i` for all `i` and `B` dedicated LN node are in the n-of-n set.
The argument that 2-of-2 channels are non-custodial and trust-minimized extends to n-of-n for all n.
Regards,
ZmnSCPxj
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] Scaling Lightning With Simple Covenants
2023-09-17 0:59 ` jlspc
@ 2023-09-26 16:42 ` Antoine Riard
2023-10-06 16:26 ` jlspc
0 siblings, 1 reply; 14+ messages in thread
From: Antoine Riard @ 2023-09-26 16:42 UTC (permalink / raw)
To: jlspc; +Cc: Bitcoin Protocol Discussion, lightning-dev
[-- Attachment #1: Type: text/plain, Size: 18344 bytes --]
Hi John,
Thanks for the additional insightful comments. See new questions at the end.
> "My main point is that there's a huge pool of potential users that just
want payments to work, and they don't want to devote time or hardware
resources to making them work (if they can away with that)"
Sure, though somehow a "sovereign" casual user will still have to store
signatures and corresponding witnesses for off-chain balances at some
hardware somewhere, or delegate to another set of entities the storage or
on-chain broadcast (e.g watchtower). And then you start to have
interpedency with the timelocks of your off-chain construction and the
"bare minimum" witness space feerate average cost. All efficiency
considerations, ideally which can be laid out to reason on the trade-off of
off-chain constructions.
> "I also think resizing channels can be done fairly effectively off-chain
with hierarchical channels [1] (and even better with hierarchical channels
within timeout-trees)".
Yes, transactional scaling of Lightning (i.e how many transfers can be
performed off-chain per on-chain transaction) sounds good at first sight,
though in practice liquidity unbalance due to asymmetries in liquidity
flows among counterparties is a bottleneck. Note, how the on-chain
splicing for LSP spec upgrade improves on this dimension and where
"resizing" or "pool rebalancing" aims to keep this off-chain.
> "I just don't believe that is possible in practice, due to the need to
get a million casual users to sign a transaction where the transaction
specifies the casual users that need to sign it".
Well, this is not straightforward to pre-commit a subset of casual or
inactive users that need to sign (or do not need to sign). It sounds
achievable with current tree tricks like g'root or entroot for user groups
between 10-to-1000 (maybe more a full proposal would be needed to
estimate). Of course for orders of magnitude in the million, a more
efficient cryptographic accumulator than a Merkle tree would need to be
introduced at the consensus-level.
> "With these proposals, it's possible to dramatically limit the
interactivity".
Yes, from my rough understanding of timeout-trees and channel resizing, it
sounds to suffer from the same issue as Jeremy radix-tree's proposal or
Christian OG channel factory, namely the lack of fault-tolerance when one
of the casual user or end of tree balance owner aims to go on-chain. The
fragmentation cost sounds to be borne by all the users located in the tree
branch. Note fault-tolerance is one of the key payment pool design goals to
advance over factories.
> "I propose that if the active drain fails, the casual user should put
their channel in the old timeout-tree on-chain (so that it won't timeout on
them). "
I think there is still some issue there where you need to handle the
malicious HTLC-withholding case along your multi-hop payment paths and wait
for the expiration. Then go on-chain to expire the old timeout-tree, which
might come with a high timevalue cost by default. Not saying keeping
timevalue cost low is solved for today's Lightning.
> "I agree this isn't ideal, but I think it's much better than having them
have to perform some action at a specific time or within a very limited
time window (such as a day or a week)".
Yes, I think all the other off-chain constructions are encumbering the
casual users to perform some action within a very limited time window, and
as such requires strong liveliness (e.g to watch your counterparty
potential revoked commitment construction). This sounds to me a novel
aspect of TP-channel factories of allowing the casual user to decide when
they have to be on-time.
> "Getting fees right could be particularly challenging due to the
"thundering herd" problem, as _aj_ pointed out".
Yes, the thundering herd issue is explicitly mentioned in the OG Lightning
paper. To the best of my knowledge this is a distinct problem other than
exploitable asymmetries in local node policies and propagation, that it
cannot be fixed by transaction-relay changes.
> "These costs could be large, but hopefully they're rare as they are
failures by dedicated users that can afford to have highly-available
hardware and who want to maintain a good reputation".
Yes, though note as soon as a dedicated user starts to have a lot of
off-chain tree in the hand, and this is observable by adversaries the
dedicated user becomes an attack target (e.g for channel jamming or
time-dilation) which substantially alter the trade-offs.
> "However, the paper has a proposal for the use of "short-cut"
transactions that may be able to eliminate this logarithmic blow-up".
Yes "cut-through" to reduce on-chain footprint in mass exit cases has been
discussed since the early days of off-chain constructions and Taproot /
Grafroot introduction to the best of my knowledge, see:
https://tokyo2018.scalingbitcoin.org/transcript/tokyo2018/multi-party-channels-in-the-utxo-model-challenges-and-opportunities
Few questions from reading Dave's description of TP protocol here:
https://bitcoinops.org/en/newsletters/2023/03/29/#preventing-stranded-capital-with-multiparty-channels-and-channel-factories
.
In the scenario of multiple parties (e.g Alice, Bob, Caroll) owning a state
transaction + control output, what prevents Caroll to double-spend Bob's
revoked state transaction to a destination controlled by her in collusion
with Bob, at the harm of Alice ?
In the scenario of multiple commitment transactions spending the same state
transaction of an offliner user, what prevents Caroll to fake offliness and
equivocate at the harm of Alice or another party ?
Still building my understanding of the TP protocol security model and
seeing where it converges / diverges w.r.t other off-chain constructions
trade-offs.
Best,
Antoine
Le dim. 17 sept. 2023 à 01:59, jlspc <jlspc@protonmail•com> a écrit :
> Hi Antoine,
>
> Thanks for your note. Responses are in-line below:
>
> > Hi John,
>
> > Thanks for the proposal, few feedback after a first look.
>
> > ><i> If Bitcoin and Lightning are to become widely-used, they will have to be adopted by casual users who want to send and receive bitcoin, but > who do not want to go to any effort in order to provide the infrastructure for making payments.
> > </i>><i> Instead, it's reasonable to expect that the Lightning infrastructure will be provided by dedicated users who are far less numerous than
> > </i>
> > I don't know if it is that simple to classify expected users in
> > "casual"-vs"dedicated" and then design protocols accordingly. In
> > practice, if you take today Lightning as an example the trust
> > assumptions is more a matrix than a dichotomie, e.g you have the
> > choice between full-node vs light client to get block-relay,
> > large-sized mempool vs small mempool or no mempool at all for fee
> > estimations, routing HTLCs or not, running local watchtower or not...
> > without all those choices being necessarily interdependent. Generally,
> > I would say "tell me your IO disk/bandwidth/CPU performance/fees
> > ressources and level of technical knowledge and I'll tell you what
> > level of trust-minimization you can afford".
>
> Fair enough.
>
> I'm sure there are users with a wide range of expertise, resources, and interest in supporting Bitcoin.
> My main point is that there's a huge pool of potential users that just want payments to work, and they don't want to devote time or hardware resources to making them work (if they can get away with that).
> I also think we should do whatever we can to meet their needs.
>
> > ><i> This difference in numbers implies that the key challenge in scaling Bitcoin and Lightning is providing bitcoin and Lightning to casual
> > </i>
> > ><i> users.
> > </i>><i> As a result, the rest of this post will focus on this challenge.
> > </i>
> > I think few different scaling notions can be introduced to measure the
> > performance of an off-chain construction. Onboarding scaling defining
> > how many users can co-exist off-chain, considering throughput limits
> > (e.g blocksize, average block interval). Transactional scaling
> > defining how many transfers can be performed off-chain per on-chain
> > transaction, considering the properties of the off-chain system. Users
> > resource scaling defining how much resource a user should mobilize /
> > consume (e.g average weight cost for cooperative / non-cooperative
> > close) to make a trust-minimized usage of the off-chain construction.
> > I think the proposal is mainly considering onboarding scalability, i.e
> > maxing out the number of channels that can be owned by a user though
> > it is unclear if other scalability dimensions are weighted in.
>
> Yes, exactly.
> I've focused on providing multiple channels to as many casual users as possible.
>
> In terms of other scalability dimensions, I think Lightning does a great job of providing a nearly unbounded number of payments per channel, without requiring on-chain transactions (once the channel is created).
> I also think resizing channels can be done fairly effectively off-chain with hierarchical channels [1] (and even better with hierarchical channels within timeout-trees).
>
> > In particular, no known protocol that uses the current Bitcoin
> > consensus rules allows a large number (e.g., tens-of-thousands to
> > millions) of Lightning channels, each co-owned by a casual user, to be
> > created from a single on-chain unspent transaction output (UTXO).
>
> > I’m not sure if this statement is 100% accurate. One could create a
> > radixpool with replacing CTV usage with Musig2 where the end
> > transactions outputs bear Lightning channel:
> > <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-June/017968.html.">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2020-June/017968.html.</a>
>
> > Of course there is no N-party update mechanism to rebalance the
> > channel internally and it’s a nightmare if a subranch of transactions
> > with some depth hit the chain, though I think it works with today
> > Bitcoin consensus rules.
>
> I agree that it's theoretically possible to use signatures to create Lightning channels for a million casual users that are funded by a single UTXO.
> I just don't believe that that is possible in practice, due to the need to get a million casual users to sign a transaction where the transaction specifies the casual users that need to sign it.
>
> > The requirement for casual users to sign transactions that specify the
> > exact set of casual users whose signatures are required creates a very
> > difficult group coordination problem that's not well-suited to the
> > behavior of casual users [9, Section 2.2].
>
> > I think you have two more precise problems designated under this group
> > coordination problem. One is the dynamic novation of this group, i.e
> > how you add / remove user, if possible in a compact fashion. The
> > second the dynamic update of the “account” / channels owned by the
> > users of this group, if possible with minimal interactivity.
>
> Yes, changing who pairs with whom and resizing channels are both important problems.
>
> I propose that changing pairings be done only via the creation and expiry of timeout-trees (with users that want to keep pairing with the same dedicated user(s) doing so via passive rollovers).
> I propose that channel resizing is mainly done via hierarchical channels, with any resizing that's not possible to do off-chain in that manner being done via creation and expiry of timeout-trees.
>
> With these proposals, it's possible to dramatically limit the interactivity.
>
> For example, if every channel created by a timeout-tree is a hierarchical channel of the form:
> * (casual user, (dedicated user, dedicated user)), or
> * (dedicated user, (dedicated user, dedicated user)), or
> * ((dedicated user, dedicated user), (dedicated user, dedicated user)),
> then at most four users ever have to coordinate to update any channel, and at most one of those users is ever a casual user.
>
> > ><i> On the other hand, sometime shortly before E, casual user A_i can use the Lightning Network to send all of their balance in the channel > > (A_i, B) to themselves in some other Lightning channel that is the leaf of some other timeout-tree.
> > </i>
> > I think there is an uncertainty in this model as there is no guarantee
> > that you have a dedicated user ready to be the gateway to route the
> > balance, neither the dedicated user have adequate channel topology
> > allowing to send the funds in the part of the network you wish to do
> > so. And this is unclear what the casual user is left to do if an
> > intermediate hop withhold the HTLC in-flight until the timeout-tree
> > mature in favor of the dedicated user, iiuc.
>
> > So I think draining is uncertain in a world where jamming is possible,
> > even assuming economic mitigation as one might earn more to jam a
> > casual user draining than loosing in jamming upfront fees.
>
> I agree that active draining by the casual user is uncertain.
> I propose that if the active drain fails, the casual user should put their channel in the old timeout-tree on-chain (so that it won't timeout on them).
> Sorry that wasn't clear.
>
> > ><i> Of course, sometime between E - to_self_delay_i and E, A_i should verify that B has created such a new timeout-tree.
> > </i>
> > I think this requirement is altering the design goal introduced at
> > first on casual users “performing actions at specific times in the
> > future” as from my understanding there is no guarantee B broadcast an
> > on-chain transaction triggering the move of A funds to the new
> > timeout-tree. This becomes unclear when A should take correction
> > actions like broadcasting its own control transaction (?) when B fails
> > to dos, especially in a world where you have mempool congestion, and
> > earlier you’re better it might in term of fee risk.
>
> Ideally, I'd like casual users to only perform actions when they want to send or receive a payment.
> Unfortunately, I don't know how to do that.
> As a result, I've been forced to add a requirement that each casual user turns on their wallet software for a few minutes (but at a time of their choosing!) every few months (with the exact number of months being selected by the user) [2].
> I agree this isn't ideal, but I think it's much better than having them have to perform some action at a specific time or within a very limited time window (such as a day or a week).
>
> > ><i> Fortunately, timeout-trees can be used to provide casual users with immediately-accessible off-chain bitcoin in addition to bitcoin in
> > </i>
> > I think this is unclear what is meant by “immediately-accessible”
> > here, if they’re confirmed or not. Pre-signed / pre-committed
> > transactions at a fixed feerate might still not propagate on the
> > network, due to mempool min fee, and the user might have to take
> > actions in consequence like access hot wallet and sign a CPFP.
>
> I agree that the bitcoin may not be obtained if the user hasn't signed and submitted a transaction with sufficient fees.
> I tried to address this issue in the "Limitations" section of the post (specifically, Limitationss 2 and 3).
>
> I think that getting a reliable transport mechanism for packages is critical.
>
> Getting fees right could be particularly challenging due to the "thundering herd" problem, as _aj_ pointed out.
> As I noted in my response to him, I think an additional change to Bitcoin that allows timing based on fee levels could be very helpful.
> I'll try to write up the details and get that out as soon as possible.
>
> > ><i> In reality, their on-chain footprint would be dominated by users who don't follow the protocol due to errors, unavailability, or malicious > intent.
> > </i>
> > The fault-tolerance of such off-chain construction is very unclear i.e
> > if for any unavailable or erring user the whole off-chain construction
> > ends up on-chain. This is one significant defect in my opinion of the
> > radixpool or old school apo channel factory (or even coinpool if no
> > time-locked kick-out transaction is used), if one user becomes
> > unresponsive after a while.
>
> With a timeout-tree, if the dedicated user(s) funding the tree is unavailable (or makes an error) and fails to rollover a given casual user, that casual user should put their channel in the old timeout-tree on-chain.
> If the failure applies to all channels in the timeout-tree, the entire timeout-tree will be forced to go on-chain (thus doubling the number of on-chain transactions as compared to just putting the channels on-chain directly, without a timeout-tree).
> Sorry this wasn't made clear.
>
> These costs could be large, but hopefully they're rare as they are failures by dedicated users that can afford to have highly-available hardware and who want to maintain a good reputation.
>
> Separately, HTLCs that are not resolved off-chain have to be put on-chain, but doing so does not force the timeout-tree itself to go on-chain.
> If the HTLC control transactions are funded via zero-valued covenant trees (as proposed in the post and paper), putting an HTLC transaction on-chain can also require putting its ancestors in the covenant tree on-chain (thus creating a blow-up that is logarithmic in the number of leaves in the covenant tree).
> However, the paper has a proposal for the use of "short-cut" transactions that may be able to eliminate this logarithmic blow-up.
>
> Thanks for your thoughtful comments and please let me know if there's anything else that wasn't clear.
>
> Regards,
> John
>
> > Best,
>
> > Antoine
>
> [1] Law, "Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://github.com/JohnLaw2/ln-hierarchical-channels
> [2] Law, "Watchtower-Free Lightning Channels For Casual Users", https://github.com/JohnLaw2/ln-watchtower-free
>
>
>
>
> Sent with Proton Mail <https://proton.me/> secure email.
>
>
>>
>
[-- Attachment #2: Type: text/html, Size: 21100 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] Scaling Lightning With Simple Covenants
2023-09-18 4:14 ` ZmnSCPxj
@ 2023-09-28 15:56 ` jlspc
0 siblings, 0 replies; 14+ messages in thread
From: jlspc @ 2023-09-28 15:56 UTC (permalink / raw)
To: ZmnSCPxj; +Cc: Bitcoin Protocol Discussion, lightning-dev
Hi ZmnSCPxj,
> Good morning John,
> ><i> On the other hand, if the consensus rules are changed to allow even simple covenants, this scaling bottleneck is eliminated.
> </i>><i> The key observation is that with covenants, a casual user can co-own an off-chain Lightning channel without having to sign all (or any) of the transactions on which it depends.
> </i>><i> Instead, a UTXO can have a covenant that guarantees the creation of the casual user's channel.
> </i>><i> The simplest way to have a single UTXO create channels for a large number of casual users is to put a covenant on the UTXO that forces the creation of a tree of transactions, the leaves of which are the casual users' channels.
> </i>><i>
> </i>><i> While such a covenant tree can create channels for millions of casual users without requiring signatures or solving a difficult group coordination problem, it's not sufficient for scaling.
> </i>><i> The problem is that each channel created by a covenant tree has a fixed set of owners, and changing the ownership of a channel created by a covenant tree requires putting the channel on-chain.
> </i>><i> Therefore, assuming that all casual users will eventually want to pair with different dedicated users (and vice-versa), the covenant tree doesn't actually provide any long-term scaling benefit.
> </i>><i>
> </i>><i> Fortunately, real long-term scaling can be achieved by adding a deadline after which all non-leaf outputs in the covenant tree can be spent without having to meet the conditions of the covenant.
> </i>><i> The resulting covenant tree is called a "timeout-tree" [9, Section 5.3].
> </i>><i>
> </i>><i> Let A_1 ... A_n denote a large number of casual users, let B be a dedicated user, and let E denote some fixed time in the future.
> </i>><i> User B creates a timeout-tree with expiry E where:
> </i>><i> * leaf i has an output that funds a Lightning channel owned by A_i and B, and
> </i>><i> * after time E, each non-leaf output in the covenant tree can also be spent by user B without having to meet the conditions of the covenant.
> </i>
> I think, based solely on the description above, that it is not safe for dedicated user `B` to create this, unless it gets a signature from `A_i`.
You're right!
> The alternative is to also infect the leaf itself with a lifetime `(A_i && B) || (B && CLTV)`.
Yes, exactly.
This is the design given in the figures in the paper, as well as in the detailed descriptions that accompany those figures.
However, the text that you quoted above was incorrect and requires the change you described.
I've created a new version of the paper that includes this fix [1].
It also includes more detail (at the end of Section 4.9) on the use of hierarchical channels while performing passive rollovers.
Thanks for making this correction.
Regards,
John
[1] Law, "Scaling Lightning With Simple Covenants, version 1.1", https://github.com/JohnLaw2/ln-scaling-covenants
Sent with Proton Mail secure email.
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] Scaling Lightning With Simple Covenants
2023-09-26 16:42 ` Antoine Riard
@ 2023-10-06 16:26 ` jlspc
0 siblings, 0 replies; 14+ messages in thread
From: jlspc @ 2023-10-06 16:26 UTC (permalink / raw)
To: Antoine Riard; +Cc: Bitcoin Protocol Discussion, lightning-dev
[-- Attachment #1: Type: text/plain, Size: 7937 bytes --]
Hi Antoine,
>><i> "I also think resizing channels can be done fairly effectively off-chain
></i>with hierarchical channels [1] (and even better with hierarchical channels
>within timeout-trees)".
>Yes, transactional scaling of Lightning (i.e how many transfers can be
>performed off-chain per on-chain transaction) sounds good at first sight,
>though in practice liquidity unbalance due to asymmetries in liquidity
>flows among counterparties is a bottleneck. Note, how the on-chain
>splicing for LSP spec upgrade improves on this dimension and where
>"resizing" or "pool rebalancing" aims to keep this off-chain.
Yes, and note that with hierarchical channels you can use HTLCs to send Lightning channel capacity over the Lightning network [1], thus performing channel resizing off-chain between channels that aren't in the same pool.
>><i> "With these proposals, it's possible to dramatically limit the
></i>interactivity".
>Yes, from my rough understanding of timeout-trees and channel resizing, it
>sounds to suffer from the same issue as Jeremy radix-tree's proposal or
>Christian OG channel factory, namely the lack of fault-tolerance when one
>of the casual user or end of tree balance owner aims to go on-chain. The
>fragmentation cost sounds to be borne by all the users located in the tree
>branch. Note fault-tolerance is one of the key payment pool design goals to
>advance over factories.
Actually, in the case of a timeout-tree, the fragmentation costs imposed by a casual user going on-chain are borne exclusively by the dedicated user who funded the timeout-tree.
This makes it easier to address the problem by making the casual user pay the funder for the fragmentation costs.
I think this is an important issue, so I created a new version of the paper that includes a description of how this can be done [2].
The idea is to require casual users to reveal secrets (hash preimages) that only they know in order to put timeout-tree transactions on-chain.
Then, a fee-penalty output is added to each leaf transaction that pays from the casual user to the funding user an amount that depends on which timeout-tree transactions the casual user put on-chain.
The details are given in the new version of the paper ([2], Section 4.10, pp. 25-28).
>><i> "I propose that if the active drain fails, the casual user should put
></i>their channel in the old timeout-tree on-chain (so that it won't timeout on
>them). "
>I think there is still some issue there where you need to handle the
>malicious HTLC-withholding case along your multi-hop payment paths and wait
>for the expiration. Then go on-chain to expire the old timeout-tree, which
>might come with a high timevalue cost by default. Not saying keeping
>timevalue cost low is solved for today's Lightning.
This is an excellent point that I hadn't considered.
I think the solution is to perform passive, rather than active, rollovers.
Passive rollovers don't require use of the Lightning network, so they completely eliminate the risk of HTLC-withholding attacks.
I've added this advantage of passive rollovers in the latest version of the paper ([2], Section 4.4, p. 19).
>><i> "These costs could be large, but hopefully they're rare as they are
></i>failures by dedicated users that can afford to have highly-available
>hardware and who want to maintain a good reputation".
>Yes, though note as soon as a dedicated user starts to have a lot of
>off-chain tree in the hand, and this is observable by adversaries the
>dedicated user becomes an attack target (e.g for channel jamming or
>time-dilation) which substantially alter the trade-offs.
I believe channel jamming and HTLC-withholding attacks can be eliminated by using passive rollovers, as mentioned above.
>><i> "However, the paper has a proposal for the use of "short-cut"
></i>transactions that may be able to eliminate this logarithmic blow-up".
>Yes "cut-through" to reduce on-chain footprint in mass exit cases has been
>discussed since the early days of off-chain constructions and Taproot /
>Grafroot introduction to the best of my knowledge, see:
><a href="https://tokyo2018.scalingbitcoin.org/transcript/tokyo2018/multi-party-channels-in-the-utxo-model-challenges-and-opportunities">https://tokyo2018.scalingbitcoin.org/transcript/tokyo2018/multi-party-channels-in-the-utxo-model-challenges-and-opportunities</a>
While I see "how do we cut-through to reduce the on-chain footprint in mass exit cases?" listed as an open problem in the above reference, I don't see any specific solutions to that problem in that reference.
The "short-cut" transactions I was referring to are defined in Section 5.4 and pictured in Figure 14 on p. 32 of the revised version of the paper [2].
They are a specific proposal for addressing the logarithmic blow-up of putting a control transaction defined by a covenant tree on-chain.
I agree that this has some similarities to the Graftroot proposal, but I believe it is distinct from proposals for addressing mass exit cases (and in fact it would not work well in those cases).
>Few questions from reading Dave's description of TP protocol here:
><a href="https://bitcoinops.org/en/newsletters/2023/03/29/#preventing-stranded-capital-with-multiparty-channels-and-channel-factories">https://bitcoinops.org/en/newsletters/2023/03/29/#preventing-stranded-capital-with-multiparty-channels-and-channel-factories</a>
>.
>In the scenario of multiple parties (e.g Alice, Bob, Caroll) owning a state
>transaction + control output, what prevents Caroll to double-spend Bob's
>revoked state transaction to a destination controlled by her in collusion
>with Bob, at the harm of Alice ?
Nothing prevents Bob from putting a revoked State transaction on-chain, and nothing prevents Carol from spending the first control output of that revoked State transaction in any manner she wishes.
Doing so would allow Carol to obtain a tunable penalty (namely, the value of the first control output of Bob's revoked State transaction), but it would not harm Alice in any way.
Spending that output keeps Bob from being able to put his Commitment transaction on-chain.
On the other hand, Alice can still put her Commitment transaction on-chain, and her payment from that Commitment transaction is unchanged, so she has not been harmed in any way.
For example, see Figure 18 on p. 29 of [1].
If Bob puts a revoked ST_Bh on-chain (where h < i and i is the current state number) and Carol spends the first control output of ST_Bh, Bob cannot put COM_Bi on-chain, but Alice can still put ST_Ai and COM_Ai on-chain.
>In the scenario of multiple commitment transactions spending the same state
>transaction of an offliner user, what prevents Caroll to fake offliness and
>equivocate at the harm of Alice or another party ?
There is never a case where multiple commitment transactions can spend an output from the same state transaction.
For example, see Figure 18 on p. 29 of [1].
Each user's State transaction can only be spent by the same user's Commitment transaction (e.g., COM_Ai spends an output from ST_Ai, COM_Bi spends an output from ST_Bi, and COM_Ci spends an output fromn ST_Ci).
Furthermore, each Commitment transaction (at the 3-user hierarchical channel level) requires signatures from all 3 users in order to spend the value output from the Funding transaction F, so only the correct Commitment transaction can spend that output.
>Still building my understanding of the TP protocol security model and
>seeing where it converges / diverges w.r.t other off-chain constructions
>trade-offs.
Thanks for doing the deep-dive on these protocols!
Regards,
John
[1] Law, "Resizing Lightning Channels Off-Chain With Hierarchical Channels", https://github.com/JohnLaw2/ln-hierarchical-channels
[2] Law, "Scaling Lightning With Simple Covenants, version 1.2", https://github.com/JohnLaw2/ln-scaling-covenants
Sent with [Proton Mail](https://proton.me/) secure email.
[-- Attachment #2: Type: text/html, Size: 9083 bytes --]
^ permalink raw reply [flat|nested] 14+ messages in thread
* Re: [bitcoin-dev] [Lightning-dev] Scaling Lightning With Simple Covenants
2023-09-11 0:56 ` [bitcoin-dev] [Lightning-dev] " Anthony Towns
2023-09-17 0:52 ` jlspc
@ 2023-11-15 19:59 ` jlspc
1 sibling, 0 replies; 14+ messages in thread
From: jlspc @ 2023-11-15 19:59 UTC (permalink / raw)
To: Anthony Towns; +Cc: Bitcoin Protocol Discussion, lightning-dev
Hi aj,
A few more thoughts on this trust/safety vs. capital efficiency tradeoff:
> Optimising that formula by making LA [the channel's active lifetime] as large as possible doesn't
> necessarily work -- if a casual user spends all their funds and
> disappears prior to the active lifetime running out, then those
> funds can't be easily spent by B until the total lifetime runs out,
> so depending on how persistent your casual users are, I think that's
> another way of ending up with your capital locked up unproductively.
The risk of the casual user spending all of their funds can be addressed by having the casual user prepay the cost-of-capital fees for the dedicated user's funds for the entire lifetime of the channel.
Then, whenever the dedicated user's funds increase or decrease (due to a send or receive by the casual user), a corresponding prepayment adjustment is included in the new balances defined by the send or receive HTLC.
With prepayments, the dedicated user can safely agree to a long active lifetime for the channel.
In the paper, I assumed an active lifetime of 110,000 blocks (about 2.1 years), but allowed the casual users to obtain a new channel every 10,000 blocks (about 2.5 months) by staggering their timeout-trees ([1], Sec. 4.8 and 5).
The paper includes a rollover period (which covers the casual user's unavailability for up to 2.5 months) in addition to the timeout-tree's active lifetime (25 months) and inactive lifetime (1 week for putting leaves onchain, which definitely introduces risk).
Here are some rough calculations if one wants to eliminate risk by making the inactive lifetime long enough to put all leaves of all timeout-trees onchain before the timeout-trees' expiries:
TIME BOUND ON NUMBER OF LEAVES:
------------------------------
There are approximately 52,500 blocks / year, each with at most 4M vbytes, for a total of approximately 210B = 2.1 * 10^11 vbytes per year.
If each leaf requires an average (when all leaves in a tree are put onchain) of 2,100 vbytes, then 2.1 * 10^11 / 2,100 = 10^8 = 100M leaves can be put onchain in 1 year with full block capacity devoted to leaves, and in 1/x years with a fraction of x capacity devoted to leaves.
Therefore, at x = 0.5 capacity:
50M leaves can be put onchain per year
100M leaves can be put onchain in 2 years
1B leaves can be put onchain in 20 years
10B leaves can be put onchain in 200 years
100B leaves can be put onchain in 2,000 years
Assuming an active lifetime of 2.1 years, adding an inactive period of 2 years may be plausible, depending on the cost of capital.
Therefore, scaling to 100M or so leaves (across all timeout-trees) while maintaining the ability to put all leaves onchain may be doable.
On the other hand, an inactive period of 20 years seems unreasonable.
As a result, scaling to billions of leaves probably requires trading off safety vs. capital efficiency (as you noted).
FEERATE BOUND ON NUMBER OF LEAVES:
---------------------------------
If each leaf requires a maximum (when only that leaf is put onchain) of 10,500 vbytes and the feerate is at least 2 satoshis / vbyte, then each leaf must be worth at least 21,000 satoshis (or else the dedicated user may not have an incentive to be honest, as the casual user would lose funds by putting their leaf onchain).
There are at most 2.1 * 10^15 satoshis in existence, so there can be at most 2.1 * 10^15 / 21,000 = 10^11 = 100B leaves.
I wrote a small python3 program for analyzing scalability given the requirement that all timeout-tree leaves can be put onchain.
The trickiest part was figuring out how to quantify the onchain fees caused by increasing the fraction of each block that's devoted to casual users putting their leaves onchain.
I wanted a function that multiplies the base feerate by a factor of 1 when no leaves are put onchain and by a factor approaching infinity when nearly all of the block space is devoted to leaves.
I started with the function Fe/(1-x), where Fe is the base feerate (without leaves put onchain) and x is the fraction of block space devoted to putting leaves onchain.
This function has the desired behavior when x is near 0 or 1, and it doubles the base feerate when half the block space is devoted to leaves.
In reality, the feerate probably increases faster than that, so I added an exponent to capture how quickly the feerate grows:
feerate = Fe/(1-x)^Ex where Ex is an arbitrary exponent.
The program has the following tunable parameters:
* Ac: length (in blocks) of active lifetime of each TT (timeout-tree)
* Ro: length (in blocks) of rollover period of each TT (provides for casual user's unavailability)
* AS: average size (in vbytes) of transactions required to put one TT leaf onchain when all leaves in TT are put onchain
* MS: maximum size (in vbytes) of transactions required to put one TT leaf onchain when only one leaf in TT is put onchain
* Fe: feerate (in sats/vbyte) assuming 0% of block contains TT leaves
* Ex: exponent controlling rate of growth of feerates as TT leaves are added to blocks
* Pr: probability TTs are put on-chain
* Le: number of leaves of all TTs
* Va: value (in bitcoins) of all TT leaves put together, where each TT leaf has equal funds and during its active lifetime each leaf's funds are equally divided between:
1) casual user's immediate bitcoin,
2) casual user's Lightning balance, and
3) dedicated user's Lightning balance
* Co: cost of capital (in fraction of funders' capital/year) for allocating the funders' capital to TTs
The program calculates the inactive lifetime (that is, the time for putting all timeout-tree leaves onchain) by minimizing the dedicated users' cost-of-capital plus the expected cost of putting leaves onchain.
In all cases, it takes the safe approach of making the inactive lifetime long enough for all leaves to be onchain before the timeout-tree expires.
There's a lot of guesswork in setting the parameters, but assuming the following values:
Ac: 110,000 blocks
Ro: 10,000 blocks
AS: 2,100 vbytes
MS: 10,500 vbytes
Fe: 10 sats/vbyte
Ex: 4.0 (so fees increase to 160 sats/vbyte if half the block space is devoted to TT leaves)
Pr: 0.01 (a 1% chance that the TTs will have to be put onchain)
Le: 100,000,000 leaves (channels)
Va: 10,000,000 BTC
Co: 0.01 (a 1% annual cost of capital for associating capital with a given casual user, while still using that capital to route unrelated payments)
results in devoting up to 0.65 of the blockspace for TT leaves, an inactive lifetime (SecurityDelay) of 1.55 years, and an expected overall cost (ExpectedOverheadFraction) of 0.025 (2.5%) of the casual user's funds.
The program and some sample inputs and outputs are on GitHub [2].
The parameter values shown above are in line 63 of the file in_tt_analysis01.csv and the results are in line 72 of the file out_tt_analysis01.xlsx.
Of course, there are other limits to scalability, such as the rate at which HTLCs timeout and have to be put onchain.
I just wanted to get a sense of when the trust/safety vs. capital efficiency tradeoff you identified becomes inevitable.
Regards,
John
Sent with Proton Mail secure email.
^ permalink raw reply [flat|nested] 14+ messages in thread
end of thread, other threads:[~2023-11-15 19:59 UTC | newest]
Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-09-08 18:54 [bitcoin-dev] Scaling Lightning With Simple Covenants jlspc
2023-09-11 0:56 ` [bitcoin-dev] [Lightning-dev] " Anthony Towns
2023-09-17 0:52 ` jlspc
2023-11-15 19:59 ` jlspc
2023-09-11 2:13 ` [bitcoin-dev] " Rusty Russell
2023-09-17 0:56 ` jlspc
2023-09-11 5:27 ` Antoine Riard
2023-09-17 0:59 ` jlspc
2023-09-26 16:42 ` Antoine Riard
2023-10-06 16:26 ` jlspc
2023-09-17 11:32 ` Erik Aronesty
2023-09-19 7:44 ` ZmnSCPxj
2023-09-18 4:14 ` ZmnSCPxj
2023-09-28 15:56 ` jlspc
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox