Creating a simple cryptocurrency: part 11

The latest repository.

Distributed Hash Table (DHT)

DHT's are another breakthrough technology for creating decentralized systems. From Wikipedia:

A distributed hash table (DHT) is a class of a decentralized distributed system that provides a lookup service similar to a hash table: (key, value) pairs are stored in a DHT, and any participating node can efficiently retrieve the value associated with a given key. Responsibility for maintaining the mapping from keys to values is distributed among the nodes, in such a way that a change in the set of participants causes a minimal amount of disruption. This allows a DHT to scale to extremely large numbers of nodes and to handle continual node arrivals, departures, and failures.

A DHT is just a key-value map but distributed among many nodes, with no central point of failure. We can use a DHT map to lookup the IPv4 address:port of a server if we know its 32-byte public key, therefore we do not need to hard-code the former into our program. If a server's IP and or port number changes, we can quickly adapt.

We will use the Mainline variant of the Kademlia DHT, the same one used by Bittorrent Clients. The Mainline DHT is very large and well-established, and there is an NPM package available for interfacing with it: bittorrent-dht.

However, I found some bugs in the current version of this package and one of its dependencies and reported them, but the package is not well-maintained and after two months my fixes have not yet been incorporated. So I forked the corresponding Github project into my own repository. See below for instructions to override the original version with my version.

There are two new top-level objects in our program: dh for interfacing with the Mainline DHT, and bt for bootstrapping the DHT interface from a file of stored nodes.

The dh object (DHT)

The NPM module bittorrent-dht returns a constructor which we use to create an object, then store it in dh.dht. The new object is initialized with a port number and previously saved nodes (see below). UDP is used for communication between nodes, so this port number must be different from the server port number to avoid conflict. The command line now accepts two port arguments: server.js [dhtPort [serverPort]]. The ports default to 6881 and 6882, 6881 being a traditional DHT port.

After the local DHT table is populated with nodes, the local server IP address:port is published to the DHT, using the local public key as the DHT key. Remote Scryp servers and clients can lookup our server's IP address:port knowing out public key. This is accomplished by the dh.read property function, which is currently activated once per minute.

Thus, if any server becomes disconnected from our network and reconnects with a different IP address:port, the Scryp network will automatically adapt.

The bt object (DHT bootstrap)

The DHT table must be initialized with the IP address:port of at least one node in the Mainline DHT network, from which it can acquire information about other nodes so as to populate the local table with enough nodes to make searching for stored values efficient. On the first startup, we populate the table with special stable nodes such as router.bittorrent.com:6881. This is a dependency on the centrally controlled DNS domain lookup network, which is undesirable but could be avoided if one or more servers in the Scryp network has a permanent, dedicated IP address:port.

But once the table is populated, nodes are periodically saved to a file named .boot for future use. Using saved nodes removes the dependency on DNS and also results in more efficient lookups of previously stored information. If the .boot file becomes stale because too much time elapsed since its last update, simply remove it to trigger a re-population from a special node.

Overriding bittorrent-dht and k-rpc

As mentioned above, these two NPM packages have bugs which haven't been fixed yet, so I created forks with the fixes to override them. Here is the override procedure:

1. If your node_modules directory (where NPM packages are stored) is located in the same directory where your server.js file is stored, move it to your home directory. The require function automatically searches up the directory tree until it finds the needed package, using the first instance of the package that it finds.
2. Install the original NPM package bittorrent-dht (npm i bittorrent-dht)in the moved node_modules directory. Although we are overriding the main part of this package and one of the dependencies, there are many other dependencies that we need that are automatically installed.
3. Create a new node_modules directory where the old one used to be.
4. Download into this directory the two modified packages bittorrent-dht and k-rpc from my repository.
5. Unzip theses packages and remove the -master ending from the resulting directories. They now have the same names as their counterparts in the higher level node_modules directory and so will override them.
6. Do not run npm in this directory or in the parent of this directory, because it will remove the two manually downloaded packages, not having any record of them. Instead, run npm in the higher level directory or its parent (your home directory) if you want to acquire new packages.

< part 10 | part 12 >