13523316608

Committed 25 Feb 2025 02:12PM UTC coverage: 49.351% (-9.5%) from 58.835%

Build # 13523316608

Build Type

Pull #9549

github

Committed by

yyforyongyu

Commit Message

routing/chainview: refactor `TestFilteredChainView`

So each test has its own miner and chainView.

Pull Request Pull Request #9549: Fix unit test flake `TestHistoricalConfDetailsTxIndex`

Run Details

0 of 120 new or added lines in 1 file covered. (0.0%)

27196 existing lines in 434 files now uncovered.

100945 of 204543 relevant lines covered (49.35%)

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 / 13523316608

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