Welcome to the all-new “Let Freedom Stream” series, where we’re rolling out dWeb 3.0, the world’s first blockchain-less and distributed web. We are very excited about the debut of dWeb 3.0 and we’ve been hard at work on its many components. As promised, to kick things off, we’re going to go through dWeb’s revolutionary Graph DHT that’s a part of the all-new dMesh framework I announced just days ago. dMesh’s all-new Graph DHT is allowing us to build multi-writer distributed databases that are truly efficient, in a way we simply can’t with blockchains. It’s making our apps more decentralized and much faster than their blockchain-based counterparts.
Graph theory is one of the more interesting theories I’ve studied and if you think about it, graphs are all around us, whether it be people, ideas or pieces of data — our world is just a bunch of graphs. There are two common types of graphs, one known as an “undirected graph” (https://algs4.cs.princeton.edu/41graph/) where the edge definitions or connections between data points are “unordered pairs” and a directed graph, where the edges are “ordered pairs”. Graph theory has been around since Swiss mathematician Leonhard Euler decided to figure out how to cross over 7 bridges that connected two islands, without crossing back over the same bridge more than once. Long story short, it wasn’t possible, but it led him to an even bigger discovery, which ended up being graph theory. I bet Euler never figured that we would be using graph theory in 2021, but we certainly are and it’s about to set the dWeb apart from other webs.
As I have explained previously, a DHT is simply a key-value store, where the key is some sort of unique key and the value is whatever you want it to be. The problem with this is that a simple key-value store, if used in the most simplistic way, is not an efficient way to store data for something like a social network. In fact, it simply wouldn’t work.
For example, consider the following key-value store within a DHT:
```
KEYS VALUES
============ ==================
1. post1 this is a post
2. love1 {
forPost: post1,
byUser: user1,
}
3. repost1 {
ofPost: post1,
byUser: user1
}
4. favorite1 {
forPost: post1,
byUser: user1
}
5. follow1 {
follower: user1,
following: user2
}
```
Imagine a social network with millions of posts and millions of users. Then imagine having to traverse that database and piece together a UI of posts and all the interactions connected to them. How do you figure out which entries are for which posts, without opening up each entry and reading its value? Since you can only the traverse the database by key, you would have to open up “repost1”, just to see if it was a repost of post1, by user1. What if I wanted to find out how many reposts user1 had? Or how many times post1 had been reposted? Well, with the above design, it simply wouldn’t work. Not to mention, how in the world would you figure out who is following who? With millions of entries in the DHT, every time you loaded someone’s follower page, the service layer of your application would have to open up each entry in the DHT and then utilize only the data that applied to a particular user’s following/follower lists. This would take several minutes, which means your users would probably be pretty angry.
dMesh DHT’s new graphing system allows you to create an “edge label”, a “from edge” and a “to edge”, which ends up creating a key in the format “label/from/to”, where “/” is a separator in the key. In the case of dSocial, we utilize this to create what we call “many-to-many” connections for our data schema and since dMesh DHT’s is a directed graph, with a depth-first traversal system, we’re able to iterate over that data 1000 times more efficiently than we can with a blockchain and it costs us absolutely nothing. To give you an example of how this works, consider the following DHT-based key-value store:
```
KEY VALUE
======================== =======================
/jared/posts/500 null
/jared/loves/500 null
/jared/loves/320 null
/jared/loves/310 null
/bob/replies/401 null
/bob/replies/500 null
/bob/loves/500 null
/bob/favorites/500 null
/jared/favorites/243 null
/jared/profile/bio { data: This is Jared’s profile bio }
/jared/profile/location { data: Dallas, TX }
/jared/profile/displayname { data: Jared Rice Sr. }
/jared/profile/url { data: dweb://try.dweb }
/jared/profile/image { data: dweb://a4d32a… }
/jared/profile/himage { data: dweb://f3ad2d… }
…
500 {
postData: This is post #500,
postTimestamp: <epoch>,
postUser: jared,
postDrive: dweb://a3d3da3…
}
…
…
/500/loves/jared null
/500/reposts/bob null
/500/replies/502 null
/500/favorites/bob null
/500/loves/bob null
…
502 {
postData: This is post #502. It’s a reply to post #500,
postTimestamp: <epoch>,
postUser: bob,
postDrive: null
}
…
```
If you look at the above database, I’m guessing some of you can figure out how this works. Some of the entries we’ve created contain the “null” value, which means that they contain nothing, so why create them if they contain nothing? Well, because the data we’re utilizing is actually in the key and the key in-turn also points us to the actual data in most cases. Lets take my post (post #500). When creating this post, we actually create multiple entries in the DHT as follows:
### Entry #1:
```
/jared/posts/500 => null
```
### Entry #2:
```
500 => {
postData: This is post #500,
postTimestamp: <epoch>,
postUser: jared,
postDrive: dweb://a3d3da3…
}
```
Then, when I love my own post (of course), multiple entries are created for this as well, as follows:
### Entry #1:
```
/jared/loves/500 => null
```
### Entry #2:
```
500/loves/jared => null
```
This sort of format makes it easy to traverse the DHT for the data we need. For example, I can traverse the DHT for just the “label edge” and the “from edge” and it will give me all entries that match that portion of the key. For example, I could search for “/jared/loves/” and it will then give me all the entries in the DHT that match that. This would return the following:
```
/jared/loves/500
/jared/loves/320
/jared/loves/310
```
In the same way, I could search “500/loves” and it would return all the usernames that have loved postID 500. Using the above database, this would return:
```
500/loves/jared
500/loves/bob
```
NOTE: It’s important to note that the keys you see above are truly stored in binary within the DHT but can be traversed as hexadecimal-based strings, or by their human-readable format as shown above.
Since dMesh’s Graph DHT uses a depth-first traversal, we could utilize a depth of 10, and it would only return the first 10 results. This allows us to iterate over the DHT in ways you essentially cannot with the Hyper network. I mention Hyper because we originally used their DHT, before forking and moving in a different direction. I will say though, we borrowed a lot from what they were able to accomplish over the past several years.
All of you GraphQL lovers out there are already seeing the light I’m sure. You’re probably wondering how GraphQL can fit into this as a potential building block in a dApp’s service layer. dApps can essentially use GraphQL to create an undirected graph, on top of the directed graph that’s created by dMesh’s Graph DHT. This means we’re able to traverse a DHT even more efficiently, which is quite scary if you think about it. The beautiful thing about dMesh’s Graph DHT is that its libraries can be used on top of ANY Node.JS-based Kademilia DHT, considering we’re using dMesh’s Graph DHT on top of dWeb’s DHT (https://github.com/dwebprotocol/dht). You can use the “@dmesh/graph-dht” library to create edges and traverse any DHT for specific points on a graph. Simply put, the “graph-dht” library is used to generate specially formatted keys (label/from/to), and for traversing a DHT for those formatted keys, using a depth-first traversal. In the coming days, we will be releasing the code the “graph-dht” library, although we have already released the code for “@dmesh/graph-keys”, which you can find at https://github.com/dwebprotocol/dmesh-keys. The “dmesh-keys” library is used for generating and parsing graph keys.
It’s important to remember that data added to the DHT can be either immutable or mutable. Mutable data must be signed by a private key and only that private key holder can add a new sequence to the already existing key. So in other words, lets say I love a post that I no longer love, I could “unlove” that post. By unloving the post, I would make a mutation to the “/jared/loves/postid” and “postid/loves/jared” edges, by simply adding a value to them that says “deleted” or by simply removing the mutable entry altogether. This way, when traversing through this data, we can easily separate “deleted” loves, from “active” loves (that simply have a “null” value). This is just one way of doing things. You may be wondering how in the world one DHT can be used to validate the data in another (like which users are posting what or whether post data is compliant with the DHT’s data physics). Believe it or not, one DHT can be used as a database of users, where their usernames are keys, and the value is an object of permission levels and their matching public keys like so:
```
{
owner: <key>,
active: <key>
}
```
We call these “Authenticator DHTs”. This way, when a user creates a mutable entry on one DHT, you can ensure that the key they’re signing the entry with, matches the key for a particular user’s permission level on an Authenticator DHT (if your entry key uses usernames [jared/loves/500]), or the username within the value object (if the value object uses a username). That brings me to our next few posts, involving DHT-based validation, authenticator DHTs and DHT bridges — all of which we’re debuting over the next few days as well. I’ll see you there.
===========
WHAT’S NEXT?
We’re going to break down DHT-based validation, Authenticator DHTs and DHT bridges
===========
