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 #2176 from TheBlueMatt/2023-04-expose-success-prob

Move the historical bucket tracker to 32 unequal sized buckets

Merge pull request #2579 from rmalonson/unsignedtx

Remove one unnecessary call for sign_holder_commitment_and_htlcs

Remove unnecessary signing call in ChannelMonitor

Merge pull request #2577 from TheBlueMatt/2023-09-msrv

Fix MSRV tests and drop internet-required test

Move to a constant for "bucket one" in the scoring buckets

Scoring buckets are stored as fixed point ints, with a 5-bit
fractional part (i.e. a value of 1.0 is stored as "32"). Now that
we also have 32 buckets, this leads to the codebase having many
references to 32 which could reasonably be confused for each other.

Thus, we add a constant here for the value 1.0 in our fixed-point
scheme.

Decay `historical_estimated_channel_liquidity_*` result to `None`

`historical_estimated_channel_liquidity_probabilities` previously
decayed to `Some(([0; 8], [0; 8]))`. This was thought to be useful
in that it allowed identification of cases where data was previously
available but is now decayed away vs cases where data was never
available. However, with the introduction of
`historical_estimated_payment_success_probability` (which uses the
existing scoring routines so will decay to `None`) this is
unnecessarily confusing.

Given data which has decayed to zero will also not be used anyway,
there's little reason to keep the old behavior, and we now decay to
`None`.

We also take this opportunity to split the overloaded
`get_decayed_buckets`, removing uneccessary code during scoring.

Special-case the 0th minimum bucket in historical scoring

Points in the 0th minimum bucket either indicate we sent a payment
which is < 1/16,384th of the channel's capacity or, more likely,
we failed to send a payment. In either case, averaging the success
probability across the full range of upper-bounds doesn't make a
whole lot of sense - if we've never managed to send a "real"
payment over a channel, we should be considering it quite poor.

To address this, we special-case the 0th minimum bucket and only
look at the largest-offset max bucket when calculating the success
probability.

Track "steady-state" channel balances in history buckets not live

The lower-bound of the scoring history buckets generally never get
used - if we try to send a payment and it fails, we don't learn
a new lower-bound for the liquidity of a channel, and if we
successfully send a payment we only learn a lower-bound that
applied *before* we sent the payment, not after it completed.

If we assume channels have some "steady-state" liquidity, then
tracking our liquidity estimates *after* a payment doesn't really
make sense - we're not super likely to make a second payment across
the same channel immediately (or, if we are, we can use our
un-decayed liquidity estimates for that). By the time we do go to
use the same channel again, we'd assume that its back at its
"steady-state" and the impacts of our payment have been lost.

To combat both of these effects, here we "subtract" the impact of
any just-successful payments from our liquidity estimates prior to
updating the historical buckets.

Move the historical bucket tracker to 32 unequal sized buckets

Currently we store our historical estimates of channel liquidity in
eight evenly-sized buckets, each representing a full octile of the
channel's total capacity. This lacks precision, especially at the
edges of channels where liquidity is expected to lie.

To mitigate this, we'd originally checked if a payment lies within
a bucket by comparing it to a sliding scale of 64ths of the
channel's capacity. This allowed us to assign penalties to payments
that fall within any more than the bottom 64th or lower than the
top 64th of a channel.

However, this still lacks material precision - on a 1 BTC channel
we could only consider failures for HTLCs above 1.5 million sats.
With today's lightning usage often including 1-100 sat payments in
tips, this is a rather significant lack of precision.

Here we rip out the existing buckets and replace them with 32
*unequal* sized buckets. This allows us to focus our precision at
the edges of a channel (where the liquidity is likely to lie, and
where precision helps the most).

We set the size of the edge buckets to 1/16,384th of the channel,
with the size increasing exponentially until it approaches the
inner buckets. For backwards compatibility, the buckets divide
evenly into octets, allowing us to convert the existing buckets
into the new ones cleanly.

