Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning

[Rusty Russell]

Conner Fromknecht  writes:
> IMHO, the current signed invoice + preimage is a very weak proof of payment.
> It's the hash equivalent to proving you own a public key by publishing the
> secret key. There is an assumption that the only way someone could get that
> preimage is by having made a payment, but this assumption is broken most
> directly by the proving mechanism. Similarly, any intermediary who acquires
> an invoice with the appropriate hash could also make this claim since they
> also have the preimage.

Agreed.

> Further, I think it's a mistake to conflate
>   1) me being able to present a valid preimage/invoice pair, with
>   2) me having received the correct preimage in response to an onion packet
> that I personally crafted for the receiving node in the invoice.
>
> The main issue is that the proof does not bind a specific sender,
> making statement 1 producible by multiple individuals. I think it would be
> potentially worthwhile to explore proofs of stronger statements, such as 2,
> that could utilize the ephemeral keys in the onion packets, or even the
> onion as a witness, which is more rigidly coupled to having actually
> completed a payment.

Yes; this places more emphasis on the invoice's precision, eg. "I will
ship X to Y".

In practice, as we move to payment decorrelation the proof-of-payment
does half of what you suggest: only the initial payer has the necessary
proof, but it's still open-kimono if they reveal it.

Using some kind of point-supplied-in-onion to tweak result might help
here (handwave?!) since you can prove you know the secret for the point
easily without revealing it, and then AMP is simply an aggregation of
tweaks.

> TL;DR: I'm not convinced the signed invoice + hash is really a good
> yardstick
> by which to measure provability, and I think doing some research into proofs
> of payment on stronger statements would be incredibly valuable. Therefore,
> I'm not sure if AMPs really lose this, so much as force us to reconsider
> what it actually requires to soundly prove a payment to an external
> verifier.

Proof-of-payment is a unique lightning property, which I think is
terribly underrated (because we're used to not having it).  Our actions
so far have been to boltser this (hence BOLT11), and I'd hate to see us
discard it for convenience: I fear we'd never get it back!

Fortunately I think we *can* have our cake and eat it too...

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

Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning

[Conner Fromknecht]

Hi everyone,

I've seen some discussions over losing proofs of payment in the AMP setting,
and wanted to address some lingering concerns I have regarding the
soundness of using the current invoicing system to prove payments.

In general, I think we are ascribing too much weight to simply having a
preimage and BOLT 11 invoice. The structure of non-interactive payments
definitely poses some interesting challenges in adapting the existing
invoicing
scheme. However, I believe there exist stronger and better means of doing
proofs of payment, and would prefer not to tie our hands by assuming
this is the best way to approach the problem.

IMHO, the current signed invoice + preimage is a very weak proof of payment.
It's the hash equivalent to proving you own a public key by publishing the
secret key. There is an assumption that the only way someone could get that
preimage is by having made a payment, but this assumption is broken most
directly by the proving mechanism. Similarly, any intermediary who acquires
an invoice with the appropriate hash could also make this claim since they
also have the preimage.

Further, I think it's a mistake to conflate
  1) me being able to present a valid preimage/invoice pair, with
  2) me having received the correct preimage in response to an onion packet
that I personally crafted for the receiving node in the invoice.

The main issue is that the proof does not bind a specific sender,
making statement 1 producible by multiple individuals. I think it would be
potentially worthwhile to explore proofs of stronger statements, such as 2,
that could utilize the ephemeral keys in the onion packets, or even the
onion as a witness, which is more rigidly coupled to having actually
completed a payment.

Without any modification to the spec, we can always use something like
ZKBoo to prove (w/o trusted setup) knowledge of a preimage without
totally revealing it to the verifier. This isn't perfect, but at least
gives the
sender the option to prove the statement without necessarily giving up
the preimage.

TL;DR: I'm not convinced the signed invoice + hash is really a good
yardstick
by which to measure provability, and I think doing some research into proofs
of payment on stronger statements would be incredibly valuable. Therefore,
I'm not sure if AMPs really lose this, so much as force us to reconsider
what it actually requires to soundly prove a payment to an external
verifier.

Best,
Conner

On Mon, Feb 12, 2018 at 6:56 PM ZmnSCPxj via Lightning-dev <
lightning-dev@lists.linuxfoundation.org> wrote:

