The Kademlia Protocol Succinctly®
CHAPTER 8
The Dht–Bootstrapping
From the spec: “To join the network, a node u must have a contact to an already participating node w. u inserts w into the appropriate k-bucket. u then performs a node lookup for its own node ID. Finally, u refreshes all k-buckets further away than its closest neighbor. During the refreshes, u both populates its own k-buckets and inserts itself into other nodes’ k-buckets as necessary.”
The Wikipedia page adds a little more detail:
“The joining node inserts the bootstrap node into one of its k-buckets. The joining node then does a FIND_NODE of its own ID against the bootstrap node (the only other node it knows). The “self-lookup” will populate other nodes’ k-buckets with the new node ID, and will populate the joining node’s k-buckets with the nodes in the path between it and the bootstrap node. After this, the joining node refreshes all k-buckets further away than the k-bucket the bootstrap node falls in. This refresh is just a lookup of a random key that is within that k-bucket range.”
By choosing a random ID within the contact’s bucket range, we are creating an ID whose prefix determines the ordering of the contacts returned by GetCloseContacts:
Select(c => new { contact = c, distance = c.ID.Value ^ key.Value }).OrderBy(d => d.distance)
This will sort the contacts such that those that are closer—those where no bits are set in the prefix of the contact—are first in the list. Ideally, with many peers participating, we should get k contacts that are closer.
Of particular note here is that when a peer network is small or in the throes of being born, other contacts that nodes have will not be discovered until the bootstrapping bucket splits. We’ll see how the network self-corrects later on. It’s also interesting to realize that “joining” actually means contacting another node with any one of the four RPC calls. A new peer could join an existing network with its first RPC being FindValue!
Bootstrapping implementation
Getting a random ID within a bucket range is based on knowing that bucket ranges are always powers of 2. We use this for unit testing.
Code Listing 61: RandomIDWithinBucket
/// <summary> /// Returns an ID within the range of the bucket's Low and High range. /// The optional parameter forceBit1 is for our unit tests. /// This works because the bucket low-high range will always be a power of 2! /// </summary> public static ID RandomIDWithinBucket(KBucket bucket, bool forceBit1 = false) { // Simple case: // High = 1000 // Low = 0010 // We want random values between 0010 and 1000 // Low and High will always be powers of 2. var lowBits = new ID(bucket.Low).Bytes.Bits().Reverse(); var highBits = new ID(bucket.High).Bytes.Bits().Reverse(); // We randomize "below" this High prefix range. int highPrefix = highBits.TakeWhile(b => !b).Count() + 1; // Up to the prefix of the Low range. // This sets up a mask of 0's for the LSB's in the Low prefix. int lowPrefix = lowBits.TakeWhile(b => !b).Count(); // RandomizeBeyond is little endian for "bits after" so reverse high/low prefixes. ID id = Zero.RandomizeBeyond(Constants.ID_LENGTH_BITS - highPrefix, // The we add the low range. id = new ID(bucket.Low + id.Value); return id; } |
Bootstrapping
The actual bootstrap implementation is straightforward.
Code Listing 62: DHT Bootstrap
/// <summary> /// Bootstrap our peer by contacting another peer, adding its contacts /// to our list, then getting the contacts for other peers not in the /// bucket range of our known peer we're joining. /// </summary> public RpcError Bootstrap(Contact knownPeer) { node.BucketList.AddContact(knownPeer); var (contacts, error) = knownPeer.Protocol.FindNode(ourContact, ourId); HandleError(error, knownPeer); if (!error.HasError) { contacts.ForEach(c => node.BucketList.AddContact(c)); KBucket knownPeerBucket = node.BucketList.GetKBucket(knownPeer.ID); // Resolve the list now, so we don't include additional contacts as we var otherBuckets = node.BucketList.Buckets.Where( otherBuckets.ForEach(b => RefreshBucket(b)); foreach (KBucket otherBucket in otherBuckets) { RefreshBucket(otherBucket); } } return error; } { bucket.Touch(); ID rndId = ID.RandomIDWithinBucket(bucket); // Isolate in a separate list as contacts collection for this bucket might change. List<Contact> contacts = bucket.Contacts.ToList(); contacts.ForEach(c => { var (newContacts, timeoutError) = c.Protocol.FindNode(ourContact, rndId); HandleError(timeoutError, c); newContacts?.ForEach(otherContact => node.BucketList.AddContact(otherContact)); }); } |
Bootstrapping unit tests
Getting a random ID within a bucket range is complicated enough that it deserves a unit test.
Code Listing 63: RandomWithinBucketTests
[TestMethod] public void RandomWithinBucketTests() { // Must be powers of 2. List<(int low, int high)> testCases = new List<(int low, int high)>() { (0, 256), // 7 bits should be set (256, 1024), // 2 bits (256 + 512) should be set (65536, 65536 * 2), // no additional bits should be set. (65536, 65536 * 4), // 2 bits (65536 and 65536*2) should be set. (65536, 65536 * 16), // 4 bits (65536, 65536*2, 65536*4, 65536*8) set. }; foreach (var testCase in testCases) { KBucket bucket = new KBucket(testCase.low, testCase.high); // We force all bits in the range we are "randomizing" to be true // so it's not really randomized. This verifies the outer algorithm // that figures out which bits to randomize. ID id = ID.RandomIDWithinBucket(bucket, true); Assert.IsTrue(id >= bucket.Low && id < bucket.High, // The ID, because we're forcing bits, should always be (high - 1) and int bitCheck = (testCase.high - 1) & ~Math.Max(0, testCase.low - 1); Assert.IsTrue(id.Value == bitCheck, "Expected bits are not correct."); } } |
BootstrapWithinBootstrappingBucket
In the actual bootstrapping unit test, we are setting up a bootstrapping peer we are joining to with 10 contacts. One of those contacts also knows about 10 other contacts. The joining peer will receive 10 contacts (for a total of 11, the bootstrapper + 10) and will not find any others because the “other peers not in the known peer bucket” are all in the same bucket (the bucket hasn’t split yet). The IDs for our peers are irrelevant in this scenario.
Code Listing 64: BootstrapWithinBootstrappingBucketTest
[TestMethod] public void BootstrapWithinBootstrappingBucketTest() { // We need 22 virtual protocols. One for the bootstrap peer, // 10 for the nodes the bootstrap peer knows about, and 10 for the nodes // one of those nodes knows about, and one for us to rule them all. VirtualProtocol[] vp = new VirtualProtocol[22]; 22.ForEach((i) => vp[i] = new VirtualProtocol()); // Us Dht dhtUs = new Dht(ID.RandomID, vp[0], () => new VirtualStorage(), new Router()); vp[0].Node = dhtUs.Router.Node; // Our bootstrap peer Dht dhtBootstrap = new Dht(ID.RandomID, vp[1], vp[1].Node = dhtBootstrap.Router.Node; Node n = null; // Our boostrapper knows 10 contacts 10.ForEach((i) => { Contact c = new Contact(vp[i + 2], ID.RandomID); n = new Node(c, new VirtualStorage()); vp[i + 2].Node = n; dhtBootstrap.Router.Node.BucketList.AddContact(c); }); // One of those nodes, in this case the last one we added to our bootstrapper // for convenience, knows about 10 other contacts. 10.ForEach((i) => { Contact c = new Contact(vp[i + 12], ID.RandomID); Node n2 = new Node(c, new VirtualStorage()); vp[i + 12].Node = n; n.BucketList.AddContact(c); // Note we're adding these contacts to the 10th node. }); dhtUs.Bootstrap(dhtBootstrap.Router.Node.OurContact); Assert.IsTrue(dhtUs.Router.Node.BucketList.Buckets.Sum( } |
BootstrapOutsideBootstrappingBucket
In this test, we set up 20 nodes in the bootstrap peer so that we know how the buckets split for us (20 in the left one, one in the right one) and add 10 contacts to the one in the right one. Because out bootstrap peer will be in our left bucket, we should have a total of 31 contacts (bootstrap + its 20 contacts + the other nodes 10 contacts).
Code Listing 65: BootstrapOutsideBootstrappingBucketTest
[TestMethod] public void BootstrapOutsideBootstrappingBucketTest() { // We need 32 virtual protocols. One for the bootstrap peer, // 20 for the nodes the bootstrap peer knows about, 10 for the nodes // one of those nodes knows about, and one for us to rule them all. VirtualProtocol[] vp = new VirtualProtocol[32]; 32.ForEach((i) => vp[i] = new VirtualProtocol()); // Us, ID doesn't matter. Dht dhtUs = new Dht(ID.RandomID, vp[0], () => new VirtualStorage(), new Router()); vp[0].Node = dhtUs.Router.Node; // Our bootstrap peer // All IDs are < 2^159 Dht dhtBootstrap = new Dht(ID.Zero.RandomizeBeyond(Constants.ID_LENGTH_BITS - 1), vp[1].Node = dhtBootstrap.Router.Node; Node n = null; // Our boostrapper knows 20 contacts 20.ForEach((i) => { ID id; // All IDs are < 2^159 except the last one, which is >= 2^159 // which will force a bucket split for _us_ if (i < 19) { id = ID.Zero.RandomizeBeyond(Constants.ID_LENGTH_BITS - 1); } else { id = ID.Max; } Contact c = new Contact(vp[i + 2], id); n = new Node(c, new VirtualStorage()); vp[i + 2].Node = n; dhtBootstrap.Router.Node.BucketList.AddContact(c); }); // One of those nodes, in this case specifically the last one we added to 10.ForEach((i) => { Contact c = new Contact(vp[i + 22], ID.RandomID); Node n2 = new Node(c, new VirtualStorage()); vp[i + 22].Node = n; n.BucketList.AddContact(c);// Note we're adding these contacts to the 10th node. }); dhtUs.Bootstrap(dhtBootstrap.Router.Node.OurContact); Assert.IsTrue(dhtUs.Router.Node.BucketList.Buckets.Sum( } |
- 1800+ high-performance UI components.
- Includes popular controls such as Grid, Chart, Scheduler, and more.
- 24x5 unlimited support by developers.