commit f8f365f1eaee1b91755ee1682da07a28c588747b
parent a23aac76d3f5bdabae5e7379a7e1aba6f172670f
Author: SomberNight <somber.night@protonmail.com>
Date: Mon, 16 Apr 2018 18:13:44 +0200
naive route finding
Diffstat:
2 files changed, 103 insertions(+), 4 deletions(-)
diff --git a/lib/lnbase.py b/lib/lnbase.py
@@ -12,7 +12,7 @@ import queue
import traceback
import itertools
import json
-from collections import OrderedDict
+from collections import OrderedDict, defaultdict
import asyncio
import sys
import os
@@ -30,7 +30,7 @@ from .bitcoin import (public_key_from_private_key, ser_to_point, point_to_ser,
from . import bitcoin
from . import constants
from . import transaction
-from .util import PrintError, bh2u, print_error, bfh
+from .util import PrintError, bh2u, print_error, bfh, profiler
from .transaction import opcodes, Transaction
# hardcoded nodes
@@ -341,6 +341,7 @@ class Peer(PrintError):
self.channels = {} # received channel announcements
self.channel_u_origin = {}
self.channel_u_final = {}
+ self.graph_of_payment_channels = defaultdict(set) # node -> short_channel_id
def diagnostic_name(self):
return self.host
@@ -509,7 +510,7 @@ class Peer(PrintError):
flags = int.from_bytes(payload['flags'], byteorder="big")
direction = bool(flags & 1)
short_channel_id = payload['short_channel_id']
- if direction:
+ if direction == 0:
self.channel_u_origin[short_channel_id] = payload
else:
self.channel_u_final[short_channel_id] = payload
@@ -519,10 +520,86 @@ class Peer(PrintError):
short_channel_id = payload['short_channel_id']
self.print_error('channel announcement', binascii.hexlify(short_channel_id))
self.channels[short_channel_id] = payload
+ self.add_channel_to_graph(payload)
+
+ def add_channel_to_graph(self, payload):
+ node1 = payload['node_id_1']
+ node2 = payload['node_id_2']
+ channel_id = payload['short_channel_id']
+ self.graph_of_payment_channels[node1].add(channel_id)
+ self.graph_of_payment_channels[node2].add(channel_id)
#def open_channel(self, funding_sat, push_msat):
# self.send_message(gen_msg('open_channel', funding_satoshis=funding_sat, push_msat=push_msat))
+ @profiler
+ def find_route_for_payment(self, from_node_id, to_node_id, amount_msat=None):
+ """Return a route between from_node_id and to_node_id.
+
+ Returns a list of (node_id, short_channel_id) representing a path.
+ To get from node ret[n][0] to ret[n+1][0], use channel ret[n][1]
+ """
+ # TODO find multiple paths??
+
+ def edge_cost(short_channel_id, direction):
+ """Heuristic cost of going through a channel.
+ direction: 0 or 1. --- 0 means node_id_1 -> node_id_2
+ """
+ channel_updates = self.channel_u_origin if direction == 0 else self.channel_u_final
+ try:
+ cltv_expiry_delta = channel_updates[short_channel_id]['cltv_expiry_delta']
+ htlc_minimum_msat = channel_updates[short_channel_id]['htlc_minimum_msat']
+ fee_base_msat = channel_updates[short_channel_id]['fee_base_msat']
+ fee_proportional_millionths = channel_updates[short_channel_id]['fee_proportional_millionths']
+ except KeyError:
+ return float('inf') # can't use this channel
+ if amount_msat is not None and amount_msat < htlc_minimum_msat:
+ return float('inf') # can't use this channel
+ amt = amount_msat or 50000 * 1000 # guess for typical payment amount
+ fee_msat = fee_base_msat + amt * fee_proportional_millionths / 1000000
+ # TODO revise
+ # paying 10 more satoshis ~ waiting one more block
+ fee_cost = fee_msat / 1000 / 10
+ cltv_cost = cltv_expiry_delta
+ return cltv_cost + fee_cost + 1
+
+ # run Dijkstra
+ distance_from_start = defaultdict(lambda: float('inf'))
+ distance_from_start[from_node_id] = 0
+ prev_node = {}
+ nodes_to_explore = queue.PriorityQueue()
+ nodes_to_explore.put((0, from_node_id))
+
+ while nodes_to_explore.qsize() > 0:
+ dist_to_cur_node, cur_node = nodes_to_explore.get()
+ if cur_node == to_node_id:
+ break
+ if dist_to_cur_node != distance_from_start[cur_node]:
+ # queue.PriorityQueue does not implement decrease_priority,
+ # so instead of decreasing priorities, we add items again into the queue.
+ # so there are duplicates in the queue, that we discard now:
+ continue
+ for edge in self.graph_of_payment_channels[cur_node]:
+ node1 = self.channels[edge]['node_id_1']
+ node2 = self.channels[edge]['node_id_2']
+ neighbour, direction = (node1, 1) if node1 != cur_node else (node2, 0)
+ alt_dist_to_neighbour = distance_from_start[cur_node] + edge_cost(edge, direction)
+ if alt_dist_to_neighbour < distance_from_start[neighbour]:
+ distance_from_start[neighbour] = alt_dist_to_neighbour
+ prev_node[neighbour] = cur_node, edge
+ nodes_to_explore.put((alt_dist_to_neighbour, neighbour))
+ else:
+ return None # no path found
+
+ # backtrack from end to start
+ cur_node = to_node_id
+ path = [(cur_node, None)]
+ while cur_node != from_node_id:
+ cur_node, edge_taken = prev_node[cur_node]
+ path += [(cur_node, edge_taken)]
+ path.reverse()
+ return path
+
@aiosafe
async def main_loop(self):
self.reader, self.writer = await asyncio.open_connection(self.host, self.port)
diff --git a/lib/tests/test_lnbase.py b/lib/tests/test_lnbase.py
@@ -1,6 +1,6 @@
import json
import unittest
-from lib.util import bh2u
+from lib.util import bh2u, bfh
from lib.lnbase import make_commitment, get_obscured_ctn, Peer, make_offered_htlc
from lib.transaction import Transaction
from lib import bitcoin
@@ -135,3 +135,25 @@ class Test_LNBase(unittest.TestCase):
def test_message_node_announcement(self):
message = b'\x01\x01\xd5\xf9X\xed\x95=b\xd8\x86\x1fT\xcf\xdb\x1eV\xe7\xf9xd>B\xa8\x8d\xc1b\x81\xf7\xc4{Z\x08\x81\x10H\x13\xfb^\x1e)A\xd4\xb0m\x92x\x9d\x19!\xe3\x8a\xf0\xc4\x0fq\x0b\xd7\xc7\x7f\\$\xe3_\xe4R\x00\x00Z\xd3G`\x03\xfd\n\xeb\xde\x87\x13\xe9\xc3\x11\xf2$h\xd3\xd0RNx\x8b\x1e\xf5\x7fL\xdaA\xbf[Z#\x00\xfc\\\xd6\xcc\x00\x00ruphware++\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x07\x01V=C\xb7&\x07'
peer.process_message(message)
+
+ def test_find_route_for_payment(self):
+ p = Peer('', 0, 'a')
+ p.on_channel_announcement({'node_id_1': 'b', 'node_id_2': 'c', 'short_channel_id': bfh('0000000000000001')})
+ p.on_channel_announcement({'node_id_1': 'b', 'node_id_2': 'e', 'short_channel_id': bfh('0000000000000002')})
+ p.on_channel_announcement({'node_id_1': 'b', 'node_id_2': 'a', 'short_channel_id': bfh('0000000000000003')})
+ p.on_channel_announcement({'node_id_1': 'd', 'node_id_2': 'c', 'short_channel_id': bfh('0000000000000004')})
+ p.on_channel_announcement({'node_id_1': 'e', 'node_id_2': 'd', 'short_channel_id': bfh('0000000000000005')})
+ p.on_channel_announcement({'node_id_1': 'a', 'node_id_2': 'd', 'short_channel_id': bfh('0000000000000006')})
+ p.on_channel_update({'short_channel_id': bfh('0000000000000001'), 'flags': b'0', 'cltv_expiry_delta': 10, 'htlc_minimum_msat': 250, 'fee_base_msat': 100, 'fee_proportional_millionths': 150})
+ p.on_channel_update({'short_channel_id': bfh('0000000000000001'), 'flags': b'1', 'cltv_expiry_delta': 10, 'htlc_minimum_msat': 250, 'fee_base_msat': 100, 'fee_proportional_millionths': 150})
+ p.on_channel_update({'short_channel_id': bfh('0000000000000002'), 'flags': b'0', 'cltv_expiry_delta': 99, 'htlc_minimum_msat': 250, 'fee_base_msat': 100, 'fee_proportional_millionths': 150})
+ p.on_channel_update({'short_channel_id': bfh('0000000000000002'), 'flags': b'1', 'cltv_expiry_delta': 10, 'htlc_minimum_msat': 250, 'fee_base_msat': 100, 'fee_proportional_millionths': 150})
+ p.on_channel_update({'short_channel_id': bfh('0000000000000003'), 'flags': b'0', 'cltv_expiry_delta': 10, 'htlc_minimum_msat': 250, 'fee_base_msat': 100, 'fee_proportional_millionths': 150})
+ p.on_channel_update({'short_channel_id': bfh('0000000000000003'), 'flags': b'1', 'cltv_expiry_delta': 10, 'htlc_minimum_msat': 250, 'fee_base_msat': 100, 'fee_proportional_millionths': 150})
+ p.on_channel_update({'short_channel_id': bfh('0000000000000004'), 'flags': b'0', 'cltv_expiry_delta': 10, 'htlc_minimum_msat': 250, 'fee_base_msat': 100, 'fee_proportional_millionths': 150})
+ p.on_channel_update({'short_channel_id': bfh('0000000000000004'), 'flags': b'1', 'cltv_expiry_delta': 10, 'htlc_minimum_msat': 250, 'fee_base_msat': 100, 'fee_proportional_millionths': 150})
+ p.on_channel_update({'short_channel_id': bfh('0000000000000005'), 'flags': b'0', 'cltv_expiry_delta': 10, 'htlc_minimum_msat': 250, 'fee_base_msat': 100, 'fee_proportional_millionths': 150})
+ p.on_channel_update({'short_channel_id': bfh('0000000000000005'), 'flags': b'1', 'cltv_expiry_delta': 10, 'htlc_minimum_msat': 250, 'fee_base_msat': 100, 'fee_proportional_millionths': 999})
+ p.on_channel_update({'short_channel_id': bfh('0000000000000006'), 'flags': b'0', 'cltv_expiry_delta': 10, 'htlc_minimum_msat': 250, 'fee_base_msat': 100, 'fee_proportional_millionths': 99999999})
+ p.on_channel_update({'short_channel_id': bfh('0000000000000006'), 'flags': b'1', 'cltv_expiry_delta': 10, 'htlc_minimum_msat': 250, 'fee_base_msat': 100, 'fee_proportional_millionths': 150})
+ print(p.find_route_for_payment('a', 'e', 100000))
