<div dir="ltr"><div>Hi Y&#39;all, </div><div><br></div><div>A common question I&#39;ve seen concerning Lightning is: &quot;I have five $2</div><div>channels, is it possible for me to *atomically* send $6 to fulfill a</div><div>payment?&quot;. The answer to this question is &quot;yes&quot;, provided that the receiver</div><div>waits to pull all HTLC&#39;s until the sum matches their invoice. Typically, one</div><div>assumes that the receiver will supply a payment hash, and the sender will</div><div>re-use the payment hash for all streams. This has the downside of payment</div><div>hash re-use across *multiple* payments (which can already easily be</div><div>correlated), and also has a failure mode where if the sender fails to</div><div>actually satisfy all the payment flows, then the receiver can still just</div><div>pull the monies (and possibly not disperse a service, or w/e).</div><div><br></div><div>Conner Fromknecht and I have come up with a way to achieve this over</div><div>Lightning while (1) not re-using any payment hashes across all payment</div><div>flows, and (2) adding a *strong* guarantee that the receiver won&#39;t be paid</div><div>until *all* partial payment flows are extended. We call this scheme AMP</div><div>(Atomic Multi-path Payments). It can be experimented with on Lightning</div><div>*today* with the addition of a new feature bit to gate this new</div><div>feature. The beauty of the scheme is that it requires no fundamental changes</div><div>to the protocol as is now, as the negotiation is strictly *end-to-end*</div><div>between sender and receiver.</div><div><br></div><div>TL;DR: we repurpose some unused space in the onion per-hop payload of the</div><div>onion blob to signal our protocol (and deliver some protocol-specific data),</div><div>then use additive secret sharing to ensure that the receiver can&#39;t pull the</div><div>payment until they have enough shares to reconstruct the original pre-image.</div><div><br></div><div><br></div><div>Protocol Goals</div><div>==============</div><div>1. Atomicity: The logical transaction should either succeed or fail in</div><div>entirety. Naturally, this implies that the receiver should not be unable to</div><div>settle *any* of the partial payments, until all of them have arrived.</div><div><br></div><div>2. Avoid Payment Hash Reuse: The payment preimages validated by the</div><div>consensus layer should be distinct for each partial payment.  Primarily,</div><div>this helps avoid correlation of the partial payments, and ensures that</div><div>malicious intermediaries straddling partial payments cannot steal funds.</div><div><br></div><div>3. Order Invariance: The protocol should be forgiving to the order in which</div><div>partial payments arrive at the destination, adding robustness in the face of</div><div>delays or routing failures.</div><div><br></div><div>4. Non-interactive Setup: It should be possible for the sender to perform an</div><div>AMP without directly coordinating with the receiving node. Predominantly,</div><div>this means that the *sender* is able to determine the number of partial</div><div>payments to use for a particular AMP, which makes sense since they will be</div><div>the one fronting the fees for the cost of this parameter. Plus, we can</div><div>always turn a non-interactive protocol into an interactive one for the</div><div>purposes of invoicing.</div><div><br></div><div><br></div><div>Protocol Benefits
</div><div>=================</div><div><br></div><div>Sending pay payments predominantly over an AMP-like protocol has several</div><div>clear benefits:</div><div><br></div><div>  - Eliminates the constraint that a single path from sender to receiver</div><div>    with sufficient directional capacity. This reduces the pressure to have</div><div>    larger channels in order to support larger payment flows. As a result,</div><div>    the payment graph be very diffused, without sacrificing payment</div><div>    utility</div><div><br></div><div>  - Reduces strain from larger payments on individual paths, and allows the</div><div>    liquidity imbalances to be more diffuse. We expect this to have a</div><div>    non-negligible impact on channel longevity. This is due to the fact that</div><div>    with usage of AMP, payment flows are typically *smaller* meaning that</div><div>    each payment will unbalance a channel to a lesser degree that</div><div>    with one giant flow.</div><div><br></div><div>  - Potential fee savings for larger payments, contingent on there being a</div><div>    super-linear component to routed fees. It&#39;s possible that with</div><div>    modifications to the fee schedule, it&#39;s actually *cheaper* to send</div><div>    payments over multiple flows rather than one giant flow.</div><div><br></div><div>  - Allows for logical payments larger than the current maximum value of an</div><div>    individual payment. Atm we have a (temporarily) limit on the max payment</div><div>    size. With AMP, this can be side stepped as each flow can be up the max</div><div>    size, with the sum of all flows exceeding the max.</div><div><br></div><div>  - Given sufficient path diversity, AMPs may improve the privacy of LN</div><div>    Intermediaries are now unaware to how much of the total payment they are</div><div>    forwarding, or even if they are forwarding a partial payment at all.</div><div><br></div><div>  - Using smaller payments increases the set of possible paths a partial</div><div>    payment could have taken, which reduces the effectiveness of static</div><div>    analysis techniques involving channel capacities and the plaintext</div><div>    values being forwarded.</div><div><br></div><div><br></div><div>Protocol Overview</div><div>==================</div><div>This design can be seen as a generalization of the single, non-interactive</div><div>payment scheme, that uses decoding of extra onion blobs (EOBs?) to encode</div><div>extra data for the receiver. In that design, the extra data includes a</div><div>payment preimage that the receiver can use to settle back the payment. EOBs</div><div>and some method of parsing them are really the only requirement for this</div><div>protocol to work. Thus, only the sender and receiver need to implement this</div><div>feature in order for it to function, which can be announced using a feature</div><div>bit. </div><div><br></div><div>First, let&#39;s review the current format of the per-hop payload for each node</div><div>described in BOLT-0004.</div><div><br></div><div>┌───────────────┬───────────────────┬────────────────┬───────────────────────┬─────────────────┬─────────────────┐</div><div>│Realm (1 byte) │Next Addr (8 bytes)│Amount (8 bytes)│Outgoing CLTV (4 bytes)│Unused (12 bytes)│ HMAC (32 bytes) │</div><div>└───────────────┴───────────────────┴────────────────┴───────────────────────┴─────────────────┴─────────────────┘</div><div>■────────────────────────────────────────────────────────────────────────────────────────────────────────────────■</div><div>                                              ┌─────────────────┐</div><div>                                              │65 Bytes Per Hop │</div><div>                                              └─────────────────┘</div><div><br></div><div>Currently, *each* node gets a 65-byte payload. We use this payload to give</div><div>each node instructions on *how* to forward a payment. We tell each node: the</div><div>realm (or chain to forward on), then next node to forward to, the amount to</div><div>forward (this is where fees are extracted by forwarding out less than in),</div><div>the outgoing CLTV (allows verification that the prior node didn&#39;t modify any</div><div>values), and finally an HMAC over the entire thing. </div><div><br></div><div>Two important points:</div><div>  1. We have 12 bytes for each hop that are currently unpurposed and can be</div><div>  used by application protocols to signal new interpretation of bytes and</div><div>  also deliver additional encrypted+authenticated data to *each* hop.</div><div><br></div><div>  2. The protocol currently has a hard limit of 20-hops. With this feature</div><div>  we ensure that the packet stays fixed sized during processing in order to</div><div>  avoid leaking positional information. Typically most payments won&#39;t use</div><div>  all 20 hops, as a result, we can use the remaining hops to stuff in *even</div><div>  more* data.</div><div><br></div><div><br></div><div>Protocol Description</div><div>====================</div><div>The solution we propose is Atomic Multi-path Payments (AMPs). At a high</div><div>level, this leverages EOBs to deliver additive shares of a base preimage,</div><div>from which the payment preimages of partial payments can be derived. The</div><div>receiver can only construct this value after having received all of the</div><div>partial payments, satisfying the atomicity constraint.</div><div><br></div><div>The basic protocol:

