Probabilistic channel scoring

Add a Score implementation based on "Optimally Reliable & Cheap Payment
Flows on the Lightning Network" by Rene Pickhardt and Stefan Richter[1].
Given the uncertainty of channel liquidity balances, probability
distributions are defined based on knowledge learned from successful and
unsuccessful attempts. Then the negative log of the success probability
is used to determine the cost of routing a specific HTLC amount through
a channel.

[1]: https://arxiv.org/abs/2107.05322

Effective channel capacity for router and scoring

A channel's capacity may be inferred or learned and is used to make
routing decisions, including as a parameter to channel scoring. Define
an EffectiveCapacity for this purpose. Score::channel_penalty_msat takes
the effective capacity (less in-flight HTLCs for the same payment), and
never None. Thus, for hops given in an invoice, the effective capacity
is now considered (near) infinite if over a private channel or based on
learned information if over a public channel.

If a Score implementations needs the effective capacity when updating a
channel's score, i.e. in payment_path_failed or payment_path_successful,
it can access the channel's EffectiveCapacity via the NetworkGraph by
first looking up the channel and then specifying which direction is
desired using ChannelInfo::as_directed.

Benchmark zero-penalty scorer

Benchmark router using a scorer seeded with data

Scorers may have different performance characteristics after seeing
failed and successful paths. Seed the scorer with some random data
before executing the benchmark in order to exercise such behavior.

Add first_hops to generate_routes benchmarks

Passing first_hops to get_route increases the coverage of the benchmark
test. For scorers needing the sending node, it allows for using a single
scorer in the benchmark rather than re-initializing on each iteration.
As a consequence, the scorer can be seeded with success and failure
data.

Remove duplicate generate_routes benchmark code

Refactor generate_routes and generate_mpp_routes into a single utility
for benchmarking. The utility is parameterized with features in order to
test both single path and multi-path routing. Additionally, it is
parameterized with a Score to be used with other scorers.

Merge pull request #1234 from tnull/limit_max_cltv_delta

Limit maximum CLTV delta during routing

Merge pull request #1248 from naveensrinivasan/naveen/feat/update-readme

Docs: Updated README to include crates information

Limit maximum total CLTV expiry delta during routing.

Docs: Updated README to include crates information

Included crates information into README.

Merge pull request #1258 from lightningdevkit/dependabot/cargo/hex-0.4

Update hex requirement from 0.3 to 0.4

Fixed some typos

Update hex requirement from 0.3 to 0.4

