Hierarchical Consensus: A Horizontal Scaling

Framework for Blockchains

Alfonso de la Rocha
Protocol Labs
alfonso@protocol.ai

Lefteris Kokoris-Kogias
IST Austria
ekokoris@ist.ac.at

Jorge M. Soares
Protocol Labs
jorge@protocol.ai

Marko Vukolic´
Protocol Labs
marko@protocol.ai

Abstract

—We present the Filecoin Hierarchical Consensus
framework, which aims to overcome the throughput challenges
of blockchain consensus by horizontally scaling the network.
Unlike traditional sharding designs, based on partitioning the
state of the network, our solution centers on the concept of
subnets –which are organized hierarchically– and can be spawned
on-demand to manage new state. Child subnets are firewalled
from parent subnets, have their own specific policies, and run
a different consensus algorithm, increasing the network capacity
and enabling new applications. Moreover, they benefit from the
security of parent subnets by periodically checkpointing state.
In this paper, we introduce the overall system architecture, our
detailed designs for cross-net transaction handling, and the open
questions that we are still exploring.

Index Terms—blockchain, consensus, distributed systems, P2P,
scalability, sharding

I. INTRODUCTION

Consensus, or establishing total order across transactions, poses a major scalability bottleneck in blockchain networks [1]. This is particularly the case when all nodes (often called validators or miners) are required to process all transactions. Regardless of the specific consensus protocol implementation used, this makes blockchains unable to increase their performance by adding more participants (scale-out).

In traditional distributed computing, one possible approach to overcoming this limitation is to resort to the partitioning, or sharding, of state processing and transaction ordering. In a sharded system the blockchain stack is divided into different groups called shards, each operated by its own set of nodes, which keep a subset of the state and are responsible for processing a part of the transactions sent to the system. In existing sharded designs [2], [3], the system often acts as a distributed controller that assigns miners to different shards and attempts to load-balance the state evenly across shards.

The main challenge with applying traditional sharding to the Byzantine fault-tolerant context of the blockchain lies in the security/performance tradeoff. As miners are assigned to shards, there is a danger of diluting security when compared to the original single-chain (single-shard) solution. In both proof-of-work and proof-of-stake (PoS) blockchains, sharding may lead to the ability of the attacker to compromise a single shard with only a fraction of the mining power, potentially compromising the system as a whole. Such attacks are often referred to as 1% attacks [2], [4]. To circumvent them, sharding systems need to periodically reassign miners to shards in an unpredictable way, so as to cope with a semi-dynamic adversary [5], [6]. We believe that this traditional approach to scaling, which considers the system as a monolith, is not suitable for decentralized blockchains due to their complexity and the fact that sharded systems reshuffle state without the consent of its owners.

In our efforts to scale the Filecoin network [7], [8], we depart from the traditional sharding approach to build hierarchical consensus. In hierarchical consensus, instead of algorithmically assigning node membership and load balancing the distribution of the state, we follow an approach where users and miners are grouped into subnets in which they can freely partake. Users can spawn new child subnets from the one they are operating in accordance with their needs, and become miners there if they fulfill all the requirements set by the protocol. Each subnet can run its own independent consensus algorithm and set its own security and performance guarantees. Subnets in the system are organized hierarchically, each having one parent subnet and any number of child subnets — except for the root subnet (called root network or rootnet), which has no parent and is the initial anchor of trust. To circumvent the 1% attacks pertinent to traditional sharding, subnets in hierarchical consensus are firewalled [9], in the sense that a security violation in a given subnet is limited, in effect, to that particular subnet and its children, with bounded economic impact on its ancestors. This bounded impact of an attack is, at most, the circulating supply of the parent token in the child subnet. Moreover, ancestor subnets help secure their descendant subnets through checkpointing—which helps alleviate attacks on a child subnet, such as long-range and related attacks in the case of a PoS-based subnet [10]. At a high level, hierarchical consensus allows for incremental, on-demand, blockchain scaling and simplifies deployment of new use cases with clearly isolated security domains that provide flexibility for varied use cases. Our design further supports ordinary (e.g., token payment) and atomic transactions across subnets.

