Spreadable - a decentralized network option

Why do we need to decentralize at all? Many people do not quite understand the point, because everything seems to work well without that. There are actually several reasons, but usually the proponents of the approach only touch on complex technical issues, and it becomes difficult to see the essence. For me, for example, everything is quite simple.

Let’s say you started a cool project. With development, it will begin to require more and more computer resources. The problem is that the average person is very limited in funds. But if other people are interested in your idea, then they can independently launch their servers, change and add new functionality, expand capabilities, etc. At the same time, the costs are not so significant for an individual. They are distributed among all, and the total profit for each is summarized. This enables ordinary people to create complex solutions.

In fact, this is an alternative to the current dominant option when you need to look for investors who are going to foot the bill. But in this case, you often have to close the project from the outside world and completely depend on these people, put up with any decisions because it is “good for business”, etc. At some point you may even be an extra element and they will say goodbye to you.

If an idea can be effectively implemented in a decentralized way, it is best to do so. When the critical mass reaches this point, there will be many standardized and convenient mechanisms for implementing higher-level solutions. In the meantime, let’s look at one simple algorithm for creating a decentralized network - spreadable.

Option number one: single-level

Nodes can perform two roles: master and slave (M and S). Roles are assigned randomly and can be changed at any time. In other words, no node has a real advantage over the other. The role M is needed for maintaining lists of S in order to unite all in a single network for receiving and sending information in the future. The number of M always tends to the square root of the network size: if the network has 9 nodes, then M will be 3 pieces. Each M keeps its own list of S. The number of S in one such list also always tends to the square root. As a result, with 9 nodes we have 3 M and each has 3 S in its list. Information about which nodes play the role of M is transmitted and stored at all nodes in synchronization mode.

The network is crawled as follows:

• The client wants to perform an action.
• A coordinator is selected for it — a random node that will start the entire process.
• The coordinator, like any node, has a list of all M’s, so it makes a request to the client for all these nodes in parallel.
• Each M makes the necessary request to all S in its list, also in parallel.
• As a result, all the necessary information is collected, filtered and returned to the client.

Let’s calculate how much time it takes. Consider the ideal option. Let’s assume the average time per request is 50ms. Then we get a total time of 3 * 50 = 150 ms, regardless of the network size.

In reality, each node can respond at different speeds or even hang. Therefore, a timeout mechanism has been implemented that allows you to control the acceptable deviations at each stage.

Pluses of this algorithm:

• Easy to implement
• Very fast network traversal with a large number of nodes
• High resistance to connecting / disconnecting nodes and roles changing
• Acceptable amount of work to prevent Sybil attacks
• Maximum proximity to p2p despite hybridity

Minuses:

• The ability to effectively make parallel requests is limited by the OS and server resources.
• The larger the list of each master, the longer data processing takes.

These cons limit the maximum network size. According to my estimates, 10,000–100,000 nodes are the limit of effective work. Such a number of nodes is enough to solve most problems, so I have focused on this algorithm for now.

Option number two: multi-level

This algorithm is almost the same, only the nesting levels of the lists becomes an infinite amount. The size of the node list is optional, not the square root. Take the number 2 for further examples. The role of the masters becomes hierarchical. There are masters of the first level, the second, and so on. (M1, M2 …). M3 have M2 lists, M2 -> M1, M1 -> S.

In this scheme, we initially have one level. As soon as there are more nodes than 4 a new level and the first M2 will appear, when there are more nodes than 6 a third level and M3 will appear, after 12 nodes we get level four and so on.

The network traversal mechanism is similar to the first algorithm, but the chain becomes longer depending on the selected list size and the number of nodes. So with each new level we get a delay in the client result for only one average request.

Pluses of this algorithm:

• Infinite scalability
• Fast network traversal with a huge number of nodes
• Maximum proximity to p2p despite hybridity

Minuses:

• Difficult to implement
• A large amount of work to prevent Sybil attacks

Security

Decentralized networks are more or less vulnerable to various Sybil attacks. This is when a node or several nodes belong to an attacker who modifies the code in such a way as to compromise the entire network in some way. The more open the network, the more bottlenecks there are for impact. Offhand, some of the most obvious ways to do harm:

• Giving the client incorrect data from your node.
• Spam the database to increase the processing time.
• Make all host routes hanging, causing constant timeouts and slowing down the time it takes to make requests.
• If the network has some kind of voting system, you can try to gain a critical mass of nodes and influence decisions.
• Find bottlenecks in the list management system and change the code, causing disruptions and delays in syncing nodes with each other.

