# PnV: An Efficient Parallel Consensus Protocol Integrating Proof and Voting
## 2 Related Work
### Blockchain Consensus Integrating Voting and Proof  
Blockchain consensus protocols can be categorized into voting-based and proof-based protocols, and their fusion, as shown in Table 1. Strictly speaking, the first and third types represent advancements over Byzantine Fault Tolerant (BFT) protocols in traditional distributed theory, although the latter incorporates certain unique features of proof-based consensus specific to blockchain systems.  
PBFT [7], as the most renowned BFT protocol, distinguishes between primary and replica nodes, effectively reducing the algorithmic complexity from exponential to polynomial level. The only primary node confirms and receives client requests, while replicas confirm the primary node's and each other's information to ensure consistency. This advancement made BFT protocols practically applicable. BFT-SMART [8] shares similarities with PBFT but offers enhanced reliability, modularity, and flexible programming interfaces. Due to its separation of tokens and high-speed verification capabilities, PBFT and its variants have sparked extensive discussions within communities. The consensus delay achieved is at a second-level magnitude, meeting real-time requirements while ensuring high-throughput performance. However, it should be noted that the communication cost scales with \(\mathrm{O}(n^{2})\), implying that as the number of nodes (\(n\)) increases, there will be a rapid growth in data volume leading to increased network burden. To support large-scale networks, Algorand [27] employs a delegated mechanism wherein only a subset of nodes can participate in a Byzantine agreement protocol called BA\(\star\)[28; 29] for a transaction set during a consensus round. Specifically, it utilizes a verifiable random function to enable users to privately and demonstrably ascertain their successful election for the subsequent consensus round.  
In order to enhance blockchain scalability, researchers have proposed incorporating proof-based consensus into voting-based consensus. The first fusion consensus protocol,  
\begin{table}
\begin{tabular}{c c c} \hline
**Consensus Type** & **Description** & **Protocols** \\ \hline \multirow{6}{*}{Voting-based} & Rely on message interaction & \multirow{2}{*}{PBFT, BFT-SMART, Algorand, DAG-Rider, Tusk, and Bull-Shark consistency.} \\  & and require each consensus & \\  & round to produce a single & \\  & block without forks. & \\  & Demonstrate strong & \\  & consistency. & \\  & Possess inherent potential for & \\  & generating divergent blocks & \\  & but reconcile conflicts through & \\  & resolution techniques to & \\  & ensure eventual consistency. & \\  & Integrate voting-based and & \\  & proof-based characteristics to & \\ Fusion & leverage advantages of both & \\  & while addressing individual & \\  & limitations. & \\ \hline \end{tabular}
\end{table}
Table 1: Categorization of consensus protocols.  
known as PoV [12], adopts a delegated approach by assigning voting rights and bookkeeping rights to voters and bookkeepers, respectively. Blocks are produced by bookkeepers and determined based on the proofs derived from voting results among voters. PoV exhibits linear communication complexity with \(O(3n)\). HotStuff [14] extends PBFT's two phases to three phases while utilizing threshold signatures to reduce proof data and enable pipelined consensus process for improved throughput. Additionally, Sync HotStuff [30] presents a simplified and intuitive synchronous version featuring a two-phase vote. However, in scenarios involving multiple bookkeepers, these fusion protocols still face challenges where non-leader bookkeepers remain idle, thereby impacting the complete resolution of scalability issues.