This allows us to consider HTLCs down to 6,000 sats for 1 BTC
channels. In order to avoid failing to penalize channels which have
always failed, we drop the sliding scale for comparisons and simply
check if the payment is above the minimum bucket we're analyzing and
below *or in* the maximum one. This generates somewhat more
pessimistic scores, but fixes the lower bound where we suddenly
assign a 0% failure probability.

While this does represent a regression in routing performance, in
some cases the impact of not having to examine as many nodes
dominates, leading to a performance increase.

On a Xeon E3-1220 v5, the `large_mpp_routes` benchmark shows a 15%
performance increase, while the more stable benchmarks show an 8%
and 15% performance regression.

Implement serialization for `[u16; 32]`, DRYing it with `[u8; *]`

In the next commit we'll need serialization for `[u16; 32]`, which
we add here, unifying it with the `[u8; *]` serialization macro.

Clarify some scoring documentation by removing extraneous info

Pin memchr in our release dependency list due to `core2` using it

We're working with rust-bitcoin to remove the `core2` dependency
at https://github.com/rust-bitcoin/rust-bitcoin/pull/2066 but until
that lands and we can upgrade rust-bitcoin we're stuck with it. In
the mean time, we should still pass our MSRV tests.

Merge pull request #2571 from davidcaseria/htlc-descriptor-writeable

Make HTLCDescriptor writeable

Drop `test_esplora_connects_to_public_server`

`blockstream.info` is currently down, causing our CI to fail. This
shouldn't really be a thing, so we drop the blockstream.info-based
test here.

More generally, I'm not really a fan of having tests which run
(outside of CI) and call out to external servers - a developer
working on LDK shouldn't have to have internet access to run our
test suite and shouldn't be registering their presence with a third
party to run our tests.

Pin `syn` back to 2.0.32 fix MSRV in testing

Merge pull request #2568 from tnull/2023-09-housekeeping

Housekeeping: fix some warning and docs

Merge pull request #2572 from benthecarman/rexport-route-hint-secret

Re-export RouteHint and PaymentSecret

Re-export RouteHint and PaymentSecret

Fix unused import warning in `shutdown_tests`

Fix more unused warnings in `test_utils`

Fix warnings in `lightning-net-tokio`

Fix unused variable warning in `monitor_tests`

Merge pull request #2413 from valentinewallace/2023-07-route-blinding

Route blinding MVP

Merge pull request #2521 from TheBlueMatt/2023-08-one-less-write

Avoid persisting ChannelManager in some cases and separate event from persist notifies

Cleanup `ChannelId` re-export

`ChannelId` was weirdly listed in the re-export section of the docs and
reachable via multiple paths. Here we opt to make the `channel_id`
module private and leave only the `ChannelId` struct itself exposed.

Only allow creating 1-hop blinded paths.

Useful until forwarding and receiving to multi-hop blinded paths is supported.

Test sending and receiving to 1-hop blinded paths

Support receiving to 1-hop blinded payment paths.

Parameterize InboundPayload reads with NodeSigner

This will be used in the next commit to deserialize encrypted TLVs for
receiving to 1-hop blinded paths.

Support paying blinded paths.

Restrict `ChannelManager` persist in fuzzing to when we're told to

In the `chanmon_consistency` fuzz, we currently "persist" the
`ChannelManager` on each loop iteration. With the new logic in the
past few commits to reduce the frequency of `ChannelManager`
persistences, this behavior now leaves a gap in our test coverage -
missing persistence notifications.

In order to cath (common-case) persistence misses, we update the
`chanmon_consistency` fuzzer to no longer persist the
`ChannelManager` unless the waker was woken and signaled to
persist, possibly reloading with a previous `ChannelManager` if we
were not signaled.

Merge pull request #2169 from TheBlueMatt/2023-03-monitor-e-monitor

Block the mon update removing a preimage until upstream mon writes

Make HTLCDescriptor writeable

Remove largely useless checks in chanmon_consistency fuzzer

When reloading nodes A or C, the chanmon_consistency fuzzer
currently calls `get_and_clear_pending_msg_events` on the node,
potentially causing additional `ChannelMonitor` or `ChannelManager`
updates, just to check that no unexpected messages are generated.

