Re: [Lightning-dev] [PROPOSAL]: FAST - Forked Away Simultaneous Transactions

[Ugam Kamat]

Thanks Christian for the references! As ZmnSCPxj pointed out, there was a 
loophole in my proposal that could potentially lead to DoS and failure attacks 
in the channels. These references should help me in working my proposal to 
circumvent such attacks. Have a great weekend.

 

Ugam

 

From: Christian Decker  
Sent: Friday, June 28, 2019 11:09 PM
To: Ugam Kamat 
Cc: lightning-dev 
Subject: Re: [Lightning-dev] [PROPOSAL]: FAST - Forked Away Simultaneous 
Transactions

 

Hi Ugam,

 

I just wanted to quickly note that the current proposal [1] (implemented here 
[2]) is to give up on the fixed 65 byte frames altogether and allow variable 
payloads (reclaiming what previously was padding in the hop payloads). Given 
the low diameter of the network, this gives us a lot of freedom to put 
additional payloads in the onion :-)

 

Cheers,

Christian

 

[1] https://github.com/lightningnetwork/lightning-rfc/pull/619

[2] https://github.com/ElementsProject/lightning/pull/2689

 

On Tue, Jun 25, 2019 at 1:07 PM Ugam Kamat mailto:ugamkam...@gmail.com> > wrote:

Hey guys, 

 

I’m kind of new to this mailing list, so let me know if this has been proposed 
previously. While reading Olaoluwa Osuntokun’s Spontaneous Payment proposal, I 
came up with the idea of simultaneous payments to multiple parties using the 
same partial route. In other words, say Alice, Bob, Charlie, Dave and Eric have 
channel opened with one another, and say Dave also has channel with Frank who 
has channel with Grace. Now, Alice is at a restaurant and wants to pay the bill 
amount to Eric (the restaurant owner) and a tip to Grace (who was her waiter). 
In the current scenario, Alice would have to send two payments A->B->C->D->E 
and A->B->C->D->F->G. However, if we repurpose the onion blob 
<https://github.com/ElementsProject/lightning/pull/2363>  in the same way as is 
needed for Spontaneous Payments, we can create a scenario where there is no 
path duplication. Dave would split the payments, one to Eric and other going to 
Grace through Frank. The preimage PM used in commitments A->B, B->C and C->D 
will be a function of pre-images P1 of D->E and P2 of D->F and F->G such that 
PM = f(P1, P2).

 

Proposal can be implemented by repurposing the onion in similar fashion as 
Spontaneous Payments with slight modification

This proposal works in similar fashion to Spontaneous Payment proposal, by 
packing in additional data in the unused hops. For B and C the onion blob will 
be identical to other lightning payments. When D parses the onion, the 4 MSB of 
the realm will tell D how much data can be extracted. This data will encode the 
hashes of the pre-images that would be used for commitment transaction towards 
Eric and other towards Frank.  For simplicity and privacy, I propose using 2 
onion blobs for the data. So the payload can be 64 + 33 bytes = 97 bytes. The 
first byte would indicate how many hashes are packed, so we have 96 bytes for 
the payload, meaning we can pack a maximum of 3 hashes for 3 route payments 
from D. Now D will split the onion (18 hops as it has used the first two for 
bifurcation data) into number of routes. In the above case it will be 9 hops 
each. Now these two onions are similar to other lightning payments. The first 
hop tells D the short-channel id, amount to forward, CLTV and the padding. 
Since, the preimage is 32 bytes, we can pack that in one single hop that is 
received by the final party. This leaves the remaining 7 hops can be used for 
routing. Below figure depicts the onion split in terms of how A will create it. 
D will add the filler to make each onion have 20 hops. Onion data is encoded in 
the same order in which the payment hashes are packed in the bifurcation data 
for D.



 

Calculating the preimages