Updates the requirements on [hex](https://github.com/KokaKiwi/rust-hex) to permit the latest version.
- [Release notes](https://github.com/KokaKiwi/rust-hex/releases)
- [Commits](https://github.com/KokaKiwi/rust-hex/compare/v0.3...v0.4.3)

---
updated-dependencies:
- dependency-name: hex
  dependency-type: direct:production
...

Signed-off-by: dependabot[bot] <support@github.com>

Merge pull request #1243 from naveensrinivasan/naveensrinivasan/dependabot

Enable Dependabot

Create dependabot.yml

Signed-off-by: naveen <172697+naveensrinivasan@users.noreply.github.com>

Merge pull request #1249 from tnull/fix_compile_warnings

Fix compiler warning during building/testing.

Fix unused return warning for 'transmute_copy'.

Merge pull request #1238 from TheBlueMatt/2022-01-lockorder-checks

Fix and test lockorder

Check lockorders in tests with a trivial lockorder tracker

Merge pull request #1229 from lightning-signer/2021-12-htlc-anchor-sighashtype

anchors: Fix SigHashType and weight calculations for anchors

Fixed comment on weight_received_htlc

Set opt_anchors for calls to CommitmentTransaction::new_with_auxiliary_htlc_data

Add anchor tests to outbound_commitment_test

Debit funder's output to cover anchors

Convert HTLC_{SUCCESS,TIMEOUT}_TX_WEIGHT to anchor-aware functions

Convert COMMITMENT_TX_BASE_WEIGHT to anchor-aware function

Add unit test coverage for package::weight_{offered,received}_htlc

make WEIGHT{_REVOKED,}_{OFFERED,RECEIVED}_HTLC functions with opt_anchors parameter

Isolated channelmonitor weight unit tests and added anchor loops

Set the SigHashType of remote htlc signatures w/ anchors to SinglePlusAnyoneCanPay

Fix some (non-bug) lock-order-inversions in tests

Make lockorder consistent in channelmanager

This resolves a lockorder inversion in
`ChannelManager::finalize_claims` where `pending_outbound_payments`
is locked after `pending_events`, opposite of, for example, the
lockorder in `ChannelManager::fail_htlc_backwards_internal` where
`pending_outbound_payments` is locked at the top of the
`HTLCSource::OutboundRoute` handling and then `pending_events` is
locked at the end.

Merge pull request #1013 from TheBlueMatt/2021-07-warning-msgs

Rely on Error/Warning message data lengths being correct

In https://github.com/lightning/bolts/pull/950, the (somewhat
strange) requirement that error messages be handled even if the
length field is set larger than the size of the package was
removed. Here we change the code to drop the special handling for
this, opting to just fail to read the message if the length is
incorrect.

Send `warning` instead of `error` when we incounter bogus gossip

Convert `shutdown` invalid script checks to warning messages

As required by the warning messages PR, we should simply warn our
counterparty in this case and let them try again, continuing to try
to use the channel until they tell us otherwise.

Send warning messages when appropriate in gossip handling pipeline

Handle sending and receiving warning messages

Add a new `WarningMessage` message to send and receive warnings

Merge pull request #1230 from lightning-signer/2021-01-invoice-bech32-dep

Do not turn on bech32/std by default for lightning-invoice

Do not turn on bech32/std by default for lightning-invoice

Merge pull request #1223 from lightning-signer/2021-12-invoice-nostd

Adapt lightning-invoice to no_std

Adapt lightning-invoice to no_std

Merge pull request #1226 from TheBlueMatt/2022-01-bindings-no-std

Support building `cfg=c_bindings` with `no-std`

Support building `cfg=c_bindings` with `no-std`

This will be needed for JavaScript bindings eventually.

Merge pull request #1220 from TheBlueMatt/2021-12-stale-update-gossip-log

Log gossip rejections due to stale channel_updates at GOSSIP level

Merge pull request #1225 from hackerrdave/update-repo-lightningdevkit

update repo name to use lightningdevkit

update repo name to use lightningdevkit

Merge pull request #1218 from TheBlueMatt/2021-12-minor-bindings-tweaks

Minor Bindings Tweaks

Log gossip rejections due to stale channel_updates at GOSSIP level

This further reduces noise at the TRACE level during initial gossip
sync.

Swap around generic argument ordering in InvoicePayer for bindings

The bindings generation really should support generic bounds other
than Deref::Target in where clauses, but currently does not. To
avoid needing to add support during the current release process,
we simply swap around the arguments to move them to the first <>
instead of the where.

Add a C-not exported tag to `NetGraphMsgHandler.network_graph`

Add a constructor to MultiThreadedLockableScore

...as otherwise the struct is rather useless.

Merge pull request #1217 from TheBlueMatt/2021-12-0.0.104

Cut 0.0.104

Swap around generic argument ordering in DefaultRouter for bindings

The bindings generation really should support default generic types
in where clauses, but currently does not. To avoid needing to add
support during the current release process, we simply swap around
the arguments to move them to the first <> instead of the where.

Bump versions to 0.0.104/invoice 0.12

Update CHANGELOG for 0.0.104

Merge pull request #1216 from valentinewallace/2021-12-preimage-getter

Add utility for retrieving an LDK payment preimage

Remove trailing whitespace in the FeeEstimator interface

inbound_payment: Add utility to get payment preimage given hash/secret

User-requested feature

inbound_payment: DRY verify method for use in getting preimage

in the next commit(s)

create_inbound_payment: warn about dup hashes

Leftover feedback from #1177

Salt inbound payment ExpandedKey

Leftover feedback from #1177

Merge pull request #1177 from valentinewallace/2021-11-derivable-payment-secret

Stop storing pending inbound payment data; instead make it derivable on receive

Add new invoice CreationError::InvalidAmount for use in checking `create_inbound_payment`

in an invoice creation utility. Note that if the error type of `create_inbound_payment` ever
changed, we'd be forced to update the invoice utility's callsite to handle the new error

Drop need to store pending inbound payments

and replace payment_secret with encrypted metadata

See docs on `inbound_payment::verify` for details

Also add min_value checks to all create_inbound_payment* methods

Add get_single_block to chacha20 module

In the next commit, we'll want to get a single block from a chacha stream that
takes a 16-byte nonce.

Macro-ize checking that the total value of an MPP's parts is sane

This DRY-ed code will be used in upcoming commits when we stop storing inbound
payment data

Add get_inbound_payment_key_material to KeysInterface

This will allow us to retrieve key material for encrypting/decrypting inbound
payment info, in upcoming commits

Merge pull request #1212 from TheBlueMatt/2021-12-timeout-graph

Add a method to prune stale channels from NetworkGraph

Automatically prune NetworkGraph of stale channels hourly in BP

Reject channel_update messages with timestamps too old or new

Because we time out channel info that is older than two weeks now,
we should also reject new channel info that is older than two
weeks, in addition to rejecting future channel info.

Add a method to prune stale channels from `NetworkGraph`

We define "stale" as "haven't heard an updated channel_update in
two weeks", as described in BOLT 7.

We also filter out stale channels at write-time for `std` users, as
we can look up the current time.

Drop `allow_wallclock_use` feature in favor of simply using `std`

Fixes #1147.

DRY up network_graph tests substantially with message creation fns

Merge pull request #1214 from TheBlueMatt/2021-12-fix-tokio-msrv-bump

Build no-std on 1.47 now that core2 supports it

Pin tokio to 1.14.0 in CI for older rustc's

Merge pull request #1148 from dunxen/2021-11-new-onion-errors

Add mpp_timeout and invalid_onion_payload descriptions

Merge pull request #1211 from ConorOkus/2021-11-add-max-conversion

Update docs to add max return value to conversion list

Merge pull request #1202 from TheBlueMatt/2021-12-fix-retries-races

Fix payment retry races and inform users when a payment fails

Make attempting to retry a succeeded payment an APIError, not Route

This is symmetric with the new failure once a payment is abandoned.

Use `Event::PaymentFailed` in `InvoicePayer` to remove retry count

This finally fixes the bug described in the previous commits where
we retry a payment after its retry count has expired due to early
removal of the payment from the retry count tracking map. A test is
also added which demonstrates the bug in previous versions and
which passes now.

Fixes #1164.

Expose an event when a payment has failed and retries complete

When a payment fails, a payer needs to know when they can consider
a payment as fully-failed, and when only some of the HTLCs in the
payment have failed. This isn't possible with the current event
scheme, as discovered recently and as described in the previous
commit.

This adds a new event which describes when a payment is fully and
irrevocably failed, generating it only after the payment has
expired or been marked as expired with
`ChannelManager::mark_retries_exceeded` *and* all HTLCs for it
have failed. With this, a payer can more simply deduce when a
payment has failed and use that to remove payment state or
finalize a payment failure.

Add a variant to `PendingOutboundPayment` for retries-exceeded

When a payer gives up trying to retry a payment, they don't know
for sure what the current state of the event queue is.
Specifically, they cannot be sure that there are not multiple
additional `PaymentPathFailed` or even `PaymentSuccess` events
pending which they will see later. Thus, they have a very hard
time identifying whether a payment has truly failed (and informing
the UI of that fact) or if it is still pending. See [1] for more
information.

In order to avoid this mess, we will resolve it here by having the
payer give `ChannelManager` a bit more information - when they
have given up on a payment - and using that to generate a
`PaymentFailed` event when all paths have failed.

This commit adds the neccessary storage and changes for the new
state inside `ChannelManager` and a public method to mark a payment
as failed, the next few commits will add the new `Event` and use
the new features in our `PaymentRetrier`.

[1] https://github.com/lightningdevkit/rust-lightning/issues/1164

DRY up payment failure macros in functional_test_utils

... with a more extensible expectation-checking framework for them.

Add mpp_timeout and invalid_onion_payload descriptions & handling

Updates Fee estimator docs to include a max return value for get_est_sat_per_1000_weight

Updates docs to include a max return value for get_est_sat_per_1000_weight

Adds max to both conversions

Additional detail

Merge pull request #1169 from TheBlueMatt/2021-11-fix-update-announcements

Fix announcements of our own gossip

Add a comment describing the timestamp field's use

Merge pull request #1203 from lightning-signer/2021-12-value-to-self

Getter for the total channel balance

Merge pull request #1210 from TheBlueMatt/2021-12-new-codecod-upload

Upgrade to codecov uploader v2

Upgrade to codecov uploader v2

Some time ago codecov stopped supporting their old v1 uploader, and
it seems they've now finally turned it off, so we aren't getting
any coverage reports anymore. Hopefully upgrading is pretty trivial.

Merge pull request #1208 from TheBlueMatt/2021-12-less-force-close

Reduce force-closures with user fee estimators which round poorly

Merge pull request #1205 from TheBlueMatt/2021-12-new-feature-bit

Support the channel_type feature bit.

Reduce force-closures with user fee estimators which round poorly

See comment for more

Support the `channel_type` feature bit.

Note that this feature bit does absolutely nothing. We signal it
(as we already support channel type negotiation), but do not bother
to look to see if peers support it, as we don't care - we simply
look for the TLV entry and deduce if a peer supports channel type
negotiation from that.

The only behavioral change at all here is that we don't barf if a
peer sets channel type negotiation to required via the feature bit
(instead of failing the channel at open-time), but of course no
implementations do this, and likely won't for some time (if ever -
you can simply fail channels with unknown types later, and there's
no reason to refuse connections, really).

As defined in https://github.com/lightning/bolts/pull/906

Getter for the total channel balance

The existing balance getters subtract reserve, this one does not.

Merge pull request #1201 from jkczyz/2021-12-idempotent-channelmanager

Ensure ChannelManager methods are idempotent

Ensure ChannelManager methods are idempotent

During event handling, ChannelManager methods may need to be called as
indicated in the Event documentation. Ensure that these calls are
idempotent for the same event rather than panicking. This allows users
to persist events for later handling without needing to worry about
processing the same event twice (e.g., if ChannelManager is not
persisted but the events were, the restarted ChannelManager would return
some of the same events).