Repository: lightningnetwork/lnd
Pull request #3686 (2019-11-07 10:28:59)

routing: use distinct probability estimation for local channels
Previously we used the a priori probability also for our own untried channels. This led to local channels that had seen a success already being prioritized over untried local channels. In some cases,  depending
on the configured payment attempt cost, this could lead to the payment taking a two hop route while a direct payment was also possible.


Patch:
diff --git a/routing/missioncontrol.go b/routing/missioncontrol.go
index cebac51c4..2d5deb508 100644
--- a/routing/missioncontrol.go
+++ b/routing/missioncontrol.go
@@ -118,6 +118,9 @@ type MissionControlConfig struct {
 	// probability completely and only base the probability on historical
 	// results, unless there are none available.
 	AprioriWeight float64
+
+	// SelfNode is our own pubkey.
+	SelfNode route.Vertex
 }
 
 // TimedPairResult describes a timestamped pair result.
@@ -261,6 +264,11 @@ func (m *MissionControl) GetProbability(fromNode, toNode route.Vertex,
 	now := m.now()
 	results := m.lastPairResult[fromNode]
 
+	// Use a distinct probability estimation function for local channels.
+	if fromNode == m.cfg.SelfNode {
+		return m.estimator.getLocalPairProbability(now, results, toNode)
+	}
+
 	return m.estimator.getPairProbability(now, results, toNode, amt)
 }
 
