An in-depth review of blockchain — cryptography and metaverse (part five- concurrency-part five)

A specialized and analytical article for programmers and blockchain and web3 experts #blockchain #concurrency #metaverse #metaverse #cryptography #cryptocurrency #metamondial

In the previous articles, I provided detailed explanations about concurrency, and in this article, I will discuss more about the commonalities of concurrency and blockchain, and at the end of the article; The topics related to the competition are finished.

Dining philosophers problem

In computer science, the problem of philosophers at the dinner table is an allegorical problem related to the design of algorithmic parallelism, usually used to illustrate concurrency problems and techniques and their solution. This problem was originally developed by Mr. Dykstra in 1965 as a student exam exercise and presented in relation to computers competing for access to tape drive peripherals.

Five silent philosophers sit around a table. There are bowls of noodles on the table. Forks are placed between each pair of philosophers placed side by side. Every philosopher must take turns thinking and eating. However, a philosopher can only eat noodles if he has both a left and a right fork. Each fork can only be used by one philosopher at any given time, and therefore a philosopher can only use a fork if the fork is not being used by another philosopher. After a philosopher has finished eating, he must place both forks on the table for the others to use. A philosopher can only take his right fork or his left fork, if available, and cannot begin eating until he has taken both forks. The amount consumed has nothing to do with the remaining volume of the noodles or the space in people’s stomachs; In other words, it is assumed that the amount of noodles is unlimited and the amount of food is also unlimited. The problem is how to design an order of behavior (convergence algorithm) in such a way that no philosopher goes hungry; This means that everyone can eat and think indefinitely. Provided, of course, that no philosopher knows when other philosophers plan to eat or think.

This problem was designed to demonstrate the challenges of preventing deadlocks. A deadlock is a state of the system where no progress is possible. To see that solving this problem is not that simple, suppose that every philosopher should behave according to the following instructions:

• Think until the left fork is available. Then, when the left fork is available, pick it up;
• Think until the right fork is available. And if it’s available, take it;
• If you get both forks, eat for a set amount of time;
• Then place the right fork on the table;
• and then put the left fork on the table;
• Start over again.

This tempting solution will fail because it allows the system to get stuck in an impasse where no progress is possible. This situation occurs when every philosopher has removed the left fork and is waiting for the right fork to become available. With the instructions given above, this situation will likely occur, and when it does, each philosopher must wait for the other philosopher on the right to release a fork.

A resource shortage can also occur independently of deadlocks if a particular philosopher is unable to get both forks due to a scheduling issue. For example, there might be a rule that after waiting 10 minutes for another fork to be available, philosophers put the fork they have on the table, wait another 10 minutes, and then try again. This protocol eliminates the possibility of a deadlock because the system can transition to another state at any time. But there is still the live lock issue. If all 5 philosophers enter the dining room at exactly the same moment and each of them picks up their left fork at the same moment, the philosophers wait 10 minutes and then all put their forks on the table at the same time. and then 10 They wait another minute and again everyone picks up their forks.

Mutual exclusivity is the basic idea of the problem. In fact, philosophers at the dinner table offer a general, abstract, practical scenario for describing such problems. The problems these philosophers face are similar to those encountered in real computer programming (when multiple programs require exclusive access to shared resources). These problems are discussed in concurrent programming. This problem originally related to external devices such as tape drives. However, the problems simulated by the problem of philosophers at the dinner table are much more likely to occur when multiple processes are accessing the data to be updated. Complex systems like operating system kernels use thousands of locks and synchronizations that require strict adherence to procedures and protocols to avoid problems like deadlocks, starvation, and data corruption.

What is interesting is that the first solution that came to the mind of Bitcoin’s creator or creators is to pause for 10 minutes for the block to form, it is not wrong to generalize the blockchain structure with the concurrency structure, the basic idea is the same, to solve the above problem, there are many solutions that do not fit the scope of this article, but my aim is that solving problems should be scientific and thorough, you probably now understand why the network has to wait a certain amount of time to mine each bitcoin, but do you really have to wait long? Wasn’t there another way to avoid wasting time and increase speed?

In the following paragraphs you will see that the method of hashing information is not strictly necessary for security and that there are better encryption methods or ways to prevent 51% attacks that do not necessarily depend on the strength of the network, can there be a method that doesn’t require an interrupt? The answer is definitely yes, I will explain further.

What is consensus?

You’ve probably heard that Bitcoin uses the consensus protocol.

origin of the designation

The adjective Byzantine refers to the problem of the Byzantine generals. When besieging a city, several generals have a communication problem. Because of the strong fortifications, the generals and their troops had to attack the city from different directions at the same time. The generals can communicate with each other via messengers. However, some of the generals scheme against others. Their goal is to bring their competitors into disrepute — for example, by trying to drive the others to an early attack by cleverly spreading misinformation. None of the generals now know what information is authentic and who they can trust.

So there is a problem of agreement, which is that the generals must decide unanimously whether to attack or not. The problem is complicated by the spatial separation of the commanders; so they have to send messengers back and forth. There is also the possibility that there may be traitors among the generals who can intentionally send misleading information to the other generals.

