13211764208

Committed 08 Feb 2025 03:08AM UTC coverage: 49.288% (-9.5%) from 58.815%

Build # 13211764208

Build Type

Pull #9489

github

Committed by

calvinrzachman

Commit Message

itest: verify switchrpc server enforces send then track

We prevent the rpc server from allowing onion dispatches for
attempt IDs which have already been tracked by rpc clients.

This helps protect the client from leaking a duplicate onion
attempt. NOTE: This is not the only method for solving this
issue! The issue could be addressed via careful client side
programming which accounts for the uncertainty and async
nature of dispatching onions to a remote process via RPC.
This would require some lnd ChannelRouter changes for how
we intend to use these RPCs though.

Pull Request Pull Request #9489: multi: add BuildOnion, SendOnion, and TrackOnion RPCs

Run Details

474 of 990 new or added lines in 11 files covered. (47.88%)

27321 existing lines in 435 files now uncovered.

101192 of 205306 relevant lines covered (49.29%)

1.54 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

28.21

/autopilot/top_centrality.go

package autopilot

import (
        "runtime"

        "github.com/btcsuite/btcd/btcutil"
)

// TopCentrality is a simple greedy technique to create connections to nodes
// with the top betweenness centrality value. This algorithm is usually
// referred to as TopK in the literature. The idea is that by opening channels
// to nodes with top betweenness centrality we also increase our own betweenness
// centrality (given we already have at least one channel, or create at least
// two new channels).
// A different and much better approach is instead of selecting nodes with top
// centrality value, we extend the graph in a loop by inserting a new non
// existing edge and recalculate the betweenness centrality of each node. This
// technique is usually referred to as "greedy" algorithm and gives better
// results than TopK but is considerably slower too.
type TopCentrality struct {
        centralityMetric *BetweennessCentrality
}

// A compile time assertion to ensure TopCentrality meets the
// AttachmentHeuristic interface.
var _ AttachmentHeuristic = (*TopCentrality)(nil)

// NewTopCentrality constructs and returns a new TopCentrality heuristic.
func NewTopCentrality() *TopCentrality {
        metric, err := NewBetweennessCentralityMetric(
                runtime.NumCPU(),
        )
        if err != nil {
                panic(err)
        }

        return &TopCentrality{
                centralityMetric: metric,
        }
}

// Name returns the name of the heuristic.
func (g *TopCentrality) Name() string {
        return "top_centrality"
}

// NodeScores will return a [0,1] normalized map of scores for the given nodes
// except for the ones we already have channels with. The scores will simply
// be the betweenness centrality values of the nodes.
// As our current implementation of betweenness centrality is non-incremental,
// NodeScores will recalculate the centrality values on every call, which is
// slow for large graphs.
func (g *TopCentrality) NodeScores(graph ChannelGraph, chans []LocalChannel,
        chanSize btcutil.Amount, nodes map[NodeID]struct{}) (
        map[NodeID]*NodeScore, error) {

        // Calculate betweenness centrality for the whole graph.
        if err := g.centralityMetric.Refresh(graph); err != nil {
                return nil, err
        }

        normalize := true
        centrality := g.centralityMetric.GetMetric(normalize)

        // Create a map of the existing peers for faster filtering.
        existingPeers := make(map[NodeID]struct{})
        for _, c := range chans {
                existingPeers[c.Node] = struct{}{}
        }

        result := make(map[NodeID]*NodeScore, len(nodes))
        for nodeID := range nodes {
                // Skip nodes we already have channel with.
                if _, ok := existingPeers[nodeID]; ok {
                        continue
                }

                // Skip passed nodes not in the graph. This could happen if
                // the graph changed before computing the centrality values as
                // the nodes we iterate are prefiltered by the autopilot agent.
                score, ok := centrality[nodeID]
                if !ok {
                        continue
                }

                result[nodeID] = &NodeScore{
                        NodeID: nodeID,
                        Score:  score,
                }
        }

        return result, nil
}

