Merge pull request #1916 from valentinewallace/2022-11-chanman-payment-retries

`ChannelManager` Payment Retries

Merge pull request #1948 from alecchendev/custom-fail-back-err

Allow specifying an error when failing back HTLC

Merge pull request #1799 from TheBlueMatt/2022-10-heap-nerdsnipe

Router Optimizations

Add test_fail_htlc_backwards_with_reason

Add a test for newly added function failing back a basic payment
and ensuring the intended failure code and data are sent back
to the peer.

Add FailureCode enum and ChannelManager::fail_htlc_backwards_with_reason

FailureCode is used to specify which error code and data to send
to peers when failing back an HTLC.

ChannelManager::fail_htlc_backwards_with_reason
allows a user to specify the error code and
corresponding data to send to peers when failing back an HTLC.
This function is mentioned in Event::PaymentClaimable docs.
ChannelManager::get_htlc_fail_reason_from_failure_code was also
added to assist with this function.

Disambiguate send_payment_internal from pay_internal

Payment retries: copy tests from InvoicePayer

As part of migrating payment retries from InvoicePayer to ChannelManager,
several tests don't need a rewrite and can be pretty much copied and pasted.

Test ChannelManager automatic retries

Support sending payments with a retry strategy in ChannelManager

Retry HTLCs in process_pending_htlc_forwards

Remove AllPathsFailed outbounds at send_payment_internal callsites instead

This makes it easier to retry payments if all paths fail on initial send, in
in which case we'll want to hold off on removing the pending payment

Generate PendingHTLCsForwardable upon retryable payment

Decode onion fail outside of outbound_payments lock

It's not ideal to do all this computation while the lock is held. We also want
to decode the failure *before* taking the lock, so we can store the failed scid
in the relevant outbound for retry in the next commit(s).

Store retry data in PendingOutboundPayment::Retryable

Used in upcoming commit(s) to automatically retry HTLCs in ChannelManager

Clean up `compute_fees` and add a saturating variant

Often when we call `compute_fees` we really just want it to
saturate and we deal with `u64::max_value` later. In that case,
we're much better off doing the saturating in the `compute_fees` as
it can use CMOVs rather than branching at each step and then
`unwrap_or`ing at the callsite.

Add a fuzzer to check that `IndexedMap` is equivalent to `BTreeMap`

Swap `IndexedMap` implementation for a `HashMap`+B-Tree

Our network graph has to be iterable in a deterministic order and
with the ability to iterate over a specific range. Thus,
historically, we've used a `BTreeMap` to do the iteration. This is
fine, except our map needs to also provide high performance lookups
in order to make route-finding fast. Sadly, `BTreeMap`s are quite
slow due to the branching penalty.

Here we replace the implementation of our `IndexedMap` with a
`HashMap` to store the elements itself and a `BTreeSet` to store
the keys set in sorted order for iteration.

As of this commit on the same hardware as the above few commits,
the benchmark results are:

```
test routing::router::benches::generate_mpp_routes_with_probabilistic_scorer ... bench: 109,544,993 ns/iter (+/- 27,553,574)
test routing::router::benches::generate_mpp_routes_with_zero_penalty_scorer  ... bench:  81,164,590 ns/iter (+/- 55,422,930)
test routing::router::benches::generate_routes_with_probabilistic_scorer     ... bench:  34,726,569 ns/iter (+/- 9,646,345)
test routing::router::benches::generate_routes_with_zero_penalty_scorer      ... bench:  22,772,355 ns/iter (+/- 9,574,418)
```

Add a new `IndexedMap` type and use it in network graph storage

Our network graph has to be iterable in a deterministic order and
with the ability to iterate over a specific range. Thus,
historically, we've used a `BTreeMap` to do the iteration. This is
fine, except our map needs to also provide high performance lookups
in order to make route-finding fast. Sadly, `BTreeMap`s are quite
slow due to the branching penalty.

Here we replace the `BTreeMap`s in the scorer with a dummy wrapper.
In the next commit the internals thereof will be replaced with a
`HashMap`-based implementation.