> Good morning Christian and Corne,
>
> Another idea to consider, is techniques like ZKCP and ZKCSP, which provide
> atomic access to information in exchange for monetary compensation.
> Ensuring atomicity of the exchange can be done by providing the information
> encrypted, a hash of the encryption key, and proofs that the encrypted data
> is the one desired and that the data was encrypted with the given key; the
> proof-of-payment is the encryption key, and possession of the encryption
> key is sufficient to gain access to the information, with no need to bring
> in legal structures.
>
> (admittedly, ZKCP and ZKCSP are dependent on new cryptography...)
>
> (also, AMP currently cannot provide a proof-of-payment, unlike current
> payment routing that has proof-of-payment, but that is an eventual design
> goal that would enable use of ZKC(S)P on-Lightning, assuming we eventually
> find out that zk-SNARKs and so on are something we can trust)
>
> Regards,
> ZmnSCPxj
>
> ​
> Sent with ProtonMail Secure Email.
> ​
>
>  Original Message 
>  On February 13, 2018 2:05 AM, Christian Decker <
> decker.christ...@gmail.com> wrote:
>
> >Honestly I don't get why we are complicating this so much. We have a
> > system that allows atomic multipath payments using a single secret, and
> > future decorrelation mechanisms allow us to vary the secret in such a
> > way that multiple paths cannot be collated, why introduce a whole set of
> > problems by giving away the atomicity? The same goes for the overpaying
> > and trusting the recipient to only claim the owed amount, there is no
> > need for this. Just pay the exact amount, by deriving secrets from the
> > main secret and make the derivation reproducible by intermediate hops.
> >
> > Having proof-of-payment be presentable in a court is a nice feature, but
> > it doesn't mean we need to abandon all guarantees we have worked so hard
> > to establish in LN.
> >
> > Corné Plooy via Lightning-dev lightning-dev@lists.linuxfoundation.org
> >writes:
> >
> >>I was thinking that, for that use case, a different signed invoice could
> >> be formulated, stating
> >> - several payment hashes with their corresponding amounts
> >>
> >> - the obligation of signer to deliver Z if all corresponding payment
> >> keys are shown
> >>
> >> - some terms to handle the case where only a part of the payments was
> >> successful, e.g. an obligation to refund
> >>The 

Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning

[ZmnSCPxj via Lightning-dev]

Good morning Christian and Corne,

Another idea to consider, is techniques like ZKCP and ZKCSP, which provide 
atomic access to information in exchange for monetary compensation.  Ensuring 
atomicity of the exchange can be done by providing the information encrypted, a 
hash of the encryption key, and proofs that the encrypted data is the one 
desired and that the data was encrypted with the given key; the 
proof-of-payment is the encryption key, and possession of the encryption key is 
sufficient to gain access to the information, with no need to bring in legal 
structures.

(admittedly, ZKCP and ZKCSP are dependent on new cryptography...)

(also, AMP currently cannot provide a proof-of-payment, unlike current payment 
routing that has proof-of-payment, but that is an eventual design goal that 
would enable use of ZKC(S)P on-Lightning, assuming we eventually find out that 
zk-SNARKs and so on are something we can trust)

Regards,
ZmnSCPxj

​
Sent with ProtonMail Secure Email.
​

 Original Message 
 On February 13, 2018 2:05 AM, Christian Decker  
wrote:

>Honestly I don't get why we are complicating this so much. We have a
> system that allows atomic multipath payments using a single secret, and
> future decorrelation mechanisms allow us to vary the secret in such a
> way that multiple paths cannot be collated, why introduce a whole set of
> problems by giving away the atomicity? The same goes for the overpaying
> and trusting the recipient to only claim the owed amount, there is no
> need for this. Just pay the exact amount, by deriving secrets from the
> main secret and make the derivation reproducible by intermediate hops.
>
> Having proof-of-payment be presentable in a court is a nice feature, but
> it doesn't mean we need to abandon all guarantees we have worked so hard
> to establish in LN.
>
> Corné Plooy via Lightning-dev lightning-dev@lists.linuxfoundation.org
>writes:
>
>>I was thinking that, for that use case, a different signed invoice could
>> be formulated, stating
>> - several payment hashes with their corresponding amounts
>>
>> - the obligation of signer to deliver Z if all corresponding payment
>> keys are shown
>>
>> - some terms to handle the case where only a part of the payments was
>> successful, e.g. an obligation to refund
>>The third item is a bit problematic: in order to distinguish this case
>> from a complete success, the payee would have to prove absence of
>> successful transactions, which is hard. Absence of successful
>> transactions can only be declared by the payer, so in order to reliably
>> settle without going to court first, the payer should sign a
>> declaration stating that certain transactions were canceled and that the
>> other ones should be refunded. This can be another invoice.
>>So, the original invoice states:
>> - several payment hashes with their corresponding amounts
>>
>> - if all corresponding payment keys are shown: the obligation of 
>> to deliver Z, UNLESS stated otherwise by an invoice signed by 
>>-- signed by 
>>But if a payment partially fails, it can be refunded cooperatively with
>> an invoice created by payer:
>> - declares which of the original payments were successful (with payment
>> keys) and which were not
>>
>> - replaces the obligation of  to deliver Z with an obligation to
>> refund the successful transactions
>>
>> - several payment hashes with their corresponding amounts
>>
>> - if all corresponding payment keys are shown: cancel the obligation of
>>  to refund
>>-- signed by 
>>Maybe this can be repeated iteratively if necessary; hopefully the
>> not-yet-settled amount will converge to zero.
>>Important advantage: this only requires changes to the invoice format,
>> not to the network protocol.
>>The point is: in this use case, the court is apparently the final point
>> of settlement for invoices, just like the blockchain is for the other
>> channels in the route. IANAL, but I think the "scripting language"
>> accepted by courts is quite flexible, and you can use that to enforce
>> atomicity. With the construction described above, you can either refund
>> cooperatively (and collect evidence that refund has happened), or, if
>> that fails, go to court to enforce settlement there.
>>CJP
>>Op 12-02-18 om 10:23 schreef Christian Decker:
>>>CJP c...@ultimatestunts.nl writes:
Can you give a use case for this?
Usually, especially in the common case that a payment is done in
 exchange for some non-cryptographic asset (e.g. physical goods), there
 already is some kind of trust between payer and payee. So, if a payment
 is split non-atomically into smaller transactions, and only a part
 succeeds, presumably they can cooperatively figure out some way to
 settle the situation.
 The scenario that is commonly used in these cases is a merchant that
 provides a signed invoice "if you pay me X with payment_hash Y I will
 deliver Z". Now the user performs the 

Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning

[Christian Decker]

Jim Posen  writes:
> If using two hashes to deliver the payment while still getting a proof, I'm
> not sure what that provides above just sending regular lightning payments
> over multiple routes with one hash. Firstly, if there is a second hash, it
> would presumably be the same for all routes, making them linkable again,
> which AMP tries to solve. And secondly, the receiver has no incentive to
> claim any of the HTLCs before all of them are locked in, because in that
> case they are releasing the transaction receipt before fully being paid.

Arguably the second concern is not really an issue, if you allow partial
claims you'll end up in a whole lot of trouble. It should always be the
case that the payment as whole is atomic, i.e., either the entirety of
the payment goes through or none of it, independently of whether it was
a singlepath or a multipath payment. This is actually one of the really
nice features that was enforced using the simple "just reuse the
hash"-mechanism, you always had to wait for the complete payment or
you'd risk losing part of it.
___
Lightning-dev mailing list
Lightning-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev

Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning

[ZmnSCPxj via Lightning-dev]

Good morning Cezary,

> That would be great improvement, if AMP could work this way:
>
> 1. I would like to send 0.1 BTC, so I split this to 5 payment 0.02 BTC each + 
> one extra 0.02 BTC payment.
> 2. When recipient received 6 htlcs, he is able to spend only 5 of them.
> If recipient receives, only 5 of them, it is still fine, and payment is 
> success.
>
> In such scenario, single route/payment would fail, and payment as whole would 
> still be success. Do you think that would be possible? It could greatly 
> increase reliability of LN payments.

I will leave it to better mathematicians to answer your direct question, but, 
my intuition suggests it is not possible as stated.

However, let me propose an alternative AMP method instead.

--

Roughly, we want to proceed this way.

1.  When paying:
1.1.  Try to pay.
1.2.  If it fails, split it into two smaller payments and recurse into 1.

Now we should ensure that the receiver can only receive if it has received all 
payments, and once it has received all payments, it can claim all payments.

So let me first introduce the below dual:

* A pseudorandom number generator can be represented by its algorithm and the 
seed.  Alternatively, it can be represented by a stream of numbers.

Now, a  stream of numbers has no end, but it does have a start (i.e. the first 
random number generated by the PRNG from the seed).  It is possible to "split" 
a stream into two streams, by taking the 0th, 2nd, 4th... numbers in one 
stream, and taking the 1st, 3rd, 5th... numbers in the other stream.

Each such "split" stream can itself be further split into two streams.  Split 
streams can be re-"merged" by interleaving their members to yield the original 
pre-split stream.

Now, we also want to be able to split a random seed into two seeds.  This 
splitting need not correspond to the stream-split (i.e. the split seeds will 
NOT generate the split streams); we only need to split seeds to prevent the 
receiver from claiming partial amounts.  This can be done by using another 
random source to generate a new "seed", and XOR it with the real seed.  The 
split "halves" are then the random number, and seed XOR the random number; the 
result is two apparently random numbers which, when XORed together, generate 
the original seed.

Let us now sketch our algorithm:

1.  def pay(seed, stream, dest, amount):
1.1.  try { r = route(dest, amount, randomstuff); offer_htlc(H(stream[0]), r, 
seed, stream);
1.2.  } catch(PaymentFailure) { sd1, sd2 = split_seed(seed); sr1, sr2 = 
split_stream(stream); pay(sd1, sr1, dest, amount / 2); pay(sd2, sr2, dest, 
amount / 2); }

Now notice that the hash we use is H(stream[0]).  That is, the first item in 
the stream of random numbers.  Thus our streams do not actually need to give 
anything more than the first number in a stream.  We can represent a "split" 
stream simply by the index into the original stream.  For example, if we have:

s = original stream
sl, sr = split_stream(s)
sll, slr = split_stream(sl)

Then s[0] and sl[0] and sll[0] are simply index 0 into the original stream, 
sr[0] is index 1, and slr[0] is index 2.  We can thus represent streams and 
their splits by the tuple (seed, index, depth), where depth indicates how many 
splits the stream has been through.  So, for the below:

s = (seed, 0, 0)
sl, sr = split_stream(s) = (seed, 0, 1), (seed, 1, 1)
sll, slr = split_stream(sl) = (seed, 0, 2), (seed, 2, 2)
split_stream( (seed, index, depth) ) = (seed, index, depth + 1), (seed, 
index + 2**depth, depth + 1)

Then, for any stream s whose RNG algorithm is PRNG:

   s[0] = (seed, index, _)[0] = PRNG(seed)[index]

Let us now consider how our payment might proceed.

1.  First, we generate a random seed, and call pay(seed, (seed, 0, 0), dest, 
amount)
2.  Let us suppose that payment fails for the entire amount.  Split the amount 
into two:
2.1.  In one branch we have pay(X, (seed, 0, 1), dest, amount / 2).  X is a new 
random number.
2.2.  In other branch we have pay(seed ^ X, (seed, 1, 1), dest, amount / 2).  X 
is the same number as branch 2.1.
2.2.1.  Suppose this payment fails.  Split it again intow two payments:
2.2.1.1  In one sub-branch we have pay(Y, (seed, 1, 2), dest, amount / 4).
2.2.1.2.  In other sub-branch we have pay(seed ^ X ^ Y, (seed, 3, 2), dest, 
amount / 4).

The receiver receives the branches 2.1, 2.2.1.1, and 2.2.1.2., which provide 
the seeds:

2.1. => X
2.2.1.1 => Y
2.2.1.2. => seed ^X ^ Y

Xoring all of the above provides X ^ Y ^ seed ^ X ^ Y = seed.

The receiver can claim branch 2.1. by using PRNG(seed)[0], can claim branch 
2.2.1.1 using PRNG(seed)[1], and branch 2.2.1.2 using PRNG(seed)[3].

Thus the sender needs only to send the split seed (say 32 bytes) and the index 
(say 1 byte for up to 8-level splitting into up to 256 payments).  The receiver 
gathers each split seed, XOR them all together to get the original PRNG seed, 
and runs the PRNG the appropriate number of times to get the 

Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning

[Cezary Dziemian]

That would be great improvement, if AMP could work this way:

1. I would like to send 0.1 BTC, so I split this to 5 payment 0.02 BTC each
+ one extra 0.02 BTC payment.
2. When recipient received 6 htlcs, he is able to spend only 5 of them.
If recipient receives, only 5 of them, it is still fine, and payment is
success.

In such scenario, single route/payment would fail, and payment as whole
would still be success. Do you think that would be possible? It could
greatly increase reliability of LN payments.

2018-02-09 11:15 GMT+01:00 CJP :

