The Kademlia Protocol Succinctly^®
by Marc Clifton

CHAPTER 3

Getting Started

First, let’s cover some basic implementation requirements for a node.

The BigInteger class

We could write our own byte array manipulation and comparison operators, which is what zencoders did, or we could use the BigInteger class in the System.Numerics namespace to handle the range of IDs from 0 <= id <= 2¹⁶⁰ - 1. This is much more convenient than implementing all the bitwise logic and unit tests! As a side node, I was impressed with Python’s ability to handle these values without any special classes:

Code Listing 2: Python Big Numbers

>>> 2 ** 160

1461501637330902918203684832716283019655932542976L

The node specification

“Participating computers each have a node ID in the 160-bit key space,” which is simple enough. However, beware of how buckets in a node are initialized. In the shorter specification, it is implied that a node has 160 k-buckets, one for each bit in the 160-bit SHA1 hash. The longer specification discusses bucket splitting and “initially, a node u’s routing tree has a single node— one k-bucket covering the entire ID space.” By looking at an implementation’s initialization of the k-buckets, one can immediately determine which specification the code is written against.

A framework for the implementation

The initial framework for the implementation consists of the following classes:

Dht: The peer’s entry point for interacting with other peers.
Router: Manages peer (node) lookups for acquiring nearest peers and finding key-value pairs.
Node: Provides the Ping, Store, FindNode, and FindValue implementations.
BucketList: Manages the contacts (peers) in each bucket and the algorithm for adding contacts (peers) to a particular bucket.
ID: Implements a wrapper for BigInteger and various helper methods and operator overloads for the XOR logic
Contact: Maintains the protocol that the contact (peer) uses, its ID, and LastSeen DateTime, which is used for determining whether a peer should be tested for eviction.
KBucket: Retains the collection of contacts (peers) that are associated with a specific bucket, implements the bucket splitting algorithm, and provides other useful methods for obtaining information regarding the bucket.

These interact as illustrated in the model diagram:

Blue: classes
Orange: interfaces
Purple: collections
Green: value type fields

The Class Model

Figure 1: The Class Model

The ID class: initial implementation

Code Listing 3: ID Class

public class ID

