Tweak alignment and memory order in the `ProbabilisticScorer`

During routing, the majority of our time is spent in the scorer.
Given the scorer isn't actually doing all that much computation,
this means we're quite sensitive to memory latency. Thus, the cache
lines our data sits on is incredibly important.

Here, we manually lay out the `ChannelLiquidity` and
`HistoricalLiquidityTracker` structs to ensure that we can do the
non-historical scoring and skip historical scoring for channels
with insufficient data by just looking at the same cache line the
channel's SCID is on.

Sadly, to do the full historical scoring we need to load a second
128-byte cache line pair, but we have some time to get there. We
might consider issuing a preload instruction in the future.

This improves performance a few percent.

Cache the total points tracked in our historical liquidity data

When we go to score a channel using the historical liquidity data,
the first thing we do is step through all the valid bucket
combinations, multiply the min and max bucket, and then add them
together to calculate the total number of points tracked. This
isn't a free operation, and for scorers without much data it
represents a large part of the total time spent scoring during
routefinding.

Thus, here we cache this value, updating it every time the buckets
are updated.

Change the directed history tracker's storage of its direction

Rather than storing the two direction's buckets in
`HistoricalMinMaxBuckets` (renamed
`DirectedHistoricalLiquidityTracker`), we store a single reference
to the `HistoricalLiquidityTracker` as well as the direction bool.

This will allow us in the next commit to reference fields in the
`HistoricalLiquidityTracker` aside from the two directions.

Make the historical bucket data private to `bucketed_history`

In a comming commit we'll cache some additional data in the
historical bucket tracker. In order to do so, here we isolate the
buckets themselves into the `bucketed_history` module, reducing
the possibility of accidentally updating them directly without
updating caches.

Store both min and max historical buckets in one, new, struct

In the coming commits we'll isolate historical bucket logic slightly
further, allowing us to cache some state. This is the first step
towards that, storing the historical liquidity information in a new
`HistoricalLiquidityTracker` rather than in the general
`ChannelLiquidity`.

Format `log_approx.rs` per rustfmt

Move log approximation from `scoring.rs` to its own file

Merge pull request #3242 from jkczyz/2024-08-payment-id-auth-api

Add `PaymentId` authentication to public API

Add PaymentId authentication to public API

When receiving an InvoiceError message, it should be authenticated
before using it to abandon the payment. Add methods to PaymentId's
public API for constructing and verifying an HMAC for use in
OffersContext::OutboundPayment. This allows other implementations of
OffersMessageHandler to construct the HMAC and authenticate the message.

Merge pull request #3239 from arik-so/bitcoin-0.32.2-upgrade

Bitcoin 0.32.2 upgrade

Fix fuzz warnings.

Version 0.32.2 of `rust-bitcoin` deprecates a number of methods that
are commonly used in this project, most visibly `txid()`, which is
now called `compute_txid()`. This resulted in a lot of warnings, and
this commit is part of a series that seeks to address that.

Fix lightning-transaction sync warnings.

Version 0.32.2 of `rust-bitcoin` deprecates a number of methods that
are commonly used in this project, most visibly `txid()`, which is
now called `compute_txid()`. This resulted in a lot of warnings, and
this commit is part of a series that seeks to address that.

Fix lightning-block-sync warnings.

Version 0.32.2 of `rust-bitcoin` deprecates a number of methods that
are commonly used in this project, most visibly `txid()`, which is
now called `compute_txid()`. This resulted in a lot of warnings, and
this commit is part of a series that seeks to address that.

Fix lightning-background-processor warnings.

Version 0.32.2 of `rust-bitcoin` deprecates a number of methods that
are commonly used in this project, most visibly `txid()`, which is
now called `compute_txid()`. This resulted in a lot of warnings, and
this commit is part of a series that seeks to address that.

Fix lightning warnings.

Version 0.32.2 of `rust-bitcoin` deprecates a number of methods that
are commonly used in this project, most visibly `txid()`, which is
now called `compute_txid()`. This resulted in a lot of warnings, and
this commit is part of a series that seeks to address that.

Suppress Taproot warnings.

Taproot is not yet being actively used, and this commit suppresses
the noisy warning generation.

Remove secp256k1 dependency.

Upgrade rust-bitcoin to 0.32.2.

Merge pull request #3182 from valentinewallace/2024-07-expose-advance-bp

Expose blinded paths' `advance_path_by_one`

Return a Result from verify_payment_id

Reimplement io::Cursor.