> Can you give a use case for this?
>
> Usually, especially in the common case that a payment is done in
> exchange for some non-cryptographic asset (e.g. physical goods), there
> already is some kind of trust between payer and payee. So, if a payment
> is split non-atomically into smaller transactions, and only a part
> succeeds, presumably they can cooperatively figure out some way to
> settle the situation.
>
> I spoke to people of the "interledger" project, and what they are
> planning to do is to non-atomically split *every* transaction into lots
> of micro-payments. In fact, they consider it unnecessary to enforce
> HTLCs with scripts, because their amounts are so small(*). If one
> micro-payment fails, that just makes them learn that a certain channel
> is unreliable, and they'll send further payments (and even the remaining
> part of the same payment) through a different route.
>
> CJP
>
> (*) not worth the extra on-blockchain fee due to the increased tx size.
>
> Olaoluwa Osuntokun schreef op di 06-02-2018 om 05:26 [+]:
> > Hi Y'all,
> >
> >
> > A common question I've seen concerning Lightning is: "I have five $2
> > channels, is it possible for me to *atomically* send $6 to fulfill a
> > payment?". The answer to this question is "yes", provided that the
> > receiver
> > waits to pull all HTLC's until the sum matches their invoice.
> > Typically, one
> > assumes that the receiver will supply a payment hash, and the sender
> > will
> > re-use the payment hash for all streams. This has the downside of
> > payment
> > hash re-use across *multiple* payments (which can already easily be
> > correlated), and also has a failure mode where if the sender fails to
> > actually satisfy all the payment flows, then the receiver can still
> > just
> > pull the monies (and possibly not disperse a service, or w/e).
> >
> >
> > Conner Fromknecht and I have come up with a way to achieve this over
> > Lightning while (1) not re-using any payment hashes across all payment
> > flows, and (2) adding a *strong* guarantee that the receiver won't be
> > paid
> > until *all* partial payment flows are extended. We call this scheme
> > AMP
> > (Atomic Multi-path Payments). It can be experimented with on Lightning
> > *today* with the addition of a new feature bit to gate this new
> > feature. The beauty of the scheme is that it requires no fundamental
> > changes
> > to the protocol as is now, as the negotiation is strictly *end-to-end*
> > between sender and receiver.
> >
> >
> > TL;DR: we repurpose some unused space in the onion per-hop payload of
> > the
> > onion blob to signal our protocol (and deliver some protocol-specific
> > data),
> > then use additive secret sharing to ensure that the receiver can't
> > pull the
> > payment until they have enough shares to reconstruct the original
> > pre-image.
> >
> >
> >
> >
> > Protocol Goals
> > ==
> > 1. Atomicity: The logical transaction should either succeed or fail in
> > entirety. Naturally, this implies that the receiver should not be
> > unable to
> > settle *any* of the partial payments, until all of them have arrived.
> >
> >
> > 2. Avoid Payment Hash Reuse: The payment preimages validated by the
> > consensus layer should be distinct for each partial payment.
> > Primarily,
> > this helps avoid correlation of the partial payments, and ensures that
> > malicious intermediaries straddling partial payments cannot steal
> > funds.
> >
> >
> > 3. Order Invariance: The protocol should be forgiving to the order in
> > which
> > partial payments arrive at the destination, adding robustness in the
> > face of
> > delays or routing failures.
> >
> >
> > 4. Non-interactive Setup: It should be possible for the sender to
> > perform an
> > AMP without directly coordinating with the receiving node.
> > Predominantly,
> > this means that the *sender* is able to determine the number of
> > partial
> > payments to use for a particular AMP, which makes sense since they
> > will be
> > the one fronting the fees for the cost of this parameter. Plus, we can
> > always turn a non-interactive protocol into an interactive one for the
> > purposes of invoicing.
> >
> >
> >
> >
> > Protocol Benefits
> > =
> >
> >
> > Sending pay payments predominantly over an AMP-like protocol has
> > several
> > clear benefits:
> >
> >
> >   - Eliminates the constraint that a single path from sender to
> > receiver
> 

Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning

[CJP]

Can you give a use case for this?

Usually, especially in the common case that a payment is done in
exchange for some non-cryptographic asset (e.g. physical goods), there
already is some kind of trust between payer and payee. So, if a payment
is split non-atomically into smaller transactions, and only a part
succeeds, presumably they can cooperatively figure out some way to
settle the situation.

I spoke to people of the "interledger" project, and what they are
planning to do is to non-atomically split *every* transaction into lots
of micro-payments. In fact, they consider it unnecessary to enforce
HTLCs with scripts, because their amounts are so small(*). If one
micro-payment fails, that just makes them learn that a certain channel
is unreliable, and they'll send further payments (and even the remaining
part of the same payment) through a different route.

CJP

(*) not worth the extra on-blockchain fee due to the increased tx size.

