Include any recipient overpayment amounts in the route fee limit

If the user told us to limit their total fee exposure, we should
do so including any potential overpayment to the recipient, which
is ultimately a part of the "fee" as far as the user is concerned.

Try to overpay the recipient if we fail to find a path at all

Previously we'd only try to overpay if we managed to find a path
to the recipient which was sufficient. However, if we fail to find
any path to the recipient at all we should still retry overpaying
the recipient. Ultimately we should be silling to pay whatever
reasonable performance penalty if the alternative is not finding a
path at all, which we do here.

Allow routefinding again due to HTLC limit based on >= not >

While this doesn't matter much in practice, if we go around again
when route-finding to try to meet an htlc_minimum_msat, we use the
`recommended_value_msat` which can work if we meet the
`htlc_minimum_msat` on a channel exactly, so using >= rather than >
can capture cases with 1msat more.

Merge pull request #2612 from TheBlueMatt/2023-09-namespace-split

Refer to top-level persistence namespaces as primary_namespace

Merge pull request #2575 from tnull/2023-09-fix-debug-panic

Various router fixes and #2417 follow-ups

Merge pull request #2611 from TheBlueMatt/2023-09-no-close-on-bad-update

Don't FC when a `channel_update` has a bogus `htlc_minimum_msat`

Update remaining references to primary/secondary namespaces

Update various variables, error strings, and the pending changelog
entry to refer to new namespace terminology.

Update storage constants to new PRIMARY/SECONDARY namespace terms

Rename the persistence `sub_namespace` to `secondary_namespace`

With the top-level namespace now called "primary", "secondary"
makes more sense than "sub".

Don't retry overpaid values for `PartialFailure`s

Previously, if an overpaid path would fail immediately, we'd retry a
`PartialFailure` with the full path amount, _including_ any overpayment.

Here, we now subtract the succeeded paths' values from the
net. value to exclude the overpaid amounts on retry.

Assert query's and route's `final_value_msat` are equal

Refactor `mpp_retry[_overpay]` tests to use `SendEvent::from_event`

.. as a follow-up from #2417.

Make ignored candidate counts `u32`

.. as a follow-up from #2417.

Avoid adding duplicate hint candidates if they are first hops

If we have a direct channel to a node generating an invoice with route
hints, we'd previously happily add multiple candidates that all refer to
the same channel. To keep our candidate set small and unify our tracking
where possible, we now check if its `short_channel_id` is an
`outbound_scid_alias` of any of our first hops and refrain from adding
another candidate if it's the case.

Also add route hints if we are the source

Previously, we would only consider route hints if we had a direct
channel to the first node in the hint or if the first node in the hint
was part of the public network graph.

However, this left out the possiblity of us being part of the first hop,
especially if our own node is not announced and part of the graph.

Merge pull request #2607 from DhananjayPurohit/civkit-branch

Issue in adding rust lightning as dependency on windows

Merge pull request #2606 from wpaulino/anchors-counterparty-htlc-claim-sequence

Use correct input sequence for HTLC claims from counterparty commitments

Log full channel_update messages received for our channels

Extend logging of ignored candidates

Use `saturating_add` when adding inflight HTLCs values

Previously this calculation could overflow, leading to panicking in `debug`.

chore: remove time_utils.rs

No longer needed time_utils in lightning-invoice

Refer to top-level persistence namespaces as `primary_namespace`

This fixes a bindings build error as `namespace` is a C++ keyword
which cannot be used as an argument, and while this could be fixed
in the bindings rather than here, separating the term `namespace`
between the concept (which refers to the primary and sub
namespaces) and the primary namespace makes the documentation more
readable.

Use `Result<_, io::Error>` over `io::Result<_>`

Personally I've always found the overload of a prelude enum to be
confusing, and never bothered to handle it properly in bindings as
a result. To avoid needing to do so now, we simply move the
newly-introduced `io::Result` usages over to
`Result<_, io::Error>`.

Don't FC when a `channel_update` has a bogus `htlc_minimum_msat`

If a peer sends us a `channel_update` for our own channel with an
`htlc_minimum_msat` which is more than the channel's amount, that's
dumb, but there's no reason to force-close the channel. We don't
even use the field.

Here we simply drop the unnecessary check.

