getroutes: allocating more than spendable_msat

[daywalker90]

On regtest with a few nodes and channels i call getroutes with a large amount and it will return paths that immediately fail sendpay with Capacity exceeded. I added up the amounts+fees of the first, local channel and compared them with the spendable_msat value.

Some channels are over-allocated by getroutes:

• spendable_msat: 384718000
• total amount_msat allocated by getroutes without fee: 384718000
  • with fees: 384721847

I expect getroutes to not go over spendable_msat or even be below that since iirc this value does not account for some things and the real value is even lower?

Could be related to #7550

[rustyrussell]

OK, this is hard to reproduce, since I can't get getroutes() to even try to jam that much down a channel (so close to capacity).

Got a setup I can copy?

[daywalker90]

def test_mpp_pay2(node_factory, bitcoind):
    import logging

    logger = logging.getLogger(__name__)
    l1, l2, l3 = node_factory.get_nodes(
        3,
        opts=[
            {},
            {},
            {},
        ],
    )
    l1.fundwallet(10_000_000)
    l2.fundwallet(10_000_000)
    l1.rpc.fundchannel(
        l2.info["id"] + "@localhost:" + str(l2.port), 100_000, mindepth=1
    )
    l2.rpc.fundchannel(
        l3.info["id"] + "@localhost:" + str(l3.port), 100_000, mindepth=1
    )
    bitcoind.generate_block(1)
    sync_blockheight(bitcoind, [l1, l2])
    l1.rpc.fundchannel(
        l2.info["id"] + "@localhost:" + str(l2.port), 100_000, mindepth=1
    )
    l2.rpc.fundchannel(
        l3.info["id"] + "@localhost:" + str(l3.port), 100_000, mindepth=1
    )
    bitcoind.generate_block(1)
    sync_blockheight(bitcoind, [l1, l2])
    l1.rpc.fundchannel(
        l2.info["id"] + "@localhost:" + str(l2.port), 200_000, mindepth=1
    )
    l2.rpc.fundchannel(
        l3.info["id"] + "@localhost:" + str(l3.port), 200_000, mindepth=1
    )
    bitcoind.generate_block(1)
    sync_blockheight(bitcoind, [l1, l2])
    l1.rpc.fundchannel(
        l2.info["id"] + "@localhost:" + str(l2.port), 300_000, mindepth=1
    )
    l2.rpc.fundchannel(
        l3.info["id"] + "@localhost:" + str(l3.port), 300_000, mindepth=1
    )
    bitcoind.generate_block(1)
    sync_blockheight(bitcoind, [l1, l2])
    l1.rpc.fundchannel(
        l2.info["id"] + "@localhost:" + str(l2.port), 400_000, mindepth=1
    )
    l2.rpc.fundchannel(
        l3.info["id"] + "@localhost:" + str(l3.port), 400_000, mindepth=1
    )
    bitcoind.generate_block(6)
    sync_blockheight(bitcoind, [l1, l2, l3])

    wait_for(lambda: len(l1.rpc.listchannels()["channels"]) == 20)

    routes = l1.rpc.call(
        "getroutes",
        {
            "source": l1.info["id"],
            "destination": l3.info["id"],
            "amount_msat": 800_000_000,
            "layers": ["auto.localchans", "auto.sourcefree"],
            "maxfee_msat": 50_000_000,
            "finalcltv": 10,
        },
    )
    channels = l1.rpc.call("listpeerchannels")
    logger.info(routes)
    logger.info(channels)

Atleast one channel gets overallocated in this setup for me.

[rustyrussell]

Thanks, IOU a beer. I'll take a look...

[rustyrussell]

Seems to work for me:

+def test_mpp_pay2(node_factory, bitcoind):
+    l1, l2, l3 = node_factory.get_nodes(3)
+    l1.fundwallet(10_000_000)
+    l2.fundwallet(10_000_000)
+    l1.rpc.connect(l2.info['id'], 'localhost', port=l2.port)
+    l2.rpc.connect(l3.info['id'], 'localhost', port=l3.port)
+
+    capacities = (100_000, 100_000, 200_000, 300_000, 400_000)
+    for capacity in capacities:
+        l1.rpc.fundchannel(l2.info["id"], capacity, mindepth=1)
+        l2.rpc.fundchannel(l3.info["id"], capacity, mindepth=1)
+
+        bitcoind.generate_block(1, wait_for_mempool=2)
+        sync_blockheight(bitcoind, [l1, l2])
+
+    bitcoind.generate_block(5)
+    wait_for(lambda: len(l1.rpc.listchannels()["channels"]) == 2 * 2 * len(capacities))
+
+    routes = l1.rpc.getroutes(
+        source=l1.info["id"],
+        destination=l3.info["id"],
+        amount_msat=800_000_000,
+        layers=["auto.localchans", "auto.sourcefree"],
+        maxfee_msat=50_000_000,
+        final_cltv=10,
+    )
+
+    # Don't exceed spendable_msat
+    maxes = {}
+    for chan in l1.rpc.listpeerchannels()['channels']:
+        maxes["{}/{}".format(chan['short_channel_id'], chan['direction'])] = chan['spendable_msat']
+
+    for r in routes['routes']:
+        for p in r['path']:
+            scidd = "{}/{}".format(p['short_channel_id'], p['direction'])
+            if scidd in maxes:
+                assert p['amount_msat'] <= maxes[scidd]

[daywalker90]

Sorry, i wasn't precise enough: I meant that if you add up all the amounts+fee that getroutes returns per local channel, they might add up to more than spendable_msat. Maybe this will make it more clear:

def test_mpp_pay2(node_factory, bitcoind):
    l1, l2, l3 = node_factory.get_nodes(3)
    l1.fundwallet(10_000_000)
    l2.fundwallet(10_000_000)
    l1.rpc.connect(l2.info["id"], "localhost", port=l2.port)
    l2.rpc.connect(l3.info["id"], "localhost", port=l3.port)

    capacities = (100_000, 100_000, 200_000, 300_000, 400_000)
    for capacity in capacities:
        l1.rpc.fundchannel(l2.info["id"], capacity, mindepth=1)
        l2.rpc.fundchannel(l3.info["id"], capacity, mindepth=1)

        bitcoind.generate_block(1, wait_for_mempool=2)
        sync_blockheight(bitcoind, [l1, l2])

    bitcoind.generate_block(5)
    wait_for(lambda: len(l1.rpc.listchannels()["channels"]) == 2 * 2 * len(capacities))

    routes = l1.rpc.getroutes(
        source=l1.info["id"],
        destination=l3.info["id"],
        amount_msat=800_000_000,
        layers=["auto.localchans", "auto.sourcefree"],
        maxfee_msat=50_000_000,
        finalcltv=10,
    )

    # Don't exceed spendable_msat
    maxes = {}
    for chan in l1.rpc.listpeerchannels()["channels"]:
        maxes["{}/{}".format(chan["short_channel_id"], chan["direction"])] = chan[
            "spendable_msat"
        ]

    path_maxes = {}
    for r in routes["routes"]:
        key = "{}/{}".format(
            r["path"][0]["short_channel_id"], r["path"][0]["direction"]
        )
        path_maxes[key] = path_maxes.get(key, 0) + r["path"][0]["amount_msat"]

    for scidd in maxes.keys():
        if scidd in path_maxes:
            assert maxes[scidd] >= path_maxes[scidd]

This returns assert 285718000 >= 285720859 for me

[Lagrang3]

This is my fault!

There is a sat precision in the MCF capacities to avoid large numbers.
The problem seems to derive from there, maybe we are letting the capacity constraint be
the ceil(msat/1000) instead of floor(msat/1000).

In the future I would like to set the smallest unit according to the payment amount...

UPD: fixed in renepay 5a68289, but it is not the same thing in askrene.