Olaoluwa Osuntokun schreef op di 06-02-2018 om 05:26 [+]:
> Hi Y'all, 
> 
> 
> A common question I've seen concerning Lightning is: "I have five $2
> channels, is it possible for me to *atomically* send $6 to fulfill a
> payment?". The answer to this question is "yes", provided that the
> receiver
> waits to pull all HTLC's until the sum matches their invoice.
> Typically, one
> assumes that the receiver will supply a payment hash, and the sender
> will
> re-use the payment hash for all streams. This has the downside of
> payment
> hash re-use across *multiple* payments (which can already easily be
> correlated), and also has a failure mode where if the sender fails to
> actually satisfy all the payment flows, then the receiver can still
> just
> pull the monies (and possibly not disperse a service, or w/e).
> 
> 
> Conner Fromknecht and I have come up with a way to achieve this over
> Lightning while (1) not re-using any payment hashes across all payment
> flows, and (2) adding a *strong* guarantee that the receiver won't be
> paid
> until *all* partial payment flows are extended. We call this scheme
> AMP
> (Atomic Multi-path Payments). It can be experimented with on Lightning
> *today* with the addition of a new feature bit to gate this new
> feature. The beauty of the scheme is that it requires no fundamental
> changes
> to the protocol as is now, as the negotiation is strictly *end-to-end*
> between sender and receiver.
> 
> 
> TL;DR: we repurpose some unused space in the onion per-hop payload of
> the
> onion blob to signal our protocol (and deliver some protocol-specific
> data),
> then use additive secret sharing to ensure that the receiver can't
> pull the
> payment until they have enough shares to reconstruct the original
> pre-image.
> 
> 
> 
> 
> Protocol Goals
> ==
> 1. Atomicity: The logical transaction should either succeed or fail in
> entirety. Naturally, this implies that the receiver should not be
> unable to
> settle *any* of the partial payments, until all of them have arrived.
> 
> 
> 2. Avoid Payment Hash Reuse: The payment preimages validated by the
> consensus layer should be distinct for each partial payment.
> Primarily,
> this helps avoid correlation of the partial payments, and ensures that
> malicious intermediaries straddling partial payments cannot steal
> funds.
> 
> 
> 3. Order Invariance: The protocol should be forgiving to the order in
> which
> partial payments arrive at the destination, adding robustness in the
> face of
> delays or routing failures.
> 
> 
> 4. Non-interactive Setup: It should be possible for the sender to
> perform an
> AMP without directly coordinating with the receiving node.
> Predominantly,
> this means that the *sender* is able to determine the number of
> partial
> payments to use for a particular AMP, which makes sense since they
> will be
> the one fronting the fees for the cost of this parameter. Plus, we can
> always turn a non-interactive protocol into an interactive one for the
> purposes of invoicing.
> 
> 
> 
> 
> Protocol Benefits

> =
> 
> 
> Sending pay payments predominantly over an AMP-like protocol has
> several
> clear benefits:
> 
> 
>   - Eliminates the constraint that a single path from sender to
> receiver
> with sufficient directional capacity. This reduces the pressure to
> have
> larger channels in order to support larger payment flows. As a
> result,
> the payment graph be very diffused, without sacrificing payment
> utility
> 
> 
>   - Reduces strain from larger payments on individual paths, and
> allows the
> liquidity imbalances to be more diffuse. We expect this to have a
> non-negligible impact on channel longevity. This is due to the
> fact that
> with usage of AMP, payment flows are typically *smaller* meaning
> that
> each payment will unbalance a channel to a lesser degree that
> with one giant flow.
> 
> 
>   - Potential fee savings for larger payments, contingent on there
> being a
> super-linear component to 

Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning

[Johan Torås Halseth]

Yeah, that is true, it would only give you the atomicity, not the 
decorrelation. I don’t see how you could get all the same properties using only 
one hash though. I guess the sender has no incentive to claim any of the 
payments before all of them have arrived, but you get no guarantee that partial 
payments cannot be made. Seems hard to do without introducing new primitives.
- Johan

On Thu, Feb 8, 2018 at 12:44, Jim Posen  wrote:
If using two hashes to deliver the payment while still getting a proof, I'm not 
sure what that provides above just sending regular lightning payments over 
multiple routes with one hash. Firstly, if there is a second hash, it would 
presumably be the same for all routes, making them linkable again, which AMP 
tries to solve. And secondly, the receiver has no incentive to claim any of the 
HTLCs before all of them are locked in, because in that case they are releasing 
the transaction receipt before fully being paid.

On Thu, Feb 8, 2018 at 8:41 AM, Johan Torås Halseth < joha...@gmail.com 
[joha...@gmail.com] > wrote:
An obvious way to make this compatible with proof-of-payment would be to 
require two hashes to claim the HTLC: the presage from the invoice payment hash 
(as today) + the new hash introduced here. This would give the sender a receipt 
after only one of the HTLCs was claimed. Would require changes to the scripts 
of course.
With Schnorr/EC operations this could probably be made more elegant, as 
mentioned.

- Johan
On Wed, Feb 7, 2018 at 18:21, Rusty Russell < ru...@rustcorp.com.au 
[ru...@rustcorp.com.au] > wrote:
Olaoluwa Osuntokun < laol...@gmail.com [laol...@gmail.com] > writes:
> Hi Y'all,
>
> A common question I've seen concerning Lightning is: "I have five $2
> channels, is it possible for me to *atomically* send $6 to fulfill a
> payment?". The answer to this question is "yes", provided that the receiver

This is awesome! I'm kicking myself for not proposing it :)

