The dBFT Algorithm
The dBFT(Delegated Byzantine Fault Tolerant) algorithm is based on PBFT(Practical Byzantine Fault Tolerance) algorithm, which is more suitable in blockchain than the latter. PBFT algorithm can solve distributed network consensus effectively, but the more nodes join consensus, the quicker the performance drops, as the time complexity is O(n2). For this reason, NEO proposes an algorithm named dBFT, which combines the characteristics of dPoS. By voting on the blockchain, it decides the name list of consensus nodes for next round, namely authorizing a few nodes to reach consensus and create new block, the other nodes will act as ordinary nodes to receive and verify blocks.
Consensus Node: This node participates in the consensus activity, make a block proposal and vote.
Ordinary Node: This node can transfer, make a transaction, but does not participate in the consensus activity.
Speaker(Unique in each round): The Speaker is responsible to create and transmit a proposal block to the system.
Delegates(Multiple): Delegates are responsible for voting on the proposal block. The proposal will be accepted if more than
2f+1consensus nodes vote it.
fis the limit of Byzantine nodes. More details is in Symbolic Definition below.
Validator candidate: Nodes participating in elections. Candidate nodes for consensus activity.
View: The dataset used during one consensus activity. The view number start from 0 in each round, and the number will increase when it failed to reach consensus in a round.
N: The number of active consensus nodes.
f：The threshold of dishonest consensus nodes (Byzantine nodes) in the system. No more than ⌊(N-1)/3⌋.
v: The view number, start from 0.
h：The current block height during consensus activity.
p: The index of Speaker in array.
p = (h - v) mod N
i：The index of consensus node in array.
t: The block interval, config in
protocol.json/SecondsPerBlock, default 15 seconds.
𝑏𝑙𝑜𝑐𝑘：The proposal block
〈𝑏𝑙𝑜𝑐𝑘〉𝜎𝑖: The block's signature of the
ith consensus node.
Assume the total number of active consensus nodes is
N, up to
f fault tolerance nodes. At the begin, the nodes have the same view number
v = 0, and block height
h = current block height. If not at the same height, it can be achieved by block synchronization between P2Ps. The process involved in the consensus algorithm is as follows:
A user initiate a transaction through a wallet.(to transfer or to deploy smart contract, to issue new asset, etc.)
The wallet signs the transaction data, and broadcasts it to the p2p network.
The consensus nodes receive the transaction, and put into the memory pool.
In a certain round of consensus, the speaker packages transactions from the memory pool into a new proposal block, then broadcasts it as 〈𝑃𝑟𝑒𝑝𝑎𝑟𝑒𝑅𝑒𝑞𝑢𝑒𝑠𝑡,ℎ,𝑣,𝑝,𝑏𝑙𝑜𝑐𝑘,〈𝑏𝑙𝑜𝑐𝑘〉𝜎𝑝〉.
Load all the transactions in memory pool.
IPolicyPluginplugin, sort and filter the transactions.
Calculate the network fee (
= inputs.GAS - outputs.GAS - transactions_system_fee), and take it as the reward for the current Speaker in
Combine the above transactions and the previous validators votes to calculate the hash of next round consensus nodes, and assign the hash of multi-signature script to
block.NextConsensus, locking the consensus nodes of the next round.
Set the timestamp of block to the current time and calculate the signature of the speaker.
invmessage, attached with transaction's hash except
MinerTransaction, to notify other nodes to synchronize the transactions in the proposal block.
Delegates recieve the proposal block, and verify it, then broadcast 〈𝑃𝑟𝑒𝑝𝑎𝑟𝑒𝑅𝑒𝑠𝑝𝑜𝑛𝑠𝑒,ℎ,𝑣,𝑖,〈𝑏𝑙𝑜𝑐𝑘〉𝜎𝑖〉 message.
Any consensus node, on receiving at least
n-f〈𝑏𝑙𝑜𝑐𝑘〉𝜎𝑖 , reaches a consensus and publishes the new block.
Any node, on receiving a new block, deletes all transactions in the block from memory pool. If the node is a consensus node, then it starts the next round consensus.
The algorithm can be divided into three stages.
PRE-PREPARE, the speaker of this round is responsible for broadcasting
Prepare-requestmessage to the delegates and initiating the proposal block.
PREPARE, on receiving
PRE-PREPARE, the delegates broadcast
Prepare-Responseif the proposal block is verified successfully. When a consensus node receives at least
N-f〈𝑏𝑙𝑜𝑐𝑘〉𝜎𝑖, it enters the third stage.
PERSIST, the node publishes a new block and enter the next consensus round.
- At the very beginning of the blockchain network,
StandbyValidatorsare read from the configuration file
protocol.jsonas backup validators. For there isn't any enrolled validator yet.
- Unlike ordinary block, the Genesis block is the first block in the blockchain by default, which is not published by consensus nodes. In the Genesis block, the field
NextConsensusis set to the hash value of
StandbyValidators, so the consensus nodes for the next block is determined.
As the process of consensus is in an open p2p network environment, there are cases that no consensus can be reached. For example a key consensus message is delayed in the network, or a dishonest node sends illegal data, etc. The consensus nodes can initiate a
ChangeView proposal in such situations. They will enter a new view with new speaker, and restart consensus, after receiving at least
ChangeView messages with the same view number.
The View-Change process will be initiated, when one consensus node could not reach consensus in 2v+1⋅ 𝑡 time interval, or it received an illegal proposal(invalid transactions).
Given 𝑘 = 1, 𝑣𝑘 = 𝑣 + 𝑘；
𝑖th node initiate a 〈𝐶ℎ𝑎𝑛𝑔𝑒𝑉𝑖𝑒𝑤,ℎ,𝑣,𝑖,𝑣𝑘〉 proposal.
When any one node received at least
ChangeViewwith the same 𝑣𝑘 from different consensus nodes, the View Change will be completed. Set 𝑣 = 𝑣𝑘 and start the consensus process.
If the View Change is not completed in 2𝑣𝑘 +1 ⋅ 𝑡 time interval, then increase k and back to step 2).
With the increase of k, the waiting time before another change view will increase exponentially, which can avoid frequent View Change and make the nodes reach agreement within a reasonable time. The original view
v is still valid until the completion of View Change, avoiding unnecessary View Change due to accidental network latency.
In case of dead links, please contact firstname.lastname@example.org