Blockchain Note – Consensus Algorithms

General Blockchain consensus algorithms:
  • PoW:Proof of Work
  • PoS:Proof of Stake
  • DPoS:Delegated Proof of Stake
  • PBFT:Practical Byzantine Fault Tolerance
  • PoSpace/PoC:Proof-of-space/Proof-of-Capacity
  • PoA:Proof of activity
  • PoB:Proof of burn
  • PoET:Proof of elapsed time
  • Casper:Ethereum new consensus algorithm
Typical-consensus-algorithms-comparison

Figure 1 Consensus Algorithms

  1. POW (Proof-of-Work)

It is an economic response to service or resource abuse or to block service attacks. Generally, users are required to perform some complicated and time-consuming complex calculations, and the answers can be quickly checked by the service provider, so that the time, equipment and energy consumed are used as guarantee costs to ensure that services and resources are used by real needs. The principle of PoW is that each node competes for the right to write in the current block by solving the problem. The fastest answer is to release the answer and other selected transaction content (that is, the current block content) to other nodes. Node verification, if other nodes verify that the block content is correct and agree that he is the earliest solver, then join the chain and store the contents of the block, and use this block content as a basis to start solving the next topic.

The advantages of POW are:
(1) For the safest public-chain consensus mechanism, Bitcoin uses this consensus algorithm
(2) The mechanism is simpler and easier to implement
(3) Relatively fair mining mechanism (that is, the generation and distribution of cryptocurrency)

The disadvantages of POW are:
(1) Consumption of a large amount of energy is calculated at the expense of energy consumption. For example, mining of mining machines now requires huge amounts of electricity.
(2) The confirmation time of the block is hard to shorten, and the bitcoin network congestion problem is getting worse.
(3) There may be a fork and you need to wait for multiple confirmations to complete the transaction.
(4) Based on (3), in theory we can say that POW has no finality, because longer chains may always appear to replace the current book, but in fact the probability of six is ​​close to 0 after confirmation.
The digital currency using the POW consensus algorithm stands for BTC, LTC, ETH, etc.

  1. POS (Proof of Stake)

First, there are no miners, only trade verifiers.
The miners in the POW have to do three things: verify the transaction, package the transaction, and count the random number, while the certifier in the POS only does the verification transaction.
Second, only the holder of the currency can verify the transaction.
One coin is one ballot. Everyone chooses the block that they think is correct, so people who don’t hold the money have no influence on the system account.

We can see two major advantages of POS:
First, the block is faster. Because the whole network does not have to work hard to calculate random numbers, only focus on verifying accounts, so POS is much faster than POW.
Second, exclude interference from unrelated stakeholders (non-shareholders) on accounting. Overall, the interests of the participating bookkeepers are the same, and everyone is maintaining the security of the entire system for their own benefit.

If I vote for a fake block made by a malicious node, I try to wind up the blocks to erase the transactions I pay to others. Once such a double payment occurs, what kind of punishment will I receive?
The answer is no punishment, this is the place where ordinary POS can’t get up, ie: Nothing at Stake.

ETH:
It can run automatically and exchange value, so naturally there is the concept of DAC Decentralized Autonomous Corporation – it is hard to imagine that in the future, a few pages of code will be a company that can perform all the tasks you can think of.

Nothing at Stake Issue -> Casper
Casper asked the verifier to charge at least 1,000 Ethereums, considering that each Ethereum is now worth $1,000, which means that the initial amount of the verification transaction has exceeded $1 million, and few people are willing to use this money as a joke. It is safer than normal POS.

Casper itself is a smart contract that doesn’t care how much margin or power is imposed by a malicious verifier. Once the evidence is malicious, it immediately strips the verifier’s chips. For the correct verifier, a normal reward will be given according to the POS algorithm.

The advantage of Casper’s POS over POW is that it reduces the scale advantage. There are a lot of calculations or a lot of coins. It used to be a very good thing, but after Casper came out, this advantage would be completely eliminated. It’s nothing to have money and resources, and it’s right. Because once you bully the system, Casper will sweep the bets on their desktops. Compared to Bitcoin, Ethereum after the implementation of POS is more decentralized.

POS is the more stencils that have more cryptocurrency (equity), the easier it is to get the right to write in the current block. It is different from POW and does not require a lot of computational power because there is no need to compete. The original version of POS produced all the currency in the early days of the creation, meaning that the new block does not give birth to new currency, so the performer verifier is not called a miner, but is still called a blacksmith, but they still get it. Transaction fee is used as a reward. Later versions of POS also had the design of block mining rewards, especially if the POS was to be applied to the public chain.
And how does POS specifically select the current block writer? If you always choose the highest equity, the member with the most currency will always have exclusive write rights, so the following two methods are usually implemented:
(1) The method of randomization
Generate random random numbers, and use random numbers to match the specific formula to select the writer. Only the high-income people still have a higher probability of being selected.
(2) Method of selection based on currency age

If you assume that everyone at DPOS is giving yourself, DPOS is actually a POS, and POS is subject to no interest. If everyone is voting for a person, then this is the centralization system.

The advantages of POS are:
(1) No competition, so low energy consumption
(2) Members of the competition write right must have money, so they prefer to guard the system to avoid evaporation of the currency compared to destruction.
(3) Compared to POW, the same size hardware budget can protect more chain assets

The disadvantages of POS are:
(1) A member who has an interest may not wish to participate in accounting
(2) If the bad guy who gets the right to write rewrites another fake chain, it only takes a small amount of computing power, which may lead to a successful double spending attack.
(3) The cost of doing bad things is very low, there is no penalty mechanism
(4) Based on (2) and (3) above, the implementation of POS needs to be combined with other mechanisms to improve this situation, and therefore more complicated than POW.
Digital currency using the POS consensus algorithm, which stands for BLK, QTUM, etc.

  1. DPOS (Delegated Proof of Stake)

The POW algorithm allows all the computing power to compete and guess the random number. The first guessed good luck person is qualified to produce the block, and the whole network node is the verifier.

In the POS algorithm, the nodes in the whole network are producers, and the holders (share holders) are responsible for verification. For example, in the future Ethereum: there is no miner, only the verifier, verify that the reward is correct, and the verification error is forfeited.

First, randomly specify the order in which the producers appear;
Second, blocks that are not produced in order are invalid;
Third, shuffle every one cycle, disrupting the original order;

Under DPOS, the work done by the producers is a bit like the bitcoin mining pool. The difference is that the producers no longer have to spend any energy to find
Random numbers, only put all the energy into the production of the correct block.
We know through the articles in the first season: the work of finding random numbers is very laborious, very slow, DPOS does not find random numbers, only
Verify the transaction, and the verification work is extremely simple. Therefore, the speed of the DPOS is like the flying power over the gap.

POW-based bitcoin processes 7 transactions per second;
Ethereum based on POW and POS handles 15 transactions per second;
Bitmap stocks (BTS) based on DPOS can handle more than 100,000 transactions per second.

Once the block is produced, it does not mean that the block will be accepted, it still needs to be verified, so the DPOS algorithm is
There are a lot of validators in the system, and production is only a prerequisite for the block. This block is valid only when everyone else agrees.

Incentive: Nothing to do, nothing to do, nothing at Stake

Without incentives, it seems that the block results are not credible, because the selected producers may not be too lazy to produce, but the holders (the holders, that is, those who have voting rights in the network) will not be too lazy to vote. Will drive those bad nodes out of the network, leaving only those honest nodes.
No network will survive because of its internal power, but only because it creates external value. Suffixed power holders will only make the entire network value lower and lower until it disappears.

Therefore, in order to lead the network to create external value, the holders will never stand by and watch any malicious, and must choose a reliable node production block. This is the only option because the interests of everyone in the network are tied together.

From the point of view of the block producers, there is no such thing as a world report (economic punishment on the spot), but it loses the most important wealth and is the only asset in the future network: credibility.

The node does evil to at least satisfy this condition:
First, hold the currency, otherwise there is no voting rights;
Second, ensure that the current gains of doing evil exceed the sum of the benefits of good deeds. But how is this possible?

One of the shortcomings of POS is that members who have rights do not necessarily want to participate in billing, and DPOS can solve this problem. Similar to the democratic representative system, it first selects the billing participant (verification node) through the equity certificate, and then through The operational mechanism allows these verification nodes to compete for block writes. At the same time, due to the significant reduction in the number of verification nodes, a consensus can be quickly reached.

In addition to the advantages of POS, DPOS has:
(1) Reducing the number of participating verification nodes and greatly increasing the speed of consensus, which is one of the key reasons why EOS can support high concurrent applications.
The disadvantages of DPOS are:
(1) Must rely on cryptocurrency, but in many cases in the current league chain there is no cryptocurrency
(2) Excluding Casper, most DPOS still have no block finality.
The digital currency using the DPOS consensus algorithm stands for BTS, EOS, etc.

  1. BFT (Byzantine Fault Tolerant)

Widely used in: Hyperleder, Stellar, Dispatch, and Ripple
Advantages: high throughput; low consumption; scalable
Disadvantages: Half trust (1⁄2 node is reliable)

This is a classic distributed computing problem, usually explained by the Byzantine failure. The problem describes the contents of several Byzantine generals and their troops, and the beleaguered cities. They must unanimously decide whether to attack. If the generals attacked separately, their siege of the city would end in failure. The generals were separated by distance and had to use messages to communicate. Some cryptocurrency protocols use different versions of BFT to reach consensus, each with its own advantages and disadvantages.

