ElementsProject / ElementsProject/lightning
When htlc min breaks renepay
- Dominant language
- C
- Stars
- 3.1k
- Forks
- 1k
- Avg merge
- 4d 10h
- Merged PRs (30d)
- 13
Description
I came up with the following test case for `renepay`:
```python
def test_htlc_minmax(node_factory):
"""
Topology:
1----2----4
| |
3----5----6
Try sending a payment from 1 to 6, there are two routes
1->2->4->6 and 1->3->5->6.
The route 1->2->4->6 contains a channel with
htlcmin=htlcmax=X but 0 routing fees, the other path has high routing fees.
The optimal solution sends n*X along 1->2->4->6 and the rest through
1->3->5->6.
"""
opts = [
{"disable-mpp": None, "fee-base": 0, "fee-per-satoshi": 0},#1
{"disable-mpp": None, "fee-base": 0, "fee-per-satoshi": 0},#2
{"disable-mpp": None, "fee-base": 1000, "fee-per-satoshi": 1000},#3
{"disable-mpp": None, "fee-base": 0, "fee-per-satoshi": 0},#4
{"disable-mpp": None, "fee-base": 1000, "fee-per-satoshi": 1000},#5
{"disable-mpp": None, "fee-base": 0, "fee-per-satoshi": 0},#6
]
l1, l2, l3, l4, l5, l6 = node_factory.get_nodes(6, opts=opts)
channels = start_channels(
[
(l1, l2, 1000000),
(l2, l4, 1000000),
(l4, l6, 1000000),
(l1, l3, 1000000),
(l3, l5, 1000000),
(l5, l6, 1000000),
]
)
htlc_max = 100100000
htlc_min = 99900000
l4.rpc.setchannel(l6.info["id"], htlcmin=htlc_min, htlcmax=htlc_max)
l6.rpc.setchannel(l4.info["id"], htlcmin=htlc_min, htlcmax=htlc_max)
scid = l4.get_channel_scid(l6)
wait_for(
lambda: [c["htlc_minimum_msat"] for c in l1.rpc.listchannels(scid)["channels"]]
== [htlc_min, htlc_min]
)
wait_for(
lambda: [c["htlc_maximum_msat"] for c in l1.rpc.listchannels(scid)["channels"]]
== [htlc_max, htlc_max]
)
# 200000sat (circa) go through 1->2->4->6
# 50000sat (circa) go through 1->3->5->6
amt = "250000sat"
# in the worst case we send 2*99900sat through 1->2->4->6 at 0 fees and the
# rest 50200sat through 1->3->5->6, paying in total 102451msat in fees.
worst_case = "250102451msat"
inv = l6.rpc.invoice(amt, "inv", "description")
response = l1.rpc.call("renepay", {"invstring": inv["bolt11"]})
l1.wait_for_htlcs()
invoice = only_one(l6.rpc.listinvoices("inv")["invoices"])
assert invoice["amount_received_msat"] >= Millisatoshi(amt)
# This test would fail if all 250000sat go through 1->3->5->6 paying
# 502251msat in fees or more.
assert response["amount_sent_msat"] <= Millisatoshi(worst_case)
```
The idea is to break `renepay`'s optimality by exploiting a constraint the Min Cost Flow (MCF) algorithm cannot handle.
That is, `htlc_maximum` can be taken into account either by limiting the flow capacity or the arcs, or when dissecting flows into routes. But `htlc_minimum` has, at least to my knowledge, no way to be set as a constrain in the solver.
The `htlc_minimum` constraint must be taken into account after MCF computation.
Currently in this situation `renepay` will determine the best route is `1->2->4->6` and since there is an `htlc_maximum` constraint there, it will construct 3 different payment routes with `100000sat`, `100000sat` and `50000sat` using the same path.
Before `sendpay` is called, the plugin will determine that `50000sat` is smaller than `htlc_minimum` for channel `4->6` and that
channel will be flagged as disabled, then MCF will be called again and then the entire payment will be sent through
`1->3->5->6`, when it would have sufficed to send `50000sat` through `1->3->5->6`.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.