Drop A* implementation in the router for simple Dijkstra's

As evidenced by the previous commit, it appears our A* router
does worse than a more naive approach. This isn't super surpsising,
as the A* heuristic calculation requires a map lookup, which is
relatively expensive.

```
test routing::router::benches::generate_mpp_routes_with_probabilistic_scorer ... bench: 169,991,943 ns/iter (+/- 30,838,048)
test routing::router::benches::generate_mpp_routes_with_zero_penalty_scorer  ... bench: 122,144,987 ns/iter (+/- 61,708,911)
test routing::router::benches::generate_routes_with_probabilistic_scorer     ... bench:  48,546,068 ns/iter (+/- 10,379,642)
test routing::router::benches::generate_routes_with_zero_penalty_scorer      ... bench:  32,898,557 ns/iter (+/- 14,157,641)
```

Merge pull request #1983 from valentinewallace/2022-01-update-contributingmd

Merge pull request #1878 from dunxen/2022-11-config-minfinalcltvexpiry

Allow configurable `min_final_cltv_expiry_delta`

contributing.md: fix link and link to CoC

Merge pull request #1967 from arik-so/2023-01-rename-signer-traits

Split out `EcdsaChannelSigner` method from `BaseSign`, and rename it to `ChannelSigner`

Parameterize add_new_pending_payment with retry strategy and route params

Copy Retry from invoice module to outbound_payment module

Also configure it such that in std tests, it will use SinceEpoch instead of
Instant so time can be manually advanced.

Add new payment type and metadata bytes

Adds two new payment `Method`s for identifying payments with custom
`min_final_cltv_expiry_delta` as payments with LDK or user payment
hashes.

The `min_final_cltv_expiry_delta` value is packed into the first 2
bytes of the expiry timestamp in the payment secret metadata.

Add `min_final_cltv_expiry` parameter to invoice utils

All utility functions for invoice construction will now also accept an
Option<>al `min_final_cltv_expiry_delta` which is useful for things like
swaps etc. The `min_final_cltv_expiry_delta` will default back to
`MIN_FINAL_CLTV_EXPIRY_DELTA` if `None` is provided.

Add `_delta` suffix to `min_final_cltv_expiry`

This matches the spec and helps avoid any confusion around
naming. We're also then consistent with `cltv_expiry` in an HTLC being
the actual block height value for the CLTV and not a delta.

Make `Channel` and `ChannelManager` less particular about their `Signer` type.

Rename `Sign` to `WriteableEcdsaChannelSigner`.

Separate channel-type-agnostic methods into `ChannelSigner` trait.

Rename `BaseSign` to `EcdsaChannelSigner`.

Merge pull request #1926 from jkczyz/2022-12-invoice

BOLT 12 `invoice` encoding and building

Copy PaymentAttempts from invoice module to outbound_payment module

Fix unused_imports warning in no-std tests

Invoice parsing tests

Tests for checking invoice semantics when parsing invoice bytes as
defined by BOLT 12.

Invoice building tests

Tests for checking invoice message semantics when building an invoice as
defined by BOLT 12.

Expand invoice module docs and include an example

Use SystemTime::now() for Invoice creation time

For std builds, Invoice::created_at can be automatically set upon
construction using SystemTime::now() offset by SystemTime::UNIX_EPOCH.
Change InvoiceRequest::respond_with and Refund::respond_with to only
take a created_at parameter in no-std builds.

Builder for creating invoices for refunds

Add a builder for creating invoices for a refund and required fields.
Other settings are optional and duplicative settings will override
previous settings. Building produces a semantically valid `invoice`
message for the refund, which then can be signed with the key associated
with the provided signing pubkey.

Builder for creating invoices for offers

Add a builder for creating invoices for an offer from a given request
and required fields. Other settings are optional and duplicative
settings will override previous settings. Building produces a
semantically valid `invoice` message for the offer, which then can be
signed with the key associated with the offer's signing pubkey.

Invoice encoding and parsing

Define an interface for BOLT 12 `invoice` messages. The underlying
format consists of the original bytes and the parsed contents.