This paper is organized as follows: Section II provides a high-level overview of the system and its specifications; Section III describes the life cycle of a subnet and its key operations; Section IV explains the semantics for cross-subnet transactions; finally, Section V surveys the related work and Section VI outlines conclusions and future directions.

II. SYSTEM OVERVIEW

Fig. 1 depicts a high-level overview of a hierarchical consensus system. The system starts with a rootnet which, at first, keeps the entire state and processes all the transaction in the system (like present-day Filecoin). At one point, a subset of users requiring lower latency or higher throughput can spawn a new subnet to accommodate their performance requirements. This subnet instantiates a new chain with its own state, independent from the root chain, replicated among the subset of participants of the overall system who are members of the subnet. From this point on, the new subnet processes transactions involving the state in the subnet independently from the root chain. Further subnets can then be spawned from any point in the hierarchy.

Subnets are able to interact with the state of other subnets (and that of the rootnet) through cross-subnet (or, simply, cross-net) messages. Full nodes in a given subnet have trusted access to the state of its parent subnet. We implement this by having nodes sync the chain of its parent (i.e., child subnet nodes also run full nodes on the parent subnet). Miners on parent subnets do not need to sync with child subnets’ chains.

In hierarchical consensus, it may be hard to enforce an honest majority of mining power in every subnet, which can result in the subnet chain being compromised or attacked. The system provides a firewall security property, introduced in [9]; this guarantees that, for token exchanges, the impact of a child subnet being compromised is limited to, at most, its circulating supply of the token, determined by the (positive) balance between cross-net transactions entering the subnet and cross-net transactions leaving the subnet. Addresses in a subnet are funded through cross-net transactions that inject tokens into the subnet. In order for users to be able to spawn a new subnet, they need to deposit an initial collateral into the new subnet’s parent. This collateral offers a minimum level of trust to new users injecting tokens to the subnet and can be slashed in case of misbehavior by subnet validators.

Miners in subnets are rewarded with fees for the transactions executed in the subnet. Subnets can run a consensus algorithm of their choosing to validate blocks and can determine the consensus proofs they want to include for light clients (i.e., nodes that do not synchronize and retain a full copy of the blockchain and thus do not verify all transactions). Subnets periodically commit a proof of their state in their parent through checkpoints. These proofs are propagated to the top of the hierarchy, making them accessible to any member of the system. They should include enough information that any client receiving it is able to verify the correctness of the subnet consensus. Subnets are free to choose a proof scheme that suits their consensus best [e.g., multi-signature, threshold signature or zero-knowledge (ZK) proofs]. With this, users are able to determine the level of trust over a subnet according to the security level of the consensus run by the subnet and the proofs provided to light clients. Checkpoints are also used to propagate to other subnets in the hierarchy the information pertaining to cross-net messages.

III. LIFECYCLE OF A SUBNET

A. Spawning and joining a subnet

Creating a new subnet instantiates a new independent state with all its subnet-specific requirements to operate independently. This includes, in particular: a new attack-resilient pubsub [11] topic that peers use as the transport layer to exchange chain-specific messages, a new mempool instance, a new instance of the Virtual Machine (VM), as well as any other additional module required by the consensus that the subnet is running (system actors, i.e., smart contracts in Filecoin terminology; mining power resources; etc. [7]).