There's not much reason to do so, the fuzzer could always swap for
a different command to call the same method, and the additional
checking requires some weird monitor persistence introspection.

Here we simplify the fuzzer by simply removing this logic.

Skip persistence in the usual case handling channel_reestablish

When we handle an inbound `channel_reestablish` from our peers it
generally doesn't change any state and thus doesn't need a
`ChannelManager` persistence. Here we avoid said persistence where
possible.

Always persist the `ChannelManager` on a failed ChannelUpdate

If we receive a `ChannelUpdate` message which was invalid, it can
cause us to force-close the channel, which should result in a
`ChannelManager` persistence, though its not critical to do so.

Avoid persisting `ChannelManager` in response to peer connection

When a peer connects and we send some `channel_reestablish`
messages or create a `per_peer_state` entry there's really no
reason to need to persist the `ChannelManager`. None of the
possible actions we take immediately result in a change to the
persisted contents of a `ChannelManager`, only the peer's later
`channel_reestablish` message does.

Move a handful of channel messages to notify-without-persist

Many channel related messages don't actually change the channel
state in a way that changes the persisted channel. For example,
an `update_add_htlc` or `update_fail_htlc` message simply adds the
change to a queue, changing the channel state when we receive a
`commitment_signed` message.

In these cases there's really no reason to wake the background
processor at all - there's no response message and there's no state
update. However, note that if we close the channel we should
persist the `ChannelManager`. If we send an error message without
closing the channel, we should wake the background processor
without persisting.

Here we move to the appropriate `NotifyOption` on some of the
simpler channel message handlers.

Update `channelmanager::NotifyOption` to indicate persist or event

As we now signal events-available from persistence-needed
separately, the `NotifyOption` enum should include a separate
variant for events-but-no-persistence, which we add here.

Separate ChannelManager needing persistence from having events

Currently, when a ChannelManager generates a notification for the
background processor, any pending events are handled and the
ChannelManager is always re-persisted.

Many channel related messages don't actually change the channel
state in a way that changes the persisted channel. For example,
an `update_add_htlc` or `update_fail_htlc` message simply adds the
change to a queue, changing the channel state when we receive a
`commitment_signed` message.

In these cases we shouldn't be re-persisting the ChannelManager as
it hasn't changed (persisted) state at all. In anticipation of
doing so in the next few commits, here we make the public API
handle the two concepts (somewhat) separately. The notification
still goes out via a single waker, however whether or not to
persist is now handled via a separate atomic bool.

Make it harder to forget to call CM::process_background_events

Prior to any actions which may generate a `ChannelMonitorUpdate`,
and in general after startup,
`ChannelManager::process_background_events` must be called. This is
mostly accomplished by doing so on taking the
`total_consistency_lock` via the `PersistenceNotifierGuard`. In
order to skip this call in block connection logic, the
`PersistenceNotifierGuard::optionally_notify` constructor did not
call the `process_background_events` method.

However, this is very easy to misuse - `optionally_notify` does not
convey to the reader that they need to call
`process_background_events` at all.

Here we fix this by adding a separate
`optionally_notify_skipping_background_events` method, making the
requirements much clearer to callers.

Test monitor update completion actions on pre-startup completion

This adds a test for monitor update actions being completed on
startup if a monitor update completed "while we were shut down"
(or, really, the manager didn't get persisted after the update
completed).

Split `expect_payment_forwarded` into a function called by macro

Also allowing us to pass the event manually.

Update tests to test re-claiming of forwarded HTLCs on startup

Because some of these tests require connecting blocks without
calling `get_and_clear_pending_msg_events`, we need to split up
the block connection utilities to only optionally call
sanity-checks.

Correct `expect_payment_forwarded` upstream channel checking

`expect_payment_forwarded` takes a bool to indicate that the
inbound channel on which we received a forwarded payment has been
closed, but then ignores it in favor of looking at the fee in the
event. While this is generally correct, in cases where we process
an event after a channel was closed, which was generated before a
channel closed this is incorrect.

Instead, we examine the bool we already passed and use that.

Block the mon update removing a preimage until upstream mon writes

