Delay removal of fulfilled outbound payments for a few timer ticks

Previously, once a fulfilled outbound payment completed and all
associated HTLCs were resolved, we'd immediately remove the payment
entry from the `pending_outbound_payments` map.

Now that we're using the `pending_outbound_payments` map for send
idempotency, this presents a race condition - if the user makes a
redundant `send_payment` call at the same time that the original
payment's last HTLC is resolved, the user would reasonably expect
the `send_payment` call to fail due to our idempotency guarantees.

However, because the `pending_outbound_payments` entry is being
removed, if it completes first the `send_payment` call will
succeed even though the user has not had a chance to see the
corresponding `Event::PaymentSent`.

Instead, here, we delay removal of `Fulfilled`
`pending_outbound_payments` entries until several timer ticks have
passed without any corresponding event or HTLC pending.

Allow users to specify the `PaymentId` for new outbound payments

In c986e52ce83e9aeaa9447abebc5f6600470337cf, an `MppId` was added
to `HTLCSource` objects as a way of correlating HTLCs which belong
to the same payment when the `ChannelManager` sees an HTLC
succeed/fail. This allows it to have awareness of the state of all
HTLCs in a payment when it generates the ultimate user-facing
payment success/failure events. This was used in the same PR to
avoid generating duplicative success/failure events for a single
payment.

Because the field was only used as an internal token to correlate
HTLCs, and retries were not supported, it was generated randomly by
calling the `KeysInterface`'s 32-byte random-fetching function.
This also provided a backwards-compatibility story as the existing
HTLC randomization key was re-used for older clients.

In 28eea12bbe0d78d256f79ec725cf02366dce4e36 `MppId` was renamed to
the current `PaymentId` which was then used expose the
`retry_payment` interface, allowing users to send new HTLCs which
are considered a part of an existing payment.

At no point has the payment-sending API seriously considered
idempotency, a major drawback which leaves the API unsafe in most
deployments. Luckily, there is a simple solution - because the
`PaymentId` must be unique, and because payment information for a
given payment is held for several blocks after a payment
completes/fails, it represents an obvious idempotency token.

Here we simply require the user provide the `PaymentId` directly in
`send_payment`, allowing them to use whatever token they may
already have for a payment's idempotency token.

Merge pull request #1780 from wpaulino/rust-edition-2018

Bump workspace to rust edition 2018

Mostly motivated by the need of async/await.

Merge pull request #1770 from jkczyz/2022-10-debug-route-hints

Add logging in route hint filtering

Merge pull request #1788 from TheBlueMatt/2022-10-mtlc-writer

Add `WriteableScore` bindings impl for `MultiThreadedLockableScore`

Add `WriteableScore` bindings impl for `MultiThreadedLockableScore`

In 56b07e52aabdaca521987e765f1fa864966a5d49 we made
`MultiThreadedLockableScore` fully bindings-compatible. However, it
did not add a `WriteableScore` implementation for it. This was an
oversight as it is a `WriteableScore` in Rust and needs to be for
use in other parts of the API.

Here we add the required impl in a way that the bindings generator
is able to handle it and add conversion utilities.

Add logging in route hint filtering

Knowing why a channel was not included as an invoice route hint can be
valuable. Add logging on the decisions made when filtering channels.

Merge pull request #1748 from valentinewallace/2022-10-custom-oms

Support custom onion messages

Disallow sending invalid custom OM TLVs

Onion message data TLV types must be >= 64, enforce this on send

Implement sending and receiving custom onion messages

This uses the work done in the preceding commits to implement encoding a user's
custom TLV in outbound onion messages, and decoding custom TLVs in inbound
onion messages, to be provided to the new CustomOnionMessageHandler.

Merge pull request #1678 from TheBlueMatt/2022-08-funding-locked-mon-persist-fail

Handle async initial ChannelMonitor persistence failing on restart

Rename `ChannelState::MonitorUpdateFailed` `MonitorUpdateInProgress`

As we're moving towards monitor update async being a supported
use-case, we shouldn't call an async monitor update "failed", but
rather "in progress". This simply updates the internal channel.rs
enum name to reflect the new thinking.

Handle async initial ChannelMonitor persistence failing on restart

If the initial ChannelMonitor persistence is done asynchronously
but does not complete before the node restarts (with a
ChannelManager persistence), we'll start back up with a channel
present but no corresponding ChannelMonitor.

