PBFT

From BitcoinWiki
This is the approved revision of this page, as well as being the most recent.
Jump to: navigation, search


PBFT concise description[edit]

Practical Byzantine Fault Tolerance (pBFT) is a specific case and the optimization of the Byzantine Fault Tolerance network ability. It was developed by Barbara Liskov and Miguel Castro and introduced in 1999.

PBFT provides the network with Byzantine state machine approach, meaning implementing a Byzantine Fault Tolerance by copying servers and synchronizing client interactions with server copies. PBFT can ensure the networks fault-tolerance while allowing it to process thousands of operations per second with almost negligible increases in waiting time.

Byzantine Fault Tolerance description[edit]

Practical Byzantine Fault Tolerance (pBFT) is a specific case and the optimization of the Byzantine Fault Tolerance network ability. Byzantine Fault Tolerance is the ability of a network to unmistakably reach a consensus despite malicious nodes’ attempts to propagate false data to other peers.

This ability is crucially important for the distributed networks to prevent the spread of mistakes and incorrect information that is sent by malicious or broken nodes. Networks that are not Byzantine Fault Tolerant if they have no sufficient consensus on the status of the nodes.

For example, a server broke down and is spreading incorrect data. In a Byzantine Fault Tolerant network, the consensus remains between the nodes that are still functioning correctly. Data, spread by the broken server is not corresponding with the data of the other network’s participants and does not affect its maintenance. The failure detecting systems in such network will detect its problem and restrict it from the further operating. In a "Byzantine failure" this server will be seen differently by different nodes. Some nodes will consider it fully functioning and continue gathering its info. It would be hard to automatically shutdown the server due to the lack of consensus between the participants on its condition.

The idea and modern term is derived from the Byzantine Generals' Problem, that is described in the following paragraph.

Byzantine Generals' Problem[edit]

Bizantine Generals Problem

The Byzantine Generals’ Problem is formulated differently in various sources, but no meaning changes were issued, only the stylistic ones. (illustration by Debraj Ghosh, PhD)

Byzantium. The night before the great battle.

The Byzantine army consists of n legions, each commanded by its General. The army also has a commander-in-chief, to whom the generals obey.

At the same time, the Byzantine Empire is in decline, and any of the generals and even the commander-in-chief may be traitors, interested in the defeat of Byzantine.

One of the generals gets the leader of the order course of action at 10 a.m. (time is the same for all and known in advance), namely: "attack the enemy" or "retreat".

Possible outcomes of the battle:

  • If all the faithful generals attack-Byzantium will destroy the enemy (favorable outcome).
  • If all the faithful generals retreat-Byzantium will retain its army (intermediate, neutral outcome).
  • If some loyal generals attack, and some retreat — the enemy will destroy the entire army of Byzantium (unfavorable outcome).

Also one has to note that if the commander in chief a traitor, he can make opposing generals orders to ensure the destruction of the army. Therefore, generals better not trust his orders.

If each General will act completely independently of the other (for example, make a random selection), the probability of a favorable outcome is very low. Therefore, the generals need to exchange information among themselves to come to a common solution.

According to the results of the exchange, each of the loyal generals must obtain a vector of integers of length n, in which the i-th element is either equal to the true number of the I-th army (if its General is loyal), or contains disinformation about the number of the I-th army (if its General is not loyal). At the same time, the vectors obtained by all loyal commanders should be completely identical, even if the info about the enemy army is false.

PBFT functioning[edit]

Liskov and Castro designed the pBFT to be efficiently functioning in asynchronous systems and. It is optimized to remain high-performance with an impressive overhead runtime and only a slight increase in latency.

All of the nodes in the pBFT model are ordered in a way so there is no leader (center) in the network. Every node can communicate the other. This system helps the network to maintain the consensus on the current state of the system amongst the honest nodes. In pBFT, nodes must closely interact with each other. pBFT networks require the network both to validate the messages from other nodes, and to verify the message’s reliability and changelessness.

Leslie B. Lamport proved that in a system with m wrongly working processors ("disloyal generals") it is possible to reach agreement only in the presence of 2m+1 correctly working processors ("loyal generals"). Meaning that strictly more than two thirds of the total number of processors should be honest.

pBFT network implements Lamport’s approach and makes an assumption that ⅔ of the network is loyal. If more than ⅓ of the network’s nodes are malicious it becomes vulnerable to the attacks.

PBFT and cryptocurrency[edit]

In relation to the cryptocurrency industry, pBFT can be an alternative or addition to the proof-of-work (POW) consensus mechanism. While Bitcoin reaches Byzantine Fault Tolerance with its proof-of-work, it has many downsides. Bitcoin consensus demands large energy consumption, is difficult to scale and not very fast.

In pBFT networks, there is no need to validate each transaction as all the nodes of the network are in consensus on the overall state of the network. In make pBFT significantly less computationally intensive and, therefore, less energy demanding.

However, pBFT requires high level of communication between the nodes, which leads to the limitations in terms of the size of the network that can be well governed with pBFT. Smaller possible sizes of such networks can lead to the sybil attack - an attack performed with forging a large number of entities in the network to take over > ⅓ of the network.

With some additional features, pBFT is implemented in the Zilliqa cryptocurrency and in the Hyperledger project. pBFT in Hyperledger is used to provide its projects with additional scalability and in Zilliqa to provide high transactions per second indicator by combining pBFT with traditional Proof-of-Work.

Sources:

See Also on BitcoinWiki[edit]