forked from tendermint/tendermint
-
Notifications
You must be signed in to change notification settings - Fork 2
/
dynamic_verifier.go
275 lines (245 loc) · 8.4 KB
/
dynamic_verifier.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
package lite
import (
"bytes"
"fmt"
"sync"
log "github.com/kava-labs/tendermint/libs/log"
lerr "github.com/kava-labs/tendermint/lite/errors"
"github.com/kava-labs/tendermint/types"
)
const sizeOfPendingMap = 1024
var _ Verifier = (*DynamicVerifier)(nil)
// DynamicVerifier implements an auto-updating Verifier. It uses a
// "source" provider to obtain the needed FullCommits to securely sync with
// validator set changes. It stores properly validated data on the
// "trusted" local system.
// TODO: make this single threaded and create a new
// ConcurrentDynamicVerifier that wraps it with concurrency.
// see https://github.com/kava-labs/tendermint/issues/3170
type DynamicVerifier struct {
chainID string
logger log.Logger
// Already validated, stored locally
trusted PersistentProvider
// New info, like a node rpc, or other import method.
source Provider
// pending map to synchronize concurrent verification requests
mtx sync.Mutex
pendingVerifications map[int64]chan struct{}
}
// NewDynamicVerifier returns a new DynamicVerifier. It uses the
// trusted provider to store validated data and the source provider to
// obtain missing data (e.g. FullCommits).
//
// The trusted provider should be a DBProvider.
// The source provider should be a client.HTTPProvider.
func NewDynamicVerifier(chainID string, trusted PersistentProvider, source Provider) *DynamicVerifier {
return &DynamicVerifier{
logger: log.NewNopLogger(),
chainID: chainID,
trusted: trusted,
source: source,
pendingVerifications: make(map[int64]chan struct{}, sizeOfPendingMap),
}
}
func (dv *DynamicVerifier) SetLogger(logger log.Logger) {
logger = logger.With("module", "lite")
dv.logger = logger
dv.trusted.SetLogger(logger)
dv.source.SetLogger(logger)
}
// Implements Verifier.
func (dv *DynamicVerifier) ChainID() string {
return dv.chainID
}
// Implements Verifier.
//
// If the validators have changed since the last known time, it looks to
// dv.trusted and dv.source to prove the new validators. On success, it will
// try to store the SignedHeader in dv.trusted if the next
// validator can be sourced.
func (dv *DynamicVerifier) Verify(shdr types.SignedHeader) error {
// Performs synchronization for multi-threads verification at the same height.
dv.mtx.Lock()
if pending := dv.pendingVerifications[shdr.Height]; pending != nil {
dv.mtx.Unlock()
<-pending // pending is chan struct{}
} else {
pending := make(chan struct{})
dv.pendingVerifications[shdr.Height] = pending
defer func() {
close(pending)
dv.mtx.Lock()
delete(dv.pendingVerifications, shdr.Height)
dv.mtx.Unlock()
}()
dv.mtx.Unlock()
}
//Get the exact trusted commit for h, and if it is
// equal to shdr, then it's already trusted, so
// just return nil.
trustedFCSameHeight, err := dv.trusted.LatestFullCommit(dv.chainID, shdr.Height, shdr.Height)
if err == nil {
// If loading trust commit successfully, and trust commit equal to shdr, then don't verify it,
// just return nil.
if bytes.Equal(trustedFCSameHeight.SignedHeader.Hash(), shdr.Hash()) {
dv.logger.Info(fmt.Sprintf("Load full commit at height %d from cache, there is not need to verify.", shdr.Height))
return nil
}
} else if !lerr.IsErrCommitNotFound(err) {
// Return error if it is not CommitNotFound error
dv.logger.Info(fmt.Sprintf("Encountered unknown error in loading full commit at height %d.", shdr.Height))
return err
}
// Get the latest known full commit <= h-1 from our trusted providers.
// The full commit at h-1 contains the valset to sign for h.
prevHeight := shdr.Height - 1
trustedFC, err := dv.trusted.LatestFullCommit(dv.chainID, 1, prevHeight)
if err != nil {
return err
}
// sync up to the prevHeight and assert our latest NextValidatorSet
// is the ValidatorSet for the SignedHeader
if trustedFC.Height() == prevHeight {
// Return error if valset doesn't match.
if !bytes.Equal(
trustedFC.NextValidators.Hash(),
shdr.Header.ValidatorsHash) {
return lerr.ErrUnexpectedValidators(
trustedFC.NextValidators.Hash(),
shdr.Header.ValidatorsHash)
}
} else {
// If valset doesn't match, try to update
if !bytes.Equal(
trustedFC.NextValidators.Hash(),
shdr.Header.ValidatorsHash) {
// ... update.
trustedFC, err = dv.updateToHeight(prevHeight)
if err != nil {
return err
}
// Return error if valset _still_ doesn't match.
if !bytes.Equal(trustedFC.NextValidators.Hash(),
shdr.Header.ValidatorsHash) {
return lerr.ErrUnexpectedValidators(
trustedFC.NextValidators.Hash(),
shdr.Header.ValidatorsHash)
}
}
}
// Verify the signed header using the matching valset.
cert := NewBaseVerifier(dv.chainID, trustedFC.Height()+1, trustedFC.NextValidators)
err = cert.Verify(shdr)
if err != nil {
return err
}
// By now, the SignedHeader is fully validated and we're synced up to
// SignedHeader.Height - 1. To sync to SignedHeader.Height, we need
// the validator set at SignedHeader.Height + 1 so we can verify the
// SignedHeader.NextValidatorSet.
// TODO: is the ValidateFull below mostly redundant with the BaseVerifier.Verify above?
// See https://github.com/kava-labs/tendermint/issues/3174.
// Get the next validator set.
nextValset, err := dv.source.ValidatorSet(dv.chainID, shdr.Height+1)
if lerr.IsErrUnknownValidators(err) {
// Ignore this error.
return nil
} else if err != nil {
return err
}
// Create filled FullCommit.
nfc := FullCommit{
SignedHeader: shdr,
Validators: trustedFC.NextValidators,
NextValidators: nextValset,
}
// Validate the full commit. This checks the cryptographic
// signatures of Commit against Validators.
if err := nfc.ValidateFull(dv.chainID); err != nil {
return err
}
// Trust it.
return dv.trusted.SaveFullCommit(nfc)
}
// verifyAndSave will verify if this is a valid source full commit given the
// best match trusted full commit, and if good, persist to dv.trusted.
// Returns ErrNotEnoughVotingPowerSigned when >2/3 of trustedFC did not sign sourceFC.
// Panics if trustedFC.Height() >= sourceFC.Height().
func (dv *DynamicVerifier) verifyAndSave(trustedFC, sourceFC FullCommit) error {
if trustedFC.Height() >= sourceFC.Height() {
panic("should not happen")
}
err := trustedFC.NextValidators.VerifyFutureCommit(
sourceFC.Validators,
dv.chainID, sourceFC.SignedHeader.Commit.BlockID,
sourceFC.SignedHeader.Height, sourceFC.SignedHeader.Commit,
)
if err != nil {
return err
}
return dv.trusted.SaveFullCommit(sourceFC)
}
// updateToHeight will use divide-and-conquer to find a path to h.
// Returns nil error iff we successfully verify and persist a full commit
// for height h, using repeated applications of bisection if necessary.
//
// Returns ErrCommitNotFound if source provider doesn't have the commit for h.
func (dv *DynamicVerifier) updateToHeight(h int64) (FullCommit, error) {
// Fetch latest full commit from source.
sourceFC, err := dv.source.LatestFullCommit(dv.chainID, h, h)
if err != nil {
return FullCommit{}, err
}
// If sourceFC.Height() != h, we can't do it.
if sourceFC.Height() != h {
return FullCommit{}, lerr.ErrCommitNotFound()
}
// Validate the full commit. This checks the cryptographic
// signatures of Commit against Validators.
if err := sourceFC.ValidateFull(dv.chainID); err != nil {
return FullCommit{}, err
}
// Verify latest FullCommit against trusted FullCommits
FOR_LOOP:
for {
// Fetch latest full commit from trusted.
trustedFC, err := dv.trusted.LatestFullCommit(dv.chainID, 1, h)
if err != nil {
return FullCommit{}, err
}
// We have nothing to do.
if trustedFC.Height() == h {
return trustedFC, nil
}
// Try to update to full commit with checks.
err = dv.verifyAndSave(trustedFC, sourceFC)
if err == nil {
// All good!
return sourceFC, nil
}
// Handle special case when err is ErrNotEnoughVotingPowerSigned.
if types.IsErrNotEnoughVotingPowerSigned(err) {
// Divide and conquer.
start, end := trustedFC.Height(), sourceFC.Height()
if !(start < end) {
panic("should not happen")
}
mid := (start + end) / 2
_, err = dv.updateToHeight(mid)
if err != nil {
return FullCommit{}, err
}
// If we made it to mid, we retry.
continue FOR_LOOP
}
return FullCommit{}, err
}
}
func (dv *DynamicVerifier) LastTrustedHeight() int64 {
fc, err := dv.trusted.LatestFullCommit(dv.chainID, 1, 1<<63-1)
if err != nil {
panic("should not happen")
}
return fc.Height()
}