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

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.

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.

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`.

Remove `forward_htlc` after `channel_state` lock order

The `forward_htlc` was prior to this commit only held at the same time
as the `channel_state` lock during the write process of the
`ChannelManager`. This commit removes the lock order dependency, by
taking the `channel_state`lock temporarily during the write process.

Remove unnecessary aquiring of the `channel_state` lock

Move `forward_htlcs` into standalone lock

As we are eventually removing the `channel_state` lock, this commit
moves the `forward_htlcs` map out of the `channel_state` lock, to ease
that process.

Merge pull request #1725 from TheBlueMatt/2022-09-no-bench-lockorder

Stop building with lockorder debugging in benchmarks

Merge pull request #1694 from jurvis/jurvis/2022-08-move-scorer-from-router

Move `LockableScore` requirement away from `Router` trait

Move Scorer requirement away from Router trait

We do this to enable users to create routers that do not need a scorer.
This can be useful if they are running a node the delegates pathfinding.

* Move `Score` type parameterization from `InvoicePayer` and `Router` to
`DefaultRouter`
* Adds a new field, `scorer`, to `DefaultRouter`
* Move `AccountsForInFlightHtlcs` to `DefaultRouter`, which we
will use to wrap the new `scorer` field, so scoring only happens in
`DefaultRouter` explicitly.
* Add scoring related functions to `Router` trait that we used to call
directly from `InvoicePayer`.
* Instead of parameterizing `scorer` in `find_route`, we replace it with
inflight_map so `InvoicePayer` can pass on information about inflight
HTLCs to the router.
* Introduced a new tuple struct, InFlightHtlcs, that wraps functionality
for querying used liquidity.

Stop building with lockorder debugging in benchmarks

`cargo bench` sets `#[cfg(test)]` so our current checks for
enabling our lockorder debugging end up matching when we're trying
to build performance benchmarks.

This adds explicit checks to our debug_lockorder logic to filter
out `feature = "_bench_unstable"` builds.

Do not broadcast commitment txn on Permanent mon update failure

See doc updates for more info on the edge case this prevents, and
there isn't really a strong reason why we would need to broadcast
the latest state immediately. Specifically, in the case of HTLC
claims (the most important reason to ensure we have state on chain
if it cannot be persisted), we will still force-close if there are
HTLCs which need claiming and are going to expire.

Surprisingly, there were no tests which failed as a result of this
change, but a new one has been added.

Merge pull request #1708 from tnull/2022-09-rgs-unpub-modules

Improve RGS documentation

Add `no-std` support for RGS

Rework RGS crate-level docs

Merge pull request #1707 from TheBlueMatt/2022-09-no-global-features

Move supported-feature-set logic into the supporting modules

Assert that all defined features are in the known features set

Now that the features contexts track the full set of all known
features, rather than the set of supported features, all defined
features should be listed in the context definition macro.

This adds a compile-time assertion to check that all bits for known
features are set in the context known set.

Stop tracking feature bits as known or required in features.rs

Now that the `*Features::known` constructor has been removed, there
is no reason to define feature bits as either optional required in
`features.rs` - that logic now belongs in the modules that are
responsible for the given features.

Instead, we only list all features in each context.

Remove the `*Features::known` constructor

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we (finally) remove the `known` constructor entirely,
modifying tests in the `features` module as required.

Remove all remaining references to `*Features::known`

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

In anticipation of removing the `known` constructor, this commit
removes all remaining references to it outside of features.rs.

Stop relying on `*Features::known` in fuzzing tests

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in our fuzz tests.

Stop relying on `*Features::known` in BP and persister tests

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in the
`lightning-background-processor` and `lightning-persister` crate
tests.

Stop relying on the `*Features::known` method in net-tokio

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in the
`lightning-net-tokio` crate.

Stop relying on the `*Features::known` method in lightning-invoice

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in the
`lightning-invoice` crate.

Stop relying on `*Features::known` in channel{,manager}.rs

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in the channel modules.

Stop relying on `*Features::known` in functional test utils

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in the
functional_test_utils module.

Stop relying on the `*Features::known` method in functional tests

This diff is commit, like the last, stops relying on the `known`
feature set constructor, doing so entirely with import changes and
sed rules.