Merge pull request #2570 from valentinewallace/2023-08-router-fuzz-fail

Fix router fuzz failure

Use correct input sequence for HTLC claims from counterparty commitments

HTLC outputs, like the `to_remote` output, in commitment transactions
with anchor outputs also have an additional `1 CSV` constraint on the
counterparty. When spending such outputs, their corresponding input
needs to have their sequence set to 1. This was done for HTLC claims
from holder commitments, but unfortunately not for counterparty
commitments as we were lacking test coverage.

get_route: fix path value contribution to include min htlc overpay

Previously, the fuzzer hit a debug panic because we wouldn't include the amount
overpaid to meet a last hop's min_htlc in the total collected paths value. We
now include this value and also penalize hops along the overpaying path to
ensure that it gets deprioritized in path selection.

get_route: fix path_min for first_hop<>network_node candidates

Previously, we would add a first_hop<>network_node channel that did not have
enough contribution amount to cover the next channel's min htlc plus fees,
because we were storing the next hop as having a path_min that did not include
fees, and would add a connecting first_hop node that did not have enough
contribution amount, leading to a debug panic upon invalid path construction.

get_route: fix path_min for first_hop<>blinded_hint candidates

See previous commit, but the bug where we would underestimate how much a first
hop candidate needed to be able to relay was also present in blinded paths.

get_route: fix path_min when adding first_hop<>route_hint candidates

Previously, we would add a candidate hop to the list of potential hops even
though its available contribution wasn't sufficient to meet the next hop's
min_htlc. We'd subsequently build an invalid path using this hop and hit a
debug assertion.

get_route: fix outdated var name

Previously this variable was a bool, but has since been updated to be an
Option, so rename accordingly.

Pathfinding: ignore blinded route hints where we are the intro node

See tests, but the fuzzer found several panics from not fully ignoring these
hints.

We should support these route hints eventually, but it will involve some
reworking of the Path/BlindedTail structs.

Remove trailing whitespace in get_route

Because my text editor loves to do that.

Refuse to pathfind when provided our_node_id matches internal dummy pk

The fuzzer managed to hit this and it causes some invalid paths to be generated
internally.

Pathfinding: log when we ignore one hop blinded route hints

Merge pull request #2601 from TheBlueMatt/2023-09-117-alpha2

Bump versions to 0.0.117-alpha2/invoice 0.25.0-alpha2

Merge pull request #2603 from TheBlueMatt/2023-09-default-route-limit

Set a default max_total_routing_fee_msat of 1% + 50sats

Merge pull request #2602 from TheBlueMatt/2023-09-descriptor-hash

Derive `Hash` for `SpendableOutputDescriptor`

Merge pull request #2359 from domZippilli/2023-06-monitor-updating-persister

Monitor updating persister

Add MonitorUpdatingPersister

MonitorUpdatingPersister is an implementation of Persister that stores
ChannelMonitorUpdates separately from ChannelMonitors. Its RFC is
in #2545, at https://github.com/orgs/lightningdevkit/discussions/2545.

Co-Authored-By: Elias Rohrer <dev@tnull.de>

Merge pull request #2486 from wvanlint/batch_channel_opens

Batch funding for v1 channel establishments

Set a default `max_total_routing_fee_msat` of 1% + 50sats

When using the normal default constructors, we should have some
fee maximum to ensure our default behavior is safe. Here we pick
1% + 50 sats to ensure we're always willing to pay
reasonabl(y high) fees, but not anything too wild.

Derive `Debug` and `Display` for `Route`

Derive `Hash` for `SpendableOutputDescriptor`

This allows for easy descriptor de-duplication before building a
claiming transaction.

Batch funding for v1 channel establishments

Rename finish_force_close_channel to finish_close_channel

Always call finish_force_close_channel on closure

This is a step towards more unified closing of channels, and provides a
place where the per_peer_state lock is not held.

Bump versions to 0.0.117-alpha2/invoice 0.25.0-alpha2

Merge pull request #2417 from tnull/2023-07-max-total-fee

Add config option to set maximum total routing fee

Test `max_total_routing_fee_msat` handling when retrying overpaid paths

