Closed renepickhardt closed 9 months ago
@thomash-acinq can you have a look at this? It could be interesting if this simple change improves our expected success rate.
That's a very interesting proposal, thanks @renepickhardt I'm adding an option to use this so we can run A/B tests.
This is excellent news! I am really looking forward to learn if this will also work well on a well connected routing node in mainnet. I were delighted if I could use the results of your A/B test in the evaluation section of my paper (e.g in the form of a table or diagram)
Please allow me to to emphasize again 3 remarks:
700 sats
then your maximum expected value will be at least 700 sats
lets call it 700+x sats
. In such case it woul be preferable to send 2 onions: first the 700 sats
onion and then a few milliseconds later the residual x sats
onion. The reason is that one can proof that generally sending 1 onion for an amount a
has at most the expected value of sending two onions with amounts b
and c
such that b+c=a
. In fact splitting down every onion to 1 sat onions woul maximize the expected value. However this would obviously not be feasible because of the base_fee
and available htlc
slots. Never the less pealing of the certainly available liquidy seems reasonable in any payment splitting schemeImplemented in https://github.com/ACINQ/eclair/pull/2792
- There is actually a stupid observation: Lets say for a route you know that each channel has at least
700 sats
then your maximum expected value will be at least700 sats
lets call it700+x sats
. In such case it woul be preferable to send 2 onions: first the700 sats
onion and then a few milliseconds later the residualx sats
onion. The reason is that one can proof that generally sending 1 onion for an amounta
has at most the expected value of sending two onions with amountsb
andc
such thatb+c=a
. In fact splitting down every onion to 1 sat onions woul maximize the expected value. However this would obviously not be feasible because of thebase_fee
and availablehtlc
slots. Never the less pealing of the certainly available liquidy seems reasonable in any payment splitting scheme
Even ignoring the base fee, we wouldn't gain anything here. If both the 700 and the x succeed, then a 700+x would have worked just as well. And if the x fails, we need to retry via another route anyway, it's not different than trying 700+x first and then retrying 700 via the same route and x via a different route.
@thomash-acinq: I agree if you say my hint is premature optimization. Yet I mildly disagree. Maybe I explained it wrongly. If we know for sure (because of the estimates) that the 700 sats are available. then doing those first will lead to a success and on the same route one could in a similar onion try the +x this will be better than trying x+700 attomically. because in the case where 700+x fails which can happen we would not even have delivered the 700. Yes we would have to try another route anyway but with a residual amount lowered by 700 sats. Here is a diagram for your convenience indicating the situation
in the first diagram I send an atomic payment where sending 45 sats maximizes the exp value to about 40 sats.
whereas in the second diagram I would send the 35 sats of known liquidity in one onion and then on the residual channel compute the max expected value sending a second onion of 28. Assuming my conditional probabilities are correct I will for sure deliver 35. but I even expect to deliver 49 by allocating a total of 63 sats.
As discussed with @t-bast out of band in result to this ldk comment this is a draft PR that indicates how easily it would be to exchange the random allocation of HTLC amounts to candidate paths to an allocation that maximizes the expected value of delivered sats.
Caution: I don't speak Scala and @stefanwouldgo and I just used the github web interface to provide this patch as a rough idea on which few lines would have to be adopted. This patch may thus not even have correct syntax or compile.
Context: The method of using allocations on Routes that maximizes the expected value was also proposed in this issue. I am currently working on a paper with a simulation that indicates that this approach results in more efficient usage of liquidity. Instead of only having simulated results some data confirming the theoretic and simulated results via a mainnet A/B test would be very desirable, hence this draft PR.
Additions:
split
Shortcomings
p(amount) = (cap - inflight + 1 - amount)(cap - inflight + 1)
to compute the expected valueE(a) = a*p_1(a)*...*p_n(a)
for channels1,...,n
.low
andhigh
estimates of the liquidity to compute the conditional probability with previously observed observations for each hop in the expected value computationSeq
of routs fromYen's
algorithm it would probably be more desirable to compute Dijkstra over and over again with updated cost function (weights) between selecting a Route / allocation.Remarks
We skip the computation of a probability on the first hop as we assume that
computeRouteMaxAmount
would not return anything higher than the local liquidity. However routing the local liquidity is certainly possible as we know that we have this liquidity.Thanks for two hours with @stefanwouldgo to discuss the scala way of achieving things