commit cdb72509a7a1db6bdc8305582ffe917c3f59d2a7
parent 367d30d6c0585e9e270ad312c5f79105d3d77dc5
Author: SomberNight <somber.night@protonmail.com>
Date: Tue, 3 Mar 2020 02:12:42 +0100
lnrouter: change edge cost estimate (distance metric)
Old estimate was heavily biased towards simply minimising CLTV sum.
(fees had a too low weight; typically they were ~noise)
Now also take payment_amount into account.
Diffstat:
2 files changed, 16 insertions(+), 10 deletions(-)
diff --git a/electrum/lnrouter.py b/electrum/lnrouter.py
@@ -131,7 +131,7 @@ class LNPathFinder(Logger):
def _edge_cost(self, short_channel_id: bytes, start_node: bytes, end_node: bytes,
payment_amt_msat: int, ignore_costs=False, is_mine=False, *,
my_channels: Dict[ShortChannelID, 'Channel'] = None) -> Tuple[float, int]:
- """Heuristic cost of going through a channel.
+ """Heuristic cost (distance metric) of going through a channel.
Returns (heuristic_cost, fee_for_edge_msat).
"""
channel_info = self.channel_db.get_channel_info(short_channel_id, my_channels=my_channels)
@@ -157,12 +157,20 @@ class LNPathFinder(Logger):
return float('inf'), 0 # payment amount too large
if not route_edge.is_sane_to_use(payment_amt_msat):
return float('inf'), 0 # thanks but no thanks
- fee_msat = route_edge.fee_for_edge(payment_amt_msat) if not ignore_costs else 0
- # TODO revise
- # paying 10 more satoshis ~ waiting one more block
- fee_cost = fee_msat / 1000 / 10
- cltv_cost = route_edge.cltv_expiry_delta if not ignore_costs else 0
- return cltv_cost + fee_cost + 1, fee_msat
+
+ # Distance metric notes: # TODO constants are ad-hoc
+ # ( somewhat based on https://github.com/lightningnetwork/lnd/pull/1358 )
+ # - Edges have a base cost. (more edges -> less likely none will fail)
+ # - The larger the payment amount, and the longer the CLTV,
+ # the more irritating it is if the HTLC gets stuck.
+ # - Paying lower fees is better. :)
+ base_cost = 500 # one more edge ~ paying 500 msat more fees
+ if ignore_costs:
+ return base_cost, 0
+ fee_msat = route_edge.fee_for_edge(payment_amt_msat)
+ cltv_cost = route_edge.cltv_expiry_delta * payment_amt_msat * 15 / 1_000_000_000
+ overall_cost = base_cost + fee_msat + cltv_cost
+ return overall_cost, fee_msat
@profiler
def find_path_for_payment(self, nodeA: bytes, nodeB: bytes,
diff --git a/electrum/tests/test_lnrouter.py b/electrum/tests/test_lnrouter.py
@@ -96,9 +96,7 @@ class Test_LNRouter(TestCaseForTestnet):
cdb.add_channel_update({'short_channel_id': bfh('0000000000000006'), 'message_flags': b'\x00', 'channel_flags': b'\x01', 'cltv_expiry_delta': o(10), 'htlc_minimum_msat': o(250), 'fee_base_msat': o(100), 'fee_proportional_millionths': o(150), 'chain_hash': BitcoinTestnet.rev_genesis_bytes(), 'timestamp': b'\x00\x00\x00\x00'})
path = path_finder.find_path_for_payment(b'\x02aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa', b'\x02eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee', 100000)
self.assertEqual([(b'\x02bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb', b'\x00\x00\x00\x00\x00\x00\x00\x03'),
- (b'\x02cccccccccccccccccccccccccccccccc', b'\x00\x00\x00\x00\x00\x00\x00\x01'),
- (b'\x02dddddddddddddddddddddddddddddddd', b'\x00\x00\x00\x00\x00\x00\x00\x04'),
- (b'\x02eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee', b'\x00\x00\x00\x00\x00\x00\x00\x05')
+ (b'\x02eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeee', b'\x00\x00\x00\x00\x00\x00\x00\x02'),
], path)
start_node = b'\x02bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb'
route = path_finder.create_route_from_path(path, start_node)