Practical Byzantine Fault Tolerant Algorithm (PBFT): One of the priority solutions is called the Practical Byzantine Fault Tolerant Algorithm. The Hyper ledger Fabric is currently in use, with very few (<20, and possibly a little more) pre-selected generals performing PBFT and showing incredibly efficient. Advantages: high transaction throughput; disadvantages: centralized / licensed.

Federal Byzantine Agreement (FBA): FBA is another solution for Byzantine generals that has been used in both Stellar and Ripple currencies. The overall idea (heh, translator’s note: author’s original heh, may want to express puns, the general’s idea), is that each general is responsible for his own chain, according to the receipt of the truth to arrange the message. In Ripple, the generals (output verification nodes) are pre-selected by the Ripple Foundation. In Stellar, anyone can be a verifier, so you can choose the verifier you want to trust.

  1. PBFT (Practical Byzantine Fault Tolerance)

“Byzantine fault tolerance” refers to the “wrong” in the distributed system, while at the same time achieving the correct consensus.
We are already familiar with the classic Byzantine fault-tolerant solution: the POW algorithm – use the workload proof to find random numbers.

PBFT just dispels the traditional scheme is not practical, so add a hypothesis, don’t underestimate this hypothesis, it will make the workload of the original shop to the horizon become almost no workload, the assumption is: bad nodes do not exceed the total number of nodes 1/3.

The whole process of the PBFT consensus algorithm is divided into five steps: the first step is “request”, which is equivalent to the client requesting read and write, and the fifth step is “reply”, that is equivalent to the system’s final response to the client.
The real consensus is the middle three steps:
Step 2: You ask the minister (pre-prepared)
The third step: the minister answers (preparation)
Step 4: Reconfirm (confirm) between bureaucratic systems

PBFT refers to you and all ministers (all network nodes) as “copy”, and you are the most important copy, the “master node”, responsible for collecting information from ministers, coordinating distribution confirmation, and finally leading the answer.

The master node broadcasts to the entire network, and this process is pre-prepared. The key to pre-preparation is distribution, where the primary node numbers each request and then sends the packet to all replicas.

The prepared message (the three arrows on the right side of Figure 1) contains the requested digital signature (poke this review), which makes it easy for other copies to verify the authenticity.

After verification, it enters the preparation phase: at this point, the copy broadcasts its own reply to the entire network. To prevent malicious attacks, the copy records both the prepared message and the prepared message on its own small book. If you look at the pre-preparation message is not pleasing to the eye, do nothing.

The most important thing in the preparation phase: Make sure all normal nodes agree.
But there are always inconsistent nodes, such as the minister who only spits out the smoke ring (copy 3), and PBFT treats this unresponsive node as invalid. Handling the failed node is what the next “confirmation phase” has to do.

In the confirmation phase, the copy first verifies the digital signature of the message. After the broadcast confirmation, the master node is responsible for statistical consensus. To put it bluntly, you only do one thing: the consensus is reached to reach 2/3 of the total number of system nodes. This consensus is the final answer.

First, at least ensure that 2/3 of the majority of normal nodes are in the same view. In other words, if the consensus does not exceed the 2/3 majority, the master node ran to reply to the client and the replica would assume that the master node failed.
Second, the request number must be within the range specified by the system. Remember that in the pre-preparation session, the master node has to assign a number to the request to broadcast? This number is designed to be mutually identifiable, otherwise the request will not be accounted for, but it also leaves a back door for the main node to disturb the system: deliberately assigning large numbers and blasting memory.

The response plan is also very simple. It is ok to set a number upper limit. This upper limit is called “waterline”. Once the copy discovery request number exceeds the waterline range, the primary node is considered to be invalid.
Third, you must define the length of the timeout, and you cannot wait for the copy to have no bottom line;

To meet this requirement, whenever a copy receives a request, it begins to time until the copy makes the final reply timing. If the response time set by the system is exceeded and the master node does not see the reply client, the copy will determine that the master node is invalid.

Therefore, the system can always deal with the failure of the master node: you are the center of work, once you are falsified or absent, it is only the next second to find someone to change, this is the core logic of the PBFT algorithm.

The PBFT algorithm is not a decentralized consensus, but a centralized control, which is why many people do not classify Ripple’s token XRP as a decentralized currency.
However, the efficiency of PBFT is the last to kill POW, so almost all large financial projects tend to use PBFT to build a coalition chain. The consensus algorithm applies to the public chain, and PBFT is a consensus mechanism that is more suitable for the alliance chain. PBFT uses the mathematical proof model to verify the speed and fault tolerance of its consensus. In the fault tolerance range, the system can not be forked. The above POW or POS can prevent the hacker from forging a large number of beneficial The node is verified, but the native PBFT does not have this capability, but if it is used in the alliance chain, this problem is naturally solved because the members and nodes of the alliance chain are originally screened and verified.

PBFT, and even all BFT can’t be applied to more than 100 nodes
The key to the reason is the message complexity of O(N^2). What does it mean? Point-to-point message transmission needs to send a message. This is O(1) message complexity. If you broadcast a message, you need to send the message to everyone in the network, which is O(N) message complexity. And if you want to reliably broadcast a message in a network with a Byzantine node (malicious node), you need at least O(N^2) message complexity, that is, if the network has 100 nodes, if you If you want to confirm that other people on the network have received your message, you must send at least 10,000 messages.

Then there was Bitcoin, which solved the reliable part with rewards, mining and the longest chain, so the larger network is just O(N) message complexity, which is scalable.

The trading output of PBFT is 1000 times per second, but it can’t be expanded. If no one has tried more than 64 nodes, it can be considered as unavailable.

The way Bitcoin reduces the communication complexity of Byzantine fault tolerance to O(N) is to give the cheater a penalty.

Thus, from the perspective of game theory, the cost and possible benefits of malicious node cheating are simplified—the only way to benefit is double payment, and the cost is more than 50% of computing power.

The study of the entire public chain consensus algorithm is actually looking for a way to ensure that block publishers will not cheat

The advantages of PBFT are:
(1) The system cannot be bifurcated within the fault tolerance range
(2) The system can tolerate any type of error within the scope of fault tolerance
(3) Verification and consensus are extremely fast
(4) No competition, so low energy consumption
(5) Based on the aforementioned point (1), the block is final

The disadvantages of PBFT are:
(1) If more than 1/3 of the verification nodes fail, the system cannot continue to operate.
(2) No ability to prevent hackers from forging a large number of verification nodes

  1. POC:Proof-of-Capacity
Most alternative agreements use certain types of paid participation models. The proof of capacity is no exception, but you need to pay for hard disk space. The more hard drives you have, the more likely you are to mine the next block and get the block reward.
This mechanism generates a large amount of plots data that will be stored in your hardware before mining in the capacity certification system. The more plots you have, the more likely you are to find the next block.
  1. POA:Proof of Activity

In order to avoid hyperinflation, Bitcoin will eventually have only 2,100 coins. This means that at some point in time, Bitcoin block rewards will stop and Bitcoin miners will only receive transaction fees.
Some people think that this will lead to serious problems, people’s behavior will be self-interest, and it will destroy the system. Therefore, Proof of activity emerged as an alternative incentive structure for Bitcoin.

Proof of activity is a hybrid approach that combines proof of effort with proof of entitlement.
In the proof of activity, mining is carried out in the form of traditional workload proofs, and miners compete with each other to solve cryptographic problems. The blocks produced by mining (which are more like templates) do not contain any transactions, so the winning block contains only the head and miner reward addresses.

At this time, the system switches to the equity certificate. Based on the header information, a random verifier is selected to sign the new block. The more tokens a system of certifiers have, the more likely it is to be selected. As long as all certifiers sign it, the template becomes a mature block.

If some of the selected certifiers do not complete the block, then the next winning block is selected, then a new set of certifiers is selected, and so on, until the block gets the correct number of signatures. The transaction fee was distributed to the miners and the verifiers of all signature blocks.

The drawback of the proof of activity is that there are drawbacks of the proof of the workload (requires a lot of energy to mine the block), and there are also the drawbacks of the proof of equity (the verifier cannot detect the double signature).
Decred is currently the only currency that uses proof of activity.

Widely used in: POA.Network, Ethereum Kovn testnet
Advantages: high throughput; scalability
Disadvantages: Centralized system
PoA is a consensus algorithm for a transaction to be verified by a user similar to the “system administrator”. These accounts are confirmed by the truth provided by other nodes. PoA has high throughput and optimizes private networks. But because it is too concentrated, you are unlikely to see this consensus in the public chain.
  1. PoB:Proof of Burn
In the proof of destruction, expensive computing equipment is not required, but they are destroyed by sending the coins to an address, and this is irreversible. By sending your currency to the imaginary address, you get the right to permanently mine in the system according to the random selection process.
Depending on the implementation of the destruction certificate, the miner may destroy the tokens of the original token or other chain, such as bitcoin. The more coins you destroy, the more chance you get to mine the next blockchain.
As time goes on, your shares in the system will decrease, so eventually you will destroy more coins to increase your chances of mining blocks. (This is a bit like Bitcoin’s mining process, you need to continually invest in more advanced computing equipment to maintain your computing power.)
  1. PoET:Proof of elapsed time