1	package autopilot
2
3	import (
4	"runtime"
5
6	"github.com/btcsuite/btcd/btcutil"
7	)
8
9	// TopCentrality is a simple greedy technique to create connections to nodes
10	// with the top betweenness centrality value. This algorithm is usually
11	// referred to as TopK in the literature. The idea is that by opening channels
12	// to nodes with top betweenness centrality we also increase our own betweenness
13	// centrality (given we already have at least one channel, or create at least
14	// two new channels).
15	// A different and much better approach is instead of selecting nodes with top
16	// centrality value, we extend the graph in a loop by inserting a new non
17	// existing edge and recalculate the betweenness centrality of each node. This
18	// technique is usually referred to as "greedy" algorithm and gives better
19	// results than TopK but is considerably slower too.
20	type TopCentrality struct {
21	centralityMetric *BetweennessCentrality
22	}
23
24	// A compile time assertion to ensure TopCentrality meets the
25	// AttachmentHeuristic interface.
26	var _ AttachmentHeuristic = (*TopCentrality)(nil)
27
28	// NewTopCentrality constructs and returns a new TopCentrality heuristic.
29	func NewTopCentrality() *TopCentrality {	3✔
30	metric, err := NewBetweennessCentralityMetric(	3✔
31	runtime.NumCPU(),	3✔
32	)	3✔
33	if err != nil {	3✔
34	panic(err)	×
35	}
36
37	return &TopCentrality{	3✔
38	centralityMetric: metric,	3✔
39	}	3✔
40	}
41
42	// Name returns the name of the heuristic.
43	func (g *TopCentrality) Name() string {	3✔
44	return "top_centrality"	3✔
45	}	3✔
46
47	// NodeScores will return a [0,1] normalized map of scores for the given nodes
48	// except for the ones we already have channels with. The scores will simply
49	// be the betweenness centrality values of the nodes.
50	// As our current implementation of betweenness centrality is non-incremental,
51	// NodeScores will recalculate the centrality values on every call, which is
52	// slow for large graphs.
53	func (g *TopCentrality) NodeScores(graph ChannelGraph, chans []LocalChannel,
54	chanSize btcutil.Amount, nodes map[NodeID]struct{}) (
UNCOV 55	map[NodeID]*NodeScore, error) {	×
UNCOV 56		×
UNCOV 57	// Calculate betweenness centrality for the whole graph.	×
UNCOV 58	if err := g.centralityMetric.Refresh(graph); err != nil {	×
59	return nil, err	×
60	}	×
61
UNCOV 62	normalize := true	×
UNCOV 63	centrality := g.centralityMetric.GetMetric(normalize)	×
UNCOV 64		×
UNCOV 65	// Create a map of the existing peers for faster filtering.	×
UNCOV 66	existingPeers := make(map[NodeID]struct{})	×
UNCOV 67	for _, c := range chans {	×
UNCOV 68	existingPeers[c.Node] = struct{}{}	×
UNCOV 69	}	×
70
UNCOV 71	result := make(map[NodeID]*NodeScore, len(nodes))	×
UNCOV 72	for nodeID := range nodes {	×
UNCOV 73	// Skip nodes we already have channel with.	×
UNCOV 74	if _, ok := existingPeers[nodeID]; ok {	×
UNCOV 75	continue	×
76	}
77
78	// Skip passed nodes not in the graph. This could happen if
79	// the graph changed before computing the centrality values as
80	// the nodes we iterate are prefiltered by the autopilot agent.
UNCOV 81	score, ok := centrality[nodeID]	×
UNCOV 82	if !ok {	×
83	continue	×
84	}
85
UNCOV 86	result[nodeID] = &NodeScore{	×
UNCOV 87	NodeID: nodeID,	×
UNCOV 88	Score: score,	×
UNCOV 89	}	×
90	}
91
UNCOV 92	return result, nil	×
93	}

lightningnetwork / lnd / 13211764208

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous