Skip to content

Instantly share code, notes, and snippets.

@ajtowns

ajtowns/Makefile Secret

Last active February 11, 2023 08:53
Show Gist options
  • Save ajtowns/12f58fa8a4dc9f136ed04ca2584816a2 to your computer and use it in GitHub Desktop.
Save ajtowns/12f58fa8a4dc9f136ed04ca2584816a2 to your computer and use it in GitHub Desktop.
lnpenalty taproot
@startuml
title State channels with layered-txs
database Blockchain
participant Alice
participant Bob
participant Carol
== Setup ==
Alice -> Bob : add_htlc(R, Talice)
Bob -> Carol : add_htlc(R, Tbob)
== Bob wants to expire the htlc ==
note across: height = Tbob - grace
Bob -> Carol : drop_htlc(R, Tbob)
Carol ->X Bob : (no response)
note across: height = Tbob
Bob -> Blockchain : post unilateral close (Bob/Carol)
Bob -> Blockchain : post pay-to-self timeout layered tx
note across: height = Tbob + confirm_delay
Blockchain --> Bob : confirmed
== Alice wants to expire the htlc ==
note across: height = Talice - grace
Alice -> Bob: drop_htlc(R, Talice)
Bob -> Alice: ack
hnote across #aqua
Note, Bob must set
Tbob < Talice - confirm_delay - grace
in order to know his funds are reclaimed from Carol
prior to sending the ack to Alice.
end note
@enduml
@startuml
title State channels without layered-txs
database Blockchain
participant Alice
participant Bob
participant Carol
== Terminology ==
hnote across #aqua
Bob has forwarded a payment from Alice to Carol.
Carol isn't failing the payment, and the timeout has been reached,
so Bob is closing his channel with Carol. He wants to ensure Carol
cannot claim the payment, before reporting payment failure to Alice.
Terms:
"to_self_delay" - how long an old commitment tx has to sit on the chain
before it can be claimed, to allow for punishment/etc.
(100 blocks? 1000?)
"confirm_delay" - how long we expect a tx to confirm on the blockchain
(may depend on the fee rate we use; 6 blocks?)
"grace" - how long we expect it to take for a live peer to respond to a
p2p message (1 minute?)
end note
== Setup ==
Alice -> Bob : add_htlc(R, Talice)
Bob -> Carol : add_htlc(R, Tbob)
== Bob wants to expire the htlc ==
note across: height = X
Bob -> Carol : drop_htlc(R, Tbob)
Carol ->X Bob : (no response)
note across: height = X + grace
Bob -> Blockchain : post unilateral close (Bob/Carol)
note across: height = X + grace + confirm_delay
Blockchain --> Bob : confirmed commitment tx
Bob -> Bob : waits for to_self_delay to expire to give Carol the ability to prove he was cheating
note across: height = X + grace + confirm_delay + to_self_delay
Bob -> Blockchain : post refund tx (CSV and CLTV have passed)
hnote across #aqua
Bob cannot post the refund tx until his timeout has expired,
so Tbob = X + grace + confirm_delay + to_self_delay
ie X = Tbob - grace - confirm_delay - to_self_delay
end note
note across: height = Tbob + confirm_delay
Blockchain --> Bob : confirmed claim of HTLC
== Alice wants to expire the htlc ==
note across: height = Y
Alice -> Bob: drop_htlc(R, Talice)
Bob -> Alice: ack
hnote across #aqua
Using the same logic, we have Y = Talice - grace - confirm_delay - to_self_delay
But in order for Bob to be able to ack Alice's close, we also must have Y being
after Bob's refund tx confirms, so that he is sure Carol isn't able to claim the
funds and complete the payment. ie:
Y > Tbob + confirm_delay
Talice > Tbob + grace + 2*confirm_delay + to_self_delay
But this means Alice's timeout has to be bumped by the entire to_self_delay from
Bob's.
end note
@enduml

Layered transactions

When dealing with payment channels we have two timeouts to consider:

  • the payment timeout, after which the sender of the payment can require a refund if the payment hasn't completed.

  • the revocation timeout, after which the channel state can be considered final, and not subject to being updated (eg in eltoo channels) or subject to a penalty (eg in current Poon-Dryja channels).

The interaction between these two timeouts can cause problems.

Without layered commitments

The worst case scenario for obtaining a refund occurs when you're forwarding a payment, and the node to which you've forwarded the payment has gone completely offline, forcing you to drop the channel to the blockchain.