Eric and Grace will parse the onion and use the pre-images for settlement. Let 
P1 represent the pre-images of D->E and P2 of D->F and F->G. When the 
pre-images arrive at node D, it will combine them such that PM = f(P1, P2). The 
easiest way for both A and D to calculate that will be PM = SHA256(P1 || P2 || 
ss_d). Where || represents concatenation and ss_d is the shared secret created 
using the ephemeral public key of sender (the one generated by Alice) and 
private key of Dave. The need for using shared secret is to prevent the 
vulnerability where one channel operator who has nodes across both branches can 
use them to calculate the PM. Using shared secret also ensures that it is in 
fact D that has parsed them together. 

 

Advantages of this proposal:

*   Commitment transactions between A & B, B & C, and C & D now carry only 
one HTLC instead of two

*   This means lower fees in case of on-chain settlement
*   Lower routing fees for Alice as Bob and Charlie would not get to charge 
for two routings
*   Since 483 is the max limit of the htlcs nodes can accepts, preventing 
duplication will al

Re: [Lightning-dev] [PROPOSAL]: FAST - Forked Away Simultaneous Transactions

[Christian Decker]

Hi Ugam,

I just wanted to quickly note that the current proposal [1] (implemented
here [2]) is to give up on the fixed 65 byte frames altogether and allow
variable payloads (reclaiming what previously was padding in the hop
payloads). Given the low diameter of the network, this gives us a lot of
freedom to put additional payloads in the onion :-)

Cheers,
Christian

[1] https://github.com/lightningnetwork/lightning-rfc/pull/619
[2] https://github.com/ElementsProject/lightning/pull/2689

On Tue, Jun 25, 2019 at 1:07 PM Ugam Kamat  wrote:

> Hey guys,
>
>
>
> I’m kind of new to this mailing list, so let me know if this has been
> proposed previously. While reading Olaoluwa Osuntokun’s Spontaneous
> Payment proposal, I came up with the idea of simultaneous payments to
> multiple parties using the same partial route. In other words, say Alice,
> Bob, Charlie, Dave and Eric have channel opened with one another, and say
> Dave also has channel with Frank who has channel with Grace. Now, Alice is
> at a restaurant and wants to pay the bill amount to Eric (the restaurant
> owner) and a tip to Grace (who was her waiter). In the current scenario,
> Alice would have to send two payments A->B->C->D->E and A->B->C->D->F->G.
> However, if we repurpose the onion blob
>  in the same way
> as is needed for Spontaneous Payments, we can create a scenario where there
> is no path duplication. Dave would split the payments, one to Eric and
> other going to Grace through Frank. The preimage PM used in commitments
> A->B, B->C and C->D will be a function of pre-images P1 of D->E and P2 of
> D->F and F->G such that PM = f(P1, P2).
>
>
>
> *Proposal can be implemented by repurposing the onion in similar fashion
> as Spontaneous Payments with slight modification*
>
> This proposal works in similar fashion to Spontaneous Payment proposal, by
> packing in additional data in the unused hops. For B and C the onion blob
> will be identical to other lightning payments. When D parses the onion, the
> 4 MSB of the realm will tell D how much data can be extracted. This data
> will encode the hashes of the pre-images that would be used for commitment
> transaction towards Eric and other towards Frank.  For simplicity and
> privacy, I propose using 2 onion blobs for the data. So the payload can be
> 64 + 33 bytes = 97 bytes. The first byte would indicate how many hashes are
> packed, so we have 96 bytes for the payload, meaning we can pack a maximum
> of 3 hashes for 3 route payments from D. Now D will split the onion (18
> hops as it has used the first two for bifurcation data) into number of
> routes. In the above case it will be 9 hops each. Now these two onions are
> similar to other lightning payments. The first hop tells D the
> short-channel id, amount to forward, CLTV and the padding. Since, the
> preimage is 32 bytes, we can pack that in one single hop that is received
> by the final party. This leaves the remaining 7 hops can be used for
> routing. Below figure depicts the onion split in terms of how A will create
> it. D will add the filler to make each onion have 20 hops. Onion data is
> encoded in the same order in which the payment hashes are packed in the
> bifurcation data for D.
>
>
>
> *Calculating the preimages*
>
> Eric and Grace will parse the onion and use the pre-images for settlement.
> Let P1 represent the pre-images of D->E and P2 of D->F and F->G. When the
> pre-images arrive at node D, it will combine them such that PM = f(P1, P2).
> The easiest way for both A and D to calculate that will be PM = SHA256(P1
> || P2 || ss_d). Where || represents concatenation and ss_d is the shared
> secret created using the ephemeral public key of sender (the one generated
> by Alice) and private key of Dave. The need for using shared secret is to
> prevent the vulnerability where one channel operator who has nodes across
> both branches can use them to calculate the PM. Using shared secret also
> ensures that it is in fact D that has parsed them together.
>
>
>
> *Advantages of this proposal:*
>
>- Commitment transactions between A & B, B & C, and C & D now carry
>only one HTLC instead of two
>   - This means lower fees in case of on-chain settlement
>   - Lower routing fees for Alice as Bob and Charlie would not get to
>   charge for two routings
>   - Since 483 is the max limit of the htlcs nodes can accepts,
>   preventing duplication will allow more number of htlcs in flight.
>- If each payment of Eric and Grace is below the htlc min B or C
>accepts, but together if it is higher, this route is now usable
>
>
>
> *Some thoughts on if this proposal can be misused?*
>
>- The probability of transaction failures increases as now the
>transaction is dependent on 2/3 branches
>
>
>
> *Deployment*
>
> Not all nodes need to support this feature. For example, B, C, E, F,  and
> G does not even know that the payment arrived through 