When we forward a payment and receive an `update_fulfill_htlc`
message from the downstream channel, we immediately claim the HTLC
on the upstream channel, before even doing a `commitment_signed`
dance on the downstream channel. This implies that our
`ChannelMonitorUpdate`s "go out" in the right order - first we
ensure we'll get our money by writing the preimage down, then we
write the update that resolves giving money on the downstream node.

This is safe as long as `ChannelMonitorUpdate`s complete in the
order in which they are generated, but of course looking forward we
want to support asynchronous updates, which may complete in any
order.

Thus, here, we enforce the correct ordering by blocking the
downstream `ChannelMonitorUpdate` until the upstream one completes.
Like the `PaymentSent` event handling we do so only for the
`revoke_and_ack` `ChannelMonitorUpdate`, ensuring the
preimage-containing upstream update has a full RTT to complete
before we actually manage to slow anything down.

Clean up test handling of resending responding commitment_signed

When we need to rebroadcast a `commitment_signed` on reconnect in
response to a previous update (ie not one which contains any
updates) we previously hacked in support for it by passing a `-1`
for the number of expected update_add_htlcs. This is a mess, and
with the introduction of `ReconnectArgs` we can now clean it up
easily with a new bool.

Fix various unused warnings in test and regular builds

Merge pull request #2567 from G8XSU/payment-id

Add PaymentId in ChannelManager.list_recent_payments()

Merge pull request #2566 from G8XSU/check-best-block-2538

Verify channel-monitor processes blocks with skipped best_block

Add PaymentId in ChannelManager.list_recent_payments()

Merge pull request #2563 from tnull/2023-09-kvstore-followups

`KVStore` upstreaming followups

Add length check for read ChannelMonitor keys

Make PersistenceNotifierGuard::optionally_notify take a ChanMan ref

Long ago, for reasons lost to the ages, the
`PersistenceNotifierGuard::optionally_notify` constructor didn't
take a `ChannelManager` reference, but rather explicit references
to the fields of it that it needs.

This is cumbersome and useless, so we fix it here.

Rename `ChannelManager` update future methods for new API

In the next commit, we separate `ChannelManager`'s concept of
waking a listener to both be persisted and to allow the user to
handle events. Here we rename the future-fetching method in
anticipation of this split.

Merge pull request #2514 from valentinewallace/2023-08-compute-blindedpayinfo

Aggregate `BlindedPayInfo` for blinded routes

Merge pull request #2495 from dunxen/2023-07-channelenummap

Use a single peer state map for all channel phases in peer state

Verify channel-monitor processes blocks with skipped best_block

This can happen due to races b/w client's call to block_connect
and adding newly created channel-monitor to chain-monitor using
watch_channel in funding_created.

Remove v1 peer state channel maps & refactor with ChannelPhase

Refactor `ChannelManager` with `ChannelPhase`

Merge pull request #2549 from yanganto/socket-addr

Rename SocketAddress from NetAddress

Struct-ify blinded payment path intermediate node info

Remove unnecessary doc links

Fix blinded payment TLV ser to not length-prefix

impl_writeable_tlv_based includes a length prefix to the TLV stream, which we
don't want.

Derive Clone and Debug for blinded payment TLV structs

Make blinded payment TLV fields public.

These should've been made public when they were added for use in
BlindedPath::new_for_payment.

Support aggregating htlc_maximum_msat for BlindedPayInfo

Support aggregating htlc_minimum_msat for BlindedPayInfo

Compute aggregated BlindedPayInfo in path construction

Rename SocketAddress from NetAddress

Introduce `ChannelPhase` enum

We introduce the `ChannelPhase` enum which will contain the different
channel structs wrapped by each of its variants so that we can place
these within a single `channel_by_id` map in `peer_state` in the
following commits. This will reduce the number of map lookup operations
we need to do in `ChannelManager`'s various methods. It will also make
certain channel counting logic easier to reason about with less risk of
forgetting to modify logic when new channels structs are introduced for
V2 channel establishment.

Remove outdated `Channel` TODO

Have `path_to_windows_str` take reference to avoid `clone`s