The `bitcoin::io` Cursor will miss a bunch of functionality that we were
using that we will reimplement here, most critically `set_position`.

Introduce io module.

The rust-bitcoin upgrade will introduce `bitcoin::io` module, which
will be missing a necessary subset of traits.

To accommodate those traits' future implementations, we move the
`lightning::io` module to its own file, where we will be able to
implement the missing trait subset in the next commit.

Drop Seek and SeekFrom usage.

In lieu of using `Seek` and `SeekFrom`, we will instead rely
exclusively on the `io::Cursor` type.

Simplify Readable mutability.

In anticipation of the rust-bitcoin upgrade, which incorporates its
own `io::Read` implementation, we need to make our usage compatible
with dropping `std::io` and `core2::io`.

Notably, in version 0.32.2, `bitcoin::io`'s `Read` is no longer
implemented for `&mut R where R: Read + ?Sized`, which results in
errors anytime `&mut &mut Readable` is passed instead of
`&mut Readable`.

This commit fixes those instances.

Make advance_path_by_one an associated method.

Tweak phrasing in Blinded{Message,Payment}Path::advance_path_by_one docs.

Move NextMessageHop into blinded_path::message

It's only used for onion messages, not payments.

Make BlindedPath type private.

Users should use the Blinded{Message,Payment}Path types instead.

Reduce visibility of BlindedMessagePath inner path.

Works towards making the inner BlindedPath struct private to the module.

Merge pull request #3241 from TheBlueMatt/2024-08-ret-slice-not-ref-vec

Return slices, rather than `Vec` references, in addresses

Reduce visibility of BlindedPaymentPath inner path.

Works towards making the inner BlindedPath struct private to the module.

Add accessor methods for inner blinded path fields.

Move public_intro_node util into Blinded{Message,Payment}Path

Helps move towards making the BlindedPath struct private.

Move compact blinded path util to message paths only.

It's only used for message paths, so let's move it there to help make the
BlindedPath struct private.

Expose blinded paths' advance_path_by_one methods.

Useful for LDK users that are using the onion messages module, like LNDK.

Add BlindedMessagePath type to disambiguate from blinded payment paths.

Add BlindedPaymentPath type, to disambiguate from message paths.

Next up, we'll add a BlindedMessagePath type so the API is clear which type of
path is expected in each context.

Return slices, rather than `Vec` references, in addresses

Its a bit strange to return a reference to a `Vec` in Rust, when a
slice is really intended as the way to do so. Worse, the bindings
don't know how to map a reference to a `Vec` (but do have code to
map a slice of `Clone`able objects).

Here, we move `NodeAnnouncementInfo::addresses` to return a slice,
though to do so we have to adapt the `WithoutLength` `Writeable`
impl to support slices as well.

Merge pull request #3192 from jkczyz/2024-07-invoice-error-auth

Authenticate `InvoiceError` messages

Make PaymentFailureReason downgradable

The PaymentFailureReason variants for invoice request failures will
cause downgrades to break. Instead, use a new TLV for the reason and
continue to write the old TLV, only use None for the new reasons.

Make PaymentFailureReason upgradable

This allows downgrading to version 0.0.124 or later and using None for a
PaymentFailureReason that was added after.

Add PaymentFailureReason::InvoiceRequestRejected

Instead of re-using PaymentFailureReason::RecipientRejected, define a
new InvoiceRequestRejected variant for when an InvoiceError is received
instead of a Bolt12Invoice. This allows user to differentiate the cause
of the failure.

Add PaymentFailureReason::InvoiceRequestExpired

Now that Event::PaymentFailed is generated when an InvoiceRequest times
out, define a new PaymentFailureReason for this situation.

Add pending changelog for Event::PaymentFailed

Remove Event::InvoiceRequestFailed

Now that Event::PaymentFailed has an option payment_hash, it can be used
in replace of Event::InvoiceRequestFailed. This allows for including a
reason when abandoning a payment before an invoice is received.

Make payment_hash optional in Event::PaymentFailed

When abandoning a BOLT12 payment before a Bolt12Invoice is received, an
Event::InvoiceRequestFailed is generated and the abandonment reason is
lost. Make payment_hash optional in Event::PaymentFailed so that
Event::InvoiceRequestFailed can be removed in favor of it.

Test Bolt12Invoice with unknown required features

Remove unused macro param

Add InvoiceBuilder::features_unchecked

In order to test handling of unknown required features in a
Bolt12Invoice, add a test-only function to allow setting arbitrary
feature bits.

Use a smaller bit for UnknownFeature

