13566028875

Committed 27 Feb 2025 12:09PM UTC coverage: 49.396% (-9.4%) from 58.748%

Build # 13566028875

Build Type

Pull #9555

github

Committed by

ellemouton

Commit Message

graph/db: populate the graph cache in Start instead of during construction

In this commit, we move the graph cache population logic out of the
ChannelGraph constructor and into its Start method instead.

Pull Request Pull Request #9555: graph: extract cache from CRUD [6]

Run Details

34 of 54 new or added lines in 4 files covered. (62.96%)

27464 existing lines in 436 files now uncovered.

101095 of 204664 relevant lines covered (49.4%)

1.54 hits per line

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

74.68

/shachain/store.go

package shachain

import (
        "encoding/binary"
        "io"

        "github.com/btcsuite/btcd/chaincfg/chainhash"
        "github.com/go-errors/errors"
)

// Store is an interface which serves as an abstraction over data structure
// responsible for efficiently storing and restoring of hash secrets by given
// indexes.
//
// Description: The Lightning Network wants a chain of (say 1 million)
// unguessable 256 bit values; we generate them and send them one at a time to
// a remote node.  We don't want the remote node to have to store all the
// values, so it's better if they can derive them once they see them.
type Store interface {
        // LookUp function is used to restore/lookup/fetch the previous secret
        // by its index.
        LookUp(uint64) (*chainhash.Hash, error)

        // AddNextEntry attempts to store the given hash within its internal
        // storage in an efficient manner.
        //
        // NOTE: The hashes derived from the shachain MUST be inserted in the
        // order they're produced by a shachain.Producer.
        AddNextEntry(*chainhash.Hash) error

        // Encode writes a binary serialization of the shachain elements
        // currently saved by implementation of shachain.Store to the passed
        // io.Writer.
        Encode(io.Writer) error
}

// RevocationStore is a concrete implementation of the Store interface. The
// revocation store is able to efficiently store N derived shachain elements in
// a space efficient manner with a space complexity of O(log N). The original
// description of the storage methodology can be found here:
// https://github.com/lightningnetwork/lightning-rfc/blob/master/03-transactions.md#efficient-per-commitment-secret-storage
type RevocationStore struct {
        // lenBuckets stores the number of currently active buckets.
        lenBuckets uint8

        // buckets is an array of elements from which we may derive all
        // previous elements, each bucket corresponds to the element with the
        // particular number of trailing zeros.
        buckets [maxHeight]element

        // index is an available index which will be assigned to the new
        // element.
        index index
}

// A compile time check to ensure RevocationStore implements the Store
// interface.
var _ Store = (*RevocationStore)(nil)

// NewRevocationStore creates the new shachain store.
func NewRevocationStore() *RevocationStore {
        return &RevocationStore{
                lenBuckets: 0,
                index:      startIndex,
        }
}

// NewRevocationStoreFromBytes recreates the initial store state from the given
// binary shachain store representation.
func NewRevocationStoreFromBytes(r io.Reader) (*RevocationStore, error) {
        store := &RevocationStore{}

        if err := binary.Read(r, binary.BigEndian, &store.lenBuckets); err != nil {
                return nil, err
        }

        for i := uint8(0); i < store.lenBuckets; i++ {
                var hashIndex index
                err := binary.Read(r, binary.BigEndian, &hashIndex)
                if err != nil {
                        return nil, err
                }

                var nextHash chainhash.Hash
                if _, err := io.ReadFull(r, nextHash[:]); err != nil {
                        return nil, err
                }

                store.buckets[i] = element{
                        index: hashIndex,
                        hash:  nextHash,
                }
        }

        if err := binary.Read(r, binary.BigEndian, &store.index); err != nil {
                return nil, err
        }

        return store, nil
}

// LookUp function is used to restore/lookup/fetch the previous secret by its
// index. If secret which corresponds to given index was not previously placed
// in store we will not able to derive it and function will fail.
//
// NOTE: This function is part of the Store interface.
func (store *RevocationStore) LookUp(v uint64) (*chainhash.Hash, error) {
        ind := newIndex(v)

        // Trying to derive the index from one of the existing buckets elements.
        for i := uint8(0); i < store.lenBuckets; i++ {
                element, err := store.buckets[i].derive(ind)
                if err != nil {
                        continue
                }

                return &element.hash, nil
        }

        return nil, errors.Errorf("unable to derive hash #%v", ind)
}

