At the Heart of Ring: OpenDHT — A Distributed Hash Table

Adrien Béraud encryptedThe need for efficient public distributed systems is becoming increasingly important as the influence of the Net giants centralizing information and communications more than ever is growing every day. This is a paradox since the Internet gives network nodes the unprecedented opportunity to exchange directly, without centralized processing point.

To address this issue, we developed OpenDHT — a free and open library implementing a distributed hash table and incorporating a number of important innovations. OpenDHT is at the heart of Ring, the decentralized communication system that we are also releasing today.

DHT (distributed hash table) is a class of distributed systems that provides access to a shared dictionary of keyvalue pairs from any node of the network, and in which this data is distributed among the participants. Currently, the most popular DHT networks, such as Mainline DHT (BitTorrent), are used for peer to peer file sharing. On these networks, the key is the identifier of the torrent file — also called “Magnet link” — and the values are the IP addresses of the seeders, i.e. the clients sharing the torrent.

OpenDHT

OpenDHT is a light and robust network project DHT in C++11 proposing a simple to use interface for application developers. Originally inspired by the DHT library developed by Juliusz Chroboczek and used, for example, by the BitTorrent client Transmission, OpenDHT includes a number of important innovations.

OpenDHT provides the ability to store any type of data — not just IP addresses — with a limit value of 64 KB. It has also a listening function (listen) enabling a node to be informed of changes in key values. Since we needed these crucial features for the Ring project, we wew pushed to create OpenDHT with the counterparty to make its protocol incompatible with the Mainline DHT network of BitTorrent.

The listen function is for example used in Ring to enable receiving calls or messages, even for computers behind NATs. In conjunction with the ICE technology, OpenDHT then allows the robust establishment of peer-to-peer connections.

OpenDHT is published on GitHub under the The GNU General Public License v3.0. Comments and patches are welcome. An early documentation is also available here.

OpenDHT is simple to use, thus reducing the cost and difficulty of developing applications that benefit from it. For example, starting a new node on local port 4222, and connecting to the network through a known node is as simple as these three lines of C++:

dht::DhtRunner node; node.run(4222, dht::crypto::generateIdentity(), true);
node.bootstrap("bootstrap.ring.cx", "4222");

Then storing any value on the network is achieved with a single line of code:

node.put("my_key", std::vector(5, 10));

The key to use will then be the SHA1 condensate of the text string “my_key”. The value will be a sequence of 5 bytes worth 10.

Later retrieve this value from another node will be as simple as this:

node.get("my_key", [](const std::vector& values) {
    for (const auto& value : values)
        std::cout << "Value found: "<< *value << std::endl;
    return true;
});

Some theory on DHTs

In the most popular type of DHT network (Kademlia) used by OpenDHT, each node (participant program) of the network has a unique identifier evenly distributed in the identifiers space — a 160-bit space in our case.

Similarly, each data stored on the network is characterized by an identifier which is its key. The keys are uniformly distributed in the same 160-bit space as the node identifiers. Multiple values can share the same key.

The binary operator XOR (⊕) is defined as the distance operator between key, or between keys and node IDs. To recap, the XOR result is true if both operands have different Boolean values. This implies that the XOR result of two 160-bit keys is the “binary distance” between these keys: A ⊕ A = 0 for every key A. For two distinct keys A and B with X = A ⊕ B, the number of zero bits at the beginning of X will be equal to the number of bits common to the beginning of A and B.

This interesting property offers the ability to partition each node’s routing table using a binary tree. In fact, each node maintains and updates a routing table including mainly the neighbouring nodes (in the sense of distance of the XOR operator introduced above).

DHT node exploration diagram
Fig. 1. To find the R node with the values for key H, the S node contacts A which is the closest to H node in its routing table. The response of A includes the IP address of B, now the closest to H in the table of S, and which is contacted, and so on.

A data element, that is to say a key-value pair (K, V), will be stored on the L nodes that are closest to key K (typically with L = 8). Any node knowing K will be able to find V by an iterative algorithm which will lead him to contact nodes whose identifiers are increasingly closer to K (Fig. 1).

Queries including the K key and the reply of each node include a list of other nodes known as closest to K. V value will be found in just O (log (N)) iterations — N representing the number of nodes on the network.

Cryptography

Just like the Internet, public DHT are inherently unreliable networks. They involve trusting many other programs randomly on the network to store data.

Instead of trying to make the protocol resistant and withstanding any type of malicious node, which would be illusive, the OpenDHT approach is to consider the network itself as untrustworthy and build over an optional cryptographic layer public key, using the PKCS infrastructure, and to verify the author and message integrity (signature) and encrypt the latter with public certificates published on the DHT network.