diff --git a/routing/probability_estimator.go b/routing/probability_estimator.go
index 991a77562..1e60608cb 100644
--- a/routing/probability_estimator.go
+++ b/routing/probability_estimator.go
@@ -116,13 +116,43 @@ func (p *probabilityEstimator) getPairProbability(
 	now time.Time, results NodeResults,
 	toNode route.Vertex, amt lnwire.MilliSatoshi) float64 {
 
+	nodeProbability := p.getNodeProbability(now, results, amt)
+
+	return p.calculateProbability(
+		now, results, nodeProbability, toNode, amt,
+	)
+}
+
+// getLocalPairProbability estimates the probability of successfully traversing
+// our own local channels to toNode.
+func (p *probabilityEstimator) getLocalPairProbability(
+	now time.Time, results NodeResults, toNode route.Vertex) float64 {
+
+	// For local channels that have never been tried before, we assume them
+	// to be successful. We have accurate balance and online status
+	// information on our own channels, so when we select them in a route it
+	// is close to certain that those channels will work.
+	nodeProbability := p.prevSuccessProbability
+
+	return p.calculateProbability(
+		now, results, nodeProbability, toNode, lnwire.MaxMilliSatoshi,
+	)
+}
+
+// calculateProbability estimates the probability of successfully traversing to
+// toNode based on historical payment outcomes and a fall-back node probability.
+func (p *probabilityEstimator) calculateProbability(
+	now time.Time, results NodeResults,
+	nodeProbability float64, toNode route.Vertex,
+	amt lnwire.MilliSatoshi) float64 {
+
 	// Retrieve the last pair outcome.
 	lastPairResult, ok := results[toNode]
 
 	// If there is no history for this pair, return the node probability
 	// that is a probability estimate for untried channel.
 	if !ok {
-		return p.getNodeProbability(now, results, amt)
+		return nodeProbability
 	}
 
 	// For successes, we have a fixed (high) probability. Those pairs
@@ -131,8 +161,6 @@ func (p *probabilityEstimator) getPairProbability(
 		return p.prevSuccessProbability
 	}
 
-	nodeProbability := p.getNodeProbability(now, results, amt)
-
 	// Take into account a minimum penalize amount. For balance errors, a
 	// failure may be reported with such a minimum to prevent too aggressive
 	// penalization. If the current amount is smaller than the amount that
diff --git a/server.go b/server.go
index b8872e9ef..7baf14468 100644
--- a/server.go
+++ b/server.go
@@ -672,6 +672,7 @@ func newServer(listenAddrs []net.Addr, chanDB *channeldb.DB,
 			PenaltyHalfLife:       routingConfig.PenaltyHalfLife,
 			MaxMcHistory:          routingConfig.MaxMcHistory,
 			AprioriWeight:         routingConfig.AprioriWeight,
+			SelfNode:              selfNode.PubKeyBytes,
 		},
 	)
 	if err != nil {


Test patch:
diff --git a/contractcourt/htlc_outgoing_contest_resolver.go b/contractcourt/htlc_outgoing_contest_resolver.go
index 789558a67..43549a261 100644
--- a/contractcourt/htlc_outgoing_contest_resolver.go
+++ b/contractcourt/htlc_outgoing_contest_resolver.go
@@ -76,6 +76,36 @@ func (h *htlcOutgoingContestResolver) Resolve() (ContractResolver, error) {
 	default:
 	}
 
+	// We'll check the current height, if the HTLC has already expired,
+	// then we'll morph immediately into a resolver that can sweep the
+	// HTLC.
+	//
+	// TODO(roasbeef): use grace period instead?
+	_, currentHeight, err := h.ChainIO.GetBestBlock()
+	if err != nil {
+		return nil, err
+	}
+
+	// If the current height is >= expiry-1, then a spend will be valid to
+	// be included in the next block, and we can immediately return the
+	// resolver.
+	//
+	// TODO(joostjager): Statement above may not be valid. For CLTV locks,
+	// the expiry value is the last _invalid_ block. The likely reason that
+	// this does not create a problem, is that utxonursery is checking the
+	// expiry again (in the proper way). Same holds for minus one operation
+	// below.
+	//
+	// Source:
+	// https://github.com/btcsuite/btcd/blob/991d32e72fe84d5fbf9c47cd604d793a0cd3a072/blockchain/validate.go#L154
+	if uint32(currentHeight) >= h.htlcResolution.Expiry-1 {
+		log.Infof("%T(%v): HTLC has expired (height=%v, expiry=%v), "+
+			"transforming into timeout resolver", h,
+			h.htlcResolution.ClaimOutpoint, currentHeight,
+			h.htlcResolution.Expiry)
+		return &h.htlcTimeoutResolver, nil
+	}
+
 	// If we reach this point, then we can't fully act yet, so we'll await
 	// either of our signals triggering: the HTLC expires, or we learn of
 	// the preimage.
@@ -95,18 +125,9 @@ func (h *htlcOutgoingContestResolver) Resolve() (ContractResolver, error) {
 				return nil, errResolverShuttingDown
 			}
 
-			// If the current height is >= expiry-1, then a timeout
-			// path spend will be valid to be included in the next
-			// block, and we can immediately return the resolver.
-			//
-			// TODO(joostjager): Statement above may not be valid.
-			// For CLTV locks, the expiry value is the last
-			// _invalid_ block. The likely reason that this does not
-			// create a problem, is that utxonursery is checking the
-			// expiry again (in the proper way).
-			//
-			// Source:
-			// https://github.com/btcsuite/btcd/blob/991d32e72fe84d5fbf9c47cd604d793a0cd3a072/blockchain/validate.go#L154
+			// If this new height expires the HTLC, then we can
+			// exit early and create a resolver that's capable of
+			// handling the time locked output.
 			newHeight := uint32(newBlock.Height)
 			if newHeight >= h.htlcResolution.Expiry-1 {
 				log.Infof("%T(%v): HTLC has expired "+
diff --git a/contractcourt/htlc_outgoing_contest_resolver_test.go b/contractcourt/htlc_outgoing_contest_resolver_test.go
deleted file mode 100644
index 244b438d3..000000000
--- a/contractcourt/htlc_outgoing_contest_resolver_test.go
+++ /dev/null
@@ -1,187 +0,0 @@
-package contractcourt
-
-import (
-	"fmt"
-	"testing"
-
-	"github.com/btcsuite/btcd/wire"
-	"github.com/lightningnetwork/lnd/chainntnfs"
-	"github.com/lightningnetwork/lnd/input"
-	"github.com/lightningnetwork/lnd/lntypes"
-	"github.com/lightningnetwork/lnd/lnwallet"
-)
-
-const (
-	outgoingContestHtlcExpiry = 110
-)
-
-// TestHtlcOutgoingResolverTimeout tests resolution of an offered htlc that
-// timed out.
-func TestHtlcOutgoingResolverTimeout(t *testing.T) {
-	t.Parallel()
-	defer timeout(t)()
-
-	// Setup the resolver with our test resolution.
-	ctx := newOutgoingResolverTestContext(t)
-
-	// Start the resolution process in a goroutine.
-	ctx.resolve()
-
-	// Notify arrival of the block after which the timeout path of the htlc
-	// unlocks.
-	ctx.notifyEpoch(outgoingContestHtlcExpiry - 1)
-
-	// Assert that the resolver finishes without error and transforms in a
-	// timeout resolver.
-	ctx.waitForResult(true)
-}
-
-// TestHtlcOutgoingResolverRemoteClaim tests resolution of an offered htlc that
-// is claimed by the remote party.
-func TestHtlcOutgoingResolverRemoteClaim(t *testing.T) {
-	t.Parallel()
-	defer timeout(t)()
-
-	// Setup the resolver with our test resolution and start the resolution
-	// process.
-	ctx := newOutgoingResolverTestContext(t)
-	ctx.resolve()
-
-	// The remote party sweeps the htlc. Notify our resolver of this event.
-	preimage := lntypes.Preimage{}
-	ctx.notifier.spendChan <- &chainntnfs.SpendDetail{
-		SpendingTx: &wire.MsgTx{
-			TxIn: []*wire.TxIn{
-				{
-					Witness: [][]byte{
-						{0}, {1}, {2}, preimage[:],
-					},
-				},
-			},
-		},
-	}
-
-	// We expect the extracted preimage to be added to the witness beacon.
-	<-ctx.preimageDB.newPreimages
-
-	// We also expect a resolution message to the incoming side of the
-	// circuit.
-	<-ctx.resolutionChan
-
-	// Assert that the resolver finishes without error.
-	ctx.waitForResult(false)
-}
-
-type resolveResult struct {
-	err          error
-	nextResolver ContractResolver
-}
-
-type outgoingResolverTestContext struct {
-	resolver           *htlcOutgoingContestResolver
-	notifier           *mockNotifier
-	preimageDB         *mockWitnessBeacon
-	resolverResultChan chan resolveResult
-	resolutionChan     chan ResolutionMsg
-	t                  *testing.T
-}
-
-func newOutgoingResolverTestContext(t *testing.T) *outgoingResolverTestContext {
-	notifier := &mockNotifier{
-		epochChan: make(chan *chainntnfs.BlockEpoch),
-		spendChan: make(chan *chainntnfs.SpendDetail),
-		confChan:  make(chan *chainntnfs.TxConfirmation),
-	}
-
-	checkPointChan := make(chan struct{}, 1)
-	resolutionChan := make(chan ResolutionMsg, 1)
-
-	preimageDB := newMockWitnessBeacon()
-
-	chainCfg := ChannelArbitratorConfig{
-		ChainArbitratorConfig: ChainArbitratorConfig{
-			Notifier:   notifier,
-			PreimageDB: preimageDB,
-			DeliverResolutionMsg: func(msgs ...ResolutionMsg) error {
-				if len(msgs) != 1 {
-					return fmt.Errorf("expected 1 "+
-						"resolution msg, instead got %v",
-						len(msgs))
-				}
-
-				resolutionChan <- msgs[0]
-				return nil
-			},
-		},
-	}
-
-	outgoingRes := lnwallet.OutgoingHtlcResolution{
-		Expiry: outgoingContestHtlcExpiry,
-		SweepSignDesc: input.SignDescriptor{
-			Output: &wire.TxOut{},
-		},
-	}
-
-	resolver := &htlcOutgoingContestResolver{
-		htlcTimeoutResolver: htlcTimeoutResolver{
-			ResolverKit: ResolverKit{
-				ChannelArbitratorConfig: chainCfg,
-				Checkpoint: func(_ ContractResolver) error {
-					checkPointChan <- struct{}{}
-					return nil
-				},
-			},
-			htlcResolution: outgoingRes,
-		},
-	}
-
-	return &outgoingResolverTestContext{
-		resolver:       resolver,
-		notifier:       notifier,
-		preimageDB:     preimageDB,
-		resolutionChan: resolutionChan,
-		t:              t,
-	}
-}
-
-func (i *outgoingResolverTestContext) resolve() {
-	// Start resolver.
-	i.resolverResultChan = make(chan resolveResult, 1)
-	go func() {
-		nextResolver, err := i.resolver.Resolve()
-		i.resolverResultChan <- resolveResult{
-			nextResolver: nextResolver,
-			err:          err,
-		}
-	}()
-
-	// Notify initial block height.
-	i.notifyEpoch(testInitialBlockHeight)
-}
-
-func (i *outgoingResolverTestContext) notifyEpoch(height int32) {
-	i.notifier.epochChan <- &chainntnfs.BlockEpoch{
-		Height: height,
-	}
-}
-
-func (i *outgoingResolverTestContext) waitForResult(expectTimeoutRes bool) {
-	i.t.Helper()
-
-	result := <-i.resolverResultChan
-	if result.err != nil {
-		i.t.Fatal(result.err)
-	}
-
-	if !expectTimeoutRes {
-		if result.nextResolver != nil {
-			i.t.Fatal("expected no next resolver")
-		}
-		return
-	}
-
-	_, ok := result.nextResolver.(*htlcTimeoutResolver)
-	if !ok {
-		i.t.Fatal("expected htlcTimeoutResolver")
-	}
-}
diff --git a/routing/missioncontrol_test.go b/routing/missioncontrol_test.go
index bbef69c94..f7b2f33a0 100644
--- a/routing/missioncontrol_test.go
+++ b/routing/missioncontrol_test.go
@@ -13,7 +13,7 @@ import (
 
 var (
 	mcTestRoute = &route.Route{
-		SourcePubKey: route.Vertex{10},
+		SourcePubKey: mcTestSelf,
 		Hops: []*route.Hop{
 			{
 				ChannelID:     1,
@@ -30,6 +30,7 @@ var (
 	}
 
 	mcTestTime  = time.Date(2018, time.January, 9, 14, 00, 00, 0, time.UTC)
+	mcTestSelf  = route.Vertex{10}
 	mcTestNode1 = mcTestRoute.Hops[0].PubKeyBytes
 	mcTestNode2 = mcTestRoute.Hops[1].PubKeyBytes
 
@@ -80,6 +81,7 @@ func (ctx *mcTestContext) restartMc() {
 			PenaltyHalfLife:       testPenaltyHalfLife,
 			AprioriHopProbability: testAprioriHopProbability,
 			AprioriWeight:         testAprioriWeight,
+			SelfNode:              mcTestSelf,
 		},
 	)
 	if err != nil {
@@ -98,7 +100,6 @@ func (ctx *mcTestContext) cleanup() {
 
 // Assert that mission control returns a probability for an edge.
 func (ctx *mcTestContext) expectP(amt lnwire.MilliSatoshi, expected float64) {
-
 	ctx.t.Helper()
 
 	p := ctx.mc.GetProbability(mcTestNode1, mcTestNode2, amt)
@@ -138,6 +139,13 @@ func TestMissionControl(t *testing.T) {
 
 	testTime := time.Date(2018, time.January, 9, 14, 00, 00, 0, time.UTC)
 
+	// For local channels, we expect a higher probability than our a prior
+	// test probability.
+	selfP := ctx.mc.GetProbability(mcTestSelf, mcTestNode1, 100)
+	if selfP != prevSuccessProbability {
+		t.Fatalf("expected prev success prob for untried local chans")
+	}
+
 	// Initial probability is expected to be the a priori.
 	ctx.expectP(1000, testAprioriHopProbability)