September 23, 2022

Beosin Web3.0 Classroom: Cross-chain Bridge (I) — Introduction of Polkadot

In this cross-chain bridge series, we will select some of the representative cross-chain bridge projects to conduct an in-depth analysis of their architecture, algorithm, mechanism, etc. Today we will look at Polkadot.

Polkadot is a heterogeneous multi-chain framework, which mainly consists of Relay chain, Parachain, and Bridge. Among them, Parachains are responsible for specific business scenario implementation, which allows parallel processing of transactions and each parallel chain has a unique state transition function (STF). Relay chains are responsible for the consensus verification of the whole network. As long as the logic code of a chain can be compiled into Wasm and comply with the Relay Chain API, it can be connected to the Polkadot network ecosystem as a parallel chain. The bridge connects the polkadot ecosystem with external independent blockchains (e.g. Ethereum). The Polkadot system architecture is shown in the following figure.

1 Hybrid Consensus

The consensus block-producing process for Polkadot’s entire network is minly as follows.

l. Parachain Phase: The Collator collects transactions on the parachain to packetize candidate blocks and send them to the validator of that parachain. Among them, the candidate block may be invalid and it must be checked for validity before it can be included in the relay chain.

2. Relay chain submission phase: The validator will validate the candidate block by using the validation function exposed by the parachain registration code. If the validation is successful, this validator passes it to other validators in the network to continue the validation. Otherwise, the candidate block is judged to be invalid. When the candidate block is passed by more than half of the validators, the validator generates a candidate receipt containing information such as: parallel chain ID, collator ID and signature, state root of the parallel chain before the candidate block is executed, and state root of the parachain after the candidate block is executed, which is eventually included in the state of the relay chain.

3. Availability and unavailability sub-Protocols

4. Level 2 GRANDPA approval validity check

5. Byzantine fault-tolerant finality widget is called to consolidate the chain

In traditional PoS systems, block generation depends on the amount of tokens held rather than arithmetic power, and the higher the number of staked tokens the higher the probability of becoming a validator, and the greater the impact on the blockchain system. Therefore, certain measures must be taken to reduce this possible risk of centralization, and having specialized personnel and equipment to maintain the number of validator candidates in the system would increase operational costs. Therefore, for systems with a large number of validators, it is preferable to create a pool of candidate validators off-chain and randomly select validators from the candidates. The validator selection algorithm used by Polkadot is NPoS.

Firstly we will introduce probabilistic and provable certainty in consensus algorithms. A Satoshi Nakamoto blockchain running PoW can then only achieve probabilistic and reach a final consensus. Where probabilistic means that after a given block, we can calculate the probability of it being on the longest chain based on the number of blocks connected thereafter. Final consensus means that at some point in the future, all nodes will agree on a set of data, but this final consensus may take a long time and it is impossible to determine how much time it will take. However, deterministic tools like GRANDPA (GHOST-based Recursive ANcestor Deriving Prefix Agreement) or Ethereum’s Casper FFG can provide stronger guarantees of block finalization. After some process of Byzantine protocol, irreversible consensus, called provable certainty, can be formed.

Polkadot uses a hybrid consensus algorithm combining BABE (Blind Assignment for Blockchain Extension) and GRANDPA algorithms in order to guarantee both probabilistic and provable certainty. Among them, the BABE algorithm is responsible for block production, while the GRANDPA algorithm is responsible for the finalizing of blocks in the blockchain.

1.1 GRANDPA

GRANDPA stands apart from other Byzantine fault-tolerant (BFT) blockchain algorithms in that validators vote on chains, not blocks. This process allows several blocks to be finalized in one round. GRANDPA, like other BFT derivatives, has O(n²) complexity. That is to say, if you double the number of nodes, you have to send four times the number of messages. Polkadot separates block production from finality process, an approach that improves the efficiency of the entire consensus system, increases the efficiency of block production (O(n) for BABE), and can finalize several of them together in one round.

GRANDPA will select the highest block number that has the highest number of validators and can be considered as the final block. Look at the log in the Kusama node as an example.

Notice that in one round, GRANDPA finalized three blocks (664,254 to 664,256).

https://polkadot.network/blog/polkadot-consensus-part-2-grandpa/

The dark gray blocks on the left are the blocks that were previously finalized, and the gray oval on the right represents the validator, who voted for a new round of candidate blocks and finalized three of them. It can be found that the chain where the blocks were finalized using the GRANDPA algorithm may contain a fork.

Voters perform the following to finalize new blocks:

1. A node that is designated as the “primary” broadcasts the highest block that it thinks could be final from the previous round.

2. After waiting for a network delay, each validator broadcasts a “pre-vote”for the highest block that it thinks should be finalized. If the supermajority of validators are honest, this block should extend the chain that the primary broadcast. This new chain could be several blocks longer than the last finalized chain.

3. Each validator computes the highest block that can be finalized based on the set of pre-votes. If the set of pre-votes extends the last finalized chain, then each validator will cast a “pre-commit” to that chain.

4. Each validator waits to receive enough pre-commits to form a commit message on the newly finalized chain.

A subtle but important distinction from other Byzantine fault-tolerant algorithms (like PBFT and Hotstuff) is that there is no view change on the critical path. Although the primary changes each round, this view change is only to start a new round in asynchronous network conditions so that in partially synchronous networks, the protocol will always advance, even without assigning a primary.

