Skip to content

Commit e6b343d

Browse files
sipasipa
committed
Make addrman's bucket placement deterministic.
Give each address a single fixed location in the new and tried tables, which become simple fixed-size arrays instead of sets and vectors. This prevents attackers from having an advantages by inserting an address multiple times. This change was suggested as Countermeasure 1 in Eclipse Attacks on Bitcoin’s Peer-to-Peer Network, Ethan Heilman, Alison Kendler, Aviv Zohar, Sharon Goldberg. ePrint Archive Report 2015/263. March 2015. It is also more efficient.
1 parent b23add5 commit e6b343d

File tree

2 files changed

+231
-206
lines changed

2 files changed

+231
-206
lines changed

‎src/addrman.cpp‎

Lines changed: 124 additions & 146 deletions
Original file line numberDiff line numberDiff line change
@@ -14,12 +14,12 @@ int CAddrInfo::GetTriedBucket(const uint256& nKey) const
1414
{
1515
CDataStream ss1(SER_GETHASH, 0);
1616
std::vector<unsigned char> vchKey = GetKey();
17-
ss1 << ((unsigned char)32) << nKey << vchKey;
17+
ss1 << nKey << vchKey;
1818
uint64_t hash1 = Hash(ss1.begin(), ss1.end()).GetCheapHash();
1919

2020
CDataStream ss2(SER_GETHASH, 0);
2121
std::vector<unsigned char> vchGroupKey = GetGroup();
22-
ss2 << ((unsigned char)32) << nKey << vchGroupKey << (hash1 % ADDRMAN_TRIED_BUCKETS_PER_GROUP);
22+
ss2 << nKey << vchGroupKey << (hash1 % ADDRMAN_TRIED_BUCKETS_PER_GROUP);
2323
uint64_t hash2 = Hash(ss2.begin(), ss2.end()).GetCheapHash();
2424
return hash2 % ADDRMAN_TRIED_BUCKET_COUNT;
2525
}
@@ -29,15 +29,24 @@ int CAddrInfo::GetNewBucket(const uint256& nKey, const CNetAddr& src) const
2929
CDataStream ss1(SER_GETHASH, 0);
3030
std::vector<unsigned char> vchGroupKey = GetGroup();
3131
std::vector<unsigned char> vchSourceGroupKey = src.GetGroup();
32-
ss1 << ((unsigned char)32) << nKey << vchGroupKey << vchSourceGroupKey;
32+
ss1 << nKey << vchGroupKey << vchSourceGroupKey;
3333
uint64_t hash1 = Hash(ss1.begin(), ss1.end()).GetCheapHash();
3434

3535
CDataStream ss2(SER_GETHASH, 0);
36-
ss2 << ((unsigned char)32) << nKey << vchSourceGroupKey << (hash1 % ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP);
36+
ss2 << nKey << vchSourceGroupKey << (hash1 % ADDRMAN_NEW_BUCKETS_PER_SOURCE_GROUP);
3737
uint64_t hash2 = Hash(ss2.begin(), ss2.end()).GetCheapHash();
3838
return hash2 % ADDRMAN_NEW_BUCKET_COUNT;
3939
}
4040

41+
int CAddrInfo::GetBucketPosition(const uint256 &nKey, bool fNew, int nBucket) const
42+
{
43+
CDataStream ss1(SER_GETHASH, 0);
44+
std::vector<unsigned char> vchKey = GetKey();
45+
ss1 << nKey << (fNew ? 'N' : 'K') << nBucket << vchKey;
46+
uint64_t hash1 = Hash(ss1.begin(), ss1.end()).GetCheapHash();
47+
return hash1 % ADDRMAN_BUCKET_SIZE;
48+
}
49+
4150
bool CAddrInfo::IsTerrible(int64_t nNow) const
4251
{
4352
if (nLastTry && nLastTry >= nNow - 60) // never remove things tried in the last minute
@@ -128,130 +137,81 @@ void CAddrMan::SwapRandom(unsigned int nRndPos1, unsigned int nRndPos2)
128137
vRandom[nRndPos2] = nId1;
129138
}
130139

131-
int CAddrMan::SelectTried(int nKBucket)
140+
void CAddrMan::Delete(int nId)
132141
{
133-
std::vector<int>& vTried = vvTried[nKBucket];
134-
135-
// randomly shuffle the first few elements (using the entire list)
136-
// find the least recently tried among them
137-
int64_t nOldest = -1;
138-
int nOldestPos = -1;
139-
for (unsigned int i = 0; i < ADDRMAN_TRIED_ENTRIES_INSPECT_ON_EVICT && i < vTried.size(); i++) {
140-
int nPos = GetRandInt(vTried.size() - i) + i;
141-
int nTemp = vTried[nPos];
142-
vTried[nPos] = vTried[i];
143-
vTried[i] = nTemp;
144-
assert(nOldest == -1 || mapInfo.count(nTemp) == 1);
145-
if (nOldest == -1 || mapInfo[nTemp].nLastSuccess < mapInfo[nOldest].nLastSuccess) {
146-
nOldest = nTemp;
147-
nOldestPos = nPos;
148-
}
149-
}
142+
assert(mapInfo.count(nId) != 0);
143+
CAddrInfo& info = mapInfo[nId];
144+
assert(!info.fInTried);
145+
assert(info.nRefCount == 0);
150146

151-
return nOldestPos;
147+
SwapRandom(info.nRandomPos, vRandom.size() - 1);
148+
vRandom.pop_back();
149+
mapAddr.erase(info);
150+
mapInfo.erase(nId);
151+
nNew--;
152152
}
153153