Merge pull request #2371 from jkczyz/2023-06-offer-message-handling

BOLT 12 Invoice payments

Merge pull request #2472 from tnull/2023-08-add-kvstore

Replace `KVStorePersister` with `KVStore`

Configure BOLT 12 invoice payment retry strategy

Replace a constant three retry attempts for BOLT 12 invoice payments
with a retry strategy specified when creating a pending outbound
payment. This is configured by users in a later commit when constructing
an InvoiceRequest or a Refund.

Use u32 instead of usize in Retry::Attempts

An upcoming commit requires serializing Retry, so use a type with a
fixed byte length. Otherwise, using eight bytes to serialize a usize
would fail to read on 32-bit machines.

Add tests for send_payment_for_bolt12_invoice

pub(crate) visibility for offers/test_utils.rs

The test utilities for Offers are needed for testing message handling in
ChannelManager and OutboundPayments.

Support paying BOLT 12 invoices

Add a send_payment_for_bolt12_invoice method to OutboundPayments for
initiating payment of a BOLT 12 invoice. This will be called from an
OffersMessageHandler, after which any retries are handled using the
Retryable logic.

Rename OutboundPayments::retry_payment_internal

It will be used for initial attempts at paying BOLT 12 invoices, so
rename it something that covers both that and retries.

Refactor OutboundPayments::retry_payment_internal

Consolidate the creation and insertion of onion_session_privs to the
PendingOutboundPayment::Retryable arm. In an upcoming commit, this
method will be reused for an initial BOLT 12 invoice payment. However,
onion_session_privs are created using a different helper.

Add PendingOutboundPayment::InvoiceReceived

When a BOLT 12 invoice has been received, a payment attempt is made and
any errors result in abandoning the PendingOutboundPayment. This results
in generating at PaymentFailed event, which has a PaymentHash. Thus,
when receiving an invoice, transition from AwaitingInvoice to a new
InvoiceReceived state, the latter of which contains a PaymentHash such
the abandon_payment helper can still be used.

Test removing abandoned AwaitingInvoice payments

Test for removing stale AwaitingInvoice payments

Move IDEMPOTENCY_TIMEOUT_TICKS to where it is used

Add PendingOutboundPayment::AwaitingInvoice

When a BOLT 12 invoice has been requested, in order to guarantee
invoice payment idempotency the future payment needs to be tracked. Add
an AwaitingInvoice variant to PendingOutboundPayment such that only
requested invoices are paid only once. Timeout after a few timer ticks
if a request has not been received.

Add `TestStore` implementation of `KVStore`

Add benchmarking for `FilesystemStore`

We re-add benchmarking for `FilesystemStore` now that we switched over
to it.

Migrate `FilesystemPersister` tests to `FilesystemStore`

Migrate to `KVStore`/`FilesystemStore`

Firstly, we switch our BP over to use `FilesystemStore`, which also gives us test
coverage and ensures the compatibility.

Then, we remove the superseded `KVStorePersister` trait and
the `FilesystemPersister` code.

Add `read_channel_monitors` utility

This replaces the `FilesystemPersister::read_channelmonitors` method, as
we can now implement a single utility for all `KVStore`s.

Add `FilesystemStore`

We upstream the `FilesystemStore` implementation, which is backwards
compatible with `lightning-persister::FilesystemPersister`.

Add `test_utils`

We add a utility function needed by upcoming `KVStore` implementation
tests.

Update `lightning-persister` crate

Add `KVStore` interface trait

We upstream the `KVStore` interface trait from LDK Node, which will
replace `KVStorePersister` in the coming commits.

Besides persistence, `KVStore` implementations will also offer to `list`
keys present in a given `namespace` and `read` the stored values.

Add an InvoiceRequestFailed event

When an invoice is requested but either receives an error or never
receives a response, surface an event to indicate to the user that the
corresponding future payment has failed.

Merge pull request #2134 from jbesraa/add_fromstr_to_netaddress

implement fromstr trait to netaddress

Merge pull request #2557 from waterson/stale-monitor-force-close-debugging

Log each condition that was violated for a stale monitor