Commit message · auto-pr-botFix over-estimate of path max contribution with >= 100% fees
@val wrote:
> The formula computing the maximum value a path can contribute to the
> final value received by the payee used to assume the aggregated
> proportional fee of the hops following a given hop was below 100%.
> Invoice hints (and blinded paths) may carry arbitrary fees, and with an
> aggregate proportional fee of 100% or more the computed maximum
> overshot the true one by 1 msat, building paths that exceed a hop's
> available liquidity (and panicking in debug builds). [...]
@val asked:
> @auto-pr-bot please open a PR to address this issue
209cb2aa2e0d67bf89a130b070f7116178e9ddb4 computed the maximum as
ceil(((max - agg_base) * 1_000_000) / (1_000_000 + agg_prop)) via the
(a + b - 1) / b idiom, and 7ebdf45b3 switched it to floor by dropping
only the `+ 1_000_000 - 1` term. That left `+ agg_prop` in the numerator,
computing floor((a + agg_prop) / (1_000_000 + agg_prop)) instead, which
overshoots the intended floor by 1 whenever a mod (1_000_000 + agg_prop)
is at least 1_000_000. Invoice route hints can carry proportional fees of
100% or more, which makes that remainder reachable and the resulting
1-msat overshoot builds paths exceeding a hop's available liquidity,
tripping the `used_liquidity_msat <= hop_max_msat` debug assertion.
Drop the stray term so we compute the floor the comment describes. A
floor cannot overshoot the true maximum even though hop fees are rounded
up with ceil: any f satisfying f * (1_000_000 + agg_prop)
<= (max - agg_base) * 1_000_000 also satisfies
f + ceil(f * agg_prop / 1_000_000) <= max - agg_base.
Add a regression test, contributed by @val in the issue, which panics in
debug builds without the fix.
Requested-by: @val
Authored-By: matt/GLM-5.3-Flash-GGUF:Q4_K_XL <goose@users.noreply.local>
83/100 · StrongMessage clarity
✓ Specific, descriptive subject✓ Names a concrete action or component✓ Provides detailed explanatory context✓ Mentions testing or verification
Why it was queuedfuzzing or regression evidence