154-
int CAddrMan::ShrinkNew(int nUBucket)
154+
void CAddrMan::ClearNew(int nUBucket, int nUBucketPos)
155155
{
156-
assert(nUBucket >= 0 && (unsigned int)nUBucket < vvNew.size());
157-
std::set<int>& vNew = vvNew[nUBucket];
158-
159-
// first look for deletable items
160-
for (std::set<int>::iterator it = vNew.begin(); it != vNew.end(); it++) {
161-
assert(mapInfo.count(*it));
162-
CAddrInfo& info = mapInfo[*it];
163-
if (info.IsTerrible()) {
164-
if (--info.nRefCount == 0) {
165-
SwapRandom(info.nRandomPos, vRandom.size() - 1);
166-
vRandom.pop_back();
167-
mapAddr.erase(info);
168-
mapInfo.erase(*it);
169-
nNew--;
170-
}
171-
vNew.erase(it);
172-
return 0;
173-
}
174-
}
175-
176-
// otherwise, select four randomly, and pick the oldest of those to replace
177-
int n[4] = {GetRandInt(vNew.size()), GetRandInt(vNew.size()), GetRandInt(vNew.size()), GetRandInt(vNew.size())};
178-
int nI = 0;
179-
int nOldest = -1;
180-
for (std::set<int>::iterator it = vNew.begin(); it != vNew.end(); it++) {
181-
if (nI == n[0] || nI == n[1] || nI == n[2] || nI == n[3]) {
182-
assert(nOldest == -1 || mapInfo.count(*it) == 1);
183-
if (nOldest == -1 || mapInfo[*it].nTime < mapInfo[nOldest].nTime)
184-
nOldest = *it;
156+
// if there is an entry in the specified bucket, delete it.
157+
if (vvNew[nUBucket][nUBucketPos] != -1) {
158+
int nIdDelete = vvNew[nUBucket][nUBucketPos];
159+
CAddrInfo& infoDelete = mapInfo[nIdDelete];
160+
assert(infoDelete.nRefCount > 0);
161+
infoDelete.nRefCount--;
162+
vvNew[nUBucket][nUBucketPos] = -1;
163+
if (infoDelete.nRefCount == 0) {
164+
Delete(nIdDelete);
185165
}
186-
nI++;
187-
}
188-
assert(mapInfo.count(nOldest) == 1);
189-
CAddrInfo& info = mapInfo[nOldest];
190-
if (--info.nRefCount == 0) {
191-
SwapRandom(info.nRandomPos, vRandom.size() - 1);
192-
vRandom.pop_back();
193-
mapAddr.erase(info);
194-
mapInfo.erase(nOldest);
195-
nNew--;
196166
}
197-
vNew.erase(nOldest);
198-
199-
return 1;
200167
}
201168

202-
void CAddrMan::MakeTried(CAddrInfo& info, int nId, int nOrigin)
169+
void CAddrMan::MakeTried(CAddrInfo& info, int nId)
203170
{
204-
assert(vvNew[nOrigin].count(nId) == 1);
205-
206171
// remove the entry from all new buckets
207-
for (std::vector<std::set<int> >::iterator it = vvNew.begin(); it != vvNew.end(); it++) {
208-
if ((*it).erase(nId))
172+
for (int bucket = 0; bucket < ADDRMAN_NEW_BUCKET_COUNT; bucket++) {
173+
int pos = info.GetBucketPosition(nKey, true, bucket);
174+
if (vvNew[bucket][pos] == nId) {
175+
vvNew[bucket][pos] = -1;
209176
info.nRefCount--;
177+
}
210178
}
211179
nNew--;
212180

213181
assert(info.nRefCount == 0);
214182

215183
// which tried bucket to move the entry to
216184
int nKBucket = info.GetTriedBucket(nKey);
217-
std::vector<int>& vTried = vvTried[nKBucket];
218-
219-
// first check whether there is place to just add it
220-
if (vTried.size() < ADDRMAN_TRIED_BUCKET_SIZE) {
221-
vTried.push_back(nId);
222-
nTried++;
223-
info.fInTried = true;
224-
return;
225-
}
226-
227-
// otherwise, find an item to evict
228-
int nPos = SelectTried(nKBucket);
229-
230-
// find which new bucket it belongs to
231-
assert(mapInfo.count(vTried[nPos]) == 1);
232-
int nUBucket = mapInfo[vTried[nPos]].GetNewBucket(nKey);
233-
std::set<int>& vNew = vvNew[nUBucket];
234-
235-
// remove the to-be-replaced tried entry from the tried set
236-
CAddrInfo& infoOld = mapInfo[vTried[nPos]];
237-
infoOld.fInTried = false;
238-
infoOld.nRefCount = 1;
239-
// do not update nTried, as we are going to move something else there immediately
240-
241-
// check whether there is place in that one,
242-
if (vNew.size() < ADDRMAN_NEW_BUCKET_SIZE) {
243-
// if so, move it back there
244-
vNew.insert(vTried[nPos]);
245-
} else {
246-
// otherwise, move it to the new bucket nId came from (there is certainly place there)
247-
vvNew[nOrigin].insert(vTried[nPos]);
185+
int nKBucketPos = info.GetBucketPosition(nKey, false, nKBucket);
186+
187+
// first make space to add it (the existing tried entry there is moved to new, deleting whatever is there).
188+
if (vvTried[nKBucket][nKBucketPos] != -1) {
189+
// find an item to evict
190+
int nIdEvict = vvTried[nKBucket][nKBucketPos];
191+
assert(mapInfo.count(nIdEvict) == 1);
192+
CAddrInfo& infoOld = mapInfo[nIdEvict];
193+
194+
// Remove the to-be-evicted item from the tried set.
195+
infoOld.fInTried = false;
196+
vvTried[nKBucket][nKBucketPos] = -1;
197+
nTried--;
198+
199+
// find which new bucket it belongs to
200+
int nUBucket = infoOld.GetNewBucket(nKey);
201+
int nUBucketPos = infoOld.GetBucketPosition(nKey, true, nUBucket);
202+
ClearNew(nUBucket, nUBucketPos);
203+
assert(vvNew[nUBucket][nUBucketPos] == -1);
204+
205+
// Enter it into the new set again.
206+
infoOld.nRefCount = 1;
207+
vvNew[nUBucket][nUBucketPos] = nIdEvict;
208+
nNew++;
248209
}
249-
nNew++;
210+
assert(vvTried[nKBucket][nKBucketPos] == -1);
250211

251-
vTried[nPos] = nId;
252-
// we just overwrote an entry in vTried; no need to update nTried
212+
vvTried[nKBucket][nKBucketPos] = nId;
213+
nTried++;
253214
info.fInTried = true;
254-
return;
255215
}
256216

257217
void CAddrMan::Good_(const CService& addr, int64_t nTime)
@@ -281,12 +241,12 @@ void CAddrMan::Good_(const CService& addr, int64_t nTime)
281241
return;
282242

283243
// find a bucket it is in now
284-
int nRnd = GetRandInt(vvNew.size());
244+
int nRnd = GetRandInt(ADDRMAN_NEW_BUCKET_COUNT);
285245
int nUBucket = -1;
286-
for (unsigned int n = 0; n < vvNew.size(); n++) {
287-
int nB = (n + nRnd) % vvNew.size();
288-
std::set<int>& vNew = vvNew[nB];
289-
if (vNew.count(nId)) {
246+
for (unsigned int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) {
247+
int nB = (n + nRnd) % ADDRMAN_NEW_BUCKET_COUNT;
248+
int nBpos = info.GetBucketPosition(nKey, true, nB);
249+
if (vvNew[nB][nBpos] == nId) {
290250
nUBucket = nB;
291251
break;
292252
}
@@ -300,7 +260,7 @@ void CAddrMan::Good_(const CService& addr, int64_t nTime)
300260
LogPrint("addrman", "Moving %s to tried\n", addr.ToString());
301261

302262
// move nId to the tried tables
303-
MakeTried(info, nId, nUBucket);
263+
MakeTried(info, nId);
304264
}
305265

306266
bool CAddrMan::Add_(const CAddress& addr, const CNetAddr& source, int64_t nTimePenalty)
@@ -348,12 +308,25 @@ bool CAddrMan::Add_(const CAddress& addr, const CNetAddr& source, int64_t nTimeP
348308
}
349309

350310
int nUBucket = pinfo->GetNewBucket(nKey, source);
351-
std::set<int>& vNew = vvNew[nUBucket];
352-
if (!vNew.count(nId)) {
353-
pinfo->nRefCount++;
354-
if (vNew.size() == ADDRMAN_NEW_BUCKET_SIZE)
355-
ShrinkNew(nUBucket);
356-
vvNew[nUBucket].insert(nId);
311+
int nUBucketPos = pinfo->GetBucketPosition(nKey, true, nUBucket);
312+
if (vvNew[nUBucket][nUBucketPos] != nId) {
313+
bool fInsert = vvNew[nUBucket][nUBucketPos] == -1;
314+
if (!fInsert) {
315+
CAddrInfo& infoExisting = mapInfo[vvNew[nUBucket][nUBucketPos]];
316+
if (infoExisting.IsTerrible() || (infoExisting.nRefCount > 1 && pinfo->nRefCount == 0)) {
317+
// Overwrite the existing new table entry.
318+
fInsert = true;
319+
}
320+
}
321+
if (fInsert) {
322+
ClearNew(nUBucket, nUBucketPos);
323+
pinfo->nRefCount++;
324+
vvNew[nUBucket][nUBucketPos] = nId;
325+
} else {
326+
if (pinfo->nRefCount == 0) {
327+
Delete(nId);
328+
}
329+
}
357330
}
358331
return fNew;
359332
}
@@ -388,13 +361,13 @@ CAddress CAddrMan::Select_(int nUnkBias)
388361
// use a tried node
389362
double fChanceFactor = 1.0;
390363
while (1) {
391-
int nKBucket = GetRandInt(vvTried.size());
392-
std::vector<int>& vTried = vvTried[nKBucket];
393-
if (vTried.size() == 0)
364+
int nKBucket = GetRandInt(ADDRMAN_TRIED_BUCKET_COUNT);
365+
int nKBucketPos = GetRandInt(ADDRMAN_BUCKET_SIZE);
366+
if (vvTried[nKBucket][nKBucketPos] == -1)
394367
continue;
395-
int nPos = GetRandInt(vTried.size());
396-
assert(mapInfo.count(vTried[nPos]) == 1);
397-
CAddrInfo& info = mapInfo[vTried[nPos]];
368+
int nId = vvTried[nKBucket][nKBucketPos];
369+
assert(mapInfo.count(nId) == 1);
370+
CAddrInfo& info = mapInfo[nId];
398371
if (GetRandInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30))
399372
return info;
400373
fChanceFactor *= 1.2;
@@ -403,16 +376,13 @@ CAddress CAddrMan::Select_(int nUnkBias)
403376
// use a new node
404377
double fChanceFactor = 1.0;
405378
while (1) {
406-
int nUBucket = GetRandInt(vvNew.size());
407-
std::set<int>& vNew = vvNew[nUBucket];
408-
if (vNew.size() == 0)
379+
int nUBucket = GetRandInt(ADDRMAN_NEW_BUCKET_COUNT);
380+
int nUBucketPos = GetRandInt(ADDRMAN_BUCKET_SIZE);
381+
if (vvNew[nUBucket][nUBucketPos] == -1)
409382
continue;
410-
int nPos = GetRandInt(vNew.size());
411-
std::set<int>::iterator it = vNew.begin();
412-
while (nPos--)
413-
it++;
414-
assert(mapInfo.count(*it) == 1);
415-
CAddrInfo& info = mapInfo[*it];
383+
int nId = vvNew[nUBucket][nUBucketPos];
384+
assert(mapInfo.count(nId) == 1);
385+
CAddrInfo& info = mapInfo[nId];
416386
if (GetRandInt(1 << 30) < fChanceFactor * info.GetChance() * (1 << 30))
417387
return info;
418388
fChanceFactor *= 1.2;
@@ -460,22 +430,30 @@ int CAddrMan::Check_()
460430
if (mapNew.size() != nNew)
461431
return -10;
462432

463-
for (int n = 0; n < vvTried.size(); n++) {
464-
std::vector<int>& vTried = vvTried[n];
465-
for (std::vector<int>::iterator it = vTried.begin(); it != vTried.end(); it++) {
466-
if (!setTried.count(*it))
467-
return -11;
468-
setTried.erase(*it);
433+
for (int n = 0; n < ADDRMAN_TRIED_BUCKET_COUNT; n++) {
434+
for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
435+
if (vvTried[n][i] != -1) {
436+
if (!setTried.count(vvTried[n][i]))
437+
return -11;
438+
if (mapInfo[vvTried[n][i]].GetTriedBucket(nKey) != n)
439+
return -17;
440+
if (mapInfo[vvTried[n][i]].GetBucketPosition(nKey, false, n) != i)
441+
return -18;
442+
setTried.erase(vvTried[n][i]);
443+
}
469444
}
470445
}
471446

472-
for (int n = 0; n < vvNew.size(); n++) {
473-
std::set<int>& vNew = vvNew[n];
474-
for (std::set<int>::iterator it = vNew.begin(); it != vNew.end(); it++) {
475-
if (!mapNew.count(*it))
476-
return -12;
477-
if (--mapNew[*it] == 0)
478-
mapNew.erase(*it);
447+
for (int n = 0; n < ADDRMAN_NEW_BUCKET_COUNT; n++) {
448+
for (int i = 0; i < ADDRMAN_BUCKET_SIZE; i++) {
449+
if (vvNew[n][i] != -1) {
450+
if (!mapNew.count(vvNew[n][i]))
451+
return -12;
452+
if (mapInfo[vvNew[n][i]].GetBucketPosition(nKey, true, n) != i)
453+
return -19;
454+
if (--mapNew[vvNew[n][i]] == 0)
455+
mapNew.erase(vvNew[n][i]);
456+
}
479457
}
480458
}
481459

0 commit comments

Comments
 (0)