31

Can anyone explain PBFT Algorithm in detail without giving any link for the same? And how it works in hyperledger. So, once the transaction is sent to the blockchain:

  1. Who validates the transaction?

  2. How the consensus is achieved on the transaction?

  3. How the transaction is committed to the blockchain?

Narendranath Reddy
  • 3,833
  • 3
  • 13
  • 32
Saurabh
  • 1,249
  • 2
  • 13
  • 14

4 Answers4

23

"Hyperledger" is a blockchain consortium under The Linux Foundation. Currently there are at least 4 different implementations of blockchain frameworks under Hyperledger:

  • Fabric (IBM)
  • Corda (R3)
  • Iroha
  • Sawtooth Lake (Intel)

In Fabric v0.6:

All validation peers keep open connection to each other. You can submit your transaction to any of them, and this transaction will be broadcasted to other peers in the network. One of peer is elected as "leader". At the moment when a new block is going to be generated:

  1. The leader orders the transactions candidates that should be included in a block, and broadcasts this list of ordered transactions to all other validation peers in the network.
  2. When each of the Validation Peers receives the ordered list of transactions, each validation peer does the following:
    1. It starts executing the ordered transactions one by one.
    2. As soon as all the transactions are executed, it will calculate the hash code for the newly created bloc (the hash code includes hashes for executed transactions and final state of the world).
    3. Then it broadcasts its answer (the resulting hash code) to other peers in the network, and starts counting the responses from them.
    4. If it sees that 2/3 of all validation peers have the same hash code, it will commit the new block to its local copy of the ledger.

In Fabric v1.0:

This version is still in development. In v1 the is no "leader", separate service "Orderer" is responsible for transactions order in a block. This service is pluggable and announced that the will be 3 different options:

  1. Solo - single process is responsible for ordering
  2. Kafka orderer - leverages the Kafka pubsub system to perform the ordering
  3. PBFT - is not implemented yet.

In Corda:

PBFT is not used. This implementation uses another architecture approach.

Dan Anderson
  • 2,265
  • 1
  • 9
  • 20