The bytes are later needed for serialization. This is because it must
mirror all the `offer` and `invoice_request` TLV records, including
unknown ones, which aren't represented in the contents.

Invoices may be created for an Offer (from an InvoiceRequest) or for a
Refund. The primary difference is how the signing pubkey is given -- by
the writer of the offer or the reader of the refund.

Update min-inbound-fee values on `NetworkGraph` load

Historically we've had various bugs in keeping the
`lowest_inbound_channel_fees` field in `NodeInfo` up-to-date as we
go. This leaves the A* routing less efficient as it can't prune
hops as aggressively.

In order to get accurate benchmarks, this commit updates the
minimum-inbound-fees field on load. This is not the most efficient
way of doing so, but suffices for fetching benchmarks and will be
removed in the coming commits.

Note that this is *slower* than the non-updating version in the
previous commit. While I haven't dug into this incredibly deeply,
the graph snapshot in use has min-fee info for only 9,618 of
20,818 nodes. Thus, it is my guess that with the graph snapshot
as-is the branch predictor is able to largely remove the A*
heuristic lookups, but with this change it is forced to wait for
A* heuristic map lookups to complete, causing a performance
regression.

```
test routing::router::benches::generate_mpp_routes_with_probabilistic_scorer ... bench: 182,980,059 ns/iter (+/- 32,662,047)
test routing::router::benches::generate_mpp_routes_with_zero_penalty_scorer  ... bench: 151,170,457 ns/iter (+/- 75,351,011)
test routing::router::benches::generate_routes_with_probabilistic_scorer     ... bench:  58,187,277 ns/iter (+/- 11,606,440)
test routing::router::benches::generate_routes_with_zero_penalty_scorer      ... bench:  41,210,193 ns/iter (+/- 18,103,320)
```

Update the lightning graph snapshot used in benchmarks

The previous copy was more than one and a half years old, the
lightning network has changed a lot since!

As of this commit, performance on my Xeon W-10885M with a
SK hynix Gold P31 storing a BTRFS volume is as follows:

```
test ln::channelmanager::bench::bench_sends                                  ... bench:   5,896,492 ns/iter (+/- 512,421)
test routing::gossip::benches::read_network_graph                            ... bench: 1,645,740,604 ns/iter (+/- 47,611,514)
test routing::gossip::benches::write_network_graph                           ... bench: 234,870,775 ns/iter (+/- 8,301,775)
test routing::router::benches::generate_mpp_routes_with_probabilistic_scorer ... bench: 166,155,032 ns/iter (+/- 30,206,162)
test routing::router::benches::generate_mpp_routes_with_zero_penalty_scorer  ... bench: 136,843,661 ns/iter (+/- 67,111,218)
test routing::router::benches::generate_routes_with_probabilistic_scorer     ... bench:  52,954,598 ns/iter (+/- 11,360,547)
test routing::router::benches::generate_routes_with_zero_penalty_scorer      ... bench:  37,598,126 ns/iter (+/- 17,262,519)
test bench::bench_sends                                                      ... bench:  37,760,922 ns/iter (+/- 5,179,123)
test bench::bench_reading_full_graph_from_file                               ... bench:      25,615 ns/iter (+/- 1,149)
```

Merge pull request #1951 from wpaulino/remove-get-node-secret

Merge pull request #1964 from TheBlueMatt/2023-01-no-debug-panics

Use test/_test_utils to enable single-threaded debug assertions

Remove NodeSigner::get_node_secret

Secrets should not be exposed in-memory at the interface level as it
would be impossible the implement it against a hardware security
module/secure element.

Use NodeSigner::ecdh to compute SharedSecrets

Sign gossip messages with NodeSigner

Add NodeSigner::sign_gossip_message

Adds signing capability to NodeSigner for all gossip messages that
require a node signature.

Merge pull request #1860 from wpaulino/open-channel-anchors-support

Support opening anchor channels and test end-to-end unilateral close

Remove unused NodeSigner implementations in tests

These implementations have every method panic, so assuming that the test
suite passes, these implementations are never used.

Always set `_test_utils` when building lightning for some tests

