1
PoVD: Efficient Consensus Protocol based on Verifiable Delay Function
arXiv:2609.21627v1 [cs.DC] 18 Sep 2026
Rui Jiang, Xintong Ling, Member, IEEE, Bin Cao, Senior Member, IEEE, Jiaheng Wang, Senior Member, IEEE, Xiqi Gao, Fellow, IEEE, Zhi Ding, Fellow, IEEE
Abstract—Consensus protocols ensure the robustness and scalability of blockchains and decentralized applications built on them. However, existing consensus mechanisms often impose high computational cost or require heavy communication overhead. To address these challenges, we propose proof of verifiable delay (PoVD), a lightweight consensus protocol based on the verifiable delay function (VDF). We present the detailed protocol of PoVD, including the block mining and verification rules, and illustrate how PoVD can flexibly adjust the block time distribution according to the network condition. Through mathematical proof, we point out that, under a relatively weak network assumption, PoVD can achieve a lower fork rate than PoW while maintaining the same throughput. Our experiments verify that PoVD exhibits low computation and communication complexity and can also improve the blockchain consistency, making it particularly suitable for resource-constrained nodes and bandwidth-limited networks. Index Terms—Blockchain, consensus protocol, distributed system, modeling technique, verifiable delay function (VDF).
I. I NTRODUCTION With the rapid development of distributed applications, blockchains have emerged as foundational infrastructures for supporting distributed systems across various sectors, such as telecommunications, the Internet of Things (IoT), and unmanned aerial vehicles (UAVs) [1]–[4]. As the core component of blockchain systems, the consensus protocol is required to maintain network consistency among participating devices and ensure the robustness and scalability of decentralized services and applications [5]–[8]. However, designing highly efficient consensus protocols for resource-constrained and bandwidthlimited environments remains challenging. In such environments, nodes often have limited resources and bandwidths and are unable to handle high-frequency message exchanges or intensive computational loads [9], [10]. Generally, existing blockchain consensus protocols can be broadly classified into two categories: interaction-based protocols that rely on multi-round message exchange and proofbased protocols that often require intensive computations. For example, practical Byzantine fault tolerance (PBFT) is a R. Jiang, X. Ling, J. Wang, and X. Gao are with the National Mobile Communications Research Laboratory, Southeast University, Nanjing 210096, China, and also with the Purple Mountain Laboratories, Nanjing 210023, China (e-mail: {ruijiang, xtling, jhwang, xqgao}@seu.edu.cn). J. Wang is also with School of Cyber Science and Engineering, Southeast University, Nanjing 210096, China. Bin Cao is with the State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China (e-mail: [email protected]). Z. Ding is with Department of Electrical and Computer Engineering, University of California, Davis, California, 95616 (e-mail: [email protected]).
well-known interaction-based protocol that achieves agreement through four sequential stages, including request submission, message propagation, verification, and commitment [11]. However, its O n2 messaging complexity incurs significant communication overhead [12]. Meanwhile, proof of work (PoW) is the most recognized proof-based consensus protocol [13]. In PoW, nodes compete in solving intensive cryptographic puzzles to generate the next block, which consumes significant computational resources. As one can see, both types of protocols have their drawbacks. On the one hand, interaction-based protocols require frequent multi-round message exchanges, which leads to high communication complexity and poor scalability for large networks. Especially, in bandwidth-limited networks, such repeated message exchanges can increase block propagation delay and raise the probability of forks, thereby undermining ledger consistency. On the other hand, energy-intensive mining process of proof-based protocols requires miners to use specialized hardware with extremely huge power consumption, which not only raises sustainability concerns but also limits more miners to participating in blockchain maintenance. As a result, an efficient consensus problem must take both communication overhead and computation cost into consideration. The verifiable delay function (VDF) has the potential to address the above key challenges. VDF is a cryptographic technique that cannot be accelerated through parallel computing [14]. Nodes cannot predict the result in advance but have to compute for a certain period of time to obtain the solution to VDF. That is, VDF can ensure that each node experiences a verifiable delay without consuming too much computing power, which is applicable for resource-constrained devices. Moreover, the output of the VDF can be efficiently verified, which can avoid multi-round interactions or a large amount of computations. Therefore, it is promising to use VDF to design advanced consensus protocols to reduce both communication overheads and computation consumption. A. Related Work Most existing lightweight consensus protocols are permissioned and based on message exchanges. Recent studies in [12], [15]–[17] aim to lower the consensus overhead of BFTstyle consensus by, e.g., localizing commit stage communication [15], streamlining the pre-prepare and prepare pipelines [16], or reducing the cost of verifying quorum certificates [17]. RAFT-based consensus protocols attempt to improve the heartbeat mechanism by embedding useful information into
2
Table I R ELATED LIGHTWEIGHT CONSENSUS PROTOCOLS . Ref.
Name
Year
Type
Design Focus
Role of VDF
Protocol Framework
[27]
/
2019
[28]
RandChain
2020
Permissionless
Resource consumption
Replace PoW
PoW-fashion
Permissionless
Communication overhead
Replace PoW
[15]
/
PoW-fashion
2020
Permissioned
Communication overhead
Not used
[29]
PBFT
PoSAT
2021
Permissioned
Dynamic availability consensus
Random beacon
Leader selection
[30]
R3V
2021
Permissioned
Communication complexity and fairness
Replace PoW
PoW-fashion
[18]
Weighted RAFT
2021
Permissioned
Communication latency
Not used
RAFT
[24]
VaaP
2022
Permissioned
Communication overhead
Not used
BFT
[31]
/
2022
Permissioned
Fairness
Random beacon
Leader election
[32]
Fairledger
2022
Permissioned
Resource consumption and fairness
Replace PoW
PoW-fashion
[16]
Fast-HotStuff
2023
Permissioned
Communication overhead
Not used
BFT
[33]
BLMA
2023
Permissioned
Resource consumption and communication latency
Not used
PBFT
[34]
Gorilla
2023
Permissioned
Protocol operation efficiency and safety
Random beacon
BFT
[22]
/
2024
Permissioned
Fairness
Not used
Leader election
[23]
/
2024
Permissioned
Protocol operation efficiency and safety
Not used
Leader election
[25]
/
2024
Permissioned
Communication latency
Not used
BFT
[26]
BitFT
2024
Permissioned
Resource consumption
Not used
BFT
[21]
/
2024
Permissioned
Protocol operation efficiency and safety
Not used
BFT
[35]
/
2024
Permissionless
Protocol operation efficiency and safety
Random beacon
Leader election
[36]
Sprints
2024
Permissionless
Resource consumption
Replace PoW
PoW-fashion
[37]
/
2024
Permissioned
Protocol operation efficiency and safety
Random beacon
BFT
[12]
GS
2024
Permissioned
Resource consumption
Not used
PBFT
[19]
SBC
2024
Permissioned
Resource consumption and communication latency
Not used
RAFT
[38]
PoVF
2025
Permissioned
Protocol operation efficiency
Random beacon
Leader election
[20]
PoRL
2025
Permissioned
Protocol operation efficiency and safety
Not used
Leader election
[17]
JUMBO
2025
Permissioned
Resource consumption and communication latency
Not used
BFT
heartbeat messages [18] or reducing the frequency of heartbeat transmissions [19]. Several works adopted a simpler approach to reduce consensus overhead via leader election and lightweight agreement workflows. [20], [21] used verifiable random function to simplify proposer selection. The authors of [22], [23] proposed committee-election mechanisms, which confine voting to small subsets to limit messaging. [24] employed a vote-based proof mechanism to simplify the proposal and confirmation workflow. [25] introduced decentralized coordinator services with verifiable global states. [26] designed a resource-efficient consensus protocol that combines multi-round sortition with vote-based confirmation. Most recently, VDF is introduced in consensus protocols as a cutting-edge technology [39]; however, it has not been well utilized yet. In general, VDF plays two roles in consensus protocols. First, VDF is used as the random beacon for leader or committee member elections. For example, [29], [31], [32], [34] leveraged the unpredictability of VDF outputs to elect leaders for generating new blocks. [35], [38] utilized VDF as a random timer, allowing only committee members within designated time windows to propose new blocks. In [37], VDF was introduced to support fixed-time polling in Byzantine agreement (BA) protocols and promoted election fairness and efficiency in the consensus process. In such consensus protocols, the core idea of introducing VDF is to improve the reliability of the election results.
As another approach, VDF is used as a mining puzzle to replace the hash function. [27], [28] are two typical examples where the first miner solving the VDF puzzle wins the right to create a new block. Some, such as Sprints [36], use the same principle but associated VDF-based mining with hash puzzles. These protocols [27], [28], [36] did not prevent miners from performing parallel computations with different VDF inputs. As a result, miners may attempt to accelerate block generation by investing computational power, leading to high energy consumption. The characteristics of these schemes are similar to PoW. To resist parallel computing, R3V [30] limited the VDF input and excluded the block hash from the mining process. However, without involving the block hash into the mining process, such a consensus protocol cannot protect the on-chain information from being tampered with. Table I summarizes the above related studies on consensus protocols. We can identify two fundamental drawbacks of existing works from Table I. Most lightweight consensus protocols without using VDF are often based on intensive interactions. Although some designs attempt to reduce communication complexity, they still require repeated broadcasting and flooding, imposing a heavy burden on the network. Particularly, as the network size grows, these schemes are not scalable because of rapidly increasing communication overhead. As a result, some works have to set the scenario within single-hop or single-cell networks, which are somehow centralized.
3
Truly, VDF can largely reduce the amount of message exchange. However, the role of VDF is still questionable. The existing consensus protocols based on VDF face the dilemma between computational efficiency and blockchain security. From the above review, one can see that the dilemma comes from how the protocol associates the block content or its digest, such as the block hash, with the VDF input. The security and integrity of most blockchains are based on the connections between blocks based on the block hashes to protect the on-chain data from being modified. However, when mining, miners can change the block content (e.g., change the order of transactions) and generate multiple block hashes so that they can compute with multiple VDF inputs in parallel. In this way, miners can gain extra advantages by investing additional computing power, resulting in a similar energy consumption problem as PoW does. However, if we remove the block content (or its digest) from the VDF computing, then the new chain structure cannot guarantee the integrity of on-chain information. The above dilemma may be one of the important reasons why VDF has not been widely used for consensus protocols. B. Our Contributions In this work, we propose an efficient consensus protocol based on VDF, named proof of verifiable delay (PoVD), which is both communication- and computation-efficient and suitable for deployment in resource-constrained and bandwidth-limited environments. PoVD does not require intensive message exchange and can operate in a permissionless setting. PoVD introduces VDF to resist parallel computing so that miners cannot gain advantages by increasing computational resources, and thus, PoVD can effectively reduce energy consumption. Furthermore, PoVD can flexibly adjust the block time distribution so that it can achieve better chain performance according to the network condition. Our experiments show that PoVD is suitable for resource-constrained devices in bandwidth-limited networks. We summarize our main contributions as follows: • We design the PoVD consensus protocol with the blockchain structure and illustrate the entire consensus process in detail, including VDF-based mining, VDF proof generation, and block verification. • Since PoVD can adjust the block time distribution, we build a mining model under arbitrary block time distributions and assess the performance of PoVD in terms of fork rate and blockchain throughput. • Through rigorous mathematical proof, we point out that, under a relatively weak network condition, PoVD can achieve a lower fork rate than PoW with the same blockchain throughput. • By comparing with several representative benchmarks, we demonstrate PoVD’s low computational and communication complexities and highlight PoVD’s advantage in improving blockchain consistency. The code is available at: https://github.com/RayJ9/VDF-based-PoVD. The remainder of the paper is structured as follows. Section II presents the system model. Section III describes the basic principles of VDF. Section IV illustrates the PoVD protocol.
Section V models the PoVD mining process. Section VI shows the superiority of PoVD regarding fork rate. Section VII presents experimental results, and Section VIII concludes the paper. II. S YSTEM M ODEL A. Byzantine Agreement Setting Our study is based on the BA setting [37], [40], [41], which defines a system with a finite number of participants and models the system’s operation by dividing real-world continuous time into discrete rounds of equal duration. All nodes operate under the same constraints in each round. The discrete BA setting can approach the accurate continuous-time performance with a shorter round duration. Specifically, in BA setting, the system comprises n miners. These miners attempt to generate new blocks by computing random oracles in every round. For example, in PoW, the random oracle is the hash function such as SHA256. In general, if a miner obtains a valid oracle solution, the miner wins the right to generate a new block. The new block will be broadcast to the entire network after being generated. The rest of the miners will verify it based on the verification criteria of the consensus protocol. If the block is verified, miners will add it to their local chains to synchronize the state. Usually, the verification time is negligible compared to the time spent generating new blocks [37]. Furthermore, we assume a flat model where all miners possess identical computational capabilities, i.e., every miner performs the same number of oracles per round [40]. Even though this assumption may not hold in practice, we can cluster the flat-model miners into larger virtual entities each of which comprises more than one flat-model player to describe the practical non-flat case where miners have differing computational capabilities. For example, if there are 10 miners, with half possessing twice the computing power of the others, we can create a new model of 15 miners, where 10 pair up to form a new unit. This adjustment allows the analysis to proceed as though there are 15 equivalent miners. B. PoW in BA Setting Next, we use PoW as a typical example to illustrate the above BA setting. Miner i continuously attempts different inputs, i.e., nonce, to calculate hash values satisfying the difficult target: yh,i = Hash (yh−1 , IDi , mh,i , πh,i ) < φ,
(1)
where h is the blockchain height, yh−1 represents the hash of the previous block, IDi is the miner’s identity, mh,i is the block payload data represented by its digest, πh,i denotes the nonce, and φ indicates the current hash target. When a miner finds a nonce whose hash value is smaller than the target φ, the miner generates a new block with the corresponding hash value and broadcasts it to the other miners. The newly generated block will be added into the main chain if there is no other fork, and the blockchain grows in this way. The hash target φ is determined by the mining difficulty to control the average
4
block time. For example, a larger hash target implies an easier mining process and thus a shorter block time. We show the workflow of PoW in Fig. 2(b) of Section IV. C. Network Model Usually, block propagation inevitably experiences delays, particularly in limited network environments. To characterize the propagation process, we introduce a d-dimensional propagation vector: wd = (w0 , w1 , . . . , wd−1 ) ,
(2)
where d is the maximum propagation delay. The element wi ∈ [0, 1) for i = 0, 1, ..., d − 1 represents that nwi miners receive the block in round r + i if the block is generated in round r. Note that, if a block is generated in round r, n − 1 miners are not yet aware of the block in round r, implying that w0 is always 1/n. During the propagation process, more miners will receive the block, so w0 ≤ w1 ≤ · · · ≤ wd−1 < 1. Given the maximum propagation delay d, all the miners will receive the block in round r + d. In an ergodic and stable network, wd can be statistically measured through experimental results. Furthermore, we define the network capability indicator c as d−1
c=
1X wi , d i=0
(3)
which can reflect the network’s propagation capability. Given the maximum delay d, a larger c implies more miners receive the block earlier, i.e., a faster propagation speed. Note that the network capability indicators c are incomparable for two networks with different d. Network propagation model does not involve the number of miners and thus can provide convenience for subsequent mathematical modeling. III. V ERIFIABLE D ELAY F UNCTION A. Definition This section will provide a detailed definition of VDF and explain its principle [39]. A verifiable delay function is a function f : Z → Y that requires a predetermined amount of time to compute and cannot be accelerated by parallel processing. Every input z ∈ Z has a valid output y ∈ Y. Moreover, once the computation is complete, anyone can verify the output quickly. More specifically, a VDF that implements a function Z → Y is a tuple of three algorithms: • Setup (sp, T ) → pp is a randomized algorithm that takes a security parameter sp and a time bound T , and outputs a public parameter pp. • Eval (pp, z) → (y, π) takes an input z ∈ Z and outputs the VDF result y ∈ Y and the proof π. • Verify (pp, z, y, π) → {accept; reject} outputs accept if y is the correct evaluation of the VDF on input z, or outputs reject if y is incorrect. Meanwhile, a VDF must satisfy three properties: • Bounded-evaluation time. Eval (pp, z) → (y, π) runs no less than T time, for all z ∈ Z and all pp output by Setup (sp, T ).
Serialization. A parallel algorithm A that uses at most poly (sp) processors and runs in time less than T cannot compute the function. Specifically, for a random z ∈ Z and pp output by Setup (sp, T ), if the correct result of Eval (pp, z) is (y, π) then Pr (A (pp, z) = y) is negligible. • Uniqueness. For a given input z ∈ Z, exactly one y ∈ Y will be accepted. Specifically, given pp as an input, let A be an efficient algorithm that outputs (z, y, π) such that Verify (pp, z, y, π) = accept. Then Pr (A (pp, z) ̸= y) is negligible. •
B. Wesolowski’s Implementation Currently, there are several implementation approaches to VDF. This subsection describes Wesolowski’s scheme [39], which serves as the foundation for our proposed PoVD. Specifically, the input consists of a tuple (G, z, y, T ), where G denotes an integer group with finite elements. A prover and a verifier are included in the following protocol to prove T y = z (2 ) ∈ G. Let Primes (κ) be the set containing the first 2κ primes. 1) The verifier checks whether z, y ∈ G or not. 2) The verifier sends to the prover a random prime v sampled uniformly from Primes(κ). 3) The prover computes u, ε ∈ Z++ such that 2T = uv + ε with 0 ≤ ε < v, and sends π ← z u to the verifier. Here, Z++ denotes the positive integer set. 4) The verifier computes ε ← 2T mod v and outputs accept if π ∈ G and y = π v z ε ∈ G. The verifier computes ε ← 2T mod v, which only takes log2 T multiplications in Z++ /v. In [39], a constant space algorithm for efficiently computing π = z u ∈ G is implemented. Hence, the verifier is efficient.
IV. P OVD C ONSENSUS P ROTOCOL A. Overview We first illustrate the block structure of PoVD and how blocks connect to one another in Fig. 1. Every block includes the block proposer’s ID, the last block’s VDF result yh−1 , the current block’s payload data mh (recorded by the hash value), the VDF result yh , and the proof πh . Similarly to PoW, PoVD also has the mining and verification phases, as shown in Fig. 2(a). (For comparison, we also show the workflow of PoW in Fig. 2(b).) Specifically, in the PoVD mining process, miners compute the VDF, generate the necessary proofs, and encapsulate them into the proposed blocks. The miner who first solves the VDF puzzle earns the right to propose a new block. Once a new block is proposed, other miners in the network verify it, i.e., the verification phase. They verify the VDF solution’s correctness and proof and check the block’s consistency with the previous block. If a block passes all the verification, it is appended to the miner’s local blockchain. The blockchain then grows in this manner.
5
Figure 1. Illustration of PoVD block structure.
B. PoVD Mining Consider a blockchain with height h − 1. For miner i attempting to generate a block at height h, the VDF mining process begins with generating the input zh,i and time parameter Th,i : zh,i = Hash (yh−1 , IDi , mh,i ) ,
(4)
Th,i = g (Hash (yh−1 , IDi )) .
(5)
Here, yh−1 is the VDF result from the previous block at height h − 1, which is usually the same for all miners in the system, and therefore, we omit the subscript i representing the winner of the last block. IDi is the miner’s identity, and mh,i is the block hash representing the block payload data. Meanwhile, the calculation of zh,i and Th,i requires two hash functions: • Hash: S → C, which is a standard cryptographic hash function, with S representing the set of strings of arbitrary length and C denoting a set of integers. This function maps S uniformly into C. • g: C → G, which maps integers from C to another integer group G with predefined settings. The number and the range of elements in the set C depend on the function Hash. For example, in the widely used SHA256, C is the set of integers from 0 to 2256 − 1, with each element having an identical probability of being selected. For any arbitrary outputs x, its values are uniformly distributed among the set C, i.e., Pr (x = Hash (s)) =
1 . |C|
(6)
That is, in (5), the output of the function Hash, which is also the input of g, follows a uniform distribution. In PoVD, miner i iteratively computes the square of zh,i for Th,i times in G to derive yh,i by the fast power algorithm, yielding the VDF result: Th,i
2 yh,i = zh,i
2g(Hash(yh−1 ,IDi ))
= (Hash (yh−1 , IDi , mh,i ))
. (7)
Miner i must complete Th,i rounds’ computation to generate a valid VDF result (if we assume that each miner computes one square per round). Hence, Th,i is the time to generate a new block, i.e., the so-called verifiable delay in PoVD. The function g can control the distribution of Th,i , i.e., the
(a)
(b) Figure 2. Block mining process and verification rules of PoVD and PoW consensus protocols. (a) PoVD. (b) PoW.
block time distribution, given the uniformly distributed Hash output shown by (6). That is how PoVD adjusts the block time distribution. Upon obtaining the VDF result yh,i , miner i generates the proof πh,i according to the following steps: 1) Determine a factor v of the decomposed exponent. A predetermined rule is used to select one of the factors of the exponent. For example, v can be the prime indexed by Hash (yh,i , zh,i , Th,i ) within the set Primes(κ). 2) Find another exponent u satisfying 2Th,i = uv+ε, where 0 ≤ ε < v. u 3) Generate the proof πh,i = zh,i . Usually, the time to generate the proof is negligible. Once miner i completes these steps, it can directly package the computed results into a block and broadcast the block to the network. The consensus process guarantees that miner i must experience the delay Th,i with a verifiable proof. That is why the consensus protocol is called proof of verifiable delay.
6
By comparing Fig. 2(a) and Fig. 2(b), we can find the similarities and differences between PoW and PoVD. Essentially, both PoW and PoVD are races among miners. Both protocols require miners to generate a new block by finding a solution satisfying certain conditions. Such a process automatically embeds a period of time into the block generation process to reduce the probability that multiple new blocks are generated simultaneously, which would result in forks. In PoW, a miner can perform hash trials in parallel to increase the winning probability. As a result, PoW consumes immense computational power and often requires specific hardware such as mining rigs. In PoVD, miners cannot gain extra payoff by investing more in computational resources since the time to generate a new block cannot be accelerated by parallel computing. Hence, PoVD is more energy efficient than PoW since the race on computational resources becomes meaningless. C. PoVD Verification In this subsection, we show the verification rule of PoVD. As shown in Fig. 1, the PoVD verification requires the following elements: the miner ID, the calculation input of the current block zh , the time parameter Th , the proof πh , the calculation result yh and the calculation result of the previous block yh−1 . If any of them is absent, the block should be considered illegal. Except for zh and Th , all other elements can be directly obtained from the block. Every miner can derive zh and Th through (4) and (5), respectively. Based on these elements, miners can further calculate v and ε. As mentioned in Section IV-B, the method for generating v is predetermined and known to all miners. Subsequently, miners derive ε by performing the modulus operation on v with 2T . Finally, they calculate yh∗ = π v z ε and compare it with yh . If the two values match, the block passes the verification. We also need to verify the chain consistency. The consistency verification requires the previous block’s computation result to be included in the currently received block’s header, ∗ denoted as yh−1 . This value is also in the previous block’s header as yh−1 . If these two values are the same, the block passes the consistency check. From the description in the above section, yh−1 is derived from zh−1 , and the generation of zh−1 depends on the previous block. Therefore, the consistency of yh−1 directly determines whether the data between consecutive blocks is consistent. As shown in Fig. 1, blocks are connected through the VDF result yh . D. Discussions on Security and Efficiency Remark that most VDF-based consensus protocols face the dilemma between energy efficiency and security. For instance, R3V [30] restricts each miner to compute the VDF with a unique input. In this way, R3V can prevent parallel computation and reduce energy consumption; however, such design does not involve the block payload data or its digest, i.e., the block hash, in the VDF input so that R3V cannot protect the on-chain information from being tampered with. In contrast, [27], [28], [36] include the block hash as one of the VDF inputs to protect the payload data, but miners can
revise the block payload data and create multiple different digests as the VDF inputs by, e.g., simply exchanging the order of transactions, for parallel VDF computing to obtain extra mining profits. It now seems that the two goals, efficiency and security, cannot be achieved simultaneously. To address this dilemma, PoVD gives an alternative design. To guarantee the blockchain integrity, PoVD involves the block payload data mh,i , represented by the hash value, into the VDF computation. But modifying the payload data mh,i does not affect the time Th,i for a miner to obtain the VDF output, since the verifiable delay Th,i solely depends on the previous VDF output yh−1 and the miner IDi . Miners can generate multiple blocks by parallel computing; however, all of these blocks require the time Th,i to be generated. That is, miners cannot accelerate block generation by increasing computational power. Note that PoVD involves the miner’s identity into the VDF computation, just like most VDF-based consensus protocols. It is inevitable since the mining process must associate with an identity. However, if a miner can create multiple identities, i.e., launch a Sybil attack, it can increase the chance to be the first one to generate a new block. To address this, resourcebased Sybil resistance mechanisms are typically employed to make identity creation prohibitively costly [42], [43]. One typical solution is to introduce a registration process for newlyjoined miners. For example, in protocols such as Algorand [44] and OmniLedger [45], newly-joined miners are required to stake some funds and sign a registration transaction with their private key. The miner is allowed to participate in the consensus process only if the registration transaction is confirmed by the network. Other existing miners can verify the identity of the block proposer using the public key. In these solutions, creating multiple identities incurs both time and monetary costs. These existing blockchain projects based on Algorand and OmniLedger illustrate that the registration process is an effective method against Sybil attacks. Anyway, one miner can still generate more than one block at the same height, to split the network and compromise the ledger consistency. Specifically, a malicious miner may broadcast multiple blocks at the same height to different peers, referred to as equivocation, to increase the chance that one of them gets accepted into the main chain. This issue can be addressed by using Casper, a stake-based finality mechanism [46]. In Casper, only one block can be finalized, so mining multiple blocks at the same height becomes unprofitable. Moreover, Casper’s voting process can identify a miner’s misbehavior of broadcasting multiple blocks at the same height, and such equivocation will be detected and penalized via slashing. Meanwhile, a malicious miner may still hold the generated blocks and release them strategically to launch a long-range double-spending attack by maintaining a private branch. This attack can be defended by the finalization mechanism based on validator voting. In Casper, a checkpoint becomes finalized after it has received sufficient validator support and its validity has been further confirmed in the following stage. Therefore, once the checkpoint is finalized, the malicious competing branch can no longer replace it. Hence, even a long-range private fork revealed later cannot revert finalized checkpoints,
7
which greatly enhances the difficulty of such manipulation. Besides the above attacks, the attackers may launch more advanced attacks such as the grinding attack. Miner i may still mine multiple candidate blocks with different payload ∗ data mh,i and find yh,i to minimize the block generation time for the next block Th+1,i . If miner i’s block is successfully ∗ included in the main chain with such a carefully chosen yh,i , then it may take advantage of winning in the next height since it chooses a short Th+1,i . To mitigate this attack, we can use a binding commitment mechanism [47], [48], under which each miner must broadcast a claim to bind the digest of the payload data before starting the mining process, i.e., before calculating the VDF. When other miners receive the block corresponding to the previously received claim, they firstly validate that the block contains the same payload data as the claim, so that grinding by changing the payload after mining is not applicable. Besides, they perform a local timing check, which is to validate that the duration between receiving the claim and the corresponding block must be larger than Th,i . This mechanism ensures that the claim is generated before the VDF calculation begins. Otherwise, if a miner attempts to launch a grinding attack and broadcasts the claim after completing the VDF computation, it must wait for roughly another Th,i , which greatly reduces the benefit of such an attack. Only when both validations pass will the verifier continue the subsequent process, otherwise this block will be considered invalid locally.
If we would like to let T follow a geometric distribution like PoW, we can set the function g as follows: x r−1 r < (1 − p) , (9) g (x) = r, if (1 − p) ≤ |C| where 0 < p < 1, x = 0, 1, ..., |C|, and r = 1, 2, ... In (9), as r increases, the range of x that satisfies the corresponding inequalities decreases geometrically. Since the input x is uniformly distributed over C by the Hash function, the resulting distribution of T obeys: r−1
Pr (T = r) = (1 − p)
r−1
= p (1 − p)
Pr (Ur = 1) =np̃ (r) (1 − p̃ (r))
(1 − p̃ (k)) , for r = 0, 1, ...
(10)
r−1 Y
n
(1 − p̃ (k)) , (11)
k=0 r−1 Y
n
(1 − p̃ (k)) ,
(12)
k=0
As we have shown in (5), PoVD can flexibly adjust the block time distribution by setting the function g properly. Note that most PoW-style consensus protocols can only set the average block time by adjusting mining difficulty, while the block time distribution always obeys a Bernoulli distribution. It can be viewed as an extra advantage of PoVD beyond its communication- and computation-efficiency. However, the mining process becomes more difficult to model under an adjustable block time distribution. We have to rethink the mining model and construct a more general mining process model with arbitrary block time distributions before quantifying PoVD’s improvement. According to the PoVD protocol, each miner’s time parameter Th,i is independent, identically distributed, and is determined by the function g in (5). Therefore, we drop the subscript indicating the block height and miner identity and define the random variable T to represent the number of rounds a miner needs to generate a new block. The probability mass function (PMF) of T is denoted as Pr (T = r). Furthermore, we introduce p̃ (r) to represent the probability that a miner generates a block in round r after the previous block has been generated. Notably, p̃ (0) = 0. The PMF of T is expressed as r−1 Y
n−1
n
A. Rethink the Mining Model
Pr (T = r) = p̃ (r)
, for r = 1, 2, ...
One can easily obtain the block time distribution p̃ (r) = p for all r = 1, 2, ... In other words, the probability that a miner mines a new block is identical for every round, which aligns with the property of PoW. In the following analysis, we focus on the block time distribution p̃ (r), since the random variable T can be easily characterized by p̃ (r). Let the random variable Ur be the number of blocks generated in round r with no blocks generated in the previous r − 1 rounds. Then, we have
Pr (Ur ≥ 1) = (1 − (1 − p̃ (r)) )
V. P ERFORMANCE A NALYSIS
r
− (1 − p)
(8)
k=0
The meaning of (8) is clear. A miner successfully mining a new block in round r means that it does not generate any block in the first r − 1 rounds, but succeeds in round r.
which represent the probability that exactly one block is generated and the probability that at least one block is generated, Qr−1respectively.nThese two equations share a common term k=0 (1 − p̃ (k)) , which represents the probability that no block is generated in the first r − 1 rounds. Equations (11) and (12) are the basis of the blockchain performance analysis regarding fork rate and block time under a given distribution p̃ (r). B. Fork Rate and Block Time We first derive the fork rate. Assume that the network is in a consistent state in round 0, i.e., every miner reaches an agreement on the main chain. We consider the event Ar , where only one block is generated in round r, and no additional blocks are generated by any other miners in the subsequent d rounds during its propagation process. The probability of the event Ar is given by Pr (Ar ) = Pr (Ur = 1)
d−1 Y
(1 − p̃ (r + j))
n(1−wj )
.
(13)
j=1
S∞ We can use the event A = r=1 Ar to describe that only one block is generated from a consistent state in round 0. Note that the complement of event A means at least one fork occurs, and thus, the fork rate F (p̃ (r)) can be expressed as ! ∞ ∞ [ X (a) F (p̃ (r)) = 1 − Pr Ar = 1 − Pr (Ar ) , (14) r=1
r=1
8
F (p̃ (r)) = 1 −
∞ r−1 X Y d−1 Y
n−1
np̃ (r) (1 − p̃ (r))
n
n(1−wj )
(1 − p̃ (k)) (1 − p̃ (r + j))
.
(15)
r=1 k=0 j=1
where (a) is because every Ar is exclusive. By substituting (11) and (13) into (14), we obtain the expression for the fork rate in (15) with an arbitrary block time distribution p̃ (r). According to (15), Q the fork rate is composed of three comd−1 n(1−wj ) ponents. The term + j)) represents j=1 (1 − p̃ (r Q r−1 n the impact of network propagation, k=0 (1 − p̃ (k)) is the probability that no block is generated in the first r − 1 rounds, n−1 and np̃ (r) (1 − p̃ (r)) corresponds to the event where only one miner generates a block in round r. The combination of these three parts indicates that the network has no fork. The fork rate essentially reflects the consistency of the blockchain. Forks mean that different miners have different visions on the main chain. Therefore, the fork rate (15) is an important quantitative metric of blockchain’s consistency describing the fundamental property of distributed systems. The lower the fork rate, the more consistent the blockchain is. Block time is the expected number of rounds between two consecutive blocks. The expected number of rounds for block generation can be obtained from (12), yielding the (average) block time B (p̃ (r)): B (p̃ (r)) = =
∞ X
p̃a (r) = p and (3) into (15), we can derive the fork rate F (p̃a (r)) for PoW as follows: P n d− d−1 wi )
i=0 np (1 − p) ( F (p̃a (r)) = 1 − n 1 − (1 − p)
nd(1−c)
=1−
rPr (Ur ≥ 1) n
n
r (1 − (1 − p̃ (r)) ) (1 − p̃ (k)) . (16)
r=1 k=0
Notably, our derivation is based on the probability that at least one block is generated, i.e., Pr (Ur ≥ 1). Hence, the inverse of block time accurately reflects the main chain’s growth rate [49]. The smaller the block time, the more transactions the blockchain can process per unit of time, resulting in higher throughput. Therefore, block time in (16) can be viewed as a critical metric for quantifying the throughput of a blockchain. In conclusion, we rebuild a blockchain mining model with an arbitrary block time distribution and derive the fork rate in (15) and block time in (16) in closed forms. Note that the above modeling and analysis are derived from a consistent state. The obtained fork rate and block time are accurate under this assumption and provide good approximations even without the assumption, as shown in the experimental results.
C. PoW as an Example Note that our mining model also works for PoW. Given the mining difficulty and the number of hash trials in a round, the probability that a miner generates a block in a round in PoW is constant. Hence, T can be modeled as a geometric distribution, and the block time distribution of PoW can be denoted as p̃a (r) = p, where r = 1, 2, ... By substituting
.
(17)
In fact, (17) is a conditional probability. The denominator, 1 − n (1 − p) , represents the probability that blocks are generated nd(1−c) in a given round. The term np (1 − p) represents the probability that only one block is generated, and the exponent nd (1 − c) represents the number of miners who have not received the block during the d rounds propagation process. In [50], the authors obtained similar results by calculating the probability of no block being generated during propagation. Similarly, by substituting p̃a (r) = p into (16), we can derive the average block time of PoW B (p̃a (r)) as follows: B (p̃a (r)) =
∞ X
n
r (1 − (1 − p) ) (1 − p)
n(r−1)
r=1
=
r=1 ∞ r−1 Y X
np (1 − p) n 1 − (1 − p)
1 n. 1 − (1 − p)
(18)
Note that, in PoW, the probability that at least one block is n generated within a round is 1 − (1 − p) . As a result, the time to generate new blocks can also be modeled as a geometric 1 distribution, with an expectation of 1−(1−p) n , which is exactly the block time of PoW. As shown in (18), increasing either p or n reduces the block time. This is because a higher p or n increases the probability that miners mine a new block in each round, which reduces the number of rounds to generate a new block and thus lowers the block time. As one can see, both F (p̃a (r)) and B (p̃a (r)) of PoW are determined by the parameters of p and n. Meanwhile, PoVD can flexibly adjust the fork rate and block time by setting the block time distribution p̃ (r) via the function g, which is another significant advantage of PoVD. VI. P OVD B LOCK T IME R E -D ISTRIBUTION A. δ-spaced Block Time Distribution The fork rate and block time are two key metrics of blockchains, serving as quantitative indicators of consistency and throughput, respectively. A lower fork rate reflects higher consistency, while a shorter block time indicates higher throughput. However, although reducing block time can improve throughput, it also increases the probability that more than one block is generated during the propagation of another block, leading to a higher fork rate. Therefore, we should balance the trade-off between fork rate and block time in the blockchain design. Therefore, can we reduce the fork rate F (p̃ (r)) with the same block time B (p̃ (r)), by adjusting the distribution p̃ (r)?
9
Due to the complicated expressions of F (p̃ (r)) and B (p̃ (r)), this is a very challenging problem. So far, the optimal block time distribution to minimize the fork rate under the block time constraint remains open. However, we would like to provide the δ-spaced block time distribution, denoted by p̃δ (r), that can achieve a lower fork rate than PoW. The δ-spaced block time distribution p̃δ (r) is given by ( pδ , r = 1, δ + 1, 2δ + 1, ... p̃δ (r) = (19) 0, otherwise, where δ is a positive integer. Essentially, under the δ-spaced block time distribution p̃δ (r), a miner can only mine a block every δ rounds. In this case, we can set the function g to be g (x) = r, if (1 − pδ )
r+δ−1 δ
≤
r−1 x < (1 − pδ ) δ , |C|
(20)
where r = 1, δ + 1, 2δ + 1, ..., and 0 ≤ x ≤ |C|. In a network with the maximum propagation delay d, the δ-spaced block time distribution p̃δ (r) with δ = d yields the fork rate F (p̃δ (r)) and the block time B (p̃δ (r)), given by
where ω (n) > 0 and ln (1 − q) < 0. Finally, we can prove (23): ln ω (n) /d 1 ln ω (n) /d 1 − < lim − ln (1 − q) n n→∞ ln (1 − q) n 1+dq−q 1 exp ln − 1 n 1−q 1 1 (a) = ln lim ln (1 − q) d n→∞ exp 1 ln 1 − 1 n 1−q 1+dq−q 1 n ln 1−q 1 1 (b) = ln lim ln (1 − q) d n→∞ 1 ln 1 n 1−q 1 ln (1 + dq − q) 1 (c) ln − , (26) = ln (1 − q) d d ln (1 − q) where (a) is because limn→∞ n1 = 0 and rewrites the formula, (b) is based on exp (x) − 1 ∼ x as x → 0, and (c) simplifies the formula. Lemma 2. Let d = 1, 2..., be a constant. Then, for any q ∈ (0, 1), the following holds:
n−1
npδ (1 − pδ ) n , 1 − (1 − pδ ) n δ (1 − pδ ) B (p̃δ (r)) = n + 1. 1 − (1 − pδ ) F (p̃δ (r)) =1 −
(21)
ln
ln(1+dq−q) 1 d − d ln(1−q)
ln (1 − q)
Lemma 1. Let q ∈ (0, 1) and d = 1, 2..., be constants. Then, for any n = 1, 2, ..., the following inequality holds: ln(1+dq−q) 1 ln − d d ln(1−q) ln ω (n) /d 1 − < . (23) ln (1 − q) n ln (1 − q) Proof. We first prove ω (n) < 0. Let f1 (n) =
1+dq−q 1−q
n1
−
n1
1 1, which is the numerator of ω (n), and f2 (n) = 1−q −1, which is the denominator. Note that for any q ∈ (0, 1), we have 1+dq−q 1 > 1−q > 1, and we further have f1 (n) > f2 (n) > 0 1−q ′ and f1 (n) < f2′ (n) < 0. Hence, the derivative of ω (n), i.e., ω ′ (n), is
ω ′ (n) = < =
1 (f2 (n)) 1 (f2 (n)) f1 (n) (f2 (n))
′ ′ 2 (f2 (n) f1 (n) − f1 (n) f2 (n)) ′ ′ 2 (f1 (n) f1 (n) − f1 (n) f2 (n)) ′ ′ 2 (f1 (n) − f2 (n)) < 0.
d 1 − . 2 2
(27)
Proof. We define the left-hand side of (27) as function h (q):
h (q) =
To further compare PoVD with PoW under the same average block time, we give two lemmas that will be used to bound the threshold of the network capability indicator.
<
(22)
B. Superiority of PoVD
′
(24)
Therefore, the left side of (23) increases in n since ∂ ln ω (n) /d 1 ω ′ (n) 1 − = + 2 > 0, (25) ∂n ln (1 − q) n ω (n) ln (1 − q) n
ln d1 1 − ln(1+dq−q) ln(1−q)
ln (1 − q) 1 1 h1 (q) = ln − , h2 (q) d dh2 (q)
(28)
where h1 (q) = ln (1 + dq − q) , and h2 (q) = ln (1 − q). Next, we prove that h (q) decreases in q. The derivative of h (q) is given by: h′ (q) =
1 2
(h2 (q) − h1 (q)) (h2 (q)) 1 h1 (q) · (h1 (q) − h2 (q)) h′2 (q) ln − d dh2 (q) ! ′ h1 (q) 3 (h2 (q)) . − (29) h2 (q)
The denominator of h′ (q) is negative since h2 (q) − h1 (q) = ln ((1 − q) / (1 + (d − 1) q)) < ln 1 = 0. We would like to show that the numerator of h′ (q) is positive. Note that d−1 > 0) and h2 (q) h1 (q) increases in q (since h′1 (q) = 1+dq−q 1 ′ decreases in q (since h2 (q) = q−1 < 0), so h1 (q) /h2 (q) in′ creases in q. Therefore, we further have (h1 (q) /h2 (q)) > 0, and h1 (q) h1 (q) ln (1 + (d − 1) q) > lim+ = lim+ h2 (q) q→0 h2 (q) q→0 ln (1 − q) (d − 1) q (a) = lim+ = 1 − d, −q q→0
(30)
10
+ where (a) isbased on ln (1 + x) ∼ x as x → 0 . Hence, h1 (q) 1 1 we have ln d − dh2 (q) < ln d · d = 0. Now, we can summarize each term of the numerator of h′ (q): > 0, h1 (q) − h2 (q) = ln 1+(d−1)q 1−q 1 ′ h (q) = q−1 < 0, 2 h1 (q) < 0, ln d1 − dh (31) ′ 2 (q) h (q) 1 > 0, h2 (q) 3 3 (h2 (q)) = (ln (1 − q)) < 0.
Therefore, the numerator of h′ (q) is positive, and h (q) decreases in q. Finally, we can prove (27): h (q) < lim+ h (q) q→0 −1 ln 1 + d1 − ln(1+dq−q) d ln(1−q) (a) = lim ln (1 − q) q→0+ (b)
= lim+
Figure 3. Threshold cth of network capability indicator under different block time.
Substituting (18) and (22) into B (p̃δ (r)) = B (p̃a (r)) with δ = d yields
ln(1+dq−q) 1 d − d ln(1−q) − 1
−q (1 − d) ln (1 − q) − ln (1 + dq − q) (c) 1 = lim d q→0+ −q ln (1 − q) 1 (1 − d) ln (1 − q) − ln (1 + dq − q) (d) = lim+ d q→0 q2 1 d−1 (d − 1) 1−q − 1+dq−q (e) 1 = lim d q→0+ 2q 2 d q − dq (f ) 1 = lim d q→0+ 2q (1 − q) (1 + dq − q) d2 q − dq d 1 (g) 1 = lim+ = − , d q→0 2q 2 2
n
q→0
where (a) introduces infinitesimal term, i.e., 1 ln (1 + dq − q) lim+ − − 1 = 0, d d ln (1 − q) q→0
n
(1 − pδ ) =
n
where ω (n) is given by (32)
1+dq−q 1−q
(33)
With the two lemmas above, we can summarize the superiority of PoVD in terms of fork rate in the following theorem. Theorem 1. Assume that a network with the maximum delay d 1 . By has the network capability indicator satisfying c ≤ 12 − 2d setting δ = d, PoVD with the δ-spaced block time distribution p̃δ (r) can achieve a lower fork rate than PoW under the same average block time, i.e., F (p̃δ (r)) < F (p̃a (r)) , B (p̃a (r)) = B (p̃δ (r)) . Proof. According to (17) and (21), F (p̃δ (r)) < F (p̃a (r)) with δ = d is equivalent to: n−1
ω (n) =
q→0+
nd(1−c)
pδ (1 − pδ ) p (1 − p) n > n . 1 − (1 − pδ ) 1 − (1 − p)
(35)
Combining (34) and (35), and letting q = 1 − (1 − p) ∈ (0, 1), we derive the condition for the network capability indicator c that satisfies both F (p̃δ (r)) < F (p̃a (r)) and B (p̃a (r)) = B (p̃δ (r)): 1 ln ω (n) /d 1 th c<c ≜1− 1+ − , (36) d ln (1 − q) n
according to (30), (b) substitutes the numerator based on ln (1 + x) ∼ x as x → 0, (c) simplifies the formula, (d) substitutes the infinitesimal term ln (1 − q) ∼ −q, (e) applies the L’Hopital’s rule, (f) simplifies the formula, and (g) calculates the nonzero limit in the denominator, i.e., lim (1 − q) = lim (1 + dq − q) = 1. q→0+
(1 − p) n n. d (1 − (1 − p) ) + (1 − p)
(34)
1 1−q
n1
n1
−1 .
(37)
−1
Next, we derive the lower bound for cth : ln(1+dq−q) 1 ln − (a) d d ln(1−q) 1 cth > 1 − 1 + d ln (1 − q) (b) d 1 1 1 1 > 1− 1+ − = − , d 2 2 2 2d
(38)
where (a) is because of Lemma 1, and (b) is because of Lemma 1 2. Therefore, given the network condition c ≤ 12 − 2d , when B (p̃a (r)) = B (p̃δ (r)), the inequality F (p̃δ (r)) < F (p̃a (r)) always holds. Theorem 1 indicates that, as long as the network capability 1 indicator satisfies c ≤ 12 − 2d , PoVD can achieve a lower fork rate than PoW with the same block time by using the δspaced block time distribution p̃δ (r). Note that Theorem 1 is a sufficient criterion for PoVD to achieve higher blockchain consistency than PoW without sacrificing throughput, since Theorem 1 is based on the δ-spaced block time distribution p̃δ (r), rather than the optimal distribution. This further highlights the great potential of PoVD. Note that some networks with long-tail latency do not 1 satisfy the condition of c ≤ 12 − 2d . These networks may
11
3 R 9 ' 3 % ) 7
& R P P X Q L F D W L R Q F R P S O H [ L W \
3 R : 9 ' ) % D V H O L Q H
1 X P E H U R I P L Q H U V
Figure 4. Communication complexity of different consensus protocols under varying numbers of miners. (Communication complexity is defined as the average number of messages exchanged to generate a new block.)
just need much fewer rounds than d to distribute the block among most miners, e.g., 95% or more; however, it may take a very lengthy time to ensure that all the miners receive the message. In this case, we can use a smaller δ < d, and PoVD still outperforms PoW in terms of fork rate. It is verified by our experiments in Section VII. The reason behind choosing δ < d is that propagation can be approximately considered complete after δ rounds. This allows the network capability 1 indicator with delay δ to satisfy the condition c ≤ 12 − 2δ . Moreover, from a practical perspective, since the majority of miners have already reached a consensus on the main chain after δ rounds of propagation, the few remaining miners who have not yet received the block are unlikely to fork. Moreover, the proof of Theorem 1 provides cth in (36) as the accurate threshold of network capability indicator beyond 1 the sufficient condition c ≤ 12 − 2d in the statement of Theorem 1. PoVD can outperform PoW, as long as c ≤ cth 1 holds, and meanwhile c ≤ 12 − 2d is just a stricter condition 1 on the network. (Fig. 3 shows that cth > 21 − 2d always holds.) As B (p̃a (r)) → ∞ and n → ∞, the threshold cth 1 gradually approaches the lower bound 12 − 2d . The figure also shows that when the block time is smaller, i.e., a high blockchain throughput is required, PoVD imposes weaker network requirements (and thus a wider range of c), which implies that PoVD offers greater design space for improving consistency under some high throughput requirements. VII. E XPERIMENTAL R ESULTS In this section, we conduct experiments based on the ChainXim blockchain simulator1 to demonstrate the communication- and computation-efficiency of PoVD and validate PoVD’s fork rate superiority. In the following figures, PoVD, PoW, and PBFT refer to the corresponding protocols in this work, [13] and [11]. VDF baseline refers to a class of VDF-based consensus protocols [27], [28], [36]. 1 ChainXim is a blockchain simulator developed by XinLab to simulate and verify blockchain systems under different parameter settings, and it is available on https://github.com/ChainXim-Team/ChainXim.
Figure 5. Computational complexity of different consensus protocols with different numbers of processors. (Computational complexity is defined as the average number of oracles performed by a miner to generate a block.)
PoW
PoVD
Figure 6. Fork rate of PoW and PoVD under different block time with n = 10, and d = δ = 10. (The curves are analytical results, and the markers are experimental ones.)
A. Communication and Computational Complexity First, we illustrate the communication and computational complexities of different consensus protocols in Fig. 4 and Fig. 5, respectively. In Fig. 4, communication complexity is defined as the average number of messages exchanged to generate a new block. We can observe that, for all consensus protocols, the communication complexity increases with the number of miners, but at different rates. The communication complexity of PBFT increases significantly as the number of miners grows. In contrast, PoVD, PoW, and the VDF baseline are communication efficient. As the network scales, the advantage of communication complexity becomes more pronounced, highlighting PoVD’s scalability for bandwidthlimited networks. Fig. 5 presents the computational complexity of PoVD, PoW, and the VDF baseline, which is defined as the average number of oracles performed by a miner to generate a block. Specifically, in PoW, oracles refer to the computation of hashes, while in VDF baseline and PoVD, they refer to the number of square computations. In Fig. 5, every miner is equipped with a different number of processors, representing
12
Figure 7. Fork rate of PoW and PoVD under different block time with n = 16, and c = 0.4. (The curves are analytical results, and the markers are experimental ones.)
Figure 8. Fork rate of PoW and PoVD under circle topology with 16 miners, and 32 miners. (The curves are analytical results, and the markers are experimental ones.)
varying power of parallelism. Fig. 5 demonstrates that PoVD consistently maintains a low computational cost regardless of the number of processors, whereas PoW and the VDF baseline exhibit a significant increase. This difference in computational complexity emphasizes PoVD’s advantage in computationalefficiency compared to PoW and other benchmarks, making it suitable for lightweight devices.
PoW
B. Fork Rate Superiority Now, we present the fork rates under different conditions. VDF baselines have similar performance to PoW and are thus omitted. In Fig. 6 and Fig. 7, the network capability indicator 1 . Both figures demonstrate that is set to satisfy c ≤ 12 − 2d the fork rate of PoVD is lower than that of PoW, which aligns with Theorem 1. Moreover, Fig. 6 shows that when the propagation delay d is fixed, the advantage of PoVD in fork rate becomes more significant as the propagation speed decreases (i.e., as c decreases). In contrast, Fig. 7 illustrates that when the network capability indicator c remains constant, increasing the propagation delay d does not significantly affect the consistency advantage but increases the fork rate. We also present the fork rates across two special propagation networks in Fig. 8, where the miners are connected in a loop. In this case, we have the theoretical propagation vector and thus derive the accurate fork rate and block time accordingly. In Fig. 8, analytical and simulation results are represented by lines and markers, respectively. The resulting propagation vectors are w8 = (1/16, 3/16, . . . , 15/16) for 16 miners, and w16 = (1/32, 3/32, . . . , 31/32) for 32 miners. As expected, Fig. 8 shows that PoVD can achieve a lower fork rate than PoW, as it can be easily verified that the network capability indicators corresponding to w8 and w16 also satisfy the 1 sufficient condition c ≤ 12 − 2d . Fig. 9 shows the performance of PoVD over a long-tail network with a large d. In the experiments, we set w18 ≈ 0.97 and w19 ≈ 0.99 for d = 20 and w46 ≈ 0.98 and w48 ≈ 0.99 for d = 50. Fig. 9 implies that, even when d > δ, PoVD still exhibits a lower fork rate than PoW. This supports the remarks given after Theorem 1. Hence, the network condition
Figure 9. Fork rate of PoW and PoVD under different block time with 256 miners.
for PoVD to achieve better performance than PoW is quite weak. To more intuitively demonstrate the fundamental differences in fork rates between PoVD and PoW, we evaluate the concurrent fork rate and the propagation fork rate under a 16-miner network in Fig. 10. In the legend, concurrent fork refers to the generation of multiple blocks in the same round, and propagation fork refers to the block conflicts during propagation. The fork rate of PoW consists of both the concurrent and propagation fork rate, and the propagation fork rate is the dominant component. In contrast, PoVD has no propagation fork, which makes the total fork rate lower than PoW. C. Experimental Energy Consumption Finally, we measure the CPU power consumption of PoVD, PoW, and VDF baseline through experiments. The experiments are based on a Windows desktop computer with a 16-core 4.3 GHz CPU and 128 GB of RAM. Fig. 11 presents the real-time energy consumption by using different numbers of processors. In the figure, the power curves from light to dark correspond to 1, 4, 8, and 16 processors, respectively. We
13
time of PoVD under an adjustable block time distribution. Through mathematical proof, we pointed out that, under some relatively weak network conditions, PoVD can achieve a lower fork rate than PoW for equivalent blockchain throughput. Finally, experiments against PBFT, PoW, and other VDF-based benchmarks illustrated the low computational and communication complexities of PoVD and highlighted its ability to adjust block time distribution for improving blockchain consistency.
3 R : F R Q F X U U H Q W I R U N 3 R : S U R S D J D W L R Q I R U N
3 R 9 ' F R Q F X U U H Q W I R U N
) R U N U D W H
R EFERENCES
)
)
)
)
)
0 L Q L Q J 7 D U J H W
Figure 10. Statistical results of different types of fork rate under varying difficulty target with 16 miners. (PoVD has no propagation fork.)
î 3 R 9 '
S U R F H V V R U V
3 R : 9 ' ) % D V H O L Q H
S U R F H V V R U V
3 R Z H U Z D W W
î
î
S U R F H V V R U
S U R F H V V R U V
î
7 L P H P L Q
Figure 11. Experimental energy consumption of different consensus protocols with various numbers of processors.
can observe that the energy consumption of PoW and VDF baseline with a single process is almost identical to that of PoVD. However, as the number of processors increases, the energy consumption of PoW and the VDF baseline grows significantly, while PoVD remains at low power consumption. This comparison highlights that PoVD is more energy-efficient than PoW and VDF baseline and is more suitable for resourceconstrained devices. VIII. C ONCLUSIONS In this study, we proposed PoVD, an efficient consensus protocol based on VDF. We designed the block generation and verification rules of PoVD and discussed potential security implications with corresponding countermeasures. Our design significantly reduces both communication and computation overhead and makes PoVD suitable for establishing consensus in resource-constrained and bandwidth-limited environments. Furthermore, PoVD can control the block time distribution according to, e.g., the network environment, and thus can more flexibly balance the trade-off between blockchain consistency and throughput. Due to the above reasons, we rethought the mining model of PoVD and derived the fork rate and block
[1] X. Ling, Y. Le, J. Wang, Y. Huang, and X. You, “Trust and trustworthiness in information and communications technologies,” IEEE Wireless Commun., vol. 32, no. 2, pp. 84–92, Apr. 2025. [2] M. Wu, X. Ling, J. Wang, Y. Le, K. Huang, B. Cao, Y. Huang, D. Niyato, Z. Ding, and X. You, “Blockchain-driven resource management in wireless communications and networks: Models, approaches, and applications,” IEEE Commun. Surveys Tuts., vol. 28, pp. 2306–2344, Feb. 2026. [3] W. Cao, X. Ling, J. Wang, X. Gao, and Z. Ding, “Optimization-based proof of useful work: Framework, modeling, and security analysis,” arXiv preprint arXiv:2405.19027, Mar. 2025. [4] Y. Zou and M. Xu, “A fast consensus for permissioned wireless blockchains,” IEEE Internet Things J., vol. 10, no. 14, pp. 12 102– 12 111, Oct. 2021. [5] J. Xu, C. Wang, and X. Jia, “A survey of blockchain consensus protocols,” ACM Comput. Surv., vol. 55, no. 13, pp. 1–35, Jul. 2023. [6] Z. Cui, X. Ling, X. Zhou, J. Wang, Z. Ding, and X. Gao, “Bagchain: A dual-functional blockchain leveraging bagging-based distributed learning,” arXiv preprint arXiv:2502.11464, Feb. 2025. [7] X. Ling, Y. Le, S. Chen, J. Wang, and X. Zhou, “Blockchain-enabled decentralized services and networks: Assessing roles and impacts,” IEEE J. Sel. Areas Commun., pp. 1–1, Apr. 2025. [8] S. Wan, M. Li, G. Liu, and C. Wang, “Recent advances in consensus protocols for blockchain: A survey,” Wireless Netw., vol. 26, no. 8, pp. 5579–5593, Nov. 2019. [9] B. Chen, X. Ling, W. Cao, J. Wang, and Z. Ding, “Analysis of channel uncertainty in trusted wireless services via repeated interactions,” IEEE J. Sel. Areas Commun., pp. 1–1, Apr. 2025. [10] Y. Zou, L. Yang, G. Jing, R. Zhang, Z. Xie, H. Li, and D. Yu, “A survey of fault tolerant consensus in wireless networks,” High-Confid. Comput., vol. 4, no. 2, pp. 100 202–100 202, Jun. 2024. [11] M. Castro and B. Liskov, “Practical Byzantine fault tolerance,” in Proc. 3rd Symp. Operating Syst. Des. Implementation (OSDI’99), New Orleans, LA, USA, Feb. 1999, pp. 173–186. [12] H. Luo, G. Sun, H. Yu, B. Lei, and M. Guizani, “An energy-efficient wireless blockchain sharding scheme for PBFT consensus,” IEEE Trans. Network Sci. Eng., vol. 11, no. 3, pp. 3015–3027, May. 2024. [13] S. Nakamoto, “Bitcoin: A peer-to-peer electronic cash system,” Oct. 2008, available: https://bitcoin.org/bitcoin.pdf. [14] Q. Wu, L. Xi, S. Wang, S. Ji, S. Wang, and Y. Ren, “Verifiable delay function and its blockchain-related application: A survey,” Sens., vol. 22, no. 19, pp. 7524–7524, Oct. 2022. [15] W. Li, C. Feng, L. Zhang, H. Xu, B. Cao, and M. A. Imran, “A scalable multi-layer PBFT consensus for blockchain,” IEEE Trans. Parallel Distrib. Syst., vol. 32, no. 5, pp. 1146–1160, May 2021. [16] M. M. Jalalzai, J. Niu, C. Feng, and F. Gai, “Fast-HotStuff: A fast and robust BFT protocol for blockchains,” IEEE Trans. Dependable Secure Comput., vol. 21, no. 4, pp. 2478–2493, Jul. 2024. [17] H. Cheng, Y. Lu, Z. Lu, Q. Tang, Y. Zhang, and Z. Zhang, “JUMBO: Fully asynchronous BFT consensus made truly scalable,” IEEE Trans. Dependable Secure Comput., vol. 22, no. 5, pp. 5584–5602, Sept. 2025. [18] X. Xu, L. Hou, Y. Li, and Y. Geng, “Weighted RAFT: An improved blockchain consensus mechanism for Internet of things application,” in Proc. 7th Int. Conf. Comput. Commun. (ICCC’21), Chengdu, CN, Dec. 2021, pp. 1520–1525. [19] H. Luo, Q. Zhang, G. Sun, H. Yu, and D. Niyato, “Symbiotic blockchain consensus: Cognitive backscatter communications-enabled wireless blockchain consensus,” IEEE/ACM Trans. Networking, pp. 1– 16, Sep. 2024. [20] M. M. Islam, M. M. Merlec, and H. P. IN, “Proof of random leader: A fast and manipulation-resistant proof-of-authority consensus algorithm for permissioned blockchains using verifiable random function,” IEEE Trans. Serv. Comput., vol. 18, no. 3, pp. 1655–1668, May 2025.
14
[21] Y. Zhao, Y. Qu, Y. Xiang, F. Chen, and L. Gao, “Context-aware consensus algorithm for blockchain-empowered federated learning,” IEEE Trans. Cloud Comput., vol. 12, no. 2, pp. 491–503, Apr. 2024. [22] M. Zhai, Q. Wu, Y. Liu, B. Qin, X. Dai, Q. Gao, and W. Susilo, “Secret multiple leaders & committee election with application to sharding blockchain,” IEEE Trans. Inf. Forensics Security, vol. 19, pp. 5060– 5074, Jan. 2024. [23] M. Zhai, Y. Liu, Q. Wu, B. Qin, H. Zheng, X. Dai, Z. Ding, and W. Susilo, “Accountable secret committee election and anonymous sharding blockchain consensus,” IEEE Trans. Inf. Forensics Security, vol. 19, pp. 9158–9172, Jan. 2024. [24] X. Fu, H. Wang, and P. Shi, “Votes-as-a-Proof (VaaP): Permissioned blockchain consensus protocol made simple,” IEEE Trans. Parallel Distrib. Syst., vol. 33, no. 12, pp. 4964–4973, Dec. 2022. [25] K. Zhou, X. Zhang, C. Wang, and H. Cheng, “Accelerating crossshard blockchain consensus via decentralized coordinators service with verifiable global states,” IEEE Trans. Serv. Comput., vol. 17, no. 4, pp. 1340–1353, Jul. 2024. [26] R. Hao, X. Dai, and W. Dai, “BitFT: An understandable, performant and resource-efficient blockchain consensus,” IEEE Trans. Sustain. Comput., vol. 9, no. 3, pp. 522–534, May 2024. [27] J. Long and R. Wei, “Nakamoto consensus with verifiable delay puzzle,” arXiv preprint arXiv:1908.06394, Aug. 2019. [28] R. Han, H. Lin, and J. Yu, “RandChain: A scalable and fair decentralised randomness beacon,” Cryptology ePrint Archive: 2020/1033, Aug. 2020. [29] S. Deb, S. Kannan, and D. Tse, “PoSAT: Proof-of-work availability and unpredictability, without the work,” in Proc. Financ. Cryptogr. Data Secur. (FC’21), ser. Lect. Notes Comput. Sci., vol. 12674, Berlin, DE, Oct. 2021, pp. 104–128. [30] M. Raikwar and D. Gligoroski, “R3V: Robust round robin VDF-based consensus,” in Proc. 3rd Conf. Blockchain Res. Appl. Innovative Netw. Serv. (BRAINS’21), Paris, FR, Sep. 2021, pp. 81–88. [31] M. Raikwar, “Competitive decentralized randomness beacon protocols,” in Proc. 4th ACM Int. Symp. Blockchain Secure Crit. Infrastruct. (BSCI’22), New York, NY, USA, May 2022, pp. 83–94. [32] R. Xu and Y. Chen, “Fairledger: A fair proof-of-sequential-work based lightweight distributed ledger for IoT networks,” in Proc. IEEE Int. Conf. on Blockchain (Blockchain’22), Espoo, FI, Aug. 2022, pp. 348–355. [33] F. Li, H. Xu, Q. Song, L. Zhang, X. Du, N. Tong, and D. Wang, “BLMA: Editable blockchain-based lightweight massive IIoT device authentication protocol,” IEEE Internet Things J., vol. 10, no. 24, pp. 21 633–21 646, Aug. 2023. [34] Y. Pu, A. Farahbakhsh, L. Alvisi, and I. Eyal, “Gorilla: Safe permissionless Byzantine consensus,” arXiv preprint arXiv:2308.04080, Aug. 2023. [35] W. Wang, L. Wang, J. Duan, X. Tong, and H. Peng, “Redactable blockchain based on decentralized trapdoor verifiable delay functions,” IEEE Trans. Inf. Forensics Security, vol. 19, pp. 7492–7507, Jan. 2024. [36] M. Mirkin, L. Zhou, I. Eyal, and F. Zhang, “Sprints: Intermittent blockchain PoW mining,” in Proc. 33rd USENIX Secur. Symp. (USENIX Security’24), Philadelphia, PA, USA, Aug. 2024, pp. 6273–6289. [37] P. Das, L. Eckey, S. Faust, J. Loss, and M. Maitra, “Round efficient Byzantine agreement from VDFs,” in Proc. Sec. Cryptogr. Netw. (SCN’24), vol. 14973, Cham, DE, Aug. 2024, pp. 139–160. [38] C. Xiong, T. Yang, Y. Wang, and B. Dong, “PoVF: Empowering decentralized blockchain systems with verifiable function consensus,” Comput. Networks, vol. 259, pp. 111 092–111 092, Mar. 2025. [39] D. Boneh, B. Bünz, and B. Fisch, “A survey of two verifiable delay functions using proof of exponentiation,” IACR Commun. Cryptol., vol. 1, no. 1, pp. 1–15, Apr. 2024. [40] P. Ni, H. Li, and D. Pan, “Analysis of Bitcoin backbone protocol in the non-flat model,” Sci. China Inf. Sci., vol. 63, no. 3, pp. 130 105–130 105, Feb. 2020. [41] J. Garay, A. Kiayias, and N. Leonardos, “The Bitcoin backbone protocol: Analysis and applications,” J. ACM, vol. 71, no. 4, pp. 1–49, Aug. 2024. [42] M. Iqbal and R. Matulevicius, “Exploring sybil and double-spending risks in blockchain systems,” IEEE Access, vol. 9, pp. 76 153–76 177, May 2021. [43] Y. Xiao, N. Zhang, W. Lou, and Y. T. Hou, “A survey of distributed consensus protocols for blockchain networks,” IEEE Commun. Surveys Tuts., vol. 22, no. 2, pp. 1432–1465, Jan. 2020. [44] Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich, “Algorand: Scaling Byzantine agreements for cryptocurrencies,” in Proc. 26th Symp. Operating Syst. Principles (SOSP’17), New York, NY, USA, Oct. 2017, pp. 51–68.
[45] E. Kokoris-Kogias, P. Jovanovic, L. Gasser, N. Gailly, E. Syta, and B. Ford, “Omniledger: A secure, scale-out, decentralized ledger via sharding,” in Proc. IEEE Symp. on Secur. and Privacy (SP’18), San Francisco, CA, USA, May 2018, pp. 583–598. [46] V. Buterin and V. Griffith, “Casper the friendly finality gadget,” arXiv preprint arXiv:1710.09437, Oct. 2017. [47] K. Choi, A. Manoj, and J. Bonneau, “Sok: Distributed randomness beacons,” in Proc. IEEE Symp. on Secur. and Privacy (SP’23), San Francisco, CA, USA, May 2023, pp. 75–92. [48] E. Syta, P. Jovanovic, E. K. Kogias, N. Gailly, L. Gasser, I. Khoffi, M. J. Fischer, and B. Ford, “Scalable bias-resistant distributed randomness,” in Proc. IEEE Symp. on Secur. and Privacy (SP’17), San Jose, CA, USA, May 2017, pp. 444–460. [49] A. Fujihara, “Theoretical analysis on block time distributions in Byzantine fault-tolerant consensus blockchains,” in Proc. IEEE Int. Conf. Blockchain (Blockchain’24), Copenhagen, DK, Aug. 2024, pp. 378–385. [50] C. Decker and R. Wattenhofer, “Information propagation in the Bitcoin network,” in Proc. 2013 IEEE P2P, Trento, IT, Sep. 2013, pp. 1–10.