preface

This article mainly explains some knowledge points, mostly from Wikipedia and previous summaries.

Turing complete

Turing machine

The first way to understand Turing completeness is to understand Turing machines. The following explanation is taken from Wikipedia:

Turing Machine (English: Turing Machine), also known as the definitive Turing machine, is an abstract computing model proposed by British mathematician Alan Turing in 1936. It can be regarded as a mathematical logic machine, which is equivalent to any finite logical mathematical process.

Alan’s basic idea was to use a machine to simulate the mathematical operations carried out by humans with pen and paper, which he described as two simple motions:

  • To write or erase a symbol on paper;
  • To move attention from one position on the paper to another;

At each stage, the person decides what to do next, depending on (a) the symbol on the page that the person is currently focusing on and (b) the current state of the person’s mind.

In order to simulate this process, Alan constructed an imaginary machine consisting of the following parts:

  1. An infinite length of paper TAPE. The tape was divided into a series of small cells, each containing a symbol from a finite alphabet with a special symbol (blank) for the blank. The squares on the tape are numbered, from left to right, 0, 1, 2… The right end of the tape can be extended indefinitely.
  2. A read-write HEAD HEAD. The read-write head can move left and right on the tape, it can read the symbol on the current pointing grid, and can change the symbol on the current grid.
  3. A set of control rules TABLE. It determines the next action of the read/write head according to the current state of the machine and the symbol on the grid indicated by the current read/write head, and changes the value of the status register to make the machine enter a new state, and tells the Turing machine commands in the following order:
    1. Write (replace) or erase the current symbol;
    2. Move HEAD, ‘L’ to the left, ‘R’ to the right, or ‘N’ not to move;
    3. Keep the current state or go to another state
  4. A status register. It is used to save the current state of the Turing machine. The number of possible states of a Turing machine is finite, and there is a special state called the down state.

What is Turing complete

A simple way to determine Turing completeness is to see if the language can simulate a Turing machine. In short, it means that any computable problem can be computed, which is called Turing complete.

Turing completeness is the concept of a set of rules for manipulating data. Data manipulation rules can be a programming language or a set of instructions implemented in a computer. When a set of rules can perform all the functions of a Turing machine model, it is said to be Turing complete.

Common reasons for Turing’s incomplete language were loops or recursion limitations (inability to write programs that do not terminate, such as while(true){};). , cannot implement data structures such as arrays or lists (cannot simulate paper tape). This will enable a limited number of programs to be written.

BTC and ETH

The core difference between the two is that ETH scripts are Turing-complete, while BTC scripts are not. The Bitcoin scripting language is not Turing-complete and has certain limitations. It does not have loop statements or complex conditional control statements. Because of this limitation, there is no way to use the language to write infinite loops or malicious code that can lead to DOS attacks, thus avoiding DOS attacks on the Bitcoin network. At each full node, the transaction is validated. This limited scripting language prevents the authentication mechanism from being seen as a flaw in an attack on the Bitcoin network.

As a result, BTC can only meet simple financial contracts, such as establishing tokens, establishing multi-signature wallets, etc. ETH, on the other hand, is Turing-complete and can theoretically be used to write anything modern computer languages can, making it a good foundation for decentralized applications and smart contracts.

Consensus algorithm

POW: Proof of Work.

Bitcoin uses POW mechanism during Block generation. A compliant Block Hash consists of N leading zeros, and the number of zeros depends on the difficulty value of the network. Getting a reasonable Block Hash requires a lot of trial and error, depending on the speed of the machine. When a node provides a reasonable Block Hash value, it indicates that the node has been evaluated with a large number of attempts. Of course, the absolute value of the number of attempts cannot be obtained because finding a reasonable Hash is a probabilistic event. When a node has n% of the network computing power, the node has an N /100 probability of finding the Block Hash.

For example, getting this hash that makes sense is like rolling a die, where there are no faces on the die, and then everyone is rolling the die like crazy, and when you roll less than a certain number, you win. And the dice roll is a probabilistic event, so it’s all about who gets the most rolls and who gets the most. So if you had 100 flips per unit of time, and you had n flips, the probability of you getting any of them would be n over 100.

POS: Proof of Stake

