📅 Original date posted:2022-03-20
📝 Original message:
Good morning everyone,
with regards to zerobasefee, I think that the argument that HTLCs are
costly doesn't quite hold up because they are always free to an
attacker as it stands. However, I fully agree with Zmn's opinion that
it's not necessary to bang our head against any opposition to this
because we can simply follow his excellent method for overweighing
base fee. I believe this is a very natural approach to let the market
decide on the relative importance of optimized routing vs base fees.
As to Martin's approximation research, I have asked myself similar
questions. Unfortunately, the paper you cite is paywalled and not
available at sci-hub, so I haven't read it. FWIW, I believe I have a
simple proof that minimum cost flow preserves approximation FACTORS:
Let O be the original problem and A the approximated problem such that
every flow in O can be mapped 1:1 to a flow in A and vice versa. Let
every edge e in O be represented by a set of edges in A whose total
cost is within a factor (1+epsilon) for every possible flow (could be
over- or underestimating). Note that this means that every flow in O
has cost within a factor (1+epsilon) for the corresponding flow in A
and vice versa.
Now let f_a be the min cost flow in A and f_o the min cost flow in O.
Assume that c(f_o)(1+epsilon)<c(f_a). Then f_o corresponds to a flow
in A that is cheaper than f_a, but that's impossible because f_a is
the min cost flow.
QED.
Problems might arise anyway because we represent probabilities only
logarithmically in the cost, so that a factor of (1+epsilon)
corresponds to an exponent (1+epsilon) for the probabilities. But René
seems optimistic that the resulting flows look good enough in
practice.
I am still optimistic that exact solvers with something like the cost
scaling approach might also be feasible (as long as they produce
integer flows), but I am happy that this simple approximation approach
seems good enough. This should save us a lot of work because there are
many linear min cost solvers available that represent years of
cumulative work in optimization research.
Cheers
Stefan
Am Sa., 19. März 2022 um 22:09 Uhr schrieb Martin via Lightning-dev
<lightning-dev at lists.linuxfoundation.org>:
>
> Dear Carsten, Rene and fellow lightning developers,
>
> Regarding the approximation quality of the minimum convex cost flow formulation for multi-part payments on the lightning network [1] and Carsten's discussion points on Twitter [2] and on the mailing list:
>
> > 8) Quality of Approximation
> >
> > There are some problems in computer science that are hard/impossible to
> > approximate, in the sense that any kind of deviation from the optimum
> > could cause the computed results to be extremely bad. Do you have some
> > idea (or proof) that your kind of approximation isn't causing a major
> > issue? I guess a piece-wise linearization with an infinite number of
> > pieces corresponds to the optimal result. Given a finite number of
> > pieces, how large is the difference to the optimum?
>
> I did some literature research and came across an insightful paper [3] by Dorit Hochbaum from 1993, that proves proximity results for integer and continuous optimal solutions of the minimum convex cost flow as well as proximity results of the optimal solutions for a piecewise linear approximation and the original problem.
>
> Admittedly theoretical results, however, it further underpins that a piecewise linear approximation is a reasonable approach to find optimal flows and even shows that searching for optimal solutions on the continuous domain (e.g. with descent methods from convex optimization) also gives near-optimal solutions on the integer domain.
>
> Cheers,
> Martin
>
> [1] https://arxiv.org/abs/2107.05322
> [2] https://twitter.com/renepickhardt/status/1502293438498234371
> [3] https://www.worldscientific.com/doi/abs/10.1142/9789812798190_0005
> _______________________________________________
> Lightning-dev mailing list
> Lightning-dev at lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev
Stefan Richter [ARCHIVE] /
npub19f…f4wf0
2023-06-09 13:05:33
in reply to nevent1q…x95w
Author Public Key
npub19fnl48y9j4fk9w0a284mqvszq6fuppelqp2tcxf0s37l95avdtussf4wf0Published at
2023-06-09 13:05:33Event JSON
{
"id": "b8a4be28d3a816dcfb61421e62ed1964d2f202d68cb08360c72b7b40b575ceae",
"pubkey": "2a67fa9c85955362b9fd51ebb032020693c0873f0054bc192f847df2d3ac6af9",
"created_at": 1686315933,
"kind": 1,
"tags": [
[
"e",
"23813e61141e9c848ba0b144e5a9930e93968efb778b53acea9487b101f83f67",
"",
"root"
],
[
"e",
"f3520c70f311212cf2cdbde5a80e298dcbef2db50408883672548da1fab82522",
"",
"reply"
],
[
"p",
"471a68046745ba903f6c10dc195004e5d638e78e025e71fecd1ea22be625fc5e"
]
],
"content": "📅 Original date posted:2022-03-20\n📝 Original message:\nGood morning everyone,\n\nwith regards to zerobasefee, I think that the argument that HTLCs are\ncostly doesn't quite hold up because they are always free to an\nattacker as it stands. However, I fully agree with Zmn's opinion that\nit's not necessary to bang our head against any opposition to this\nbecause we can simply follow his excellent method for overweighing\nbase fee. I believe this is a very natural approach to let the market\ndecide on the relative importance of optimized routing vs base fees.\n\nAs to Martin's approximation research, I have asked myself similar\nquestions. Unfortunately, the paper you cite is paywalled and not\navailable at sci-hub, so I haven't read it. FWIW, I believe I have a\nsimple proof that minimum cost flow preserves approximation FACTORS:\n\nLet O be the original problem and A the approximated problem such that\nevery flow in O can be mapped 1:1 to a flow in A and vice versa. Let\nevery edge e in O be represented by a set of edges in A whose total\ncost is within a factor (1+epsilon) for every possible flow (could be\nover- or underestimating). Note that this means that every flow in O\nhas cost within a factor (1+epsilon) for the corresponding flow in A\nand vice versa.\n\nNow let f_a be the min cost flow in A and f_o the min cost flow in O.\nAssume that c(f_o)(1+epsilon)\u003cc(f_a). Then f_o corresponds to a flow\nin A that is cheaper than f_a, but that's impossible because f_a is\nthe min cost flow.\nQED.\n\nProblems might arise anyway because we represent probabilities only\nlogarithmically in the cost, so that a factor of (1+epsilon)\ncorresponds to an exponent (1+epsilon) for the probabilities. But René\nseems optimistic that the resulting flows look good enough in\npractice.\n\nI am still optimistic that exact solvers with something like the cost\nscaling approach might also be feasible (as long as they produce\ninteger flows), but I am happy that this simple approximation approach\nseems good enough. This should save us a lot of work because there are\nmany linear min cost solvers available that represent years of\ncumulative work in optimization research.\n\nCheers\n Stefan\n\nAm Sa., 19. März 2022 um 22:09 Uhr schrieb Martin via Lightning-dev\n\u003clightning-dev at lists.linuxfoundation.org\u003e:\n\u003e\n\u003e Dear Carsten, Rene and fellow lightning developers,\n\u003e\n\u003e Regarding the approximation quality of the minimum convex cost flow formulation for multi-part payments on the lightning network [1] and Carsten's discussion points on Twitter [2] and on the mailing list:\n\u003e\n\u003e \u003e 8) Quality of Approximation\n\u003e \u003e\n\u003e \u003e There are some problems in computer science that are hard/impossible to\n\u003e \u003e approximate, in the sense that any kind of deviation from the optimum\n\u003e \u003e could cause the computed results to be extremely bad. Do you have some\n\u003e \u003e idea (or proof) that your kind of approximation isn't causing a major\n\u003e \u003e issue? I guess a piece-wise linearization with an infinite number of\n\u003e \u003e pieces corresponds to the optimal result. Given a finite number of\n\u003e \u003e pieces, how large is the difference to the optimum?\n\u003e\n\u003e I did some literature research and came across an insightful paper [3] by Dorit Hochbaum from 1993, that proves proximity results for integer and continuous optimal solutions of the minimum convex cost flow as well as proximity results of the optimal solutions for a piecewise linear approximation and the original problem.\n\u003e\n\u003e Admittedly theoretical results, however, it further underpins that a piecewise linear approximation is a reasonable approach to find optimal flows and even shows that searching for optimal solutions on the continuous domain (e.g. with descent methods from convex optimization) also gives near-optimal solutions on the integer domain.\n\u003e\n\u003e Cheers,\n\u003e Martin\n\u003e\n\u003e [1] https://arxiv.org/abs/2107.05322\n\u003e [2] https://twitter.com/renepickhardt/status/1502293438498234371\n\u003e [3] https://www.worldscientific.com/doi/abs/10.1142/9789812798190_0005\n\u003e _______________________________________________\n\u003e Lightning-dev mailing list\n\u003e Lightning-dev at lists.linuxfoundation.org\n\u003e https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev",
"sig": "b5e3c8a3d0222438e6060d8e018a053c4ea673b4f6889033d922c17b35cd49b7722de8873390812be9aaf140a18f1f3ac858eed86021b603a7667bc736e9405e"
}