Chip manufacturer Intel released its own consensus protocol runtime proof. The system works like a workload proof system but consumes very little energy. Moreover, participants do not need to address cryptographic challenges. Instead, the mechanism uses a Trusted Execution Environment (TEE)—such as SGX—to ensure that blocks are generated in a random manner, but without the need for workload.
Intel’s approach is based on guaranteed latency provided by TEE. According to Intel, the mechanism can scale to thousands of nodes and can run efficiently in any Intel processor that supports SGX.
  1. Casper: from Ethereum
In order to solve the shortcomings of the low cost of doing the bad things in the above POS consensus, Ethereum proposed to pay the margin (cryptocurrency) to participate in the verification of the node, and if the verification node violated the rules to participate in the fraud or attack, or even just do If the system considers “invalid”, the margin will be confiscated. This consensus mechanism is called Casper. Ethereum claims that Casper will be used as a consensus algorithm at an appropriate timing in the future. Casper is not just a simple DPOS, but actually refers to the PBFT mechanism to make improvements.
Pure DPOS, like POS, has forks that can’t be finalized, and Casper guarantees the finality of the block through improved mechanisms. If the attack really occurs, both blocks of the same height are finally confirmed. If at least one-third of the verification nodes violate the rules, the margins of these nodes will be confiscated, and the value may be as high as tens of millions of dollars. As these cryptocurrencies disappear from the market, the price of the currency will rise. This may replace the previous means of enabling emergency hard forks to correct attacks.
  1. zk‑SNARK (Zero‑Knowledge Succinct Non‑Interactive Arguments of Knowledge)

1)Zero-Knowledge: You can prove your gender to the drunkard without a real guy.
2)Succinct: The evidence is short and clear, and the verification is convenient.
3)Non-Interactive means that the two sides do not talk much. The certifier only sends the information to the verifier. When it is extremely complicated, at most one round-trip can be verified.
4)Arguments of Knowledge: Others cannot be forged and have a high degree of credibility.

Zk‐proof (zero knowledge evidence)

1) Proof the number
You are the certifier, with two numbers in your pocket: 3 and 4. You want to prove that you have it, but because these two numbers are important as addresses, such as private keys, you don’t want to be seen.
I am a verifier and want to verify that you do have these two numbers, but I can’t reach out to your pocket. In the traditional sense, we only recognize it as a reality, so it is impossible to do this.

You find a glass box that is draped over the number. This box refracts the numbers so that they don’t look like 3 and 4, but 9 and 10. This magical glass box is the homomorphic hidden function E(x), which has three characteristics:
1, look at the representation number 9, can not guess the internal number 3 – although transparent, but the confidentiality is good, can not be derived by E (x).
2. Envelope 3 reveals 9 and wraps 4 out of 10 – different inputs get different outputs, ie if x≠y, then E(x)≠E(y).
3. As a verifier, I don’t know the specific number in your pocket, but the number on the surface of the glass box has the characteristics of the numbers in the glass box: I rely on E(x) and E(y), and I can get E through complex calculations. The value of x+y).
If a complex operation yields a value of E(x+y) equal to the sum of the two numbers E(x)+E(y) on the surface of the glass box, it is verified by zk‐SNARKs.

Homomorphic hiding is a type of encryption function. There are two types of subdivision: this example belongs to the additive homomorphism, that is, E(x)+E(y)= E(x+y); if E(x)Å*E is satisfied (y) = E(xy), which is the multiplicative homomorphism.

To prevent brute force: Random offset You must find a random number t so that the number transmitted by your glass box is not E(x) and E(y) itself, but E(x+t) and E(yt) ,
Otherwise your secrets are at risk of being exhausted by me. That is to say, what I see from the box at this time is no longer 9 and 10 (E(x) and E(y)), but 26 and 47 (E(x+t) and E(y-t))

2). Prove dynamic numbers
Complex scenes mean: How do you prove that you have this polynomial without showing the polynomial itself?
A glass box that relies on a homomorphic hidden function is no longer sufficient. Because in a polynomial, x may have infinite numbers. The verifier sends a random point s to the prover. The prover can complete the verification first by replying to the value of the verifier P(s). I may take the clues you gave me and brute force your polynomial, so you must find a random offset polynomial R(s ). This R(s) must be like an eye drop, so that I can’t see the P(s) at all.

You put the sum of P(s) and R(s) into the homomorphic encrypted glass box, only let me take a look at the surface number: E(P(s)+R(s)), but this is enough for me. verification.

The second question is: I sent you a random point s=2, you can find a value to fool me, because the value of P(x) may have a basket, if you don’t have this polynomial, but you can especially Guess, guess what, what should I do? The easiest way is to encrypt the random point s and send it to you.