This ensures that we hit additional assertions which are intended
to always be run in tests.

Add test yielding anchor-related events

Add mine_transactions test util

Support negotiating anchors throughout channel open

Encoding for TLV stream without signature records

When using bytes from an InvoiceRequest to constructing bytes for an
Invoice, any signature TLV records in the bytes must be excluded. Define
a wrapper for encoding such pre-serialized bytes in this manner. This
will allow the forthcoming InvoiceBuilder to construct bytes for an
Invoice properly.

Define TlvStream::skip_signatures

Provide a helper for skipping signature TLV records from a TLV stream.
This prevents needing to duplicate the check for signature TLV records
when writing a TLV stream without signatures in an upcoming commit.

Drop AsRef<[u8]> implementation for TlvRecord

Explicitly using TlvRecord::record_bytes makes reading the code more
obvious than hiding which bytes are used in AsRef<[u8]>::as_ref.

Merge pull request #1956 from TheBlueMatt/2023-01-ser-cleanups

Trivial Serialization Tweaks

Merge pull request #1968 from lexe-tech/max/net-tokio-no-arc

lightning-net-tokio: Don't require `Arc<PeerManager>`

lightning-net-tokio: Don't require `Arc<PeerManager>`

Merge pull request #1962 from TheBlueMatt/2023-01-bp-no-std

Use the user-provided `SleepFuture` for interval checks in `background-processor`

Use `test`/`_test_utils` to enable single-threaded debug assertions

We have a number of debug assertions which are expected to never
fire when running in a single thread. This is just fine in tests,
and gives us good coverage of our lockorder requirements, but is
not-irregularly surprising to users, who may run with their own
debug assertions in test environments.

Instead, we gate these checks by the `cfg(test)` setting as well as
the `_test_utils` feature, ensuring they run in our own tests, but
not downstream tests.

Always set `_test_utils` when building lightning for some tests

This ensures that we hit additional assertions which are intended
to always be run in tests.

Merge pull request #1960 from tnull/2023-01-deref-router-in-invoicepayer

Make `InvoicePayer`'s `Router` `Deref`

Merge pull request #1957 from TheBlueMatt/2022-01-mon-ref-lockorder

Pass MonitorUpdates by ref and tweak manager lockorder

Define option_anchors_zero_fee_htlc_tx feature bit

Fix stale reference to BaseSign::ready_channel

Add missing space in DebugTx logging

Use a variable-length integer for many serialization wrappers

The lightning protocol uses u16s for lengths in most cases. As our
serialization framework primarily targets that, we must as well.
However, because we may serialize objects that have  more than 65K
entries, we want to be able to store larger values. Thus, we define
a variable length integer here which is backwards-compatible but
treats 0xffff as "read eight more bytes".

This doesn't address any specific known issue, but feels like good
practice just in case.

Make `background-processor` no-std-friendly (ish)

This makes `background-processor` build without `std` at all. This
isn't particularly useful in the general no-std case as
`background-processor` is only useful with the `futures` feature,
and async will generally need `std` in some way or another. Still,
it ensures we don't end up reintroducing a dependency on the
current time, which breaks `wasm` use-cases.

Merge pull request #1955 from TheBlueMatt/2023-01-1950-message-text

Fix link text in `reply_short_channel_ids_end`

Merge pull request #1963 from lexe-tech/max/derive-debug

derive `Debug` for `ConfirmationTarget`

derive `Debug` for `ConfirmationTarget`

Merge pull request #1959 from danielgranhao/stop-passing-init-features-in-msg-handlers

Stop passing `InitFeatures` in msg handlers

Merge pull request #1939 from TheBlueMatt/2022-01-fuzz-hashbrown

Misc fuzzing tweaks

Use the user-provided `SleepFuture` for interval checks in BP

`background-processor` does a number of jobs on various timers.
Instead of doing those by interrogating `std::time::Instant`, this
change swaps to using the existing user-provided sleep future.

Fixes #1864.

Use flexible timer types in background processor's regular jobs

