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

Jim Posen jim.posen at gmail.com
Wed Feb 7 08:36:35 UTC 2018


This is a really neat idea.

This is a question about non-interactive payments in general, but is there
any way to get a proof of payment? With regular invoices, knowledge of the
preimage serves as cryptographic proof that the payment was delivered.

On Feb 6, 2018 6:26 PM, "Conner Fromknecht" <conner at lightning.engineering>
wrote:

>
> Hi ZmnSCPxj and Laolu,
>
> >  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.
>
> As Laolu pointed out, we have yet to see how fees evolve on mainnet or
> what will
> emerge as a sane, default fee schedules. I agree that if the same
> proportional
> fee is used across all partial payments, then it could certainly be more
> expensive.
>
> However, it could also be the case that you were paying a needlessly high
> proportional fee to begin with, because paths of sufficient capacity to the
> destination were scarce. In an AMP world, there will be an abundance of
> channels
> that can route small, partial payments, which may itself drive down the
> competitive fee rate for smaller payments. Just a hypothesis, we shall see
> where
> supply meets demand!
>
> At the end of the day, the user can always fall back to regular payment if
> they
> expect to end up paying more fees using an AMP.
>
> > (If we want to support multiple routes converging to an intermediate
> node,
> > then continue routing to a different final node after routes have merged
> (i.e.
> > A->B->C->D, and A->E->C->D, with the payment being merged by C, who
> forwards
> > the combination to D), then we need to follow the current hop data
> format, but
> > I think supporting AMP at final payees is actually enough...
>
> I think this is an interesting idea, sounds maybe like a
> recursive/hierarchical
> AMP? The ability to merge the payments seems like it would result in a
> decent privacy
> leak, as I believe an intermediary would have enough evidence to prove
> that two
> payments were merged/correlated. Simple traffic analysis would also reveal
> a
> discrepancy in the number of incoming and outgoing packets, and possibly
> other
> observable differences in routing (some) AMPs vs regular payments.
>
> FWIW the current proposal allows the paths of partial payments to overlap,
> in such a scenario C would just forward the HTLCs independently. One could
> send
> them all along the same path if they desired! I'm assuming the intent here
> is to
> try and reduce total fees?
>
> Minor correction^2:
>
> > This should actually be (H(s_0 || s_1 || ...), s_i).
>
> This assumes the receiver knows the indexes of each share. Without this
> knowledge they would have to brute force all orderings to check the
> fingerprint.
>
> To maintain order invariance on the receiving end, I would propose sending
> (0, s_i) for the first n-1 partial payments, and then (n, s_i) on the
> final one.
> As in the description of the basic AMP scheme, the receiver maintains a
> persistent count of how many partial payments have been received for ID.
> If the
> receiver does not get the last payment last, the receiver just waits until
> all n
> have been received before deciding that its reconstructed value is BP.
>
> The receiver can verify they've received the correct BP and n by
> rederiving the
> partial preimages r_i = H(BP || i) and checking that there are n
> outstanding
> payments, one for each h_i = H(r_i). This also saves the receiving node n
> additional hash invocations.
>
> -Conner
>
> On Tue, Feb 6, 2018 at 4:04 PM Olaoluwa Osuntokun <laolu32 at gmail.com>
> wrote:
>
>> 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 <ZmnSCPxj at protonmail.com> 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
>>> not need to understand realm bytes that are understood by other nodes in
>>> the route, including the realm bytes understood by the final destination,
>>> as intermediate nodes cannot, indeed, read the hop data of other nodes.
>>> 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.
>>>
>>> Indeed, the `realm` byte controls the interpretation of the rest of the
>>> 65-byte packet.  If you define, instead, a separate `realm` that is
>>> understood by the destination node, you can redefine the entire 64 bytes of
>>> the final hop data as you wish.
>>>
>>> If we support AMP only at final payees, we can completely redefine the
>>> 64 bytes in the final hop data for the new AMP `realm`, and not consume the
>>> next hop (which would reduce route length by 1).
>>>
>>> (If we want to support multiple routes converging to an intermediate
>>> node, then continue routing to a different final node after routes have
>>> merged (i.e. A->B->C->D, and A->E->C->D, with the payment being merged by
>>> C, who forwards the combination to D), then we need to follow the current
>>> hop data format, but I think supporting AMP at final payees is actually
>>> enough... AMP at intermediate nodes might not be used often enough by
>>> senders for it to matter, as taking advantage of that seems more complex
>>> than just asking your routing algo to provide you multiple routes to a
>>> destination, which you are probably already doing)
>>>
>>> ----
>>>
>>> Overall, good work I think.
>>>
>>> Regards,
>>> ZmnSCPxj
>>>
>> _______________________________________________
>> Lightning-dev mailing list
>> Lightning-dev at lists.linuxfoundation.org
>> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>>
>
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180207/48a507f8/attachment-0001.html>


More information about the Lightning-dev mailing list