Is Paxos a blockchain communication protocol

The way in which people keep accounts together is also known as "distributed" or "decentralized", because everyone keeps accounts, and the accuracy of the account book is determined by the program algorithm, not by an authoritative organization

this is the blockchain, the core is finished, blockchain is so simple, a common account book

six core algorithms of blockchain Technology:

blockchain core algorithm 1: Byzantine agreement

the story of Byzantine is like this: the Byzantine Empire has great wealth, and the surrounding 10 neighbors have been around for a long time, but the Byzantine walls stand tall and firm, No single neighbor has been able to successfully invade. Any single neighbor's invasion will fail, and at the same time, it may be invaded by other nine neighbors. Byzantine Empire's defense ability is so strong that at least more than half of its ten neighbors attack at the same time before it can be broken. However, if one or several of the neighbors agree to attack together, but betray in the actual process, then the invaders may be annihilated. So each side was careful and could not easily trust its neighbors. This is the question of Byzantine Generals

blockchain core algorithm 2: asymmetric encryption technology

in the above Byzantine agreement, if several of the 10 generals send messages at the same time, it is bound to cause confusion in the system, resulting in different attack time schemes and inconsistent actions. Anyone can send the message of attack, but who will send it? In fact, it only needs to add a cost, that is, only one node can spread information in a period of time. When a node sends a unified attack message, each node must sign and seal to confirm its identity when receiving the message from the initiator

blockchain core algorithm 3: fault tolerance problem

we assume that in this network, messages may be lost, damaged, delayed and sent repeatedly, and the order of receiving is inconsistent with the order of sending. In addition, the behavior of nodes can be arbitrary: they can join or exit the network at any time, they can discard messages, forge messages, stop working and so on, and they may also have all kinds of human or non-human failures. Our algorithm provides fault tolerance for consensus system composed of consensus nodes, which includes both security and availability, and is suitable for any network environment

blockchain core algorithm 4: Paxos algorithm (consistency algorithm)

the problem solved by Paxos algorithm is how a distributed system can reach an agreement on a certain value (decision). 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 operation sequence, then they can finally get a consistent state. In order to ensure that each node executes the same command sequence, it is necessary to execute a "consistency algorithm" on each instruction to ensure that the instructions seen by each node are consistent. A general consistency algorithm can be applied in many scenarios, which is an important problem in distributed computing. There are two models of node communication: shared memory and message passing. Paxos algorithm is a consistency algorithm based on message passing model

blockchain core algorithm 5: consensus mechanism

blockchain consensus algorithm is mainly workload proof and equity proof. Take bitcoin as an example. In fact, from a technical point of view, POW can be regarded as a reusable hashcash, and the generation workload proves to be a random process in probability. When mining a new secret currency and generating a block, the consent of all participants must be obtained, and the miner must obtain the pow work proof of all data in the block. At the same time, miners have to constantly observe and adjust the difficulty of this work, because the requirement for the network is to generate a block every 10 minutes on average

blockchain core algorithm 6: distributed storage is a kind of data storage technology, which uses the disk space of each machine through the network, and forms a virtual storage device with these scattered storage resources, and the data is stored in every corner of the network. Therefore, distributed storage technology does not store complete data in each computer, but stores the data in different computers after cutting. It's like storing 100 eggs, not in the same basket, but separately in different places. The total number is 100. Want to learn more, you can make more use of network search, network search results - small knowledge

Paxos algorithm is Leslie Lamport, which is "La & quot;" in latex;, This person is now in Microsoft Research Institute) in 1990 proposed a consistency algorithm based on message passing. This algorithm is considered to be the most effective of the similar algorithms

Lambert's Paxos algorithm consists of two parts:

one is basic Paxos algorithm, which describes how to reach a consensus on a certain value among multiple nodes

the other is the idea of multi Paxos, which describes the implementation of multiple basic Paxos instances to reach a consensus on a series of values

but the idea of multi Paxos mentioned by Lambert lacks the necessary details of code implementation (such as how to elect leaders), so it is difficult to understand. Basic Paxos is the core of multi Paxos

extended data

background

the problem solved by Paxos algorithm is how to reach an agreement on a certain value (decision) in a distributed system. 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 operation sequence, then they can get a consistent state at last

in order to ensure that each node executes the same command sequence, it is necessary to execute a "consistency algorithm" on each instruction to ensure that the instructions seen by each node are consistent