`background-processor` does a number of jobs on various timers.
Currently, those are all done by checking the timers every 100ms
by interrogating `std::time::Instant`. This is fine for the
threaded version, but we'd like more flexibility in the `futures`-
based `background-processor`.

Here we swap the `std::time::Instant` interrogation for a lambda
which we will switch out to the user-provided sleeper in the next
commit.

Make `InvoicePayer`'s `Router` `Deref`

As of HEAD the `ChannelManager` is parametrized by a `Router`, while
`InvoicePayer` also owns a `Router`. In order to allow for a single
object being reused, we make the `InvoicePayer` side `Deref`.

Stop passing `InitFeatures` in msg handlers

Swap per_peer_state lock order

Pass monitor updates by reference, not owned

In the next commit(s) we'll start holding `ChannelMonitorUpdate`s
that are being persisted in `Channel`s until they're done
persisting. In order to do that, switch to applying the updates by
reference instead of value.

Use `ChannelUnavailable` for a peer disconnecting not `MisuseError`

This fixes a crash in the `full_stack_target` fuzz test (found by
Chaincode's generous fuzzing infrastructure!) but ultimately is a
better error code - a peer disconnecting before we can fund a
channel isn't a "misuse error" its an unavailable channel.

Make fuzz assertions explicit in Cargo.toml

Do not rely on auto-deref'ing when aaccessing a `Hash{Map,Set}`

In newer versions of `hashbrown` this code would be broken. While
we aren't updating `hashbrown` any time soon (as it requires an
MSRV bump), it is useful to swap for a newer `hashbrown` when
fuzzing, which this makes easier.

Switch to hashbrown in fuzzing

hashbrown by default uses ahash, which may be a bit faster, but
more importantly, if we upgrade to hashbrown 0.13/ahash 0.8 we can
make it use a constant randomization factor, making fuzzers happier.

Bump fuzz `afl` dependency to latest upstream version

Convert `Vec` de/serialization impl to a macro and impl for tuples

...to make it easier to add new implementations and implement it
for all tuples which implement `Readabe` + `Writeable`. Note that
we don't want to just convert to a blanket implementation as we'd
really like to keep our optimized `Vec<u8>` wrapper or we'll end
up spinning way too much when writing vecs of bytes.

Add support for including `ignorable` types in enum de/ser macros

An enum implements de/serialization via
`impl_writeable_tlv_based_enum_upgradable` currently cannot contain
an object that only implements `MaybeReadable`.

This solves that by implementing the required blocks for
`ignorable`, opting to return `Ok(None)` in the top-level read in
cases where the inner field read returns `Ok(None)`.

Implement (de)serialization for BTreeMap same as HashMap

Fix link text in `reply_short_channel_ids_end`

Merge pull request #1950 from tnull/2023-01-fix-doc-warnings-and-nits

Fix doc warnings and doc cleanup in `msgs.rs`/`ser.rs`

Merge pull request #1946 from wpaulino/init-features-user-config

Use UserConfig to determine advertised InitFeatures by ChannelManager

Merge pull request #1953 from arik-so/2023-01-debug-gossip-heisenbug

Allow manually passing a timestamp to `channel_failed`. Fixes #1914.

Add error messages to stale gossip cleanup assertions.

Should help debug #1914.

Use UserConfig to determine advertised InitFeatures by ChannelManager

This is purely a refactor that does not change the InitFeatures
advertised by a ChannelManager. This allows users to configure which
features should be advertised based on the values of `UserConfig`. While
there aren't any existing features currently leveraging this behavior,
it will be used by the upcoming anchors_zero_fee_htlc_tx feature.

The UserConfig dependency on provided_init_features caused most
callsites of the main test methods responsible for opening channels to
be updated. This commit foregos that completely by no longer requiring
the InitFeatures of each side to be provided to these methods. The
methods already require a reference to each node's ChannelManager to
open the channel, so we use that same reference to obtain their
InitFeatures. A way to override such features was required for some
tests, so a new `override_init_features` config option now exists on
the test harness.

Merge pull request #1930 from arik-so/2022-12-remove-keysinterface

Remove KeysInterface

Fix misc. warnings from `--document-private-items`