17011395530

Committed 16 Aug 2025 06:08PM UTC coverage: 57.298% (-9.5%) from 66.765%

Build # 17011395530

Build Type

Pull #10167

github

Committed by

web-flow

Commit Message

Merge 3c250722d into fb1adfc21

Pull Request Pull Request #10167: multi: bump Go to 1.24.6

Run Details

99112 of 172975 relevant lines covered (57.3%)

1.78 hits per line

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

10.26

/autopilot/prefattach.go

package autopilot

import (
        "context"
        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(ctx context.Context, 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{})
        )
        err := g.ForEachNodesChannels(
                ctx, func(_ context.Context, node Node,
                        channels []*ChannelEdge) error {

                        for _, e := range channels {
                                if _, ok := seenChans[e.ChanID.ToUint64()]; ok {
                                        continue
                                }
                                seenChans[e.ChanID.ToUint64()] = struct{}{}
                                allChans = append(allChans, e.Capacity)
                        }

                        return nil
                },
                func() {
                        allChans = nil
                        clear(seenChans)
                },
        )
        if 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)
        err = g.ForEachNodesChannels(
                ctx, func(ctx context.Context, node Node,
                        edges []*ChannelEdge) error {

                        var nodeChans int
                        for _, e := range edges {
                                // 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.
                                //
                                //nolint:ll
                                if e.Capacity <
                                        medianChanSize/minMedianChanSizeFraction {

                                        nodeChans--

                                        continue
                                }

                                // Larger channels we count.
                                nodeChans++
                        }

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

lightningnetwork / lnd / 17011395530

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