But the trick is to do this: you can’t calculate P(s), R(s), and the cryptographic function value E(P(s)+R(s)).
So, in order for you to easily calculate E(P(s)+R(s)), I will send you all E(1), E(s), E(s2), E(s3) (s2 and s3) Represents the square and cube of s, the same below).

According to the third nature of the encryption function, you can calculate E(P(s)+R(s) based on E(1), E(s), E(s2), and E(s3).
A particularly valuable point is that the specific data of the random point s is not exposed at this time. In other words, you don’t know that I casually say that the s value is equal to 2, but you can still send valuable information to me for verification.

But if you really don’t have a polynomial, you are growing up in a lottery. How can I act as a verifier against your luck? The answer to zk‐SNARK is to continue to fill in random and dilute your good fortune.

I generate a random number k while generating the random number s, and then send you information about s and k, you just give me two numbers.
Just do:
First, the encrypted value of P(s) E(P(s))
Second, the encrypted value of kP(s) E(kP(s))

I select the random point s and the random coefficient k to send you the value of the two-slip encryption function:
E(1), E(s), E(s2), E(s3);
E(k), E(ks), E(ks2), E(ks3);
You generate a random offset polynomial R(x), which is calculated according to the value I give you:
E(P(s)+R(s))
E(kP(s)+kR(s))
You can calculate the above two values ​​and throw it to me for verification. zk‐SNARK will guarantee that we will not suffer or be fooled.

The information sent by the verifier to the prover does not change with the verification content. Therefore, it can be set in advance and reused continuously. This information that can be set in advance is called: Common Reference String: CRS Common Reference String

First, if you verify a complex polynomial, you need to spend a lot of computing resources, so it will be expensive to run on the burning platform.
The pre-common solution is to pre-compile and then run on the wind. Therefore, optimizing the calculation process is still a long and arduous road.

Second, the way to generate and store random information is still very earthy. For example, in Zcash using zk‐SNARK technology, only the encrypted value of random point s and random coefficient k is stored in CRS, while the plaintext of s and k is kept by 6 people privately.

  1. DAG (Directed Acyclic Graph)
A24724CE-F0DC-4342-8568-ABA58106E5E1

Figure 2. DAG

The transaction that is ligated together is called a tangled (Tangle)
You may be wondering why these transactions need to be wired and marked with arrows. Because each time a user initiates a transaction, they must verify the two previous transactions.

POW: The transaction initiator chooses two legal transactions and spends 2 seconds to find a random number, so that the hash value of “random number + information” meets the system requirements. The amount of work required for verification is directly proportional to the weight of the front-hand transaction. The transaction weight is equivalent to the difficulty of verification. The higher the difficulty, the longer the verification time.

In IOTA, the weight is the exponential growth of 3: 3’s 1st power, 3’s 2 power, 3’s 3 power… The more the number of times the transaction is verified, the greater the weight of the transaction

The IOTA team said that the network is not yet mature, so first find a coordinator to see the site. This coordinator is a server called Coordinator. Whether all transactions are legal or not, the boarder will make a decision for the time being, and tell the other nodes after the boarding, which transactions should be verified.

IOTA uses its own hash algorithm curl, but the hash value of the curl algorithm is very easy to collide, so it can forge digital signatures.

34% attack.
One way to prevent such attacks is to recruit miners, but since the IOTA has no fees, all of them do not respond to the mines. At the same time, IOTA is also facing the possibility of denial of service attacks, like the community that does not charge property fees, relying on owner autonomy. It is very difficult to clear the illegal elements and even sweep the fallen leaves.

DAG is a data storage structure that has been in use for more than 30 years since it was invented and has no problem in itself. But the difference between it and the blockchain is that DAG has no traditional consensus, and the credibility of each transaction depends on the number of people who believe in the deal.

So the core issue of adopting DAG technology is how to protect the consistency achieved by the whole network?

The IOTA used a centralized solution: first, the assistants took care of them, and then slowly let go. The Byte-ball, another cryptocurrency that uses DAG, is very simple, and 12 miners protect the system by collecting transaction fees.

DAG used to be a bitcoin expansion solution, but it was not adopted at the end because DAG-based distributed networks are harder to be more effective than blocks in terms of protection consensus.

  1. HashGraph

Separation of accounts is the first time in human history that distributed accounting has been done.
Honest nodes exceed 2/3 of the total number of nodes, which is the fundamental assumption of all Byzantine fault-tolerant algorithms.

The money control person and the bookkeeper are distributed on both sides of the shopkeeper, and they are mutually restrained, but they often have nothing to worry about. Later, the bank paid full-time management and handed over the statement every month. The treasurer checked his own account and continued to be safe.

Until someone suspects something inside the bank, it will silently issue coins that you don’t know. This person invented a new accounting technique.
– Blockchain: A handbook, everyone remembers, whoever is not.
Many people think that the blockchain is distributed accounting, and the distributed account does not have to be recorded with the blockchain. There is also a method: hash map.

Hash Graph is a kind of distributed accounting technology. The most dazzling feature is fast and accurate. It can record the whole network account between the electric and the flint.
Fast and quasi-Hash map’s Gossip Protocol: All nodes tell their neighbors about their trading information, and pass the transaction messages of the neighbors to other nodes. So rumors are like nuclear fission, shot to the whole network

When all the nodes receive the next moment of your event, the account is already recorded. Why?

Because you know that “others know this thing”, and others know that “you know that others know this thing”, stunned? But knowing that this chain can be extended indefinitely, eventually forming a consensus across the network. The whole process is amazing: everyone did not sit around and raise their hands and vote, and this event was recognized.

In Hashitu, this process is called Virtual Voting. “Virtual” means there is no ballot box or teller, but everyone can calculate the consensus without any mistakes.

All of this must be characterized by the hash value: concise and not counterfeit. On this basis, with the rumor agreement and virtual voting, the hash map is finally rushed to a ride.

The hash map is also a Byzantine fault-tolerant algorithm. The sub-category belongs to the completely asynchronous Byzantine Fault Tolerance (aBFT). The name is very awkward, but it is very simple to translate into vernacular: no assumptions about the speed of information dissemination, so Can deal with the impact of communication failures and denial of service attacks Of course, the shortcomings of the completely asynchronous algorithm are also obvious: waiting for less than 2/3 majority nod, all nodes can not be consensus, because everyone is waiting for each other.
The key question is: What should I do when a malicious node exceeds 1/3?
The answer is that there is no way to do it.

License Chain: Nodes need to be approved to be finalists.
The scope boundary of the license chain is the capability boundary of the hash map, which is one of the limitations.
Hashtu is a patented technology that can’t be used without paying.

Each transaction can be booked according to the time it actually takes place, instead of the blockchain technology like Bitcoin, the actual trading time is often not matched with the time recorded by the book.

This is because bitcoin miners usually have to look at the transaction broadcast first, if they find that the priority of a transaction is not high enough) or the fee is not sexy, the miner will press it under the drawer, first package other transactions , look left and right, etc., the registration time on the final account book will be later than the actual transaction time.

