Methods and systems for fast consensus within distributed ledgers
Blockchains operate as decentralized, self-regulating systems that involve contributions from hundreds of thousands of participants who work on the verification and authentication of transactions occurring on the blockchain. The consensus mechanism within such a system provides the set of rules that determine the legitimacy of contributions made by the various participants of the blockchain. The consensus mechanism should not only be tolerant of faults but also have low latency in establishing consensus. Prior art solutions either could tolerate at most (n+1)/5 faults reaching consensus or execution of three or more communication steps to provide tolerance of arbitrary (Byzantine) faults or cannot guarantee strong safety property for an honest primary. To improve the speed of the consensus mechanism the inventors have established a BFT consensus protocol that operates with just two communication steps. The proposed protocol tolerates at most (n−1)/3 faults and provides strong safety guarantees for an honest primary.
1 . The method comprising
providing a plurality of n nodes communicating via a communications network, each node performing tasks relating to the distributed ledger and comprising a microprocessor for executing software instructions stored within a memory accessible to the microprocessor; and
providing the memory storing the software instructions where the software instructions relate to processing blocks of the distributed ledger and a protocol for handling Byzantine faults within a subset of the plurality of n nodes; wherein
the protocol operates in two modes, a normal mode and a view change mode;
the protocol achieves consensus whilst operating in the normal mode with only two communication steps between the plurality of n nodes via a communications network, these comprising:
a first communication step of the two communication steps being receipt of a message via the communications network at each node of the plurality of n nodes of a proposal message signed and broadcast by a primary node of the plurality of n nodes via the communications network relating to a block b; and
a second communication step of the two communication steps being transmittal of another broadcast message via the communications network comprising a vote for the block b from each the node of the plurality of n nodes which performs a successful safety check of the signed proposal message after successful verification of a primary signature within the signed proposal message and a message format of the signed proposal message;
each node of the plurality of n nodes commits the block b upon receipt of 2f+1 votes for the block b from the plurality of n nodes;
the protocol can reach consensus when a number f of the plurality of n nodes exhibit a Byzantine fault; and
f is the upper bound on number of Byzantine nodes and f=(n−1)/3.
2 . The method according to claim 1 , wherein
each node of the plurality of n nodes that commits to the block b sends a reply message to each client for whom a transaction is included within the block b;
each client establishes that its transaction is committed upon receipt of 2f+1 reply messages; and
the primary also commits the block b upon receipt of the 2f+1 votes.
3 . The method according to claim 1 , wherein
each node of the plurality of n nodes that commits to the block b further builds a quorum certificate (QC) from the votes it received for block b; and
the QC is subsequently employed either as a proof of commit during a subsequent view change mode to replace the primary or as proof of commit to an application executing over the top of the protocol relating to transactions.
4 . A system comprising:
a plurality of n nodes communicating via a communications network, each node performing tasks relating to a distributed ledger and comprising a microprocessor for executing software instructions stored within a memory accessible to the microprocessor; and
the memory storing the software instructions where the software instructions relate to processing blocks of the distributed ledger and a protocol for handling Byzantine faults within a subset of the plurality of n nodes; wherein
the protocol operates in two modes, a normal mode and a view change mode;
the protocol achieves consensus whilst operating in the normal mode with only two communication steps between the plurality of n nodes via a communications network, these comprising:
a first communication step of the two communication steps being receipt of a message via the communications network at each node of the plurality of n nodes of a proposal message signed and broadcast by a primary node of the plurality of n nodes via the communications network relating to a block b; and
a second communication step of the two communication steps being transmittal of another broadcast message via the communications network comprising a vote for the block b from each the node of the plurality of n nodes which performs a successful safety check of the signed proposal message after successful verification of a primary signature within the signed proposal message and a message format of the signed proposal message;
each node of the plurality of n nodes commits the block b upon receipt of 2f+1 votes for the block b from the plurality of n nodes;
the protocol can reach consensus when a number f of the plurality of n nodes exhibit a Byzantine fault; and
f is the upper bound on number of Byzantine nodes and f=(n−1)/3.
5 . The system according to claim 4 , wherein
each node of the plurality of n nodes that commits to the block b sends a reply message to each client for whom a transaction is included within the block b;
each client establishes that its transaction is committed upon receipt of 2f+1 reply messages; and
the primary also commits the block b upon receipt of the 2f+1 votes.
6 . The system according to claim 4 , wherein
each node of the plurality of n nodes that commits to the block b further builds a quorum certificate (QC) from the votes it received for block b; and
the QC is subsequently employed either as a proof of commit during a subsequent view change mode to replace the primary or as proof of commit to an application executing over the top of the protocol relating to transactions.
7 . Non-volatile non-transitory storage media storing computer executable instructions, wherein the computer executable instructions when executed configure each microprocessor of a node of a plurality of n nodes to execute a process for processing blocks of a distributed ledger; wherein
the process includes a protocol for handling Byzantine faults within a subset of a plurality of n nodes which communicate information relating to the distributed ledger via a communications network;
the protocol operates in two modes, a normal mode and a view change mode;
the protocol achieves consensus whilst operating in the normal mode with only two communication steps between the plurality of n nodes via a communications network, these comprising:
a first communication step of the two communication steps being receipt of a message via the communications network at each node of the plurality of n nodes of a proposal message signed and broadcast by a primary node of the plurality of n nodes via the communications network relating to a block b; and
a second communication step of the two communication steps being transmittal of another broadcast message via the communications network comprising a vote for the block b from each the node of the plurality of n nodes which performs a successful safety check of the signed proposal message after successful verification of a primary signature within the signed proposal message and a message format of the signed proposal message;
each node of the plurality of n nodes commits the block b upon receipt of 2f+1 votes for the block b from the plurality of n nodes;
the protocol can reach consensus when a number f of the plurality of n nodes exhibit a Byzantine fault; and
f is the upper bound on number of Byzantine nodes and f=(n−1)/3.
8 . The non-volatile non-transitory storage media according to claim 7 , wherein
the safety check of the signed proposal message by a node of the plurality of n nodes accepts two parameters, these being the received block b and a quorum certificate built from 2f+1 votes received by that node of the plurality of n nodes for the previous block within the distributed ledger employed to generate block b.
9 . The non-volatile non-transitory storage media according to claim 7 , wherein
each node of the plurality of n nodes that commits to the block b sends a reply message to each client for whom a transaction is included within the block b;
each client establishes that its transaction is committed upon receipt of 2f+1 reply messages; and
the primary also commits the block b upon receipt of the 2f+1 votes.
10 . The non-volatile non-transitory storage media according to claim 7 , wherein
each node of the plurality of n nodes that commits to the block b further builds a quorum certificate (QC) from the votes it received for block b; and
the QC is subsequently employed either as a proof of commit during a subsequent view change mode to replace the primary or as proof of commit to an application executing over the top of the protocol relating to transactions.