Mathematically, it was shown that under these conditions, the loyal generals only have a chance of reaching an agreement if the proportion of schemers is less than a third. As a result, there was no solution for three generals in particular, one of whom is a schemer — at least not with the help of classic communication methods such as messengers.

Methods for solving the problem of Byzantine generals:

• Practical Byzantine Fault Tolerance (PBFT)
• Federated Byzantine Agreement (FBA)
• Delegated Byzantine Fault Tolerance (DBFT)
• Practical Byzantine fault tolerance

Practical Byzantine Fault Tolerance (PBFT) is one of the first solutions to the Byzantine generals problem. The PBFT model works by providing a worksharing mechanism that accepts malicious nodes. This algorithm was designed to work in asynchronous systems.

PBFT works under the following assumptions:

The distributed system is asynchronous: the network cannot send, delay or duplicate messages.

Bad nodes can behave randomly, A strong adversary can coordinate faulty nodes, delaying communications, or delaying correct nodes to inflict maximum damage to the service.

The nodes in a PBFT network, called replicas, consist of a main node, called the leader, and the rest are supporting nodes. All nodes continuously communicate with each other and try to reach a state of consensus. For a message, in order to send t out, each node must prove that the message was received by a particular peer node using public key signing and message integrity using message authentication codes (MAC).

Nun, jetzt richten wir unseren Blick von der Concurrency auf die Untersuchung von Blockchain und Netzwerk.

Als erste Kryptowährung, die über ein dezentrales Netzwerk verfügt, verwendet Bitcoin einen Proof-of-Work-Algorithmus, um einen Konsens zu erreichen. Dieser Algorithmus ist nicht sehr optimal und erfordert viel Rechenleistung, weshalb Blockchain-Experten seit Jahren versuchen, bessere Alternativen bereitzustellen. Derzeit gibt es neben PoW mehrere Konsensalgorithmen, der bekannteste und am weitesten verbreitete ist Proof of Stake (PoS). Cardano nutzt es als wichtigsten Konkurrenten von Ethereum. Ethereum-Entwickler planen und stellen seit zwei Jahren eine Plattform für die Migration von PoW zu PoS bereit. Über diese beiden werden wir im Folgenden mehr erfahren.

Der Proof of Work (PoW)-Algorithmus ist der Pionier der Blockchain-Konsensalgorithmen. Dieser Algorithmus wurde zuerst in Bitcoin implementiert, aber sein Konzept gibt es schon lange. In diesem Konsensalgorithmus hashen Validatoren (Miner genannt) die Daten, die sie hinzufügen möchten (Blöcke mit Transaktionen), bis sie eine geeignete Lösung finden, die vom Protokoll akzeptiert wird.

Ein Hash ist eine scheinbar zufällige Folge von Buchstaben und Zahlen, die generiert wird, wenn Sie Daten durch eine Hash-Funktion laufen lassen. Wenn Sie die gleichen Daten noch einmal durch die gleiche Hash-Funktion laufen lassen, erhalten Sie immer die gleiche Ausgabe. Eine sehr geringfügige Änderung führt jedoch zu einem völlig anderen Hash.

You probably can’t tell what information went into the function by looking at the output. In other words, the input cannot be recognized by the output of the consensus algorithm’s hash function. Because of this, they are useful for proving that you already knew the contents of a record. You can pass the hash to someone, and if you later disclose the data, that person can pass the data to the function and ensure that the output is the same.

In the proof-of-work consensus algorithm, the protocol determines the conditions under which a block is counted as valid. For example, the protocol can declare that only a block whose hash starts with 00 is valid. The only way for a miner to create a block that matches the desired log composition is through brute force input; They can produce different outputs by changing a parameter in the data (block) until they arrive at the correct hash. This work continues until an acceptable result is achieved. Because of this, there is competition between miners on the Bitcoin network or other blockchains based on the Proof-of-Work consensus algorithm; Any node that gets the response first wins the reward.

With large blockchains, the competitive pressure is incredibly high. In order to compete with other miners, you need a warehouse full of special hashing hardware (ASIC miner device) to have a chance to create a valid block. In other words, the computational power required to find suitable hashes (due to the protocol’s tightening of conditions) has increased in his consensus algorithm to the point that it can no longer be validated using desktop computers and home laptops and we need specialized devices for this task, i.e. ESS miners.

When mining, your stakes (which you promise the network to guarantee honest behavior) are the cost of these devices and the electricity required to run them. ASICs are built for only one purpose, which is to process digital currency transactions, and have no use outside of the cryptocurrency world. The only way to return the initial capital is through the mining itself. If you manage to add a new block to the blockchain, you will receive a sizable reward.

Confirming whether you actually created a valid block is natural for the network. Even if you’ve tried trillions of combinations to get the right hash, you only need to run your data through the function once. If your data produces a valid hash, the network accepts it and the reward is paid out. Otherwise, it will be rejected by the network and you’ve wasted your time and power.

Epilogue:

So far I have delved deeply into parallelism in the computing world and in the context of blockchain and cryptocurrency

At Metamondial, we have concluded that using blockchain falls short of our main goal of speed, decentralization, and security.

That’s why we went on the Hashgraph platform when developing our network, but completely different from Hedera, which I will discuss in more detail in the next few articles.

Continued in the next article