A decentralized network is very similar to a human society. Imagine that each node is a separate person. We need to do everything so that, despite the harmful people, the system as a whole works normally. During the creation of all this, I went through a million times in my head different node behaviors and ways to balance it all. This task is extremely difficult, because there are too many options. As a result, all this came down to a certain system of control over the behavior of nodes. Each node has clear tasks that it must perform. There are especially many tasks in the master role. If a node does something wrong, then others who communicate with it will notice these violations. If it behaves correctly then the marks are removed. Something like karma or weights. When there are too many violations the node gets banned. All parameters are optional and there are different responses to different violations.

Voting

It would be useful in some cases to allow the client to perform certain actions only under certain conditions. For example, pass the captcha first or confirm the ip address or anything else. How can you implement this in a decentralized network? One option is to vote. Before the user can do anything, a certain part of the nodes must confirm that the client has the right to do so. This is managed using a special service approval. Out of the box, there are already classes for checking captcha and ip addresses. For custom checks, we need to inherit from the base class and change some methods.

When creating a class, we can pass some basic options:

• approversCount — a number of nodes from all available ones that will vote. By default, this is the square root of the network size, but you can specify a percentage of the size or just a number.
• decisionLevel — a sufficient number of votes for a positive decision. By default, 66.6%. You can specify just a number.
• period — a period of time for which the current list of voters will be formed. By default, 5 minutes.

The decisionLevel option is necessary because nodes can be connected and disconnected at any time. And if one of the voting nodes leaves the network during the decision-making process, the client will receive a refusal. Therefore, we allow some deviation here.

Let’s look at how nodes are selected for voting. A hash is calculated for each node based on its unique data and time period. Let’s say, approversCount=3, decisionLevel=2, period=10m for some action. All received hashes are sorted and the first 3 nodes in the array are allowed to vote within a ten-minute period. As soon as the next ten minutes come, the node hashes will change and some other array of nodes will become voting.

Next, the client must first send some information about itself to the voters via the coordinator before performing the target action. They save this data and give it their requirements (captcha, for example). The user fulfills these requirements and sends additional proofs during the required request, which will be checked by the voting nodes for truth. If at least 2 nodes out of 3 confirm the response, the client gets the result that it needed.

Based on the settings in the example, in order to “hack the algorithm”, you need to have control over 2 nodes, calculate when exactly these nodes will become simultaneously voting (with a slight improvement in the algorithm, you can remove the possibility of calculating in advance), rewrite a bunch of code and then for a ten-minute period once in N time, you can make requests without checks.

But you can specify the number of voting nodes yourself. It can be hundreds or more if necessary, which significantly reduces the probability of control.

Captcha here is implemented in the way described above.

Synchronization

In order to normalize the status of the network synchronization is used. After a certain period of time, a function is launched in which all the necessary checks and settings occur, as well as registering a node in the network and deleting outdated information. The synchronization periods are the same for everyone. To register a node you need a conductor. This is any other node that is already registered in the network. It is specified as an option. The conductor for the very first node is itself. The node where the network starts is called the root node. If the version of your node differs from the root version, it will not be synced and will not become part of the network.

Library

Everything is written in nodejs. Let’s look at an example of usage:

Server:

const Node = require('spreadable').Node;

(async () => {  
  try {
    const node = new Node({
      port: 4000,
      hostname: 'localhost',
      initialNetworkAddress: 'localhost:4000'    
    });
    await node.init();
  }
  catch(err) {
    console.error(err.stack);
    process.exit(1);
  }
})();

Client:

const Client = require('spreadable').Client;

(async () => {  
  try {
    const client = new Client({
      address: 'localhost:4000'
    });
    await client.init();
  }
  catch(err) {
    console.error(err.stack);
    process.exit(1);
  }
})();

To run the node we work with the Node class. To connect and work with the network we use the Client class.

Some features:

• The network works through the http protocol. You can also configure https.
• To start the node, you must at least specify the port (port) and the entry point (initialNetworkAddress). You can also manually pass the hostname (hostname).
• The node ID is the address. It is formed as a host:port. The host can be a domain name or IP address. For ipv6 it is [ip]:port.
• The network can be either open or closed. To close it, you can use basic authentication or overwrite the request filtering methods.
• The client is isomorphic, and you can work from the browser.
• You can work with the node from the command line.

For more information, see there.

What is not yet available

Now, in order to use the mechanism and add something of your own, you need to understand in detail how it works inside, inherit all the necessary classes, expand the routes, etc. On the one hand, this allows you to implement anything, but on the other hand, it takes a lot of time to delve into. Therefore, in the future I’m thinking of adding the ability to work with the network in the style of events (EventEmitter). This will limit some possibilities, but will simplify the work as a whole.

At the moment, you can see how to inherit everything using the example of existing extensions: metastocle, storacle, museria.

My contacts:

• @ortex
• mywebstreet@gmail.com