2

From the source code of LND, payments are split in half and retried if no path for the full amount is found:

func (p *paymentSession) RequestRoute(maxAmt, feeLimit lnwire.MilliSatoshi,
    activeShards, height uint32) (*route.Route, error) {

        ...
        // This is where the magic happens. If we can't find a
        // route, try it for half the amount.
        maxAmt /= 2
        ...

For normal payments, I understand the algorithm will split the payment until it fits a path, send it, and update the weights in the graph to avoid reusing the same path. Then we can do the same for the remaining amount. This is confirmed in this answer.

However, for MPP, it seems there is a set of parts per round, which are sent concurrently. If this is the case, how does MPP define the amount of each part before sending the parts?

1 Answer 1

3

This is not specified by the protocol. Implementations can do what ever pleases them. For example I believe many would use a more or less uniform split into parts given the amount and the number of parts they wish to send.

This form of splitting is discussed in this research paper and was shown to be not optimal. The previous link also provides the optimal solution by recognizing that payments should be understood as minimum cost flow problems. However even dissecting the resulting payment flow into shards is arbitrary and not well defined. The typical solution is to use a chain of cascading shortest paths as done in this function.

Newer research is in progress that uses augmenting paths which are saturated such that the probability of the amount for a part reaches a certain threshold.

Disclaimer: I am the main contributor of all the links provided

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.