</div><div><br></div><div>Primitives</div><div>==========</div><div>Let H be a CRH function.</div><div>Let || denote concatenation. </div><div>Let ^ denote xor.

</div><div><br></div><div><br></div><div>Sender Requirements</div><div>===================</div><div>The parameters to the sending procedure are a random identifier ID, the</div><div>number of partial payments n, and the total payment value V. Assume the</div><div>sender has some way of dividing V such that V = v_1 + … + v_n.</div><div><br></div><div>To begin, the sender builds the base preimage BP, from which n partial</div><div>preimages will be derived. Next, the sender samples n additive shares s_1,</div><div>…, s_n, and takes the sum to compute BP = s_1 ^ … ^ s_n.</div><div><br></div><div>With the base preimage created, the sender now moves on to constructing the</div><div>n partial payments. For each i in [1,n], the sender deterministically</div><div>computes the partial preimage r_i = H(BP ||  i), by concatenating the</div><div>sequence number i to the base preimage and hashing the result. Afterwards,</div><div>it applies H to determine the payment hash to use in the i’th partial</div><div>payment as h_i = H(r_i). Note that that with this preimage derivation</div><div>scheme, once the payments are pulled each pre-image is distinct and</div><div>indistinguishable from any other.</div><div><br></div><div>With all of the pieces in place, the sender initiates the i’th payment by</div><div>constructing a route to the destination with value v_i and payment hash h_i.</div><div>The tuple (ID, n, s_i) is included in the EOB to be opened by the receiver.</div><div><br></div><div>In order to include the three tuple within the per-hop payload for the final</div><div>destination, we repurpose the _first_ byte of the un-used padding bytes in</div><div>the payload to signal version 0x01 of the AMP protocol (note this is a PoC</div><div>outline, we would need to standardize signalling of these 12 bytes to</div><div>support other protocols). Typically this byte isn&#39;t set, so the existence of</div><div>this means that we&#39;re (1) using AMP, and (2) the receiver should consume the</div><div>_next_ hop as well. So if the payment length is actually 5, the sender tacks</div><div>on an additional dummy 6th hop, encrypted with the _same_ shared secret for</div><div>that hop to deliver the e2e encrypted data.</div><div><br></div><div>Note, the sender can retry partial payments just as they would normal</div><div>payments, since they are order invariant, and would be indistinguishable</div><div>from regular payments to intermediaries in the network.  
</div><div><br></div><div><br></div><div>Receiver
Requirements</div><div>=====================</div><div><br></div><div>Upon the arrival of each partial payment, the receiver will iteratively</div><div>reconstruct BP, and do some bookkeeping to figure out when to settle the</div><div>partial payments. During this reconstruction process, the receiver does not</div><div>need to be aware of the order in which the payments were sent, and in fact</div><div>nothing about the incoming partial payments reveals this information to the</div><div>receiver, though this can be learned after reconstructing BP.</div><div><br></div><div>Each EOB is decoded to retrieve (ID, n, s_i), where i is the unique but</div><div>unknown index of the incoming partial payment. The receiver has access to</div><div>persistent key-value store DB that maps ID to (n, c*, BP*), where c*</div><div>represents the number of partial payments received, BP* is the sum of the</div><div>received additive shares, and the superscript * denotes that the value is</div><div>being updated iteratively. c* and BP* both have initial values of 0.</div><div><br></div><div>In the basic protocol, the receiver cache’s the first n it sees, and</div><div>verifies that all incoming partial payments have the same n. The receiver</div><div>should reject all partial payments if any EOB deviates.  Next, the we update</div><div>our persistent store with DB[ID] = (n, c* + 1, BP* ^ s_i), advancing the</div><div>reconstruction by one step.</div><div><br></div><div>If c* + 1 &lt; n, there are still more packets in flight, so we sit tight.</div><div>Otherwise, the receiver assumes all partial payments have arrived, and can</div><div>being settling them back. Using the base preimage BP = BP* ^ s_i from our</div><div>final iteration, the receiver can re-derive all n partial preimages and</div><div>payment hashes, using r_i = H(BP || i) and h_i = H(r_i) simply through</div><div>knowledge of n and BP. </div><div><br></div><div>Finally, the receiver settles back any outstanding payments that include</div><div>payment hash h_i using the partial preimage r_i. Each r_i will appear random</div><div>due to the nature of H, as will it’s corresponding h_i. Thus, each partial</div><div>payment should appear uncorrelated, and does not reveal that it is part of</div><div>an AMP nor the number of partial payments used. </div><div><br></div><div>Non-interactive to Interactive AMPs</div><div>===================================</div><div><br></div><div>Sender simply receives an ID and amount from the receiver in an invoice</div><div>before initiating the protocol. The receiver should only consider the</div><div>invoice settled if the total amount received in partial payments containing</div><div>ID matches or exceeds the amount specified in the invoice. With this</div><div>variant, the receiver is able to map all partial payments to a pre-generated</div><div>invoice statement.</div><div><br></div><div><br></div><div>Additive Shares vs Threshold-Shares</div><div>===================================</div><div><br></div><div>The biggest reason to use additive shares seems to be atomicity. Threshold</div><div>shares open the door to some partial payments being settled, even if others</div><div>are left in flight. Haven’t yet come up with a good reason for using</div><div>threshold schemes, but there seem to be plenty against it. </div><div><br></div><div>Reconstruction of additive shares can be done iteratively, and is win for</div><div>the storage and computation requirements on the receiving end. If the sender</div><div>decides to use fewer than n partial payments, the remaining shares could be</div><div>included in the EOB of the final partial payment to allow the sender to</div><div>reconstruct sooner. Sender could also optimistically do partial</div><div>reconstruction on this last aggregate value.</div><div><br></div><div><br></div><div>Adaptive AMPs</div><div>=============</div><div><br></div><div>The sender may not always be aware of how many partial payments they wish to</div><div>send at the time of the first partial payment, at which point the simplified</div><div>protocol would require n to be chosen. To accommodate, the above scheme can</div><div>be adapted to handle a dynamically chosen n by iteratively constructing the</div><div>shared secrets as follows.</div><div><br></div><div>Starting with a base preimage BP, the key trick is that the sender remember</div><div>the difference between the base preimage and the sum of all partial</div><div>preimages used so far. The relation is described using the following</div><div>equations:</div><div><br></div><div>    X_0 = 0
</div><div>    X_i = X_{i-1} ^ s_i
</div><div>    X_n = BP ^ X_{n-1} </div><div><br></div><div>where if n=1, X_1 = BP, implying that this is in fact a generalization of</div><div>the single, non-interactive payment scheme mentioned above. For i=1, ...,</div><div>n-1, the sender sends s_i in the EOB, and  X_n for the n-th share. </div><div><br></div><div>Iteratively reconstructing s_1 ^ …. ^ s_{n-1} ^ X_n = BP, allows the</div><div>receiver to compute all relevant r_i = H(BP || i) and h_i = H(r_i). Lastly,</div><div>the final number of partial payments n could be signaled in the final EOB,</div><div>which would also serve as a sentinel value for signaling completion. In</div><div>response to DOS vectors stemming from unknown values of n, implementations</div><div>could consider advertising a maximum value for n, or adopting some sort of</div><div>framing pattern for conveying that more partial payments are on the way.</div><div><br></div><div>We can further modify our usage of the per-hop payloads to send (H(BP), s_i) to</div><div>consume most of the EOB sent from sender to receiver. In this scenario, we&#39;d</div><div>repurpose the 11-bytes *after* our signalling byte in the unused byte section</div><div>to store the payment ID (which should be unique for each payment). In the case</div><div>of a non-interactive payment, this will be unused. While for interactive</div><div>payments, this will be the ID within the invoice. To deliver this slimmer</div><div>2-tuple, we&#39;ll use 32-bytes for the hash of the BP, and 32-bytes for the</div><div>partial pre-image share, leaving an un-used byte in the payload.</div><div><br></div><div><br></div><div>Cross-Chain AMPs</div><div>================</div><div><br></div><div>AMPs can be used to pay a receiver in multiple currencies atomically...which</div><div>is pretty cool :D</div><div><br></div><div><br></div><div>Open Research Questions</div><div>=======================</div><div><br></div><div>The above is a protocol sketch to achieve atomic multi-path payments over</div><div>Lightning. The details concerning onion blob usage serves as a template that</div><div>future protocols can draw upon in order to deliver additional data to *any*</div><div>hop in the route. However, there are still a few open questions before</div><div>something like this can be feasibly deployed.</div><div><br></div><div>1. How does the sender decide how many chunked payments to send, and the</div><div>size of each payment?</div><div><br></div><div>  - Upon a closer examination, this seems to overlap with the task of</div><div>    congestion control within TCP. The sender may be able to utilize</div><div>    inspired heuristics to gauge: (1) how large the initial payment should be</div><div>    and (2) how many subsequent payments may be required. Note that if the</div><div>    first payment succeeds, then the exchange is over in a signal round.</div><div><br></div><div>2. How can AMP and HORNET be composed?</div><div><br></div><div>  - If we eventually integrate HORNET, then a distinct communications</div><div>    sessions can be established to allow the sender+receiver to exchange</div><div>    up-to-date partial payment information. This may allow the sender to more</div><div>    accurately size each partial payment.</div><div>   </div><div>3. Can the sender&#39;s initial strategy be governed by an instance of the</div><div>Push-relabel max flow algo?</div><div><br></div><div>4. How does this mesh with the current max HTLC limit on a commitment?</div><div><br></div><div>   - ATM, we have a max limit on the number of active HTLC&#39;s on a particular</div><div>     commitment transaction. We do this, as otherwise it&#39;s possible that the</div><div>     transaction is too large, and exceeds standardness w.r.t transaction</div><div>     size. In a world where most payments use an AMP-like protocol, then</div><div>     overall ant any given instance there will be several pending HTLC&#39;s on</div><div>     commitments network wise. </div><div><br></div><div>     This may incentivize nodes to open more channels in order to support</div><div>     the increased commitment space utilization.</div><div><br></div><div><br></div><div>Conclusion</div><div>==========</div><div><br></div><div>We&#39;ve presented a design outline of how to integrate atomic multi-path</div><div>payments (AMP) into Lightning. The existence of such a construct allows a</div><div>sender to atomically split a payment flow amongst several individual payment</div><div>flows. As a result, larger channels aren&#39;t as important as it&#39;s possible to</div><div>utilize one total outbound payment bandwidth to send several channels.</div><div>Additionally, in order to support the increased load, internal routing nodes</div><div>are incensed have more active channels. The existence of AMP-like payments</div><div>may also increase the longevity of channels as there&#39;ll be smaller, more</div><div>numerous payment flows, making it unlikely that a single payment comes</div><div>across unbalances a channel entirely. We&#39;ve also showed how one can utilize</div><div>the current onion packet format to deliver additional data from a sender to</div><div>receiver, that&#39;s still e2e authenticated.</div><div><br></div><div><br></div><div>-- Conner &amp;&amp; Laolu</div><div><br></div></div>