Because the Channel is pending-monitor-update and has not yet
broadcasted its initial funding transaction or sent channel_ready,
this is not a violation of our API contract nor a safety violation.
However, the previous code would refuse to deserialize the
ChannelManager treating it as an API contract violation.

The solution is to test for this case explicitly and drop the
channel entirely as if the peer disconnected before we received
the funding_signed for outbound channels or before sending the
channel_ready for inbound channels.

Merge pull request #1769 from TheBlueMatt/2022-10-disconnected-hints

Include all channel route hints if no connected channels exist

Merge pull request #1764 from G8XSU/rgs-ignore-error

Ignore Duplicate Gossip Error while updating networkGraph from RGS

Merge pull request #1777 from lexe-tech/max/best-block-header-best-block

Add `.to_best_block()` method to `ValidatedBlockHeader`

Merge pull request #1689 from wpaulino/anchors-bump-channel-close-event

Clean up private channel route hint filtering

Add `ValidatedBlockHeader::to_best_block`

Include all channel route hints if no connected channels exist

Mobile clients often take a second or two before they reconnect to
their peers as its not always clear immediately that connections
have been killed (especially on iOS). This can cause us to
spuriously fail to include route hints in our invoices if we're on
mobile.

The fix is simple, if we're selecting channels to include in route
hints and we're not not connected to the peer for any of our
channels, we should simply include the hints for all channels, even
though we're disconencted.

Fixes #1768.

Add public helper to build anchor input witnesses

Add holder anchor signing support to BaseSign

Document expected call frequency of ChainMonitor::process_pending_events

Yield channel close bump events

Generate ClaimEvent for HolderFundingOutput inputs from anchor channels

Refactor generate_claim_tx to return OnchainClaim enum

Split finalize_package into separate methods per malleability

Track funding amount in HolderFundingOutput

This will be useful later on when determining the appropriate fee rate
to use on the anchor transaction to bump its commitment transaction.

Track whether HolderFundingOutput originated from an anchor channel

Store anchors option for supported output types

As we integrate the support of anchor outputs, we'll want to know if
each input we're working with came from an anchor outputs channel.
Instead of threading through a `opt_anchors` boolean across several
methods on `PackageSolvingData` and `PackageTemplate`, we decide to
store a reference in each `PackageSolvingData` variant instead that
features a change in behavior between channels with and without anchor
outputs.

Dedupe gossip msgs while updating networkGraph from RGS

While applying gossip info from RGS-server, number of harmless
errors might arise which should be ignored. E.g. client should not
fail if there is a duplicate gossip for same channel or duplicate
update.

Update send_onion_message API to take new OnionMessageContents enum

OnionMessageContents specifies the data TLV that the sender wants in the onion
message. This enum only has one variant for now, Custom. When offers are added,
additional variants for invoice, invoice_request, and invoice_error will be
added.

This commit does not actually implement sending the custom OM contents, just
the API change.

Fix accidental newline in OnionMessenger docs

Tweak OnionMessenger log on inbound onion message receipt

Parameterize OnionMessenger by new CustomOnionMessageHandler trait

OnionMessenger::new will now take a custom onion message handler trait
implementation. This handler will be used in upcoming commit(s) to handle
inbound custom onion messages.

The new trait also specifies what custom messages are supported via its
associated type, CustomMessage. This associated type must implement a new
CustomOnionMessagesContents trait, which requires custom messages to support
being written, being read, and supplying their TLV type.

Optionally parameterize decode_tlv_stream with custom decode closure

Useful for decoding custom or user-provided TLVs. See macro docs for more info.

Used in upcoming commit(s) to support custom onion message TLVs

ser: Add MaybeReadableArgs trait

Useful in decoding a custom message, so (a) the message type can be provided to
the handler and (b) None can be returned if the message type is unknown.

Used in upcoming commit(s) to support custom onion messages.

Merge pull request #1763 from gcomte/feature/derive-eq

Derive Eq for all structs that derive PartialEq

Merge pull request #1774 from futurepaul/disable-rustfmt

disable automatic formatting

disable all formatting

Derive Eq for all structs that derive PartialEq

Merge pull request #1765 from gcomte/refactor/remove-redundant-field-names

Remove redundant field names

Remove redundant field names

Merge pull request #1754 from TheBlueMatt/2022-10-better-liq-halflife-docs

Rewrite some documentation on `ProbabilisticScorer` and increase half-life to 6 hours.

Increase the default `liquidity_offset_half_life` to six hours

