@adlrocha - Meet Mrs. Kademlia
The one responsible for the decentralization of blockchain technology.
|Dec 15, 2019|
When people think about the set of technical modules that make blockchain such a disruptive technology, what comes to their mind are things such as advanced cryptography, smart contracts or consensus algorithms. Few people relate P2P protocols with blockchain technology and, to me, the advances being made around field of P2P networking protocols, along with the development of brand new cryptographic primitives, go beyond blockchain technology. These advancements are shaping the next-generation Internet.
This is the reason why I thought it was worth dedicating a publication (or a set of them) to P2P protocols. I will start this journey introducing a technical scheme running in many of current (and past) P2P-based systems, DHT Kademlia.
Nothing new on the horizon
P2P protocols have been around for a while now. They didn’t appear with Bitcoin or blockchain technologies. Remember those applications we used in the year 2000 to download our favorite movies and songs (eDonkey, WarezP2P, Ares)? And the ones we use now (BitTorrent)? Or have you heard about Tor, the open source software that enables you to privately search the web? Well, guess what do all these systems have in common? They all use P2P protocols for its operation. They all use different implementations of several P2P protocols and schemes breaking the standard client-server model, and removing the need of centralized entities (sounds familiar, right?).
The building blocks
All these protocols in turn are conformed of several technical modules such as:
Distributed data stores: To enable the storage of information collaboratively between different nodes of the network. Some implementations of distributed data stores can be found in BitTorrent and IPFS.
Distributed Hash Tables offer a distributed lookup system that can be used as a distributed key-value database. It is generally used for routing purposes, or as a directory to locate information in the network (such as the location of the different parts that conform a file stored by nodes in a distributed network).
Merkle Trees: If you have some knowledge about blockchain technology no new knowledge for you here. These hash constructions were already used in several P2P systems before blockchain to allow efficient and secure verification of the contents of large data structures.
Mix networks: Mix networks are routing protocols that create hard-to-trace communications by using a chain of proxy servers known as mixes which take in messages from multiple senders, shuffle them, and send them back out in random order to the next destination (possibly another mix node). This breaks the link between the source of the request and the destination, making it harder for eavesdroppers to trace end-to-end communications (want to see these networks in action? Have a look at Tor).
NAT Traversal: NAT devices allow the use of private IP addresses on private networks behind routers with a single public IP address facing the Internet. The internal network devices communicate with hosts on the external network by changing the source address of outgoing requests to that of the NAT device and relaying replies back to the originating device. This is a problem for P2P systems, if we try to communicate directly between two devices behind a NAT without a intermediate server things get messy. Consequently, P2P networks use NAT traversal techniques (such as the ones used in VoIP system) to bypass this issue, enabling direct communication between devices behind NATs.
There are many more protocols and technical modules that can be used to efficiently implement P2P systems. In any case, I hope this brief overview with, in my opinion, the most important ones, gives you a grasp of the kind of things that can be done in a P2P environment. Let’s move on now to our matter at hands, the implementation of one of the P2P module I’ve been looking forward to talk about for a while, DHT Kademlia.
Kademlia is a DHT used to specify the structure of the network and the exchange of information through node lookups. It provides a way for millions of distributed devices to self-organize into a network, communicate, and share resources (such as files, blobs, objects, etc.). As I advanced, is not only used for routing and discovery purposes, but also as a mean of collaboratively sharing and storing information. Kademlia was conceived in 2002 (it is a few years from being able to go to a bar), and its discovery supposed the implementation of a significantly more reliable and efficient protocol for node discovery and routing, compared to the centralized and flood-based approaches used then.
Kademlia treats each node in the network as a leaf of a binary tree (see figure below). Generally, each Kademlia node has 160-bit NodeID, but the way of generating this value can differ according to the specific flavor or implementation of the protocol. There are scheme variations where, due to the network requirements, each node is identified through a pair of asymmetric keys, and the NodeIDs in Kademlia is represented through the hash function of the public key of the node. Thus, the Kademlia protocol can be fine-tuned according to the specific scenario and needs of the network (actually, just a few searches of “Kademlia DHT” in the Internet or Google Scholar will lead you to a ton of implementations and variations, such as the well-known S/Kademlia used to prevent Sybil Attacks and Eclipse Attacks).
Kademlia DHT introduces the notion of distance between nodes (to be strict distance between their identifiers). Thus, the distance of two nodes in the network is computed by XORing their NodeIDs:
D(x,y) = NodeIDx XOR NodeIDy
From a node point of view, the tree is divided into series of successive sub-trees where the 160th subtree contains the individual node. The Kademlia protocol ensures that each node knows of at least one node on each of its sub-trees. With this guarantee, a node can locate any other node by its ID.
Kademlia’s routing tables
Kademlia’s routing tables consists of k-buckets. A k-bucket is a list to store contact information of other nodes. There is a k-bucket for every node in the network (in the case of a node space of 160 bits, there will be a k-bucket from 0 to 160). Thus, the 160 k-bucket cover the whole 160 bit address space. For the implementation of Kademlia, its authors suggest the use of k=20, i.e. every node in the network will have lists containing up to 20 nodes for a particular bit (a particular distance from himself). In each k-bucket is typically stored the IP address, port and nodeID of another node. In this list we can add additional information useful for our specific use case, such as a specific blob stored by a device.
Every list corresponds to a specific distance from the node. Nodes that can go in the nth list must have a differing nth bit from the node's id; the first n-1 bits of the candidate id must match those of the node's id. This means that it is very easy to fill the first list as 1/2 of the nodes in the network are far away candidates. The next list can use only 1/4 of the nodes in the network (one bit closer than the first), etc. With an ID of 128 bits, every node in the network will classify other nodes in one of 128 different distances, one specific distance per bit.
As nodes are encountered on the network, they are added to the lists. This includes store and retrieval operations and even when helping other nodes to find a key. Every node encountered will be considered for inclusion in the lists. Therefore the knowledge that a node has of the network is very dynamic. This keeps the network constantly updated and adds resilience to failures or attacks.
If it is known that nodes that have been connected for a long time in a network will probably remain connected for a long time in the future. Because of this statistical distribution, Kademlia selects long connected nodes to remain stored in the k-buckets. This increases the number of known valid nodes at some time in the future and provides for a more stable network.
When a k-bucket is full and a new node is discovered for that k-bucket, the least recently seen node in the k-bucket is PINGed. If the node is found to be still alive, the new node is place in a secondary list; a replacement cache. The replacement cache is used only if a node in the k-bucket stops responding. In other words: new nodes are used only when older nodes disappear.
The Kademlia protocol specifies the following messages:
PING - used to verify that a node is still alive.
STORE - Stores a (key, value) pair in one node.
FIND_NODE - The recipient of the request will return the k nodes in his own buckets that are the closest ones to the requested key.
FIND_VALUE - as FIND_NODE, but if the recipient of the request has the requested key in its store, it will return the corresponding value.
Each RPC message includes a random value from the initiator. This ensures that when the response is received it corresponds to the request previously sent.
Locating nodes and resources
Node lookups can proceed asynchronously. A node initiates a FIND_NODE request by querying to the k nodes in its own k-buckets that are the closest ones to the desired key. When these recipient nodes receive the request, they will look in their k-buckets and return the k closest nodes to the desired key that they know. The requestor will update a results list with the results (node ID's) he receives, keeping the k best ones (the k nodes that are closer to the searched key) that respond to queries. Then the requestor will select these k best results and issue the request to them, and iterate this process again and again. Because every node has a better knowledge of his own surroundings than any other node has, the received results will be other nodes that are every time closer and closer to the searched key. The iterations continue until no nodes are returned that are closer than the best previous results. When the iterations stop, the best k nodes in the results list are the ones in the whole network that are the closest to the desired key. Thus, any device in the network can be efficiently found.
Locating a value follows the same procedure as locating the closest nodes to a key, except the search terminates when a node has the requested value in his store and returns this value. The values are stored at several nodes (k of them) to allow for nodes to come and go and still have the value available in some node. i.e. to provide redundancy. Every certain time, a node that stores a value will explore the network to find the k nodes that are close to the key value and replicate the value onto them. This compensates for disappeared nodes. This same scheme is followed by IPFS to store files in its network. In IPFS, for instance, the blobs representing files in the system are identified and stored according to their hash (I highly recommend reading IPFS’ whitepaper to see the joint operation of several P2P schemes).
Kademlia in action!
I suppose that by now you can start thinking about potential use cases for DHT Kademlia, but let me suggest a few for you:
Distributed storage (take the example of IPFS, SWARM or StorJ)
Node/Information lookup and discovery (DNS-like functionality)
Distributed network routing
Self-organized heterogeneous networks.
And probably many more I haven’t heard about, these are the ones that come to my mind right now.
And how could I be talking about the future of P2P technologies without introducing what, in my opinion, is one of the most exciting projects for the future of the Internet, libp2p. Libp2p is a modular network stack implementing several of the protocols you need to design robust an efficient distributed systems. In short, it is a framework for the development of distributed system.
There are implementation of libp2p modules in Rust, Go, NodeJs and BrowserJS. The library includes protocols for several transport protocols, implementations to perform stream multiplexing in nodes, crypto channels, discovery and peer routing protocols for distributed networks (you will find DHT implementations there), NAT Traversal functionalities, etc. Again, everything you need to ease the development of your distributed system.
In order for you to slightly grasp the potential and importance of this project, these are some notable projects already using the libp2p’s Rust implementation:
If you are curious to go a bit deeper on libp2p, what it offers and its operation, I encourage you to go to their official documentation. However, if you are too lazy for this, I will dedicate a publication soon to libp2p and some of the tests I am doing using its Rust implementation (I used go-libp2p a few years ago, but a lot has changed since then. Now is time to start learning Rust and get up to speed with libp2p in Rust).
DHT Kademlia original paper (it is short, straightforward and easy to follow, I’ve read it a few times, and I really recommend that you do it to deeply understand the scheme).
S/Kademlia original paper (another must for your reading list).
IPFS whitepaper. The best way of understanding how DHT Kademlia can be used.