1.2 BABE

BABE is a probabilistic deterministic block generation algorithm, which divides time into multiple epochs, each epoch into multiple slots, and finally selects one or more validators to create blocks at each slot interval. In Polkadot, the duration of each slot is 6 seconds, which is the target blocking time on Polkadot.

Each solt consists of a master leader that can be generated by the verifiable random function (VRF), which takes as input the epoch random seed, the slot encoding and the creator’s private key, allowing each node to generate a unique pseudo-random value for each slot. If there exists a slot below some specified threshold, the validator has the right to create blocks in that slot. This approach is more secure, but it is prone to the situation where some slots have no leader and some slots have multiple master leaders.

1. Slot has multiple validators: all validators generate a candidate block and broadcast it to the network, the first block that is received by most nodes in the network wins.

2. Slot has no validators: Polkadot selects a validator in the backend by the round-robin method, which generates a secondary block. Therefore, there must be a block in the solt, either a primary block or a secondary block. In chains with temporary forks, both primary and secondary blocks may exist.

1.3 Fork Selection Algorithm

When a fork exists in the system, BABE will continue blocking after the chain finalized by GRANDPA, and when a fork exists on the finalized chain, BABE will select the chain containing the most dominant block.

As shown above, the black blocks represent the blocks that have been finalized by GRANDPA, and the yellow blocks represent the complete blocks. The blocks marked with “1” are the primary blocks and the blocks marked with “2” are the secondary blocks. Therefore, even if the top chain contains the most blocks, it will not be selected, because it contains the least number of primary blocks. But the last chain will not be selected even if it contains the most primary blocks, because it does not continue to produce blocks on the chain after the GRANDPA finalization. The final selected chain is the penultimate one, which satisfies both of the above conditions.

2 Cross-chain Messaging

2.1 XCM

Polkadot has three types of cross-chain messaging protocols: UMP, DMP, and XCMP, where UMP (upward messaging) allows parallel chains to send messages to a relay chain of the blockchain system, and DMP (downward messaging) allows a relay chain to pass messages down to one of the parallel chains. XCM is a message format used for the above three types of cross-chain messaging.

The reason for not using the native message format on the chain is the lack of compatibility between chains. If a user intends to send messages to multiple destination systems, contracts need to be written for each destination system. If the destination system’s smart contract is upgraded, the blockchain may introduce new features or change existing features and consequently change its transaction format. To address these issues, Polkadot uses XCM as a common message format; the “message” contained in XCM is actually just a program running on XCVM, which consists of one or more XCM instructions.

2.2 Cross-chain Messaging

The following is an example of asset transfer between Moonbeam and Polkadot to introduce the cross-chain messaging process.

1. Firstly, the main DApps are accessed in the form of a parallel chain, at which time the native tokens on the relay chain need to be registered on the parallel chain.

2. Alice wants to transfer a certain amount of her DOT on Polkadot to her account on Moonbeam via an XCM.

3. Polkadot will execute an XCM message to transfer the same amount of DOT to Moonbeam’s account on Polkadot.

4. When the above assets are successfully deposited, the second part of the XCM message will be sent to Moonbeam.

5. Moonbeam will execute the instructions contained in the XCM to mint the same number of xcDOT (DOT mapped coins on Moonbeam) on that chain.

2.3 Asset Transferring

For mutually trusted chains (i.e. parallel chains in Polkadot protected by the same overall consensus and security), cross-chain asset transfers can be performed using the Teleporting framework. The basic process is to burn assets on the sender side and mint a corresponding amount of assets on the receiver side.

· WithdrawAsset: There is only one parameter, of type MultiAssets, representing which assets must be withdrawn from the ownership of the asset origin registry, but the location where the assets are placed is not specified. In this case, withdrawn and unused assets are stored temporarily in the holding registry and are not stored permanently.

· InitiateTeleport : A brand new XCM message is created on behalf of the relay chain when it executes the command and sends it to the target chain.

BuyExecution: Using assets extracted from WithdrawAsset in exchange for the computation time of XCM instructions. Most parallel chains in the Polkadot community require users to pay a fee to interact with them in order to avoid “spam” and denial-of-service (DoS) attacks. However, unlike the Ethereum transaction model, the fees in Polkadot are not included in the protocol, but for some systems that do require fees, XCM provides the ability to use assets to purchase execution resources. Three main components are included.

1. First, some assets need to be provided;

2. Second, the computation time (or weight) obtained by the asset exchange must be negotiated;

3. Finally, the XCM operation is performed.

The function contains the following two parameters.

1. fees: The amount that should be taken from the holding register and used to pay the charges. This is only the maximum value, because any unused balance is returned immediately. The final amount to be spent is determined by the system, the value of this variable just limits it, and the BuyExecution instruction will cause an error if the interpreting system needs to pay more for its required execution operations.

2. weight: Specifies the execution time to be purchased, usually the value is greater than or equal to the total weight of the XCM program.

DepositAsset: Deposit the remaining funds into the holding register. In fact, after deducting the fees, we don’t know how much assets are left, so we can use the wildcard All.into() in assets to deposit all the remaining assets into the account identified by beneficiary, where the value is Parent.into(), representing the location of the Relay chain.