To spawn a new subnet, peers need to deploy a new Subnet Actor (SA) that implements the core logic for the new subnet. The contract specifies the consensus protocol to be run by the subnet and the set of policies to be enforced for new members, leaving members, checkpointing, killing the subnet, etc. For a new subnet to interact with the rest of the hierarchy, it needs to be registered in the Subnet Coordinator Actor (SCA) of the parent chain. The SCA is a system actor that exposes the interface for subnets to interact with the hierarchical consensus protocol. This smart contract includes all the available functionalities related to subnets and their management. And, as SAs are user-defined and untrusted, it also enforces security assumptions, fund management, and the cryptoeconomics of hierarchical consensus. Subnets are identified with a unique ID that is inferred deterministically from the ID of its ancestor and from the ID of the SA that governs its operation. This deterministic naming enables the discovery of and interaction with subnets from any other point in the hierarchy without the need of a discovery service: peers need only send a message to the subnet’s specific pubsub topic, identified with the subnet’s ID.

B. Checkpointing protocol

Checkpoints are used to anchor a subnet’s security to that of its parent chain, as well as to propagate information from a child chain to other subnets in the system. Checkpoints for a subnet can be verified at any point using the state of the subnet chain which can then be used to generate equivocation proofs (or so-called fraud proofs) which, in turn, can be used for penalizing misbehaving entities (“slashing”).

Subnet miners need to provide a minimum collateral, minCollateral_subnet, in their parent’s SCA to register the subnet to the hierarchy and be able to interact with other subnets. This collateral is frozen through the lifetime of the subnet and does not become part of its circulating supply. These collateral funds are the ones slashed in the face of a valid fraud proof. If the subnet’s collateral drops below minCollateral_subnet, the subnet enters an inactive state, and it can no longer interact with the rest of the hierarchy. To recover its active state, users of the subnet need to put up additional collateral.

$$ minCollateral_{subnet} $$

$$ minCollateral_{subnet}. $$

Checkpoints need to be signed by miners of a child chain and committed to the parent chain through their corresponding SA. The specific signature policy is defined in the SA and determines the type and minimum number of signatures required for a checkpoint to be accepted and validated by the SA for its propagation to the top chain. Different signature schemes may be used here, including multi-signatures or threshold signatures among subnet miners.

As an example, consider a checkpoint for subnet /root/A/B. Periodically (in terms of subnet block time), miners access the checkpoint template that needs to be signed and populated by calling the SCA in /root/A/B. Once signed, checkpoints from /root/A/B are committed to the SA B of the subnet chain /root/A. After performing the corresponding checks, this actor triggers a message function to the SCA in /root/A, which is responsible for aggregating the checkpoint from /root/A/B with those of other children of /root/A and for generating a new checkpoint for /root/A that is then propagated to its parent chain, /root. As checkpoints flow up the chain, the SCA of each chain picks up these checkpoints and inspects them to propagate potential state changes (like balance updates in a monetary transaction) triggered by messages included in the cross-net messages (for brevity, we call these simply cross-msgs) that have the SCA’s subnet as a destination subnet (see Fig. 2).

$$ /root/A/B $$

$$ /r o o t / A / B $$

$$ /r o o t/A/B $$

$$ /o o o/. $$

$$ /o o o/A $$

$$ /r o o t/A/B $$

$$ /r o o t/A $$

$$ /r o o t/A $$

Checkpoints are always identified though their Content
Identifier (CID), a unique identifier inferred from the checkpoint’s hash, and include the corresponding signature from miners in the subnet chain (this can be the signature of an individual miner, a multi-signature, or a threshold signature, depending on the SA policy). Checkpoints include the following data: < s, proof, prev, children, crossM eta > where: (i) s is the source subnet of the checkpoint; (ii) proof is the content identifier CID (roughly corresponding to a hash) of the latest block from the subnet chain being committed in the checkpoint; (iii) prev is a pointer to the CID of the previous checkpoint of the subnet; (iv) children = (f rom, cid) is a tree which includes the subnet ID and the corresponding checkpoint CID for every child chain; and (v) crossM eta = (f rom, to, nonce, msgsCid) is a tree of cross-msg metadata including every cross-msg being propagated

$$ (mathrm C I I))^{2} $$

$$ (f r o m,c i d) $$

$$ M e t a=(f r o m,t o,n o n c e,m s g s c i d) $$

IV. CROSS-NET TRANSACTIONS AND EXECUTION