Stop relying on the `*Features::known` method in `routing` tests

As we move towards specify supported/required feature bits in the
module(s) where they are supported, the global `known` feature set
constructors no longer make sense.

Here we stop relying on the `known` method in the `routing` module,
which was only used in tests.

List supported/required feature bits explicitly in ChannelManager

Historically, LDK has considered the "set of known/supported
feature bits" to be an LDK-level thing. Increasingly this doesn't
make sense - different message handlers may provide or require
different feature sets.

In a previous PR, we began the process of transitioning with
feature bits sent to peers being sourced from the attached message
handler.

This commit makes further progress by moving the concept of which
feature bits are supported by our ChannelManager into
channelmanager.rs itself, via the new `provided_*_features`
methods, rather than in features.rs via the `known_channel_features`
and `known` methods.

Merge pull request #1721 from acid-bit/fix_typo

Fix typo in comment in Cargo.toml

Merge pull request #1720 from TheBlueMatt/2022-09-fix-fuzz-warnings

Fix compile-time warnings in fuzzing

Fix typo in comment in Cargo.toml

Fix warnings in fuzz which should have been fixed in f725c5a90a11e6

Fix compile warning in fuzzing introduced in cd0d19c005ee4fa11de93a

Merge pull request #1685 from wpaulino/anchors-prep

Merge pull request #1717 from TheBlueMatt/2022-09-req-features-in-handlers

Move checking of specific require peer feature bits to handlers

Merge pull request #1706 from jkczyz/2022-09-filtered-blocks

Support filtered blocks in `lightning-block-sync`

Update anchors test vectors to zero HTLC transaction fee variant

Each test featuring HTLCs had a minimum and maximum feerate case. This
is no longer necessary for the zero HTLC transaction anchors variant as
the commitment feerate does not impact whether HTLCs can be trimmed or
not, only the dust limit does.

Account for zero fee HTLC transaction within dust limit calculation

With the zero fee HTLC transaction anchors variant, HTLCs can no longer
be trimmed due to their amount being too low to have a mempool valid
HTLC transaction. Now they can only be trimmed based on the dust limit
of each party within the channel.

Update HTLC script detection to check for anchor output variants

Use zero fee HTLC transactions for anchor channels

This is based on the assumption that we only support the zero HTLC
transaction fee variant of anchor channels.

Exclude HTLC transactions from broadcast on anchor channels

HTLC transactions from anchor channels are constrained by a CSV of 1
block, so broadcasting them along with the unconfirmed commitment
tranasction will result in them being immediately rejected as premature.

Avoid commitment broadcast upon detected funding spend

There's no need to broadcast our local commitment transaction if we've
already seen a confirmed one as it'll be immediately rejected as a
duplicate/conflict.

This will also help prevent dispatching spurious events for bumping
commitment and HTLC transactions through anchor outputs (once
implemented in future work) and the dispatch for said events follows the
same flow as our usual commitment broadcast.

Use proper sighash flag for remote HTLCs with anchor outputs

Support filtered blocks in lightning-block-sync

Expand the BlockSource trait to allow filtered blocks now that
chain::Listen supports them (d629a7edb7241eee7fde9f5ccdf1c481d2d6297b).
This makes it possible to use BIP 157/158 compact block filters with
lightning-block-sync.

Merge pull request #1703 from TheBlueMatt/2022-09-badonion-first-check

Correctly handle BADONION onion errors

Add now-missing `unwrap`s on test calls to `peer_connected`.

Move checking of specific require peer feature bits to handlers

As we remove the concept of a global "known/supported" feature set
in LDK, we should also remove the concept of a global "required"
feature set. This does so by moving the checks for specific
required features into handlers.

Specifically, it allows the handler `peer_connected` method to
return an `Err` if the peer should be disconnected. Only one such
required feature bit is currently set - `static_remote_key`, which
is required in `ChannelManager`.

Swap some `peer_connected` features to `known` from `empty` in test

In the next commit we'll enforce counterparty `InitFeatures`
matching our required set in `ChannelManager`, implying they must
be set for many tests where they previously did not need to be (as
they were enforced in `PeerManager`, which is not used in
functional tests).

Add a note that `peer_disconnected` impls must be idempotent