a general consistency algorithm can be applied in many scenarios, which is an important problem in distributed computing. Therefore, the research on consistency algorithm has not stopped since 1980s. There are two models of node communication: shared memory and messages passing. Paxos algorithm is a consistency algorithm based on message passing model

It is proved that if a protocol satisfies b1-b3 constraints, then consistency can be guaranteed. The basic protocol is the restricted version of the preliminary protocol, which ensures the consistency. Complete Synod protocol further limits basic protocol to meet consistency and progress requirements. The specific process of these three algorithms is described below. If B1 is satisfied, the number of an election initiated by a pastor must satisfy the partial order relation. One way is that each initiating pastor uses an increasing number as the election number, but in this way, the pastor cannot immediately know whether the number they selected has been used by other pastors. Another method is to use the number + pastor's name as the election number, so as to avoid the use of their own election number by other pastors
If B2 is satisfied, the quorum of each election must be a majority set Q, so that any two elections will have a common pastor. In the original text, Lamport uses weight as a metaphor. People who are overweight are more likely to stay in the parliament hall, so that they can use pastors who are more than half of their weight as the majority. As for the actual situation, what most of the sets are depends on the specific situation
to meet B3, each pastor must find B before launching an election_ Maxvote (B, Q, b) of each priest Q in QRM< According to the above requirements, we can get the initial agreement:
1. Pastor P selects an election number B and sends nextball (b) to other pastors
2. After receiving nextball (b), other pastors Q returns lastvote (B, V) to pastor P, v = maxvote (B, Q, b) $which is the largest affirmative vote of Q less than B number. In order to guarantee B3, Q cannot be in B and B_ Vote for the election between BAL If Q sends last vote (B, V) and votes for a new election, then V is not the largest vote for Q)
3. Pastor P receives last vote (B, V) from each pastor Q in a large set of Q, and initiates a new election with the number of B, the quorum of Q, and the law D satisfies B3. Then pastor P writes the law on the back of his account and sends beginballot (B, d) to each pastor in Q
4. After receiving beginballot (B, d), pastor Q decides whether to vote for the election. If yes, he will send a vote (B, q) to pastor P
5. If pastor P receives vote vote (B, q) from each pastor Q in Q, he will write law d into his account and send success (d) message to all pastors
6. After receiving the success (d) message, pastor Q writes law d into his account
note: the first step indicates that the pastor who initiated the law wants the number of the next election to be B. Pastor Q responds to pastor P's request with lastvote (B, V), that is to say, when passing the law to pastor P, v = maxvote (B, Q, b) is guaranteed to be changed. Specifically, it is not in B and B_ Vote for the election between BAL
in the third step, the law D needs to meet B3. I am a little confused here. The value in the actual system is determined by the client, not B3. Here we will use the above example of key value database to clarify the following idea: when a node / pastor initiates an update for the first time, it means that B is an empty set, and the operation of initiating an update / election continues until all the quorum vote for the law (that is, if the node of the priority set updates the value of the key value, it is considered that the update is successful), B3 corresponds to the situation that if the previous update fails, the new election value needs to be maintained. In the fourth step, the pastor is allowed not to send vote (B, q) or send it several times. The corresponding message may not be sent or sent many times e to communication failure. Once the priest votes in favor, confirm that the value can be changed
considering that the law D was written into the account by Pastor Q in the sixth step, it is possible that pastor P wrote the law into his own account in the fifth step, and then sent success (d) to other pastors, which was not written into his own account because of correspondence or pastor leaving the Council hall, resulting in inconsistency. So the real time to write it into the accounts should be in the fourth step, when pastor Q sends pastor P's affirmative vote, he writes the law into his own accounts. It is not necessary to consider how to ensure that the law written in step 4 will lead to inconsistency, because if the law is not passed, there will be more elections to ensure consistency. Later also talked about when the law is not written into the accounts for the first time. The preliminary protocol requires every priest to keep (I) every election he initiates II) each of his votes in favour III) each $lastvote $he sends. In order to simplify the data that priests need to save, we make a restriction on the above protocol and get the basic protocol. First, three new parameters are introced:
lasttried [P] the last election initiated by Pastor P
prevvote [P] pastor P's latest vote
nextbal [P] the maximum value of B of the election number received by Pastor P, that is, the maximum election number that pastor P participates in
in the initial agreement, each pastor can launch any election at the same time, In the basic agreement, each priest is required to launch only one election last tried [P]. Once an election is launched, the information of the previous election is not important. In the initial agreement, each priest is required not to be in B_ BAL and B vote in favor of each other. In the basic agreement, it is more strictly required not to vote in favor of the election less than B. Then the basic protocol can be summarized as the following steps:
1. Pastor P selects an election number B larger than lasttried [P], and sends nextball (b) to other pastors
2. Pastor Q receives nextball (b) and B & gt; After nextbal [q], set nextbal [q] = B, and then send lastvote (B, V) to pastor P, where V = = prevba [q] If B is less than or equal to nextbal [q], then do not reply)
3. Each pastor in a certain set Q receives the last vote (B, V) message, pastor P initiates an election with the number of B, the quorum of Q, and the law of D (satisfying B3), and sends beginballot (B, d) to each pastor in Q If there is no pastor who satisfies any majority of set Q, return to the first step)
4. Pastor Q receives beginballot (B, d), decides to vote for it, sets prevvote [P] as the vote, and sends the vote (B, q) to pastor P If we find that B is not equal to nextbal [q] after receiving beginballot (B, d), we will ignore this message, which means that pastor Q has received other elections with larger number ring this period)
5. Pastor P receives voted (B, d) from each pastor Q in most of the set Q, and B = = lasttried [P], then we think that this election is successful and record law D in the account, And send success (d) to each priest Q in Q
6. After receiving the success (d) message, each pastor will write the law into the account
the basic protocol is a restricted version of the original protocol, because both of them have no behavior requirements for priests, so they do not guarantee the process (QS). The following is a protocol to guarantee the process complete synode protocol. The basic agreement guarantees consistency, but it does not guarantee any process, because it only states what the pastor may do and does not require what the pastor should do. In order to achieve the above mentioned process requirements, we need to add some additional requirements to enable the priests to complete 2-6 steps as soon as possible
consider a case in which if the election number B received by Pastor Q in the second step is larger than that received before, then pastor Q has to give up all the elections received before. However, before the confirmation of the election No. B, a larger number of "B" may be received, so that no law can be passed and the process can not be guaranteed. Therefore, in order to meet the needs of the process, we need to launch another election after one election is successful. First of all, we should know the time for the server to deliver the message and the pastor to process the message. In the network, we often set a timeout to achieve this. Similarly, if the pastor does not receive a reply from the server after a certain period of time, he will think that the server or the corresponding pastor has left the Council hall
suppose the pastor performs an action within 7 minutes and the server delivers a message within 4 minutes, then a pastor P sends a message to pastor Q, hoping that the reply time should be within 22 minutes (7 + 4 + 7 + 4 minutes)
with the assumption of the above time and considering the situation discussed above, if the pastor P who initiated the election expects to receive a reply from other pastors in the second and fourth steps within 22 minutes, if not, some pastors or waiters may have left the Council hall, or some pastors may have initiated an election with a larger number. In both cases, pastor P should terminate the election and start a new election. In order to avoid that the new election number is too small to be executed, he needs to get the latest election number from other pastors, so as to select a larger number to start the election
assuming that pastor P is the only pastor who can initiate an election and there are a large number of pastors gathered in the assembly hall, we can guarantee that a law will be passed in 99 minutes: a law with a larger number will be found in 22 minutes, and the largest number will be obtained and a larger number will be selected in 22 minutes, Complete 1-6 steps in 55 minutes to complete a successful election (question: since only pastor P can initiate an election, then the number is controlled by him. It seems unnecessary to find and choose a larger number in the first two steps. A: not all elections are sponsored by the president. The president will assign election numbers to other priests who wish to sponsor elections. From the above process, we find that a complete parliamentary agreement needs a process of electing the president, and the election algorithm of the president is not the focus of the article, so only t minutes are used to replace the time of electing the president in the article, so that a law can be passed in T + 99 minutes
the way to select president in this paper is to send his last name to all the priests in the assembly hall. If a priest does not receive a last name in the alphabet within T-11 minutes, he thinks he is president (I think the broadcast weight should be good, too, Doesn't it mean heavier people stay in the chamber longer. There is another detail: when electing the president, each pastor needs to send his last tried [P] to other pastors, so that the president can choose a sufficiently large number in the first election
so far, by electing the president and setting the timeout, the complete parliamentary agreement can guarantee the process
multi law Congress agreement
in the last section of the complete Synod protocol, after the president is elected, every pastor who wants to launch an election informs him, and the president assigns an election number to the pastor to pass only one law at a time. The multi law parliament agreement selects a president to pass a series of laws, and only needs to implement the first two steps once
specific