// AddNextEntry attempts to store the given hash within its internal storage in
// an efficient manner.
//
// NOTE: The hashes derived from the shachain MUST be inserted in the order
// they're produced by a shachain.Producer.
//
// NOTE: This function is part of the Store interface.
func (store *RevocationStore) AddNextEntry(hash *chainhash.Hash) error {
        newElement := &element{
                index: store.index,
                hash:  *hash,
        }

        bucket := countTrailingZeros(newElement.index)

        for i := uint8(0); i < bucket; i++ {
                e, err := newElement.derive(store.buckets[i].index)
                if err != nil {
                        return err
                }

                if !e.isEqual(&store.buckets[i]) {
                        return errors.New("hash isn't derivable from " +
                                "previous ones")
                }
        }

        store.buckets[bucket] = *newElement
        if bucket+1 > store.lenBuckets {
                store.lenBuckets = bucket + 1
        }

        store.index--
        return nil
}

// Encode writes a binary serialization of the shachain elements currently
// saved by implementation of shachain.Store to the passed io.Writer.
//
// NOTE: This function is part of the Store interface.
func (store *RevocationStore) Encode(w io.Writer) error {
        err := binary.Write(w, binary.BigEndian, store.lenBuckets)
        if err != nil {
                return err
        }

        for i := uint8(0); i < store.lenBuckets; i++ {
                element := store.buckets[i]

                err := binary.Write(w, binary.BigEndian, element.index)
                if err != nil {
                        return err
                }

                if _, err = w.Write(element.hash[:]); err != nil {
                        return err
                }

        }

        return binary.Write(w, binary.BigEndian, store.index)
}

1	package shachain
2
3	import (
4	"encoding/binary"
5	"io"
6
7	"github.com/btcsuite/btcd/chaincfg/chainhash"
8	"github.com/go-errors/errors"
9	)
10
11	// Store is an interface which serves as an abstraction over data structure
12	// responsible for efficiently storing and restoring of hash secrets by given
13	// indexes.
14	//
15	// Description: The Lightning Network wants a chain of (say 1 million)
16	// unguessable 256 bit values; we generate them and send them one at a time to
17	// a remote node. We don't want the remote node to have to store all the
18	// values, so it's better if they can derive them once they see them.
19	type Store interface {
20	// LookUp function is used to restore/lookup/fetch the previous secret
21	// by its index.
22	LookUp(uint64) (*chainhash.Hash, error)
23
24	// AddNextEntry attempts to store the given hash within its internal
25	// storage in an efficient manner.
26	//
27	// NOTE: The hashes derived from the shachain MUST be inserted in the
28	// order they're produced by a shachain.Producer.
29	AddNextEntry(*chainhash.Hash) error
30
31	// Encode writes a binary serialization of the shachain elements
32	// currently saved by implementation of shachain.Store to the passed
33	// io.Writer.
34	Encode(io.Writer) error
35	}
36
37	// RevocationStore is a concrete implementation of the Store interface. The
38	// revocation store is able to efficiently store N derived shachain elements in
39	// a space efficient manner with a space complexity of O(log N). The original
40	// description of the storage methodology can be found here:
41	// https://github.com/lightningnetwork/lightning-rfc/blob/master/03-transactions.md#efficient-per-commitment-secret-storage
42	type RevocationStore struct {
43	// lenBuckets stores the number of currently active buckets.
44	lenBuckets uint8
45
46	// buckets is an array of elements from which we may derive all
47	// previous elements, each bucket corresponds to the element with the
48	// particular number of trailing zeros.
49	buckets [maxHeight]element
50
51	// index is an available index which will be assigned to the new
52	// element.
53	index index
54	}
55
56	// A compile time check to ensure RevocationStore implements the Store
57	// interface.
58	var _ Store = (*RevocationStore)(nil)
59
60	// NewRevocationStore creates the new shachain store.
61	func NewRevocationStore() *RevocationStore {	3✔
62	return &RevocationStore{	3✔
63	lenBuckets: 0,	3✔
64	index: startIndex,	3✔
65	}	3✔
66	}	3✔
67
68	// NewRevocationStoreFromBytes recreates the initial store state from the given
69	// binary shachain store representation.
70	func NewRevocationStoreFromBytes(r io.Reader) (*RevocationStore, error) {	3✔
71	store := &RevocationStore{}	3✔
72		3✔
73	if err := binary.Read(r, binary.BigEndian, &store.lenBuckets); err != nil {	3✔
74	return nil, err	×
75	}	×
76
77	for i := uint8(0); i < store.lenBuckets; i++ {	6✔
78	var hashIndex index	3✔
79	err := binary.Read(r, binary.BigEndian, &hashIndex)	3✔
80	if err != nil {	3✔
81	return nil, err	×
82	}	×
83
84	var nextHash chainhash.Hash	3✔
85	if _, err := io.ReadFull(r, nextHash[:]); err != nil {	3✔
86	return nil, err	×
87	}	×
88
89	store.buckets[i] = element{	3✔
90	index: hashIndex,	3✔
91	hash: nextHash,	3✔
92	}	3✔
93	}
94
95	if err := binary.Read(r, binary.BigEndian, &store.index); err != nil {	3✔
96	return nil, err	×
97	}	×
98
99	return store, nil	3✔
100	}
101
102	// LookUp function is used to restore/lookup/fetch the previous secret by its
103	// index. If secret which corresponds to given index was not previously placed
104	// in store we will not able to derive it and function will fail.
105	//
106	// NOTE: This function is part of the Store interface.
107	func (store RevocationStore) LookUp(v uint64) (chainhash.Hash, error) {	3✔
108	ind := newIndex(v)	3✔
109		3✔
110	// Trying to derive the index from one of the existing buckets elements.	3✔
111	for i := uint8(0); i < store.lenBuckets; i++ {	6✔
112	element, err := store.buckets[i].derive(ind)	3✔
113	if err != nil {	6✔
114	continue	3✔
115	}
116
117	return &element.hash, nil	3✔
118	}
119
120	return nil, errors.Errorf("unable to derive hash #%v", ind)	×
121	}
122
123	// AddNextEntry attempts to store the given hash within its internal storage in
124	// an efficient manner.
125	//
126	// NOTE: The hashes derived from the shachain MUST be inserted in the order
127	// they're produced by a shachain.Producer.
128	//
129	// NOTE: This function is part of the Store interface.
130	func (store RevocationStore) AddNextEntry(hash chainhash.Hash) error {	3✔
131	newElement := &element{	3✔
132	index: store.index,	3✔
133	hash: *hash,	3✔
134	}	3✔
135		3✔
136	bucket := countTrailingZeros(newElement.index)	3✔
137		3✔
138	for i := uint8(0); i < bucket; i++ {	6✔
139	e, err := newElement.derive(store.buckets[i].index)	3✔
140	if err != nil {	3✔
141	return err	×
142	}	×
143
144	if !e.isEqual(&store.buckets[i]) {	3✔
UNCOV 145	return errors.New("hash isn't derivable from " +	×
UNCOV 146	"previous ones")	×
UNCOV 147	}	×
148	}
149
150	store.buckets[bucket] = *newElement	3✔
151	if bucket+1 > store.lenBuckets {	6✔
152	store.lenBuckets = bucket + 1	3✔
153	}	3✔
154
155	store.index--	3✔
156	return nil	3✔
157	}
158
159	// Encode writes a binary serialization of the shachain elements currently
160	// saved by implementation of shachain.Store to the passed io.Writer.
161	//
162	// NOTE: This function is part of the Store interface.
163	func (store *RevocationStore) Encode(w io.Writer) error {	3✔
164	err := binary.Write(w, binary.BigEndian, store.lenBuckets)	3✔
165	if err != nil {	3✔
166	return err	×
167	}	×
168
169	for i := uint8(0); i < store.lenBuckets; i++ {	6✔
170	element := store.buckets[i]	3✔
171		3✔
172	err := binary.Write(w, binary.BigEndian, element.index)	3✔
173	if err != nil {	3✔
174	return err	×
175	}	×
176
177	if _, err = w.Write(element.hash[:]); err != nil {	3✔
178	return err	×
179	}	×
180
181	}
182
183	return binary.Write(w, binary.BigEndian, store.index)	3✔
184	}

lightningnetwork / lnd / 13566028875

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