It appears our code is already correct here, but its also nice to
add a quick safety check in `channel.rs` which ensures we will
remain idempotent.

Add test for malformed update error with NODE bit set

Some tweaks by Matt Corallo <git@bluematt.me>

Correctly handle BADONION onion errors

Currently we entirely ignore the BADONION bit when deciding how to
handle HTLC failures. This opens us up to an attack where a
malicious node always fails HTLCs backwards via
`update_fail_malformed_htlc` with an error code of
`BADONION|NODE|PERM|X`. In this case, we may decide to interpret
this as a permanent node failure for the node encrypting the onion,
i.e. the counterparty of the node who sent the
`update_fail_malformed_htlc` message and ultimately failed the
HTLC.

Thus, any node we route through could cause us to fully remove its
counterparty from our network graph. Luckily we do not do any
persistent tracking of removed nodes, and thus will re-add the
removed node once it is re-announced or on restart, however we are
likely to add such persistent tracking (at least in-memory) in the
future.

Merge pull request #1712 from TheBlueMatt/2022-09-111

Cut 0.0.111

Bump versions to lightning* 0.0.111 and lightning-invoice 0.19

Update release notes for 0.0.111

Merge pull request #1714 from TheBlueMatt/2022-09-111-bindings-discovered-cleanups

Small Cleanups Discovered during Bindings for 0.0.111

Merge pull request #1715 from TheBlueMatt/2022-09-fix-msg-send

Fix encryption of broadcasted gossip messages

Update `Simple*PeerManager` type aliases to support Onion Messages

Note that `SimpleArcPeerHandler` is also updated to not wrap
`IgnoringMessageHandler` in an `Arc`, as `IgnoringMessageHandler`
is already zero-sized.

Export error type instead of entire modules

Previously the `error` and `processing` modules have been `pub`, leading
to them being included in the docs, altough (almost) empty.

Instead, we now `pub use` the `GraphSyncError` directly, cleaning up the
docs.

Merge pull request #1716 from TheBlueMatt/2022-09-log-unreadable-type

Include the message type when we send unreadable gossip msg errors

Encrypt+MAC most P2P messages in-place

For non-gossip-broadcast messages, our current flow is to first
serialize the message into a `Vec`, and then allocate a new `Vec`
into which we write the encrypted+MAC'd message and header.

This is somewhat wasteful, and its rather simple to instead
allocate only one buffer and encrypt the message in-place.

Fix encryption of broadcasted gossip messages

In 47e818f198abafba01b9ad278582886f9007dac2, forwarding broadcasted
gossip messages was split into a separate per-peer message buffer.
However, both it and the original regular-message queue are
encrypted immediately when the messages are enqueued. Because the
lightning P2P encryption algorithm is order-dependent, this causes
messages to fail their MAC checks as the messages from the two
queues may not be sent to peers in the order in which they were
encrypted.

The fix is to simply queue broadcast gossip messages unencrypted,
encrypting them when we add them to the regular outbound buffer.

Drop unused type parameter on `BlindedRoute::new`

I'm not sure why rustc didn't complain about the unused parameter
or why we're allowed to get away without explicitly bounding the
`Sign` in the `KeysInterface`, but the current code requires all
`BlindedPath` construction to explicitly turbofish an unused type.

Add relevant `(C-not exported)` tags on OnionMessenger aliases

The "helpful" type aliases don't make sense for C bindings as all
generics are concretized anyway.

Inline generic bounds rather than using the `where` clause

The bindings generator is pretty naive in its generic resolution
and doesn't like `where` clauses for bounds that are simple traits.
This should eventually change, but for now its simplest to just
inline the relevant generic bounds.

Do not use blanket impls when building for `c_bindings`

The C bindings generator isn't capable of figuring out if a blanket
impl applies in a given context, and instead opts to always write
out any relevant impl's for a trait. Thus, blanket impls should be
disabled when building with `#[cfg(c_bindings)]`.

Rename `{Signed,}RawInvoice::hash` to avoid naming collisions

Now that `{Signed,}RawInvoice` implement the std `Hash` trait,
having a method called `hash` is ambiguous.

Instead, we rename the `hash` methods `signed_hash` to make it
clear that the hash is the one used for the purpose of signing the
invoice.