{"type":"rich","version":"1.0","author_name":"npub19helcfnqgk2jrwzjex2aflq6jwfc8zd9uzzkwlgwhve7lykv23mq5zkvn4","author_url":"https://nostr.ae/npub19helcfnqgk2jrwzjex2aflq6jwfc8zd9uzzkwlgwhve7lykv23mq5zkvn4","provider_name":"njump","provider_url":"https://nostr.ae","html":"📅 Original date posted:2018-02-06\n📝 Original message:\nHi Y'all,\n\nA common question I've seen concerning Lightning is: \"I have five $2\nchannels, is it possible for me to *atomically* send $6 to fulfill a\npayment?\". The answer to this question is \"yes\", provided that the receiver\nwaits to pull all HTLC's until the sum matches their invoice. Typically, one\nassumes that the receiver will supply a payment hash, and the sender will\nre-use the payment hash for all streams. This has the downside of payment\nhash re-use across *multiple* payments (which can already easily be\ncorrelated), and also has a failure mode where if the sender fails to\nactually satisfy all the payment flows, then the receiver can still just\npull the monies (and possibly not disperse a service, or w/e).\n\nConner Fromknecht and I have come up with a way to achieve this over\nLightning while (1) not re-using any payment hashes across all payment\nflows, and (2) adding a *strong* guarantee that the receiver won't be paid\nuntil *all* partial payment flows are extended. We call this scheme AMP\n(Atomic Multi-path Payments). It can be experimented with on Lightning\n*today* with the addition of a new feature bit to gate this new\nfeature. The beauty of the scheme is that it requires no fundamental changes\nto the protocol as is now, as the negotiation is strictly *end-to-end*\nbetween sender and receiver.\n\nTL;DR: we repurpose some unused space in the onion per-hop payload of the\nonion blob to signal our protocol (and deliver some protocol-specific data),\nthen use additive secret sharing to ensure that the receiver can't pull the\npayment until they have enough shares to reconstruct the original pre-image.\n\n\nProtocol Goals\n==============\n1. Atomicity: The logical transaction should either succeed or fail in\nentirety. Naturally, this implies that the receiver should not be unable to\nsettle *any* of the partial payments, until all of them have arrived.\n\n2. Avoid Payment Hash Reuse: The payment preimages validated by the\nconsensus layer should be distinct for each partial payment.  Primarily,\nthis helps avoid correlation of the partial payments, and ensures that\nmalicious intermediaries straddling partial payments cannot steal funds.\n\n3. Order Invariance: The protocol should be forgiving to the order in which\npartial payments arrive at the destination, adding robustness in the face of\ndelays or routing failures.\n\n4. Non-interactive Setup: It should be possible for the sender to perform an\nAMP without directly coordinating with the receiving node. Predominantly,\nthis means that the *sender* is able to determine the number of partial\npayments to use for a particular AMP, which makes sense since they will be\nthe one fronting the fees for the cost of this parameter. Plus, we can\nalways turn a non-interactive protocol into an interactive one for the\npurposes of invoicing.\n\n\nProtocol Benefits\n=================\n\nSending pay payments predominantly over an AMP-like protocol has several\nclear benefits:\n\n  - Eliminates the constraint that a single path from sender to receiver\n    with sufficient directional capacity. This reduces the pressure to have\n    larger channels in order to support larger payment flows. As a result,\n    the payment graph be very diffused, without sacrificing payment\n    utility\n\n  - Reduces strain from larger payments on individual paths, and allows the\n    liquidity imbalances to be more diffuse. We expect this to have a\n    non-negligible impact on channel longevity. This is due to the fact that\n    with usage of AMP, payment flows are typically *smaller* meaning that\n    each payment will unbalance a channel to a lesser degree that\n    with one giant flow.\n\n  - Potential fee savings for larger payments, contingent on there being a\n    super-linear component to routed fees. It's possible that with\n    modifications to the fee schedule, it's actually *cheaper* to send\n    payments over multiple flows rather than one giant flow.\n\n  - Allows for logical payments larger than the current maximum value of an\n    individual payment. Atm we have a (temporarily) limit on the max payment\n    size. With AMP, this can be side stepped as each flow can be up the max\n    size, with the sum of all flows exceeding the max.\n\n  - Given sufficient path diversity, AMPs may improve the privacy of LN\n    Intermediaries are now unaware to how much of the total payment they are\n    forwarding, or even if they are forwarding a partial payment at all.\n\n  - Using smaller payments increases the set of possible paths a partial\n    payment could have taken, which reduces the effectiveness of static\n    analysis techniques involving channel capacities and the plaintext\n    values being forwarded.\n\n\nProtocol Overview\n==================\nThis design can be seen as a generalization of the single, non-interactive\npayment scheme, that uses decoding of extra onion blobs (EOBs?) to encode\nextra data for the receiver. In that design, the extra data includes a\npayment preimage that the receiver can use to settle back the payment. EOBs\nand some method of parsing them are really the only requirement for this\nprotocol to work. Thus, only the sender and receiver need to implement this\nfeature in order for it to function, which can be announced using a feature\nbit.\n\nFirst, let's review the current format of the per-hop payload for each node\ndescribed in BOLT-0004.\n\n┌───────────────┬───────────────────┬────────────────┬───────────────────────┬─────────────────┬─────────────────┐\n│Realm (1 byte) │Next Addr (8 bytes)│Amount (8 bytes)│Outgoing CLTV (4\nbytes)│Unused (12 bytes)│ HMAC (32 bytes) │\n└───────────────┴───────────────────┴────────────────┴───────────────────────┴─────────────────┴─────────────────┘\n■────────────────────────────────────────────────────────────────────────────────────────────────────────────────■\n                                              ┌─────────────────┐\n                                              │65 Bytes Per Hop │\n                                              └─────────────────┘\n\nCurrently, *each* node gets a 65-byte payload. We use this payload to give\neach node instructions on *how* to forward a payment. We tell each node: the\nrealm (or chain to forward on), then next node to forward to, the amount to\nforward (this is where fees are extracted by forwarding out less than in),\nthe outgoing CLTV (allows verification that the prior node didn't modify any\nvalues), and finally an HMAC over the entire thing.\n\nTwo important points:\n  1. We have 12 bytes for each hop that are currently unpurposed and can be\n  used by application protocols to signal new interpretation of bytes and\n  also deliver additional encrypted+authenticated data to *each* hop.\n\n  2. The protocol currently has a hard limit of 20-hops. With this feature\n  we ensure that the packet stays fixed sized during processing in order to\n  avoid leaking positional information. Typically most payments won't use\n  all 20 hops, as a result, we can use the remaining hops to stuff in *even\n  more* data.\n\n\nProtocol Description\n====================\nThe solution we propose is Atomic Multi-path Payments (AMPs). At a high\nlevel, this leverages EOBs to deliver additive shares of a base preimage,\nfrom which the payment preimages of partial payments can be derived. The\nreceiver can only construct this value after having received all of the\npartial payments, satisfying the atomicity constraint.\n\nThe basic protocol:\n\nPrimitives\n==========\nLet H be a CRH function.\nLet || denote concatenation.\nLet ^ denote xor.\n\n\nSender Requirements\n===================\nThe parameters to the sending procedure are a random identifier ID, the\nnumber of partial payments n, and the total payment value V. Assume the\nsender has some way of dividing V such that V = v_1 + … + v_n.\n\nTo begin, the sender builds the base preimage BP, from which n partial\npreimages will be derived. Next, the sender samples n additive shares s_1,\n…, s_n, and takes the sum to compute BP = s_1 ^ … ^ s_n.\n\nWith the base preimage created, the sender now moves on to constructing the\nn partial payments. For each i in [1,n], the sender deterministically\ncomputes the partial preimage r_i = H(BP ||  i), by concatenating the\nsequence number i to the base preimage and hashing the result. Afterwards,\nit applies H to determine the payment hash to use in the i’th partial\npayment as h_i = H(r_i). Note that that with this preimage derivation\nscheme, once the payments are pulled each pre-image is distinct and\nindistinguishable from any other.\n\nWith all of the pieces in place, the sender initiates the i’th payment by\nconstructing a route to the destination with value v_i and payment hash h_i.\nThe tuple (ID, n, s_i) is included in the EOB to be opened by the receiver.\n\nIn order to include the three tuple within the per-hop payload for the final\ndestination, we repurpose the _first_ byte of the un-used padding bytes in\nthe payload to signal version 0x01 of the AMP protocol (note this is a PoC\noutline, we would need to standardize signalling of these 12 bytes to\nsupport other protocols). Typically this byte isn't set, so the existence of\nthis means that we're (1) using AMP, and (2) the receiver should consume the\n_next_ hop as well. So if the payment length is actually 5, the sender tacks\non an additional dummy 6th hop, encrypted with the _same_ shared secret for\nthat hop to deliver the e2e encrypted data.\n\nNote, the sender can retry partial payments just as they would normal\npayments, since they are order invariant, and would be indistinguishable\nfrom regular payments to intermediaries in the network.\n\n\nReceiver Requirements\n=====================\n\nUpon the arrival of each partial payment, the receiver will iteratively\nreconstruct BP, and do some bookkeeping to figure out when to settle the\npartial payments. During this reconstruction process, the receiver does not\nneed to be aware of the order in which the payments were sent, and in fact\nnothing about the incoming partial payments reveals this information to the\nreceiver, though this can be learned after reconstructing BP.\n\nEach EOB is decoded to retrieve (ID, n, s_i), where i is the unique but\nunknown index of the incoming partial payment. The receiver has access to\npersistent key-value store DB that maps ID to (n, c*, BP*), where c*\nrepresents the number of partial payments received, BP* is the sum of the\nreceived additive shares, and the superscript * denotes that the value is\nbeing updated iteratively. c* and BP* both have initial values of 0.\n\nIn the basic protocol, the receiver cache’s the first n it sees, and\nverifies that all incoming partial payments have the same n. The receiver\nshould reject all partial payments if any EOB deviates.  Next, the we update\nour persistent store with DB[ID] = (n, c* + 1, BP* ^ s_i), advancing the\nreconstruction by one step.\n\nIf c* + 1 \u003c n, there are still more packets in flight, so we sit tight.\nOtherwise, the receiver assumes all partial payments have arrived, and can\nbeing settling them back. Using the base preimage BP = BP* ^ s_i from our\nfinal iteration, the receiver can re-derive all n partial preimages and\npayment hashes, using r_i = H(BP || i) and h_i = H(r_i) simply through\nknowledge of n and BP.\n\nFinally, the receiver settles back any outstanding payments that include\npayment hash h_i using the partial preimage r_i. Each r_i will appear random\ndue to the nature of H, as will it’s corresponding h_i. Thus, each partial\npayment should appear uncorrelated, and does not reveal that it is part of\nan AMP nor the number of partial payments used.\n\nNon-interactive to Interactive AMPs\n===================================\n\nSender simply receives an ID and amount from the receiver in an invoice\nbefore initiating the protocol. The receiver should only consider the\ninvoice settled if the total amount received in partial payments containing\nID matches or exceeds the amount specified in the invoice. With this\nvariant, the receiver is able to map all partial payments to a pre-generated\ninvoice statement.\n\n\nAdditive Shares vs Threshold-Shares\n===================================\n\nThe biggest reason to use additive shares seems to be atomicity. Threshold\nshares open the door to some partial payments being settled, even if others\nare left in flight. Haven’t yet come up with a good reason for using\nthreshold schemes, but there seem to be plenty against it.\n\nReconstruction of additive shares can be done iteratively, and is win for\nthe storage and computation requirements on the receiving end. If the sender\ndecides to use fewer than n partial payments, the remaining shares could be\nincluded in the EOB of the final partial payment to allow the sender to\nreconstruct sooner. Sender could also optimistically do partial\nreconstruction on this last aggregate value.\n\n\nAdaptive AMPs\n=============\n\nThe sender may not always be aware of how many partial payments they wish to\nsend at the time of the first partial payment, at which point the simplified\nprotocol would require n to be chosen. To accommodate, the above scheme can\nbe adapted to handle a dynamically chosen n by iteratively constructing the\nshared secrets as follows.\n\nStarting with a base preimage BP, the key trick is that the sender remember\nthe difference between the base preimage and the sum of all partial\npreimages used so far. The relation is described using the following\nequations:\n\n    X_0 = 0\n    X_i = X_{i-1} ^ s_i\n    X_n = BP ^ X_{n-1}\n\nwhere if n=1, X_1 = BP, implying that this is in fact a generalization of\nthe single, non-interactive payment scheme mentioned above. For i=1, ...,\nn-1, the sender sends s_i in the EOB, and  X_n for the n-th share.\n\nIteratively reconstructing s_1 ^ …. ^ s_{n-1} ^ X_n = BP, allows the\nreceiver to compute all relevant r_i = H(BP || i) and h_i = H(r_i). Lastly,\nthe final number of partial payments n could be signaled in the final EOB,\nwhich would also serve as a sentinel value for signaling completion. In\nresponse to DOS vectors stemming from unknown values of n, implementations\ncould consider advertising a maximum value for n, or adopting some sort of\nframing pattern for conveying that more partial payments are on the way.\n\nWe can further modify our usage of the per-hop payloads to send (H(BP),\ns_i) to\nconsume most of the EOB sent from sender to receiver. In this scenario, we'd\nrepurpose the 11-bytes *after* our signalling byte in the unused byte\nsection\nto store the payment ID (which should be unique for each payment). In the\ncase\nof a non-interactive payment, this will be unused. While for interactive\npayments, this will be the ID within the invoice. To deliver this slimmer\n2-tuple, we'll use 32-bytes for the hash of the BP, and 32-bytes for the\npartial pre-image share, leaving an un-used byte in the payload.\n\n\nCross-Chain AMPs\n================\n\nAMPs can be used to pay a receiver in multiple currencies atomically...which\nis pretty cool :D\n\n\nOpen Research Questions\n=======================\n\nThe above is a protocol sketch to achieve atomic multi-path payments over\nLightning. The details concerning onion blob usage serves as a template that\nfuture protocols can draw upon in order to deliver additional data to *any*\nhop in the route. However, there are still a few open questions before\nsomething like this can be feasibly deployed.\n\n1. How does the sender decide how many chunked payments to send, and the\nsize of each payment?\n\n  - Upon a closer examination, this seems to overlap with the task of\n    congestion control within TCP. The sender may be able to utilize\n    inspired heuristics to gauge: (1) how large the initial payment should\nbe\n    and (2) how many subsequent payments may be required. Note that if the\n    first payment succeeds, then the exchange is over in a signal round.\n\n2. How can AMP and HORNET be composed?\n\n  - If we eventually integrate HORNET, then a distinct communications\n    sessions can be established to allow the sender+receiver to exchange\n    up-to-date partial payment information. This may allow the sender to\nmore\n    accurately size each partial payment.\n\n3. Can the sender's initial strategy be governed by an instance of the\nPush-relabel max flow algo?\n\n4. How does this mesh with the current max HTLC limit on a commitment?\n\n   - ATM, we have a max limit on the number of active HTLC's on a particular\n     commitment transaction. We do this, as otherwise it's possible that the\n     transaction is too large, and exceeds standardness w.r.t transaction\n     size. In a world where most payments use an AMP-like protocol, then\n     overall ant any given instance there will be several pending HTLC's on\n     commitments network wise.\n\n     This may incentivize nodes to open more channels in order to support\n     the increased commitment space utilization.\n\n\nConclusion\n==========\n\nWe've presented a design outline of how to integrate atomic multi-path\npayments (AMP) into Lightning. The existence of such a construct allows a\nsender to atomically split a payment flow amongst several individual payment\nflows. As a result, larger channels aren't as important as it's possible to\nutilize one total outbound payment bandwidth to send several channels.\nAdditionally, in order to support the increased load, internal routing nodes\nare incensed have more active channels. The existence of AMP-like payments\nmay also increase the longevity of channels as there'll be smaller, more\nnumerous payment flows, making it unlikely that a single payment comes\nacross unbalances a channel entirely. We've also showed how one can utilize\nthe current onion packet format to deliver additional data from a sender to\nreceiver, that's still e2e authenticated.\n\n\n-- Conner \u0026\u0026 Laolu\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/lightning-dev/attachments/20180206/8c4a40c4/attachment-0001.html\u003e"}