Editor's Note: This article comes fromPolkaWorld（ID：gh_6c4c2038ddba), reproduced by Odaily with authorization.
), reproduced by Odaily with authorization.
Blockchain nodes use a consensus engine to reach consensus on the state of the blockchain. This article introduces the basic principles of consensus in blockchain systems, how consensus interacts with the runtime in the Substrate framework, and the consensus engines available in the framework.
mdnice editor
State Machines and Conflicts
The blockchain runtime is a state machine [1]. It has some internal state and state transition functions that allow it to transition from the current state to a future state. In most runtimes, some state has valid transitions to multiple future states, but one transition must be chosen.
The blockchain must agree on the following:
some initial state, called "genesis"
final (current) state
In order to agree on the resulting state after the transition, all operations in the state transition function [2] of the blockchain must be deterministic.
mdnice editor
conflict exclusion
In a centralized system, centralized authorities choose between mutually exclusive alternatives by recording state transitions in the order they see them, and choose the first of competing alternatives in the event of a conflict. In a decentralized system, nodes will see transactions in a different order, so they must use more granular methods to exclude transactions. To complicate matters further, blockchain networks strive to be fault-tolerant, meaning that even if some participants do not follow the rules, the system should continue to provide consensus data.
Aura (Round Robin)
Substrate provides several block construction algorithms and also allows you to create your own:
PoW
BABE (slot based)
mdnice editor
Rules for Fork Selection
A fork choice rule is an algorithm that takes a blockchain and chooses the "best" chain, and thus the chain that should be extended. Substrate demonstrates this concept with SelectChain.
Substrate allows you to write a custom fork selection rule, or use a ready-made one. For example:
longest chain rule
Longest Chain Rule Simply put, the best chain is the longest chain. Substrate provides this chain selection rule with the LongestChain structure. GRANDPA uses the longest chain rule for voting.
GHOST rules
The GHOST rule is that, starting from the genesis block, each fork is resolved by recursively choosing the branch on which the most blocks are built.
block production
PoW
Certain nodes in the blockchain network are able to generate new blocks, a process called authoring. Exactly which nodes can write blocks depends on the consensus engine you use. In a centralized network, a single node can write all the blocks, while in a completely permissionless network, the algorithm must choose the producer of the block at each height.
Substrate provides a PoW block production engine.
slot
Slot-based consensus algorithms must have a known set of validators who can produce blocks. Time is divided into different slots, and in each slot only some validators can produce blocks. Within each slot, the details of which validators can write blocks vary by engine. Substrate offers Aura and Babe, both slot-based block production engines.
Finality
mdnice editor
Finality
Users in any system want to know when their transactions are complete, and blockchains are no exception. In some traditional systems, finality occurs when receipts are handed over or documents are signed.
Using the block production scheme and fork selection rules described so far, transactions are never fully finalized. There is always a chance that a longer (or heavier) chain will come along and restore your transaction. However, the more blocks are built on a particular block, the less likely it is to be reverted. In this way, block production and appropriate fork selection rules provide probabilistic finality.
Some consensus systems link block generation and finality, for example, finality is part of the block generation process, and a new block N+1 cannot be generated until block N is completed. However, Substrate separates these two processes and can use any block engine with probabilistic finality by itself, or couple it with the finality gadget for deterministic finality.
In systems using finality gadgets, the fork selection rules must be modified to take into account the outcome of the finality game. For example, nodes will choose the longest chain containing the most recently completed block, rather than choosing the cycle of the longest chain.
Consensus in Substrate
Aura
mdnice editor
BABE
Aura[4] provides a slot-based block production mechanism. In Aura, a known set of permissions produces blocks in turn.
mdnice editor
Because multiple validators may produce a block in the same slot, forks are more common in BABE than in Aura, even under good network conditions.
PoW
mdnice editor
GRANDPA
mdnice editor
GRANDPA[6] provides block finality. It has a permission set of known weight like BABE. However, GRANDPA does not produce blocks, it only listens to the "gossip" of blocks produced by production engines (such as the three above). GRANDPA validators vote on-chain, not on-block, i.e. they vote for a block that they consider "best", and their vote is transitively applied to all previous blocks. Once more than two-thirds of GRANDPA authorities vote for a particular block, it is considered final.
mdnice editor
To accommodate these consensus features, Substrate has the notion of a DigestItem, a message passed from outside the node (where consensus resides) to the runtime, and vice versa.
learn more
mdnice editor
BABE Research[7]
GRANDPA Research[8]
learn more
Not all consensus protocols define a single canonical chain. Some protocols validate a directed acyclic graph [11] (DAG) when two blocks with the same parent block have no conflicting state changes.
original:https://substrate.dev/
Translation: PolkaWorld Community