Even at relatively high payment volumes, decaying knowledge of each
individual channel every hour causes aggressive retrying of
channels as we quickly forget the state of a channel. Even with the
historical tracker, this isn't fully remedied, as we'll track the
history bounds with the decayed value.

Instead, we decay every six hours here, reducing how often we'll
retry a channel due to decay.

In addition to this, the decay likely needs to be substantially
more linear, as tracked in #1752.

Rewrite documentation some on `ProbabilisticScorer`

We had some user confusion on how the probabilistic scorer works,
especially in reference to the half-life parameter. This attempts
to clarify how the bounds work, and how they are decayed.

Merge pull request #1744 from tnull/2022-09-fix-bp-futures-doc

Fix `background-processor` doc build for `futures`

Add `futures` CI check

This adds testing of the `futures` feature to CI. In order to avoid
introducing a dependency on `std`, we switch to using the `futures-util`
crate directly enabling only a subset of features. To this end, we also
switch to using the `select_biased!` macro, which is equivalent to
`select!` except that it doesn't choose ready futures pseudo-randomly
at runtime.

Fix `background-processor` doc build for `futures`

Merge pull request #1756 from TheBlueMatt/2022-10-rgs-no-std

Fix `rapid-gossip-sync` `no-std` and properly test no-std in CI

Specify full import path in decode_tlv macro

Prevents unresolved import error

Merge pull request #1649 from dunxen/2022-08-implementnodefailure

Implement permanent node failure handling

Merge pull request #1693 from valentinewallace/2022-09-readme-updates

Fix outdated README sections

Merge pull request #1758 from TheBlueMatt/2022-10-fix-pre-notified-future

Fix (and test) `Future` creation after a `Notifier` was notified

Test a full `no-std` build in the `no-std-check` crate in CI

Rust is incredibly forgiving in attempts to access `std`, making it
rather difficult to test `no-std` properly. In practice, the only
decent way to do so is to actually build for a platform that does
not have `std`, which we do here by building the `no-std-check`
crate for `arm-thumbv7m-none-eabi`.

Merge pull request #1625 from TheBlueMatt/2022-07-history-tracking

Merge pull request #1751 from TheBlueMatt/2022-10-fix-score-log-direction

Correct the directionality of liquidity non-update messages

Merge pull request #1760 from TheBlueMatt/2022-10-invoice-builder-round

Fix outdated README sections

Remove and track perm failed nodes & channels

We never had the `NetworkGraph::node_failed` method implemented. The
scorer now handles non-permanent failures by downgrading nodes, so we
don't want that implemented.

The method is renamed to `node_failed_permanent` to explicitly indicate
that this is the only case it handles. We also add tracking in the form
of two maps as fields of `NetworkGraph`, namely, `removed_nodes` and
`removed_channels`. We track these removed graph entries to ensure we
don't just resync them right away from gossip soon after removing them.
We stop tracking these removed nodes whenever `remove_stale_channels_and_tracking()`
is called and the entries have been tracked for longer than
`REMOVED_ENTRIES_TRACKING_AGE_LIMIT_SECS` which is currently set to one
week.

Drop the subsecond part of timestamps when constructing invoices

We had a user who was confused why an invoice failed to round-trip
(i.e. was not `PartialEq` with itself after write/read) when a
subsecond creation time was used (e.g. via the `from_system_time`
constructor).

This commit should address this confusion by dropping subsecond
parts in easily-accessible constructors when creating BOLT 11
invoices.

Fixes #1759.

Support platforms with only 32-bit atomics

Given there is only one instance in our code of `AtomicU64` its
simplest to just remove it rather than try to add some kind of
wrapper.

Test `rapid-gossip-sync` in `no-std` in CI

Update `rapid-gossip-sync` docs to not reference `std`-only methods

Fix (and test) `Future` creation after a `Notifier` was notified

After a `Notifier` has been `notify`'d, attempts to `get_future`
should return a `Future` which is pre-completed, however this was
not the case.

This commit simply fixes the behavior, adding a test to demonstrate
the issue.

Decay historical liquidity tracking when no new data is added

To avoid scoring based on incredibly old historical liquidity data,
we add a new half-life here which is used to (very slowly) decay
historical liquidity tracking buckets.

Track a reference to scoring parameters in DirectedChannelLiquidity

This simplifies adding additional half lives in
DirectedChannelLiquidity by simply storing a reference to the full
parameter set rather than only the single current half-life.