{

public BigInteger Value { get { return id; } set { id = value; } }

protected BigInteger id;

public ID(byte[] data)

{

IDInit(data);

}

public ID(BigInteger bi)

{

id = bi;

}

protected void IDInit(byte[] data)

{

Validate.IsTrue<IDLengthException>(data.Length == Constants.ID_LENGTH_BYTES, "ID

must be " + Constants.ID_LENGTH_BYTES + " bytes in length.");

id = new BigInteger(data.Append0());

}

Note: The Validate class defines some helper methods for asserting the condition and throwing the exception specified as the generic parameter.

There are two things to note here. First, we append the byte array with a 0 to force unsigned values in the BigInteger. If we don’t do this, any byte array where the MSB of byte[0] is set will be treated as a negative number, which we don’t want when we are comparing the range of a bucket. This is handled by a simple extension method, as in Code Listing 4.

Code Listing 4: The Append0 Extension Method

public static byte[] Append0(this byte[] b)

{

return b.Concat(new byte[] { 0 }).ToArray();

}

Second, the byte array is in little-endian order, meaning that the least significant byte is stored first. This can get confusing when contrasted with the way that the Kademlia specification talks about ID “prefixes” and the way we tend to represent bits in an array. For example, this ID, in bits, is written out in big-endian order:

11001000 00001100

The 6-bit prefix would be 110010. As a BigInteger, the array is in little-endian order, so the bytes are ordered such that the least significant byte (the LSB) is stored first:

00001100 11001000

For convenience, we implement a couple of helper properties. An extension method Bits is used to create a fluent method-chaining coding style.

Code Listing 5: Getting the bits in Big Endian Order

public string AsBigEndianString

{

get
{
return String.Join(““, Bytes.Bits().Reverse().Select(b => b ? "1" : "0"));
}

}

public bool[] AsBigEndianBool
{
get
{
return Bytes.Bits().Reverse().ToArray();
}
}

Also notice the local method, which is a C# 7 feature.

Code Listing 6: Bits Extension Method

public static IEnumerable<bool> Bits(this byte[] bytes)

{

IEnumerable<bool> GetBits(byte b)

{

byte shifter = 0x01;

for (int i = 0; i < 8; i++)

{

yield return (b & shifter) != 0;

shifter <<= 1;

}

return bytes.SelectMany(GetBits);

}

The ID class: unit tests

We can implement a few simple unit tests to verify the implementation:

Code Listing 7: ID Unit Tests

[TestClass]

public class IDTests

{

[TestMethod]

public void LittleEndianTest()

{

byte[] test = new byte[20];

test[0] = 1;

Assert.IsTrue(new ID(test) == new BigInteger(1), "Expected value to be 1.");

}

[TestMethod]

public void PositiveValueTest()

{

byte[] test = new byte[20];

test[19] = 0x80;

Assert.IsTrue(new ID(test) == BigInteger.Pow(new BigInteger(2), 159), "Expected
value to be 1.");

}

[TestMethod, ExpectedException(typeof(IDLengthException))]

public void BadIDTest()

{

byte[] test = new byte[21];

new ID(test);

}

[TestMethod]

public void BigEndianTest()

{

byte[] test = new byte[20];

test[19] = 0x80;

Assert.IsTrue(new ID(test).AsBigEndianBool[0] == true, "Expected big endian bit
15 to be set.");

Assert.IsTrue(new ID(test).AsBigEndianBool[8] == false, "Expected big endian bit
7 to NOT be set.");

}

The Router class

At the moment, the Router class simply manages the host’s node (the host is our peer).

Code Listing 8: Stub for the Router

public class Router

{
protected Node node;

public Router(Node node)

{

this.node = node;

}

The Contact class

The Contact class manages the contact’s ID, LastSeen, and network connectivity. Because I want to abstract the way network protocols are handled such that it is easy to test nodes in a virtual (in-memory) network, or nodes that use different protocols (UDP, TCP/IP, WebSockets, etc.), the network protocol is abstracted in an interface.

Code Listing 9: Basic Contact Class

Public class Contact : Icomparable

{

public IProtocol Protocol { get; set; }

public DateTime LastSeen { get; set; }

public ID ID { get; set; }

/// <summary>

/// Initialize a contact with its protocol and ID.

/// </summary>

public Contact(IProtocol protocol, ID contactID)

{

Protocol = protocol;

ID = contactID;

Touch();

}

/// <summary>

/// Update the fact that we’ve just seen this contact.

/// </summary>

public void Touch()

{

LastSeen = DateTime.Now;

}

The KBucket class

Each k-bucket maintains a list of up to k contacts.

Code Listing 10: The KBucket Class

public class KBucket

{

public DateTime TimeStamp { get; set; }

public List<Contact> Contacts { get { return contacts; } }
public BigInteger Low { get { return low; } set { low = value; } }

public BigInteger High { get { return high; } set { high = value; } }

public bool IsBucketFull { get { return contacts.Count == Constants.K; } }

protected List<Contact> contacts;

protected BigInteger low;

protected BigInteger high;

public KBucket()

{

contacts = new List<Contact>();

low = 0;

high = BigInteger.Pow(new BigInteger(2), 160);

}

/// <summary>

/// Initializes a k-bucket with a specific ID range.

/// </summary>

public KBucket(BigInteger low, BigInteger high)

{

contacts = new List<Contact>();

this.low = low;

this.high = high;

}

public void Touch()

{

TimeStamp = DateTime.Now;

}

public void AddContact(Contact contact)

{

Validate.IsTrue<TooManyContactsException>(contacts.Count < Constants.K, "Bucket
is full");

contacts.Add(contact);

}
}

The KBucket class: a unit test

A simple start for a unit test for the KBucket class is simply to verify that an exception is thrown when too many contacts are added.

Code Listing 11: Basic KBucket Unit Test

[TestClass]

public class KBucketTests

{

[TestMethod, ExpectedException(typeof(TooManyContactsException))]

public void TooManyContactsTest()

{

KBucket kbucket = new KBucket();

// Add max # of contacts.

Constants.K.ForEach(n => kbucket.AddContact(new Contact(null, new ID(n))));

// Add one more.

kbucket.AddContact(new Contact(null, new ID(21)));

}

Notice the extension method ForEach.

Code Listing 12: ForEach Extension Method

public static void ForEach(this int n, Action<int> action)

{

for (int i = 0; i < n; i++)

{

action(i);

}

Again, this is used for a more fluent method chaining syntax.

The BucketList class

The BucketList class is a high-level singleton container for buckets and operations that manipulate buckets. For the moment, most of this is stubbed with minimal behavior.

Code Listing 13: The BucketList Class

public class BucketList : IBucketList

{

public List<KBucket> Buckets { get { return buckets; } }

public ID OurID { get { return ourID; } }

protected List<KBucket> buckets;

public BucketList(ID id)

{

ourID = id;

buckets = new List<KBucket>();

// First kbucket has max range.

buckets.Add(new KBucket());

}

public void AddContact(Contact contact)

{
// To be implemented…

}
}

The Node class

The Node class is another high-level singleton container for handling the Kademlia commands sent over the wire. This is mostly stubbed for now.

Code Listing 14: The Node Class

public class Node : INode

{

public Contact OurContact { get { return ourContact; } }

public IBucketList BucketList { get { return bucketList; } }

public IStorage Storage { get { return storage; } set { storage = value; } }

protected Contact ourContact;

protected IBucketList bucketList;

protected IStorage storage;

public Node(Contact contact, IStorage storage, IStorage cacheStorage = null)

{

ourContact = contact;

bucketList = new BucketList(contact.ID);

this.storage = storage;

}

public Contact Ping(Contact sender)
{

     // To be implemented…

    return ourContact;
}

public void Store(Contact sender, ID key, string val)
{
    // To be implemented…
}

public (List<Contact> contacts, string val) FindNode(Contact sender, ID key)
{
    // To be implemented…
}

public (List<Contact> contacts, string val) FindValue(Contact sender, ID key)
{
    // To be implemented…
}
}

Of note here is the interface IStorage, which abstracts the storage mechanism for key-value pairs. Ultimately, IStorage will implement the following methods from Code Listing 15.

Code Listing 15: The IStorage Interface

public interface IStorage

{

bool Contains(ID key);

bool TryGetValue(ID key, out string val);

string Get(ID key);

string Get(BigInteger key);

DateTime GetTimeStamp(BigInteger key);

void Set(ID key, string value, int expirationTimeSec = 0);

int GetExpirationTimeSec(BigInteger key);

void Remove(BigInteger key);

List<BigInteger> Keys { get; }

void Touch(BigInteger key);

}

The Dht class

The Dht class is the “server”—the entry point for instantiating our peer. At the moment, the Dht class is simply a container for the Router:

Code Listing 16: Stub for the Dht Class

public class Dht : IDht
{
public BaseRouter Router { get { return router; } }
protected BaseRouter router;
}

Build apps 2X faster

using Syncfusion Essential Studio^® suite

1800+ high-performance UI components.
Includes popular controls such as Grid, Chart, Scheduler, and more.
24x5 unlimited support by developers.

Get Your Free Trial Now

Getting Started

The BigInteger class

The node specification

A framework for the implementation

The ID class: initial implementation

The ID class: unit tests

The Router class

The Contact class

The KBucket class

The KBucket class: a unit test

The BucketList class

The Node class

The Dht class

DISCLAIMER: Web reader is currently in beta. Please report any issues through our support system. PDF and Kindle format files are also available for download.