Unfortunately, your proposal defines a way to make multipath donations,
not multipath payments :(

In other words, you've lost proof of payment, which IMHO is critical.

Fortunately, this can be fairly trivially fixed when we go to scriptless
scripts or other equivalent decorrelation mechanism, when I think this
mechanism becomes extremely powerful.

> - Potential fee savings for larger payments, contingent on there being a
> super-linear component to routed fees. It's possible that with
> modifications to the fee schedule, it's actually *cheaper* to send
> payments over multiple flows rather than one giant flow.

This is a stretch. I'd stick with the increased reliability/privacy
arguments which are overwhelmingly compelling IMHO.

If I have any important feedback on deeper reading (and after a sccond
coffee), I'll send a separate email.

Thanks!
Rusty.
__ _
Lightning-dev mailing list
Lightning-dev@lists. linuxfoundation.org 
[Lightning-dev@lists.linuxfoundation.org]
https://lists.linuxfoundation. org/mailman/listinfo/ lightning-dev 
[https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev]

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

Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning

[Johan Torås Halseth]

An obvious way to make this compatible with proof-of-payment would be to 
require two hashes to claim the HTLC: the presage from the invoice payment 
hash (as today) + the new hash introduced here. This would give the sender 
a receipt after only one of the HTLCs was claimed. Would require changes to 
the scripts of course.
With Schnorr/EC operations this could probably be made more elegant, as 
mentioned.


- Johan
On Wed, Feb 7, 2018 at 18:21, Rusty Russell  wrote:
Olaoluwa Osuntokun  writes:
> Hi Y'all,
>
> A common question I've seen concerning Lightning is: "I have five $2
> channels, is it possible for me to *atomically* send $6 to fulfill a
> payment?". The answer to this question is "yes", provided that the 
receiver


This is awesome! I'm kicking myself for not proposing it :)

Unfortunately, your proposal defines a way to make multipath donations,
not multipath payments :(

In other words, you've lost proof of payment, which IMHO is critical.

Fortunately, this can be fairly trivially fixed when we go to scriptless
scripts or other equivalent decorrelation mechanism, when I think this
mechanism becomes extremely powerful.

> - Potential fee savings for larger payments, contingent on there being a
> super-linear component to routed fees. It's possible that with
> modifications to the fee schedule, it's actually *cheaper* to send
> payments over multiple flows rather than one giant flow.

This is a stretch. I'd stick with the increased reliability/privacy
arguments which are overwhelmingly compelling IMHO.

If I have any important feedback on deeper reading (and after a sccond
coffee), I'll send a separate email.

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

Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning

[Rusty Russell]

Olaoluwa Osuntokun  writes:
> Hi Y'all,
>
> A common question I've seen concerning Lightning is: "I have five $2
> channels, is it possible for me to *atomically* send $6 to fulfill a
> payment?". The answer to this question is "yes", provided that the receiver

This is awesome!  I'm kicking myself for not proposing it :)

Unfortunately, your proposal defines a way to make multipath donations,
not multipath payments :(

In other words, you've lost proof of payment, which IMHO is critical.

Fortunately, this can be fairly trivially fixed when we go to scriptless
scripts or other equivalent decorrelation mechanism, when I think this
mechanism becomes extremely powerful.

>   - Potential fee savings for larger payments, contingent on there being a
> super-linear component to routed fees. It's possible that with
> modifications to the fee schedule, it's actually *cheaper* to send
> payments over multiple flows rather than one giant flow.

This is a stretch.  I'd stick with the increased reliability/privacy
arguments which are overwhelmingly compelling IMHO.

If I have any important feedback on deeper reading (and after a sccond
coffee), I'll send a separate email.

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

Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning

[Rusty Russell]

Olaoluwa Osuntokun  writes:
> Protocol Overview
> ==
> This design can be seen as a generalization of the single, non-interactive
> payment scheme, that uses decoding of extra onion blobs (EOBs?) to encode
> extra data for the receiver. In that design, the extra data includes a
> payment preimage that the receiver can use to settle back the payment. EOBs
> and some method of parsing them are really the only requirement for this
> protocol to work. Thus, only the sender and receiver need to implement this
> feature in order for it to function, which can be announced using a feature
> bit.

OK, so this proposal conflates two things:

1. split payments.
2. expansion of onion space.

We've got a wiki page for #2 which could probably use some love:

https://github.com/lightningnetwork/lightning-rfc/wiki/Brainstorming#using-multiple-hops_data-cells-in-the-onion

For the final hop this may not be necessary, as we have 8 unused bytes
in `next addr`, giving us 20 free bytes.

But why not simplify the proposal: the payment preimage is the XOR of
those 20 bytes (with 12 zero bytes prepended)?  And the receiver gives
up to 30 seconds(?) to receive all the parts after the first one.

That means the sender gets dynamic resizing (if they want to split a
payment further, set one to randomness, and XOR that into the other),
the receive has only to remember the combination-so-far.

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

Re: [Lightning-dev] AMP: Atomic Multi-Path Payments over Lightning

[Olaoluwa Osuntokun]

Hi ZmnSCPxj,

> This is excellent work!

Thanks!

> I think, a `globalfeatures` odd bit could be used for this.  As it is
> end-ot-end, `localfeatures` is not appropriate.

Yep, it would need to be a global feature bit. In the case that we're
sending to a destination which isn't publicly advertised, then perhaps an
extension to BOLT-11 could be made to signal receiver support.

> I believe, currently, fees have not this super-linear component

Yep they don't. Arguably, we should also have a component that scales
according to the proposed CLTV value of the outgoing HTLC. At Scaling
Bitcoin Stanford, Aviv Zohar gave a talked titled "How to Charge Lightning"
where the authors analyzed the possible evolution of fees on the network
(and also suggested adding this super-linear component to extend the
lifetime of channels).  However, the talk itself focused on a very simple
"mega super duper hub" topology. Towards the end he alluded to a forthcoming
paper that had more comprehensive analysis of more complex topologies. I
look forward to the publication of their finalized work.

> Indeed, the existence of per-hop fees (`fee_base_msat`) means, splitting
> the payment over multiple flows will be, very likely, more expensive,
> compared to using a single flow.

Well it's still to be seen how the fee structure on mainnet emerges once the
network is still fully bootstrapped. AFAIK, most running on mainnet atm are
using the default fee schedules for their respective implementations. For
example, the default fee_base_msat for lnd is 1000 msat (1 satoshi).

> I believe the `realm` byte is intended for this.

The realm byte is meant to signal "forward this to the dogecoin channel".
ATM, we just default to 0 as "Bitcoin". However, the byte itself only really
need significance between the sender and the intermediate node. So there
isn't necessarily pressure to have a globally synchronized set of realm
bytes.

> Thus, you can route over nodes that are unaware of AMP, and only provide
> an AMP realm byte to the destination node, who, is able to reconstruct
this
> your AMP data as per your algorithm.

Yes, the intermediate nodes don't need to be aware of the end-to-end
protocol. For the final hop, there are actually 53 free bytes (before one
needs to signal the existence of EOBs):

  * 1 byte realm
  * 8 bytes next addr (all zeroes to signal final dest)
  * 32 bytes hmac (also all zeroes for the final dest)
  * 12 bytes padding

So any combo of these bytes can be used to signal more advanced protocols to
the final destination.


A correction from the prior email description:

> We can further modify our usage of the per-hop payloads to send
> (H(BP), s_i) to consume most of the EOB sent from sender to receiver.

This should actually be (H(s_0 || s_1 || ...), s_i). So we still allow them
to check this finger print to see if they have all the final shares, but
don't allow them to preemptively pull all the payments.


-- Laolu


On Mon, Feb 5, 2018 at 11:12 PM ZmnSCPxj  wrote:

> Good morning Laolu,
>
> This is excellent work!
>
> Some minor comments...
>
>
> (Atomic Multi-path Payments). It can be experimented with on Lightning
> *today* with the addition of a new feature bit to gate this new
> feature. The beauty of the scheme is that it requires no fundamental
> changes
> to the protocol as is now, as the negotiation is strictly *end-to-end*
> between sender and receiver.
>
>
> I think, a `globalfeatures` odd bit could be used for this.  As it is
> end-ot-end, `localfeatures` is not appropriate.
>
>   - Potential fee savings for larger payments, contingent on there being a
> super-linear component to routed fees. It's possible that with
> modifications to the fee schedule, it's actually *cheaper* to send
> payments over multiple flows rather than one giant flow.
>
>
> I believe, currently, fees have not this super-linear component.  Indeed,
> the existence of per-hop fees (`fee_base_msat`) means, splitting the
> payment over multiple flows will be, very likely, more expensive, compared
> to using a single flow.  Tiny roundoffs in computing the proportional fees
> (`fee_proportional_millionths`) may make smaller flows give a slight fee
> advantage, but I think the multiplication of per-hop fees will dominate.
>
>
>   - Using smaller payments increases the set of possible paths a partial
> payment could have taken, which reduces the effectiveness of static
> analysis techniques involving channel capacities and the plaintext
> values being forwarded.
>
>
> Strongly agree!
>
>
> In order to include the three tuple within the per-hop payload for the
> final
> destination, we repurpose the _first_ byte of the un-used padding bytes in
> the payload to signal version 0x01 of the AMP protocol (note this is a PoC
> outline, we would need to standardize signalling of these 12 bytes to
> support other protocols).
>
>
> I believe the `realm` byte is intended for this.  Intermediate nodes do