Merge pull request #11290 from allenpiscitello/fix/blinded-path-fee-overflow

### docs/release-notes/release-notes-0.22.0.md
@@ -22,6 +22,16 @@
 
 # Bug Fixes
 
+* [Fixed an overflow](https://github.com/lightningnetwork/lnd/pull/11290)
+  in the accumulated fee calculation for blinded paths. The aggregate base fee
+  and fee rate advertised in a blinded path's payinfo were computed with
+  `uint32` arithmetic, which wrapped once the summed fees exceeded about 4295
+  msat or 4295 ppm. The under-reported fees made payers underpay, so payments
+  to such invoices failed. The aggregates are now computed with checked
+  arithmetic, and a candidate path whose aggregate fees don't fit in the
+  invoice's `uint32` payinfo fields is skipped instead of being advertised
+  with under-reported fees.
+
 * [Fixed historical graph
   synchronization](https://github.com/lightningnetwork/lnd/pull/11173) so a
   peer whose channel range response cannot be used is rotated out of the
@@ -195,6 +205,7 @@
 
 # Contributors (Alphabetical Order)
 
+* Allen Piscitello
 * bitromortac
 * Boris Nagaev
 * Erick Cestari

### routing/blindedpath/blinded_path.go
@@ -5,6 +5,7 @@ import (
 	"errors"
 	"fmt"
 	"math"
+	"math/bits"
 	"sort"
 
 	"github.com/btcsuite/btcd/btcec/v2"
@@ -144,8 +145,8 @@ func BuildBlindedPaymentPaths(cfg *BuildBlindedPathCfg) (
 		path, err := buildBlindedPaymentPath(cfg, candidatePath)
 		if errors.Is(err, errInvalidBlindedPath) {
 			log.Debugf("Not using route (%s) as a blinded path "+
-				"since it resulted in an invalid blinded path",
-				route)
+				"since it resulted in an invalid blinded "+
+				"path: %v", route, err)
 
 			continue
 		} else if err != nil {
@@ -185,9 +186,13 @@ func buildBlindedPaymentPath(cfg *BuildBlindedPathCfg, path *candidatePath) (
 
 	// Using the collected relay info, we can calculate the aggregated
 	// policy values for the route.
-	baseFee, feeRate, cltvDelta := calcBlindedPathPolicies(
+	baseFee, feeRate, cltvDelta, err := calcBlindedPathPolicies(
 		relayInfo, uint16(cfg.MinFinalCLTVExpiryDelta),
 	)
+	if err != nil {
+		return nil, fmt.Errorf("could not calculate blinded path "+
+			"policies: %w", err)
+	}
 
 	currentHeight, err := cfg.BestHeight()
 	if err != nil {
@@ -303,7 +308,7 @@ func buildBlindedPaymentPath(cfg *BuildBlindedPathCfg, path *candidatePath) (
 
 	// Now construct a z32 blinded path.
 	return &zpay32.BlindedPaymentPath{
-		FeeBaseMsat:                 uint32(baseFee),
+		FeeBaseMsat:                 baseFee,
 		FeeRate:                     feeRate,
 		CltvExpiryDelta:             cltvDelta,
 		HTLCMinMsat:                 uint64(minHTLC),
@@ -829,13 +834,19 @@ func AddPolicyBuffer(policy *BlindedHopPolicy, incMultiplier,
 // These values include the total base fee, the total proportional fee and the
 // total CLTV delta. This function assumes that all the passed relay infos have
 // already been adjusted with a buffer to account for easy probing attacks.
+//
+// The aggregate fees are advertised in the invoice's uint32 payinfo fields, so
+// they must represent the fees enforced inside the blinded path exactly. If
+// either aggregate does not fit, an error wrapping errInvalidBlindedPath is
+// returned so that the path is not advertised.
 func calcBlindedPathPolicies(relayInfo []*record.PaymentRelayInfo,
-	ourMinFinalCLTVDelta uint16) (lnwire.MilliSatoshi, uint32, uint16) {
+	ourMinFinalCLTVDelta uint16) (uint32, uint32, uint16, error) {
 
 	var (
-		totalFeeBase lnwire.MilliSatoshi
+		totalFeeBase uint32
 		totalFeeProp uint32
 		totalCLTV    = ourMinFinalCLTVDelta
+		err          error
 	)
 	// Use the algorithms defined in BOLT 4 to calculate the accumulated
 	// relay fees for the route:
@@ -844,39 +855,111 @@ func calcBlindedPathPolicies(relayInfo []*record.PaymentRelayInfo,
 	for i := len(relayInfo) - 1; i >= 0; i-- {
 		info := relayInfo[i]
 
-		totalFeeBase = calcNextTotalBaseFee(
+		totalFeeBase, err = calcNextTotalBaseFee(
 			totalFeeBase, info.BaseFee, info.FeeRate,
 		)
+		if err != nil {
+			return 0, 0, 0, err
+		}
 
-		totalFeeProp = calcNextTotalFeeRate(totalFeeProp, info.FeeRate)
+		totalFeeProp, err = calcNextTotalFeeRate(
+			totalFeeProp, info.FeeRate,
+		)
+		if err != nil {
+			return 0, 0, 0, err
+		}
 
 		totalCLTV += info.CltvExpiryDelta
 	}
 
-	return totalFeeBase, totalFeeProp, totalCLTV
+	return totalFeeBase, totalFeeProp, totalCLTV, nil
 }
 
 // calcNextTotalBaseFee takes the current total accumulated base fee of a
 // blinded path at hop `n` along with the fee rate and base fee of the hop at
-// `n+1` and uses these to calculate the accumulated base fee at hop `n+1`.
-func calcNextTotalBaseFee(currentTotal, hopBaseFee lnwire.MilliSatoshi,
-	hopFeeRate uint32) lnwire.MilliSatoshi {
+// `n+1` and uses these to calculate the accumulated base fee at hop `n+1`. An
+// error wrapping errInvalidBlindedPath is returned if the calculation
+// overflows or the result does not fit in a uint32.
+func calcNextTotalBaseFee(currentTotal uint32, hopBaseFee lnwire.MilliSatoshi,
+	hopFeeRate uint32) (uint32, error) {
+
+	million := uint64(oneMillion)
+
+	// Calculate the numerator for the accumulated base fee. Adding
+	// million-1 before dividing by million rounds any fractional fee up
+	// to the next whole millisatoshi.
+	//
+	// Formula: hopBaseFee*1e6 + currentTotal*(1e6+hopFeeRate) + (1e6-1).
+	baseTerm, baseTermOK := mulUint64(uint64(hopBaseFee), million)
+	totalTerm, totalTermOK := mulUint64(
+		uint64(currentTotal), million+uint64(hopFeeRate),
+	)
+	numerator, termsSumOK := addUint64(baseTerm, totalTerm)
+	roundedNumerator, roundingOK := addUint64(numerator, million-1)
+	if !baseTermOK || !totalTermOK || !termsSumOK || !roundingOK {
+		return 0, fmt.Errorf("%w: aggregate base fee overflows uint64",
+			errInvalidBlindedPath)
+	}
 
-	numerator := (uint32(hopBaseFee) * oneMillion) +
-		(uint32(currentTotal) * (oneMillion + hopFeeRate)) +
-		oneMillion - 1
+	total := roundedNumerator / million
+	if total > math.MaxUint32 {
+		return 0, fmt.Errorf("%w: aggregate base fee of %d msat "+
+			"exceeds the maximum of %d msat", errInvalidBlindedPath,
+			total, uint32(math.MaxUint32))
+	}
 
-	return lnwire.MilliSatoshi(numerator / oneMillion)
+	return uint32(total), nil
 }
 
-// calculateNextTotalFeeRate takes the current total accumulated fee rate of a
+// calcNextTotalFeeRate takes the current total accumulated fee rate of a
 // blinded path at hop `n` along with the fee rate of the hop at `n+1` and uses
-// these to calculate the accumulated fee rate at hop `n+1`.
-func calcNextTotalFeeRate(currentTotal, hopFeeRate uint32) uint32 {
-	numerator := (currentTotal+hopFeeRate)*oneMillion +
-		currentTotal*hopFeeRate + oneMillion - 1
+// these to calculate the accumulated fee rate at hop `n+1`. An error wrapping
+// errInvalidBlindedPath is returned if the calculation overflows or the
+// result does not fit in a uint32.
+func calcNextTotalFeeRate(currentTotal, hopFeeRate uint32) (uint32, error) {
+	million := uint64(oneMillion)
+
+	// Calculate the numerator for the accumulated fee rate. Adding
+	// million-1 before dividing by million rounds any fractional rate up
+	// to the next whole part per million.
+	//
+	// Formula: (currentTotal+hopFeeRate)*1e6 + currentTotal*hopFeeRate +
+	// (1e6-1).
+	sumTerm, sumTermOK := mulUint64(
+		uint64(currentTotal)+uint64(hopFeeRate), million,
+	)
+	productTerm, productTermOK := mulUint64(
+		uint64(currentTotal), uint64(hopFeeRate),
+	)
+	numerator, termsSumOK := addUint64(sumTerm, productTerm)
+	roundedNumerator, roundingOK := addUint64(numerator, million-1)
+	if !sumTermOK || !productTermOK || !termsSumOK || !roundingOK {
+		return 0, fmt.Errorf("%w: aggregate fee rate overflows uint64",
+			errInvalidBlindedPath)
+	}
+
+	total := roundedNumerator / million
+	if total > math.MaxUint32 {
+		return 0, fmt.Errorf("%w: aggregate fee rate of %d ppm "+
+			"exceeds the maximum of %d ppm", errInvalidBlindedPath,
+			total, uint32(math.MaxUint32))
+	}
+
+	return uint32(total), nil
+}
+
+// mulUint64 returns a*b and true, or false if the product overflows a uint64.
+func mulUint64(a, b uint64) (uint64, bool) {
+	hi, lo := bits.Mul64(a, b)
+
+	return lo, hi == 0
+}
+
+// addUint64 returns a+b and true, or false if the sum overflows a uint64.
+func addUint64(a, b uint64) (uint64, bool) {
+	sum, carry := bits.Add64(a, b, 0)
 
-	return numerator / oneMillion
+	return sum, carry == 0
 }
 
 // hopData packages the record.BlindedRouteData for a hop on a blinded path with

### routing/blindedpath/blinded_path_test.go
@@ -4,6 +4,7 @@ import (
 	"bytes"
 	"encoding/hex"
 	"fmt"
+	"math"
 	"math/rand"
 	"reflect"
 	"testing"
@@ -206,15 +207,133 @@ func TestBlindedPathAccumulatedPolicyCalc(t *testing.T) {
 	// Alice's minimum final expiry delta is chosen to be 12.
 	aliceMinFinalExpDelta := uint16(12)
 
-	totalBase, totalRate, totalCLTVDelta := calcBlindedPathPolicies(
+	totalBase, totalRate, totalCLTVDelta, err := calcBlindedPathPolicies(
 		hopPolicies, aliceMinFinalExpDelta,
 	)
+	require.NoError(t, err)
 
-	require.Equal(t, lnwire.MilliSatoshi(201), totalBase)
+	require.EqualValues(t, 201, totalBase)
 	require.EqualValues(t, 1001, totalRate)
 	require.EqualValues(t, 300, totalCLTVDelta)
 }
 
+// TestCalcBlindedPathPoliciesFeeOverflow asserts that the accumulated
+// fee base and rate of a blinded route are calculated exactly up to the
+// maximum value of the uint32 invoice fields, and that a path whose aggregate
+// fees cannot be represented exactly is rejected instead of being advertised
+// with under-reported fees.
+func TestCalcBlindedPathPoliciesFeeOverflow(t *testing.T) {
+	t.Parallel()
+
+	tests := []struct {
+		name         string
+		policies     []*record.PaymentRelayInfo
+		expectedBase uint32
+		expectedRate uint32
+		expectedErr  string
+	}{
+		{
+			// 2 x 2750 ppm sums past ~4295 ppm, where the uint32
+			// rate calculation wrapped to 1213.
+			name: "fee rate above uint32 range",
+			policies: []*record.PaymentRelayInfo{
+				{FeeRate: 2750, BaseFee: 1100},
+				{FeeRate: 2750, BaseFee: 1100},
+			},
+			expectedBase: 2204,
+			expectedRate: 5508,
+		},
+		{
+			// A single 5000 msat base fee already exceeds the
+			// uint32 range once scaled by one million.
+			name: "base fee above uint32 range",
+			policies: []*record.PaymentRelayInfo{
+				{FeeRate: 1, BaseFee: 5000},
+				{FeeRate: 1, BaseFee: 5000},
+			},
+			expectedBase: 10001,
+			expectedRate: 3,
+		},
+		{
+			name: "aggregate base fee equal to max uint32",
+			policies: []*record.PaymentRelayInfo{
+				{BaseFee: 1},
+				{BaseFee: math.MaxUint32 - 1},
+			},
+			expectedBase: math.MaxUint32,
+		},
+		{
+			// 4294962999 + 1 + ceil(4294962999 * 1 / 1e6)
+			// = 4294967295.
+			name: "aggregate fee rate equal to max uint32",
+			policies: []*record.PaymentRelayInfo{
+				{FeeRate: 1},
+				{FeeRate: 4294962999},
+			},
+			expectedRate: math.MaxUint32,
+		},
+		{
+			name: "aggregate base fee one above max uint32",
+			policies: []*record.PaymentRelayInfo{
+				{BaseFee: 2},
+				{BaseFee: math.MaxUint32 - 1},
+			},
+			expectedErr: "aggregate base fee of 4294967296 msat " +
+				"exceeds",
+		},
+		{
+			// 4294963000 + 1 + ceil(4294963000 * 1 / 1e6)
+			// = 4294967296.
+			name: "aggregate fee rate one above max uint32",
+			policies: []*record.PaymentRelayInfo{
+				{FeeRate: 1},
+				{FeeRate: 4294963000},
+			},
+			expectedErr: "aggregate fee rate of 4294967296 ppm " +
+				"exceeds",
+		},
+		{
+			// The hop base fee scaled by one million doesn't fit
+			// in a uint64.
+			name: "base fee uint64 overflow",
+			policies: []*record.PaymentRelayInfo{
+				{BaseFee: math.MaxUint64 / 1_000_000 * 2},
+			},
+			expectedErr: "aggregate base fee overflows uint64",
+		},
+		{
+			// Two valid uint32 fee rates whose product plus their
+			// scaled sum doesn't fit in a uint64.
+			name: "fee rate uint64 overflow",
+			policies: []*record.PaymentRelayInfo{
+				{FeeRate: math.MaxUint32},
+				{FeeRate: math.MaxUint32},
+			},
+			expectedErr: "aggregate fee rate overflows uint64",
+		},
+	}
+
+	for _, test := range tests {
+		t.Run(test.name, func(t *testing.T) {
+			t.Parallel()
+
+			totalBase, totalRate, _, err := calcBlindedPathPolicies(
+				test.policies, 12,
+			)
+			if test.expectedErr != "" {
+				require.ErrorIs(t, err, errInvalidBlindedPath)
+				require.ErrorContains(t, err, test.expectedErr)
+
+				return
+			}
+
+			require.NoError(t, err)
+			require.Equal(t, test.expectedBase, totalBase)
+			require.Equal(t, test.expectedRate, totalRate)
+		})
+	}
+}
+
 // TestPadBlindedHopInfo asserts that the padding of blinded hop data is done
 // correctly and that it takes the expected number of iterations.
 func TestPadBlindedHopInfo(t *testing.T) {
@@ -1037,6 +1156,96 @@ func TestSingleHopBlindedPath(t *testing.T) {
 	require.EqualValues(t, 12, path.CltvExpiryDelta)
 }
 
+// TestBuildBlindedPathSkipsFeeOverflow asserts that a candidate route whose
+// aggregate fees cannot be represented in the invoice is skipped, while the
+// other usable candidates are still turned into blinded paths.
+func TestBuildBlindedPathSkipsFeeOverflow(t *testing.T) {
+	t.Parallel()
+
+	// Alice receives via two single-hop candidate routes: one through
+	// Carol, whose base fee doesn't fit in the uint32 invoice field, and
+	// one through Bob with ordinary fees.
+	var (
+		_, pkC = btcec.PrivKeyFromBytes([]byte{1})
+		_, pkB = btcec.PrivKeyFromBytes([]byte{2})
+		_, pkA = btcec.PrivKeyFromBytes([]byte{3})
+
+		carol = route.NewVertex(pkC)
+		bob   = route.NewVertex(pkB)
+		alice = route.NewVertex(pkA)
+
+		chanCA = uint64(1)
+		chanBA = uint64(2)
+	)
+
+	routes := []*route.Route{
+		{
+			SourcePubKey: carol,
+			Hops: []*route.Hop{{
+				PubKeyBytes: alice,
+				ChannelID:   chanCA,
+			}},
+		},
+		{
+			SourcePubKey: bob,
+			Hops: []*route.Hop{{
+				PubKeyBytes: alice,
+				ChannelID:   chanBA,
+			}},
+		},
+	}
+
+	policies := map[uint64]*models.ChannelEdgePolicy{
+		chanCA: {
+			ChannelID:   chanCA,
+			ToNode:      alice,
+			FeeBaseMSat: math.MaxUint32 + 1,
+			MaxHTLC:     1_000_000,
+		},
+		chanBA: {
+			ChannelID:                 chanBA,
+			ToNode:                    alice,
+			FeeBaseMSat:               100,
+			FeeProportionalMillionths: 500,
+			TimeLockDelta:             144,
+			MaxHTLC:                   1_000_000,
+		},
+	}
+
+	paths, err := BuildBlindedPaymentPaths(&BuildBlindedPathCfg{
+		FindRoutes: func(_ lnwire.MilliSatoshi) ([]*route.Route,
+			error) {
+
+			return routes, nil
+		},
+		FetchChannelEdgesByID: func(chanID uint64) (
+			*models.ChannelEdgeInfo, *models.ChannelEdgePolicy,
+			*models.ChannelEdgePolicy, error) {
+
+			return nil, policies[chanID], nil, nil
+		},
+		BestHeight: func() (uint32, error) {
+			return 1000, nil
+		},
+		AddPolicyBuffer: func(p *BlindedHopPolicy) (*BlindedHopPolicy,
+			error) {
+
+			return p, nil
+		},
+		PathID:                  []byte{1, 2, 3},
+		ValueMsat:               1000,
+		MinFinalCLTVExpiryDelta: 12,
+		BlocksUntilExpiry:       200,
+	})
+	require.NoError(t, err)
+
+	// Only the path through Bob is returned.
+	require.Len(t, paths, 1)
+	require.True(t, paths[0].Hops[0].BlindedNodePub.IsEqual(pkB))
+	require.EqualValues(t, 100, paths[0].FeeBaseMsat)
+	require.EqualValues(t, 500, paths[0].FeeRate)
+}
+
 func decryptAndDecodeHopData(t *testing.T, priv *btcec.PrivateKey,
 	ephem *btcec.PublicKey, cipherText []byte) (*record.BlindedRouteData,
 	*btcec.PublicKey) {