When testing Bolt12Invoice unknown require feature handling, a large
feature bit can cause SendError::TooBigPacket when creating an onion
message. Use a smaller feature bit for UnknownFeature, which also has
the added benefit of reducing test output.

Move BOLT12 invoice features check

When handling a BOLT12 invoice, and invoice error is sent if the invoice
contains unknown required features. However, since the payment is still
in state AwaitingInvoice, abandoning it results in losing the reason
since an InvoiceRequestFailed event would be generated. Move the check
to PendingOutboundPayments such that the payment is first moved to state
InvoiceReceived so that a PaymentFailed event is generated instead.

Don't include HMAC in Refund paths

Refunds are typically communicated via QR code, where a smaller size is
desirable. Make the HMAC in OutboundPayment data optional such that it
is elided from blinded paths used in refunds. This prevents abandoning
refunds if the reader sends an invoice_error instead of an invoice
message. However, this use case isn't necessary as the corresponding
outbound payment will either timeout when the refund expires or can be
explicitly abandoned by the creator.

Don't use UserAbandoned reason for auto-failing

A BOLT12 payment may be abandoned when handling the invoice or when
receiving an InvoiceError message. When abandoning the payment, don't
use UserAbandoned as the reason since that is meant for when the user
calls ChannelManager::abandon_payment.

Don't abandon payments for duplicate invoices

When making an outbound BOLT12 payment, multiple invoices may be
received for the same payment id. Instead of abandoning the payment when
a duplicate invoice received, simply ignore it without responding with
an InvoiceError. This prevents abandoning in-progress payments and
sending unnecessary onion messages.

Authenticate payment_id from OffersContext

Before abandoning a payment when receiving an InvoiceError, verify that
the PaymentId included in the OffersContext with the included HMAC. This
prevents a malicious actor sending an InvoiceError with a known payment
id from abandoning our payment.

Add an HMAC to OffersContext::OutboundPayment

When receiving an InvoiceError in response to an InvoiceRequest, the
corresponding payment should be abandoned. Add an HMAC to
OffersContext::OutboundPayment such that the payment ID can be
authenticated prior to abandoning the payment.

Add Sha256 HMAC (de)serialization

An HMAC needs to be included in OffersContext::OutboundPayment to
authenticate the included PaymentId. Implement Readable and Writeable to
allow for this.

HMAC construction and verification for PaymentID

When receiving an InvoiceError in response to an InvoiceRequest, the
corresponding payment should be abandoned. Add functions for
constructing and verifying an HMAC over a Payment ID to allow for this.

Merge pull request #3212 from dunxen/2024-07-sensible-balances

Accuracy fixes and differentiating sources for `Balance`

Merge pull request #3234 from TheBlueMatt/2024-08-lightning-dep-inv

Swap the dep order between `lightning` and `lightning-invoice`

Merge pull request #3020 from tnull/2024-04-drop-electrsd-autodownload-for-good

Drop `electrsd`'s auto-download feature for good

Enable caching for `bitcoind`/`electrs` in CI

`rustfmt` new files added in the past few commits

The past handful of commits were mostly moving code around, so to
aid reviewers violated our `rustfmt` rules. Here we rectify that by
`rustfmt`'ing the newly-added files.

Prepare to `rustfmt` newly added files

In the next commit we'll `rustfmt` newly-added files, but before
we do so we clean up some code so that the resulting files won't be
quite as absurd. We also exclude the new `invoice_utils.rs` file,
as it needs quite substantial cleanups.

Provide the signer with a full `RawBolt11Invoice` to sign

Now that the `lightning` crate depends on the `lightning-invoice`
crate, there's no reason to have the `sign_invoice` method take raw
base32 field elements as we can now give it a real
`RawBolt11Invoice`, which we do here.

This simplifies the interface and avoids a
serialization-deserialization roundtrip when signing invoices in a
validating signer.

FIxes #3227

Swap the dep order between `lightning` and `lightning-invoice`

`lightning-invoice` previously had a dependency on the entire
`lightning` crate just because it wants to use some of the useful
types from it. This is obviously backwards and leads to some
awkwardness like the BOLT 11 invoice signing API in the `lightning`
crate taking a `[u5]` rather than a `Bolt11Invoice`.

Here we finally rectify this issue, swapping the dependency order
and making `lightning` depend on `lightning-invoice` rather than
the other way around.

This moves various utilities which were in `lightning-invoice` but
relied on `lightning` payment types to make payments to where they
belong (the `lightning` crate), but doesn't bother with integrating
them well in their new home.