A. Cross-net messages

Users in a subnet interact with other subnets through cross-net transactions. The propagation of a cross-net transaction may slightly differ depending on the location of subnets in the hierarchy, e.g., if moving up or down the hierarchy. In particular, we distinguish: top-down, bottom-up, and path messages.

Top-down messages are cross-msgs directed towards a subnet that is lower in the hierarchy. When a new top-down transaction is triggered, the SCA of the source subnet (parent) increments a nonce that is unique to the top-down transaction directed to each of its child subnets (destination) and stores it in the SCA state. These nonces determine the total order of arrival of cross-msgs to the subnet; without them, different consensus nodes could execute different orderings, leading to nondeterminism. The commitment of a top-down transaction in the SCA also triggers the freezing, in the parent, of the funds included in the message, and updates the circulating supply in the destination subnet. Child subnet miners always sync with their parent chains (i.e., track their latest state) to stay informed of updates to the state of the SCA and SA in the parent, and so are immediately notified when there are new unverified top-down messages directed to them.

Bottom-up messages are cross-msgs directed towards a subnet that is higher in the hierarchy but shares the same prefix. Bottom-up messages are propagated in checkpoints. At every checkpoint period, the SCA collects all CrossMsgMeta from bottom-up transactions originated in the subnet and all the CrossMsgMeta received from the subnet’s child subnets, and includes them in the next checkpoint to be propagated up the hierarchy. Every message leaving the subnet triggers the burn (in the child) and release (in the parent) of the funds included in the message, updating its circulating supply.

When the checkpoint from the child subnet is committed in the parent chain, the SCA of the parent chain inspects all CrossMsgMeta in the checkpoint and collects the ones directed to it. Bottom-up messages targeting other subnets are propagated farther up the hierarchy in the next checkpoint, while bottom-up CrossMsgMeta targeting the current subnet are assigned an increasing nonce for posterior validation and application by the subnet’s consensus algorithm.

Path messages. Every message routed in the hierarchy can be seen as a combination of top-down and bottom-up transactions. Path messages are cross-net messages in which the source and destination subnets are not in the same branch. These are propagated through bottom-up messages (i.e., CrossMsgMeta in checkpoints) up to the common parent (root, in the worst case), and through top-down messages from there to the destination. As checkpoints move up in the hierarchy, funds are conveniently released and burned in each of the subnets as cross-msgs flow. The opposite happens for top-down messages, where flowing messages trigger the minting of new funds in destination subnets. This updates the circulating supply of subnets as messages flow through the hierarchy.

According to the route that messages need to follow through the hierarchy and the specific consensus algorithms run by each of the subnets, the propagation of these transactions may be slow. To accelerate the process, each SA in the path can send a direct message to the destination, certifying that the user is the legitimate owner of the funds. This information can be used by the destination subnet (depending on the finality required for the actions to be performed) to indicate a pending payment or even as tentative information to start operating as if these funds were already settled and available in the subnet.

B. Cross-msg pool

Nodes in subnets keep two types of message pools: an internal pool to track unverified messages originating in and targeting the subnet and a cross-msg pool that listens to unverified cross-msgs directed at (or traversing) the subnet. To verify and execute cross-msgs in a subnet, they need to be included by the consensus algorithm in a subnet block.

Miners’ cross-msg pools collect unverified cross-net messages by syncing with state changes in the SCA of the parent subnet. Whenever the SCA in the parent receives a new top-down message or collects a new bottom-up CrossMsgMeta from a child checkpoint, the cross-msg pool is notified. Top-down messages can be proposed to and applied directly in the subnet. For bottom-up messages, the cross-msg pool only has the CID of the CrossMsgMeta that points to the cross-msgs to be applied and, therefore, needs to make a request to the content resolution protocol (Section IV-C) to retrieve the raw messages, so that it may propose and apply them. Blocks in subnets include both messages originated within the subnet and cross-msgs targeting (or traversing) the subnet. When a new block including top-down cross-msgs is verified in the subnet consensus, the cross-msgs are committed, and every node receiving the new block executes the cross-msgs to trigger the corresponding state changes and fund exchanges in the subnet (Fig. 3).

Cross-msgs have to go through several checks before they are stored in the SCA and provided to the subnet consensus through the cross-msg pool, but the application of these messages may still fail. This is especially true for arbitrary messages. If the message for a specific nonce cannot be applied and keeps failing when trying to be applied in the respective SCA, the subnet consensus could stall. This represents a vector for Distributed Denial of Service (DDoS) attacks. To prevent this, a cross-msg that cannot be applied in a subnet triggers a new cross-msg with the subnet where the execution of the message failed as source and the original source of the message as destination. This message is used to revert every intermediate state change that may have been triggered in the original cross-msg route through the hierarchy.

D. Generality of the approach beyond payments: Atomic executions

An issue arises when state changes need to be atomic and impact the state of different subnets [12]. A simple example of this is the atomic swap of two assets hosted in different subnets. The state change in the subnets needs to be atomic, and it requires from state that lives in both subnets. To handle these atomic transactions, users in the subnets can choose any subnet in the hierarchy in which they both have a certain level of trust to migrate the corresponding state and orchestrate the execution. Generally, subnets will choose the closest common parent as the execution subnet, as they are already propagating their checkpoints to it and therefore leveraging shared trust.

A cross-net atomic execution takes tuples of input states and returns tuples of outputs states, which may belong to different subnets, but should appear as a single transaction in which all input/output states belong to the same subnet. Our atomic execution protocol has the following properties:

(i) Timeliness: The protocol eventually completes by committing or aborting.

(ii) Atomicity: If all involved subnets commit and no subnet aborts beforehand, the protocol commits and all subnets involved have the output state available as part of their subnet state. Otherwise, the protocol aborts and all subnets revert to their initial state.

(iii) Unforgeability: No entity in the system (user or contract) is able to forge the inputs and outputs provided for the execution or the set of messages orchestrating the protocol.

Finally, the data structures used by the protocol need to ensure the consistency of the state in each subnet, i.e., that the output state of the atomic execution can be applied onto the original state (and history) of the subnet without conflicts.

V. RELATED WORK

There are several concurrent approaches to the challenging problem of scaling blockchains [1]. We group them coarsely into four categories: sharding, payment/state channels, rollups and sidechains/subnets.

Sharding approaches (e.g., [2], [4]–[6], [12]–[15]) partition blockchain state processing across different groups of nodes, unlike our hierarchical consensus. Security and performance of sharding systems typically requires complex and periodic reassignment of nodes [2] and state across shards [3]. Sharding approaches have been in the focus of most academic work on horizontal scaling to date, they have been deployed in some blockchain systems (e.g., Zilliqa [16] and Near Protocol [17]), and are considered as candidates in others (e.g., Ethereum [18]).

Payment channels [19] are a scaling approach in which a payment is carried out privately among small groups of parties, off chain, with the on-chain communication being reserved only for setup and dispute resolution. Payment channels have been deployed in practice, with the most prominent example being the Bitcoin Lightning Network [20]. This approach was later generalized to general-state channels (e.g., [21]).

Rollups propose a tiered blockchain architecture where, in short, a top tier (L1) blockchain only orders transactions which are then retrieved from other tiers (given a data availability tier) for execution. Separate execution nodes (L2) post back results to L1 so that not everyone needs to execute. This approach is somewhat similar to the tiered approach pioneered by the Hyperledger Fabric permissioned blockchain [22]. Current early rollup implementations include: (i) optimistic rollups (e.g., [23]) in which only a subset of execution nodes execute publicly available transactions in the common case and where transactions are reexecuted on L1 in case of misbehavior of L2 nodes (similar to payment channels) and (ii) ZK rollups (e.g., [24], [25]) which have execution nodes cryptographically prove their execution correct while allowing for fast verification (e.g., [26]).