However, under the Hash, the trading time is consistent with the actual situation, because the moment of the transaction has spread throughout the network and is recognized. Don’t underestimate this efficiency. There are many innovative applications in the real world. The most famous one is to prevent pre-emptive transactions in the securities industry.

Hash diagram maintains network calm through pre-screening, but it can’t resist malicious flooding itself, so once it flocks to a strange node, it will poke the dead point of the hash map: security.

  1. IPFS
HTTP drawbacks

1) HTTP is inefficient, and the server is expensive. You can only download one file at a time from a single computer server using the HTTP protocol, instead of getting files from multiple computers at the same time. Video transmission over P2P can save up to 60% of bandwidth costs.

2) Historical files have been deleted for an average life of 100 days, and a large number of website files cannot be stored for a long time. Some important documents may disappear on the Internet forever due to improper operation.

3) A centralized network limits the opportunity that the Internet has always been a catalyst for human progress, but a centralized network is easily controlled and is a threat to the sound development of the Internet.

4) Network applications are too dependent on the backbone network

In order to ensure the reliability of the data, the application we developed relies too much on a large central server and guarantees data security through a large number of backups.

IPFS can essentially change the distribution mechanism of network data. How IPFS works:
1) Each file and all its blocks are given a unique fingerprint called a cryptographic hash.

2) IPFS deletes files with the same hash value through the network. It can be used to determine which files are redundant and duplicated. And keep track of the version history of each file.

3) Each network node only stores the content it is interested in, as well as some index information, which helps to figure out who is storing what.

4) When looking for a file, you can find the desired file on the network by looking up the node where the file is saved by using the hash value of the file.
Using a file called IPNS (Decentralized Naming System), each file can be collaboratively named as an easy-to-read name. Searching makes it easy to find the files you want to view.

As can be seen from the introduction of IPFS, IPFS envisages that all network terminal nodes not only serve as the role of Browser or Client. In fact, everyone can act as the operator of this network, and everyone can be a server.

