Anthony Towns [ARCHIVE] on Nostr: 📅 Original date posted:2021-08-31 📝 Original message: On Thu, Aug 26, 2021 at ...

📅 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