Calculate a new penalty based on historical channel liquidity range

Our current `ProbabilisticScorer` attempts to build a model of the
current liquidity across the payment channel network. This works
fine to ignore channels we *just* tried to pay through, but it
fails to remember patterns over longer time horizons.

Specifically, there are *many* channels within the network that are
very often either fully saturated in one direction, or are
regularly rebalanced and rarely saturated. While our model may
discover that, when it decays its offsets or if there is a
temporary change in liquidity, it effectively forgets the "normal"
state of the channel.

This causes substantially suboptimal routing in practice, and
avoiding discarding older knowledge when new datapoints come in is
a potential solution to this.

Here, we implement one such design, using the decaying buckets
added in the previous commit to calculate a probability of payment
success based on a weighted average of recent liquidity estimates
for a channel.

For each min/max liquidity bucket pair (where the min liquidity is
less than the max liquidity), we can calculate the probability that
a payment succeeds using our traditional `amount / capacity`
formula. From there, we weigh the probability by the number of
points in each bucket pair, calculating a total probability for the
payment, and assigning a penalty using the same log-probability
calculation used for the non-historical penalties.

Track history of where channel liquidities have been in the past

This introduces two new fields to the `ChannelLiquidity` struct -
`min_liquidity_offset_history` and `max_liquidity_offset_history`,
both an array of 8 `u16`s. Each entry represents the proportion of
time that we spent with the min or max liquidity offset in the
given 1/8th of the channel's liquidity range. ie the first bucket
in `min_liquidity_offset_history` represents the proportion of time
we've thought the channel's minimum liquidity is lower than 1/8th's
the channel's capacity.

Each bucket is stored, effectively, as a fixed-point number with
5 bits for the fractional part, which is incremented by one (ie 32)
each time we update our liquidity estimates and decide our
estimates are in that bucket. We then decay each bucket by
2047/2048.

Thus, memory of a payment sticks around for more than 8,000
data points, though the majority of that memory decays after 1,387
data points.

Correct the directionality of liquidity non-update messages

When we log liquidity updates, if we decline to update anything as
the new bounds are already within the old bounds, the
directionality of the log entries was reversed.

While we're at it, we also log the old values.

Correct `rapid-gossip-sync` `no-std` build and test

While `rapid-gossip-sync` recently gained a `no-std` feature, it
didn't actually work, as there were still dangling references to
`std` and prelude assumptions. This makes `rapid-gossip-sync`
build (and test) properly in `no-std`.

Merge pull request #1106 from TheBlueMatt/2021-10-no-perm-err-broadcast

Do not broadcast commitment txn on Permanent mon update failure

Clarify ambiguous comment in persist methods

Rename APIError::MonitorUpdateFailed to MonitorUpdateInProgress

This much more accurately represents the error, indicating that a
monitor update is in progress asynchronously and may complete at a
later time.

Rename `handle_monitor_err!()` `handle_monitor_update_res!`

Rename `Channel::monitor_update_failed` to `monitor_updating_paused`

Add a TODO for an important issue for making async mon updates safe

If we receive a monitor event from a forwarded-to channel which
contains a preimage for an HTLC, we have to propogate that preimage
back to the forwarded-from channel monitor. However, once we have
that update, we're running in a relatively unsafe state - we have
the preimage in memory, but if we were to crash the forwarded-to
channel monitor will not regenerate the update with the preimage
for us. If we haven't managed to write the monitor update to the
forwarded-from channel by that point, we've lost the preimage, and,
thus, money!

Rework `chain::Watch` return types to make async updates less scary

When a `chain::Watch` `ChannelMonitor` update method is called, the
user has three options:
 (a) persist the monitor update immediately and return success,
 (b) fail to persist the monitor update immediately and return
     failure,
 (c) return a flag indicating the monitor update is in progress and
     will complete in the future.

(c) is rather harmless, and in some deployments should be expected
to be the return value for all monitor update calls, but currently
requires returning `Err(ChannelMonitorUpdateErr::TemporaryFailure)`
which isn't very descriptive and sounds scarier than it is.

Instead, here, we change the return type used to be a single enum
(rather than a Result) and rename `TemporaryFailure`
`UpdateInProgress`.

Merge pull request #1740 from TheBlueMatt/2022-09-invoice-bindings-nostd

Don't make references to `std` in `lightning-invoice` in bindings

Merge pull request #1742 from tnull/2022-09-remove-done-todo

Remove completed TODO

Don't make references to `std` in `lightning-invoice` in bindings

As we support `no-std` for `lightning-invoice` builds, we should
support them in `c_bindings` as well, which we add a test for in
CI here.

Remove done TODO

The migration to `LockTime` was already done in
7e05623befc111422d1d4230f4e51629566a2ae6, which however did not also
remove the TODO.

Merge pull request #1737 from TheBlueMatt/2022-09-future-trait

Add a bindings-only version of `Future::register_callback`

Add a bindings-only version of `Future::register_callback`

While we could, in theory, add support to the bindings logic to map
`Box<dyn Trait>`, there isn't a whole lot of use doing so when its
incredibly trivial to do directly.

This adds a trivial wrapper around `Future::register_callback` that
is only built in bindings and which is linked in the
`register_callback` docs for visibility.

Merge pull request #1734 from TheBlueMatt/2022-09-better-lock-name

Rename `MultiThreadedLockableScoreLock` `MultiThreadedScoreLock`

Rename `MultiThreadedLockableScoreLock` to `MultiThreadedScoreLock`

as the first is quite a mouthful, and the second isn't materially
less specific.

Merge pull request #1733 from TheBlueMatt/2022-09-downgrade-hashbrown

Downgrade `hashbrown` to meet MSRV

Merge pull request #1731 from valentinewallace/2022-09-router-test-utils-mod

Move router test utils into their own module

Downgrade `hashbrown` to meet MSRV

`hashbrown` depends on `ahash` which depends on `once_cell`. Sadly,
in https://github.com/matklad/once_cell/issues/201 the `once_cell`
maintainer decided they didn't want to do the work of having an
MSRV policy for `once_cell`, making `ahash`, and thus `hashbrown`
require the latest compiler. I've reached out to `ahash` to suggest
they drop the dependency (as they could trivially work around not
having it), but until then we simply downgrade `hashbrown`.

`rust-bitcoin` also requires an older `hashbrown` so we're actually
reducing our total `no-std` code here anyway.

Import util::test_utils as ::ln_test_utils in router

To disambiguate between util::test_utils and router::test_utils

Rename routing::router::test_utils to ::bench_utils

To disambiguate it from routing::test_utils

Merge pull request #1656 from ViktorTigerstrom/2022-08-forward-htlcs-as-standalone-lock

Move `forward_htlcs` into standalone lock

Move router test utils into their own module

Useful for testing onion message pathfinding in upcoming PRs and any future
routing modules we add

Add lock order docs to `ChannelManager` fields

Merge pull request #1729 from TheBlueMatt/2022-09-lockablescore-bindings

Add a `MutexGuard` wrapper for the bindings-only `LockableScore`

Merge pull request #1728 from TheBlueMatt/2022-09-slices-not-vecs

Swap `Vec<&RouteHop>` parameters for slices

Avoid returning a reference to a u64.

In c353c3ed7c40e689a3b9fb6730c6dabbd3c92cc5 an accessor method was
added which returns an `Option<&u64>`. While this allows Rust to
return an 8-byte object, returning a reference to something
pointer-sized is a somewhat strange API.

Instead, we opt for a straight `Option<u64>`, which is sadly
somewhat larger on the stack, but is simpler and already supported
in the bindings generation.

Swap `Vec<&RouteHop>` parameters for slices

In c353c3ed7c40e689a3b9fb6730c6dabbd3c92cc5, new scorer-updating
methods were added to the `Router` object, however they were
passed as a `Vec` of references. We use the list-of-references
pattern to make bindings simpler (by not requiring allocations per
entry), however there's no reason prefer to passing a `Vec` over
a slice, given the `Vec` doesn't hold ownership of the objects
anyway.

Add a `MutexGuard` wrapper for the bindings-only `LockableScore`

In the bindings, we don't directly export any `std` types. Instead,
we provide trivial wrappers around them which expose only a
bindings-compatible API (and which is code in-crate, where the
bindings generator can see it).

We never quite finished this for `MultiThreadedLockableScore` - due
to some limitations in the bindings generator and the way the
scores are used in `lightning-invoice`, the scoring API ended up
being further concretized in patches for the bindings. Luckily the
scoring interface has been rewritten somewhat, and it so happens
that we can now generate bindings with the upstream code.

The final piece of the puzzle is done here, where we add a struct
which wraps `MutexGuard` so that we can expose the lock for
`MultiThreadedLockableScore`.