Kutafuta njia na kufikisha malipo

Somo lililopita Alice alisoma ramani. Sasa lazima achague njia. Katika Lightning mlipaji ndiye anachagua njia yote, si mtandao, na lazima ifanye kazi bila kujua salio la mtu yeyote.

Tatizo la njia fupi zaidi, lenye mzunguko

Fikiria kila upande wa chaneli kama barabara yenye ushuru, yaani ada ya upitishaji. Kutafuta njia nafuu zaidi ni tatizo la zamani la njia fupi zaidi, na algorithimu ya Dijkstra inalitatua: kila mara ongeza njia nafuu zaidi uliyopata hadi ufike unakoenda.

Mzunguko: ramani inaonyesha uwezo, si ukwasi. Njia nafuu zaidi kwenye karatasi inaweza kushindwa kwa sababu chaneli haina salio upande unaohitajika.

Andika kitafuta-njia

Msimbo wa kuanzia unageuza ramani ya Alice kuwa orodha ya majirani pamoja na sera zao za ada. Jaza find_route kwa Dijkstra, ukitumia heapq:

⚡Tafuta njia yenye ada ndogo

Python

NodiAlice · LNDBob · c-lightningChan · c-lightningDina · LNDHakuna nodi

import heapq from jifunze_lab import lnd def fee_msat(policy: dict, amount_msat: int) -> int: base = int(policy.get("fee_base_msat", 0)) rate = int(policy.get("fee_rate_milli_msat", 0)) return base + amount_msat * rate // 1_000_000 def edges_from(graph: dict) -> dict: """pubkey -> list of (neighbour pubkey, policy for sending from pubkey).""" out: dict = {} for e in graph["edges"]: for a, b, pol in ((e["node1_pub"], e["node2_pub"], e.get("node1_policy")), (e["node2_pub"], e["node1_pub"], e.get("node2_policy"))): if pol and not pol.get("disabled"): out.setdefault(a, []).append((b, pol)) return out def find_route(graph: dict, source: str, target: str, amount_msat: int) -> list[str]: """Return the list of pubkeys from source to target with the lowest total fee.""" # TODO: Dijkstra. Start with heap = [(0, source, [source])] and pop the cheapest path each time. return [] alice = lnd("alice") graph = alice.graph() dina = lnd("dina").pubkey names = {n["pub_key"]: n.get("alias") for n in graph["nodes"]} route = find_route(graph, alice.pubkey, dina, 10_000_000) print(" -> ".join(names.get(p, p[:8]) for p in route))

▶ EndeshaKaguaAnza somo upyaRudisha msimbo wa kuanzia

Mazoezi haya yanahitaji kompyuta yenye maabara ikiendeshwa. Unaweza kusoma somo kwenye simu.

Kwenye maabara kuna njia moja tu, Alice → Bob → Chan → Dina, lakini kitendakazi chako kinajaribiwa kuhakikisha kila hatua inafuata chaneli halisi.

Nodi halisi zinavyofanya vizuri zaidi

• Gharama ya uwezekano. Mbali na ada, nodi hupima uwezekano wa kila chaneli kuwa na salio la kutosha. Chaneli kubwa ukilinganisha na kiasi zinaonekana salama zaidi.
• Mission control. Jaribio likishindwa, hitilafu inasema ni chaneli ipi ilishindwa. Nodi inakumbuka na kuiepuka kwa muda, kisha inajaribu tena. (Utaitumia katika somo la 16.)
• Malipo ya sehemu nyingi (MPP). Malipo makubwa yanaweza kugawanywa katika sehemu ndogo kadhaa kupitia njia tofauti, kila moja ikiwa na uwezekano mkubwa wa kutosha. Dina anaachia preimage tu baada ya kila sehemu kufika.