Re: [Lightning-dev] [PROPOSAL]: FAST - Forked Away Simultaneous Transactions

[Ugam Kamat]

Hey ZmnSCPxj, 

Really appreciate your efforts in going through the proposal in depth. The two 
choices you mentioned for the proposal are a really fair analysis of how an 
attack can be launched on such forked away payments. In the current scheme, it 
seems it will create problems rather than solve it. I'll try to do some more 
work and see if I can come up with a more solid way in order to achieve this. 
Thanks again.

Ugam

-Original Message-
From: ZmnSCPxj  
Sent: Wednesday, June 26, 2019 4:35 AM
To: ZmnSCPxj 
Cc: René Pickhardt ; Ugam Kamat 
; lightning-dev 
Subject: Re: [Lightning-dev] [PROPOSAL]: FAST - Forked Away Simultaneous 
Transactions

Good morning Ugam,


> In any case, this is effectively simply creation of fork points and join 
> points along a multipart path.
> That the payment does not later join is merely a detail, especially once we 
> get to "high" AMP (which requires payment points / scalars).
> We decided at previous dev summit not to implement this due to 
> complexity-of-implementation for payers, as well as how to resolve when one 
> branch fails while the other branch claims the payment.


On reflection, that there is no later join means that this scheme allows attack.

We have two choices:

1. Both forked branches have to succeed in order for the fork node to claim its 
incoming payment.
2. Either forked branch can succeed and the fork node can claim its incoming 
payment.

If we go with 1:

* Fork nodes can be attacked by routing a self-payment through a fork node, 
with the other branch going nowhere (give it an unuseable preimage).
  Claim the branch that goes to yourself, then wait for your outgoing payment 
to lapse.
  The fork node is forced to pay one branch but is unable to claim its incoming 
payment.
  Attacker earns free money.

If we go with 2:

* Fork nodes can attack opportunistically, by only paying out to the 
smaller-valued branch.
  Once the smaller-valued branch succeeds, the fork node can claim its incoming 
payment and forget about the other branch of the payment.
* This is the choice made for multipart payments.
  However, note that in multipart, there is always a later join (most likely at 
the ultimate, *single* destination).
  The join will not succeed unless both incoming payments arrive, so fork nodes 