Knowing the identifier of the contact_id public key of a contact, storing an encrypted data for this contact on the DHT network is as simple as:
Ring

node.putEncrypted("my_key", contact_id, value);

The cryptography layer — or identity layer — then will transparently retrieve the certificate of the contact, use the public key to encrypt the data, and then store it on the network.

This layer will also transparently check the signature of signed data received. If the check fails, the data is not presented to the application. Similarly, only encrypted data that can be decrypted are passed to the application.

Ring implements these cryptographic operations to securely exchange invitations, initiation of calls and private messages. The network is therefore really used as a public meeting place.

Published by

Adrien Béraud

Holding a Masters in micro-engineering from the École polytechnique fédérale de Lausanne, Adrien is a Systems Engineer in the Embedded team of Savoir-faire Linux. He is in charge of developing the distributed hash library OpenDHT. Linkedin | Github | Montréal

28 thoughts on “At the Heart of Ring: OpenDHT — A Distributed Hash Table”

  1. Why do you need to limit the value size to 64k? Would it be difficult extending the system to arbitrary value size? If a network is composed of several subnetworks, with fast exchange between nodes within a subnetwork, but slow exchange across subnetworks, does the system support data replication such that values are accessible in each subnetwork?

    When listening/waiting for values, what latency on top of network latency can I expect when waiting for a key that has not yet been written?

  2. I must thank you for the efforts you have put in penning this website.
    I’m hoping to view the same high-grade content from you later on as
    well. In truth, your creative writing abilities has inspired me to get my
    own website now 😉

  3. We’re a gaggle of volunteers and starting a brand
    new scheme in our community. Your website offered us with helpful info to work
    on. You have performed a formidable task and our entire community can be grateful to you.

  4. man fuck google why do they have to take over youtube?? I remember the rating stars shitiwh(ch was way better) and the beautiful channel design that had youtube back in the days of 2008. Now to create a youtube account its like making a geometry homework.

  5. OTLANGAÇ’TA ARABAYA SERVÄ°S HÄ°ZMETÄ°MÄ°Z BAÅžLAMIÅžTIR…Canım midye tava kokoreç midye dolma istedi,fakat hava soÄŸuk yaÄŸmur yağıyor dışarda oturamayız,içeri girsek üzerimize koku siner derdine son…Buyrun gelin sıcak sıcak arabanızda oturun,biz arabanıza sıcak sıcak servis yapalım..VA:F [1.9.22_1171]please wait…VA:F [1.9.22_1171](from 0 votes)

  6. I seldom drop remarks, however I read a few of the responses on OpenDHT — A Distributed Hash Table.
    I actually do have 2 questions for you if it’s allright. Is
    it only me or do a few of these comments look as if they are left by brain dead visitors?

    😛 And, if you are posting at additional online social sites, I’d like to follow you.

    Would you list of every one of your public sites like your Facebook page,
    twitter feed, or linkedin profile?

  7. Greetings I am so happy I found your blog, I really found you by
    error, while I was looking on Bing for something else, Anyhow I am here now and would just like to say kudos for a marvelous post
    and a all round exciting blog (I also love the theme/design), I don’t have time to look over it all at the moment but I
    have bookmarked it and also added in your RSS feeds, so when I
    have time I will be back to read more, Please do keep up the excellent job.

  8. I was suggested this blog by means of my cousin. I am no longer positive whether or not this submit
    is written by means of him as no one else recognise such distinctive approximately my problem.
    You’re amazing! Thanks!

  9. I would like to thank you for the efforts you have put
    in penning this website. I really hope to view the same high-grade blog posts by you in the future as well.
    In fact, your creative writing abilities has encouraged me to
    get my own, personal blog now 😉

  10. Definitely believe that which you stated. Your favorite reason seemed
    to be on the net the simplest thing to be aware of.
    I say to you, I definitely get irked while people
    think about worries that they plainly don’t know about. You managed
    to hit the nail upon the top and defined out the whole thing without having side-effects , people could take a
    signal. Will likely be back to get more. Thanks

  11. My programmer is trying to persuade me to move to .net from PHP. I have always disliked the idea because of the costs. But he’s tryiong none the less. I’ve been using WordPress on a number of websites for about a year and am worried about switching to another platform. I have heard very good things about blogengine.net. Is there a way I can import all my wordpress content into it? Any help would be really appreciated!

Leave a Reply

Your email address will not be published. Required fields are marked *