We setup an MPP scenario with two paths in which we need to overpay to
reach `htlc_minimum_msat`. We then fail the overpaid path and check that
on retry our `max_total_routing_fee_msat` only accounts for the path
fees, but not for the fees overpaid in the first attempt.

Check `max_total_routing_fee` is accounted for in `test_threaded_payment_retries`

Check `max_total_routing_fee` is reduced in `mpp_retry` test

We check that the `RouteParameters::max_total_routing_fee` field is reduced accordingly
to our previously used fees.

Account for leftover fee budget when retrying via `check_retry_payment`

Merge pull request #2597 from TheBlueMatt/2023-09-finish-force-close-deadlocks

Fix potential peer_state deadlocks in `finish_force_close_channel`

Account for leftover fee budget when retrying `PartialFailure`s

Test we adhere to `max_total_routing_fee_msat`

Consider `RouteParameters::max_total_routing_fee_msat` in `get_route`

We exclude any candidate hops if we find that using them would let the
aggregated path routing fees exceed `max_total_routing_fee_msat`.

Moreover, we return an error if the aggregated fees over all paths of
the selected route would surpass `max_total_routing_fee_msat`.

Introduce `RouteParameters::max_total_routing_fee_msat`

Currently, users have no means to upper-bound the total fees accruing
when finding a route. Here, we add a corresponding field to
`RouteParameters` which will be used to limit the candidate set during
path finding in the following commits.

Provide some test coverage of `shutdown` msgs for unfunded chans

We have code to handle receiving `shutdown` messages on unfudned
channels. However, it had no test coverage, which we add here.

Fix potential peer_state deadlocks in `finish_force_close_channel`

`ChannelManager::finish_force_close_channel` exists to do cleanups
which must happen without the `per_peer_state` mutex held. However,
because it lacked lock assertions, several changes snuck in
recently which resulted in it running with peer-state locks held,
risking a deadlock if some HTLCs need to be failed.

Merge pull request #2583 from Evanfeenstra/pub-make-onion

Pub make onion

Merge pull request #2576 from valentinewallace/2023-09-fix-outbound-bp-fail-ev

Fix `PaymentPathFailed::payment_failed_permanently` on blinded path fail

Merge pull request #2594 from benthecarman/debug-monitor-update-id

Implement Debug for MonitorUpdateId

Implement Debug for MonitorUpdateId

Blame outbound channel on UPDATE onion failure with 0-len update

We've run into this several times in the wild, likely due to
https://github.com/ElementsProject/lightning/issues/6200 wherein a node on the
path will error with 0x1000 but not provide a channel update (a spec
violation).

Previously, we would blame the inbound edge even though the buggy peer wanted
us to blame the outbound edge. Since this issue seems to be recurring and our
blaming the inbound edge is causing us to punish innocent channels, trust the
peer that the outbound edge is the one to blame.

Fix PaymentPathFailed::payment_failed_permanently on blinded path fail

Previously this value would be incorrectly set to true because we wouldn't
account for blinded hops when determining if we were processing the last hop's
failure packet.

Correct DecodedOnionFailure when processing we-are-intro-node path

We don't support sending to paths where we are the intro node yet, but may as
well set the failure correctly now.

DecodedOnionFailure::payment_retryable -> ::payment_failed_permanently

Our ultimate goal with this field is to set
PaymentPathFailed::payment_failed_permanently, so use this name rather than
flipping a bool back and forth across methods.

Struct-ify onion util internal result type

Improves readability.

Rename onion util internal var

This variable is ultimately for setting
PaymentPathFailed::payment_failed_permanently, so use this name rather than
flipping a bool back and forth.

Merge pull request #2589 from ErikDeSmedt/reexport_route_hint_hop

Reexport RouteHintHop

Merge pull request #2592 from TheBlueMatt/2023-09-117-alpha

Update crate version numbers to 0.0.117-alpha1/invoice 0.25-alpha1

Merge pull request #2590 from TheBlueMatt/2023-09-default-score-params

Use `Default::default()` to construct `()` as a test scoring param

Update crate version numbers to 0.0.117-alpha1/invoice 0.25-alpha1

Merge pull request #2562 from TheBlueMatt/2023-08-no-perm-fail

Drop the ChannelMonitorUpdateStatus::PermanentFailure variant