In this case, without layered commitments, in order to claim the funds...

no layers sequence diagram

Goals
=====
1. Support HTLCs
2. Support PTLCs
3. Minimise long-term data storage requirements
4. Minimise latency when forwarding payments
5. Minimise latency when refunding payments
6. Support offline receiving
7. Minimise on-chain footprint
8. Minimise ability for third-parties to analyse
Setup
=====
We have two participants in the channel, Alice and Bob. They each have
bip32 private keys, a and b, and share the corresponding xpubs A and B
with each other.
Musig
-----
We will use musig to combine the keys, where P = musig(A,B) = H(A,B,1)*A
+ H(A,B,2)*B. We'll talk about subkeys of P, eg P/4/5/6, which are
calculated by taking subkeys of the input and then applying musig,
eg P/4/5/6 = musig(A/4/5/6, B/4/5/6). (Note that we don't use hardened
paths anywhere)
Musig2
------
We'll use musig2 to sign for these keys, that is both parties will
pre-share two nonce points each, NA1, NA2, NB1, NB2, and the nonce will be
calculated as: R=(NA1+NB1)+k(NA2+NB2), where k=Hash(P,NA1,NA2,NB1,NB2,m),
where P is the pubkey that will be signing and m is the message to be
signed. Note that NA1, NA2, NB1, NB2 can be calculated and shared prior
to knowing what message will be signed.
The partial sig by A for a message m with nonce R as above is calculated as:
sa = (na1+k*na2) + H(R,A+B,m)*a
where na1, na2, and a are the secrets generating NA1, NA2 and A respectively.
Calculating the corresponding partial signature for B,
sb = (nb1+k*nb2) + H(R,A+B,m)*b
gives a valid signature (R,sa+sb) for (A+B):
(sa+sb)G = R + H(R,A+B,m)*(A+B)
Note that BIP340 sepcifies x-only pubkeys, so A+B and R implicitly have
even y, however since those values are caluclated via musig and musig2
respectively, this cannot be ensured in advance. Instead, if we find:
H(A,B,1)*A + H(A,B,2)*B
does not have even y, we calculate:
P = (-H(A,B,1))*A + (-H(A,B,2))*B
instead, which will have even y. Similarly, if (NA1+NB1+k(NA2+NB2)) does
not have even y, when signing, we replace each partial nonce by its negation,
eg: sa = -(na1+k*na2) + H(R,A+B,m).
Adaptor Sigs
------------
An adaptor signature for P for secret X is calculated as:
s = r + H(R+X, P, m)*p
which gives:
(s+x)G = (R+X) + H(R+X, P, m)*P
so that (R+X,s+x) is a valid signature by P of m, and the preimage for
X can be calculated as the difference between the published sig and the
adaptor sig, x=(s+x)-(s).
Note that if R+X does not have even Y, we will need to negate both R and X,
and the recovered secret preimage will be -x instead of x.
Revocable Secrets
-----------------
Alice and Bob have shachain secrets RA(n) and RB(n) respectively,
and second level shachain secrets RA2(n,i) and RB2(n,i), with n and i
counting up from 0 to a maximum.
Summary
=======
We'll introduce four layers of transactions:
1. The funding transaction - used to establish the channel, provides
the utxo backing the channel while the channel is open.
2. The balance transaction - tracks the funding transaction, contains
a "balance" output for each of the participants.
3. The inflight transactions - spends a balance output from the balance
transaction and provides outputs for any inflight htlc/ptlc transactions.
4. Layered transactions - spends inflight htlc/ptlc outputs by revealing
the preimage, while still allowing for the penalty path.
Funding transaction
===================
The funding transaction simply pays to P/0/f via taproot, where f starts
at 0 and increases any time the funding transaction is updated onchain
(eg when splicing funds in or out).
Balance transaction
===================
The balance transaction spends the funding transaction, and has two
outputs, one for Alice's balance and one for Bob's balance (omitting a
zero/dust balance).
We count the number of balance updates, starting at 0, and call it "n".
"n" is encoded in the transaction locktime and the input nsequence, so
if a balance transaction appears on chain, "n" can be decoded from the
nsequence and locktime.
Alice's balance is paid to an address with internal pubkey P/1/n/0
and a script path of "<A/1/n> CHECKSIGVERIFY <D> CSV" where D is
Alice's to_self_delay. Bob's balance is similar, with internal pubkey
P/1/n/1.
In order to update to a new balance transaction, the process is as follows.
First, nonces are exchanged in advance:
Alice:
Generates a nonce pair NA1, NA2 derived from RA(n). Shares this with
Bob.
Bob:
Generates a nonce pair NB1, NB2 derived from RB(n). Shares this with
Alice.
Then, presuming Alice initiates the update:
Alice:
Generates deterministic nonce pair, DA1, DA2, based on Bob's nonce
pair NB1, NB2, the message to be signed, and some private seed (eg her
private key). Combines this with Bob's NB1, NB2 nonce pair. Generates
partial signature for nonce (DA, NB) for the transaction. Sends DA1
and DA2 and the partial signature to Bob.
Bob:
Checks the partial signature is valid. Updates to the new balance
transaction. Generates a nonce pair, DB1, DB2, in the same way Alice
did and gnerates a partial signature for the balance transaction
for nonce (NA, DB). Sends DB1, DB2, and the partial signature to
Alice. Generates a new revocable secret RB(n+1). Revokes the previous
secret RB(n) and sends the details of both to Alice.
Alice:
Checks the partial signature is valid. Updates to the new balance
transaction. Checks the secret revocation info is correct and stores
it. Generates a new revocable secret RA(n+1). Revokes the previous
secret RA(n) and sends the details of both to Bob.
Bob:
Checks the secret revocation info is correct an stores it.
This means that both Alice and Bob have the same balance transaction here
(with the same txid) but have different signatures for it (and thus
differing wtxids).
Because updating the balance transaction involves two round trips
before Bob can be sure Alice cannot use the old state, we move all the
transaction information to the inflight transactions, which we will be
able to update immediately, without requiring a round trip at all.
Note that if Bob publishes the signature for an old state, then the
signature is:
s = ((DA1+NB1) + k(DA2+NB2)) + H(R,A+B,m)(a+b)
but Alice can calculate the secrets for both DA1 and DA2 (she generated
those deterministically herself in the first place), and NB1 and NB2 (she
has the secret revocation information, and verified that it correctly
generated the nonces Bob was using), which allows her to calculate Bob's
private key using modular arithmetic:
b = H(R,P,m) / (s - (DA1+NB1) - k(DA2+NB2)) - a
which means she can then directly sign without Bob's assistance, allowing
her to claim any funds.
Inflight and Layered Transactions
=================================
We construct two inflight transactions on top of the current balance
transaction, one spending Alice's balance, and one spending Bob's balance.
We will use "i" to represent the number of times a given inflight
transaction has been updated for the nth update to the balance
transaction.
At any time Alice can update the inflight transaction spending her balance
to transfer funds towards Bob, either by updating the balances directly,
or adding a htlc/ptlc entry to conditionally transfer funds to Bob. (And
conversely for Bob)
We will define RP=musig(A/2/n/i, RB2(n,i)).
The inflight transaction spending Alice's balance can have multiple
types of outputs:
* Alice's remaining balance: pays directly to A/2/n/i
* Bob's remaining balances: pays to RP/2 with script path
"<B/2/n/i> CHECKSIGVERIFY <D> CSV"
* An htlc paying to Bob: pays to RP/2/c with script paths:
+ "LENGTH 32 EQUALVERIFY HASH160 <X> EQUALVERIFY <B/2/n/i/c> CHECKSIGVERIFY <A/2/n/i/c> CHECKSIG"
+ "<A/2/n/i/c/1> CHECKSIGVERIFY <T> CLTV"
* A ptlc paying to Bob: pays to RP/2/c with script paths:
+ "<B/2/n/i/c> CHECKSIG NOTIF <T> CLTV DROP ENDIF <A/2/n/i/c> CHECKSIG"
Any outputs that would be zero or dust are not included.
Note that we number each currently inflight htlc/ptlc by "c",
starting at 0. The same htlc/ptlc may have a different value for c
between different inflight transactions.
The inflight transation's locktime is set to the current block
height. This enables brute force searching for the locktime of any
inflight ptlcs (so that in a penalty scenario when the other party posts
an out of date inflight transaction, you can search through a small
number of possible timeout values simply by not sending any ptlcs with
a timeout more that L blocks in the future).
The balance input's nsequence is used to encode the value of the lower
24 bits of i in the same way the balance transaction's fund input's
nsequence encodes the upper 24 bits of n.
The layered transaction will spend the htlc/ptlc outputs, with an
ANYONECANPAY|SINGLE signature by Alice using the A/2/n/i/c path.
The output committed to is:
* pays to RP/3/c with script path:
+ <B/3/n/i/c> CHECKSIGVERIFY <D> CSV
with no absolute or relative locktime.
To update the inflight transaction spending Alice's balance as well as
any dependent layered transactions, the process is as follows:
Bob:
Generates a second level revocable secret, RB2(n,i) and sends Alice
the corresponding point, PB2. Calculates a nonce pair, NB1, NB2, and
sends that to Alice. This is done in advance.
Alice:
Calculates the new inflight transaction. Calculates new nonces NA1,
NA2, and partially signs the spend of her balance via the key path,
with musig2 nonces NA1, NB1, NA2, NB2. For each inflight htlc,
Alice provides a signature via A/2/n/i/c. For each inflight ptlc,
Alice provides an adaptor signature via the A/2/n/i/c/0 path that
is conditional on the ptlc's point.
Bob:
Bob verifies the new proposed inflight state and each of the
signatures. Bob may now rely on the new state. Bob revokes their
prior secret, RB2(n, i-1), and sends a new point/nonce pair (PB2',
NB1', NB2') to Alice to prepare for the next round.
Note that Bob could stream multiple point/nonce pairs in advance,
allowing Alice to do multiple inflight tx updates within the time taken
for a roundtrip.
Alice can unilaterally do the following safely:
1. transfer from Alice's balance to Bob's balance
2. accept that a htlc/ptlc succeeded, removing the corresponding output
and allocating the funds associated with it directly to Bob's balance
3. introduce a htlc/ptlc, spending funds from Alice's balance
However refunding/cancelling a htlc/ptlc requires a two-phase commit
with 1.5 round trips:
- Bob proposes refunding a htlc/ptlc
- Alice agrees and sends a partial signature for the new transaction
with the htlc/ptlc funds transferred back to her balance,
- Bob records the new transaction, and revokes the earlier second
level secret RB2(n, i-1).
- Alice verifies the revocation, and can safely treat the funds as
refunded (and thus refund back to the original payer, eg).
The advantage of doing this over negotiating a new balance transaction
is that only the second level revocation secrets need to be online,
allowing for operation by semi-offline lightning nodes (ie, having the
channel private key and first level revocation secrets offline). Such
semi-offline nodes risk losing funds in the "inflight" transaction
(either by revealing the second level revocation secrets or by simply
data loss of the current inflight/layered transactions) but do not risk
losing or spending funds in their own output of the balance transaction.
This means the funds locked in Alice's balance can be spent in the
following ways:
* Alice can claim them directly if Bob does not post the inflight
transaction before the delay expires, via the script balance output's
script path. Alice gets the entire balance in this case.
* Bob can post a revoked inflight transaction, for which Alice knows the
secret for RB(n,i). In this case Alice recovers the value of i from
the nsequence (using brute force for the upper bits if she has
provided more than 16M updates of the inflight tx for any given
balance transaction), and then calculates the secret key for PB,
and hence PB/2/c and PB/3/c, at which point she can claim every
output via a key path spend, even if Bob posts some or all of the
layered transactions. Alice gets the entire balance in this case
(though spends more on fees).
* Bob can post a current inflight transaction, along with layered
transactions for any of the inflight htlc/ptlcs for which he knows the
corresponding preimage, allowing Alice to recover the preimages from
the on-chain spends immediately. Alice can claim her balance output and
any timed out funds immediately as well. Bob can finish claiming his
balance and any claimed htlc/ptlc funds after the delay has finished.
Note that Bob never shares his signature to spend Alice's balance prior
to posting the inflight transaction, so Alice can never post an inflight
transaction that spends her own balance.
The cases where Alice may have difficulty claiming funds is Bob posts
a revoked inflight transaction (possibly spending a revoked balance
transaction) are:
* if the inflight transaction contains a htlc output, then if Alice
has not retained the old htlc details (the hash160 and the timeout)
she will not be able to reconstruct the script path, and thus will
not be able to calculate the TapTweak to sign for the key path.
However if Bob attempts to claim the output (via the pre-signed
layered transaction), that will reveal the information she was missing,
and she can immediately claim the funds via the layered transaction
output, prior to Bob being able to spend that output.
* if the inflight transaction contains a ptlc output, then if Alice
has not retained the old ptlc details (the point and the timeout)
she will not trivially be able to reconstruct the script path,
which includes the timeout. However, presuming the timeout was
within 5000 blocks, then the only possible timeouts are the inflight
tx's nlocktime+i with 0<i<=5000, and she will only need to calculate
5000*c cases and match the corresponding scriptPubKeys to exhaustively
enumerate every possible ptlc output, which should take under a minute,
and be easily achievable. In addition, if Bob attempts to claim the
funds, he will reveal the script path, and Alice will be either able
to claim the inflight output directly or the layered output.
Misc
====
In order to transition from BOLT#3 format to this proposal, an onchain
transaction is required, as the "revocable signatures" arrangement cannot
be mimicked via the existing 2-of-2 CHECKMULTISIG output.
To allow splicing in/out, it may be important to maintain multiple
concurrent funding transactions (paying to P/0/f and P/0/f+1 eg),
which then requires maintaining multiple current balance transactions
(paying to P/1/n/* and P/1/n+1/x eg) and likewise multiple current
inflight/layered transactions. This will require ensuring the states
for all those transactions are synchoronised when verifying upates,
and requires sharing multiple nonces for signing (eg RA(n) and RA(n+1)
and RB2(n,i), and RB2(n+1,i)).
Fees for the balance and inflight transactions must be considered upfront,
and paid for from the channel balance (or perhaps via additional anchor
outputs that allocate more than the dust threshold and are immediately
spendable). Fees for the layered transactions however can (and must)
be provided by whoever is attempting to claim the funds.
Bob having a current inflight transaction spending Alice's balance is
advantageous to Alice as Bob posting the inflight transaction allows
her to immediately claim her balance, rather than having to wait for
the delay to complete.
If two nodes agree to only forward ptlcs in future, then updating the
funding transaction (to P/0/f+1 eg) and ignoring any proposed inflight
transactions that include htlc outputs is enough to ensure that all htlc
records can be forgotten without risking any part of the channel balance
being unclaimable.
This does not support option_static_remotekey, but compensates for that
by allowing balances to be recovered with only the channel setup data
even if all revocation data is lost.
References
==========
Hopefully the above includes enough explanation to be understood on its own,
but here's references for a bunch of the concepts.
* musig: https://blockstream.com/2018/01/23/en-musig-key-aggregation-schnorr-signatures/
* musig2: https://medium.com/blockstream/musig2-simple-two-round-schnorr-multisignatures-bf9582e99295
* adaptor sigs: https://github.com/ElementsProject/scriptless-scripts/blob/master/md/atomic-swap.md
* fast forwards [ZmnSCPxj]
https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-April/001986.html
https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-May/003043.html
https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-October/003265.html
* revocable signatures [LLFourn]
https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-August/002785.html
Mailing list thread is at:
https://lists.linuxfoundation.org/pipermail/lightning-dev/2021-October/003278.html
all: layered-layered.png layered-no-layers.png txs.png
%.png: %.ditaa
plantuml $<
%.png: %.uml
plantuml $<
@startuml
ditaa(--no-separation)
+--------------------------------------+ +----------------------------+
| Funding Tx ("f") | | Balance Tx ("n") |
+----------------+---------------------+ +------------+---------------+
| ... | ... | +->+ funding | Alice balance +-+
+----------------+---------------------+ | | +---------------+ |
| ... | funding output +--+ | | Bob balance | |
+----------------+---------------------+ +------------+---------------+ |
| ... | ... | |
+----------------+---------------------+ |
|
+---------------------------------------------------------------------------+
|
| +-----------------------------------------+
| | Inflight tx from Alice to Bob ("i") |
| +---------------+-------------------------+
+->| Alice balance | Alice remaining |
| +-------------------------+
| | Bob completed |
| +-------------------------+
| | HTLC 0 +---+
| +-------------------------+ |
| | PTLC 1 +-+ |
+---------------+-------------------------+ | |
| |
+----------------------------------------------+ |
| +----------------------------------------------+
| |
| | +------------------------------------------+
| | | Layered transaction |
| | +------------+-----------------------------+
| +->+ HTLC 0 | revocable payment to Bob |
| +------------+-----------------------------+
+--->+ PTLC 1 | revocable payment to Bob |
+------------+-----------------------------+
| misc funds | change from misc after fees |
+------------+-----------------------------+
@enduml
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment