Decentralizing Permissioned Blockchain with Delay Towers

Blockchains constitute distributed ledgers, that overcome the challenges of centralization, for the exchange of digital assets without trusted intermediaries in decentralized and a priori trustless environments [1]. However, the promise of decentralization poses the challenge of needing to reach consensus on a single immutable source of truth among untrusted parties, and not everyone might abide by the rules of the protocol. Without loss of generality, it is fair to assume a small percentage of (un)intentional malicious parties that act in ways that hinder the integrity and security of the blockchain network. Consequently, the consensus protocols backing blockchains must tolerate Byzantine failures in addition to benign failures. More specifically, blockchains are also prone to Sybil attacks wherein a malicious party subverts the consensus protocol by creating a large number of (pseudo)anonymous identities [2]. During a Sybil attack, the malicious node can prevent creating new blocks or manipulate the ordering of transactions. To enable Sybil resistance and ensure security, blockchain protocols must establish and persist identities.

Classification of Blockchains. Based on how blockchains establish identity and build Sybil-resistance, we classify blockchains into two broad categories – permissioned and permissionless. Permissioned blockchains such as Hyperledger Fabric [3] and Libra¹¹1On December 1st, 2020, the Libra blockchain was renamed Diem blockchain. [4] rely on a membership service provider (MSP), a trusted entity, to certify and authorize nodes to access the network. This MSP moderates the network and can revoke authorized access for malicious nodes involved in either perceived Byzantine behavior or Sybil attacks. On the other hand, permissionless blockchains, also often referred to as public blockchains, are more decentralized, i.e., they do not have a centralized authority to manage access to the network. To establish identity, permissionless blockchains such as Bitcoin [1] and Ethereum [5] leverage proof of work (PoW), wherein the nodes compute hash puzzles. The computational power required for PoW serves as a proxy for identity to enable Sybil resistance. The nodes with high computational resources would have a higher probability of proposing the next block to be appended on the decentralized ledger. The nodes in the network reach a consensus on the proposed block if there are no conflicts. In case of conflict, the longest chain is chosen as the valid ledger [1]. It is worth noting that block proposal time is different from time to reach finality (confirmation). For instance, in Bitcoin, a probabilistic agreement is used to reach finality; it takes approximately an hour to reach finality after a block proposal [6, 1]. Unlike permissionless blockchains with PoW, permissioned blockchains tend to use Byzantine fault-tolerant (BFT) protocols to reach consensus [4, 3]. BFT protocols have deterministic finality and tend to reach finality faster, i.e., when a quorum of nodes agrees upon a proposed block, and they offer better scalability than PoW [7]. We consider a system to be more scalable if it offers higher throughput (transactions/second) and faster finality (transaction confirmation time). For comparison, Bitcoin and Hyperledger have a throughput of around seven and a few thousand transactions per second, respectively [8]. An overhead exists to build Sybil resistance and enable decentralization, leading to a trade-off between decentralization and scalability of blockchains [9, 10, 11, 12]. An increase in decentralization often resulted in lower scalability, i.e., low throughput and high finality time, see Table. I.

The Quest. The problem this paper addresses is characterizing a blockchain that encourages decentralization without compromising scalability; in other words, achieving consensus without trusted intermediaries at scale. This problem is considered in the literature as the quest for the scalable blockchain fabric (e.g.,  [13]). This quest for decentralized, scalable consensus is uplifting because successful expeditions could take us one step closer to the massive adoption of blockchains.

Expeditions. There are many ongoing expeditions for this quest (e.g.,  [14, 12, 15]). Broadly, we can achieve decentralized scalable consensus by either scaling permissionless blockchains or decentralizing permissioned blockchains. Lately, multiple on-chain and off-chain solutions to scale permissionless blockchains are being developed, such as sharding [16, 17], zero-knowledge and optimistic rollups [18, 19, 20], side chains [21], bidirectional payment channels [22], and directed acyclic graph-based ledgers [23, 24].

Here, we explore the latter approach of decentralizing permissioned blockchains. We choose to extend BFT protocol-based blockchains to decentralized settings because they better address scalability challenges, and we only need to introduce decentralization. Though this sounds straightforward, making a BFT protocol permissionless raises a plethora of challenges. Firstly, a malicious party could join the network without a membership service provider and create many anonymous identities to execute a Sybil attack. Secondly, BFT protocols need a defined set of nodes, and they have to be defined without a trusted intermediary. Having failed nodes would increase the time to reach consensus; for instance, if a crashed node is chosen to propose a block, it results in a timeout instead of a new block [25]. Also, BFT protocols do not scale-out, i.e., with the increase in the number of nodes, lower throughput, and higher latency were recorded [7]. Thirdly, incentive mechanisms are needed to reward honest behavior and punish bad behavior for not contributing to the protocol [25, 26].

L4L Protocol. In this paper, we describe L4L to decentralize a permissioned blockchain that uses a BFT protocol for consensus. Specifically, we enable decentralization over the permissioned Libra blockchain [27]. We believe that a protocol should not have a centralized MSP to be decentralized. To achieve decentralization without MSP, we must establish identities in a permissionless setting. To build persistent identities without heavy PoW computations and pre-sale of native tokens, we introduce delay towers. Delay towers are puzzle towers [28] that act as a proof of elapsed time (PoET) leveraging verifiable delay functions (VDF) [29]. A VDF is a cryptographic delay function that is more eco-friendly than PoW because it cannot be parallelized, with no substantial benefit in using more computational resources. L4L uses VDFs for building delay towers. Each node locally executes a VDF to generate proofs at regular intervals, and these proofs are chained to build delay towers, i.e., each proof executes from the hash of the previous proof. In addition, L4L reconfigures nodes participating in consensus at regular intervals by punishing unwanted behavior, for example, eliminating failed nodes. The nodes which participate actively, i.e., by participating in PoET and attesting blocks to reach consensus, are given preference to validate transactions during reconfiguration. Though this approach might have a few similarities to proof of stake (PoS) as in Tendermint [30] or Algorand [31] due to usage of a BFT protocol, they are not the same because L4L relies on delay towers and not staking of native assets to establish identities. Consequently, L4L can be a fairer alternative to airdrop or pre-sale of native tokens for bootstrapping blockchain networks.

Contributions. The key goal of L4L is decentralizing a permissioned blockchain. On this journey, L4L contributes the following principle ideas:

1. 1.

   Delay towers to encourage persistent identities in permissionless settings;

2. 2.

   Mechanisms to reconfigure nodes participating in consensus to engender compliant behavior;

3. 3.

   More eco-friendly and sustainable alternatives to existing consensus protocols in permissionless settings;

4. 4.

   Mechanisms to bootstrap a blockchain network without token sales, airdrops, or susceptibility to mining attacks.

Outline. The paper is organized as follows. The next section introduces blockchain basics, VDFs, and the Libra blockchain. Having discussed how to construct VDFs, section III addresses ways of establishing identity using delay towers in L4L. This section further describes the reconfiguration of the nodes participating in the BFT consensus at regular intervals in L4L. We evaluate the cost of decentralization using delay towers from the perspective of both the node and network in section IV. Finally, we conclude with future directions in section V.

In this section. we introduce some basic blockchain formalism and introduce verifiable delay functions (VDF), the building blocks of delay towers; both of which are used in subsequent parts of this paper. We end this section with an overview of the permissioned Libra blockchain.

L4L is a consensus protocol for permissionless blockchains designed to foster decentralization, scalability, and sustainability. In other words, L4L is a Sybil-resistant Byzantine fault-tolerant state machine replication protocol developed by decentralizing the general-purpose permissioned Libra blockchain without compromising sustainability.

A criticism of permissioned blockchains is the lack of decentralization as access to the network is controlled. Nonetheless, few blockchains reasonably assert that permissioned blockchains are decentralized as their transaction processing is decentralized, i.e., no single validator can decide on a state transition of ledger $L$ by itself, and consensus requires a quorum $\mathbb{Q}$. However, this view fails to acknowledge the presence of a centralized authority, the MSP, who chooses the validator set. Having an MSP administrating the network’s validators could inherit the biases of MSP in choosing validators and could potentially result in a biased quorum $\mathbb{Q}$ assembled by an (un)trusted intermediary. Moreover, the MSP is a point of centralization, requiring a trusted intermediary and consequently, causing the protocol to lose decentralization, see Fig. 1.

The goal of L4L is to liberate the permissioned Libra blockchain from its decentralization-inhibiting MSP to render it permissionless. Thus, there is a need to eliminate the requirement for a trusted intermediary, the MSP. However, a BFT-based network needs a fixed set of validators to guarantee liveness and safety. An MSP plays a crucial role in effectively administering the validators in the network, i.e., the MSP approves requests for joining the validator set VS using the identity of that node in the real world. Perhaps the most severe disadvantage of eliminating the MSP is that there is no identity associated with candidates in the validator set, and this identity has to be established by other means in a permissionless setting.

Let us review the existing practices in establishing identity (building Sybil resistance) in permissionless blockchains. PoW blockchains use computational power as a proxy for identity, raising concerns about eco-friendliness [42, 43]. Another prominent approach is proof of stake (PoS), wherein the validators stake in their assets as native tokens to establish identity. Nevertheless, this approach requires token distribution such as initial coin offerings (ICOs) or airdrops. There is a need for establishing identity in a permissionless setting, and delay towers could be a promising alternative to existing approaches.

L4L uses delay towers to enable permissionless blockchains. The delay towers use Chia’s Pietzak VDF implementation with 120 million iterations and 512 bits for the length of prime numbers generated in the proof. This profile has an estimated lower bound of thirty minutes for generating each proof.

The miners evaluate proofs locally whereas the validators verify the validity of submitted proofs. The time employed for verifying the validity of proofs could instead be utilized for the client’s transaction processing; it is the cost L4L pays for decentralization. We benchmark the verify function’s execution time using 1500 samples, see probability distribution in Fig. 5 with a mean of 115.80 ms and a median of 114.56 ms.

If the length of the prime number generated as part of the proof deviates from 512 bits, the proof is rejected. Verification of invalid proofs of correct length has a mean of 12.6 ms (11% of valid proof computation) for 1500 samples as shown in Fig. 6. Assuming a validator submits 48 valid proofs (every thirty minutes) in an epoch, the overhead for verification is 5.52 seconds per validator per epoch. Extrapolating this to the entire validator set ($\mathbb{N}=100$) would result in 552 seconds in an epoch (0.0063%). We claim that the overhead for enabling decentralization is minimal.

We now turn to the experiments on mining the delay towers by analyzing the time taken by the evaluate method. We collected data from a Linux octa-core instance with 16 GB RAM (Intel DO-Regular model). The mean and median for 1790 samples are 2362 s and 2310 s, respectively, as shown in Fig. 7. The 25^th and 75^th percentile are at 2045 s and 2467 s, respectively. The range is wide from 1929 s to 3463 s, and subtle differences such as the compiler version could affect the execution time. Furthermore, these insignificant benefits in individual VDF proof computation times compound to significant tower height over time.

The VDF computation plays a vital role in the security of the network. One could impose software and hardware uniformity to address inconsistencies, requiring every miner to use the same configurations; however, this requirement could increase costs and be a challenge to police without affecting the network’s decentralization. Furthermore, trusted computing is more vulnerable than PoW [44]. As a countermeasure, L4L sets an upper limit on the tower height growth in an epoch to mitigate any variations different hardware may impose on VDF proof computations. The authors recommend using the number of epochs that a miner has mined a threshold $\mu$ of proofs, as an alternative to pure tower height, to select the top $\mathbb{N}$ validators. This alternative would ensure all the miners who meet a threshold to be considered equal irrespective of their CPU speeds.

As previously stated, L4L uses delay towers to provide decentralization without loss of sustainability. We measure the computational resources of running delay towers to understand the ecological impact. Using the same Linux instance as mentioned earlier, we collected the CPU consumption for building a delay tower over an epoch, as shown in the Fig. 8. The delay tower uses one CPU core instance in an octa-core processor, and there is a drop in CPU utilization between the proofs. Because the process cannot be parallelized, no more than one CPU core can ever build the same delay tower. The delay towers use minimal system memory or network for their processes. The data show that delay towers add minimal overhead to both the nodes and the network.

Intending to leverage the scalability benefits of permissioned blockchains in permissionless settings, L4L decentralizes the permissioned BFT-based Libra blockchain. To establish identities required for BFT networks, L4L utilizes delay towers that are puzzle towers with VDFs. Delay towers offer various benefits, including lowering the barriers to entry with minimal capital requirements; anyone with a CPU can mine delay towers. Importantly, PoET mining delay towers are environmentally sustainable as they use minimal computational resources, i.e., its sequential nature ensures no advantage from parallelization. Since the growth of a delay tower is linear, the advantage of peers in genesis decreases over time and provides an opportunity to anyone interested. Furthermore, delay towers enable bootstrapping a network without token sales, airdrops, or being susceptible to mining attacks.

With the limitations of the BFT network, we showed how network could scale from permissioned settings to permissionless setting. Let us measure the degree of decentralization using the Nakamoto coefficient. The Nakamoto coefficient is the minimum number of validators needed to collude to compromise the system, i.e., affect the safety or liveness of the network [45]. In a decentralized L4L network of hundred validators with no Sybils, 33 validators need to collude to affect the liveness because of the two-thirds requirement for a quorum $\mathbb{Q}$ and, hence, the Nakamoto coefficient for L4L liveness is 33. For reference, the Nakamoto coefficient for safety in Bitcoin and Ethereum is less than five [46]. Furthermore, it would be interesting to draw ideas from PoS approaches to design delegation and tower stacking as a mechanism to scale participation in consensus beyond the limits of BFT.

The authors are indebted to 00-de-lally and Zaki Manian who were instrumental in making this work possible. Finally, this work might not be possible if it were not for the broader community of blockchain technology enthusiasts and practitioners behind the 0L.network, an instance of the L4L design. The work presented in this paper was in part supported by NSERC.