Add an `UnrecoverableError` variant to `ChannelMonitorUpdateStatus`

While there is no great way to handle a true failure to persist a
`ChannelMonitorUpdate`, it is confusing for users for there to be
no error variant at all on an I/O operation.

Thus, here we re-add the error variant removed over the past
handful of commits, but rather than handle it in a truly unsafe
way, we simply panic, optimizing for maximum mutex poisoning to
ensure any future operations fail and return immediately.

In the future, we may consider changing the handling of this to
instead set some "disconnect all peers and fail all operations"
bool to give the user a better chance to shutdown in a semi-orderly
fashion, but there's only so much that can be done in lightning if
we truly cannot persist new updates.

Drop doc comments on `ChainMonitor` trait impl methods

In general, doc comments on trait impl blocks are not very visible
in rustdoc output, and unless they provide useful information they
should be elided.

Here we drop useless doc comments on `ChainMonitor`'s `Watch` impl
methods.

Drop error handling in `handle_new_monitor_update`

Now that `handle_new_monitor_update` can no longer return an error,
it similarly no longer needs any code to handle errors. Here we
remove that code, substantially reducing macro variants.

Clean up code flow in `ChannelManager`

In the previous commit various dead code was removed. Here we
finish that cleanup by removing uneccessary indentation and syntax.

Drop `PermamentFailure` persistence handling in ChannelManager

Update `ChannelMonitorUpdateStatus` documentation with async support

Since we now (almost) support async monitor update persistence, the
documentation on `ChannelMonitorUpdateStatus` can be updated to no
longer suggest users must keep a local copy that persists before
returning. However, because there are still a few remaining issues,
we note that async support is currently beta and explicily warn of
potential for funds-loss.

Fixes #1684

Rename `MonitorEvent::CommitmentTxConfirmed` to `HolderForceClosed`

The `MonitorEvent::CommitmentTxConfirmed` has always been a result
of us force-closing the channel, not the counterparty doing so.
Thus, it was always a bit of a misnomer. Worse, it carried over
into the channel's `ClosureReason` in the event API.

Here we simply rename it and use the proper `ClosureReason`.

Drop `ChannelMonitorUpdate::UpdateFailed` as its now unused

Drop `channel_perm_failed` tracking in `ChainMonitor`

Now that `PermanentFailure` is not a possible return value, we can
simply remove handling of it in `ChannelMonitor`.

Drop the `ChannelMonitorUpdateStatus::PermanentFailure` variant

When a `ChannelMonitorUpdate` fails to apply, it generally means
we cannot reach our storage backend. This, in general, is a
critical issue, but is often only a transient issue.

Sadly, users see the failure variant and return it on any I/O
error, resulting in channel force-closures due to transient issues.

Users don't generally expect force-closes in most cases, and
luckily with async `ChannelMonitorUpdate`s supported we don't take
any risk by "delaying" the `ChannelMonitorUpdate` indefinitely.

Thus, here we drop the `PermanentFailure` variant entirely, making
all failures instead be "the update is in progress, but won't ever
complete", which is equivalent if we do not close the channel
automatically.

Rewrite failure payment retry tests to avoid perm-fail storage

Two tests in the payment tests currently rely on failing to persist
ChannelMonitorUpdates as their method of failing payments before
they even get out the door.

In the coming commits we'll drop the persist failure error codes,
so here rewrite these tests to rely on trying to send more than is
available in a channel.

Reexport RouteHintHop

Earlier @benthecarman re-exported `RouteHint` to make life-easier
for developpers that use `lightning-invoice` and don't use the
`lightning`-crate.

This only solved part of the issue. To create a `RouteHint` the
developer must also have access to `RouteHintHop`.

See also:
  PR https://github.com/lightningdevkit/rust-lightning/pull/2572
commit 79b426f49b08a66e404669ce7d1332c3977c5d95

Use `Default::default()` to construct `()` as a test scoring param

In bindings, we can't use unbounded generic types, and thus have to
rip out the `ScoreParams` and replace them with static
`ProbabilisticScoringFeeParams` universally. To make this easier,
using `Default::default()` everywhere allows the type to change out
from under the test without the test needing to change.

Merge pull request #2547 from TheBlueMatt/2023-04-nonlinear-scoring

