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

6.6

/autopilot/prefattach.go

package autopilot

import (
        prand "math/rand"
        "time"

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

// minMedianChanSizeFraction determines the minimum size a channel must have to
// count positively when calculating the scores using preferential attachment.
// The minimum channel size is calculated as median/minMedianChanSizeFraction,
// where median is the median channel size of the entire graph.
const minMedianChanSizeFraction = 4

// PrefAttachment is an implementation of the AttachmentHeuristic interface
// that implement a non-linear preferential attachment heuristic. This means
// that given a threshold to allocate to automatic channel establishment, the
// heuristic will attempt to favor connecting to nodes which already have a set
// amount of links, selected by sampling from a power law distribution. The
// attachment is non-linear in that it favors nodes with a higher in-degree but
// less so than regular linear preferential attachment. As a result, this
// creates smaller and less clusters than regular linear preferential
// attachment.
//
// TODO(roasbeef): BA, with k=-3
type PrefAttachment struct {
}

// NewPrefAttachment creates a new instance of a PrefAttachment heuristic.
func NewPrefAttachment() *PrefAttachment {
        prand.Seed(time.Now().Unix())
        return &PrefAttachment{}
}

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

// NodeID is a simple type that holds an EC public key serialized in compressed
// format.
type NodeID [33]byte

// NewNodeID creates a new nodeID from a passed public key.
func NewNodeID(pub *btcec.PublicKey) NodeID {
        var n NodeID
        copy(n[:], pub.SerializeCompressed())
        return n
}

// Name returns the name of this heuristic.
//
// NOTE: This is a part of the AttachmentHeuristic interface.
func (p *PrefAttachment) Name() string {
        return "preferential"
}

// NodeScores is a method that given the current channel graph and current set
// of local channels, scores the given nodes according to the preference of
// opening a channel of the given size with them. The returned channel
// candidates maps the NodeID to a NodeScore for the node.
//
// The heuristic employed by this method is one that attempts to promote a
// scale-free network globally, via local attachment preferences for new nodes
// joining the network with an amount of available funds to be allocated to
// channels. Specifically, we consider the degree of each node (and the flow
// in/out of the node available via its open channels) and utilize the
// Barabási–Albert model to drive our recommended attachment heuristics. If
// implemented globally for each new participant, this results in a channel
// graph that is scale-free and follows a power law distribution with k=-3.
//
// To avoid assigning a high score to nodes with a large number of small
// channels, we only count channels at least as large as a given fraction of
// the graph's median channel size.
//
// The returned scores will be in the range [0.0, 1.0], where higher scores are
// given to nodes already having high connectivity in the graph.
//
// NOTE: This is a part of the AttachmentHeuristic interface.
func (p *PrefAttachment) NodeScores(g ChannelGraph, chans []LocalChannel,
        chanSize btcutil.Amount, nodes map[NodeID]struct{}) (
        map[NodeID]*NodeScore, error) {

        // We first run though the graph once in order to find the median
        // channel size.
        var (
                allChans  []btcutil.Amount
                seenChans = make(map[uint64]struct{})
        )
        if err := g.ForEachNode(func(n Node) error {
                err := n.ForEachChannel(func(e ChannelEdge) error {
                        if _, ok := seenChans[e.ChanID.ToUint64()]; ok {
                                return nil
                        }
                        seenChans[e.ChanID.ToUint64()] = struct{}{}
                        allChans = append(allChans, e.Capacity)
                        return nil
                })
                if err != nil {
                        return err
                }

                return nil
        }); err != nil {
                return nil, err
        }

        medianChanSize := Median(allChans)
        log.Tracef("Found channel median %v for preferential score heuristic",
                medianChanSize)

        // Count the number of large-ish channels for each particular node in
        // the graph.
        var maxChans int
        nodeChanNum := make(map[NodeID]int)
        if err := g.ForEachNode(func(n Node) error {
                var nodeChans int
                err := n.ForEachChannel(func(e ChannelEdge) error {
                        // Since connecting to nodes with a lot of small
                        // channels actually worsens our connectivity in the
                        // graph (we will potentially waste time trying to use
                        // these useless channels in path finding), we decrease
                        // the counter for such channels.
                        if e.Capacity < medianChanSize/minMedianChanSizeFraction {
                                nodeChans--
                                return nil
                        }

                        // Larger channels we count.
                        nodeChans++
                        return nil
                })
                if err != nil {
                        return err
                }

                // We keep track of the highest-degree node we've seen, as this
                // will be given the max score.
                if nodeChans > maxChans {
                        maxChans = nodeChans
                }

                // If this node is not among our nodes to score, we can return
                // early.
                nID := NodeID(n.PubKey())
                if _, ok := nodes[nID]; !ok {
                        log.Tracef("Node %x not among nodes to score, "+
                                "ignoring", nID[:])
                        return nil
                }

                // Otherwise we'll record the number of channels.
                nodeChanNum[nID] = nodeChans
                log.Tracef("Counted %v channels for node %x", nodeChans, nID[:])

                return nil
        }); err != nil {
                return nil, err
        }

        // If there are no channels in the graph we cannot determine any
        // preferences, so we return, indicating all candidates get a score of
        // zero.
        if maxChans == 0 {
                log.Tracef("No channels in the graph")
                return nil, nil
        }

        existingPeers := make(map[NodeID]struct{})
        for _, c := range chans {
                existingPeers[c.Node] = struct{}{}
        }

        // For each node in the set of nodes, count their fraction of channels
        // in the graph, and use that as the score.
        candidates := make(map[NodeID]*NodeScore)
        for nID, nodeChans := range nodeChanNum {

                // If the node is among or existing channel peers, we don't
                // need another channel.
                if _, ok := existingPeers[nID]; ok {
                        log.Tracef("Node %x among existing peers for pref "+
                                "attach heuristic, giving zero score", nID[:])
                        continue
                }

                // If the node had no large channels, we skip it, since it
                // would have gotten a zero score anyway.
                if nodeChans <= 0 {
                        log.Tracef("Skipping node %x with channel count %v",
                                nID[:], nodeChans)
                        continue
                }

                // Otherwise we score the node according to its fraction of
                // channels in the graph, scaled such that the highest-degree
                // node will be given a score of 1.0.
                score := float64(nodeChans) / float64(maxChans)
                log.Tracef("Giving node %x a pref attach score of %v",
                        nID[:], score)

                candidates[nID] = &NodeScore{
                        NodeID: nID,
                        Score:  score,
                }
        }

        return candidates, nil
}

1	package autopilot
2
3	import (
4	prand "math/rand"
5	"time"
6
7	"github.com/btcsuite/btcd/btcec/v2"
8	"github.com/btcsuite/btcd/btcutil"
9	)
10
11	// minMedianChanSizeFraction determines the minimum size a channel must have to
12	// count positively when calculating the scores using preferential attachment.
13	// The minimum channel size is calculated as median/minMedianChanSizeFraction,
14	// where median is the median channel size of the entire graph.
15	const minMedianChanSizeFraction = 4
16
17	// PrefAttachment is an implementation of the AttachmentHeuristic interface
18	// that implement a non-linear preferential attachment heuristic. This means
19	// that given a threshold to allocate to automatic channel establishment, the
20	// heuristic will attempt to favor connecting to nodes which already have a set
21	// amount of links, selected by sampling from a power law distribution. The
22	// attachment is non-linear in that it favors nodes with a higher in-degree but
23	// less so than regular linear preferential attachment. As a result, this
24	// creates smaller and less clusters than regular linear preferential
25	// attachment.
26	//
27	// TODO(roasbeef): BA, with k=-3
28	type PrefAttachment struct {
29	}
30
31	// NewPrefAttachment creates a new instance of a PrefAttachment heuristic.
32	func NewPrefAttachment() *PrefAttachment {	3✔
33	prand.Seed(time.Now().Unix())	3✔
34	return &PrefAttachment{}	3✔
35	}	3✔
36
37	// A compile time assertion to ensure PrefAttachment meets the
38	// AttachmentHeuristic interface.
39	var _ AttachmentHeuristic = (*PrefAttachment)(nil)
40
41	// NodeID is a simple type that holds an EC public key serialized in compressed
42	// format.
43	type NodeID [33]byte
44
45	// NewNodeID creates a new nodeID from a passed public key.
UNCOV 46	func NewNodeID(pub *btcec.PublicKey) NodeID {	×
UNCOV 47	var n NodeID	×
UNCOV 48	copy(n[:], pub.SerializeCompressed())	×
UNCOV 49	return n	×
UNCOV 50	}	×
51
52	// Name returns the name of this heuristic.
53	//
54	// NOTE: This is a part of the AttachmentHeuristic interface.
55	func (p *PrefAttachment) Name() string {	3✔
56	return "preferential"	3✔
57	}	3✔
58
59	// NodeScores is a method that given the current channel graph and current set
60	// of local channels, scores the given nodes according to the preference of
61	// opening a channel of the given size with them. The returned channel
62	// candidates maps the NodeID to a NodeScore for the node.
63	//
64	// The heuristic employed by this method is one that attempts to promote a
65	// scale-free network globally, via local attachment preferences for new nodes
66	// joining the network with an amount of available funds to be allocated to
67	// channels. Specifically, we consider the degree of each node (and the flow
68	// in/out of the node available via its open channels) and utilize the
69	// Barabási–Albert model to drive our recommended attachment heuristics. If
70	// implemented globally for each new participant, this results in a channel
71	// graph that is scale-free and follows a power law distribution with k=-3.
72	//
73	// To avoid assigning a high score to nodes with a large number of small
74	// channels, we only count channels at least as large as a given fraction of
75	// the graph's median channel size.
76	//
77	// The returned scores will be in the range [0.0, 1.0], where higher scores are
78	// given to nodes already having high connectivity in the graph.
79	//
80	// NOTE: This is a part of the AttachmentHeuristic interface.
81	func (p *PrefAttachment) NodeScores(g ChannelGraph, chans []LocalChannel,
82	chanSize btcutil.Amount, nodes map[NodeID]struct{}) (
UNCOV 83	map[NodeID]*NodeScore, error) {	×
UNCOV 84		×
UNCOV 85	// We first run though the graph once in order to find the median	×
UNCOV 86	// channel size.	×
UNCOV 87	var (	×
UNCOV 88	allChans []btcutil.Amount	×
UNCOV 89	seenChans = make(map[uint64]struct{})	×
UNCOV 90	)	×
UNCOV 91	if err := g.ForEachNode(func(n Node) error {	×
UNCOV 92	err := n.ForEachChannel(func(e ChannelEdge) error {	×
UNCOV 93	if _, ok := seenChans[e.ChanID.ToUint64()]; ok {	×
UNCOV 94	return nil	×
UNCOV 95	}	×
UNCOV 96	seenChans[e.ChanID.ToUint64()] = struct{}{}	×
UNCOV 97	allChans = append(allChans, e.Capacity)	×
UNCOV 98	return nil	×
99	})
UNCOV 100	if err != nil {	×
101	return err	×
102	}	×
103
UNCOV 104	return nil	×
105	}); err != nil {	×
106	return nil, err	×
107	}	×
108
UNCOV 109	medianChanSize := Median(allChans)	×
UNCOV 110	log.Tracef("Found channel median %v for preferential score heuristic",	×
UNCOV 111	medianChanSize)	×
UNCOV 112		×
UNCOV 113	// Count the number of large-ish channels for each particular node in	×
UNCOV 114	// the graph.	×
UNCOV 115	var maxChans int	×
UNCOV 116	nodeChanNum := make(map[NodeID]int)	×
UNCOV 117	if err := g.ForEachNode(func(n Node) error {	×
UNCOV 118	var nodeChans int	×
UNCOV 119	err := n.ForEachChannel(func(e ChannelEdge) error {	×
UNCOV 120	// Since connecting to nodes with a lot of small	×
UNCOV 121	// channels actually worsens our connectivity in the	×
UNCOV 122	// graph (we will potentially waste time trying to use	×
UNCOV 123	// these useless channels in path finding), we decrease	×
UNCOV 124	// the counter for such channels.	×
UNCOV 125	if e.Capacity < medianChanSize/minMedianChanSizeFraction {	×
126	nodeChans--	×
127	return nil	×
128	}	×
129
130	// Larger channels we count.
UNCOV 131	nodeChans++	×
UNCOV 132	return nil	×
133	})
UNCOV 134	if err != nil {	×
135	return err	×
136	}	×
137
138	// We keep track of the highest-degree node we've seen, as this
139	// will be given the max score.
UNCOV 140	if nodeChans > maxChans {	×
UNCOV 141	maxChans = nodeChans	×
UNCOV 142	}	×
143
144	// If this node is not among our nodes to score, we can return
145	// early.
UNCOV 146	nID := NodeID(n.PubKey())	×
UNCOV 147	if _, ok := nodes[nID]; !ok {	×
148	log.Tracef("Node %x not among nodes to score, "+	×
149	"ignoring", nID[:])	×
150	return nil	×
151	}	×
152
153	// Otherwise we'll record the number of channels.
UNCOV 154	nodeChanNum[nID] = nodeChans	×
UNCOV 155	log.Tracef("Counted %v channels for node %x", nodeChans, nID[:])	×
UNCOV 156		×
UNCOV 157	return nil	×
158	}); err != nil {	×
159	return nil, err	×
160	}	×
161
162	// If there are no channels in the graph we cannot determine any
163	// preferences, so we return, indicating all candidates get a score of
164	// zero.
UNCOV 165	if maxChans == 0 {	×
UNCOV 166	log.Tracef("No channels in the graph")	×
UNCOV 167	return nil, nil	×
UNCOV 168	}	×
169
UNCOV 170	existingPeers := make(map[NodeID]struct{})	×
UNCOV 171	for _, c := range chans {	×
UNCOV 172	existingPeers[c.Node] = struct{}{}	×
UNCOV 173	}	×
174
175	// For each node in the set of nodes, count their fraction of channels
176	// in the graph, and use that as the score.
UNCOV 177	candidates := make(map[NodeID]*NodeScore)	×
UNCOV 178	for nID, nodeChans := range nodeChanNum {	×
UNCOV 179		×
UNCOV 180	// If the node is among or existing channel peers, we don't	×
UNCOV 181	// need another channel.	×
UNCOV 182	if _, ok := existingPeers[nID]; ok {	×
UNCOV 183	log.Tracef("Node %x among existing peers for pref "+	×
UNCOV 184	"attach heuristic, giving zero score", nID[:])	×
UNCOV 185	continue	×
186	}
187
188	// If the node had no large channels, we skip it, since it
189	// would have gotten a zero score anyway.
UNCOV 190	if nodeChans <= 0 {	×
UNCOV 191	log.Tracef("Skipping node %x with channel count %v",	×
UNCOV 192	nID[:], nodeChans)	×
UNCOV 193	continue	×
194	}
195
196	// Otherwise we score the node according to its fraction of
197	// channels in the graph, scaled such that the highest-degree
198	// node will be given a score of 1.0.
UNCOV 199	score := float64(nodeChans) / float64(maxChans)	×
UNCOV 200	log.Tracef("Giving node %x a pref attach score of %v",	×
UNCOV 201	nID[:], score)	×
UNCOV 202		×
UNCOV 203	candidates[nID] = &NodeScore{	×
UNCOV 204	NodeID: nID,	×
UNCOV 205	Score: score,	×
UNCOV 206	}	×
207	}
208
UNCOV 209	return candidates, nil	×
210	}

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