/
NegativeUNLVote.cpp
466 lines (427 loc) · 15.5 KB
/
NegativeUNLVote.cpp
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
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
//------------------------------------------------------------------------------
/*
This file is part of rippled: https://github.com/ripple/rippled
Copyright (c) 2020 Ripple Labs Inc.
Permission to use, copy, modify, and/or distribute this software for any
purpose with or without fee is hereby granted, provided that the above
copyright notice and this permission notice appear in all copies.
THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
ANY SPECIAL , DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
*/
//==============================================================================
#include <ripple/app/consensus/RCLValidations.h>
#include <ripple/app/ledger/Ledger.h>
#include <ripple/app/main/Application.h>
#include <ripple/app/misc/NegativeUNLVote.h>
namespace ripple {
NegativeUNLVote::NegativeUNLVote(
NodeID const& myId,
beast::Journal j,
Application& app)
: myId_(myId), j_(j), app_(app)
{
}
void
NegativeUNLVote::doVoting(
std::shared_ptr<Ledger const> const& prevLedger,
hash_set<PublicKey> const& unlKeys,
RCLValidations& validations,
std::shared_ptr<SHAMap> const& initialSet)
{
// Voting steps:
// -- build a reliability score table of validators
// -- process the table and find all candidates to disable or to re-enable
// -- pick one to disable and one to re-enable if any
// -- if found candidates, add ttUNL_MODIFY Tx
// Build NodeID set for internal use.
// Build NodeID to PublicKey map for lookup before creating ttUNL_MODIFY Tx.
hash_set<NodeID> unlNodeIDs;
hash_map<NodeID, PublicKey> nidToKeyMap;
for (auto const& k : unlKeys)
{
auto nid = calcNodeID(k);
nidToKeyMap.emplace(nid, k);
unlNodeIDs.emplace(nid);
}
// Build a reliability score table of validators
if (std::optional<hash_map<NodeID, std::uint32_t>> scoreTable =
buildScoreTable(prevLedger, unlNodeIDs, validations))
{
// build next negUnl
auto negUnlKeys = prevLedger->negativeUNL();
auto negUnlToDisable = prevLedger->validatorToDisable();
auto negUnlToReEnable = prevLedger->validatorToReEnable();
if (negUnlToDisable)
negUnlKeys.insert(*negUnlToDisable);
if (negUnlToReEnable)
negUnlKeys.erase(*negUnlToReEnable);
hash_set<NodeID> negUnlNodeIDs;
for (auto const& k : negUnlKeys)
{
auto nid = calcNodeID(k);
negUnlNodeIDs.emplace(nid);
if (!nidToKeyMap.count(nid))
{
nidToKeyMap.emplace(nid, k);
}
}
auto const seq = prevLedger->info().seq + 1;
purgeNewValidators(seq);
// Process the table and find all candidates to disable or to re-enable
auto const candidates =
findAllCandidates(unlNodeIDs, negUnlNodeIDs, *scoreTable);
// Pick one to disable and one to re-enable if any, add ttUNL_MODIFY Tx
if (!candidates.toDisableCandidates.empty())
{
auto n =
choose(prevLedger->info().hash, candidates.toDisableCandidates);
assert(nidToKeyMap.count(n));
addTx(seq, nidToKeyMap[n], ToDisable, initialSet);
}
if (!candidates.toReEnableCandidates.empty())
{
auto n = choose(
prevLedger->info().hash, candidates.toReEnableCandidates);
assert(nidToKeyMap.count(n));
addTx(seq, nidToKeyMap[n], ToReEnable, initialSet);
}
// do reporting when enabled
if (prevLedger->rules().enabled(featureXahauGenesis) &&
scoreTable->size() > 0)
{
addReportingTx(seq, *scoreTable, nidToKeyMap, initialSet);
addImportVLTx(seq, initialSet);
}
}
}
void
NegativeUNLVote::addReportingTx(
LedgerIndex seq,
hash_map<NodeID, std::uint32_t> const& scoreTable,
hash_map<NodeID, PublicKey> const& nidToKeyMap,
std::shared_ptr<SHAMap> const& initalSet)
{
// RH NOTE: now that we use one key per txn with lots of txns
// this ordering step is probably not needed
std::set<PublicKey> ordered;
for (auto const& [n, score] : scoreTable)
{
if (score > (FLAG_LEDGER_INTERVAL >> 1))
ordered.emplace(nidToKeyMap.at(n));
}
for (auto const& pk : ordered)
{
STTx repUnlTx(ttUNL_REPORT, [&](auto& obj) {
obj.set(([&]() {
auto inner = std::make_unique<STObject>(sfActiveValidator);
inner->setFieldVL(sfPublicKey, pk);
return inner;
})());
obj.setFieldU32(sfLedgerSequence, seq);
});
uint256 txID = repUnlTx.getTransactionID();
Serializer s;
repUnlTx.add(s);
if (!initalSet->addGiveItem(
SHAMapNodeType::tnTRANSACTION_NM,
std::make_shared<SHAMapItem>(txID, s.slice())))
{
JLOG(j_.warn()) << "R-UNL: ledger seq=" << seq
<< ", add ttUNL_REPORT tx failed";
}
else
{
JLOG(j_.debug())
<< "R-UNL: ledger seq=" << seq
<< ", add a ttUNL_REPORT (active_val) Tx with txID: " << txID
<< ", size=" << s.size() << ", "
<< repUnlTx.getJson(JsonOptions::none);
}
}
}
std::vector<STTx>
NegativeUNLVote::generateImportVLVoteTx(
std::map<std::string, PublicKey> const& importVLKeys,
LedgerIndex seq)
{
std::vector<STTx> out;
for (auto const& [_, pk] : importVLKeys)
{
STTx repUnlTx(ttUNL_REPORT, [pk = pk, seq](auto& obj) {
obj.set(([&]() {
auto inner = std::make_unique<STObject>(sfImportVLKey);
inner->setFieldVL(sfPublicKey, pk);
return inner;
})());
obj.setFieldU32(sfLedgerSequence, seq);
});
out.push_back(std::move(repUnlTx));
}
return out;
}
void
NegativeUNLVote::addImportVLTx(
LedgerIndex seq,
std::shared_ptr<SHAMap> const& initalSet)
{
// do import VL key voting
std::vector<STTx> toInject =
generateImportVLVoteTx(app_.config().IMPORT_VL_KEYS, seq);
for (auto const& repUnlTx : toInject)
{
uint256 txID = repUnlTx.getTransactionID();
Serializer s;
repUnlTx.add(s);
if (!initalSet->addGiveItem(
SHAMapNodeType::tnTRANSACTION_NM,
std::make_shared<SHAMapItem>(txID, s.slice())))
{
JLOG(j_.warn()) << "R-UNL: ledger seq=" << seq
<< ", add ttUNL_REPORT tx failed (import_vl_key)";
}
else
{
JLOG(j_.debug())
<< "R-UNL: ledger seq=" << seq
<< ", add a ttUNL_REPORT (import_vl) Tx with txID: " << txID
<< ", size=" << s.size() << ", "
<< repUnlTx.getJson(JsonOptions::none);
}
}
}
void
NegativeUNLVote::addTx(
LedgerIndex seq,
PublicKey const& vp,
NegativeUNLModify modify,
std::shared_ptr<SHAMap> const& initialSet)
{
STTx negUnlTx(ttUNL_MODIFY, [&](auto& obj) {
obj.setFieldU8(sfUNLModifyDisabling, modify == ToDisable ? 1 : 0);
obj.setFieldU32(sfLedgerSequence, seq);
obj.setFieldVL(sfUNLModifyValidator, vp.slice());
});
uint256 txID = negUnlTx.getTransactionID();
Serializer s;
negUnlTx.add(s);
if (!initialSet->addGiveItem(
SHAMapNodeType::tnTRANSACTION_NM,
std::make_shared<SHAMapItem>(txID, s.slice())))
{
JLOG(j_.warn()) << "N-UNL: ledger seq=" << seq
<< ", add ttUNL_MODIFY tx failed";
}
else
{
JLOG(j_.debug()) << "N-UNL: ledger seq=" << seq
<< ", add a ttUNL_MODIFY Tx with txID: " << txID
<< ", the validator to "
<< (modify == ToDisable ? "disable: " : "re-enable: ")
<< vp;
}
}
NodeID
NegativeUNLVote::choose(
uint256 const& randomPadData,
std::vector<NodeID> const& candidates)
{
assert(!candidates.empty());
static_assert(NodeID::bytes <= uint256::bytes);
NodeID randomPad = NodeID::fromVoid(randomPadData.data());
NodeID txNodeID = candidates[0];
for (int j = 1; j < candidates.size(); ++j)
{
if ((candidates[j] ^ randomPad) < (txNodeID ^ randomPad))
{
txNodeID = candidates[j];
}
}
return txNodeID;
}
std::optional<hash_map<NodeID, std::uint32_t>>
NegativeUNLVote::buildScoreTable(
std::shared_ptr<Ledger const> const& prevLedger,
hash_set<NodeID> const& unl,
RCLValidations& validations)
{
// Find agreed validation messages received for
// the last FLAG_LEDGER_INTERVAL (i.e. 256) ledgers,
// for every validator, and fill the score table.
// Ask the validation container to keep enough validation message history
// for next time.
auto const seq = prevLedger->info().seq + 1;
validations.setSeqToKeep(seq - 1, seq + FLAG_LEDGER_INTERVAL);
// Find FLAG_LEDGER_INTERVAL (i.e. 256) previous ledger hashes
auto const hashIndex = prevLedger->read(keylet::skip());
if (!hashIndex || !hashIndex->isFieldPresent(sfHashes))
{
JLOG(j_.debug()) << "N-UNL: ledger " << seq << " no history.";
return {};
}
auto const ledgerAncestors = hashIndex->getFieldV256(sfHashes).value();
auto const numAncestors = ledgerAncestors.size();
if (numAncestors < FLAG_LEDGER_INTERVAL)
{
JLOG(j_.debug()) << "N-UNL: ledger " << seq
<< " not enough history. Can trace back only "
<< numAncestors << " ledgers.";
return {};
}
// have enough ledger ancestors, build the score table
hash_map<NodeID, std::uint32_t> scoreTable;
for (auto const& k : unl)
{
scoreTable[k] = 0;
}
// Query the validation container for every ledger hash and fill
// the score table.
for (int i = 0; i < FLAG_LEDGER_INTERVAL; ++i)
{
for (auto const& v : validations.getTrustedForLedger(
ledgerAncestors[numAncestors - 1 - i], seq - 2 - i))
{
if (scoreTable.count(v->getNodeID()))
++scoreTable[v->getNodeID()];
}
}
// Return false if the validation message history or local node's
// participation in the history is not good.
auto const myValidationCount = [&]() -> std::uint32_t {
if (auto const it = scoreTable.find(myId_); it != scoreTable.end())
return it->second;
return 0;
}();
if (myValidationCount < negativeUNLMinLocalValsToVote)
{
JLOG(j_.debug()) << "N-UNL: ledger " << seq
<< ". Local node only issued " << myValidationCount
<< " validations in last " << FLAG_LEDGER_INTERVAL
<< " ledgers."
<< " The reliability measurement could be wrong.";
return {};
}
else if (
myValidationCount > negativeUNLMinLocalValsToVote &&
myValidationCount <= FLAG_LEDGER_INTERVAL)
{
return scoreTable;
}
else
{
// cannot happen because validations.getTrustedForLedger does not
// return multiple validations of the same ledger from a validator.
JLOG(j_.error()) << "N-UNL: ledger " << seq << ". Local node issued "
<< myValidationCount << " validations in last "
<< FLAG_LEDGER_INTERVAL << " ledgers. Too many!";
return {};
}
}
NegativeUNLVote::Candidates const
NegativeUNLVote::findAllCandidates(
hash_set<NodeID> const& unl,
hash_set<NodeID> const& negUnl,
hash_map<NodeID, std::uint32_t> const& scoreTable)
{
// Compute if need to find more validators to disable
auto const canAdd = [&]() -> bool {
auto const maxNegativeListed = static_cast<std::size_t>(
std::ceil(unl.size() * negativeUNLMaxListed));
std::size_t negativeListed = 0;
for (auto const& n : unl)
{
if (negUnl.count(n))
++negativeListed;
}
bool const result = negativeListed < maxNegativeListed;
JLOG(j_.trace()) << "N-UNL: nodeId " << myId_ << " lowWaterMark "
<< negativeUNLLowWaterMark << " highWaterMark "
<< negativeUNLHighWaterMark << " canAdd " << result
<< " negativeListed " << negativeListed
<< " maxNegativeListed " << maxNegativeListed;
return result;
}();
Candidates candidates;
for (auto const& [nodeId, score] : scoreTable)
{
JLOG(j_.trace()) << "N-UNL: node " << nodeId << " score " << score;
// Find toDisable Candidates: check if
// (1) canAdd,
// (2) has less than negativeUNLLowWaterMark validations,
// (3) is not in negUnl, and
// (4) is not a new validator.
if (canAdd && score < negativeUNLLowWaterMark &&
!negUnl.count(nodeId) && !newValidators_.count(nodeId))
{
JLOG(j_.trace()) << "N-UNL: toDisable candidate " << nodeId;
candidates.toDisableCandidates.push_back(nodeId);
}
// Find toReEnable Candidates: check if
// (1) has more than negativeUNLHighWaterMark validations,
// (2) is in negUnl
if (score > negativeUNLHighWaterMark && negUnl.count(nodeId))
{
JLOG(j_.trace()) << "N-UNL: toReEnable candidate " << nodeId;
candidates.toReEnableCandidates.push_back(nodeId);
}
}
// If a negative UNL validator is removed from nodes' UNLs, it is no longer
// a validator. It should be removed from the negative UNL too.
// Note that even if it is still offline and in minority nodes' UNLs, it
// will not be re-added to the negative UNL. Because the UNLModify Tx will
// not be included in the agreed TxSet of a ledger.
//
// Find this kind of toReEnable Candidate if did not find any toReEnable
// candidate yet: check if
// (1) is in negUnl
// (2) is not in unl.
if (candidates.toReEnableCandidates.empty())
{
for (auto const& n : negUnl)
{
if (!unl.count(n))
{
candidates.toReEnableCandidates.push_back(n);
}
}
}
return candidates;
}
void
NegativeUNLVote::newValidators(
LedgerIndex seq,
hash_set<NodeID> const& nowTrusted)
{
std::lock_guard lock(mutex_);
for (auto const& n : nowTrusted)
{
if (newValidators_.find(n) == newValidators_.end())
{
JLOG(j_.trace()) << "N-UNL: add a new validator " << n
<< " at ledger seq=" << seq;
newValidators_[n] = seq;
}
}
}
void
NegativeUNLVote::purgeNewValidators(LedgerIndex seq)
{
std::lock_guard lock(mutex_);
auto i = newValidators_.begin();
while (i != newValidators_.end())
{
if (seq - i->second > newValidatorDisableSkip)
{
i = newValidators_.erase(i);
}
else
{
++i;
}
}
}
} // namespace ripple