MatthewLM (OP)
Legendary
Offline
Activity: 1190
Merit: 1004
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 01, 2012, 09:59:34 PM |
|
I've been looking at the addrman.cpp code. From what I've read elsewhere it is supposed to place groups of IPs in separate buckets and connect to IPs from a selection of buckets with some randomisation.
The problem is, it's hard getting my head around the code. Can anyone explain what the code is doing? I can see by the GetGroup function how it separates addresses though the rest of the code is quite complex.
Would it be adequate for my library to separate addresses much as the GetGroup function and initiate connections from random different groups with bias to "newer"/"better" addresses?
It seems to me that the addrman.cpp code adds groups in a random bucket and some groups may be put into the same bucket. Why would different groups be put into the same bucket?
And can anyone explain why there is the "new" buckets and "tried" buckets?
The whole thing seems overcomplex to me but if anyone can explain simply what it is doing and why the things are useful, then I'll take it on board.
Thank you.
|
|
|
|
terrytibbs
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 01, 2012, 10:01:10 PM |
|
I think addrman is sipa's branchild; check on IRC if you're low on time or he misses this.
|
|
|
|
MatthewLM (OP)
Legendary
Offline
Activity: 1190
Merit: 1004
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 01, 2012, 10:12:05 PM |
|
OK thanks, though I'm just about done for today I think. I'll come back to this tomorrow.
|
|
|
|
gmaxwell
Moderator
Legendary
Offline
Activity: 4242
Merit: 8647
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 02, 2012, 12:00:06 AM |
|
There is a very long and detailed 'comment' in the code that documents the design and much of the rationale behind it.
Everything it does it does in order to bound the maximum store for addresses (so an attacker can't flood you to run you out of disk), while preserving the most useful addresses, and while making it difficult for an attacker to replace all your addresses with nodes he controls.
|
|
|
|
Pieter Wuille
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 02, 2012, 12:06:30 PM |
|
The comments Gregory is referring to are here: https://github.com/bitcoin/bitcoin/blob/master/src/addrman.h#L91. The "new" buckets are for addresses to which no succesful connections has been made yet, the "tried" ones for addresses that are. The idea is that you want both, so that there is always a chance for connecting to an old and known functional node, but still always keep trying new ones as well. For "new" buckets, the bucket is derived from the origin of the node's knowledge (where you heard it from), so that an attacker needs many distincts IP ranges to poison your entire table. For the "tried" bcukets, the bucket number is based on the address itself, for the same reason. Over-complex? Maybe...
|
I do Bitcoin stuff.
|
|
|
MatthewLM (OP)
Legendary
Offline
Activity: 1190
Merit: 1004
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 02, 2012, 02:22:13 PM |
|
Ok thanks. I do understand what it is trying to do and I pretty understand why it does the different things.
The way I thought about doing it was to place addresses into buckets (new or tried) using a more suitable CSPRNG rather than a double SHA-256 hash. Then addresses will be ordered by a score in each bucket so that a random selection can be made with a bias to addresses with a better score. When an address needs to be removed, a random address is removed with bias to addresses with a low score. The score will be set like with the original client, related to the time last seen but will be reduced when connections are unsuccessful.
|
|
|
|
Pieter Wuille
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 02, 2012, 03:46:35 PM |
|
Right, addrman is not primarily intended to optimize quick connections. Its first priority is preventing sybil attacks, and limited disk/memory usage.
|
I do Bitcoin stuff.
|
|
|
MatthewLM (OP)
Legendary
Offline
Activity: 1190
Merit: 1004
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 02, 2012, 09:15:23 PM Last edit: August 03, 2012, 02:19:09 AM by John (johnthedong) |
|
Well here is how I'm generating the bucket indexes (untested). uint8_t CBAddressManagerGetBucketIndex(CBAddressManager * self,CBNetworkAddress * addr){ uint64_t group = CBAddressManagerGetGroup(self, addr); CBRandomSeed(self->rndGen, group + self->secret); // Add the group with the secure secret generated during initialisation. return CBSecureRandomInteger(self->rndGen) % CB_BUCKET_NUM; } uint64_t CBAddressManagerGetGroup(CBAddressManager * self,CBNetworkAddress * addr){ uint8_t start = 0; int8_t bits = 16; uint64_t group; if (addr->type & CB_IP_I2P) { group = CB_IP_I2P; }else if (addr->type & CB_IP_TOR){ group = CB_IP_TOR; start = 6; bits = 4; }else if (addr->type & CB_IP_IPv6){ if ((addr->type & CB_IP_SITT) || (addr->type & CB_IP_RFC6052)) { group = CB_IP_IPv4; start = 12; }else if (addr->type & CB_IP_6TO4){ start = 2; group = CB_IP_IPv4; }else if (addr->type & CB_IP_TEREDO){ return CB_IP_IPv4 | ((CBByteArrayGetByte(addr->ip, 12) ^ 0xFF) << 8) | ((CBByteArrayGetByte(addr->ip, 13) ^ 0xFF) << 16); }else if (addr->type & CB_IP_HENET){ bits = 36; group = CB_IP_IPv6; }else{ bits = 32; group = CB_IP_IPv6; } }else if (addr->type & CB_IP_IPv4){ group = CB_IP_IPv4; start = 12; }else if (addr->type & CB_IP_IPv4_LOCAL){ group = CB_IP_IPv4; bits = 0; }else{ group = CB_IP_IPv6; bits = 0; } uint8_t x = 8; for (; bits >= 8; bits -= 8, x += 8, start++) group |= CBByteArrayGetByte(addr->ip, start) << x; if (bits > 0) group |= (CBByteArrayGetByte(addr->ip, start) | ((1 << bits) - 1)) << x; return group; } bool CBAddressManagerSetup(CBAddressManager * self){ // ... Other stuff here ... self->rndGen = CBNewSecureRandomGenerator(); if (!self->rndGen) { // ... return false; } CBSecureRandomSeed(self->rndGen); // Cryptographically secure for the secret. self->secret = CBSecureRandomInteger(self->rndGen); }
|
|
|
|
jgarzik
Legendary
Offline
Activity: 1596
Merit: 1099
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 02, 2012, 11:10:38 PM |
|
Use a 'switch' statement rather than a super-long if tree ![Smiley](https://bitcointalk.org/Smileys/default/smiley.gif)
|
Jeff Garzik, Bloq CEO, former bitcoin core dev team; opinions are my own. Visit bloq.com / metronome.io Donations / tip jar: 1BrufViLKnSWtuWGkryPsKsxonV2NQ7Tcj
|
|
|
John (John K.)
Global Troll-buster and
Legendary
Offline
Activity: 1288
Merit: 1227
Away on an extended break
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 03, 2012, 02:20:57 AM |
|
Well here is how I'm generating the bucket indexes (untested). uint8_t CBAddressManagerGetBucketIndex(CBAddressManager * self,CBNetworkAddress * addr){ uint64_t group = CBAddressManagerGetGroup(self, addr); CBRandomSeed(self->rndGen, group + self->secret); // Add the group with the secure secret generated during initialisation. return CBSecureRandomInteger(self->rndGen) % CB_BUCKET_NUM; } uint64_t CBAddressManagerGetGroup(CBAddressManager * self,CBNetworkAddress * addr){ uint8_t start = 0; int8_t bits = 16; uint64_t group; if (addr->type & CB_IP_I2P) { group = CB_IP_I2P; }else if (addr->type & CB_IP_TOR){ group = CB_IP_TOR; start = 6; bits = 4; }else if (addr->type & CB_IP_IPv6){ if ((addr->type & CB_IP_SITT) || (addr->type & CB_IP_RFC6052)) { group = CB_IP_IPv4; start = 12; }else if (addr->type & CB_IP_6TO4){ start = 2; group = CB_IP_IPv4; }else if (addr->type & CB_IP_TEREDO){ return CB_IP_IPv4 | ((CBByteArrayGetByte(addr->ip, 12) ^ 0xFF) << 8) | ((CBByteArrayGetByte(addr->ip, 13) ^ 0xFF) << 16); }else if (addr->type & CB_IP_HENET){ bits = 36; group = CB_IP_IPv6; }else{ bits = 32; group = CB_IP_IPv6; } }else if (addr->type & CB_IP_IPv4){ group = CB_IP_IPv4; start = 12; }else if (addr->type & CB_IP_IPv4_LOCAL){ group = CB_IP_IPv4; bits = 0; }else{ group = CB_IP_IPv6; bits = 0; } uint8_t x = 8; for (; bits >= 8; bits -= 8, x += 8, start++) group |= CBByteArrayGetByte(addr->ip, start) << x; if (bits > 0) group |= (CBByteArrayGetByte(addr->ip, start) | ((1 << bits) - 1)) << x; return group; } bool CBAddressManagerSetup(CBAddressManager * self){ // ... Other stuff here ... self->rndGen = CBNewSecureRandomGenerator(); if (!self->rndGen) { // ... return false; } CBSecureRandomSeed(self->rndGen); // Cryptographically secure for the secret. self->secret = CBSecureRandomInteger(self->rndGen); } I've taken the rare chance to edit an post above ![Wink](https://bitcointalk.org/Smileys/default/wink.gif) You need to use code tags instead of the quote tags to prevent triggering the smilies.
|
|
|
|
MatthewLM (OP)
Legendary
Offline
Activity: 1190
Merit: 1004
|
![](https://bitcointalk.org/Themes/custom1/images/post/xx.gif) |
August 03, 2012, 02:41:24 PM |
|
Sorry, I hit the wrong tag by mistake. Here is the code with a switch statement and a new function: "CBAddressManagerTakeAddress" uint8_t CBAddressManagerGetBucketIndex(CBAddressManager * self,CBNetworkAddress * addr){ uint64_t group = CBAddressManagerGetGroup(self, addr); CBRandomSeed(self->rndGenForBucketIndexes, group + self->secret); // Add the group with the secure secret generated during initialisation. return CBSecureRandomInteger(self->rndGenForBucketIndexes) % CB_BUCKET_NUM; } uint64_t CBAddressManagerGetGroup(CBAddressManager * self,CBNetworkAddress * addr){ uint8_t start = 0; int8_t bits = 16; uint64_t group; switch (addr->type) { case CB_IP_I2P: case CB_IP_TOR: group = addr->type; start = 6; bits = 4; break; case CB_IP_SITT: case CB_IP_RFC6052: group = CB_IP_IPv4; start = 12; break; case CB_IP_6TO4: group = CB_IP_IPv4; start = 2; break; case CB_IP_TEREDO: return CB_IP_IPv4 | ((CBByteArrayGetByte(addr->ip, 12) ^ 0xFF) << 8) | ((CBByteArrayGetByte(addr->ip, 13) ^ 0xFF) << 16); case CB_IP_HENET: group = CB_IP_IPv6; bits = 36; break; case CB_IP_IPv6: group = CB_IP_IPv6; bits = 32; break; case CB_IP_IPv4: group = CB_IP_IPv4; start = 12; break; default: group = addr->type; bits = 0; break; } uint8_t x = 8; for (; bits >= 8; bits -= 8, x += 8, start++) group |= CBByteArrayGetByte(addr->ip, start) << x; if (bits > 0) group |= (CBByteArrayGetByte(addr->ip, start) | ((1 << bits) - 1)) << x; return group; } bool CBAddressManagerSetup(CBAddressManager * self){ // Allocate buckets self->buckets = malloc(sizeof(*self->buckets) * CB_BUCKET_NUM); // Create mutexes if(CBNewMutex(&self->addressMutex)){ if(CBNewMutex(&self->nodesMutex)){ // Create random number generators. self->rndGen = CBNewSecureRandomGenerator(); if (self->rndGen) { CBSecureRandomSeed(self->rndGen); // Cryptographically secure. self->secret = CBSecureRandomInteger(self->rndGen); self->rndGenForBucketIndexes = CBNewSecureRandomGenerator(); if (self->rndGenForBucketIndexes) { return true; } CBFreeSecureRandomGenerator(self->rndGen); } CBFreeMutex(self->addressMutex); CBFreeMutex(self->nodesMutex); }else{ CBGetMessage(self)->events->onErrorReceived(CB_ERROR_NETWORK_COMMUNICATOR_MUTEX_CREATE_FAIL,"The CBAddressManager 'nodesMutex' could not be created."); } CBFreeMutex(self->addressMutex); }else{ CBGetMessage(self)->events->onErrorReceived(CB_ERROR_NETWORK_COMMUNICATOR_MUTEX_CREATE_FAIL,"The CBAddressManager 'addressMutex' could not be created."); } return false; } void CBAddressManagerTakeAddress(CBAddressManager * self,CBNetworkAddress * addr){ // Find the bucket for this address. CBBucket * bucket = self->buckets + CBAddressManagerGetBucketIndex(self, addr); CBMutexLock(self->addressMutex); // Use mutex lock when modifying the addresses // Find insersion point for address uint16_t insert = 0; for (; insert < bucket->addrNum; insert++) { if (bucket->addresses[insert]->score > addr->score) // Insert here break; } if (bucket->addrNum == self->maxAddressesInBucket) { // A lot of addresses stored, remove random address but with bias to a low scoring address. uint16_t remove = (CBSecureRandomInteger(self->rndGen) % bucket->addrNum); remove *= remove; remove /= bucket->addrNum; // Release address CBReleaseObject(&bucket->addresses[remove]); if (insert < remove) // Insersion happens below removal. Move memory up to overwrite removed address and make space to insert. memmove(bucket->addresses + insert + 1, bucket->addresses + insert, remove-insert); else if (insert > remove){ // Insersion happens above removal. Move memory down to overwrite removed address and make space to insert. memmove(bucket->addresses + remove, bucket->addresses + remove + 1, insert-remove); insert--; // Move insert down since we moved memory down. } }else{ bucket->addrNum++; // Move memory up to allow insertion of address. memmove(bucket->addresses + insert + 1, bucket->addresses + insert, bucket->addrNum - insert - 1); } bucket->addresses[insert] = addr; CBMutexUnlock(self->addressMutex); // Now other threads can access the addresses. }
|
|
|
|
|