rich1.0Anthony Towns [ARCHIVE] (npub17r…x9l2h)https://yabu.me/npub17rld56k4365lfphyd8u8kwuejey5xcazdxptserx03wc4jc9g24stx9l2hnjumphttps://yabu.me📅 Original date posted:2021-10-08 📝 Original message: Hi all, Here's my proposal for replacing BOLT#2 and BOLT#3 to take advantage of taproot and implement PTLCs. It's particularly inspired by ZmnSCPxj's thoughts from Dec 2019 [0], and some of his and Lloyd Fournier's posts since then (which are listed in references) -- in particular, I think those allow us to drop the latency for forwarding a payment *massively* (though refunding a payment still requires roundtrips), and also support receiving via a mostly offline lightning wallet, which seems kinda cool. I somehow hadn't realised it prior to a conversation with @brian_trollz via twitter DM, but I think switching to PTLCs, even without eltoo, means that there's no longer any need to permanently store old payment info in order to recover the entirety of the channel's funds. (Some brute force is required to recover the timeout info, but in my testing I think that's about 0.05 seconds of work per ptlc output via python+libsecp256k1) This doesn't require any soft-forks, so I think we could start work on it immediately, and the above benefits actually seem pretty worth it, even ignoring any privacy/efficiency benefits from doing taproot key path spends and forwarding PTLCs. I've sketched up the musig/musig2 parts for the "balance" transactions in python [1] and tested it a little on signet [2], which I think is enough to convince me that this is implementable. There'll be a bit of preliminary work needed in actually defining specs/BIPs for musig and musig2 and adaptor signatures, I think. Anyway, details follow. They're also up on github as a gist [3] if that floats your boat. [0] https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-December/002375.html [1] https://github.com/ajtowns/bitcoin/blob/202109-ptlc-lnpenalty/test/functional/feature_ln_ptlc.py [2] The balance transaction (spending the funding tx and with outputs being Alice's and Bob's channel balance is at): https://explorer.bc-2.jp/tx/ba58d99dfaad83e105a0de1a9becfcf8eaf897aaaada54bd7b08134ff579997c?input:0&expand [3] https://gist.github.com/ajtowns/12f58fa8a4dc9f136ed04ca2584816a2/ 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. 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, 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) - b(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/k with script paths: + "LENGTH 32 EQUALVERIFY HASH160 <X> EQUALVERIFY <B/2/n/i/k> CHECKSIGVERIFY <A/2/n/i/k> CHECKSIG" + "<A/2/n/i/k/1> CHECKSIGVERIFY <T> CLTV" * A ptlc paying to Bob: pays to RP/2/k with script paths: + "<B/2/n/i/k> CHECKSIG NOTIF <T> CLTV DROP ENDIF <A/2/n/i/k> CHECKSIG" Any outputs that would be zero or dust are not included. Note that we number each currently inflight transaction by "k", starting at 0. The same htlc/ptlc may have a different value for k 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/k path. The output committed to is: * pays to RP/3/k with script path: + <B/3/n/i/k> 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/k. For each inflight ptlc, Alice provides an adaptor signature via the A/2/n/i/k/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/k and PB/3/k, 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*k 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