Today between 10:00-10:30 am at TABConf (npub17yq…5269) , learn about our new research on Lightning Network pathfinding strategies from my great student npub1yavvpwjc3w4yzlh33zxxaan2y23us9gkcrgrw903nm0s3t4wqpss3pdqdm (npub1yav…dqdm) Saraswathi https://github.com/orgs/TABConf/projects/4?pane=issue&itemId=77244631&issue=TABConf%7C6.tabconf.com%7C109
- We present a detailed breakdown of the underlying cost functions and constraints used by pathfinding algorithms of the different LN node implementations.
- Surprisingly, we observe that the pathfinding problems that most LN node implementations attempt to solve are NP-complete, and cannot be guaranteed to be optimally solved by the variants of Dijkstra’s algorithm currently deployed in production.
- Through comparative analysis and simulations, we evaluate efficacy of different pathfinding strategies across metrics such as success rate, fees, path length, and timelock.
We think that this study provides new insights for how pathfinding within the Lightning Network can further be improved. While beyond the scope of our study, the findings are also relevant for multi-part payments.
Link to paper: https://arxiv.org/pdf/2410.13784
ckuemmerle / Christian Kümmerle
npub1am…3w3v4
2024-10-26 13:28:40
Author Public Key
npub1amv8kzuluqq50rxny6klwslm6rpkdyusedcse6wt2dh0m5zqresqd3w3v4Published at
2024-10-26 13:28:40Event JSON
{
"id": "cbb301cc509367da0445473d43ff45768e9bd4b9ae90d77bb177ef72fd3bdb02",
"pubkey": "eed87b0b9fe001478cd326adf743fbd0c3669390cb710ce9cb536efdd0401e60",
"created_at": 1729949320,
"kind": 1,
"tags": [
[
"p",
"f10080f57aceb33837c7902f2ae2394be3c03ebc072227d07794ff6d7beed9dc",
"",
"mention"
],
[
"p",
"2758c0ba588baa417ef1888c6ef66a22a3c81516c0d03715f19edf08aeae0061",
"",
"mention"
]
],
"content": "Today between 10:00-10:30 am at nostr:npub17yqgpat6e6ensd78jqhj4c3ef03uq04uqu3z05rhjnlk67lwm8wq9w5269 , learn about our new research on Lightning Network pathfinding strategies from my great student nostr:npub1yavvpwjc3w4yzlh33zxxaan2y23us9gkcrgrw903nm0s3t4wqpss3pdqdm Saraswathi https://github.com/orgs/TABConf/projects/4?pane=issue\u0026itemId=77244631\u0026issue=TABConf%7C6.tabconf.com%7C109\n\n- We present a detailed breakdown of the underlying cost functions and constraints used by pathfinding algorithms of the different LN node implementations.\n- Surprisingly, we observe that the pathfinding problems that most LN node implementations attempt to solve are NP-complete, and cannot be guaranteed to be optimally solved by the variants of Dijkstra’s algorithm currently deployed in production.\n- Through comparative analysis and simulations, we evaluate efficacy of different pathfinding strategies across metrics such as success rate, fees, path length, and timelock. \n\nWe think that this study provides new insights for how pathfinding within the Lightning Network can further be improved. While beyond the scope of our study, the findings are also relevant for multi-part payments.\n\nLink to paper: https://arxiv.org/pdf/2410.13784",
"sig": "464272b8cd9799a8458ac94ebe8c9f527bf9e18bd1c840c8371d7ad618585f6dc595e1d992c9eaa865f04cd123ddb8c3dc4c17a304a38dd80df8b2f1f02cee63"
}