cannot perform this attack opportunistically.

A plausible fix for your scheme would be to take choice 2 (either branch 
succeeding lets fork node claim incoming payment).
Then Eric and Grace need to cooperate and only take incoming payment if both of 
them receive incoming payments.
This implies Eric and Grace must trust each other to coordinate.

Regards,
ZmnSCPxj

___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] [PROPOSAL]: FAST - Forked Away Simultaneous Transactions

[ZmnSCPxj via Lightning-dev]

Good morning Ugam,


> In any case, this is effectively simply creation of fork points and join 
> points along a multipart path.
> That the payment does not later join is merely a detail, especially once we 
> get to "high" AMP (which requires payment points / scalars).
> We decided at previous dev summit not to implement this due to 
> complexity-of-implementation for payers, as well as how to resolve when one 
> branch fails while the other branch claims the payment.


On reflection, that there is no later join means that this scheme allows attack.

We have two choices:

1. Both forked branches have to succeed in order for the fork node to claim its 
incoming payment.
2. Either forked branch can succeed and the fork node can claim its incoming 
payment.

If we go with 1:

* Fork nodes can be attacked by routing a self-payment through a fork node, 
with the other branch going nowhere (give it an unuseable preimage).
  Claim the branch that goes to yourself, then wait for your outgoing payment 
to lapse.
  The fork node is forced to pay one branch but is unable to claim its incoming 
payment.
  Attacker earns free money.

If we go with 2:

* Fork nodes can attack opportunistically, by only paying out to the 
smaller-valued branch.
  Once the smaller-valued branch succeeds, the fork node can claim its incoming 
payment and forget about the other branch of the payment.
* This is the choice made for multipart payments.
  However, note that in multipart, there is always a later join (most likely at 
the ultimate, *single* destination).
  The join will not succeed unless both incoming payments arrive, so fork nodes 
cannot perform this attack opportunistically.

A plausible fix for your scheme would be to take choice 2 (either branch 
succeeding lets fork node claim incoming payment).
Then Eric and Grace need to cooperate and only take incoming payment if both of 
them receive incoming payments.
This implies Eric and Grace must trust each other to coordinate.

Regards,
ZmnSCPxj
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] [PROPOSAL]: FAST - Forked Away Simultaneous Transactions

[ZmnSCPxj via Lightning-dev]

Good morning Rene and Ugam,

Under Scriptless Script (payment point / scalar) this is possible to do while 
retaining a form of proof-of-payment.
However, note that the proof-of-payment scalar will be the sum of Eric and 
Grace proof-of-payment scalars.
I am unsure if that provides undeniable proof that you paid Grace, or that you 
paid Eric.

Given payment points / scalars `E`/`e` from Eric and `H`/`h` from Grace, we can 
show:

   A = E + H
   a = e + h ; purportedly
   A = a * G

I am uncertain if there is a form of key cancellation possible here, wherein 
Grace denies proof-of-payment by claiming that Eric does not in fact exist and 
was created by the payer to cancel the payment point of Grace.

Another solution would be to route through Eric and leave Eric with a 
higher-than-normal fee (the usual spontaneous payment I prefer), which retains 
an undeniable proof-of-payment of Grace.
Eric would not provide proof-of-payment, but in this scenario given it seems, 
it is a "tip" and the actual payment is to the restauranteur Grace.

In any case, this is effectively simply creation of fork points and join points 
along a multipart path.
That the payment does not later join is merely a detail, especially once we get 
to "high" AMP (which requires payment points / scalars).
We decided at previous dev summit not to implement this due to 
complexity-of-implementation for payers, as well as how to resolve when one 
branch fails while the other branch claims the payment.

Regards,
ZmnSCPxj
Sent with ProtonMail Secure Email.

‐‐‐ Original Message ‐‐‐
On Tuesday, June 25, 2019 7:32 PM, René Pickhardt via Lightning-dev 
 wrote:

> Hey Ugam, 
>
> I like the very clearly communicated idea and the fact that we can do crazy 
> stuff with the filler of the onions. I have two concerns / questions: 
>
> 1.) In pathfinding we actually try to make payments smaller (like moving to 
> AMP) instead of combining payments. I think it was shown several times that 
> the probability of finding a path (successful route) decreases with larger 
> amounts. So saving fees might actually not be the metric that we are trying 
> to optimize.
> 2.) Am I correct that this proposal would only work with the spontaneous 
> payment scenario as the payment hashes of Eric and Grace could not just be 
> added up as easy as the preimages can to get the overall payment hash for 
> Alice? So in that sense on the invoice based system your proposal is not 
> working and we don't have a proof of payment as Alice already knows the 
> preimages? Could one resolve this in the world of scriptless scripts or when 
> changing to secret / curve point based preimages based on the discrete log?
>
> best Rene 
>
> On Tue, Jun 25, 2019 at 7:07 AM Ugam Kamat  wrote:
>
> > Hey guys,
> >
> > I’m kind of new to this mailing list, so let me know if this has been 
> > proposed previously. While reading Olaoluwa Osuntokun’s Spontaneous Payment 
> > proposal, I came up with the idea of simultaneous payments to multiple 
> > parties using the same partial route. In other words, say Alice, Bob, 
> > Charlie, Dave and Eric have channel opened with one another, and say Dave 
> > also has channel with Frank who has channel with Grace. Now, Alice is at a 
> > restaurant and wants to pay the bill amount to Eric (the restaurant owner) 
> > and a tip to Grace (who was her waiter). In the current scenario, Alice 
> > would have to send two payments A->B->C->D->E and A->B->C->D->F->G. 
> > However, if we repurpose the onion blob in the same way as is needed for 
> > Spontaneous Payments, we can create a scenario where there is no path 
> > duplication. Dave would split the payments, one to Eric and other going to 
> > Grace through Frank. The preimage PM used in commitments A->B, B->C and 
> > C->D will be a function of pre-images P1 of D->E and P2 of D->F and F->G 
> > such that PM = f(P1, P2).
> >
> > Proposal can be implemented by repurposing the onion in similar fashion as 
> > Spontaneous Payments with slight modification
> >
> > This proposal works in similar fashion to Spontaneous Payment proposal, by 
> > packing in additional data in the unused hops. For B and C the onion blob 
> > will be identical to other lightning payments. When D parses the onion, the 
> > 4 MSB of the realm will tell D how much data can be extracted. This data 
> > will encode the hashes of the pre-images that would be used for commitment 
> > transaction towards Eric and other towards Frank.  For simplicity and 
> > privacy, I propose using 2 onion blobs for the data. So the payload can be 
> > 64 + 33 bytes = 97 bytes. The first byte would indicate how many hashes are 
> > packed, so we have 96 bytes for the payload, meaning we can pack a maximum 
> > of 3 hashes for 3 route payments from D. Now D will split the onion (18 
> > hops as it has used the first two for bifurcation data) into number of 
> > routes. In the above case it will be 9 hops each. Now these two onions are 
> > similar to 

Re: [Lightning-dev] [PROPOSAL]: FAST - Forked Away Simultaneous Transactions

[René Pickhardt via Lightning-dev]

Hey Ugam,

I like the very clearly communicated idea and the fact that we can do crazy
stuff with the filler of the onions. I have two concerns / questions:

1.) In pathfinding we actually try to make payments smaller (like moving to
AMP) instead of combining payments. I think it was shown several times that
the probability of finding a path (successful route) decreases with larger
amounts. So saving fees might actually not be the metric that we are trying
to optimize.
2.) Am I correct that this proposal would only work with the spontaneous
payment scenario as the payment hashes of Eric and Grace could not just be
added up as easy as the preimages can to get the overall payment hash for
Alice? So in that sense on the invoice based system your proposal is not
working and we don't have a proof of payment as Alice already knows the
preimages? Could one resolve this in the world of scriptless scripts or
when changing to secret / curve point based preimages based on the discrete
log?

