[Lightning-dev] Efficient Factories For Lightning Channels
jlspc
jlspc at protonmail.com
Sun Jan 15 21:13:08 UTC 2023
TL;DR
=====
* Factories that create and update a large number of Lightning channels efficiently are essential for scaling the Lightning Network.
* This post presents the first known protocol for Lightning factories that can be closed unilaterally in O(1) time using O(1) on-chain transactions.
- If P parties use the protocol, they create P conflicting Commitment transactions, any of which can be used to establish the factory's state.
- As a result, each party must maintain P copies of the state of each channel created by the factory.
- Another factory protocol is presented that eliminates the need to maintain P copies of each channel state (at the expense of requiring more on-chain bytes).
* Both factory protocols are modifications of the Tunable-Penalty Channel protocol and share many of its properties, including:
- tunable penalties for putting old transactions on-chain, and
- watchtowers with storage that's logarithmic in the number of factory states supported (but linear in the number of parties in the factory).
Overview
========
Factories that allow multiple two-party Lightning channels to be created, re-sized and closed with a small number of on-chain transactions are essential to the scalability of Bitcoin [2].
Let P denote the number of parties, C denote tha number of channels created, and S denote the number of factory states supported.
The most efficient previously-known factory, created by Burchert, Decker and Wattenhofer [2], can be closed unilaterally in O(log S) time using O(log S) on-chain transactions and O(C + log S) on-chain bytes.
A single fixed transaction is used to instantiate the factory's channels when it's closed unilaterally, so the parties using the factory can maintain just a one version of each off-chain channel state.
Performing a unilateral close with O(log S) on-chain transactions requires that the party closing the factory interact with the blockchain at O(log S) different blockheights (so a unilateral close is an O(log S)-shot procedure [4]), which could be awkward for some users [8].
This paper presents two protocols for factories that can be closed unilaterally in O(1) time using O(1) on-chain transactions.
The first protocol, called the Tunable-Penalty Factory (TPF) protocol, requires only O(C) on-chain bytes for a unilateral close, but it can use P different transactions to instantiate the factory's channels, thus forcing the parties using the factory to maintain P different versions of each off-chain channel state.
The second protocol, called the Single-Commitment (SC) protocol, requires O(C + log S) on-chain bytes for a unilateral close, but it uses only a single transaction to instantiate the factory's channels, so multiple versions of off-chain channel states aren't required.
The TPF protocol is particularly simple and allows a 2-shot unilateral close (that is, the party closing the channel only has to perform actions at 2 different blockheights).
Both protocols are based on the Tunable-Penalty Channel (TPC) protocol [5] and they share many of its properties, including:
* tunable penalties for putting old transactions on-chain, and
* watchtowers with storage that's logarithmic in the number of factory states supported (but linear in the number of parties in the factory).
No change to the underlying Bitcoin protocol is required.
A more complete description, including a proof of correctness and better figures, is available in a paper [6].
The Tunable-Penalty Factory (TPF) Protocol
==========================================
The TPF protocol is a slight modification of the TPC protocol [5].
Each party using the TPC protocol has their own on-chain Individual transaction, the output of which they spend with their State transaction.
This State transaction is a control transaction and its first output's value is equal to the desired penalty for putting an old State transaction on-chain.
This first output can be spent by the same party's Commitment transaction for the same state, but only after a relative delay equal to the maximum of the parties' to_self_delay parameters.
The relative delay gives the other party time to revoke an old State transaction by spending its first output and thus claiming the penalty.
The State transaction also has an HTLC control output for each HTLC that is active in that state.
The TPC protocol revokes old State transactions with per-commitment keys that can be known to all parties, rather than with revocation keys that cannot be known by the party putting the revocable transaction on-chain [5].
The TPC protocol is modified to create the TPF protocol by:
* eliminating the HTLC control outputs from the State transactions,
* modifying the Commitment transactions to have channel outputs, each of which is owned by two parties in the factory, and
* supporting P > 2 parties by allowing each party to have their own Individual, State and Commitment transactions.
The TPF protocol is shown below:
+-+ A..Z +----+ AD
|F|------+-------------------------| CC |-----
+-+ | | |
| | | BC
| | |-----
| | |
. | | MZ
. | |-----
. +----+
|
| +----+ AD
+-------------------------|C_Ai|-----
| | |
| | | BC
| | |-----
| | |
| tsdAZ & A | | MZ
| +-----------| |-----
| | +----+
| |
| | +----+ AD
+-------------------------|C_Bi|-----
| | | |
| | | | BC
| | | |-----
| | | |
. | tsdAZ & B | | MZ
. +-------------| |-----
. | | +----+
| | |
| | | +----+ AD
+-------------------------|C_Zi|-----
| | | | |
. | | | | BC
. | | | |-----
. | | | |
| | | tsdAZ & Z | | MZ
V +---------------| |-----
| | | +----+
| | |
+----+ A +-----+ | | | pckeyAi
|In_A|----|St_Ai|------+-----------
+----+ | | | |
+-----+ | |
| |
+----+ B +-----+ | | pckeyBi
|In_B|----|St_Bi|----+-------------
+----+ | | |
+-----+ |
. . .
. . .
. . .
|
+----+ Z +-----+ | pckeyZi
|In_Z|----|St_Zi|--+---------------
+----+ | |
+-----+
where:
F is the Funding transaction,
CC is the Cooperative Close transaction,
In_{A..Z} is {A..Z's} Individual transaction,
St_{A..Z}i is {A..Z's} State transaction for state i, and
C_{A..Z}i is {A..Z's} Commitment transaction for state i.
Requirements for output cases are as follows:
{A..Z}: {A..Z}'s signature (a single party's signature),
A..Z: A..Z's signature (every parties' signature),
pairs of capital letters indicate signatures from those two parties,
pckey{A..Z}i: a signature using a per-commitment key for revoking {A..Z}'s state i transaction, and
tsdAZ: a relative delay equal to the maximum of {A..Z}'s to_self_delay parameters.
In order to establish a new factory state, all parties:
* calculate the State and Commitment transactions for the new state (this step includes exchanging per-commitment pubkeys for the new state with each of the other parties),
* exchange partial signatures for the new state's Commitment transactions, and
* exchange per-commitment keys for the old state, thus revoking it.
All parties constantly look for old (revoked) State transactions put on-chain by other parties, and if they find such a transaction they use the corresponding per-commitment key to spend its first output, thus obtaining the penalty funds and revoking the old state.
Once a State transaction has been on-chain for tsdAZ without its first output being spent, the party that put the State transaction on-chain can attempt to put their corresponding Commitment transaction on-chain at any time.
Any party can close the factory unilaterally by putting their current State transaction on-chain, waiting until it has been on-chain for tsdAZ, and then submitting their corresponding Commitment transaction to the blockchain.
As was the case with the TPC protocol, per-commitment keys can use the Lightning protocol's compact storage technique for revocation keys to consume only O(log S) storage to revoke a maximum of S old transactions that could be put on-chain by a single other party [7][5].
Therefore, each party requires O(P*log S) storage to hold the per-commitment keys for all of the P parties.
The Single-Commitment (SC) Factory Protocol
===========================================
Note that the TPF factory protocol uses P conflicting Commitment transactions to establish the factory state and to instantiate the factory's channels.
Therefore, a separate channel state must be maintained and updated for each of the P versions of the channel that could be instantiated, thus increasing the computation, storage, and communication for channels by a factor of P.
The result could be quite expensive if there are a large number of parties in the factory.
The SC protocol eliminates this factor of P blow-up by having all of the parties use a single shared Commitment transaction.
Like the TPF protocol, the SC protocol uses revocable State transactions, each of which spends a single party's Individual transaction output, to ensure that only the current Commitment transaction can be put on-chain.
The challenge is how to use a single shared Commitment transaction that depends on the value of an unrevoked State transaction without actually spending any of the outputs of that State transaction (as spending a State transaction output would make the Commitment transaction's input dependent on which party's State transaction it spends, thus preventing the use of a single shared Commitment transaction).
This challenge is solved by introducing a shared Trigger transaction and a per-user Mold transaction, where the Commitment and Mold transactions compete for the Trigger transaction's outputs.
The Mold transaction is put on-chain prior to the Commitment transaction, and it constrains the Commitment transactions that can be put on-chain somewhat like how a mold shapes a liquid that is poured into it.
Specifically, the Trigger transaction has one value output and log_2(S) control outputs, numbered 0 .. log_2(S) - 1. Commitment transaction i, 0 <= i <= S - 1, spends those Trigger control outputs b, 0 <= b <= log_2(S) - 1, such that bit position b of the binary representation of i is a 0.
Each Mold transaction i, 0 <= i <= S - 1, spends the output of the same party's State i transaction, and Trigger control outputs b, 0 <= b <= log_2(S) - 1, such that bit position b of the binary representation of i is a 1.
This construction guarantees that if a Mold transaction for state i is on-chain, only Commitment transactions for states j >= i can be put on-chain.
States 0 through S - 1 are supported, with the exception of states of the form 2^b where 1 <= b <= log_2(S) - 1.
These exceptions are made to guarantee that it is impossible to put Mold transactions on-chain for two consecutive states (other than states 0 and 1) where they would prevent any current Commitment transaction from being put on-chain.
When state i is supported but state i+1 is not, the next state after i is i+2.
The protocol operation is similar to that of the TPF protocol, except parties closing the channel unilaterally submit the Trigger transaction and their current State transaction to the blockchain, and once their State transaction has been on-chain for tsdAZ, submit their Mold transaction for the same state to the blockchain.
Once the Trigger transaction has been on-chain for 3tsdAZ, they submit to the blockchain the Commitment transaction for the same state as the on-chain Mold transaction.
Also, all parties monitor the blockchain for the Trigger transaction, and if they find it they use the above protocol for closing the factory as soon as possible.
Because only Mold transactions for unrevoked State transactions can be put on-chain, and because only the latest State transactions can be unrevoked, only the latest (and thus current) Commitment transactions can be put on-chain.
A figure for the SC protocol, and a detailed proof of correctness, are in the paper [6].
Related Work
============
The concept of creating a channel factory for Lightning, as well as the most efficient published protocol for such a factory, was presented by Burchert, Decker and Wattenhofer [2].
The protocols presented here differ in only requiring O(1) time and O(1) on-chain transactions for a unilateral factory close.
A number of researchers have proposed changes to Bitcoin in order to support simpler and more efficient factories.
The eltoo factory protocol [3] has a particularly simple structure and it allows the parties to maintain only one version of each off-chain channel state.
It requires O(1) time, O(1) on-chain transactions and O(1) on-chain bytes for a unilateral close.
However, a malicious party could delay the closing of the factory until O(S) transactions are put on-chain, if the malicious party is willing to pay the required fees.
The eltoo protocol differs from the protocols presented here by requiring a change to Bitcoin, namely the support for BIP 118 [1].
The TPF and SC protocols are based on the TPC protocol presented by Law [5].
Conclusions
===========
This post presents new factory protocols that require O(1) time and O(1) on-chain transactions for a unilateral close.
They are the first factory protocols known that achieve those bounds with the existing Bitcoin protocol.
The ability to unilaterally close a factory with just two or three submissions to the blockchain, with a fixed delay between them, is quite a bit simpler than closing previously-published factories [2].
As a result, it's hoped that TPF and SC factories will lead to the increased use of factories in practice, thus improving the scalability of Bitcoin and Lightning.
Regards,
John
References
==========
[1] "BIP 118: SIGHASH_ANYPREVOUT", available at https://anyprevout.xyz/ and https://github.com/bitcoin/bips/pull/943.
[2] Burchert, Decker and Wattenhofer, "Scalable Funding of Bitcoin Micropayment Channel Networks", available at http://dx.doi.org/10.1098/rsos.180089.
[3] Decker, Russell and Osuntokun. eltoo: A Simple Layer2 Protocol for Bitcoin. Available at https://blockstream.com/eltoo.pdf.
[4] Law, "Watchtower-Free Lightning Channels For Casual Users", available at https://github.com/JohnLaw2/ln-watchtower-free.
[5] Law, "Lightning Channels With Tunable Penalties", available at https://github.com/JohnLaw2/ln-tunable-penalties.
[6] Law, "Efficient Factories For Lightning Channels", available at https://github.com/JohnLaw2/ln-efficient-factories.
[7] Russell, "Efficient Per-Commitment Secret Storage", available at https://github.com/lightning/bolts/blob/master/03-transactions.md#efficient-per-commitment-secret-storage.
[8] ZmnSCPxj, "Channel Eviction From Channel Factories By New Covenant Operations", available at https://lists.linuxfoundation.org/pipermail/lightning-dev/2022-February/003479.html.
Sent with [Proton Mail](https://proton.me/) secure email.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20230115/1c24b7f0/attachment-0001.html>
More information about the Lightning-dev
mailing list