Sergey Balashevich
  • 2,101
  • 14
  • 11
  • Thanks for your detailed response. Can you please explain consensus mechanism in Ethereum. – Saurabh Jan 22 '17 at 09:41
  • 2
    Ethereum uses "proof of work" as a consensus algorithm. There are many good articles about this concept: https://en.bitcoin.it/wiki/Proof_of_work – Sergey Balashevich Jan 30 '17 at 10:43
  • 1
    @SergeyBalashevich I have doubt. All these peers are on network, does it mean on different servers on different network location. OR it means on the same VM server ? If all the nodes are on the same network then what is the use of having so many nodes.? – Sushil Mar 17 '17 at 09:51
  • Peers are expected to be deployed on different servers. These servers can be in different network locations(bigger delay on network communication) or in the same network(faster). – Sergey Balashevich Mar 22 '17 at 12:41
  • The explanation for 0.6 (and how PBFT works) is entirely wrong. Source: I am one of the developers of the PBFT package in Fabric. – Kostas Mar 22 '17 at 15:10
  • 1
    it would be great if you can help with answer improvement – Sergey Balashevich Mar 22 '17 at 16:53
  • @Kostas just curious if you can share a link to better description? I got this one from Gari Singh (IBM) on a HL meetup in Boston last year. – Sergey Balashevich Mar 27 '17 at 08:50
  • 2
    Sergey: The [Castro-Liskov paper that describes the PBFT algorithm](http://dl.acm.org/citation.cfm?id=571640) is the best reference. – Kostas Mar 27 '17 at 15:39
  • 1
    @kostas Thank you for the answer. This document is a perfect description for PBFT algorithm, but what about implementation in Fabric v0.6? It would be greate if we can go through points above one-by-one. The most interesting question is: Do Fabric v0.6 has a Leader(on of VPs) whos responsibility is to order transactions befor new block is generated ? – Sergey Balashevich Mar 27 '17 at 16:07
  • 1
    Sergey: Yes. The implementation in 0.6 is follows the 3-phase protocol described in the paper precisely. This is not captured in your response. – Kostas Mar 28 '17 at 01:26
  • @kostas "pre-prepare" Phase - block is send to all other members in network (covered in point 1). "prepare" Phase - peer executes all transactions in block and sends answer to other peers (covered in points 2, 3 and 4). "Commit" Phase - if 2/3 of nodes have the same answer the block is accepted (covered in point 5). Which of phases/steps is wrong or missing from your point of view ? – Sergey Balashevich Mar 29 '17 at 09:44
  • @SergeyBalashevich: There is no execution during the ordering phase, this is what you're getting wrong. – Kostas Mar 30 '17 at 15:02
  • @Kostas Correct, as it described in step one "Leader orders transactions in a block and broadcasts this list to...". There is no statement that transactions are executed in step 1. Execution starts only in step 2 "When Validation Peer receives ordered list of transactions it starts executing them one by one.". Do you have any other comments ? – Sergey Balashevich Mar 30 '17 at 21:25
  • 1
    @SergeyBalashevich: I don't have any other comments because this is precisely what you're getting wrong. Steps 2 to 5 are wrong. I'll submit an answer that describes what's going on over the weekend. – Kostas Mar 31 '17 at 23:05
  • 2
    @Kostas Still curious what exactly is wrong with steps 2-5, did you have a time to prepare your answer ? – Sergey Balashevich Apr 10 '17 at 09:42
  • The last statement regarding Corda is wrong. Corda nodes may use BFT-SMART consensus for notaries (even though this is still experimental currently). See here: https://docs.corda.net/running-a-notary.html – Sigmatics Apr 16 '19 at 08:27
4

In Corda, consensus is provided by notaries. It is up to the notary operator which consensus algorithm they use. BFT is one option. You can see a Corda BFT notary sample here: https://github.com/corda/corda/tree/master/samples/notary-demo.

To answer your questions:

(1). Who validates the transaction?

The transaction is validated by a cluster of one or more notaries. Notaries are nodes with the sole purpose of deconflicting double-spend attempts.

(2). How the consensus is achieved on the transaction?

Using a standard BFT algorithm. Each node in the notary cluster votes on whether they consider the transaction to be a double-spend attempt. The final decision is based on a majority rule, and can tolerate up to 1/3rd of the nodes in the cluster being malicious.

(3). How the transaction is committed to the blockchain?

In Corda, there is no central store of information that the transaction is committed to. The notary cluster simply adds the spent state reference to an internal database table. It will check future attempts to spend states against this table, and reject the spending attempt if the state reference is already stored there.

Joel
  • 22,762
  • 5
  • 26
  • 41
2

pbft is a consensus algorithm given by Barbara Liskov and Miguel Castro in 1999 in order to prevent malicious attacks as malicious attacks and software errors can cause faulty nodes to exhibit Byzantine (i.e., arbitrary) behavior. pBFT was designed to work efficiently in asynchronous systems as compared to previous bft algorithms which only worked on synchronous systems.

here is the research paper which states that

Practical algorithm for state machine replication that tolerates Byzantine faults. The algorithm offers both liveness and safety provided at most ⌊n-1 / 3⌋ out of a total of replicas are simultaneously faulty. This means that clients eventually receive replies to their requests and those replies are correct according to linearizability. The algorithm works in asynchronous systems like the Internet and it incorporates important optimizations that enable it to perform efficiently

The algorithm works roughly as follows:

  1. A client sends a request to invoke a service operation to the primary
  2. The primary multicasts the request to the backups
  3. Replicas execute the request and send a reply to the client
  4. The client waits for 1 replies from different replicas with the same result; this is the result of the operation.

Like all state machine replication techniques, two requirements are imposed on replicas:

  • They must be deterministic
  • They must start in the same state.

Given these two requirements, the algorithm ensures the safety property by guaranteeing that all nonfaulty replicas agree on a total order for the execution of requests despite failures.

Limitations of pbft:

The pbft consensus algorithm works efficiently only when the number of nodes in the distributed network are less.

Hyperledger Fabric:

According to Hyperledger Fabric v1.4 the consensus mechanisms which are currently used include SOLO, Kafka, and Raft.

Hyperledger Sawtooth:

According to Hyperledger Sawtooth, how pbft is used is well explained here

asing177
  • 934
  • 2
  • 13
  • 34
0

The above is missing the Consensus algorithms from Hyperledger Sawtooth, so here they are:

  • PoET Proof of Elapsed Time (optional Nakamoto-style consensus algorithm used for Sawtooth). PoET with SGX has BFT. PoET Simulator has CFT. Not CPU-intensive as with PoW-style algorithms, although it still can fork and have stale blocks . See PoET specification at https://sawtooth.hyperledger.org/docs/core/release s/latest/architecture/poet.html
  • RAFT Consensus algorithm that elects a leader for a term of arbitrary time. Leader replaced if it times-out. Raft is faster than PoET, but is not BFT (Raft is CFT). Also Raft does not fork. Hyperledger Sawtooth has the advantage of having Unpluggable Consensus. An algorithm can be changed without reinitializing the blockchain or even restarting the software.

Here are some other consensus algorithms:

  • PoW Proof of Work. Completing work (CPU-intensive Nakamoto-style consensus algorithm). Usually used in permissionless blockchains
  • PoS Proof of Stake. Nakamoto-style consensus algorithm based on the most wealth or age (stake)
  • PBFT Practical Byzantine Fault Tolerance. A "classical" consensus algorithm that uses a state machine. Uses leader and block election. PBFT is a three-phase, network-intensive algorithm (n^2 messages), so is not scalable to large networks
Dan Anderson
  • 2,265
  • 1
  • 9
  • 20