best Rene

On Tue, Jun 25, 2019 at 7:07 AM Ugam Kamat  wrote:

> Hey guys,
>
>
>
> I’m kind of new to this mailing list, so let me know if this has been
> proposed previously. While reading Olaoluwa Osuntokun’s Spontaneous
> Payment proposal, I came up with the idea of simultaneous payments to
> multiple parties using the same partial route. In other words, say Alice,
> Bob, Charlie, Dave and Eric have channel opened with one another, and say
> Dave also has channel with Frank who has channel with Grace. Now, Alice is
> at a restaurant and wants to pay the bill amount to Eric (the restaurant
> owner) and a tip to Grace (who was her waiter). In the current scenario,
> Alice would have to send two payments A->B->C->D->E and A->B->C->D->F->G.
> However, if we repurpose the onion blob
>  in the same way
> as is needed for Spontaneous Payments, we can create a scenario where there
> is no path duplication. Dave would split the payments, one to Eric and
> other going to Grace through Frank. The preimage PM used in commitments
> A->B, B->C and C->D will be a function of pre-images P1 of D->E and P2 of
> D->F and F->G such that PM = f(P1, P2).
>
>
>
> *Proposal can be implemented by repurposing the onion in similar fashion
> as Spontaneous Payments with slight modification*
>
> This proposal works in similar fashion to Spontaneous Payment proposal, by
> packing in additional data in the unused hops. For B and C the onion blob
> will be identical to other lightning payments. When D parses the onion, the
> 4 MSB of the realm will tell D how much data can be extracted. This data
> will encode the hashes of the pre-images that would be used for commitment
> transaction towards Eric and other towards Frank.  For simplicity and
> privacy, I propose using 2 onion blobs for the data. So the payload can be
> 64 + 33 bytes = 97 bytes. The first byte would indicate how many hashes are
> packed, so we have 96 bytes for the payload, meaning we can pack a maximum
> of 3 hashes for 3 route payments from D. Now D will split the onion (18
> hops as it has used the first two for bifurcation data) into number of
> routes. In the above case it will be 9 hops each. Now these two onions are
> similar to other lightning payments. The first hop tells D the
> short-channel id, amount to forward, CLTV and the padding. Since, the
> preimage is 32 bytes, we can pack that in one single hop that is received
> by the final party. This leaves the remaining 7 hops can be used for
> routing. Below figure depicts the onion split in terms of how A will create
> it. D will add the filler to make each onion have 20 hops. Onion data is
> encoded in the same order in which the payment hashes are packed in the
> bifurcation data for D.
>
>
>
> *Calculating the preimages*
>
> Eric and Grace will parse the onion and use the pre-images for settlement.
> Let P1 represent the pre-images of D->E and P2 of D->F and F->G. When the
> pre-images arrive at node D, it will combine them such that PM = f(P1, P2).
> The easiest way for both A and D to calculate that will be PM = SHA256(P1
> || P2 || ss_d). Where || represents concatenation and ss_d is the shared
> secret created using the ephemeral public key of sender (the one generated
> by Alice) and private key of Dave. The need for using shared secret is to
> prevent the vulnerability where one channel operator who has nodes across
> both branches can use them to calculate the PM. Using shared secret also
> ensures that it is in fact D that has parsed them together.
>
>
>
> *Advantages of this proposal:*
>
>- Commitment transactions between A & B, B & C, and C & D now carry
>only one HTLC instead of two
>   - This means lower fees in case of on-chain settlement
>   - Lower routing fees for Alice as Bob and Charlie would not get to
>   charge for two routings
>   - Since 483 is the max limit of the htlcs nodes can accepts,
>   preventing duplication will