Add a `lightning-types` dependency to `lightning-invoice`

`lightning-invoice` currently has a dependency on the entire
`lightning` crate just because it wants to use some of the useful
types from it. This is obviously backwards and leads to some
awkwardness like the BOLT 11 invoice signing API in the `lightning`
crate taking a `[u5]` rather than a `Bolt11Invoice`.

This takes tees us up for the final step, adding a
`lightning-types` dependency to `lightning-invoice` and using it
for imports rather than the `lightning` crate.

Use `check_added_monitors` test utility in invoice utils tests

In a coming commit, the `lightning-invoice::utils` module will move
to the `lightning` crate, causing its tests to be included in the
global lockorder tests done in that crate. This should be fine,
except that the `lightning-invoice::utils` module currently holds
the `added_monitors` lock too long causing lockorder violations.

Instead, this commit replaces the legacy monitors-added test with
the `check_added_monitors` test utility.

Move `UntrustedString` and `PrintableString` to `lightning-types`

`lightning-invoice` currently has a dependency on the entire
`lightning` crate just because it wants to use some of the useful
types from it. This is obviously backwards and leads to some
awkwardness like the BOLT 11 invoice signing API in the `lightning`
crate taking a `[u5]` rather than a `Bolt11Invoice`.

This takes one more step, moving the `UntrustedString` and
`PrintableString` types to `lightning-types`.

Move `Features` into `lightning-types`

`lightning-invoice` currently has a dependency on the entire
`lightning` crate just because it wants to use some of the useful
types from it. This is obviously backwards and leads to some
awkwardness like the BOLT 11 invoice signing API in the `lightning`
crate taking a `[u5]` rather than a `Bolt11Invoice`.

This takes one more step, moving the `Features` types from
`lightning` to `lightning-types`.

Replace usages of `Features::is_subset` and remove it

It turns out all the places we use `Features::is_subset` we could
as well be using `Features::requires_unknown_bits_from`. Further,
in the next commit `Features` will move to a different crate so any
methods which the `lightning` crate uses will need to be public. As
the `is_subset` API is prety confusing (it doesn't consider
optional/required bits, only whether the bits themselves are
strictly a subset) it'd be nice to not have to expose it, which is
enabled here.

Move `Rout{ingFees,eHint{,Hop}}` to `lightning-types`

`lightning-invoice` currently has a dependency on the entire
`lightning` crate just because it wants to use some of the useful
types from it. This is obviously backwards and leads to some
awkwardness like the BOLT 11 invoice signing API in the `lightning`
crate taking a `[u5]` rather than a `Bolt11Invoice`.

This takes one more step, moving the routing types
`lightning-invoice` uses into `lightning-types`.

Move `Payment{Hash,Preimage,Secret}` into a new crate

`lightning-invoice` currently has a dependency on the entire
`lightning` crate just because it wants to use some of the useful
types from it. This is obviously backwards and leads to some
awkwardness like the BOLT 11 invoice signing API in the `lightning`
crate taking a `[u5]` rather than a `Bolt11Invoice`.

This is the first step towards fixing that - moving the common
types we need into a new `lightning-types` crate which both can
depend on.

Since we're using a new crate and can't depend on the existing
`lightning` hex utility to implement `Display`, we also take this
opportunity to switch to the new `Display` impl macro in
`hex_conservative`.

Test claimable balance is expected for forwarded/outbound payments

Indicate source of balances

Introduce the `BalanceSource` enum to differentiate between force-close,
coop-close, and HTLCs in `Balance::ClaimableAwaitingConfirmations`.

Explain how rounded millisat values are included in overall balance

Test rounded msat balances

Include rounded msat balances in `Balance::ClaimableOnChannelClose`

If we're gonna push users towards using `Balance` to determine
their current balances, we really need to provide more information,
including msat balances.

Here we add rounded-out msat balances to the pre-close balance
information

Add tx fee information to `Balance::ClaimableOnChannelClose`

