g0b1el [ARCHIVE] / is on Nostr

Last Notes

2023-06-19 17:42:30

- reply

📅 Original date posted:2023-05-09
🗒️ Summary of this message: Proposal to modify the PTLC protocol into Payment Route Reservation flow, supporting reusable static invoices with atomic proof of payment and payer proofs.
📝 Original message:
Proposal Summary
================
The following proposal is intended to adapt the existing PTLC protocol into Payment Route Reservation[1] flow. Modifying the original PTLC protocol slightly, we get support for reusable static invoices with atomic proof of payment and payer proofs, that don't require previous communications between sender and receiver. By doing so, we will also reduce the number of cryptographic calculations the sender needs to perform for each PTCL payment. Then a similar approach is also applied to HTLC, with the same benefits.
To best understand the proposal, let's first start by presenting the original PTLC protocol and then proceed to describe the iterative changes made to it.
PTLC protocol
=============
Let's use Alice, Bob, Carol, and Dave example from this page: https://github.com/BlockstreamResearch/scriptless-scripts/blob/master/md/multi-hop-locks.md
Z <--------------------------------------------------------------------- Z = z*G
Alice ---------------> Bob ---------------> Carol ------------------> Dave
| | | |
y0 y1 y2 z
tab=z+y0 tbc=z+y0+y1 tcd=z+y0+y1+y2
Tab=Z+y0*G Tbc=Z+y0*G+y1*G Tcd=Z+y0*G+y1*G+y2*G
* y0, y1, y2 - decorrelation secrets
* z - proof of payment
* tij - adaptor secret for the adaptor point between nodes i and j
* Tij = tij*G adaptor lock point between nodes i and j
* sig(m,Tij) := psig(i,m,Tij) + psig(j,m,Tij) + tij - is the complete Schnorr signature for the transaction between i and j.
A brief summary of the PTLC protocol:
1. The receiver, Dave, shares proof of payment point Z(=z*G) with the sender, Alice. This is typically done by publishing a QR code.
2. Alice generates random decorrelation secrets (y0, y1, y2).
3. For each hop in the route, Alice calculates a tuple (Li,yi,Ri) using the formula:
Ri <- Li + yi*G and Lj <- Ri.
* Li - left adaptor point
* Ri - right adaptor point
* yi - decorrelation secret
4. Alice generates a payment onion that includes the previously calculated lock information for each hop on the route. For Dave, Alice includes (y0+y1+y2) decorrelation secret sum(we ignore stuckless payment for now).
5. Forwarding nodes use the lock information to construct a partial 2-of-2 MuSig2 signature.
6. When Dave signs the transaction with Carol, he reveals the adaptor secret `tcd` to Carol.
7. Carol then calculates adaptor `tbc` secret using the formula `tbc = tcd - y2`, which allows her to sign the transaction with Bob.
8. Bob calculates the adaptor secret `tab` using the similar formula `tab = tbc - y1`.
9. Eventually, when Bob signs his transactions with Alice, Alice can calculate the proof of payment `z = tab - y0`.
Note that Alice does a lot of work here, especially in step 3, which requires a lot of elliptic curve additions and multiplications. This workload increases with the length of the route, resulting in more work for the sender. While this is not typically problematic, it can become an issue if the sender is a mobile wallet with limited computational resources.
PTLC with reusable static invoices
==================================
We gonna make two modifications to the vanilla PTLC flow:
1) To alleviate Alice of heavy elliptic curve calculations, we will let routing nodes calculate their decorations secrets and adaptor points independently. But in such a way that the sender (Alice) and routing nodes get to the same shared decorrelation secret. This can be easily done because sphinx onion routing already establishes one shared secret with each hop, from which we can calculate as much as new shared secrets as we want.
For instance, we can use this formula:
yi = hmac("decorrelation secret", sharedSecret(i))
2) The second change we gonna make is how the tuple (Li,yi,Ri) is calculated for each hop.
Currently is made using this formula:
Ri <- Li + yi*G, Lj <- Ri.
and we gonna change it into:
Ri + yi*G <- Li and Lj <- Ri.
After applying this formula to the previous example, we get the following:
Alice ---------------> Bob ---------------> Carol ----------------> Dave
| | | |
y1 y2 y3, z
tab=(z+y1+y2+y3) tbc=(z+y2+y3) tcd=(z+y3)
During the PTLC resolve phase, everything remains the same, with the exception that intermediate hops will now add their decorrelation secrets instead of subtracting them:
tbc = tcd + y2
tab = tbc + y1.
In addition, Alice calculates the proof of payment (z) slightly differently:
z = tab - (y1 + y2 + y3) // tab will get when bob signs the transactionAB, (y1, y2 and y3) she has already calculated using shared secrets.
We will now apply the new PTLC protocol to the Payment Route Reservation flow[1]:
add_res(amount,onion,...) add_res(amount,onion,...) add_res(amount,onion,...)
Alice -----------------------> Bob -----------------------> Carol ------------------------> Dave
| | | |
| y1 y2 y3, z
| | | |
| res_succes(Z+Y3+Y2+Y1,...) | res_succes(Z+Y3+Y2,...)| res_succes(Z+Y3,...) |
| <-------------------------- <--------------------------- <----------------------------|
<---------------------------------------- Z -------------------------------------------------|
Z+(y1+y2+y3)*G =? Tab
| |
| sign_commitment sign_commitment sign_commitment |
| revoke_and_ack revoke_and_ack revoke_and_ack |
| <-------------------------> | <-------------------------> | <----------------------------->|
During `res_success` call, each intermediate hop gets to the expected upstream and downstream adaptor lock point, thereby obtaining all the necessary information to proceed to the commitment phase.
With just this change, PTLC protocol would NOT be safe. Bob can send Alice a lock point for which he is the one with knowledge of the secret. To prevent this, Dave needs to "send" Z point to Alice. However, Dave cannot include Z as part of the res_success response because the same Z would appear on every node, reintroducing payment correlation. The proposal on how the sender and receiver can exchange messages is left for another proposal because this got too big. This action will be denoted just as "send" in this proposal.
There are two benefits of doing PTLC this way:
1) Smaller hop onion and less work to be done by the sender. Alice has delegated all the heavy curve multiplications work to the routing nodes. Alice still has to calculate shared decorations secrets(simple hashing operation) and do one curve multiplications (y1+y2+y3)*G. As a result, this protocol should have an overall positive impact on mobile clients.
2) The biggest improvement is how Alice gets to proof of payment point Z. Now, new unique proof of payment z can be generated with every payment reservation. As a result, we can generate a single static invoice that can be paid simultaneously by multiple parties multiple times without any previous communication between the sender and receiver.
PTLC with reusable static invoices and stuckless payments[2]
============================================================
Note that the adaptor lock between Carol and Dave is built solely by Dave. This means stuckless payments would not work in such a PTLC protocol. We can already think of reservations as a weaker form of stuckless payment. When Dave sends `resservation_success` it can be seen as `ACK`(from the original stuckless payment proposal), and when Alice signs and revokes commitment with the first hop(Bob) it can be seen as `key` send. But there is still a chance for payment to get stuck during `sign_commitment` phase.
If we want to add support for stuckless payments, or if we want to increase the safety of the new PTLC protocol, we can create a third PTLC protocol by combining the previous two.
Each hop will now generate two decorrelation secrets, `fi` and `bi`:
fi = hmac("forward decorrelation secret", sharedSecret(i)) - used during add_reservation
bi = hmac("backward decorrelation secret", sharedSecret(i)) - used during res_success
Lock adaptor points are now calculated using this formula:
Ri + bi*G <- Li + fi*G, Lj <- Ri.
add_res(amount,F0,onion,...) add_res(amount,F0+F1,onion,...) add_res(amount,F0+F1+F2,onion,...)
Alice ---------------------------> Bob --------------------------> Carol ----------------------------------> Dave
| | | |
f0 f1,b1 f2,b2 f3,b3,z
| | | |
| res_succes(Z+B3+B2+B1,...) | res_succes(Z+B3+B2,...) | res_succes(Z+B3,...) |
| <----------------------------- <------------------------------ <------------------------------------|
| Tab=(F0)+(Z+B3+B2+B1) Tbc=(F0+F1)+(Z+B3+B2) Tcd=(F0+F1+F2)+(Z+B3) |
|<------------------------------------------- Z -----------------------------------------------------------|
Z+(f0+b1+b2+b3)*G =? Tab
Alice will pass (f0+f1+f2)*G point inside the onion to Dave as a precautionary measure, just to make sure routing nodes don't do anything out of order. Dave will check if `add_res` call from Carol contains the expected forward decorrelation point sum.
During the PTLC resolve phase, routing nodes would calculate the upstream lock secret by subtracting fi and adding bi:
li = ri - fi + bi
Alice will calculate proof of payment z, using this formula:
z = tab - (y1 + y2 + y3) - (f0)
This PTLC protocol now supports both reusable static invoices and stuckless payments.
PTLC with atomic Proof of Payment and Payer Proof
=================================================
The issue with the above construct is that proof of payment is known by Alice and Dave. Dave can give z, for instance, to Oscar, and if Alice comes for a refund, Dave can say that she wasn't the one that paid. Dave now can claim it was Oscar because Oscar knows proof of payment as well.
To fix this, we will borrow the idea of a `payer` key from bolt12[3] and pay for the signature[4] proposals. Alice will generate a unique `payer` secret, and then pass `payer_id`(=payer*G) point to Dave as part of the onion. This time Dave will not generate proof of payment z randomly but calculates z as Schnor's signature of the message.
z = r + h(m|R)*d
d - Dave's private key
r - random secret, R = r*G
m - the message.
The signature message can be "`payer_id` send Dave `amount` satoshis", or it can be a hash of a Merkle Tree as described in Bolt12[3]. To avoid passing the message between the payer and the sender, the message format should be defined on the protocol level. Alice can use this `payer` secret later to sign some message to prove she is the payer.
As described above, Alice will find out Z(=z*G) when `res_success` reaches her node. But she still can't validate that this public key commits to the signature of the message "`payer_id` send Dave `amount` satoshis", because she doesn't know R. To fix this Dave will "send" R instead Z to Alice. There is no need to send Z anymore because Z can be calculated.
Assuming the payment reservation was successful, and Dave has "send" R to Alice, Alice can now validate:
Z =? R + h(m|R)D, where Z = Tab-(f0+b1+b2+b3)*G.
* D - Dave's public key
If the equation holds, Alice can safely sign and revoke commitment with first hop Bob(and then "send" the stuckless key in case of stuckless payments to Dave), knowing she'll get both proofs if the receiver accepts the payment by revealing z secret.
Atomic Multipath Payments
-------------------------
Everything remains the same as in the original PTLC proposal.
HTLC with reusable static invoices with payment and payer proof
===============================================================
A similar procedure can be implemented for HTLC payments. Now `add_res` will not contain the payment hash. Payment hash H will be generated by the receiver(Dave) upon `add_reservaion` call and sent back to the sender and forwarding nodes as part of `res_success` response. Dave will also need to "send" the payment hash to Alice, to make sure routing nodes don't replace the payment hash with their hash value.
add_res(amount,onion,...) add_res(amount,onion,...) add_res(amount,onion,...)
Alice -----------------------> Bob -----------------------> Carol --------------------> Dave
| | | |
| | | |
| res_succes(H,...) | | res_succes(H,...)| | res_succes(H,...) |
| <-------------------------- <--------------------------- <-------------------------|
<-------------------------------------- H,z,R --------------------------------------------|
This construction gives us support for reusable invoices with atomic proof of payment. For payer proof, Alice sends `payer_id` in the onion, and Dave can "send" back a signed proof message (z, R), where a message can be "`payer_id` paid Dave `amount` satoshis only if `payer_id` knows primage of `H`. This way, we effectively link the atomic proof of payment with the payer proof in a cryptographically secure manner.
As it is currently, stuckles payments are not possible with HTLC unless a second hash is added into HTLC.
Different Types of Payments
===========================
Using the new PTLC/HTLC protocol, we can do a quick sketch of how different payment types will work. Here we will cover some basic use cases, though there may be many more:
1. Donations/Transfer/Key send/Spontaneous Payments/AMP...
-----------------------------------------------------------
There are multiple names for this payment type in circulation, such as donations, transfers, spontaneous payments, key sends, AMP, etc.
An example would be Alice wants to donate or transfer a certain amount of BTC to Dave. Alice also wants to receive proof of payment and payer proof.
Dave will share his `node_id` public key, either by publishing a static QR or plain text invoice. Dave can post some additional information in the invoice, but the only mandatory element is his public key. Alice scans the QR code and finds Dave's public key, picks the amount, and makes the payment. Payment proceeds as described above for PTLC/HTLC payments.
Side note for wallet developers, payer proof, might be undesirable for some donations. For instance, if we want to donate to Wikileaks, and our government is not a fan of Wikileaks, the last thing we want to have incriminating cryptographic proof saying we "paid x amount to Wikileaks". If payer proof is undesirable, the sender can omit `payer_id`, and the receiver will generate proof z randomly. Alternatively, the payer wallet can generate a random `payer_id` point. In either case, the donation transaction shouldn't appear in the payment history.
2. Purchases denominated in BTC
--------------------------------
1) One static invoice per article
An example would be a vending machine. Each article in the vending machine would have a small static QR code invoice next to it. The payer scans the invoice and then picks the quantity on his phone. If the vending machine supports multi-article purchases, the payer repeats this process for each article. Upon completion, click "send" to pay for the entire cart. If the payment succeeds, the vending machine dispenses the selected articles through a slot.
The mandatory fields in each static invoice are now `node_id`, `article_id`, and `price`. QR invoices can contain additional information like article name, article picture, etc..., which can be presented to the user on his mobile wallet.
The payment flow is similar to donations, with the exception that the buyer must provide additional information to the vending machine LN node so that the sender and receiver nodes can calculate the same proof message. The sender generates a new unique 'shopping_id` and includes this id with an array of tuples (`article_id`, `count`) as shopping information for Dave. Note that in this case maximum size of the article list is limited by the unused payment onion space. For very large purchases wallet can split the shopping cart into multiple sub-carts with different payments. Receiver Dave will now check that a payment amount matches the article price sum. The signed proof of payment message now has to contain `payer_id`, `shopping_id`, and a list of tuples (`article_id`, `count`, `price_per_article`).
Given the volatility of BTC prices, the article price on a static invoice may require frequent updates by vending machine operators. Even if prices are denominated in fiat currency, these invoices would require periodic updates. To address this issue, we can remove the article price from the invoice.
When the user scans the first article in the vending machine, the wallet informs the user that they need to retrieve the articles' prices to proceed.
This can be implemented as a new service, or a vending machine LN could be configured to "send" prices. Once the user receives the pricing information, the user can proceed with the purchase as before. This way, vending machine merchants would be able to update all article prices on their vending machines dynamically.
Lightning-based vending machines would be more cost-effective as they will not require a front-facing LCD, touch screen, or physical buttons. Furthermore, multiple customers would be able to make purchases simultaneously, though a single dispensing slot might result in conflicts about who bought which item. To address this issue, the vending machine could serialize item dispensing by delaying the dispensing of new shopping carts until the previous one is collected.
2) One dynamic invoice per shopping cart
An example would be web shopping. The user adds articles one by one into the shopping cart, clicks checkout, and then sends the payment for the whole cart.
Shopping chart invoices are dynamically created after each checkout and will contain information like a `shopping_id`, and an array of tuples (`article_id`, `count`, `price_per_article`). The payment flow is similar to single article purchases, except we are now sending just `payer_id` and `shopping_id` to the merchant node. We assume the merchant LN node can contact some other merchant service to get hashed signature message using `shopping_id`. The signed proof of payment message needs to contain `payer_id`, `shopping_id`, and a list of tuples (`article_id`, `count`, `price_per_article`). A merchant service will check if payment for this `shopping_id` hasn't been paid yet and if the payment amount corresponds to the whole cart amount.
Very large shopping carts might not fit into QR code invoices, which are limited in size. Also, larger QR code phones with weaker cameras could have difficulties scanning the code. This is an issue because the customer's wallet needs a whole shopping cart so he can validate that payer proof includes every item bought. For situations like this, merchants' QR can contain a link to the API call, which will return the whole shopping cart. Or the whole shopping chart can be "send" later during the settlement phase before the stuckless key is sent to the receiver.
3. Purchases denominated in fiat
--------------------------------
Purchases denominated in fiat can be seen as extensions of Purchases denominated in BTC, with potentially one more additional step.
Invoice now contains amounts denominated in some of the fiat currencies. Upon scanning the QR invoice, the sender will first convert the fiat amount into the BTC amount. The sender's wallet needs to track the BTC price, which most wallets already do today. Then the sender makes a payment as it is denominated in BTC using the converted amount. Onion information for the receiver should also contain the `original amount` and `original fiat currency`. Receiver checks if the reservation amount is greater or equal to his expected conversion amount. If it is, everything continues as before. The signed proof of payment message should now include `original amount`, `original currency`, and `BTC amount`.
If the amount is less than what the receiver expected, the receiver will accept payment reservation, but will also "send" a message to a sender with information about BTC missing amount for payment. The sender can decide if the receiver conversion is fair. If it is not, the sender can cancel the payment reservation. If additional payment is acceptable, the sender will create a new route with a missing amount. Unless the Bitcoin price drops significantly in the meantime, the receiver will accept a new reservation route, and payment will continue as before, but this time over one additional payment route.
4. Refund/ Partial Refund
-------------------------
Left out of this proposal, as refund requires additional constructs from Randevouz routing.
Conclusion
==========
This proposal extends the payment route reservation protocol, enabling the dynamic agreement of not only route fees, prepayment fees, and cltv deltas but also proof of payment and payer proof between the sender and receiver. Compared to Bolt12 offers proposal, there is no need for an additional round trip between sender and receiver to fetch the invoice, resulting in lower latency.
Best Regards,
g0b1el
[1] Payment Route Reservation:
Original proposal - https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-February/003867.html
Updated version - https://github.com/g0b1el/ln-design/blob/main/Payment%20Route%20Reservation.md
[2] Stuckless Payments - https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-June/002029.html
[3] Bolt12 - https://github.com/rustyrussell/lightning-rfc/blob/guilt/offers/12-offer-encoding.md
[4] Selling Signatures - https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-July/002077.html

2023-06-09 13:13:22

- reply

📅 Original date posted:2023-05-09
🗒️ Summary of this message: Proposal to modify the PTLC protocol into Payment Route Reservation flow, allowing for reusable static invoices with atomic proof of payment and payer proofs.
📝 Original message:
Proposal Summary
================
The following proposal is intended to adapt the existing PTLC protocol into Payment Route Reservation[1] flow. Modifying the original PTLC protocol slightly, we get support for reusable static invoices with atomic proof of payment and payer proofs, that don't require previous communications between sender and receiver. By doing so, we will also reduce the number of cryptographic calculations the sender needs to perform for each PTCL payment. Then a similar approach is also applied to HTLC, with the same benefits.
To best understand the proposal, let's first start by presenting the original PTLC protocol and then proceed to describe the iterative changes made to it.
PTLC protocol
=============
Let's use Alice, Bob, Carol, and Dave example from this page: https://github.com/BlockstreamResearch/scriptless-scripts/blob/master/md/multi-hop-locks.md
Z <--------------------------------------------------------------------- Z = z*G
Alice ---------------> Bob ---------------> Carol ------------------> Dave
| | | |
y0 y1 y2 z
tab=z+y0 tbc=z+y0+y1 tcd=z+y0+y1+y2
Tab=Z+y0*G Tbc=Z+y0*G+y1*G Tcd=Z+y0*G+y1*G+y2*G
* y0, y1, y2 - decorrelation secrets
* z - proof of payment
* tij - adaptor secret for the adaptor point between nodes i and j
* Tij = tij*G adaptor lock point between nodes i and j
* sig(m,Tij) := psig(i,m,Tij) + psig(j,m,Tij) + tij - is the complete Schnorr signature for the transaction between i and j.
A brief summary of the PTLC protocol:
1. The receiver, Dave, shares proof of payment point Z(=z*G) with the sender, Alice. This is typically done by publishing a QR code.
2. Alice generates random decorrelation secrets (y0, y1, y2).
3. For each hop in the route, Alice calculates a tuple (Li,yi,Ri) using the formula:
Ri <- Li + yi*G and Lj <- Ri.
* Li - left adaptor point
* Ri - right adaptor point
* yi - decorrelation secret
4. Alice generates a payment onion that includes the previously calculated lock information for each hop on the route. For Dave, Alice includes (y0+y1+y2) decorrelation secret sum(we ignore stuckless payment for now).
5. Forwarding nodes use the lock information to construct a partial 2-of-2 MuSig2 signature.
6. When Dave signs the transaction with Carol, he reveals the adaptor secret `tcd` to Carol.
7. Carol then calculates adaptor `tbc` secret using the formula `tbc = tcd - y2`, which allows her to sign the transaction with Bob.
8. Bob calculates the adaptor secret `tab` using the similar formula `tab = tbc - y1`.
9. Eventually, when Bob signs his transactions with Alice, Alice can calculate the proof of payment `z = tab - y0`.
Note that Alice does a lot of work here, especially in step 3, which requires a lot of elliptic curve additions and multiplications. This workload increases with the length of the route, resulting in more work for the sender. While this is not typically problematic, it can become an issue if the sender is a mobile wallet with limited computational resources.
PTLC with reusable static invoices
==================================
We gonna make two modifications to the vanilla PTLC flow:
1) To alleviate Alice of heavy elliptic curve calculations, we will let routing nodes calculate their decorations secrets and adaptor points independently. But in such a way that the sender (Alice) and routing nodes get to the same shared decorrelation secret. This can be easily done because sphinx onion routing already establishes one shared secret with each hop, from which we can calculate as much as new shared secrets as we want.
For instance, we can use this formula:
yi = hmac("decorrelation secret", sharedSecret(i))
2) The second change we gonna make is how the tuple (Li,yi,Ri) is calculated for each hop.
Currently is made using this formula:
Ri <- Li + yi*G, Lj <- Ri.
and we gonna change it into:
Ri + yi*G <- Li and Lj <- Ri.
After applying this formula to the previous example, we get the following:
Alice ---------------> Bob ---------------> Carol ----------------> Dave
| | | |
y1 y2 y3, z
tab=(z+y1+y2+y3) tbc=(z+y2+y3) tcd=(z+y3)
During the PTLC resolve phase, everything remains the same, with the exception that intermediate hops will now add their decorrelation secrets instead of subtracting them:
tbc = tcd + y2
tab = tbc + y1.
In addition, Alice calculates the proof of payment (z) slightly differently:
z = tab - (y1 + y2 + y3) // tab will get when bob signs the transactionAB, (y1, y2 and y3) she has already calculated using shared secrets.
We will now apply the new PTLC protocol to the Payment Route Reservation flow[1]:
add_res(amount,onion,...) add_res(amount,onion,...) add_res(amount,onion,...)
Alice -----------------------> Bob -----------------------> Carol ------------------------> Dave
| | | |
| y1 y2 y3, z
| | | |
| res_succes(Z+Y3+Y2+Y1,...) | res_succes(Z+Y3+Y2,...)| res_succes(Z+Y3,...) |
| <-------------------------- <--------------------------- <----------------------------|
<---------------------------------------- Z -------------------------------------------------|
Z+(y1+y2+y3)*G =? Tab
| |
| sign_commitment sign_commitment sign_commitment |
| revoke_and_ack revoke_and_ack revoke_and_ack |
| <-------------------------> | <-------------------------> | <----------------------------->|
During `res_success` call, each intermediate hop gets to the expected upstream and downstream adaptor lock point, thereby obtaining all the necessary information to proceed to the commitment phase.
With just this change, PTLC protocol would NOT be safe. Bob can send Alice a lock point for which he is the one with knowledge of the secret. To prevent this, Dave needs to "send" Z point to Alice. However, Dave cannot include Z as part of the res_success response because the same Z would appear on every node, reintroducing payment correlation. The proposal on how the sender and receiver can exchange messages is left for another proposal because this got too big. This action will be denoted just as "send" in this proposal.
There are two benefits of doing PTLC this way:
1) Smaller hop onion and less work to be done by the sender. Alice has delegated all the heavy curve multiplications work to the routing nodes. Alice still has to calculate shared decorations secrets(simple hashing operation) and do one curve multiplications (y1+y2+y3)*G. As a result, this protocol should have an overall positive impact on mobile clients.
2) The biggest improvement is how Alice gets to proof of payment point Z. Now, new unique proof of payment z can be generated with every payment reservation. As a result, we can generate a single static invoice that can be paid simultaneously by multiple parties multiple times without any previous communication between the sender and receiver.
PTLC with reusable static invoices and stuckless payments[2]
============================================================
Note that the adaptor lock between Carol and Dave is built solely by Dave. This means stuckless payments would not work in such a PTLC protocol. We can already think of reservations as a weaker form of stuckless payment. When Dave sends `resservation_success` it can be seen as `ACK`(from the original stuckless payment proposal), and when Alice signs and revokes commitment with the first hop(Bob) it can be seen as `key` send. But there is still a chance for payment to get stuck during `sign_commitment` phase.
If we want to add support for stuckless payments, or if we want to increase the safety of the new PTLC protocol, we can create a third PTLC protocol by combining the previous two.
Each hop will now generate two decorrelation secrets, `fi` and `bi`:
fi = hmac("forward decorrelation secret", sharedSecret(i)) - used during add_reservation
bi = hmac("backward decorrelation secret", sharedSecret(i)) - used during res_success
Lock adaptor points are now calculated using this formula:
Ri + bi*G <- Li + fi*G, Lj <- Ri.
add_res(amount,F0,onion,...) add_res(amount,F0+F1,onion,...) add_res(amount,F0+F1+F2,onion,...)
Alice ---------------------------> Bob --------------------------> Carol ----------------------------------> Dave
| | | |
f0 f1,b1 f2,b2 f3,b3,z
| | | |
| res_succes(Z+B3+B2+B1,...) | res_succes(Z+B3+B2,...) | res_succes(Z+B3,...) |
| <----------------------------- <------------------------------ <------------------------------------|
| Tab=(F0)+(Z+B3+B2+B1) Tbc=(F0+F1)+(Z+B3+B2) Tcd=(F0+F1+F2)+(Z+B3) |
|<------------------------------------------- Z -----------------------------------------------------------|
Z+(f0+b1+b2+b3)*G =? Tab
Alice will pass (f0+f1+f2)*G point inside the onion to Dave as a precautionary measure, just to make sure routing nodes don't do anything out of order. Dave will check if `add_res` call from Carol contains the expected forward decorrelation point sum.
During the PTLC resolve phase, routing nodes would calculate the upstream lock secret by subtracting fi and adding bi:
li = ri - fi + bi
Alice will calculate proof of payment z, using this formula:
z = tab - (y1 + y2 + y3) - (f0)
This PTLC protocol now supports both reusable static invoices and stuckless payments.
PTLC with atomic Proof of Payment and Payer Proof
=================================================
The issue with the above construct is that proof of payment is known by Alice and Dave. Dave can give z, for instance, to Oscar, and if Alice comes for a refund, Dave can say that she wasn't the one that paid. Dave now can claim it was Oscar because Oscar knows proof of payment as well.
To fix this, we will borrow the idea of a `payer` key from bolt12[3] and pay for the signature[4] proposals. Alice will generate a unique `payer` secret, and then pass `payer_id`(=payer*G) point to Dave as part of the onion. This time Dave will not generate proof of payment z randomly but calculates z as Schnor's signature of the message.
z = r + h(m|R)*d
d - Dave's private key
r - random secret, R = r*G
m - the message.
The signature message can be "`payer_id` send Dave `amount` satoshis", or it can be a hash of a Merkle Tree as described in Bolt12[3]. To avoid passing the message between the payer and the sender, the message format should be defined on the protocol level. Alice can use this `payer` secret later to sign some message to prove she is the payer.
As described above, Alice will find out Z(=z*G) when `res_success` reaches her node. But she still can't validate that this public key commits to the signature of the message "`payer_id` send Dave `amount` satoshis", because she doesn't know R. To fix this Dave will "send" R instead Z to Alice. There is no need to send Z anymore because Z can be calculated.
Assuming the payment reservation was successful, and Dave has "send" R to Alice, Alice can now validate:
Z =? R + h(m|R)D, where Z = Tab-(f0+b1+b2+b3)*G.
* D - Dave's public key
If the equation holds, Alice can safely sign and revoke commitment with first hop Bob(and then "send" the stuckless key in case of stuckless payments to Dave), knowing she'll get both proofs if the receiver accepts the payment by revealing z secret.
Atomic Multipath Payments
-------------------------
Everything remains the same as in the original PTLC proposal.
HTLC with reusable static invoices with payment and payer proof
===============================================================
A similar procedure can be implemented for HTLC payments. Now `add_res` will not contain the payment hash. Payment hash H will be generated by the receiver(Dave) upon `add_reservaion` call and sent back to the sender and forwarding nodes as part of `res_success` response. Dave will also need to "send" the payment hash to Alice, to make sure routing nodes don't replace the payment hash with their hash value.
add_res(amount,onion,...) add_res(amount,onion,...) add_res(amount,onion,...)
Alice -----------------------> Bob -----------------------> Carol --------------------> Dave
| | | |
| | | |
| res_succes(H,...) | | res_succes(H,...)| | res_succes(H,...) |
| <-------------------------- <--------------------------- <-------------------------|
<-------------------------------------- H,z,R --------------------------------------------|
This construction gives us support for reusable invoices with atomic proof of payment. For payer proof, Alice sends `payer_id` in the onion, and Dave can "send" back a signed proof message (z, R), where a message can be "`payer_id` paid Dave `amount` satoshis only if `payer_id` knows primage of `H`. This way, we effectively link the atomic proof of payment with the payer proof in a cryptographically secure manner.
As it is currently, stuckles payments are not possible with HTLC unless a second hash is added into HTLC.
Different Types of Payments
===========================
Using the new PTLC/HTLC protocol, we can do a quick sketch of how different payment types will work. Here we will cover some basic use cases, though there may be many more:
1. Donations/Transfer/Key send/Spontaneous Payments/AMP...
-----------------------------------------------------------
There are multiple names for this payment type in circulation, such as donations, transfers, spontaneous payments, key sends, AMP, etc.
An example would be Alice wants to donate or transfer a certain amount of BTC to Dave. Alice also wants to receive proof of payment and payer proof.
Dave will share his `node_id` public key, either by publishing a static QR or plain text invoice. Dave can post some additional information in the invoice, but the only mandatory element is his public key. Alice scans the QR code and finds Dave's public key, picks the amount, and makes the payment. Payment proceeds as described above for PTLC/HTLC payments.
Side note for wallet developers, payer proof, might be undesirable for some donations. For instance, if we want to donate to Wikileaks, and our government is not a fan of Wikileaks, the last thing we want to have incriminating cryptographic proof saying we "paid x amount to Wikileaks". If payer proof is undesirable, the sender can omit `payer_id`, and the receiver will generate proof z randomly. Alternatively, the payer wallet can generate a random `payer_id` point. In either case, the donation transaction shouldn't appear in the payment history.
2. Purchases denominated in BTC
--------------------------------
1) One static invoice per article
An example would be a vending machine. Each article in the vending machine would have a small static QR code invoice next to it. The payer scans the invoice and then picks the quantity on his phone. If the vending machine supports multi-article purchases, the payer repeats this process for each article. Upon completion, click "send" to pay for the entire cart. If the payment succeeds, the vending machine dispenses the selected articles through a slot.
The mandatory fields in each static invoice are now `node_id`, `article_id`, and `price`. QR invoices can contain additional information like article name, article picture, etc..., which can be presented to the user on his mobile wallet.
The payment flow is similar to donations, with the exception that the buyer must provide additional information to the vending machine LN node so that the sender and receiver nodes can calculate the same proof message. The sender generates a new unique 'shopping_id` and includes this id with an array of tuples (`article_id`, `count`) as shopping information for Dave. Note that in this case maximum size of the article list is limited by the unused payment onion space. For very large purchases wallet can split the shopping cart into multiple sub-carts with different payments. Receiver Dave will now check that a payment amount matches the article price sum. The signed proof of payment message now has to contain `payer_id`, `shopping_id`, and a list of tuples (`article_id`, `count`, `price_per_article`).
Given the volatility of BTC prices, the article price on a static invoice may require frequent updates by vending machine operators. Even if prices are denominated in fiat currency, these invoices would require periodic updates. To address this issue, we can remove the article price from the invoice.
When the user scans the first article in the vending machine, the wallet informs the user that they need to retrieve the articles' prices to proceed.
This can be implemented as a new service, or a vending machine LN could be configured to "send" prices. Once the user receives the pricing information, the user can proceed with the purchase as before. This way, vending machine merchants would be able to update all article prices on their vending machines dynamically.
Lightning-based vending machines would be more cost-effective as they will not require a front-facing LCD, touch screen, or physical buttons. Furthermore, multiple customers would be able to make purchases simultaneously, though a single dispensing slot might result in conflicts about who bought which item. To address this issue, the vending machine could serialize item dispensing by delaying the dispensing of new shopping carts until the previous one is collected.
2) One dynamic invoice per shopping cart
An example would be web shopping. The user adds articles one by one into the shopping cart, clicks checkout, and then sends the payment for the whole cart.
Shopping chart invoices are dynamically created after each checkout and will contain information like a `shopping_id`, and an array of tuples (`article_id`, `count`, `price_per_article`). The payment flow is similar to single article purchases, except we are now sending just `payer_id` and `shopping_id` to the merchant node. We assume the merchant LN node can contact some other merchant service to get hashed signature message using `shopping_id`. The signed proof of payment message needs to contain `payer_id`, `shopping_id`, and a list of tuples (`article_id`, `count`, `price_per_article`). A merchant service will check if payment for this `shopping_id` hasn't been paid yet and if the payment amount corresponds to the whole cart amount.
Very large shopping carts might not fit into QR code invoices, which are limited in size. Also, larger QR code phones with weaker cameras could have difficulties scanning the code. This is an issue because the customer's wallet needs a whole shopping cart so he can validate that payer proof includes every item bought. For situations like this, merchants' QR can contain a link to the API call, which will return the whole shopping cart. Or the whole shopping chart can be "send" later during the settlement phase before the stuckless key is sent to the receiver.
3. Purchases denominated in fiat
--------------------------------
Purchases denominated in fiat can be seen as extensions of Purchases denominated in BTC, with potentially one more additional step.
Invoice now contains amounts denominated in some of the fiat currencies. Upon scanning the QR invoice, the sender will first convert the fiat amount into the BTC amount. The sender's wallet needs to track the BTC price, which most wallets already do today. Then the sender makes a payment as it is denominated in BTC using the converted amount. Onion information for the receiver should also contain the `original amount` and `original fiat currency`. Receiver checks if the reservation amount is greater or equal to his expected conversion amount. If it is, everything continues as before. The signed proof of payment message should now include `original amount`, `original currency`, and `BTC amount`.
If the amount is less than what the receiver expected, the receiver will accept payment reservation, but will also "send" a message to a sender with information about BTC missing amount for payment. The sender can decide if the receiver conversion is fair. If it is not, the sender can cancel the payment reservation. If additional payment is acceptable, the sender will create a new route with a missing amount. Unless the Bitcoin price drops significantly in the meantime, the receiver will accept a new reservation route, and payment will continue as before, but this time over one additional payment route.
4. Refund/ Partial Refund
-------------------------
Left out of this proposal, as refund requires additional constructs from Randevouz routing.
Conclusion
==========
This proposal extends the payment route reservation protocol, enabling the dynamic agreement of not only route fees, prepayment fees, and cltv deltas but also proof of payment and payer proof between the sender and receiver. Compared to Bolt12 offers proposal, there is no need for an additional round trip between sender and receiver to fetch the invoice, resulting in lower latency.
Best Regards,
g0b1el
[1] Payment Route Reservation:
Original proposal - https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-February/003867.html
Updated version - https://github.com/g0b1el/ln-design/blob/main/Payment%20Route%20Reservation.md
[2] Stuckless Payments - https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-June/002029.html
[3] Bolt12 - https://github.com/rustyrussell/lightning-rfc/blob/guilt/offers/12-offer-encoding.md
[4] Selling Signatures - https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-July/002077.html

2023-06-09 13:12:55

- reply

📅 Original date posted:2023-03-25
🗒️ Summary of this message: Payment correlation attacks can link senders and receivers by observing traffic, but are costly for well-distributed networks. Centralized networks are more vulnerable. Hash correlation is the most straightforward attack, but can be fixed with point time lock contracts.
📝 Original message:
Using payment correlation attacks adversary can try to link the sender and receiver of payment by observing traffic from the potential sender to the potential receiver. Such observations can be made by the adversary nodes if they are present on the payment path or if the adversary is able to monitor the network traffic of the potential sender and receiver. In some circumstances, the adversary can detect not only his presence on the payment path, but also if the monitored nodes are the sender and receiver.
___ ____ ____ ___
| | | | | | | |
--| S |->| A1 |--> ......... -->| A2 |->| R |--
|___| |____| |____| |___|
S - potential sender
R - potential receiver
A1, A2 - adversary surveillance node
For big well-distributed networks, these forms of attacks are very costly and can be economically applied only on a small set of nodes. However, if a network is centralized, with the majority of traffic passing through a small number of big nodes, an adversary's job is much easier. An adversary can monitor traffic on those nodes, or in the case of a state-funded surveillance adversary, an adversary can acquire a court order to get complete access to big nodes routing information.
The adversary job can be simplified if:
- A1 and A2 are the same nodes. The sender and receiver are connected through a single node, the adversary node.
- A2 and R are the same nodes. The receiver is some form of custodial wallet, directly controlled or in collusion with the adversary. The adversary is going to be aware of all income transactions. The only thing left is to find out who the sender is.
- S and A1 are the same nodes. If the sender is some form of custodial wallet, directly controlled or in collusion with the adversary, the sender has no privacy, so correlation attacks are unnecessary.
- S->A1 is an unpublished channel. An adversary can identify S as the sender for all payments originating from S and passing through A1.
- A2->R is an unpublished channel. An adversary can identify R as the receiver for all payments destined for R and passing through A2.
The most notable LN payment correlations in order of severity are:
* Hash correlation
* Amount correlation
* CLTV correlation
* Timing correlation
Hash correlation
================
Hash correlation is the most straightforward to detect for surveillance nodes. If adversary nodes A1 and A2 observe a payment with the same hash, they can confidently conclude that they are on the payment path. However, the adversary cannot yet determine with enough certainty whether S is the sender and R the receiver. Yet, when combined with other correlation attacks or network topology examination, the adversary can establish such a conclusion with enough probability.
Fortunately, payment hash correlation is soon expected to be fixed with point time lock contracts (PTLCs)[1]. Each payment hop will use a unique lock contract point, so there will be no information that can correlate different payments.
Amount correlation
==================
Payment amount correlation is only slightly better than hash correlation in terms of privacy because the receiver amount on each hop is mixed with the fees of all the downstream nodes. Fees on LN are just a tiny fraction of the amount, so for the attacker fees are not an issue, especially in combination with timing correlation attacks.
Single-path payments are the most vulnerable to amount correlation attacks. Besides the fact that nodes A1 and A2 will see a payment with roughly the same amount, node A2 depending on the payment amount, can conclude that R is a receiver. For instance, if the receiver is a shop that sells some product for X satoshis, and if the attacker sees a payment of around X satoshis, he can be sure that this payment goes to that shop node.
Multi-path payments have better privacy because the amount is now split into multiple parts. The attacker can not easily find out what product the sender is buying. But there is still a potential correlation factor, depending on how we split the payment amount.
If we split the payment into equal parts, the attacker still can find out if a partial payment is multiple of the price of some of the shop products. Also, those sub-payment paths will be easily distinguishable by the amount, just like in the case of single-path payment.
So, what can be done to de-correlate sub-path payment amounts?
Rather than splitting the payment amount into equal parts, we split it into predefined values. For instance: 10k, 20k, 50k, 100k, 200k, 500k, 1000k, ... satoshis. Just like physical cash. By doing so, every individual payment is part of a much larger anonymity set consisting of all the payments at that moment. Using this approach, we can split a payment into as many paths as needed until we get to the exact number of satoshis. Splitting the payment amount into enough sub-paths to get an exact amount might be an overhead if current satoshi value, fees, and latencies are taken into account. Depending on user privacy preference, the wallet can create a payment path with exact change or overpay to the closest predefined value.
For instance, if there is a payment of 459,645 satoshis.
Users not that interested in privacy can split:
200k + 200k + 50k + 9,645.
While privacy-oriented users would overpay slightly:
200k + 200k + 50k + 10k.
Now sub-payments of privacy-oriented users are mixed with all other privacy-oriented and non-privacy-oriented users. Thus, the anonymity set is increased subsectional, especially if LN is processing a huge amount of transactions per second.
The drawback in splitting payment amounts into predefined values is that we might create more redundant payment[2] routes to match the reliability of sub-payments split into equal parts. When we split into equal parts, every redundant payment path can be used to replace any other failed paths. But in the case of predefined values, redundant sub-payment can replace only the sub-path with the same payment amount.
CLTV correlation
================
CLTV correlation is not as serious as hash or amount correlation because it doesn't explicitly connect payment routes through adversary nodes. CLTV value does give a sense of closeness to either sender or receiver. However, if hop CLTV delta values used are exactly as the one nodes gossiped, then an attacker can potentially determine the payment path as well. This is especially true when CLTV deltas are used in combination with timing correlation, allowing the attacker to calculate all cltv path combinations between A1 and A2 and deduce if they are on the payment path.
With payment route reservation [2], CLTV delta gets shuffled thanks to the payment route split. If there is no route split node can return a random CLTV value around some predefined value. Thus for the attacker's job to correlate payment with payment route reservation, using only CLTV gets much harder.
Timing correlation
==================
Every low-latency network is susceptible to timing correlation attacks. The adversary observes the network traffic between the potential sender and receiver, and the time of the transactions is used to make correlations. This type of attack can be carried out even without LN node if the adversary can monitor the surveilled node's network traffic. Low-traffic networks are more vulnerable to timing attacks than high-traffic networks. As the number of LN users and payments continues to grow, the potential payment set will increase, making it increasingly difficult to correlate payments using only timing analysis.
To mitigate timing correlation attacks, a possible solution is to introduce a small random delay for privacy-oriented payments. This approach can make the attacker's job somewhat harder.
What the attacker would most likely do is use a combination of amount, cltv, and timing correlation attacks. Each correlation attack will give some probability, and cumulative probability might reveal the payment route and, in the worst case, the sender and receiver. Therefore, it is crucial to minimize the probability of success for each attack to ensure the highest possible payment privacy.
[1] https://bitcoinops.org/en/topics/ptlc/
[2] https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-February/003867.html
Best Regards,
g0b1el

2023-06-09 13:12:52

- reply

📅 Original date posted:2023-03-02
🗒️ Summary of this message: Improvements to Lightning Network routing include all nodes on the route receiving the same amount to reserve, simplifying rendezvous routing, and eliminating the need for an HTLC onion in the second step.
📝 Original message:
There are two more improvements I missed in my first mail.
The first one is that all the nodes on the route get the same amount to reserve. So there is no need to put the amount inside the onion. This way node can fail reservation faster if there is no reservation balance left without opening the onion. Also, the onion gets smaller, and now it holds just the next hop information. This might simplify rendezvous routing(needs to explore this further).
And the second improvement is that we don't need HTLC onion in the second step. Route hops already contain all the information to create HTLC. So all that's left to do is for the sender to sign the commitment and to revoke the state with a first node in the route. Thus increase in payment latency would be just one more call between the route nodes.
Best Regards,
g0b1el
> If ASCII graphics are not rendering correctly, you can read the proposal on the mailing list archive, where for some reason are rendered correctly - https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-February/003867.html

2023-06-09 13:12:46

- reply

📅 Original date posted:2023-02-26
🗒️ Summary of this message: Proposal for Payment Route Reservation in Lightning Network to improve reliability, lower latency and fees, increase privacy, and simplify routing algorithm.
📝 Original message:
Hi, lightning devs
It's my first mail, so first, I'd like to say a big thanks to everyone involved in the development of the lightning network.
I've just finished going through this mailing list, so I'm not sure if Payment Route Reservation is already proposed in some other place. If there is a similar proposal, please point me to the right place.
I'll first list some potential improvements with this proposal:
1) Higher reliability of payments
2) Lower payment latency (on average)
3) Lower fees
4) Increase in privacy
5) Trampoline payment improvements
6) Significant reduction of gossip messages
7) Healthier, more decentralized network
8) Simplified routing algorithm
9) LN Wallet UX improvements
10) Fast spam prevention
11) Channel liquidity probing prevention
12) Eliminates the need for splice-in (and partially splice-out)
13) Eliminates the need for rebalancing and fee update scripts
14) Eliminates the need for global nodes' reputation
So what is a payment route reservation?
Payment Route Reservation
=========================
The idea behind Payment Route Reservation is to split the payment into two steps. In the first step, we reserve the route, and in the second, we send a payment. In the reservation step, routing nodes will not sign a new commitment state. Instead, they will just reserve a specified amount of satoshis. Those satoshis might be used with the next payment step or not if the reservation is canceled. Each reservation has a timeout (let's say 1 min). After a timeout, the reservation is removed from the channel reservation set and considered canceled. Reservation can be canceled manually by any upstream node.
For example:
add_reservation(payment_hash, amount) -->
┌───┐ ┌───┐ ┌───┐
───────►│ ├────────►│ ├────────►│ ├────────►
S │ A │ │ B │ │ C │ R
◄───────┤ │◄────────┤ │◄────────┤ │◄────────
└───┘ └───┘ └───┘
<- reservation_success(fees_sum, cltv_delta_sum)
S is a sender, R is a receiver, and A, B, and C are routing nodes.
S wants to send `amount` satoshis with `payment hash`[1] to R. S first creates a reservation onion for A->B->C->R route and then sends the onion to the first node in the route, using `add_reservation` call. A unwraps the onion, and if he has enough unreserved balance in A->B channel, he will add a new reservation for the `amount` request to the channel reservation set and then forward the onion to B. Reservation in reservation set can be addressed by `payment hash`.
If A has an insufficient channel reservation balance, A will return 'reservation_failed' to the upstream node(sender S). B and C will do the same. Assuming there is enough reservation balance in all channels to reserve a payment, reservation flow eventually reaches R. R unwraps the onion and checks if he knows the preimage. If he knows, R returns `reservation_success` to upstream node C.
At this point, we have successfully reserved the payment route for `amount` satoshis from S to R. But, our route nodes haven't included the fees(or cltv_delta) of downstream nodes. `reservation_success` returns to upstream route node tuple (fees_sum, cltv_delta_sum). In this case, R will return (0, 0) to C because he is the last node in the route[2]. C will try to extend his reservation by fees from the R. If reservation extension is successful, C sends `reservation_success` to B, with a tuple increased by his fees[3] and his cltv delta. If C can't extend the reservation, he will send to B `reservation_failure` and to R `cancel_reservation`[4]. A will do the same. Eventually, if everything is ok with nodes A and B, S will receive a tuple (fees_sum, cltv_delta_sum). Now S knows precisely how much fees and cltv_delta route expects, and he can now send the payment onion. If S doesn't like the fees or cltv_delta, he can try some other route.
Let's compare current payment forwarding to payment with reservation forwarding:
+-------+ +-------+ +-------+ +-------+
| |--(1)---- update_add_htlc ---->| | | |--(1)---- add_reservation ---->| |
| | | | | |<-(2)---- reservation_success--| | reservation onion
| | | | ──|─────────────────────────────────────────────────
| |--(2)--- commitment_signed --->| | | |--(3)--- commitment_signed --->| |
| A |<-(3)---- revoke_and_ack ------| B | | A |<-(4)---- revoke_and_ack ------| B |
| | | | | | | | HTLC onion
| |<-(4)--- commitment_signed ----| | | |<-(5)--- commitment_signed ----| |
| |--(5)---- revoke_and_ack ----->| | | |--(6)---- revoke_and_ack ----->| |
| | | | | | | |
+-------+ +-------+ +-------+ +-------+
One `update_add_htlc` is now replaced with two calls - `add_reservation` and `reservation_success`. Also, we have two onions now.
When node A receives reservation_success with a tuple (fees_sum, cltv_delta_sum), nodes A and B have all the information to sign a new commitment transaction. The new commitment transaction amount would be `amount` + fees_sum, and cltv_delta would be cltv_delta_sum.
For now, we've just increased the latency. I have yet to check any implementation, so it is hard to guess how significant this increase is. The thing to note is that the reservation set is stored only in memory. No information needs to be stored in DB or replicated. If the node crashes with a live reservation, nothing bad can happen. So increase in latency would probably be proportional to 1 additional call between hops and how fast hops can unwrap the onion.
But before we tackle latency, let's first address the reliability of payments.
[1] For PTLC case, we can use points
[2] R can return some low random values to prevent C from discovering that R is the receiver.
[3] Fees can be ppm, base, or whatever fee function the node operator prefers.
[4] To ensure the node can always extend a reservation, we can set aside part of the channel reserve balance just for this case (let's say 0.5 percent).
Route Split Reservation
=======================
If the routing node can't add a new reservation because the channel reservation balance is insufficient, the node can try to find some other route to reserve the missing amount for the next downstream node.
For instance, A needs to forward a reservation of 10 mBTC to B, but A->B channel has only 8 mBTC left of its channel reservation capacity[5].
┌───┐ ┌───┐
10 │ │ 8 │ │ 10
────►│ A ├──────────►│ B ├───────►
│ │ │ │
└─┬─┘ └─▲─┘
│ │
│2 ┌───┐ │2
│ │ │ │
└────►│ C ├─────┘
│ │
└───┘
Rather than returning `reservation_failure` and losing the possibility to earn fees on the remaining 8 mBTC, A will try to find a route for the remaining 2 mBTC. Let's say A picks A->C->B route. It is important to note that the new route should share the same payment hash as the main route(->A->B->)[6]. Now B will accept to forward the reservation of 10 mBTC further because he knows if a payment route is ever constructed, and if the preimage is revealed, he will receive his 10 mBTC.
There can be optimization in terms of fees. For instance, A can renounce his A->C channel fees. So the only fee A needs to pay for the new route is for 2 mBTC on C->B route. Assuming network convergences to roughly the same fees on all nodes, cumulative route split fees effect would be the same as if the whole amount was routed through A->B. Although this example looks a bit too perfect, it's quite common on the plebnet part of the lightning network, where most nodes are created using Triangle Liquidity Swaps.
It is important to note that A now needs to take into account the fees and cltv_delta of the new route. Fees are the sum of the fees in A->B channel and A->C->B route. Cumulative cltv_delta would be maximum between A->B and A->C->B route.
Note that A can try multiple reservation routes. Also, if C doesn't have enough reserve balance, C can split a route through some node D to B, etc. To prevent infinite reservation recursion calls (in case of huge payment), the route split node will pass a tuple (max_fees, max_cltv_delta) that he will accept from the new route. Each node in the route will first decrement tuple by his fees and cltv_delta. If the new tuple contains any element below 0, the node will return `reservation_error`. If tuple elements are still positive, the reservation will continue, and decremented tuple will be passed to the next downstream node.
To hide the difference between the main route and route split, the payment sender will also send the tuple(max_fees, max_cltv_delta) that he accepts for the main payment route. Now, if someone is observing lightning network traffic, he wouldn't know if a reservation is for payment or route split. Thus we have an increase in privacy of payment.
Note that now we can also send payments larger than channel capacity A->B.
# Trampoline route split reservation
What if A and B don't have a direct channel, or the sender doesn't know the whole network topology or all the channels between A and B are suddenly disabled?
┌───┐ . ┌───┐
10 │ │----> . . ---->│ │ 10
────►│ A │----> . . ---->│ B ├─────►
│ │----> . ---->│ │
└───┘ └───┘
A still can try to reserve payments through different routes to B. Idea is similar to what is currently known as Trampoline Routing.
The biggest benefit of using Trampoline route split reservation payment over Trampoline Routing payment is that a sender, before initiating the payment, knows exactly how much in fees he needs to pay. As well as how big cltv_delta will be.
How expensive is a route split reservation?
A needs to create a new reservation onion, and until that route split reservation propagates to B, B can't forward the reservation further downstream.
So we increased latency again.
My guess is that reservations with route split payment will increase the reliability of single payments to the range of 90-95%. But can we reach 99% and finally lower the average latency?
[5] The outbound liquidity can be greater than 10 mBTC, but the reservation set has only 8 mBTC left.
[6] For PTLC A->B and C->B, payment hops need to commit to the same point.
Redundant Multi Route Payment Reservation
========================================
The idea is similar to what is now called Multi-Path Payments and Stuckless Payments[7].
┌───┐ ┌───┐ ┌───┐
│ ├──────►│ ├──────►│ │
────►│ R │ │ T │ │ U ├─────►
│ ├──────►│ │ ┌──►│ │
└───┘ └───┘ │ └───┘
│
.......................
┌───┐ ┌───┐ │ ┌───┐
S │ ├──────►│ │ └───►│ │
────►│ D │ │ E │ │ F ├─────► R
│ ├────┐ │ ├──┐ │ │
└───┘ │ └───┘ │ └───┘
│ │
┌───┐ │ ┌───┐ │ ┌───┐
│ │ └─►│ │◄─┘ │ │
────►│ A │ │ B │ │ C ├─────►
│ ├──────►│ ├─────► │ │
└───┘ └───┘ └───┘
The problem with a single route reservation is that reservation fees(or cltv) might be too high, and the sender will have to create a new reservation route hoping to get a better fee. Also, reservations might take longer than we are willing to wait.
To overcome this issue, we first split the amount into N parts[8], and then we create 2*N[9] reservation routes each for the amount of `payment amount`/N. Now a sender needs to wait for just N routes out of 2N to return `reservation_success`, and then initiate payment. Note that multiple reservation routes can go through the same node.
This now creates an interesting market dynamic where the fastest route wins. And the fastest route is with the fastest nodes. Now nodes are incentivized to compete with better internet and better hardware. There would also be competition between lightning node developers to create the fastest lightning node.
If a sender is not that interested in the speed of payment, he can wait for all 2N routes to return reservation results and then pick the cheapest N routes.
Now nodes also need to compete in fees as well. Cheaper the fees, the higher probability of the sender picking the route.
All this eventually will benefit lightning network users.
It doesn't matter if the channels are balanced or not. If the node is well connected and has enough outbound liquidity, the reservation route split should(in most cases) find a route to the next node. So there is no need for rebalancing or fee update scripts.
Just because nodes reserved the route doesn't mean they have to route the payment. There is still a probability of payment failure. Payment can fail because of reservation time out, node going offline, griefing node, etc. To further increase reliability, we can also add stuckles payments.
With Redundant Multi Route Payment Reservations, I believe the reliability of payments would be around the 99% percent range.
Latency, on average, should converge around a value much lower than the average value we have now.
[7] https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-June/002029.html
[8] Unless it is a small amount, for instance, below 0.5 mBTC.
[9] Or some other multiplier
LN Wallet UX improvements
=========================
Not every payment is the same. For instance, if I'm paying a groceries bill in a supermarket, I value the speed of payments more than fees. On the other hand, if I'm paying my electricity bill at home, I value fees more than the speed of transactions. Also, if I'm paying a VPN subscription, I care more about privacy and cost over transaction speed.
With route reservation, we can present the exact user fees he is going to pay, so wallet developers can add the following element to UX:
Radio box: Fast Payment | Cheap Payment | MaxPrivacy
- If a user selects `Fast Payment` wallet will wait for the first N fastest routes and initiate payment automatically(unless fees exceed in percents some config value).
- If a user selects the `Cheap Payments` node will wait for all 2N routes to return, pick N cheapest routes, and then present the user with fees and a send button. If fees are too high, the user can press the `Try again` button.
- For `MaxPrivacy` wallet will behave as in `Cheap Payment` mode, except the routing algorithm will prefer longer routes over smaller nodes, with preferably at least one Tor node.
*N routes can be N trampoline routes if a wallet doesn't have a whole network topology.
Gossip messages spam
====================
Currently, 97 percent or more LN gossip messages go to `channel_update` messages. The reason is that most nodes on the network are running some form of automatic fee adjustment script. If the number of nodes and channels continues to grow, soon, this can become unsustainable.
Reservation is not used just to reserve the route but also to inform a sender of fees and cltvs. Thus there is no need for nodes to publish their fees to the whole network. And thus, information like base_fee, ppm fee, and cltv can be removed from the `channel_update` message.
With route reservation, there is no need for channel rebalancing or fee update scripts. Node operators can still run fee update scripts without restrictions, but those updates would not propagate to the network.
Routing algorithm and network decentralization
=============================================
In terms of network topology, a current lightning network can be seen as a decentralized network. But in terms of a payment network, it is more a hub base network, where the majority of payments go through ~30 largest nodes. Medium and smaller nodes rarely forward any payment, and they are mostly used by big nodes for channel rebalancing. This is a big issue in terms of fairness(the rich are getting richer faster), privacy, reliability of the network, cost of a transaction, etc.
I would argue that this problem is not because the rich are rich but because of the routing algorithm. Currently, used routing algorithms usually calculate the probability of routing a payment over some channel as a channel capacity function. If the channel has a large capacity probability is higher, small channels will have a lower probability of payment routing. Because all wallets are effectively running in `Fast Payment` mode, the routing algorithm will almost always choose bigger channel routes than smaller ones and thus create the hub-based model we have today.
If we remove `fees` and `cltvs` from the gossip, what is left for the routing algorithm is `channel_capacity`, `htlc_minimum_msat` and `htlc_maximum_msat`.
`htlc_maximum_msat` - can be a local node config. If the reservation attempts to reserve a greater amount than the maximum allowed for a single payment, a node can try to split the reservation over multiple channels.
`htlc_maximum_msat` - can remain a global config to avoid unnecessary reservation failures.
What about channel capacity?
Channel capacity can be the biggest misleading factor for LN routing algorithms. For instance, I can create a node and then buy 100 channels with 1BTC each of income liquidity. Then I set all channel fees to 0. Every routing algorithm will try to route payments through my node, but my node can't route a single satoshi. I would suspect that today's most popular nodes on the LN network probably have way more inbound than outbound liquidity.
So I think that capacity should not be used at all as a heuristic in the routing algorithms.
I think a better approach would be if nodes would just publish their cumulative outbound liquidity over all channels. If there are routing node A and routing node B, and they are well connected, we know that we can send(in theory) from node A to node B, with route split, a maximum payment of `min(A.balance, B.balance)` amount.
This would also signal to the rest of the network where liquidity is needed and where there is too much liquidity. There would be no liquidity sinks, and network liquidity could be better deployed. Automatic channel opening becomes trivial.
But would the nodes lie?
If the node lies, the reservation will fail on his node, and if there is a lot of reservation failure on misleading nodes, neighbor nodes might close the channel with him. Also, while processing huge payment reservations, which will eventually fail, a node could have routed a smaller payment and earned fees. So nodes will be incentives to report the real outbound liquidity or lower if privacy is the issue.
Now routing algorithm has become very simple. We make routing decisions just on hop count from our node, on node reported balance, and a bit of randomness. Randomness is the most important part. If some route fails, we can't know which node to blame. It can be any node in the route. The routing algorithm should not track any blame information about individual nodes and would not try to blacklist any particular node. If the node is well connected and the routing algorithm is random enough, we should be able eventually to find enough routes to the sender. If there is a faulty, griefing, or just slow node in the network, we let nodes handle deputies themselves. Each node will track the local reputation of each of its neighbors. If there are a lot of failed payments from one neighbor, the node operator might contact that neighbor for an explanation or just close the channel to that neighbor node.
For privacy currencies, not publishing channel capacity is a necessity. Privacy currency users (like Monero) don't want to relieve any of their UTXO amounts. Privacy currency LN can avoid publishing their channel capacity and outbound node liquidity, and only make routing decisions on hop counts and randomness. There would probably be more reservation failures, especially for larger amounts, but it should be worth privacy preserved.
Fast spam prevention
====================
Fast spam is a situation on the network when malicious nodes start creating a lot of payments to the random nodes, which will never be resolved because the receiver does not know the payment preimage. The receiver can only fail the payment.
This is not possible with a reservation anymore because receivers will reject a reservation, and there will be no payment. Now, this is a lot better because the reservation does not commit to a new channel state, and no DB operations are involved.
But how to prevent reservation spam?
If the node sees a lot of reservation errors per minute coming from one channel, the node can throttle reservations coming from that channel. Eventually, if spam continues node operator can inform the neighbor node operator to investigate the reason. The neighbor node will do the same. And if the problem persists, the node operator can just close the channel.
But what if an attacker controls both nodes(receiver and sender) or if the attacker creates a circular route?
The malicious receiver node will accept the reservation, and then when HTLC comes, it just fails the payment. This would be basically fast spam again, with a bit more work to be done by the attacker.
As proposed before[10], we can demand a prepayment. If a node sees a large amount of failed payments per minute on some of its channels, a node can start demanding some prepayment to route HTLC. The problem is how much to charge. If we charge too little, spam will continue. If we charge too much, this will affect regular micro-payments.
We can extend reservation_success tuple with a prepayment fee. And we can adjust the fee on the fly. There is no need to propagate it to the whole network. A node can initially charge 0 prepayment fees. This is in their best interest because the routing algorithm will prefer routes without prepayment. The reason is that there is still a chance of payment failure. In a payment failure case, the sender loses the pre-payed amount unconditionally. Now if a node observes a large number of payment failures per minute, he can start aggressively increasing his prepayment fees, thus making the attack very costly.
There was also a discussion on how to send a prepayment. Wouldn't the first node in the route just steal all prepayment and then fail the payment?
There are two possible scenarios here:
- prepayment is less than or equal to the fees the node is going to earn routing the payment. In this case, it is in the node's best interest to route the payment.
- prepayment amount is greater than node payment fees. I can see two possible solutions:
- let a first node steal the prepayment. This should be fine because if prepayment gets so big, most likely, the attacker is the one being robbed. Honest users will prefer routes without a prepayment, especially large prepayments.
- we can also try to send multiple keysend prepayments, but there are some privacy issues here because the length of the route is revealed to the first node, and the last route node finds out who the receiver is. A slightly less bad option is to send prepayments for the parts of the route. For instance, one keysend is for the first half of the route. The second is for the second half of the route.
[10] https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-February/002547.html
Channel liquidity probing
=========================
With a route reservation split, inspecting channel liquidity from other nodes becomes significantly more demanding. The reason is the fact that reservations should rarely fail. Now observer needs to deduct the channel liquidity from the reservation response (fee,cltv_delta). If there is a reservation split, fees and cltv_delta will most likely be higher than if there is no reservation split. But every node can change fee and cltv_delta on the fly, and by just randomizing those values on every return, potential channel observer jobs get much harder.
Also, if the attacker starts sending a lot of reservation requests, those requests might be seen as a DOS attempt, and the node might start throttling the reservation requests.
No need for splice-in(and partially splice-out)
===============================================
The idea behind the splicing is to increase the capacity of the channel, so that channel can route bigger payments. Also, the routing algorithm prefers a bigger channel so the node would route more payments.
With route split reservations, this is not necessary anymore. For example, if nodes A and B have N channels between them, node A would have the option to reserve a route through all N channels during reservation. Thus N smaller channels can be seen as one big channel, not by routing algorithm but by node A. Routing algorithm will just care if there is a connection between A and B.
If nodes A and B have N channels between them, closing one channel basically becomes a splice-out operation.
Looking forward to your feedback.
Best Regards,
g0b1el

2023-06-09 13:12:46

- reply

📅 Original date posted:2023-02-26
🗒️ Summary of this message: Proposal on ASCII graphics rendering issue can be read on the mailing list archive where they are rendered correctly. Link provided.
📝 Original message:
If ASCII graphics are not rendering correctly, you can read the proposal on the mailing list archive, where for some reason are rendered correctly - https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-February/003867.html
Cheers,
g0b1el

2023-06-09 13:08:52

- reply

📅 Original date posted:2023-05-09
📝 Original message:
Proposal Summary
================
The following proposal is intended to adapt the existing PTLC protocol into Payment Route Reservation[1] flow. Modifying the original PTLC protocol slightly, we get support for reusable static invoices with atomic proof of payment and payer proofs, that don't require previous communications between sender and receiver. By doing so, we will also reduce the number of cryptographic calculations the sender needs to perform for each PTCL payment. Then a similar approach is also applied to HTLC, with the same benefits.
To best understand the proposal, let's first start by presenting the original PTLC protocol and then proceed to describe the iterative changes made to it.
PTLC protocol
=============
Let's use Alice, Bob, Carol, and Dave example from this page: https://github.com/BlockstreamResearch/scriptless-scripts/blob/master/md/multi-hop-locks.md
Z <--------------------------------------------------------------------- Z = z*G
Alice ---------------> Bob ---------------> Carol ------------------> Dave
| | | |
y0 y1 y2 z
tab=z+y0 tbc=z+y0+y1 tcd=z+y0+y1+y2
Tab=Z+y0*G Tbc=Z+y0*G+y1*G Tcd=Z+y0*G+y1*G+y2*G
* y0, y1, y2 - decorrelation secrets
* z - proof of payment
* tij - adaptor secret for the adaptor point between nodes i and j
* Tij = tij*G adaptor lock point between nodes i and j
* sig(m,Tij) := psig(i,m,Tij) + psig(j,m,Tij) + tij - is the complete Schnorr signature for the transaction between i and j.
A brief summary of the PTLC protocol:
1. The receiver, Dave, shares proof of payment point Z(=z*G) with the sender, Alice. This is typically done by publishing a QR code.
2. Alice generates random decorrelation secrets (y0, y1, y2).
3. For each hop in the route, Alice calculates a tuple (Li,yi,Ri) using the formula:
Ri <- Li + yi*G and Lj <- Ri.
* Li - left adaptor point
* Ri - right adaptor point
* yi - decorrelation secret
4. Alice generates a payment onion that includes the previously calculated lock information for each hop on the route. For Dave, Alice includes (y0+y1+y2) decorrelation secret sum(we ignore stuckless payment for now).
5. Forwarding nodes use the lock information to construct a partial 2-of-2 MuSig2 signature.
6. When Dave signs the transaction with Carol, he reveals the adaptor secret `tcd` to Carol.
7. Carol then calculates adaptor `tbc` secret using the formula `tbc = tcd - y2`, which allows her to sign the transaction with Bob.
8. Bob calculates the adaptor secret `tab` using the similar formula `tab = tbc - y1`.
9. Eventually, when Bob signs his transactions with Alice, Alice can calculate the proof of payment `z = tab - y0`.
Note that Alice does a lot of work here, especially in step 3, which requires a lot of elliptic curve additions and multiplications. This workload increases with the length of the route, resulting in more work for the sender. While this is not typically problematic, it can become an issue if the sender is a mobile wallet with limited computational resources.
PTLC with reusable static invoices
==================================
We gonna make two modifications to the vanilla PTLC flow:
1) To alleviate Alice of heavy elliptic curve calculations, we will let routing nodes calculate their decorations secrets and adaptor points independently. But in such a way that the sender (Alice) and routing nodes get to the same shared decorrelation secret. This can be easily done because sphinx onion routing already establishes one shared secret with each hop, from which we can calculate as much as new shared secrets as we want.
For instance, we can use this formula:
yi = hmac("decorrelation secret", sharedSecret(i))
2) The second change we gonna make is how the tuple (Li,yi,Ri) is calculated for each hop.
Currently is made using this formula:
Ri <- Li + yi*G, Lj <- Ri.
and we gonna change it into:
Ri + yi*G <- Li and Lj <- Ri.
After applying this formula to the previous example, we get the following:
Alice ---------------> Bob ---------------> Carol ----------------> Dave
| | | |
y1 y2 y3, z
tab=(z+y1+y2+y3) tbc=(z+y2+y3) tcd=(z+y3)
During the PTLC resolve phase, everything remains the same, with the exception that intermediate hops will now add their decorrelation secrets instead of subtracting them:
tbc = tcd + y2
tab = tbc + y1.
In addition, Alice calculates the proof of payment (z) slightly differently:
z = tab - (y1 + y2 + y3) // tab will get when bob signs the transactionAB, (y1, y2 and y3) she has already calculated using shared secrets.
We will now apply the new PTLC protocol to the Payment Route Reservation flow[1]:
add_res(amount,onion,...) add_res(amount,onion,...) add_res(amount,onion,...)
Alice -----------------------> Bob -----------------------> Carol ------------------------> Dave
| | | |
| y1 y2 y3, z
| | | |
| res_succes(Z+Y3+Y2+Y1,...) | res_succes(Z+Y3+Y2,...)| res_succes(Z+Y3,...) |
| <-------------------------- <--------------------------- <----------------------------|
<---------------------------------------- Z -------------------------------------------------|
Z+(y1+y2+y3)*G =? Tab
| |
| sign_commitment sign_commitment sign_commitment |
| revoke_and_ack revoke_and_ack revoke_and_ack |
| <-------------------------> | <-------------------------> | <----------------------------->|
During `res_success` call, each intermediate hop gets to the expected upstream and downstream adaptor lock point, thereby obtaining all the necessary information to proceed to the commitment phase.
With just this change, PTLC protocol would NOT be safe. Bob can send Alice a lock point for which he is the one with knowledge of the secret. To prevent this, Dave needs to "send" Z point to Alice. However, Dave cannot include Z as part of the res_success response because the same Z would appear on every node, reintroducing payment correlation. The proposal on how the sender and receiver can exchange messages is left for another proposal because this got too big. This action will be denoted just as "send" in this proposal.
There are two benefits of doing PTLC this way:
1) Smaller hop onion and less work to be done by the sender. Alice has delegated all the heavy curve multiplications work to the routing nodes. Alice still has to calculate shared decorations secrets(simple hashing operation) and do one curve multiplications (y1+y2+y3)*G. As a result, this protocol should have an overall positive impact on mobile clients.
2) The biggest improvement is how Alice gets to proof of payment point Z. Now, new unique proof of payment z can be generated with every payment reservation. As a result, we can generate a single static invoice that can be paid simultaneously by multiple parties multiple times without any previous communication between the sender and receiver.
PTLC with reusable static invoices and stuckless payments[2]
============================================================
Note that the adaptor lock between Carol and Dave is built solely by Dave. This means stuckless payments would not work in such a PTLC protocol. We can already think of reservations as a weaker form of stuckless payment. When Dave sends `resservation_success` it can be seen as `ACK`(from the original stuckless payment proposal), and when Alice signs and revokes commitment with the first hop(Bob) it can be seen as `key` send. But there is still a chance for payment to get stuck during `sign_commitment` phase.
If we want to add support for stuckless payments, or if we want to increase the safety of the new PTLC protocol, we can create a third PTLC protocol by combining the previous two.
Each hop will now generate two decorrelation secrets, `fi` and `bi`:
fi = hmac("forward decorrelation secret", sharedSecret(i)) - used during add_reservation
bi = hmac("backward decorrelation secret", sharedSecret(i)) - used during res_success
Lock adaptor points are now calculated using this formula:
Ri + bi*G <- Li + fi*G, Lj <- Ri.
add_res(amount,F0,onion,...) add_res(amount,F0+F1,onion,...) add_res(amount,F0+F1+F2,onion,...)
Alice ---------------------------> Bob --------------------------> Carol ----------------------------------> Dave
| | | |
f0 f1,b1 f2,b2 f3,b3,z
| | | |
| res_succes(Z+B3+B2+B1,...) | res_succes(Z+B3+B2,...) | res_succes(Z+B3,...) |
| <----------------------------- <------------------------------ <------------------------------------|
| Tab=(F0)+(Z+B3+B2+B1) Tbc=(F0+F1)+(Z+B3+B2) Tcd=(F0+F1+F2)+(Z+B3) |
|<------------------------------------------- Z -----------------------------------------------------------|
Z+(f0+b1+b2+b3)*G =? Tab
Alice will pass (f0+f1+f2)*G point inside the onion to Dave as a precautionary measure, just to make sure routing nodes don't do anything out of order. Dave will check if `add_res` call from Carol contains the expected forward decorrelation point sum.
During the PTLC resolve phase, routing nodes would calculate the upstream lock secret by subtracting fi and adding bi:
li = ri - fi + bi
Alice will calculate proof of payment z, using this formula:
z = tab - (y1 + y2 + y3) - (f0)
This PTLC protocol now supports both reusable static invoices and stuckless payments.
PTLC with atomic Proof of Payment and Payer Proof
=================================================
The issue with the above construct is that proof of payment is known by Alice and Dave. Dave can give z, for instance, to Oscar, and if Alice comes for a refund, Dave can say that she wasn't the one that paid. Dave now can claim it was Oscar because Oscar knows proof of payment as well.
To fix this, we will borrow the idea of a `payer` key from bolt12[3] and pay for the signature[4] proposals. Alice will generate a unique `payer` secret, and then pass `payer_id`(=payer*G) point to Dave as part of the onion. This time Dave will not generate proof of payment z randomly but calculates z as Schnor's signature of the message.
z = r + h(m|R)*d
d - Dave's private key
r - random secret, R = r*G
m - the message.
The signature message can be "`payer_id` send Dave `amount` satoshis", or it can be a hash of a Merkle Tree as described in Bolt12[3]. To avoid passing the message between the payer and the sender, the message format should be defined on the protocol level. Alice can use this `payer` secret later to sign some message to prove she is the payer.
As described above, Alice will find out Z(=z*G) when `res_success` reaches her node. But she still can't validate that this public key commits to the signature of the message "`payer_id` send Dave `amount` satoshis", because she doesn't know R. To fix this Dave will "send" R instead Z to Alice. There is no need to send Z anymore because Z can be calculated.
Assuming the payment reservation was successful, and Dave has "send" R to Alice, Alice can now validate:
Z =? R + h(m|R)D, where Z = Tab-(f0+b1+b2+b3)*G.
* D - Dave's public key
If the equation holds, Alice can safely sign and revoke commitment with first hop Bob(and then "send" the stuckless key in case of stuckless payments to Dave), knowing she'll get both proofs if the receiver accepts the payment by revealing z secret.
Atomic Multipath Payments
-------------------------
Everything remains the same as in the original PTLC proposal.
HTLC with reusable static invoices with payment and payer proof
===============================================================
A similar procedure can be implemented for HTLC payments. Now `add_res` will not contain the payment hash. Payment hash H will be generated by the receiver(Dave) upon `add_reservaion` call and sent back to the sender and forwarding nodes as part of `res_success` response. Dave will also need to "send" the payment hash to Alice, to make sure routing nodes don't replace the payment hash with their hash value.
add_res(amount,onion,...) add_res(amount,onion,...) add_res(amount,onion,...)
Alice -----------------------> Bob -----------------------> Carol --------------------> Dave
| | | |
| | | |
| res_succes(H,...) | | res_succes(H,...)| | res_succes(H,...) |
| <-------------------------- <--------------------------- <-------------------------|
<-------------------------------------- H,z,R --------------------------------------------|
This construction gives us support for reusable invoices with atomic proof of payment. For payer proof, Alice sends `payer_id` in the onion, and Dave can "send" back a signed proof message (z, R), where a message can be "`payer_id` paid Dave `amount` satoshis only if `payer_id` knows primage of `H`. This way, we effectively link the atomic proof of payment with the payer proof in a cryptographically secure manner.
As it is currently, stuckles payments are not possible with HTLC unless a second hash is added into HTLC.
Different Types of Payments
===========================
Using the new PTLC/HTLC protocol, we can do a quick sketch of how different payment types will work. Here we will cover some basic use cases, though there may be many more:
1. Donations/Transfer/Key send/Spontaneous Payments/AMP...
-----------------------------------------------------------
There are multiple names for this payment type in circulation, such as donations, transfers, spontaneous payments, key sends, AMP, etc.
An example would be Alice wants to donate or transfer a certain amount of BTC to Dave. Alice also wants to receive proof of payment and payer proof.
Dave will share his `node_id` public key, either by publishing a static QR or plain text invoice. Dave can post some additional information in the invoice, but the only mandatory element is his public key. Alice scans the QR code and finds Dave's public key, picks the amount, and makes the payment. Payment proceeds as described above for PTLC/HTLC payments.
Side note for wallet developers, payer proof, might be undesirable for some donations. For instance, if we want to donate to Wikileaks, and our government is not a fan of Wikileaks, the last thing we want to have incriminating cryptographic proof saying we "paid x amount to Wikileaks". If payer proof is undesirable, the sender can omit `payer_id`, and the receiver will generate proof z randomly. Alternatively, the payer wallet can generate a random `payer_id` point. In either case, the donation transaction shouldn't appear in the payment history.
2. Purchases denominated in BTC
--------------------------------
1) One static invoice per article
An example would be a vending machine. Each article in the vending machine would have a small static QR code invoice next to it. The payer scans the invoice and then picks the quantity on his phone. If the vending machine supports multi-article purchases, the payer repeats this process for each article. Upon completion, click "send" to pay for the entire cart. If the payment succeeds, the vending machine dispenses the selected articles through a slot.
The mandatory fields in each static invoice are now `node_id`, `article_id`, and `price`. QR invoices can contain additional information like article name, article picture, etc..., which can be presented to the user on his mobile wallet.
The payment flow is similar to donations, with the exception that the buyer must provide additional information to the vending machine LN node so that the sender and receiver nodes can calculate the same proof message. The sender generates a new unique 'shopping_id` and includes this id with an array of tuples (`article_id`, `count`) as shopping information for Dave. Note that in this case maximum size of the article list is limited by the unused payment onion space. For very large purchases wallet can split the shopping cart into multiple sub-carts with different payments. Receiver Dave will now check that a payment amount matches the article price sum. The signed proof of payment message now has to contain `payer_id`, `shopping_id`, and a list of tuples (`article_id`, `count`, `price_per_article`).
Given the volatility of BTC prices, the article price on a static invoice may require frequent updates by vending machine operators. Even if prices are denominated in fiat currency, these invoices would require periodic updates. To address this issue, we can remove the article price from the invoice.
When the user scans the first article in the vending machine, the wallet informs the user that they need to retrieve the articles' prices to proceed.
This can be implemented as a new service, or a vending machine LN could be configured to "send" prices. Once the user receives the pricing information, the user can proceed with the purchase as before. This way, vending machine merchants would be able to update all article prices on their vending machines dynamically.
Lightning-based vending machines would be more cost-effective as they will not require a front-facing LCD, touch screen, or physical buttons. Furthermore, multiple customers would be able to make purchases simultaneously, though a single dispensing slot might result in conflicts about who bought which item. To address this issue, the vending machine could serialize item dispensing by delaying the dispensing of new shopping carts until the previous one is collected.
2) One dynamic invoice per shopping cart
An example would be web shopping. The user adds articles one by one into the shopping cart, clicks checkout, and then sends the payment for the whole cart.
Shopping chart invoices are dynamically created after each checkout and will contain information like a `shopping_id`, and an array of tuples (`article_id`, `count`, `price_per_article`). The payment flow is similar to single article purchases, except we are now sending just `payer_id` and `shopping_id` to the merchant node. We assume the merchant LN node can contact some other merchant service to get hashed signature message using `shopping_id`. The signed proof of payment message needs to contain `payer_id`, `shopping_id`, and a list of tuples (`article_id`, `count`, `price_per_article`). A merchant service will check if payment for this `shopping_id` hasn't been paid yet and if the payment amount corresponds to the whole cart amount.
Very large shopping carts might not fit into QR code invoices, which are limited in size. Also, larger QR code phones with weaker cameras could have difficulties scanning the code. This is an issue because the customer's wallet needs a whole shopping cart so he can validate that payer proof includes every item bought. For situations like this, merchants' QR can contain a link to the API call, which will return the whole shopping cart. Or the whole shopping chart can be "send" later during the settlement phase before the stuckless key is sent to the receiver.
3. Purchases denominated in fiat
--------------------------------
Purchases denominated in fiat can be seen as extensions of Purchases denominated in BTC, with potentially one more additional step.
Invoice now contains amounts denominated in some of the fiat currencies. Upon scanning the QR invoice, the sender will first convert the fiat amount into the BTC amount. The sender's wallet needs to track the BTC price, which most wallets already do today. Then the sender makes a payment as it is denominated in BTC using the converted amount. Onion information for the receiver should also contain the `original amount` and `original fiat currency`. Receiver checks if the reservation amount is greater or equal to his expected conversion amount. If it is, everything continues as before. The signed proof of payment message should now include `original amount`, `original currency`, and `BTC amount`.
If the amount is less than what the receiver expected, the receiver will accept payment reservation, but will also "send" a message to a sender with information about BTC missing amount for payment. The sender can decide if the receiver conversion is fair. If it is not, the sender can cancel the payment reservation. If additional payment is acceptable, the sender will create a new route with a missing amount. Unless the Bitcoin price drops significantly in the meantime, the receiver will accept a new reservation route, and payment will continue as before, but this time over one additional payment route.
4. Refund/ Partial Refund
-------------------------
Left out of this proposal, as refund requires additional constructs from Randevouz routing.
Conclusion
==========
This proposal extends the payment route reservation protocol, enabling the dynamic agreement of not only route fees, prepayment fees, and cltv deltas but also proof of payment and payer proof between the sender and receiver. Compared to Bolt12 offers proposal, there is no need for an additional round trip between sender and receiver to fetch the invoice, resulting in lower latency.
Best Regards,
g0b1el
[1] Payment Route Reservation:
Original proposal - https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-February/003867.html
Updated version - https://github.com/g0b1el/ln-design/blob/main/Payment%20Route%20Reservation.md
[2] Stuckless Payments - https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-June/002029.html
[3] Bolt12 - https://github.com/rustyrussell/lightning-rfc/blob/guilt/offers/12-offer-encoding.md
[4] Selling Signatures - https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-July/002077.html

2023-06-09 13:08:23

- reply

📅 Original date posted:2023-03-25
📝 Original message:
Using payment correlation attacks adversary can try to link the sender and receiver of payment by observing traffic from the potential sender to the potential receiver. Such observations can be made by the adversary nodes if they are present on the payment path or if the adversary is able to monitor the network traffic of the potential sender and receiver. In some circumstances, the adversary can detect not only his presence on the payment path, but also if the monitored nodes are the sender and receiver.
___ ____ ____ ___
| | | | | | | |
--| S |->| A1 |--> ......... -->| A2 |->| R |--
|___| |____| |____| |___|
S - potential sender
R - potential receiver
A1, A2 - adversary surveillance node
For big well-distributed networks, these forms of attacks are very costly and can be economically applied only on a small set of nodes. However, if a network is centralized, with the majority of traffic passing through a small number of big nodes, an adversary's job is much easier. An adversary can monitor traffic on those nodes, or in the case of a state-funded surveillance adversary, an adversary can acquire a court order to get complete access to big nodes routing information.
The adversary job can be simplified if:
- A1 and A2 are the same nodes. The sender and receiver are connected through a single node, the adversary node.
- A2 and R are the same nodes. The receiver is some form of custodial wallet, directly controlled or in collusion with the adversary. The adversary is going to be aware of all income transactions. The only thing left is to find out who the sender is.
- S and A1 are the same nodes. If the sender is some form of custodial wallet, directly controlled or in collusion with the adversary, the sender has no privacy, so correlation attacks are unnecessary.
- S->A1 is an unpublished channel. An adversary can identify S as the sender for all payments originating from S and passing through A1.
- A2->R is an unpublished channel. An adversary can identify R as the receiver for all payments destined for R and passing through A2.
The most notable LN payment correlations in order of severity are:
* Hash correlation
* Amount correlation
* CLTV correlation
* Timing correlation
Hash correlation
================
Hash correlation is the most straightforward to detect for surveillance nodes. If adversary nodes A1 and A2 observe a payment with the same hash, they can confidently conclude that they are on the payment path. However, the adversary cannot yet determine with enough certainty whether S is the sender and R the receiver. Yet, when combined with other correlation attacks or network topology examination, the adversary can establish such a conclusion with enough probability.
Fortunately, payment hash correlation is soon expected to be fixed with point time lock contracts (PTLCs)[1]. Each payment hop will use a unique lock contract point, so there will be no information that can correlate different payments.
Amount correlation
==================
Payment amount correlation is only slightly better than hash correlation in terms of privacy because the receiver amount on each hop is mixed with the fees of all the downstream nodes. Fees on LN are just a tiny fraction of the amount, so for the attacker fees are not an issue, especially in combination with timing correlation attacks.
Single-path payments are the most vulnerable to amount correlation attacks. Besides the fact that nodes A1 and A2 will see a payment with roughly the same amount, node A2 depending on the payment amount, can conclude that R is a receiver. For instance, if the receiver is a shop that sells some product for X satoshis, and if the attacker sees a payment of around X satoshis, he can be sure that this payment goes to that shop node.
Multi-path payments have better privacy because the amount is now split into multiple parts. The attacker can not easily find out what product the sender is buying. But there is still a potential correlation factor, depending on how we split the payment amount.
If we split the payment into equal parts, the attacker still can find out if a partial payment is multiple of the price of some of the shop products. Also, those sub-payment paths will be easily distinguishable by the amount, just like in the case of single-path payment.
So, what can be done to de-correlate sub-path payment amounts?
Rather than splitting the payment amount into equal parts, we split it into predefined values. For instance: 10k, 20k, 50k, 100k, 200k, 500k, 1000k, ... satoshis. Just like physical cash. By doing so, every individual payment is part of a much larger anonymity set consisting of all the payments at that moment. Using this approach, we can split a payment into as many paths as needed until we get to the exact number of satoshis. Splitting the payment amount into enough sub-paths to get an exact amount might be an overhead if current satoshi value, fees, and latencies are taken into account. Depending on user privacy preference, the wallet can create a payment path with exact change or overpay to the closest predefined value.
For instance, if there is a payment of 459,645 satoshis.
Users not that interested in privacy can split:
200k + 200k + 50k + 9,645.
While privacy-oriented users would overpay slightly:
200k + 200k + 50k + 10k.
Now sub-payments of privacy-oriented users are mixed with all other privacy-oriented and non-privacy-oriented users. Thus, the anonymity set is increased subsectional, especially if LN is processing a huge amount of transactions per second.
The drawback in splitting payment amounts into predefined values is that we might create more redundant payment[2] routes to match the reliability of sub-payments split into equal parts. When we split into equal parts, every redundant payment path can be used to replace any other failed paths. But in the case of predefined values, redundant sub-payment can replace only the sub-path with the same payment amount.
CLTV correlation
================
CLTV correlation is not as serious as hash or amount correlation because it doesn't explicitly connect payment routes through adversary nodes. CLTV value does give a sense of closeness to either sender or receiver. However, if hop CLTV delta values used are exactly as the one nodes gossiped, then an attacker can potentially determine the payment path as well. This is especially true when CLTV deltas are used in combination with timing correlation, allowing the attacker to calculate all cltv path combinations between A1 and A2 and deduce if they are on the payment path.
With payment route reservation [2], CLTV delta gets shuffled thanks to the payment route split. If there is no route split node can return a random CLTV value around some predefined value. Thus for the attacker's job to correlate payment with payment route reservation, using only CLTV gets much harder.
Timing correlation
==================
Every low-latency network is susceptible to timing correlation attacks. The adversary observes the network traffic between the potential sender and receiver, and the time of the transactions is used to make correlations. This type of attack can be carried out even without LN node if the adversary can monitor the surveilled node's network traffic. Low-traffic networks are more vulnerable to timing attacks than high-traffic networks. As the number of LN users and payments continues to grow, the potential payment set will increase, making it increasingly difficult to correlate payments using only timing analysis.
To mitigate timing correlation attacks, a possible solution is to introduce a small random delay for privacy-oriented payments. This approach can make the attacker's job somewhat harder.
What the attacker would most likely do is use a combination of amount, cltv, and timing correlation attacks. Each correlation attack will give some probability, and cumulative probability might reveal the payment route and, in the worst case, the sender and receiver. Therefore, it is crucial to minimize the probability of success for each attack to ensure the highest possible payment privacy.
[1] https://bitcoinops.org/en/topics/ptlc/
[2] https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-February/003867.html
Best Regards,
g0b1el