POS: Also known as certificate of ownership, similar to property stored in a bank, this model assigns you interest based on how much digital currency you hold and for how long. In simple terms, is a hold the amount of money and time, according to you send you the interest of a system, under the mode of equity that POS, a noun, called currency age, produce 1 dollar a day per dollar of age, for example, if you hold 100 COINS, held a total of 30 days, then your money at this time of age is 3000, this time, if you found a POS blocks, Your coin age will be cleared to 0. Every time you are emptied of 365 coins, you will receive interest of 0.05 coins from the block (assuming the interest can be understood as 5% annual interest rate), so in this case, the interest = 3000 * 5% / 365 = 0.41 coins, which is interesting, holding coins has interest.

DPOS: Delegated Proof of Stake

Bits of DPoS mechanism, mechanism of Chinese name is called authorized shares (also known as the trustee mechanism), its principle is to make every bit shares vote, the resulting 101 representatives, we can be understood as 101 super node or mineral pools, and that 101 super node right is completely equal to each other. In a way, DPOS is like a parliamentary system or a people’s Congress system. If representatives fail to perform their duties (fail to generate blocks when their turn comes), they are removed and the network elects new supernodes to replace them. The emergence of DPOS is mainly due to the emergence of mining machines, with a large amount of computing power on people who do not know or care about Bitcoin. It is similar to the scalpers of concerts who hoard tickets in large quantities and do not care about the content of concerts.

Byzantine fault tolerance

The Byzantine Generals Problem, proposed by Leslie Lambert in his thesis of the same name, is a fault tolerance Problem for distributed peer-to-peer network communication.

In distributed computing, different computers exchange information through communication and agree to act on the same set of cooperative strategies. However, sometimes, the member computers in the system may make mistakes and send wrong information, and the communication network used to transmit information may also lead to information damage, so that different members of the network reach different conclusions about the strategy of overall cooperation, thus destroying the consistency of the system. The Byzantine general problem is considered to be one of the most difficult types of fault tolerance problems.

The Byzantine general asked the story as follows:

A group of Byzantine generals led a separate army to besiege a city. To simplify matters, the operational strategy of each army was limited to attack or withdrawal. Because a partial attack and a partial withdrawal could be disastrous, the generals had to vote to agree on a strategy of all attacking together or all withdrawing together. Since the generals were on different sides of the city, they could only communicate with each other by Courier. During the voting process, each general sends his or her vote for attack or retreat to all the other generals by Courier, so that each general can decide on a strategy based on his or her vote and the information sent by all the other generals.

The problem with the system is that there may be defectors among the generals, who may not only vote for the worse strategies, but may also selectively send voting messages. Let’s say nine generals vote, and one of them is a traitor. Out of eight loyal generals, four voted for the attack and four voted for withdrawal. At this point, the traitor may deliberately send letters to the four generals who voted for the attack to vote for the attack, while sending letters to the four generals who voted for the withdrawal to vote for the withdrawal. So from the point of view of the four generals who voted for the attack, the result of the vote was that five voted for the attack, and the attack was made; In the opinion of four generals who voted to leave, five voted to leave. Thus the unity of the armies was destroyed.

Since generals need to communicate with each other by Courier, defecting generals may send fake votes by forging letters and posing as other generals. Even if the loyalty of all the generals is guaranteed, the messengers can be intercepted or even replaced by enemy spies. Therefore, it is difficult to solve the problem by ensuring the reliability of personnel and communication.

Byzantine fault-tolerance is said to have been achieved so long as loyal (or error-free) generals can still decide their strategy by majority decision. Here, the ticket will have a default value, which will be used to vote if the message (the ticket) has not been received.

When the above story is mapped into a computer system, the general becomes a computer, and the messenger becomes a communication system. Although the above problems involve electronic decision support and information security, they can not be solved simply by cryptography and digital signature. Because abnormal voltages can still affect the entire encryption process, this is not a problem that cryptography and digital signature algorithms are addressing. It is therefore possible for the computer to submit the wrong result, or to make the wrong decision.

Blockchain wants to solve this problem, but it does not solve the Byzantine problem in a real sense. It only uses techniques such as cryptography and POW consensus to converge to a consensus according to probability under the condition that each participant is rational enough to maximize his own interests and has less than 50% of the computing power. If someone wants to send the wrong message, they need to master more than 50 percent of their computing power, which is likely to outweigh the gains.

For example, the general who defected needs to pledge one million taels of gold to other generals before they can trust you. However, if you succeed in defecting, you can only get 800,000 taels of gold. Even if you succeed in defecting, you also need to lose 200,000 taels of gold. Of course, it does not exclude people who do not want to benefit, just want to play with the situation, so the blockchain mechanism in BTC is just based on economics to solve a Byzantine general problem.

reference

What is Turing complete

Consensus algorithm