Add an option to make the success probability estimation nonlinear

public make_onion_message static method on OnionMessenger

Avoid unnecessary newline in middle of log statement

Add an option to make the success probability estimation nonlinear

Our "what is the success probability of paying over a channel with
the given liquidity bounds" calculation currently assumes the
probability of where the liquidity lies in a channel is constant
across the entire capacity of a channel. This is obviously a
somewhat dubious assumption given most nodes don't materially
rebalance and flows within the network often push liquidity
"towards the edges".

Here we add an option to consider this when scoring channels during
routefinding. Specifically, if a new `linear_success_probability`
flag is unset on `ProbabilisticScoringFeeParameters`, rather than
assuming a PDF of `1` (across the channel's capacity scaled from 0
to 1), we use `(x - 0.5)^2`.

This assumes liquidity is likely to be near the edges, which
matches experimental results. Further, calculating the CDF (i.e.
integral) between arbitrary points on the PDF is trivial, which we
do as our main scoring function.

While this (finally) introduces floats in our scoring, its not
practical to exponentiate using fixed-precision, and benchmarks
show this is a performance regression, but not a huge one, more
than made up for by the increase in payment success rates.

Score in-flight amounts as amounts, not a capacity reduction

When we started considering the in-flight amounts when scoring, we
took the approach of considering the in-flight amount as an
effective reduction in the channel's total capacity. When we were
scoring using a flat success probability PDF, that was fine,
however in the next commit we'll move to a highly nonlinear one,
which makes this a pretty confusing heuristic.

Here, instead, we move to considering the in-flight amount as
simply an extension of the amount we're trying to send over the
channel, which is equivalent for the flat success probability PDF,
but makes much more sense in a nonlinear world.

Scale the success probability of channels without info down by 75%

If we are examining a channel for which we have no information at
all, we traditionally assume the HTLC success probability is
proportional to the channel's capacity. While this may be the case,
it is not the case that a tiny payment over a huge channel is
guaranteed to succeed, as we assume. Rather, the probability of
such success is likely closer to 50% than 100%.

Here we try to capture this by simply scaling the success
probability for channels where we have no information down
linearly. We pick 75% as the upper bound rather arbitrarily - while
50% may be more accurate, its possible it would lead to an
over-reliance on channels which we have paid through in the past,
which aren't necessarily always the best candidates.

Note that we only do this scaling for the historical bucket
tracker, as there we can be confident we've never seen a successful
HTLC completion on the given channel. If we were to apply the same
scaling to the simple liquidity bounds based scoring we'd penalize
channels we've never tried over those we've only ever fails to pay
over, which is obviously not a good outcome.

Split out success probability calculation to allow for changes

Our "what is the success probability of paying over a channel with
the given liquidity bounds" calculation is reused in a few places,
and is a key assumption across our main score calculation and the
historical bucket score calculations.

Here we break it out into a function to make it easier to
experiment with different success probability calculations.

Note that this drops the numerator +1 in the liquidity scorer,
which was added to compensate for the divisor + 1 (which exists to
avoid divide-by-zero), making the new math slightly less correct
but not by any material amount.

Merge pull request #2587 from wpaulino/anchors-fee-fixes

Anchor outputs fee fixes

Sanity check fees on transactions produced by the bump event handler

We add a few debug assertions to ensure we don't overpay fees by 5% more
than expected.

Account for existing input amounts throughout coin selection

We'd previously ignore the existing amount transactions were already
attempting to spend when deciding whether we should add more inputs
throughout coin selection. This would result in us attaching more inputs
than necessary to satisfy our target amount. In the case of HTLC
transactions, we'd burn the HTLC amount completely, since the pre-signed
transaction has zero fee (input amount == output amount).

Along the way, we also fix the slight overpayment in anchor
transactions. We now properly account for the fees the transaction
already paid for, simply by pretending the fees are part of the anchor
input amount.

Limit external claim feerate bumps

Since we don't know the total input amount of an external claim (those
which come anchor channels), we can't limit our feerate bumps by the
amount of funds we have available to use. Instead, we choose to limit it
by a margin of the new feerate estimate.

Merge pull request #2584 from TheBlueMatt/2023-09-msrv-try-2

Correct syn pinning on cargo 1.48