Compared to HTTP, IPFS has some of these features:
1) Based on content addressing, not domain name based addressing. The file (content) has uniqueness of existence. A file is added to the IPFS network, and a uniquely encrypted hash value is given to the content based on the calculation. This will change the habit of using domain names to access the network.
2) Provide a historical version of the file controller (such as git) and let multiple nodes use to save different versions of the file.
3) The IPFS network runs a blockchain, which is a hash table for storing Internet files. Each time there is network access, the address of the content (file) is queried on the chain.
4) By using the incentives of FileCoin, each node has the power to store data. Filecoin is a storage network driven by cryptocurrency. Miners get Filecoin by providing open hard disk space for the network, while users use Filecoin to pay for storing encrypted files on a decentralized network.
Use Case: Watch a video called ABC
1) Join the IPFS network, search the network for files called ABC, (via IPNS – decentralized file naming system)
2) The IPFS network quickly indexes the hash value on the blockchain and feeds back the search results.
3) You pay a little FileCoin token, get the ABC file cache to the local, ABC file is not downloaded from the cloud or server, but contributed by the participants of this network, it may be the closest network node to you. The advantage is that not only does the intermediate server not be needed, but the network is the most efficient.
4). If the ABC file happens to be there for several people around you, the IPFS network will split the file into a small piece, saving the storage cost of these nodes and allowing you to download the video in the most efficient way.
5) This video file is cached in your own computer, not only to watch it yourself, but also to provide resources for others.
6) You can also post new content to this network, and have access to FileCoin tokens, because you also contributed to the network. In this way, the file utilization of the entire network is achieved to achieve optimal efficiency.

Traditional distributed system consensus algorithm

  1. Paxos
It is a consistent algorithm based on message passing and highly fault tolerant.
Phase 1
a) The proposer sends a prepare message to more than half of the acceptors in the network.
b) acceptor replies to the promise message under normal circumstances
Phase 2
a) proposer sends an accept message when there are enough acceptors to reply to the promise message
b) acceptor reply accepted message under normal circumstances
A typical example of Paxos used in distributed systems is Zookeeper, the first proven consensus algorithm whose principle is based on two-phase commit and extension.
The Paxos algorithm divides nodes into three types:
Presenter: Make a proposal and wait for everyone to approve the case. Often the client plays the role
Acceptor: Responsible for voting on the proposal. Often the server plays the role
Learner: was told to close the case and harmonize it, not participating in the voting process.
It is possible to make a proposal for the client or server basic process including the proposer, first to get the support of most acceptors, and when more than half of the support, send the result of the settlement to everyone for confirmation. A potential problem is that the prover has failed during this process and can be resolved by a timeout mechanism. In the worst case, every time a new round of proposal’s proposer fails, the system can never reach agreement (probability is small). Paxos guarantees that the system will reach a consensus when more than 50% of normal nodes are present.
  1. Raft
The Raft algorithm is a simple implementation of the Paxos algorithm. Raft’s core idea is easy to understand. If several databases have the same initial state, as long as the subsequent operations are consistent, the subsequent data will be consistent. From this,
Raft uses Log to synchronize, and divides the server into three roles: Leader, Follower, Candidate, which can convert each other.
The basic process is:
1) Leader Election: Each Candidate will propose an election plan after a certain period of time. The most votes in the most recent stage are selected as Leaders.
2) Synchronization Log: Leader will find the latest Log record in the system and force all Followers to refresh to this record, where Log refers to the occurrence of various events.
  1. Zab

The full name of Zab is the Zookeeper atomic broadcast protocol, which is the consistency protocol used internally by Zookeeper. Compared to Paxos, Zab’s biggest feature is to ensure strong consistency (or linear consistency consistency).
Like Raft, Zab requires a unique Leader to participate in the resolution, and Zab can be broken down into three phases: discovery, sync, and broadcast:
1) Discovery: election PL (prospective leader), PL collection Follower epoch, according to Follower’s feedback PL generates new epoch (new epoch is generated each time a new leader is elected, similar to Raft’s term)

2) Sync: PL Completion Compared to the status of the Follower majority, the follower is then replenished compared to the state of the PL missing, PL and Follower complete the state synchronization, PL becomes the official leader (established leader)

3) Broadcast: The leader handles the client’s write operation and broadcasts the status change to the Follower. After the Follower majority passes, the Leader initiates the status change (deliver/commit).

The heartbeat between the Leader and the Follower is used to determine the health status. Normally, Zab is in the broadcast phase. When an abnormality such as Leader downtime or network isolation occurs, Zab returns to the discovery phase.

Paxos, Raft, Zab, and VR are all protocols for solving consistency problems. The Paxos protocol text tends to be theoretical. Raft, Zab, VR tend to practice, and the degree of consistency guarantee also causes differences between these protocols. Compared to Raft, Zab, and VR, Paxos is purer and closer to the source of consistency problems. Although Paxos tends to be theoretical, it does not mean that Paxos cannot be applied to engineering. Paxos-based engineering practices must consider specific requirements scenarios (such as how consistent they are) and then wrap them in Paxos’ original semantics.

Reference

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s