`Balance::ClaimableOnChannelClose` excludes the commitment
transaction fee, which makes it hard to use for current balance
calculation. Here we add it, setting the value to zero for inbound
channels (i.e. ones for which we don't pay the fee).

Move commitment tx fee calculation helpers to `chan_utils`

These don't really belong in `channel` as they're now used in other
parts of the codebase.

Drop `chan_utils` self-import

There's no reason to `use` a module within that module to refer to
that module...

Include an `outbound_payment` flag in `MaybeTimeoutClaimableHTLC`

When the user is fetching their current balances after forwarding a
payment (before it clears), they'll see a
`MaybePreimageClaimableHTLC` and a `MaybeTimeoutClaimableHTLC` but
if they sum up their balance using
`Balance::claimable_amount_satoshis` neither will be included.

Obviously, exactly one of the two balances should be included - one
of the two resolutions should happen in our favor. This causes our
visible balance to fluctuate up and down by the full value of any
HTLCs we're in the middle of forwarding, which is incredibly
confusing to see. If we want to stop the fluctuations, we need to
pick one of the two balances to include. The obvious candidate is
`MaybeTimeoutClaimableHTLC` as it is the lower of the two, and
represents our balance without the fee we'd receive from the
forward.

Sadly, if we always include it, we'll end up also including any
HTLCs which we've sent but which haven't yet been claimed by their
recipient, which is the wrong behavior.

Luckily, we have access to the `Option<HTLCSource>` while walking
HTLCs, which allows us to add an `outbound_payment` flag to
`MaybeTimeoutClaimableHTLC`. This allows us to only include
forwarded payments in `claimable_amount_satoshis`.

Sadly, even with this in place our balance still fluctuates by the
changes in the commitment transaction fees we have to pay during
forwarding, but addressing that is left for later.

Upgrade all github actions to `v4` variants

Fix misc `shellcheck` complaints

Have `shellcheck` check all scripts in `contrib`

Have `shellcheck` check all scripts in `ci`

Drop `electrsd` autodownload feature for good

... which requires a bunch of unnecessary dev dependencies, e.g., `zip`.

Instead we lean on the `download_bitcoind_electrs.sh` script also for
local testing.

Move CI downloading `bitcoind`/`electrsd` to dedicated shell script

... allowing it to be sourced locally before running
`lightning-transaction-sync` tests.

Merge pull request #3210 from tcharding/07-31-rm-hex-dep

Remove explicit dependency on hex-conservative

Merge pull request #3236 from TheBlueMatt/2024-08-unclonable-graph

Stop relying on a `Clone`able `NetworkGraph` ref in `DefaultRouter`

Stop relying on a `Clone`able `NetworkGraph` ref in `DefaultRouter`

While there's not really much harm in requiring a `Clone`able
reference (they almost always are), it does make our bindings
struggle a bit as they don't support multi-trait bounds (as it
would require synthesizing a new C trait, which the bindings don't
do automatically). Luckily, there's really no reason for it, and we
can just call the `DefaultMessageRouter` directly when we want to
route a message.

We've carried this patch for a while on the bindings branch, but
there's not a strong reason it can't go upstream.

Merge pull request #3214 from TheBlueMatt/2024-07-chan-by-val

Make `funding_transaction_generated` take a `ChannelId` by value

Use bitcoin::hex instead of bitcoin::hashes::hex

Use the `hex-conservative` crate directly from `bitcoin` instead of from
`hashes`. Although it makes no real difference it is slightly more clear
and more terse.

Remove explicit dependency on hex-conservative

The `hex` crate is re-exported by `rust-bitcoin` so we can get it from
there instead of explicitly depending on it. Doing so reduces the
maintenance burden and helps reduce the likelyhood of getting two
versions in the dependency graph.

Merge pull request #3220 from dunxen/2024-08-config-param-consistency

Set default ChannelHandshakeLimits::min_funding_satoshis to 1000

Set default ChannelHandshakeLimits::min_funding_satoshis to 1000

The original default value of 0 was inconsistent with the minimum requirement
of 1000 satoshis in ChannelHandshakeConfig::their_channel_reserve_proportional_millionths.

Merge pull request #3194 from tnull/2024-07-om-event-notifier

Add `Notifier` to `OnionMessenger`

Merge pull request #3215 from tnull/2024-08-protect-against-merkle-leaf-node-weakness

tx-sync: Protect against Core's Merkle leaf node weakness

Protect against Core's Merkle leaf node weakness

Bitcoin Core's Merkle tree implementation has no way to discern between
internal and leaf node entries. As a consequence it is susceptible to an
attacker injecting additional transactions by crafting 64-byte
transactions matching an inner Merkle node's hash (see
https://web.archive.org/web/20240329003521/https://bitslog.com/2018/06/09/leaf-node-weakness-in-bitcoin-merkle-tree-design/).

To protect against this (highly unlikely attack vector), we check that
the transaction isn't 64 bytes in length, and skip it otherwise.

Merge pull request #3230 from TheBlueMatt/2024-08-old-doc-tweaks

Minor doc tweaks to `MonitorHolder`