Skip to content

Latest commit

 

History

History
358 lines (274 loc) · 13.3 KB

21-atomic-multi-path-payments.md

File metadata and controls

358 lines (274 loc) · 13.3 KB
Raw

BOLT 21: Atomic Multi-Path Payments

Authors:

Created: 2021-03-04

Table of Contents

Introduction

Abstract

This document proposes a standard for multi-path Lightning payments where HTLC preimages are generated sender-side.

While simple, the construction directly lends itself to spontaneous payments, removing the need for a setup phase to exchange an invoice. It also enables other of useful applications where a one-time setup can be be amortized over an an unbounded number of payments, e.g e.g. static/reusable invoices, subscriptions, and exchange accounts.

Unlike traditional Lightning invoices, the ones generated by this standard can be published without comporomising the security of the payment scheme, enabling long-sought features like public donation invoices.

The proposal also offers improved privacy over existing techniques by completely avoiding payment hash reuse.

Motivation

Design Overview

    s_1  s_2  s_3    SHARES OF ROOT SEED
                   
     |    |    |     
     └──┐ | ┌──┘       S = s_1 ^ s_2 ^ s_3
        V V V        
                   
          S          ROOT SEED
                   
        | | |        
     ┌──┘ | └──┐       r_i = DeriveChild(S, s_i, child_index_i)
     V    V    V     
                   
    r_1  r_2  r_3    CHILD PREIMAGES
                   
     |    |    |     
     |    |    |       p_i = SHA256(r_i)
     V    V    V     
                   
    p_1  p_2  p_3    CHILD PAYMENT HASHES

Specification

Notation

  • ^ denotes bit-wise XOR.
  • || denotes byte array concatenation.
  • be(x) returns a byte array containing the the big-endian serialization of the integer x.

AMP Feature Bits

Bits Name Description Context Dependencies
30/31 option_amp Atomic Multi-Path payments IN9 option_mpp

AMP Record Serialization

The ability to send AMP payments is enabled primarily by the addition of a new, required TLV record embedded in the final hop's onion payload:

  1. tlvs: tlv_payload
  2. types:
    1. type: 10 (amp_record)
    2. data:
      • [32*byte:root_share]
      • [32*byte:set_id]
      • [tu32:child_index]

Due to this design, only the sender and receiver need to be running AMP-compatible software. Unlike other proposals, this does not require a network-wide upgrade of the interior routing nodes before it can be deployed in end-user applications.

AMP HTLC Sets

An AMP HTLC set is defined as the set of all HTLCs carrying the same (payment_data.payment_secret, amp_record.set_id) pair.

This definition is intentionally designed as a super set of the defintion of HTLC sets for basic_mpp. Conceptually, an HTLC without an amp_record can be described using (payment_data.payment_secret, nil).

HTLC sets satisfying the form (_, nil) are classified as MPP HTLC sets and are subject to the basic_mpp requirements specified in BOLT 4. Otherwise, the HTLC should be treated as part of an AMP HTLC set and is subject to the requirements in this document.

Throughout this document, the term "HTLC set" is assumed to refer to an AMP HTLC set unless otherwise specified.

Child Preimage Derivation

Input:

  • The root seed S: a 32-byte array, freshly generated uniformly at random
  • A root share s: a 32-byte array, an N-of-N additive sharing of S
  • A child index c: 32-bit unsigned integer

Output:

  • A child preimage r: a 32-byte array
  • A child hash p: a 32-byte array, the SHA256 image of r

The algorithm DeriveChild(S, s, c) is defined as:

  • Compute r = SHA256(S || s || be(c)).
  • Compute p = SHA256(r).
  • Return (r, p).

The inputs to the SHA256 invocation creating the child preimage are justified as follows:

  • Committing to the root seed S enforces that the recipient must learn the reconstructed seed in order to derive the preimage for any of the HTLCs in a given HTLC set.
  • For a given root seed, commiting to the root share s ensures that each child preimage in the set is unique with high probabilty. By extension, the child hash of each HTLC in the set will also be unique, which prevents intermediaries from trivially correlating HTLCs in the same HTLC due to payment hash reuse.
  • If the child preimage depends only on (S, s), then payment hash reuse is still posssible across retries, i.e. when an HTLC for same amount gets sent along a different path. The inclusion of a child index c allows the sender can rerandomize an HTLC's payment hash without needing to further split the root share s and payment amount into additional sub-payments.

Should the derivation commit to the set_id? This would effectively remove any potential for payment hash reuse, even if the same S value is somehow shared between HTLC sets.

Sending AMP Record

A sender of amp_record:

  • MUST NOT include amp_record for any non-final node.
  • if the final node does not signal support for option_amp in the I or N feature bit contexts:
    • MUST NOT include amp_record for the final node.
  • otherwise:
    • MAY include amp_record for the final node.
    • if it does include an amp_record:
      • MUST also include a payment_data record.
      • if paying to an invoice:
        • MUST use the payment_secret provided in the invoice.
      • otherwise:
        • MUST generate a uniformly random payment_secret to be used for the HTLC set.
      • if paying to an invoice with non-zero amount:
        • MUST set payment_data.total_msat equal to amount.
      • otherwise:
        • MUST set payment_data.total_msat equal to the amount it wishes to pay.
      • MUST generate a unique set_id to identify the HTLC set.
      • Each HTLC in the HTLC set:
        • MUST use the same payment_data.payment_secret.
        • MUST use the same payment_data.total_msat.
        • MUST use the same amp_record.set_id.
      • MUST generate a uniformly random root seed S to be used for the HTLC set.
      • MUST generate a random amp_record.child_index.
      • For all unfailed HTLCs in the HTLC set:
        • Let s_i be the amp_record.root_share of the i-th HTLC.
        • Let c_i be the amp_record.child_index of the i-th HTLC.
        • Let (_, p_i) = DeriveChild(S, s_i, c_i)
        • MUST set the payment hash of i-th HTLC to p_i.
        • MUST ensure that the s_1 ^ ... ^ s_n = S.
        • MUST ensure the sum of the HTLC amounts equals payment_data.total_msat.

