(To understand how QuarkChain partitions system state, please check Part 3: Sharding in QuarkChain — State Partitioning)
With partitioned sub-states and the operations (transactions) to change the sub-states (including both in-shard transactions and cross-shard transactions), the next major question is how to implement an efficient system to store the sub-states and process the transactions. In the centralized world, this is generally done by implementing a large-scale distributed system such as Google’s BigTable, Apache Cassandra, etc. However, in the decentralized world, since every full node maintains a full ledger of the blockchain and every node may be able to produce a block that contains a list of transactions to change the ledger, we need to build a consensus so that
- Who is able to produce a block (block producers (BPs))? For PoW, the BPs are the miners that repeatedly calculate the hashes of the block headers with different nonces and find the one that reaches difficulty requirements.
- How to broadcast a block to all the nodes? For Bitcoin and Ethereum, the blocks are broadcasted in their p2p networks, where the peers are full nodes that are interconnected without a centralized admin.
- How to check the validity of a block in a deterministic way? Every node, upon receiving a new block during broadcasting, should deterministically check if a block produced by a BP is valid.
- How to address forks? If inconsistent view happens because multiple BPs produce multiple blocks on the same ledger, i.e., forks are created, all the nodes should be able to eventually reach a consistent view of the ledger with a high probability over the time.
In this article, we will present QuarkChain’s consensus algorithm — Boson, which is a fundamental physical particle that carries forces. Before we introduce Boson consensus in details, let us discuss two naive consensus algorithms to the sharded blockchain and their pros and cons.
Naive Consensus 1: Single Blockchain with Large Blocksize
The first simple consensus is to run a simple blockchain with each block containing all transactions from all shards. The benefits of this approach are that we could reuse the existing blockchain consensus algorithms (and probably the code) such as PoW or dPoS. In addition, with partitioned sub-states, we could employ multi-threading or even a cluster to enhance the processing speed of a block, which is extremely helpful when transaction executions are time-consuming (e.g., virtual machine executions). With proper full node implementation, the processing speed can be up to N times faster, where N is the number of shards in the network.
However, packing all transactions in a block means that the block size can be potentially very large. For example, consider a PoW blockchain with 600s block interval, to achieve 10K TPS, the block size will be roughly 10K (TPS) * 600 (block interval) * 200 (TX size) = 1 GB (assuming the average transaction size is 200 bytes, which is typical for Bitcoin), which is 1024 times higher than current Bitcoin’s block size limit. If the number of the nodes in the network is large and the BPs are distributed around the world, propagating 1 GB block from one BP to the rest of BPs could take considerable time, and thus the probability of stale block can be dramatically increased.
A way to address the propagation issue of large block size is to limit the network size (especially the number of BPs) and have the BPs to connect with each other directly. An example of such solutions is EOS’s dPoS, where only 21 nodes are selected to produce the block and these 21 nodes are connected with each other with good network connections. This alleviates the block propagation issue. However, limiting BPs creates the further concern of centralization.
Naive Consensus 2: Multiple Blockchains In Parallel
Another simple consensus is to run the shards by multiple blockchains in parallel. For example, the system runs N blockchains (N is the number of shards), with each blockchain storing its own ledger and processing its own transactions in one shard. A node could join and mine any blockchain, and thus only need to broadcast and process the blocks in one blockchain, whose size could be much smaller.
However, running multiple blockchains in parallel also exposes several drawbacks. Suppose each blockchain employs the same PoW consensus, which is the most mature decentralized consensus these days, the system will suffer from an issue we called hashpower dilution — if there are N blockchains in the system, there exists a blockchain with less than 1/N hashpower of the network, and thus a 1/(2N) hashpower miner could easily perform double-spending attack of this chain, greatly reducing the security level of the network.
Besides the security issue, another issue is that performing a cross-shard transaction (i.e., moving the balance from one shard to another shard) could be time-consuming and insecure. To prevent a double-spending attack on a cross-shard transaction, we need some levels of the finality of source sharded blockchain before spending the transferred balance in a destination shard. Since PoW only provides probabilistic finality, reaching such finality would require several block confirmations or even more because of hashpower dilution issue, which could be extremely time-consuming (See Binance significantly increases blockchain confirmation number of BTG after BTG being double-spend attacked in 2018).
QuarkChain’s Boson Consensus
Now we are going to introduce QuarkChain’s consensus — Boson. Note that Boson consensus is not a single consensus, but rather a class of consensus algorithms that achieve:
- Security : All transactions are secured with strong guarantees. With PoW as our major consensus, this means that all transactions are protected by sufficiently high hashpower of the network regardless of the number of shards in the network.
- Decentralization : A BP is able to easily join the network and produce blocks even when it only has a small portion of hashpower (PoW) or stake (PoS) in the network. In addition, the node requires lower bandwidth compared to single blockchain with a large block size.
- Scalability : The transactions in the network could grow as the number of shards increases. In addition, the number of cross-shard transactions also increases linearly in terms of the number of shards.
By adjusting the parameters of Boson consensus, we can demonstrate that both aforementioned naive consensuses: single blockchain with large block size and multiple blockchains in parallel are subsumed as special cases of Boson consensus.
Overview
To maintain the state (ledger) and process state changes (transactions) of each shard, QuarkChain runs a two-layer blockchain:
Sharding Blockchain Layer
The QuarkChain network contains a sharding blockchain layer, which consists of a list of sharded blockchains. Each sharded blockchain would maintain a partitioned sub-state (a shard) and processes new transactions of that shard as described in Part 3:
- Each shard has its genesis block containing initial state of the shard;
- The state of the shard is changed by appending a new block, which contains a list of transactions (balance transfers or smart contract transactions);
- To append a valid block, the block must reach some criteria specified by the consensus of the shard, e.g., sufficient difficulty of proof of work (PoW), sufficient stake of proof of stake (PoS), or designated block producers in delegated proof of stake (dPoS);
- Each block in a sharded blockchain (namely minor block) has two hash pointers, one links to the previous sharded block, which is used to construct the sharded blockchain. Another hash pointer points to a root block, which is used to perform cross-shard transactions (interoperability). We will present the details of interoperability in the following articles and ignore the hash pointer to the root block in this article.
Rootchain Layer
The QuarkChain network has a root blockchain (rootchain) that confirms all blocks from sharded blockchain by including the block headers into the body of a root block. Beside the block headers and the root block header, the root block does not include any other data such as transactions. For each shard, the block headers of the shard in all root blocks must be ordered and is a valid sharded blockchain. This means, given a shard:
- The heights of the block headers in a root block must be unique and continuous;
- The block header with the smallest height in a root block must link to the block header with the largest height in the previous root block.
Full Ledger
A full ledger of a QuarkChain network is a ledger which contains the ledger of a rootchain and the corresponding ledgers of the sharded blockchains. The following figure illustrates a valid full ledger with a single shard in the network.
An Example of A Valid Full Ledger
Some examples of invalid ledgers can be found in the appendix.
Full Node
A full node is a peer in the p2p network that maintains a full ledger in the QuarkChain network. A full node also has the full static information of the network, including the consensus of each sharded blockchain and the parameters (e.g., block interval). Since a full node has all the data, the full node is able to verify any blocks (sharded block or root block) appended to the full ledger and to obtain a new full ledger.
It is also possible that a node only runs a partial ledger in the network (e.g., a single shard). However, it has to rely on other peers to determine the validity of the rest sharded blockchains and/or rootchain.
Block Producers (BPs)
At any time, a BP (miner in PoW or minter in PoS) could append a block to any sharded blockchain or the rootchain and collect block rewards as long as
- For sharded blockchain, the block contains a list of valid transactions and a valid header of the block (timestamp, Merkle tree root, etc); or
- For rootchain, the block contains a list of valid sharded minor block headers and a valid header of the block;
- The block satisfies the requirement of the consensus of sharded blockchain or rootchain such as PoW or PoS.
Incentive of Producing a Block
Incentive of Producing a Block in Sharded Blockchain
Given shard i, a BP would collect block reward after successfully append a block to the full ledger, where the miner’s reward of the sharded block is
where i is the shard id, j is the block height, and, r_{ij} is the block reward, which depends on i and j and decreases as j increases, f_{ij} is the transaction fee, and 0 ≤ a_i ≤ 1 is a factor to denote how much percentage of the reward is allocated to root block from the shard, which we refer to as “tax rate” of the shard.
Incentive of Producing a Block in Rootchain
The BP’s reward of a root block is defined as follows
where k is the height of the root block, R_k is the block reward, which decreases as k increases, \sum_{ij} a_i(r_{ij}+f_{ij}) is called “tax”, which are collected from the blocks from sharded blockchains, whose headers are included in the root block.
Some comments of the incentive are discussed as follows:
- The miner’s reward of a root block increases as the number of minor block headers included in the root block increases. This means that to maximize the reward, a root block miner should include the longest chain that starts from the one that is not included by previous root block.
- For PoW consensus, given the assumption that the hashpower of a blockchain is proportional to the incentive of the blockchain over time, we could adjust the tax rate to increase or decrease the hashpower of the rootchain.
Fork-Choice Rule
A key question in blockchain consensus is how to choose a fork if multiple forks exist in the network due to network propagation latency. The question is more important for QuarkChain’s Boson consensus as
- Any sharded blockchain may have forks
- The rootchain can also be forked.
The fork-choice rule of QuarkChain is basically answering the following questions: given two full ledgers of the QuarkChain network, which one should survive? The key to answering the question is that we called rootchain-first consensus, where given two full ledgers, we always compare their rootchains (depending on the rootchain consensus, it could be height or total difficulty) first, and then the sharded blockchain. The following gives a few examples of how rootchain-first consensus works.
An Example of Rootchain-First consensus
The above figure gives an example of two forks in the network, where the B0<-B1<-B2 is chosen over B0<-B3 even B0<-B3 contains more sharded blocks.
The rootchain-first consensus has a significant implication of double-spending attack — as long as a transaction is confirmed by a root block (by including the transaction’s sharded block header), double-spending the transaction only in the sharded blockchain will not work.
The above figure illustrates an attempt of a double-spending attack on b2<-b3 by creating a longer fork in b2<-b4<-b5<-b6. However, such an attack will not succeed as the attacking fork has lower root block height than that of the fork being attacked.
Instead, in order to revert the transaction, the attacker must also attack the root block by creating a longer rootchain fork, which is illustrated as follows.
In all, if a transaction is confirmed by rootchain, then the transaction is secured by the rootchain’s security guarantee, which could be:
- Sufficiently high hashpower over the whole network if rootchain runs PoW consensus (e.g., 50% of the hashpower of the network is allocated to rootchain);
- Majority of the stakers on the rootchain if rootchain runs PoS consensus.
Examples of QuarkChain’s Boson Consensus
The Boson consensus represents a class of two-layer blockchain consensus by adjusting
- Rootchain consensus
- Per-shard consensus
- Tax rate
- etc
In the following, we list several realizations of Boson consensus:
- Collaborative Mining : the rootchain and all sharded blockchains run PoW consensus. To achieve security, we could adjust the tax rate so that there is sufficient hashpower on rootchain.
- Collaborative Mining/Minting : the rootchain still runs PoW while some sharded blockchains run PoS, and rest of sharded blockchains run PoW. This allows more hashpower to be allocated to the rootchain.
- Decentralized dPoS : the rootchain runs dPoS while the sharded blockchains run PoW. This allows miners to join the network and produce blocks in sharded blockchain freely, while the delegates in rootchain can only include the sharded blocks that are mined. In addition, the sharded blockchain (even with PoW) can enjoy almost instant finality brought by dPoS thanks to rootchain-first consensus.
- Single blockchain with Large Block Size : this is basically achieved by setting tax rate = 100% so that the rootchain block could include the sharded blockchain transactions as much as the BP wants.
- Multiple blockchains in Parallel : this is basically achieved by setting tax rate = 0% and disabling rootchain-first consensus so that each sharded blockchain just uses its fork-choice rule individually.
In the next article, we will focus on collaborative mining/minting and discuss the attack vectors of the consensus.
Summary
In this article, we present QuarkChain’s Boson consensus to store the sharded state and process transactions in a decentralized, secure, and scalable way. We propose a two-layer blockchain and illustrate BP’s incentives and fork-choice rule (rootchain-first consensus). In the next article, we will discuss a realization of Boson consensus — collaborative mining/minting and go through some thoughts about the attack vectors.
Appendix — Examples of Invalid Full Ledgers
Missing One Minor Block in Rootchain
Unordered Minor Blocks in Rootchain
Extra Minor Block in Rootchain
Incorrect Link to the Minor Block in the Previous Rootblock
About QuarkChain
QuarkChain aims to address blockchain scalability problem by utilizing horizontal scalability technologies. The mission of QuarkChain is to allow everyone in the world to use blockchain technologies anytime anywhere. If you are interested in QuarkChain, please check the following links for more information:
Website https://www.quarkchain.io
Telegram https://t.me/quarkchainio
Twitter https://twitter.com/Quark_Chain
Steemit https://steemit.com/@quarkchain
Medium https://medium.com/quarkchain-official