区块链共识算法分析角度是什么,区块链共识算法研究
区块链共识算法是指在分布式网络环境中，通过一种特定的算法来控制网络上的交易，确保网络上的所有节点都能够达成一致，从而实现区块链的安全性和可靠性。
区块链共识算法是一种基于网络的技术，它可以帮助各个节点在网络中达成共识，从而确保网络中的数据的安全性和可靠性。由于区块链共识算法的特殊性，它可以防止网络中的恶意攻击，防止网络节点的数据篡改，保证数据的完整性和可靠性。
目前，主流的区块链共识算法主要有工作量证明（Proof of Work）、权益证明（Proof of Stake）和权益证明+（Proof of Stake+）等。其中，工作量证明是最为经典的共识算法，它主要是通过节点的计算能力来解决冲突，从而实现共识。
权益证明是一种新型的区块链共识算法，它主要是通过节点持有的网络资产（如比特币）来实现共识，从而避免了工作量证明算法中的能量消耗问题。此外，权益证明+算法是一种改进的权益证明算法，它不仅考虑节点持有的网络资产，还考虑节点的参与程度，从而实现更加安全、高效的共识。
总之，区块链共识算法是一种可以让分布式网络达成共识的技术，它可以有效地防止网络中的恶意攻击，保证网络中的数据安全性和可靠性。目前，主流的区块链共识算法主要有工作量证明、权益证明和权益证明+等，它们都有自己的特点和优势，可以满足不同场景的需求。
请查看相关英文文档
① In-depth understanding of the consensus mechanism and algorithm principles of the blockchain
The so-called "consensus mechanism" is to complete transactions in a very short time through the voting of special nodes Verification and confirmation; for a transaction, if several nodes with unrelated interests can reach a consensus, we can think that the entire network can also reach a consensus on it. To put it more simply, if a Chinese Weibo influencer, a virtual currency player in the United States, an African student and a European traveler do not know each other, but they all agree that you are a good person, then it can basically be concluded that You're not a bad person.
In order for the entire blockchain network node to maintain the same data and ensure the fairness of each participant, all participants in the entire system must have a unified agreement, which is what we have here The consensus algorithm to be used. All Bitcoin nodes follow unified protocol specifications. The protocol specification (consensus algorithm) consists of relevant consensus rules, which can be divided into two major cores: proof of work and the longest chain mechanism. The ultimate expression of all rules (consensus) is the longest chain of Bitcoin. The purpose of the consensus algorithm is to ensure that Bitcoin continues to operate on the longest chain, thereby ensuring the consistency and reliability of the entire accounting system.
Users in the blockchain do not need to consider the credit of the other party when conducting transactions, do not need to trust the other party, and do not need a trusted intermediary or central agency. They only need to follow the blockchain protocol. Realize the transaction. The premise for smooth transactions without the need for a trusted third-party intermediary is the consensus mechanism of the blockchain, that is, in a market environment of mutual understanding and trust, each node participating in the transaction considers its own interests and does not violate any regulations. Motives and behaviors of cheating, so each node will actively and consciously abide by the preset rules to judge the authenticity and reliability of each transaction, and write the record of passing inspection into the blockchain. The interests of each node are different, and logically there is no incentive for them to collude to deceive. This is especially obvious when some nodes in the network have public reputation. Blockchain technology uses a consensus algorithm based on mathematical principles to establish a "trust" network between nodes, and uses technical means to achieve an innovative credit network.
At present, the mainstream consensus algorithm mechanisms in the district industry include: workload proof mechanism, equity proof mechanism, share authorization proof mechanism and Pool verification pool.
The workload proof mechanism is the proof of workload, which is a requirement that must be met when generating a new transaction information (i.e. a new block) to be added to the blockchain. In a blockchain network built based on the proof-of-work mechanism, nodes compete for accounting rights by calculating the numerical solution of random hashing. The ability to obtain the correct numerical solution to generate blocks is a specific manifestation of the node's computing power. The proof-of-work mechanism has the advantage of being completely decentralized. In a blockchain with a proof-of-work mechanism as the consensus, nodes can enter and exit freely. EveryoneThe well-known Bitcoin network uses a proof-of-work mechanism to produce new currencies. However, since the application of the workload proof mechanism in the Bitcoin network has attracted most of the computing power of computers around the world, it is difficult for other blockchain applications that want to try to use this mechanism to obtain the same scale of computing power to maintain their own security. At the same time, mining based on the proof-of-work mechanism also causes a lot of waste of resources, and the period required to reach consensus is also long, so this mechanism is not suitable for commercial applications.
In 2012, a netizen with the pseudonym Sunny King launched Peercoin. This encrypted electronic currency uses a proof-of-work mechanism to issue new coins and a proof-of-stake mechanism to maintain network security. This is the role of the proof-of-stake mechanism in encrypted electronic currency. first application in . Rather than requiring the certifier to perform a certain amount of computational work, Proof of Stake simply requires the certifier to provide ownership of a certain amount of cryptocurrency. The way the proof-of-stake mechanism works is that when a new block is created, the miner needs to create a "coin rights" transaction, which sends a number of coins to the miners themselves according to a preset ratio. The proof-of-stake mechanism reduces the mining difficulty of nodes in equal proportions based on the proportion and time of tokens owned by each node based on the algorithm, thus speeding up the search for random numbers. This consensus mechanism can shorten the time required to reach consensus, but essentially still requires nodes in the network to perform mining operations. Therefore, the PoS mechanism does not fundamentally solve the problem that the PoW mechanism is difficult to apply in the commercial field.
The share authorization certification mechanism is a new consensus mechanism to ensure network security. While trying to solve the problems of the traditional PoW mechanism and PoS mechanism, it can also offset the negative effects of centralization by implementing technological democracy.
The share authorization certification mechanism is similar to board voting. This mechanism has a built-in real-time shareholder voting system, just like the system is convening a never-ending shareholders' meeting at any time, where all shareholders vote. determine company decisions. The decentralization of the blockchain established based on the DPoS mechanism relies on a certain number of representatives rather than all users. In such a blockchain, all nodes vote to elect a certain number of node representatives, who act on behalf of all nodes to confirm blocks and maintain the orderly operation of the system. At the same time, all nodes in the blockchain have the power to remove and appoint representatives at any time. If necessary, all nodes can vote to disqualify the current node representatives and re-elect new representatives to achieve real-time democracy.
The share authorization certification mechanism can greatly reduce the number of nodes participating in verification and accounting, thereby achieving second-level consensus verification. However, this consensus mechanism still cannot perfectly solve the application problems of blockchain in business, because this consensus mechanism cannot get rid of its dependence on tokens, and the existence of tokens is not required in many commercial applications.
The Pool verification pool is based on the traditional distributed oneEstablished using consistent technology and supplemented by a data verification mechanism, it is a consensus mechanism widely used in blockchains.
The Pool verification pool can work without relying on tokens. Based on mature distributed consensus algorithms (Pasox, Raft), it can achieve second-level consensus verification, which is more suitable for multi-party participation. Polycentric business model. However, the Pool verification pool also has some shortcomings. For example, the degree of distribution that the consensus mechanism can achieve is not as good as the PoW mechanism.
Here we mainly explain some algorithm principles of the blockchain workload proof mechanism and the Bitcoin network. How to prove your workload? I hope everyone can have a basic understanding of the consensus algorithm.
The main feature of the proof-of-work system is that the client has to do a certain amount of difficult work to get a result, and the verifier can easily use the results to check whether the client has done the corresponding work. A core feature of this scheme is asymmetry: the work is modest for the requester and easy to verify for the verifier. It differs from CAPTCHAs, which are easier to solve by humans rather than easier to solve by computers.
The figure below shows the workload proof process.
For example, give a basic character "hello, world!", the workload requirement we give is that you can add a nonce (random number) after this character creation Integer value, perform SHA-256 operation on the changed (nonce added) character creation, if the result (expressed in hexadecimal form) starts with "0000", the verification is passed. In order to achieve this proof-of-work goal, it is necessary to continuously increment the nonce value and perform a SHA-256 hash operation on the resulting character creation. According to this rule, it takes 4251 operations to find the hash with leading 4 zeros.
Through this example, we have a preliminary understanding of the proof-of-work mechanism. Some people may think that if proof of work is just such a process, then it is enough to remember that the nonce is 4521 so that the calculation can pass verification. Of course not, this is just an example.
Next we simply change the input to "Hello, World! + integer value". The integer value ranges from 1 to 1000, which means that the input is turned into an array of 1 to 1000: Hello, World !1;Hello,World!2;...;Hello,World!1000. Then perform the above proof of work on each input in the array in turn - find the hash with leading 4 zeros.
Since the hash valueThe characteristics of pseudo-randomness can be easily calculated based on the relevant knowledge of probability theory. It is expected that it will take 2 to the 16th power of attempts to obtain a hash with four leading zeros. If you count the actual results of the 1,000 calculations just performed, you will find that the average number of calculations is 66,958, which is very close to 2 to the 16th power (65,536). In this example, the number of calculations expected by mathematics is actually the required "workload". Repeating the workload proof multiple times will be a probability event that conforms to statistical laws.
The actual number of calculations used to count the input characters and obtain the corresponding target result is as follows:
For any node in the Bitcoin network, if you want to generate a new block To join the blockchain, you must solve this puzzle of the Bitcoin network. The key elements of this question are the proof-of-work function, block and difficulty value. The workload proof function is the calculation method of this question, the block is the input data of this question, and the difficulty value determines the amount of calculation required to understand this question.
The proof-of-work function used in the Bitcoin network is the SHA-256 mentioned above. Blocks are actually generated in the proof-of-work process. Kuangong constantly constructs block data and checks whether each calculated result meets the required workload, thereby determining whether the block meets the network difficulty. The block header is the input data of the Bitcoin proof-of-work function.
The difficulty value is an important reference indicator for miners to mine. It determines how many hash operations it takes for miners to generate a legal block. The Bitcoin network generates a block approximately every 10 minutes. If the generation of new blocks basically maintains this speed under different network computing power conditions, the difficulty value must be adjusted according to changes in the computing power of the entire network. The general principle is to ensure that the network always generates a new block in 10 minutes, regardless of the mining power.
The adjustment of the difficulty value occurs independently and automatically in each complete node. Every 2016 blocks, all nodes will automatically adjust the difficulty value according to a unified format. This formula is based on the time spent in the latest 2016 blocks and the expected time (assuming a withdrawal is generated every 10 minutes, the expected time is 20160 minutes) and adjusted according to the ratio of actual duration to expected duration. That is, if blocks are generated faster than 10 minutes, increase the difficulty value; anyway, decrease the difficulty value. The formula is expressed as follows:
New difficulty value = old difficulty value * (20160 minutes/time spent in the past 2016 blocks).
Proof of work requires a target value. The calculation formula of the target value (Target) of Bitcoin's proof of work is as follows:
Target value = maximum target value/difficulty value, where the maximum target value is oneConstant value
The size of the target value is inversely proportional to the difficulty value. The achievement of Bitcoin's workload proof is that the block hash value calculated in the mine must be less than the target value.
We can also simply understand the process of Bitcoin workload as performing SHA-256 hash operation by constantly changing the block header (that is, trying different nonce values) and using it as input. Find a process that has a hash value in a specific format (that is, requires a certain number of leading 0s), and the more leading 0s required, the more difficult it becomes.
The steps of Bitcoin’s proof-of-work puzzle can be roughly summarized as follows:
The process can be represented by the following figure:
Bitcoin’s proof of work is the main work we commonly call “mining”. Understanding the workload proof mechanism will lay the foundation for us to further understand the consensus mechanism of the Bitcoin blockchain.
② Blockchain --- Consensus Algorithm
The PoW algorithm is a mechanism to prevent the abuse of distributed service resources and denial of service attacks. It requires nodes to perform complex operations that consume a moderate amount of time and resources, and the operation results can be quickly verified by other nodes, using time and energy as a guarantee to ensure that services and resources are used according to real needs.
The most basic technical principle in the PoW algorithm is the use of hashing algorithms. Assume that the hash value Hash(r) is found. If the original data is r (raw), the operation result is R (Result).
R = Hash(r)
The characteristic of the hash function Hash() is that for any input value r, the result R is obtained, and r cannot be deduced from R. When the input original data r changes by 1 bit, the resulting R value changes completely. In the Bitcoin PoW algorithm, the algorithm difficulty d and the random value n are introduced, and the following formula is obtained:
Rd = Hash(r+n)
This formula requires filling in the random In the case of value n, the first d bytes of the calculation result Rd must be 0. Due to the unknown nature of the hash function results, each miner has to do a lot of calculations to get the correct result. After the calculation result is broadcast to the entire network, other nodes only need to perform a hash operation to verify it. The PoW algorithm uses this method to make calculations consume resources, and verification only needs to be done once.
The PoS algorithm requires node verifiers to pledge a certain amount of funds to be eligible for mining and packaging, and the regional chain system uses a random method when selecting packaging nodes., the more funds a node pledges, the greater its probability of being selected to package a block.
In POS mode, each coin generates 1 coin age every day. For example, if you hold 100 coins for a total of 30 days, then your coin age will be 3000 at this time. At this time, if you verify a POS block, your currency age will be cleared to 0, and the corresponding digital currency interest will be obtained from the block.
The process of a node producing blocks through the PoS algorithm is as follows: To become a block producing node, an ordinary node must first pledge its assets. When it is its turn to produce a block, it packages the block and then broadcasts it to the entire network. , other verification nodes will verify the legitimacy of the block.
The DPoS algorithm is similar to the PoS algorithm and also uses shares and equity pledges.
But the difference is that the DPoS algorithm uses a delegated pledge method, which is similar to the method of universal election of representatives to select N super nodes to record and produce blocks.
Voters cast their votes for a certain node. If a certain node is elected as an accounting node, then the accounting node can often use any method to reward its voters after obtaining the block reward.
These N accounting nodes will take turns to produce blocks, and the nodes will supervise each other. If they do evil, the pledge deposit will be deducted.
By trusting a small number of honest nodes, unnecessary steps in the block signing process can be removed, increasing the speed of transactions.
Byzantine problem:
Byzantium was the capital of the ancient Eastern Roman Empire. For defense, an army led by a single general was stationed in each fiefdom. Between the generals The message could only be delivered by messenger. In a war, all generals must reach a consensus and decide whether to go to war together.
However, there may be traitors within the army who will influence the generals to reach a consensus. The Byzantine Generals Problem refers to the problem of how the remaining generals can reach a unanimous decision when one of the generals is known to be a traitor.
BFT:
BFT is Byzantine fault tolerance. Byzantine fault tolerance technology is a type of fault tolerance technology in the field of distributed computing. The Byzantine hypothesis is a modeling of the real world, where computers and networks may behave unpredictably due to hardware errors, network congestion or outages, and malicious attacks. Byzantine fault tolerance techniques are designed to handle these abnormal behaviors and meet the specification requirements of the problem to be solved.
Byzantine fault-tolerant system:
The failed node is called a Byzantine node, and the normalNodes are non-Byzantine nodes.
Assuming that the distributed system has n nodes, and assuming that the entire system has no more than m Byzantine nodes (n ≥ 3m + 1), the Byzantine fault-tolerant system needs to meet the following two conditions:
In addition, the Byzantine fault-tolerant system needs to achieve the following two indicators:
PBFT is the practical Byzantine fault-tolerant algorithm, which solves the problem of inefficiency of the original Byzantine fault-tolerant algorithm. The time complexity of the algorithm is O(n^2 ), so that Byzantine fault tolerance problems can be solved in actual system applications
PBFT is a state machine copy replication algorithm. All copies operate in the process of a view (view) rotation. The master The node is determined by the view number and the set of node numbers, that is: main node p = v mod |R|. v: view number, |R| number of nodes, p: primary node number.
The consensus process of the PBFT algorithm is as follows: the client (Client) initiates a message request (request) and broadcasts it to each replica node (Replica), and one of the master nodes (Leader) initiates a proposal message pre -prepare and broadcast. Other nodes obtain the original message and send prepare messages after the verification is completed. Each node receives 2f+1 prepare messages, that is, it is considered ready and sends a commit message. When the node receives 2f+1 commit messages and the client receives f+1 identical reply messages, it means that the request initiated by the client has reached a network-wide consensus.
The specific process is as follows:
Client c sends a
When the master node receives the client's request, it needs to conduct the following verifications:
a. Whether the signature of the client's request message is correct.
Illegal requests are discarded. For a correct request, a number n is assigned. The number n is mainly used to sort the client's requests. Then broadcast a <
Replica node i receives the PRE-PREPARE message from the master nodeinformation, the following verification is required:
a. Whether the master node PRE-PREPARE message signature is correct.
b. Whether the current replica node has received a PRE-PREPARE message under the same v and also numbered n, but with different signatures.
c. Whether the abstracts of d and m are consistent.
d. Whether n is within the interval [h, H].
Illegal requests are discarded. Correct request, replica node i sends a
When the master node and replica node receive the PREPARE message, they need to conduct the following verifications:
a. Whether the signature of the replica node's PREPARE message is correct.
b. Whether the current replica node has received n under the same view v.
c. Whether n is within the interval [h, H].
d. Whether d is the same as d in the currently received PRE-PPREPARE
Illegal request is discarded. If replica node i receives 2f+1 verified PREPARE messages, it sends a
When the master node and replica node receive the COMMIT message, they need to conduct the following verifications:
a. Whether the signature of the COMMIT message of the replica node is correct.
b. Whether the current replica node has received n under the same view v.
c. Whether the abstracts of d and m are consistent.
d. Whether n is within the interval [h, H].
Illegal requests are discarded. If replica node i receives 2f+1 verified COMMIT messages, it means that most nodes in the current network have reached a consensus, run the client's request operation o, and returnReturn
If the master node does evil, it may assign the same sequence number to different requests, or not allocate sequence numbers, or make adjacent sequence numbers discontinuous. The backup node should have the responsibility to actively check the validity of these sequence numbers.
If the master node goes offline or does something evil and does not broadcast the client's request, the client sets a timeout mechanism. If the timeout occurs, the request message is broadcast to all replica nodes. The replica node detects that the master node has done something evil or is offline, and initiates the View Change protocol.
View Change protocol:
The replica node broadcasts
When the master node p = v + 1 mod |R| receives 2f valid VIEW-CHANGE messages, it broadcasts
The replica node receives the NEW-VIEW message from the master node, verifies the validity, and if valid, enters the v+1 state and starts the PRE-PREPARE message in O processing flow.
In the above algorithm process, in order to ensure that the previous request can be restored during the View Change process, each replica node records some messages to the local log. When the request is executed The replica node needs to clear the record messages of the previous request.
The simplest way is to execute the consensus synchronization of the current state again after the Reply message. This is relatively expensive, so it can be executed after executing multiple requests K (for example: 100). A status synchronization. This status synchronization message is the CheckPoint message.
Replica node i sends<CheckPoint, n, d, i> to other nodes, n is the last view request number retained by the current node, d is a summary of the current status, and the CheckPoint message is recorded in the log. If replica node i receives 2f+1 verified CheckPoint messages, the messages in the previous log are cleared and n is used as the current stable checkpoint.
This is an ideal situation. In fact, when the replica node i sends a CheckPoint message to other nodes, the other nodes have not completed K requests, so they will not respond to i's request immediately. It will also follow its own rhythm, moving forward, but the CheckPoint issued at this time does not form stable.
In order to prevent i from processing requests too quickly, set a high and low water level interval [h, H] mentioned above to solve this problem. The low water level h is equal to the number of the previous stable checkpoint, and the high water level H = h + L, where L is the value we specify, which is equal to an integer multiple of the number of requests processed in the checkpoint cycle K, and can be set to L = 2K. When the request processed by replica node i exceeds the high water mark H, it will stop and wait for the stable checkpoint to change before continuing.
In blockchain scenarios, it is generally suitable for private chain and alliance chain scenarios that require strong consistency. For example, in the IBM-led blockchain Hyperledger project, PBFT is an optional consensus protocol. In Hyperledger's Fabric project, the consensus module is designed as a pluggable module and supports consensus algorithms such as PBFT and Raft.
Raft is based on a leader-driven consensus model, in which an outstanding leader (Leader) will be elected, and the Leader will be fully responsible for managing the cluster. Responsible for managing replication logs between all nodes in the Raft cluster.
In the figure below, the Leader (S1) of the cluster will be selected during the startup process and serve all commands/requests from clients. All nodes in a Raft cluster maintain a distributed log (replicated log) to store and submit commands (log entries) issued by clients. The Leader accepts log entries from clients and replicates them among all followers (S2, S3, S4, S5) in the Raft cluster.
In a Raft cluster, a minimum number of nodes is required to provide the expected level of consensus guarantee, which is also called a quorum. Execute operations in a Raft clusterThe minimum number of votes required for operation is (N / 2 +1), where N is the total number of members in the group, that is, at least more than half of the votes are cast, which is why the cluster nodes usually have an odd number. So, in the example above, we need at least 3 nodes to have consensus guarantees.
If the legal quorum node is unavailable for any reason, that is, the votes do not exceed half, the negotiation will not reach an agreement and new logs cannot be submitted.
Data storage: Tidb/TiKV
Log: Alibaba's DLedger
Service discovery: Consul& etcd
< p> Cluster scheduling: HashiCorp NomadCan only accommodate faulty nodes (CFT), not evil nodes
Sequential voting, only serial apply, so high concurrency Poor performance in scenarios
Raft solves the distributed consensus problem by solving the three main sub-problems surrounding Leader election and managing the security functions of distributed logs and algorithms.
When we start a new Raft cluster or a leader is unavailable, a new leader will be elected through negotiation among all member nodes in the cluster. Therefore, in a given instance, a node of a Raft cluster can be in any of the following states: Follower, Candidate, or Leader.
When the system first starts, all nodes are followers. If they do not receive the heartbeat signal from the leader within a period of time, the follower will be converted into a candidate;
If a node If a Candidate node receives votes from the majority of nodes, the Candidate can be converted into a Leader, and the remaining Candidate nodes will return to the Follower state;
Once a Leader discovers that there is a Leader node in the system that is older than itself. If the term is higher, it will be converted to Follower.
Raft uses a heartbeat-based RPC mechanism to detect when a new election starts. During normal times, the Leader will regularly send heartbeat messages to all available Followers (in practice, the log and heartbeat may be combinedSend it). Therefore, the other node starts in the Follower state and remains in the Follower state as long as it receives periodic heartbeats from the current Leader.
When the Follower reaches its timeout, it will start the election process in the following way:
Based on the responses that the Candidate receives from other nodes in the cluster, the three steps for the election can be derived result.
The implementation of consensus algorithms is generally based on replicated state machines. What is a replicated state machine:
In simple terms: the same initial recognition state + the same input = Same end state. Different nodes should use the same and deterministic function to process input, rather than introducing uncertain values, such as local time, etc. It is a good idea to use replicated log. Log has the characteristics of persistence and order preservation, and is the cornerstone of most distributed systems.
With the Leader, all concurrent requests from the client can form an orderly log (status) sequence on the Leader's side to represent the order in which these requests are processed. The Leader then sends its log sequence to the Followers to maintain the global consistency of the entire system. Note that this is not strong consistency, but eventual consistency.
The log consists of log entries with a sequential number (log index). Each log entry consists of the term when it was created, and the data contained in the log, which can be of any type, from simple types to blocks of the blockchain. Each log entry can be represented by a [term, index, data] sequence pair, where term represents the term, index represents the index number, and data represents the log data.
The Leader attempts to execute replication commands on a majority of the nodes in the cluster. If the replication is successful, the command is submitted to the cluster and the response is sent back to the client. Similar to two-phase commit (2PC), but the difference from 2PC is that the leader only needs the consent of more than half of the nodes (in a working state).
Both leader and follower may crash, so the log maintained by the follower may have the following situations compared with the leader
When the leader and follower are inconsistent, the leader forces the follower to copy its own log, Leader will try from back to front, each time AppendEntriesAfter failure, try the previous log entry (decrementing the nextIndex value) until the log consistent position point of each Follower is successfully found (based on the two guarantees mentioned above), and then cover the Followers entries after that position one by one backwards. So missing or extra entries may persist for multiple terms.
Requires the candidate's log to be at least as up-to-date as other nodes. If not, the follower node will not vote for the candidate.
Means that each submitted entry must exist in at least one of these servers. If a candidate's log is at least as up-to-date as the other logs in the majority, it will save all committed entries, avoiding a log rollback event.
That is, at most one leader can be elected in any term. This is very important, there can only be one leader in a replica set at any time. There is more than one leader in the system at the same time, which is called brain split. This is a very serious problem and will cause data coverage loss. In raft, two points guarantee this property:
Therefore, there must be only one leader in a certain term.
When the status of nodes in the cluster changes (the cluster configuration changes), the system is vulnerable to system failure. So, to prevent this, Raft uses something called a two-phase approach to changing cluster membership. Therefore, in this approach, the cluster first changes to an intermediate state (called federated consensus) before implementing a new membership configuration. Federated consensus enables the system to be used to respond to client requests even when transitioning between configurations, and its main purpose is to improve the availability of distributed systems.
③ Analysis of the relationship between distributed and blockchain
We have talked about the discussion of blockchain technology many times in previous articles, and also I have introduced to you which programming development languages are used to realize the realization of the blockchain insight chain technology. Today we will learn together how to analyze and understand the structure of the blockchain from a distributed perspective.
Blockchain is the underlying technology in Bitcoin and is used to implement a centerless peer-to-peer cash system. Because there is no central organization involved, Bitcoin uses blocks Organize transaction data in the form of a chain to prevent "double spending" and reach transaction consensus.
Digital assets in the traditional sense, such as game currency, are managed in a centralized manner and can only be transferred in a single system, coordinated by a centralized organization. , usually stored in a database. From a macro perspective, blockchain and database are both used to store data, but the form of data access is different.
Blockchain is essentially aA distributed database with multiple activities in different places. The idea of multi-activity in different places was originally to solve the disaster recovery problem of the system. It has been a direction explored in the field of distributed databases for many years, but with little success because multi-activity in different places needs to solve the problem of data conflicts. This problem is actually Not easy to solve. However, the blockchain born in Bitcoin has realized the world's largest remote multi-active database in a completely new way. It is completely open, has no boundaries, supports tens of thousands of nodes and can join and exit at random.
The problem of data conflicts is even more prominent in the blockchain. Each node in the blockchain is a completely peer-to-peer multi-active architecture, and tens of thousands of nodes must reach an agreement. , who should the data be based on? The method used by Bitcoin is POW. Everyone calculates a puzzle. Whoever calculates it first will have the right to keep accounts. In this cycle, the account he keeps shall prevail in the next cycle. Everyone recalculates. Nodes competing for accounting rights decide which Quanlu transactions are packaged into blocks and synchronize the blocks to other nodes. Other nodes still need to verify the transactions in the block based on local data, unlike the master-slave nodes of the database. This is the consensus algorithm in the blockchain. Although POW consumes a lot of computing power, the advantage is that in the process of competing for accounting rights, POW only needs to calculate hashes in its own nodes and does not need to go through network voting for election. The cost of network communication is small, and it is suitable for consensus among large-scale nodes. Shahe Computer Training believes that POW is a complete, simple and crude method in the current public chain and can stand the test, but the problem is that the efficiency is too low.
So PoS and DPoS were developed later. Whoever has more assets will have the right to bookkeeping, or everyone will vote, but this also introduces economic problems. For example, the so-called vote-buying issue is difficult to control. In traditional distributed databases, it is not called a consensus algorithm, but a consistency algorithm, which is essentially the same thing. However, the number of nodes in a distributed database is generally very small, and the network is trustworthy. Usually the nodes are safe and reliable. We can basically trust every node. Even if it fails and does not respond, it will never respond. False response. Therefore, in traditional company distributed data, Raft or Paxos protocols are used to implement this consistency algorithm.
④ What is the role of consensus algorithm in Jinwowo blockchain technology?
Jinwowo analyzes the consensus mechanism in blockchain technology as follows:
Blockchain is a decentralized distributed ledger system. Due to the high network delay in peer-to-peer networks, the order of transactions observed by each node cannot be completely consistent.
Therefore, the blockchain system needs to design a mechanism to agree on the sequence of transactions that occur within a certain period of time. This algorithm that reaches consensus on the order of transactions within a time window is called a "consensus mechanism."
⑤ Consensus mechanism of blockchain
1. How to confirm and reach consensus on transaction information on the network?
Although consensus mechanisms are often mentioned, the meaning and understanding of consensus mechanisms are not clear. Therefore, it is necessary to understand the relevant concepts, principles and implementation methods of the consensus mechanism.
The transaction information of the blockchain is transmitted to each node in the network through network broadcast. How to confirm the broadcast information and reach a consensus among the entire network nodes and finally write it into the block? If there is no corresponding reliable and secure implementation mechanism, it will be difficult to realize its basic functions. Therefore, the consensus mechanism is a key to the operation of the entire network.
The consensus mechanism solves the problem of how the blockchain can achieve consistency in a distributed scenario. The blockchain can reach a relatively balanced state among many nodes because of the consensus mechanism. So how does the consensus mechanism solve the problem of mutual trust between nodes based on the idea of decentralization?
When the idea of distribution was proposed, people began to design consensus algorithms based on the FLP theorem and the CAP theorem. Standardly speaking, the consistency of an ideal distributed system should meet the following three points:
1. Termination: The consistency result can be completed within a limited time.
2. Consensus: The final decision-making results of different nodes should be the same.
3. Validity: The result of the decision must be a proposal put forward by other processes.
However, in actual computer clusters, the following problems may exist:
1. Nodes have different transaction processing capabilities, and the data throughput of network nodes is different
2. The communication channel between nodes may be unsafe
3. There may be malicious nodes
4. When asynchronous processing capabilities reach a high degree of consistency, The scalability of the system will become worse (cannot tolerate the addition of new nodes).
Scientists believe that it is impossible to achieve complete consistency in a distributed scenario. However, engineers can sacrifice part of the cost in exchange for the consistency of distributed scenarios. The above two major theorems also have this idea. Therefore, various formula mechanisms based on blockchain design can be regarded as sacrificing part of the cost in exchange for more adaptability. My idea is to make a flexible transformation on this idea, that is, sacrificing part of the cost at the appropriate time and space in exchange for consistency adapted to the scene at that time, and a flexible blockchain system can be realized that is pluggable. Pull-out blockchain system. Today I will introduce my views and analysis on various consensus mechanisms. Whether there are evil nodes in a distributed system is divided into Byzantine fault tolerance and non-Byzantine fault tolerance.Wrong mechanism.
The FLP theorem is the impossibility of FLP. It proves that in a distributed scenario, no matter any algorithm, even if only one process hangs up, there is an inability to reach consensus for other non-failed processes. possible.
FLP is based on the following assumptions:
Can only be modified once: Each process initially records a value (0 or 1). The process can receive messages, change the value, and send messages. When the process enters the decide state, the value will no longer change. The protocol ends successfully when all non-failed processes enter the decided state. This is relaxed to the extent that some processes enter the decided state, even if the agreement is successful.
Asynchronous communication: The biggest difference from synchronous communication is that there is no clock, no time synchronization, no timeout, no detection failure, messages can be delayed arbitrarily, and messages can be out of order.
Communication is robust: As long as the process does not fail, the message will be delayed indefinitely, but will eventually be delivered; and the message will only be delivered once (no duplication).
Fail-Stop model: A process failure is like a downtime and no more messages are processed.
Number of failed processes: At most one process fails.
CAP is the most discussed theory in distributed systems, especially in the field of distributed storage. CAP was proposed by Eric Brewer at the PODC meeting in 2000. It was a result of Eric Brewer's research on data consistency (consistency), service availability (availability), and partition fault tolerance (partition- tolerance) conjecture:
Data consistency (consistency): If the system returns success for a write operation, then subsequent read requests must read the new data; if the system returns failure, then all read operations No one can read this data. For the caller, the data has strong consistency (also called atomic and linearizable consistency) [5]
Service availability (availability) : All read and write requests are responded to within a certain period of time, can be terminated, and will not wait forever
Partition-tolerance: In the case of network partitions, the separated nodes can still function normally External services
If AP is satisfied at a certain moment, the separated nodes can serve externally at the same time but cannot communicate with each other, which will lead to inconsistent status, that is, C cannot be satisfied; if CP is satisfied, C cannot be achieved in the case of network partition, and the request only Can wait forever, that is, A is not satisfied; if CA is to be satisfied, the node status must be consistent within a certain period of time, and network partitions must not occur, then P cannot be satisfied.
C, A, and P can only satisfy at most two of them. Like the FLP theorem, the CAP theorem also indicates an unreachable result (impossibility result).
⑥ What is the analysis of blockchain technology from a narrow and broad perspective?
The analysis of Jinwowo Network Technology from a narrow and broad perspective is as follows:
In a narrow sense In other words, blockchain is a chain data structure that combines data blocks in a sequential manner in chronological order, and is a cryptographically guaranteed distributed ledger that cannot be tampered with or forged.
Broadly speaking, blockchain technology uses block chain data structures to verify and store data, uses distributed node consensus algorithms to generate and update data, and uses cryptography to ensure the security of data transmission and access. A new distributed infrastructure and computing paradigm that uses smart contracts composed of automated script code to program and manipulate data.
⑦ POA (Proof of Activity) blockchain consensus algorithm
POA (Proof of Activity) algorithm is a blockchain consensus algorithm. The basic principle is to combine POW (Proof of Activity) work) and POS (Proof of stake) algorithm. For the specific content of POW algorithm and POS algorithm, please refer to:
POW algorithm: https://www.jianshu.com/p/b23cbafbbad2
POS algorithm: https://blog.csdn.net/wgwgnihao/article/details/80635162
Compared with other algorithms, the POA algorithm can improve the network topology and maintain the proportion of online nodes. Fewer transaction fees while reducing energy consumption during the consensus algorithm process.
The network required by the POA algorithm also contains two types of nodes, miners and ordinary participants, among which ordinary participants may not always stay online. The POA algorithm first constructs a block header by miners, and selects N coins from the block header. The owners of these N coins participate in the subsequent verification and block generation process.
From here we can see that the POA algorithm is not only related to computing power, but the subsequent election of N participants is completely determined by the total number of coins owned by the participants in the network.Quantity determines. Participants with more coins have a greater chance of being selected as N subsequent participants. The necessary condition for the subsequent participation of N participants is that these N participants must be online, which is also the origin of the POA name. The maintenance of the POA algorithm depends on the active nodes (Active) in the network.
An ideal basic process of the POA algorithm is that, similar to the POW protocol, the miner constructs a block header that meets the difficulty requirements, and calculates the number of N coins from the block header obtained by the miner. Traceability in the chain can reveal the current participants of these coins. The miner sends the block header to the N participants, among which the first N-1 participants verify and sign the block, and the last N-th participant verifies and adds the transaction to the block, and the block is Publishing it out means completing the production of a block.
An ideal process is shown in the figure below:
In actual operation, there is no guarantee that all participants on the network are online, and participants who are not online cannot perform checksum signatures. This Block headers that cannot be verified and signed will be discarded.
That is, in actual operation, a miner should construct a block header and broadcast it to each participant for signature, while continuing to reconstruct a new block header to prevent any of the N participants derived from the previous block header from being online. As a result, the block header was abandoned.
Therefore, in this case, whether a block is confirmed is not only related to the computing power of the miner but also to the online ratio on the network.
Compared with pure POW, when a block is produced in the same 10 minutes as Bitcoin (POW), POA will have losses caused by participants not being online. Therefore, the number of blocks that miners can construct within 10 minutes The number will be greater, that is, the difficulty limit of the block will be reduced, and the energy loss caused by miners during the mining process will also be reduced.
Compared with pure POS, it can be seen that the block generation process of POA does not upload the relevant information in the process of constructing the block, which can significantly reduce the redundant information generated by the maintenance protocol on the blockchain. quantity.
This section analyzes some parameter settings in the appeal protocol
After the miner constructs the block header, it verifies the block header and selects the number of N participants in the block construction. The determination is similar to the selection of the block time of each block in Bitcoin. Bitcoin has chosen 10 minutes as the expected block time for each block and adapted it by dynamically adjusting the difficulty.
The value of N here can also be selected or dynamically adjusted. Dynamic adjustment requires more complex protocol content, which may lead to data expansion in the blockchain, and complex protocols also increase the possibility of attackers attacking. In addition, there is currently no way to prove what benefits dynamic adjustment can bring.Static adjustment can obtain a value of N=3 in the subsequent analysis (4 Safety Analysis), which is more appropriate.
As can be seen from the above description, in addition to miners, there are also N currency owners derived from the block header who construct new blocks. After constructing a new block, these participants should also receive certain incentives to keep participants online.
The non-matching ratio between miners and participants is related to the online status of the participants. The incentives given to participants are closely related to their enthusiasm to stay online. The more participants stay online, the better the stability of the network can be maintained. Therefore, when there are not enough online participants on the network, the incentive share ratio that participants receive can be increased, thereby motivating more participants to come online.
How to determine the online status of the current participant? When the last Nth participant constructs a block, the constructed but discarded block headers can be added to the block. If the number of discarded block headers is too large, it means that the number of people online is too low, and the sharing ratio should be adjusted.
At the same time, the final N-th participant’s share with other participants also needs to be considered. The N-th participant needs to add the transaction to the block, that is, the UTXO pool needs to be maintained. At the same time, the N-th participant also needs to add the transaction to the block. The discarded block header is added to the newly constructed block.
In order to encourage them to add abandoned block headers to newly constructed blocks, a small amount of incentives can be appropriately added according to the added block headers. Although adding more block headers can increase the share in the next round, it should be enough to motivate participants to add unused block headers to the block (it is impossible for participants to add more block headers in order to increase their share) , each block header means the workload of a miner).
If a participant does not maintain the UTXO pool, he cannot construct the block, but he can participate in the first N-1 signatures. Therefore, in order to motivate participants to maintain the UTXO pool, as the last participant to construct the block, he must be given More incentives, like twice as much as other participants.
From the description in 3.2, we can know that a user must be online and maintain the UTXO pool to gain as much benefit as possible. This mechanism will inevitably lead some users to entrust their accounts to a centralized organization. This institution remains online at all times and maintains their accounts for users, participating in the construction of blocks and obtaining benefits when they are selected as participants in constructing blocks. Finally, the organization divides the proceeds in some form.
As mentioned above, participants must use their own keys to sign, and after being entrusted to an organization, the organization can use this key to sign and construct blocks, and it is also possible to use this key to consume users' property. A limited-spend key can be used here. This key has two functions. One is to consume part of the property in the account, and the other is to transfer all the property to a designated account. When hosting, you can useUsing this key, you can immediately transfer all your property to another account after being notified that part of the property has been spent to ensure the security of your property.
From the above analysis, we can see that the security of POA is related to the computing power owned by the attacker and the equity owned by the attacker. Assuming that the proportion of online equity owned by the attacker is , the attacker's computing power needs to be times that of all other computing powers to achieve a fork. Assuming that the total proportion of the attacker's equity is , and the online proportion of honest users in the network is , then the attacker's computing power needs to be times that of all other computing powers to achieve the attack.
The analysis table of the attack is as follows:
As can be seen from the above analysis, the POA algorithm can improve the network topology, maintain the proportion of online nodes, and require less transaction fees than other algorithms. At the same time, the energy loss during the consensus algorithm process is reduced. At the same time, the attack cost of the PoA protocol is higher than that of Bitcoin's pure PoW protocol.
References: Proof of Activity: Extending Bitcoin's Proof of Work via Proof of Stake
⑧ Six core algorithms of blockchain technology
Block Six Core Algorithms of Chain Technology
Blockchain Core Algorithm 1: Byzantine Agreement
The story of Byzantium probably goes like this: The Byzantine Empire has huge wealth, and its 10 neighboring countries have been around for a long time, but Byzantium's high walls were so impregnable that no single neighbor could successfully invade. Any invasion by a single neighbor will fail, and it is also possible that it will be invaded by 9 other neighbors. The Byzantine Empire's defensive capabilities were so strong that at least half of its ten neighbors had to attack at the same time to be able to break through. However, if one or several of the neighbors agree to attack together, but betrayal occurs during the actual process, then the invaders may all be annihilated. So each party acted cautiously and did not dare to trust its neighbors easily. This is the Byzantine Generals Problem.
In this distributed network: each general has a message ledger that is synchronized with other generals in real time. The signature of each general in the ledger can be used to verify the identity. If any messages are inconsistent, you can know which generals the messages are inconsistent with. Even if there is inconsistent information, as long as more than half agree to attack, the minority obeys the majority, and a consensus is reached.
Thus, in a distributed system, although there are bad guys, bad guys can do anything (not restricted by the protocol), such as not responding, sending error messages, sending different decisions to different nodes, and combining different wrong nodes. Get up and do bad things, etc. However, as long as most people are good people, it is entirely possible to achieve consensus in a decentralized manner
Blockchain Core Algorithm 2: Asymmetric Encryption Technology
In the above Byzantine Agreement, if one of the 10 generals Several colleaguesInitiating messages at the same time will inevitably cause chaos in the system, resulting in different attack time plans, making it difficult to act in a consistent manner. Anyone can initiate offensive information, but who will send it? In fact, this only requires adding a cost, that is: only one node can spread the information within a period of time. When a node sends a unified attack message, each node must sign and stamp the message from the initiator to confirm their identity.
It seems today that asymmetric encryption technology can completely solve this signature problem. The asymmetric encryption algorithm uses two different keys for encryption and decryption. These two keys are the "public key" and "private key" that we often hear. Public keys and private keys generally appear in pairs. If a message is encrypted with a public key, the private key corresponding to the public key is required to decrypt it; similarly, if a message is encrypted with a private key, the public key corresponding to the private key is required to decrypt it.
Blockchain Core Algorithm Three: Fault Tolerance Issue
We assume that in this network, messages may be lost, damaged, delayed, sent repeatedly, and the order received is inconsistent with the order sent. In addition, the behavior of nodes can be arbitrary: they can join and exit the network at any time, they can discard messages, forge messages, stop working, etc. Various human or non-human failures may also occur. Our algorithm provides excellent fault tolerance for a consensus system composed of consensus nodes. This fault tolerance includes both security and availability, and is applicable to any network environment.
Blockchain core algorithm 4: Paxos algorithm (consensus algorithm)
The problem solved by the Paxos algorithm is how a distributed system can reach agreement on a certain value (resolution). A typical scenario is that in a distributed database system, if the initial state of each node is consistent and each node performs the same sequence of operations, then they can finally obtain a consistent state. In order to ensure that each node executes the same command sequence, a "consistency algorithm" needs to be executed on each instruction to ensure that the instructions seen by each node are consistent. A general consensus algorithm can be applied in many scenarios and is an important issue in distributed computing. There are two models for node communication: shared memory and message passing. The Paxos algorithm is a consensus algorithm based on the message passing model.
Blockchain Core Algorithm Five: Consensus Mechanism
The blockchain consensus algorithm is mainly proof of work and proof of equity. Taking Bitcoin as an example, in fact, from a technical point of view, PoW can be regarded as reused Hashcash. Generating proof of work is a random process in terms of probability. To mine a new confidential currency, when generating a block, all participants must agree, and the miner must obtain PoW proof of work for all data in the block. At the same time, miners must constantly observe and adjust the difficulty of this work, because the network requirement is to generate a block every 10 minutes on average.
Blockchain Core Algorithm Six: Distributed Storage
Distributed storage is a data storage technology that uses each machine through the networkOn the disk space, these scattered storage resources form a virtual storage device, and the data is scattered and stored in every corner of the network. Therefore, distributed storage technology does not store complete data on each computer, but splits the data and stores it in different computers. It's like storing 100 eggs, not in the same basket, but in different places. The total sum is 100.
- 上一篇： kfc区块链众筹是什么价格啊,区块链众筹什么意思
- 下一篇： nat区块链,区块链 ntf