Handling Failed HTLCs

If the sender detects that an HTLC in an AMP HTLC set fails:

  • MAY abort the payment.
  • otherwise, if the sender wants to retry the HTLC along a different route:
    • MUST re-randomize the amp_record.child_index.
  • otherwise, when sender wants to split the failed HTLC into two or more sub-HTLCs.
    • MUST generate the new HTLCs such that they satisfy the sending requiements above.

The most difficult task in splitting a failed HTLC is with regards to ensuring the root share S is not ultimately invalidated. This can be done using the algorithm presented in Recursive Splitting of Root Shares.

Recursive Splitting of Root Shares

There are many possible strategies in which the sender may choose to satisfy the requirement that, for a given S, the amp_record.root_share values in the HTLC set always XOR to S. Implementers are of course free to choose shares as they see fit, so long as S reconstructs properly and, most importantly, S cannot be recovered knowing only a subset of the HTLC set.

Several alternative algorithms were considered, however, the one presented as chosen as the recommended strategy due to the following useful properties:

  • The final number of HTLCs does not need to be known a priori, nor does it ever need to be explicitly committed to by the sender. This permits the sender to adaptively discover the number of required HTLCs for the payment.
  • There is no "distinguished" HTLC, i.e. an HTLC that cannot be further split or must be sent in a paritcular order.
  • Splitting an HTLC does not require shared state amongst the other HTLCs, which greatly simplifies the resulting implementation.

Implementers should be mindful of these contraints when selecting alternative strategies, and analyze the tradeoffs in terms complexity as well as potential restrictions placed on the sender's ability to adapatively send AMP HTLCs.

Input:

  • A root share s: a 32-byte array

Output:

  • A root share l: a 32-byte array, satisfying l ^ r = s
  • A root share r: a 32-byte array, satisfying l ^ r = s

The algorithm SplitShare(s) is defined as:

  • Generate l uniformly at random.
  • Compute r = l ^ s.
  • Return (l, r).

Assume that n active HTLCs exist in a given AMP HTLC set, and that each HTLC carries an amp_data.root_share value of s_i.

The root seed of the HTLC set is computed as:

    s_1 ^ ... ^ s_n = S                                                     (1)

WLOG, assume that HTLC carrying s_n fails. The sender splits the share as:

    (l, r) = SplitShare(s_n)

and replaces the HTLC containing s_n with two new HTLCs containing l and r as their amp_record.root_share.

The root seed for the new HTLC set (now of cardinatlity n+1) is computed as:

    s_1 ^ ... ^ s_n-1 ^ l ^ r  = s_1 ^ ... ^ s_n-1 ^ (l ^ r)
                               = s_1 ^ ... ^ s_n-1 ^ (l ^ (l ^ s_n))
                               = s_1 ^ ... ^ s_n-1 ^ s_n
                               = S                                      by (1)

It follows that SplitShare can also be applied recursively to its own outputs without invalidating S. This allows the sender to split any of the HTLCs in the HTLC set as necessary in order to satisfy any liquidity constraints in the network.

For the base case we have simply that s_1 = S, meaning the root seed is sent directly when the HTLC set consists of only one HTLC.

Receiving AMP Record

A receiver of amp_record:

  • MUST fail the HTLC with invalid_onion_payload if it is not the final node.
  • MUST fail the HTLC with invalid_onion_payload if the payment_data record is not also present.
  • if an invoice is known containining payment_secret equal to payment_data.payment_secret:
    • if the invoice does not advertise option_amp:
      • MUST fail the HTLC with incorrect_payment_details.
  • otherwise:
    • MAY create and store an invoice that:
      • has payment_secret equal to payment_data.payment_secret, and
      • has amount equal to payment_data.total_msat, and
      • advertises support for option_amp and all transitive feature dependencies.
  • Let "the HTLC set" be defined as all known, unfailed HTLCs containing the same payment_data.payment_secret and amp_record.set_id values.
  • MUST fail the HTLC if payment_data.total_msat is not the same for all HTLCs in the HTLC set.
  • MUST add the HTLC to the HTLC set.
  • Let total be the sum of the HTLCs in the HTLC set.
  • if total > payment_data.total_msat:
    • MUST fail the HTLC with incorrect_payment_detials.
  • otherwise, if total = payment_data.total_msat:
    • For each HTLC in the HTLC set:
      • Let s_i be the i-th HTLC's amp_record.root_share.
    • Compute the root seed S = s_1 ^ ... ^ s_n.
    • For each HTLC in the HTLC set:
      • Let c_i be the i-th HTLC's amp_record.child_index.
      • Compute (r_i, p_i) = DeriveChild(S, s_i, c_i).
    • if any p_i does not match the i-th HTLC's payment hash:
      • MUST fail the HTLC set with incorrect_payment_details.
    • otherwise:
      • MAY fulfill the i-th HTLC in the HTLC set using r_i.
      • MUST fulfill the entire HTLC set if it fulfills any HTLC in the HTLC set.
  • otherwise, when total < payment_data.total_msat:
    • SHOULD wait for more HTLCs in the set to arrive.
    • MUST fail the HTLC set with mpp_timeout after some reasonable timeout.
      • SHOULD wait for at least 60 seconds after the initial HTLC.

Applications

Spontaneous Payments

Reusable Invoices

Public Invoices

Multi-Path Probing

Appendix

Test Vectors

Reference Code

Footnotes

Acknowledgements