2023-06-09 13:08:19

- reply

📅 Original date posted:2023-03-02
📝 Original message:
There are two more improvements I missed in my first mail.
The first one is that all the nodes on the route get the same amount to reserve. So there is no need to put the amount inside the onion. This way node can fail reservation faster if there is no reservation balance left without opening the onion. Also, the onion gets smaller, and now it holds just the next hop information. This might simplify rendezvous routing(needs to explore this further).
And the second improvement is that we don't need HTLC onion in the second step. Route hops already contain all the information to create HTLC. So all that's left to do is for the sender to sign the commitment and to revoke the state with a first node in the route. Thus increase in payment latency would be just one more call between the route nodes.
Best Regards,
g0b1el
> If ASCII graphics are not rendering correctly, you can read the proposal on the mailing list archive, where for some reason are rendered correctly - https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-February/003867.html

2023-06-09 13:08:13

- reply

📅 Original date posted:2023-02-26
📝 Original message:
If ASCII graphics are not rendering correctly, you can read the proposal on the mailing list archive, where for some reason are rendered correctly - https://lists.linuxfoundation.org/pipermail/lightning-dev/2023-February/003867.html
Cheers,
g0b1el

2023-06-09 13:08:12

- reply

📅 Original date posted:2023-02-26
📝 Original message:
Hi, lightning devs
It's my first mail, so first, I'd like to say a big thanks to everyone involved in the development of the lightning network.
I've just finished going through this mailing list, so I'm not sure if Payment Route Reservation is already proposed in some other place. If there is a similar proposal, please point me to the right place.
I'll first list some potential improvements with this proposal:
1) Higher reliability of payments
2) Lower payment latency (on average)
3) Lower fees
4) Increase in privacy
5) Trampoline payment improvements
6) Significant reduction of gossip messages
7) Healthier, more decentralized network
8) Simplified routing algorithm
9) LN Wallet UX improvements
10) Fast spam prevention
11) Channel liquidity probing prevention
12) Eliminates the need for splice-in (and partially splice-out)
13) Eliminates the need for rebalancing and fee update scripts
14) Eliminates the need for global nodes' reputation
So what is a payment route reservation?
Payment Route Reservation
=========================
The idea behind Payment Route Reservation is to split the payment into two steps. In the first step, we reserve the route, and in the second, we send a payment. In the reservation step, routing nodes will not sign a new commitment state. Instead, they will just reserve a specified amount of satoshis. Those satoshis might be used with the next payment step or not if the reservation is canceled. Each reservation has a timeout (let's say 1 min). After a timeout, the reservation is removed from the channel reservation set and considered canceled. Reservation can be canceled manually by any upstream node.
For example:
add_reservation(payment_hash, amount) -->
┌───┐ ┌───┐ ┌───┐
───────►│ ├────────►│ ├────────►│ ├────────►
S │ A │ │ B │ │ C │ R
◄───────┤ │◄────────┤ │◄────────┤ │◄────────
└───┘ └───┘ └───┘
<- reservation_success(fees_sum, cltv_delta_sum)
S is a sender, R is a receiver, and A, B, and C are routing nodes.
S wants to send `amount` satoshis with `payment hash`[1] to R. S first creates a reservation onion for A->B->C->R route and then sends the onion to the first node in the route, using `add_reservation` call. A unwraps the onion, and if he has enough unreserved balance in A->B channel, he will add a new reservation for the `amount` request to the channel reservation set and then forward the onion to B. Reservation in reservation set can be addressed by `payment hash`.
If A has an insufficient channel reservation balance, A will return 'reservation_failed' to the upstream node(sender S). B and C will do the same. Assuming there is enough reservation balance in all channels to reserve a payment, reservation flow eventually reaches R. R unwraps the onion and checks if he knows the preimage. If he knows, R returns `reservation_success` to upstream node C.
At this point, we have successfully reserved the payment route for `amount` satoshis from S to R. But, our route nodes haven't included the fees(or cltv_delta) of downstream nodes. `reservation_success` returns to upstream route node tuple (fees_sum, cltv_delta_sum). In this case, R will return (0, 0) to C because he is the last node in the route[2]. C will try to extend his reservation by fees from the R. If reservation extension is successful, C sends `reservation_success` to B, with a tuple increased by his fees[3] and his cltv delta. If C can't extend the reservation, he will send to B `reservation_failure` and to R `cancel_reservation`[4]. A will do the same. Eventually, if everything is ok with nodes A and B, S will receive a tuple (fees_sum, cltv_delta_sum). Now S knows precisely how much fees and cltv_delta route expects, and he can now send the payment onion. If S doesn't like the fees or cltv_delta, he can try some other route.
Let's compare current payment forwarding to payment with reservation forwarding:
+-------+ +-------+ +-------+ +-------+
| |--(1)---- update_add_htlc ---->| | | |--(1)---- add_reservation ---->| |
| | | | | |<-(2)---- reservation_success--| | reservation onion
| | | | ──|─────────────────────────────────────────────────
| |--(2)--- commitment_signed --->| | | |--(3)--- commitment_signed --->| |
| A |<-(3)---- revoke_and_ack ------| B | | A |<-(4)---- revoke_and_ack ------| B |
| | | | | | | | HTLC onion
| |<-(4)--- commitment_signed ----| | | |<-(5)--- commitment_signed ----| |
| |--(5)---- revoke_and_ack ----->| | | |--(6)---- revoke_and_ack ----->| |
| | | | | | | |
+-------+ +-------+ +-------+ +-------+
One `update_add_htlc` is now replaced with two calls - `add_reservation` and `reservation_success`. Also, we have two onions now.
When node A receives reservation_success with a tuple (fees_sum, cltv_delta_sum), nodes A and B have all the information to sign a new commitment transaction. The new commitment transaction amount would be `amount` + fees_sum, and cltv_delta would be cltv_delta_sum.
For now, we've just increased the latency. I have yet to check any implementation, so it is hard to guess how significant this increase is. The thing to note is that the reservation set is stored only in memory. No information needs to be stored in DB or replicated. If the node crashes with a live reservation, nothing bad can happen. So increase in latency would probably be proportional to 1 additional call between hops and how fast hops can unwrap the onion.
But before we tackle latency, let's first address the reliability of payments.
[1] For PTLC case, we can use points
[2] R can return some low random values to prevent C from discovering that R is the receiver.
[3] Fees can be ppm, base, or whatever fee function the node operator prefers.
[4] To ensure the node can always extend a reservation, we can set aside part of the channel reserve balance just for this case (let's say 0.5 percent).
Route Split Reservation
=======================
If the routing node can't add a new reservation because the channel reservation balance is insufficient, the node can try to find some other route to reserve the missing amount for the next downstream node.
For instance, A needs to forward a reservation of 10 mBTC to B, but A->B channel has only 8 mBTC left of its channel reservation capacity[5].
┌───┐ ┌───┐
10 │ │ 8 │ │ 10
────►│ A ├──────────►│ B ├───────►
│ │ │ │
└─┬─┘ └─▲─┘
│ │
│2 ┌───┐ │2
│ │ │ │
└────►│ C ├─────┘
│ │
└───┘
Rather than returning `reservation_failure` and losing the possibility to earn fees on the remaining 8 mBTC, A will try to find a route for the remaining 2 mBTC. Let's say A picks A->C->B route. It is important to note that the new route should share the same payment hash as the main route(->A->B->)[6]. Now B will accept to forward the reservation of 10 mBTC further because he knows if a payment route is ever constructed, and if the preimage is revealed, he will receive his 10 mBTC.
There can be optimization in terms of fees. For instance, A can renounce his A->C channel fees. So the only fee A needs to pay for the new route is for 2 mBTC on C->B route. Assuming network convergences to roughly the same fees on all nodes, cumulative route split fees effect would be the same as if the whole amount was routed through A->B. Although this example looks a bit too perfect, it's quite common on the plebnet part of the lightning network, where most nodes are created using Triangle Liquidity Swaps.
It is important to note that A now needs to take into account the fees and cltv_delta of the new route. Fees are the sum of the fees in A->B channel and A->C->B route. Cumulative cltv_delta would be maximum between A->B and A->C->B route.
Note that A can try multiple reservation routes. Also, if C doesn't have enough reserve balance, C can split a route through some node D to B, etc. To prevent infinite reservation recursion calls (in case of huge payment), the route split node will pass a tuple (max_fees, max_cltv_delta) that he will accept from the new route. Each node in the route will first decrement tuple by his fees and cltv_delta. If the new tuple contains any element below 0, the node will return `reservation_error`. If tuple elements are still positive, the reservation will continue, and decremented tuple will be passed to the next downstream node.
To hide the difference between the main route and route split, the payment sender will also send the tuple(max_fees, max_cltv_delta) that he accepts for the main payment route. Now, if someone is observing lightning network traffic, he wouldn't know if a reservation is for payment or route split. Thus we have an increase in privacy of payment.
Note that now we can also send payments larger than channel capacity A->B.
# Trampoline route split reservation
What if A and B don't have a direct channel, or the sender doesn't know the whole network topology or all the channels between A and B are suddenly disabled?
┌───┐ . ┌───┐
10 │ │----> . . ---->│ │ 10
────►│ A │----> . . ---->│ B ├─────►
│ │----> . ---->│ │
└───┘ └───┘
A still can try to reserve payments through different routes to B. Idea is similar to what is currently known as Trampoline Routing.
The biggest benefit of using Trampoline route split reservation payment over Trampoline Routing payment is that a sender, before initiating the payment, knows exactly how much in fees he needs to pay. As well as how big cltv_delta will be.
How expensive is a route split reservation?
A needs to create a new reservation onion, and until that route split reservation propagates to B, B can't forward the reservation further downstream.
So we increased latency again.
My guess is that reservations with route split payment will increase the reliability of single payments to the range of 90-95%. But can we reach 99% and finally lower the average latency?
[5] The outbound liquidity can be greater than 10 mBTC, but the reservation set has only 8 mBTC left.
[6] For PTLC A->B and C->B, payment hops need to commit to the same point.
Redundant Multi Route Payment Reservation
========================================
The idea is similar to what is now called Multi-Path Payments and Stuckless Payments[7].
┌───┐ ┌───┐ ┌───┐
│ ├──────►│ ├──────►│ │
────►│ R │ │ T │ │ U ├─────►
│ ├──────►│ │ ┌──►│ │
└───┘ └───┘ │ └───┘
│
.......................
┌───┐ ┌───┐ │ ┌───┐
S │ ├──────►│ │ └───►│ │
────►│ D │ │ E │ │ F ├─────► R
│ ├────┐ │ ├──┐ │ │
└───┘ │ └───┘ │ └───┘
│ │
┌───┐ │ ┌───┐ │ ┌───┐
│ │ └─►│ │◄─┘ │ │
────►│ A │ │ B │ │ C ├─────►
│ ├──────►│ ├─────► │ │
└───┘ └───┘ └───┘
The problem with a single route reservation is that reservation fees(or cltv) might be too high, and the sender will have to create a new reservation route hoping to get a better fee. Also, reservations might take longer than we are willing to wait.
To overcome this issue, we first split the amount into N parts[8], and then we create 2*N[9] reservation routes each for the amount of `payment amount`/N. Now a sender needs to wait for just N routes out of 2N to return `reservation_success`, and then initiate payment. Note that multiple reservation routes can go through the same node.
This now creates an interesting market dynamic where the fastest route wins. And the fastest route is with the fastest nodes. Now nodes are incentivized to compete with better internet and better hardware. There would also be competition between lightning node developers to create the fastest lightning node.
If a sender is not that interested in the speed of payment, he can wait for all 2N routes to return reservation results and then pick the cheapest N routes.
Now nodes also need to compete in fees as well. Cheaper the fees, the higher probability of the sender picking the route.
All this eventually will benefit lightning network users.
It doesn't matter if the channels are balanced or not. If the node is well connected and has enough outbound liquidity, the reservation route split should(in most cases) find a route to the next node. So there is no need for rebalancing or fee update scripts.
Just because nodes reserved the route doesn't mean they have to route the payment. There is still a probability of payment failure. Payment can fail because of reservation time out, node going offline, griefing node, etc. To further increase reliability, we can also add stuckles payments.
With Redundant Multi Route Payment Reservations, I believe the reliability of payments would be around the 99% percent range.
Latency, on average, should converge around a value much lower than the average value we have now.
[7] https://lists.linuxfoundation.org/pipermail/lightning-dev/2019-June/002029.html
[8] Unless it is a small amount, for instance, below 0.5 mBTC.
[9] Or some other multiplier
LN Wallet UX improvements
=========================
Not every payment is the same. For instance, if I'm paying a groceries bill in a supermarket, I value the speed of payments more than fees. On the other hand, if I'm paying my electricity bill at home, I value fees more than the speed of transactions. Also, if I'm paying a VPN subscription, I care more about privacy and cost over transaction speed.
With route reservation, we can present the exact user fees he is going to pay, so wallet developers can add the following element to UX:
Radio box: Fast Payment | Cheap Payment | MaxPrivacy
- If a user selects `Fast Payment` wallet will wait for the first N fastest routes and initiate payment automatically(unless fees exceed in percents some config value).
- If a user selects the `Cheap Payments` node will wait for all 2N routes to return, pick N cheapest routes, and then present the user with fees and a send button. If fees are too high, the user can press the `Try again` button.
- For `MaxPrivacy` wallet will behave as in `Cheap Payment` mode, except the routing algorithm will prefer longer routes over smaller nodes, with preferably at least one Tor node.
*N routes can be N trampoline routes if a wallet doesn't have a whole network topology.
Gossip messages spam
====================
Currently, 97 percent or more LN gossip messages go to `channel_update` messages. The reason is that most nodes on the network are running some form of automatic fee adjustment script. If the number of nodes and channels continues to grow, soon, this can become unsustainable.
Reservation is not used just to reserve the route but also to inform a sender of fees and cltvs. Thus there is no need for nodes to publish their fees to the whole network. And thus, information like base_fee, ppm fee, and cltv can be removed from the `channel_update` message.
With route reservation, there is no need for channel rebalancing or fee update scripts. Node operators can still run fee update scripts without restrictions, but those updates would not propagate to the network.
Routing algorithm and network decentralization
=============================================
In terms of network topology, a current lightning network can be seen as a decentralized network. But in terms of a payment network, it is more a hub base network, where the majority of payments go through ~30 largest nodes. Medium and smaller nodes rarely forward any payment, and they are mostly used by big nodes for channel rebalancing. This is a big issue in terms of fairness(the rich are getting richer faster), privacy, reliability of the network, cost of a transaction, etc.
I would argue that this problem is not because the rich are rich but because of the routing algorithm. Currently, used routing algorithms usually calculate the probability of routing a payment over some channel as a channel capacity function. If the channel has a large capacity probability is higher, small channels will have a lower probability of payment routing. Because all wallets are effectively running in `Fast Payment` mode, the routing algorithm will almost always choose bigger channel routes than smaller ones and thus create the hub-based model we have today.
If we remove `fees` and `cltvs` from the gossip, what is left for the routing algorithm is `channel_capacity`, `htlc_minimum_msat` and `htlc_maximum_msat`.
`htlc_maximum_msat` - can be a local node config. If the reservation attempts to reserve a greater amount than the maximum allowed for a single payment, a node can try to split the reservation over multiple channels.
`htlc_maximum_msat` - can remain a global config to avoid unnecessary reservation failures.
What about channel capacity?
Channel capacity can be the biggest misleading factor for LN routing algorithms. For instance, I can create a node and then buy 100 channels with 1BTC each of income liquidity. Then I set all channel fees to 0. Every routing algorithm will try to route payments through my node, but my node can't route a single satoshi. I would suspect that today's most popular nodes on the LN network probably have way more inbound than outbound liquidity.
So I think that capacity should not be used at all as a heuristic in the routing algorithms.
I think a better approach would be if nodes would just publish their cumulative outbound liquidity over all channels. If there are routing node A and routing node B, and they are well connected, we know that we can send(in theory) from node A to node B, with route split, a maximum payment of `min(A.balance, B.balance)` amount.
This would also signal to the rest of the network where liquidity is needed and where there is too much liquidity. There would be no liquidity sinks, and network liquidity could be better deployed. Automatic channel opening becomes trivial.
But would the nodes lie?
If the node lies, the reservation will fail on his node, and if there is a lot of reservation failure on misleading nodes, neighbor nodes might close the channel with him. Also, while processing huge payment reservations, which will eventually fail, a node could have routed a smaller payment and earned fees. So nodes will be incentives to report the real outbound liquidity or lower if privacy is the issue.
Now routing algorithm has become very simple. We make routing decisions just on hop count from our node, on node reported balance, and a bit of randomness. Randomness is the most important part. If some route fails, we can't know which node to blame. It can be any node in the route. The routing algorithm should not track any blame information about individual nodes and would not try to blacklist any particular node. If the node is well connected and the routing algorithm is random enough, we should be able eventually to find enough routes to the sender. If there is a faulty, griefing, or just slow node in the network, we let nodes handle deputies themselves. Each node will track the local reputation of each of its neighbors. If there are a lot of failed payments from one neighbor, the node operator might contact that neighbor for an explanation or just close the channel to that neighbor node.
For privacy currencies, not publishing channel capacity is a necessity. Privacy currency users (like Monero) don't want to relieve any of their UTXO amounts. Privacy currency LN can avoid publishing their channel capacity and outbound node liquidity, and only make routing decisions on hop counts and randomness. There would probably be more reservation failures, especially for larger amounts, but it should be worth privacy preserved.
Fast spam prevention
====================
Fast spam is a situation on the network when malicious nodes start creating a lot of payments to the random nodes, which will never be resolved because the receiver does not know the payment preimage. The receiver can only fail the payment.
This is not possible with a reservation anymore because receivers will reject a reservation, and there will be no payment. Now, this is a lot better because the reservation does not commit to a new channel state, and no DB operations are involved.
But how to prevent reservation spam?
If the node sees a lot of reservation errors per minute coming from one channel, the node can throttle reservations coming from that channel. Eventually, if spam continues node operator can inform the neighbor node operator to investigate the reason. The neighbor node will do the same. And if the problem persists, the node operator can just close the channel.
But what if an attacker controls both nodes(receiver and sender) or if the attacker creates a circular route?
The malicious receiver node will accept the reservation, and then when HTLC comes, it just fails the payment. This would be basically fast spam again, with a bit more work to be done by the attacker.
As proposed before[10], we can demand a prepayment. If a node sees a large amount of failed payments per minute on some of its channels, a node can start demanding some prepayment to route HTLC. The problem is how much to charge. If we charge too little, spam will continue. If we charge too much, this will affect regular micro-payments.
We can extend reservation_success tuple with a prepayment fee. And we can adjust the fee on the fly. There is no need to propagate it to the whole network. A node can initially charge 0 prepayment fees. This is in their best interest because the routing algorithm will prefer routes without prepayment. The reason is that there is still a chance of payment failure. In a payment failure case, the sender loses the pre-payed amount unconditionally. Now if a node observes a large number of payment failures per minute, he can start aggressively increasing his prepayment fees, thus making the attack very costly.
There was also a discussion on how to send a prepayment. Wouldn't the first node in the route just steal all prepayment and then fail the payment?
There are two possible scenarios here:
- prepayment is less than or equal to the fees the node is going to earn routing the payment. In this case, it is in the node's best interest to route the payment.
- prepayment amount is greater than node payment fees. I can see two possible solutions:
- let a first node steal the prepayment. This should be fine because if prepayment gets so big, most likely, the attacker is the one being robbed. Honest users will prefer routes without a prepayment, especially large prepayments.
- we can also try to send multiple keysend prepayments, but there are some privacy issues here because the length of the route is revealed to the first node, and the last route node finds out who the receiver is. A slightly less bad option is to send prepayments for the parts of the route. For instance, one keysend is for the first half of the route. The second is for the second half of the route.
[10] https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-February/002547.html
Channel liquidity probing
=========================
With a route reservation split, inspecting channel liquidity from other nodes becomes significantly more demanding. The reason is the fact that reservations should rarely fail. Now observer needs to deduct the channel liquidity from the reservation response (fee,cltv_delta). If there is a reservation split, fees and cltv_delta will most likely be higher than if there is no reservation split. But every node can change fee and cltv_delta on the fly, and by just randomizing those values on every return, potential channel observer jobs get much harder.
Also, if the attacker starts sending a lot of reservation requests, those requests might be seen as a DOS attempt, and the node might start throttling the reservation requests.
No need for splice-in(and partially splice-out)
===============================================
The idea behind the splicing is to increase the capacity of the channel, so that channel can route bigger payments. Also, the routing algorithm prefers a bigger channel so the node would route more payments.
With route split reservations, this is not necessary anymore. For example, if nodes A and B have N channels between them, node A would have the option to reserve a route through all N channels during reservation. Thus N smaller channels can be seen as one big channel, not by routing algorithm but by node A. Routing algorithm will just care if there is a connection between A and B.
If nodes A and B have N channels between them, closing one channel basically becomes a splice-out operation.
Looking forward to your feedback.
Best Regards,
g0b1el