Our hierarchical consensus is inspired by the PoS sidechain design—to our knowledge first proposed in [9]. In general, sidechains allow a faster and less secure chain to benefit from the security of a more robust, slower chain by writing critical information (e.g., a checkpoint) to it. In our case, subnets are sidechains, hierarchically orchestrated, instantiating the sidechain approach of [9] in a specific and novel way, which allows for general-state cross-net atomic transactions. Furthermore, unlike [9], hierarchical consensus subnets can run any type of consensus and are not limited to PoS-based consensus algorithms, including on the rootnet.

A related approach to ours is that of Avalanche subnets [27], inspired by [28], which, unlike hierarchical consensus, support limited subnet hierarchies and do not consider cross-net semantics. Concretely, the 3 subnets of the Avalanche primary network (rootnet), are split into: an asset exchange chain (X-chain), a platform chain (P-chain), which allows

VI. CONCLUSIONS

This paper presented a hierarchical consensus framework that enables the horizontal scaling of blockchain systems. It does so by allowing the creation of subnets at any point in the hierarchy, each being able to run a different consensus protocol and set different policies.

Subnets can process internal transactions without going through the main chain, only submitting periodic checkpoints to their parent. They can also take part in cross-net transactions, with support for atomic execution. In addition to increasing chain capacity, our framework enables new use cases by providing highly-customized environments, largely free from the the constraints of the root chain.

While still a work in progress, we plan for this framework to be adopted by the Filecoin blockchain. A prototype implementation of the framework is already available, with ongoing work to integrate different consensus protocols, including Tendermint [29] and MirBFT [30].

REFERENCES

[1]M. Vukolireplication,” c,´ “The quest for scalable blockchain fabric: Proof-of-work vs. BFT in Int. Workshop on Open Problems in Network Security (iNetSec), 2015, pp. 112–125.
[2]E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta, and B. Ford, “Omniledger: A secure, scale-out, decentralized ledger via sharding,” in 2018 IEEE Symp. Secur. Privacy (SP) 2018, Proc., 21–23 May 2018, San Francisco, CA, USA. IEEE Computer Society, 2018, pp. 583–598. [Online]. Available: https://doi.org/10.1109/SP.2018.000-5
[3]M. Krol, O. Ascigil, S. Rene, A. Sonnino, M. Al-Bassam, and E. Rivi ´ ere, `“Shard scheduler: object placement and migration in sharded account-based blockchains,” 2021.
[4]L. Luu, V. Narayanan, C. Zheng, K. Baweja, S. Gilbert, and P. Saxena, “A secure sharding protocol for open blockchains,” in CCS ’16: Proc. 2016 ACM SIGSAC Conf. Comp. Commun. Secur., ser. CCS ’16.
New York, NY, USA: Association for Computing Machinery, 2016, p. 17–30.
[5]G. Yu, X. Wang, K. Yu, W. Ni, J. A. Zhang, and R. P. Liu, “Survey: Sharding in blockchains,” IEEE Access, vol. 8, pp. 14 155–14 181, 2020.
[6]G. Avarikioti, E. Kokoris-Kogias, and R. Wattenhofer, “Divide and scale: Formalization of distributed ledger sharding protocols,” arXiv preprint arXiv:1910.10434, 2019.
[7]Protocol Labs, “Filecoin: A decentralized storage network,” https://filecoin.io/filecoin.pdf, 2017.
[8]“Filecoin,” https://filecoin.io/, 2021.
[9]P. Gazi, A. Kiayias, and D. Zindros, “Proof-of-stake sidechains,” in 2019 IEEE Symp. Secur. Privacy, (SP) 2019, San Francisco, CA, USA, May 19-23, 2019. IEEE, 2019, pp. 139–156.
[10]S. Steinhoff, C. Stathakopoulou, M. Pavlovic, and M. Vukolic, “BMS: ´ Secure decentralized reconfiguration for blockchain and BFT systems,” 2021.