📅 Original date posted:2021-08-31
📝 Original message:
On Thu, Aug 26, 2021 at 04:33:23PM +0200, René Pickhardt via Lightning-dev wrote:
> As we thought it was obvious that the function is not linear we only explained
> in the paper how the jump from f(0)=0 to f(1) = ppm+base_fee breaks convexity.
(This would make more sense to me as "f(0)=0 but f(epsilon)->b as
epsilon->0, so it's discontinuous")
> "Do we really want users to solve an NP-hard problem when
> they wish to find a cheap way of paying each other on the Lightning Network?"
FWIW, my answer to this is "sure, if that's the way it turns out".
Another program which solves an NP-hard problem every time it runs is
"apt-get install" -- you can simulate 3SAT using Depends: and Conflicts:
relationships between packages. I worked on a related project in Debian
back in the day that did a slightly more complicated variant of that
problem, namely working out if updating a package in the distro would
render other packages uninstallable (eg due to providing a different
library version) -- as it turned out, that even actually managed to hit
some of the "hard" NP cases every now and then. But it was never really
that big a deal in practice: you just set an iteration limit and consider
it to "fail" if things get too complicated, and if it fails too often,
you re-analyse what's going on manually and add a new heuristic to cope
with it.
I don't see any reason to think you can't do roughly the same for
lightning; at worst just consider yourself as routing on log(N) different
networks: one that routes payments of up to 500msat at (b+0.5ppm), one
that routes payments of up to 1sat at (b+ppm), one that routes payments
of up to 2sat at (b+2ppm), one that routes payments of up to 4sat at
(b+4ppm), etc. Try to choose a route for all the funds; if that fails,
split it; repeat. In some case that will fail despite there being a
possible successful multipath route, and in other cases it will choose a
moderately higher fee path than necessary, but if you're talking a paying
a 0.2% fee vs a 0.1% fee when the current state of the art is a 1% fee,
that's fine.
Cheers,
aj
Anthony Towns [ARCHIVE] /
npub17r…x9l2h
2023-06-09 13:03:36
in reply to nevent1q…km9k
Author Public Key
npub17rld56k4365lfphyd8u8kwuejey5xcazdxptserx03wc4jc9g24stx9l2hPublished at
2023-06-09 13:03:36Event JSON
{
"id": "4ad90d1ca6eea07b19fec7e2a29b6a8b84c641f4bbdb6f9590878b4a62016e4d",
"pubkey": "f0feda6ad58ea9f486e469f87b3b9996494363a26982b864667c5d8acb0542ab",
"created_at": 1686315816,
"kind": 1,
"tags": [
[
"e",
"01d9c9502f49dd38e6e1b40b488725a995f866aed238951b8ee32ae941e02526",
"",
"root"
],
[
"e",
"a1dbe9588827323cf6b4a226b8c397a1061119b6b967c5b6a2ee920f9327acb1",
"",
"reply"
],
[
"p",
"17ccd89be295c0ae65f1cd3740a9dad84ec8b6d7050712a7f04ae5284b2fab99"
]
],
"content": "📅 Original date posted:2021-08-31\n📝 Original message:\nOn Thu, Aug 26, 2021 at 04:33:23PM +0200, René Pickhardt via Lightning-dev wrote:\n\u003e As we thought it was obvious that the function is not linear we only explained\n\u003e in the paper how the jump from f(0)=0 to f(1) = ppm+base_fee breaks convexity.\n\n(This would make more sense to me as \"f(0)=0 but f(epsilon)-\u003eb as\nepsilon-\u003e0, so it's discontinuous\")\n\n\u003e \"Do we really want users to solve an NP-hard problem when\n\u003e they wish to find a cheap way of paying each other on the Lightning Network?\" \n\nFWIW, my answer to this is \"sure, if that's the way it turns out\".\n\nAnother program which solves an NP-hard problem every time it runs is\n\"apt-get install\" -- you can simulate 3SAT using Depends: and Conflicts:\nrelationships between packages. I worked on a related project in Debian\nback in the day that did a slightly more complicated variant of that\nproblem, namely working out if updating a package in the distro would\nrender other packages uninstallable (eg due to providing a different\nlibrary version) -- as it turned out, that even actually managed to hit\nsome of the \"hard\" NP cases every now and then. But it was never really\nthat big a deal in practice: you just set an iteration limit and consider\nit to \"fail\" if things get too complicated, and if it fails too often,\nyou re-analyse what's going on manually and add a new heuristic to cope\nwith it.\n\nI don't see any reason to think you can't do roughly the same for\nlightning; at worst just consider yourself as routing on log(N) different\nnetworks: one that routes payments of up to 500msat at (b+0.5ppm), one\nthat routes payments of up to 1sat at (b+ppm), one that routes payments\nof up to 2sat at (b+2ppm), one that routes payments of up to 4sat at\n(b+4ppm), etc. Try to choose a route for all the funds; if that fails,\nsplit it; repeat. In some case that will fail despite there being a\npossible successful multipath route, and in other cases it will choose a\nmoderately higher fee path than necessary, but if you're talking a paying\na 0.2% fee vs a 0.1% fee when the current state of the art is a 1% fee,\nthat's fine.\n\nCheers,\naj",
"sig": "eccfdfe819e76a7ffdbf5418434fa127c00e7e61e11ea0e2326173c91848b49bcf691ed5f76044451b61af139f9bf43da92faa796cdfefcc529d39ee1b81097f"
}