HotDAG: Hybrid Consensus via Sharding in the Permissionless Model

A major design to improve scalability and performance of blockchain is sharding, which maintains a distributed ledger by running classical Byzantine Fault Tolerance (BFT) protocols through several relatively small committees. However, there are several drawbacks with the existing sharding protocols. First, the sharding mechanism which ensures that each committee is strongly bias-resistant either weakens the decentralization or reduces the performance of the protocol. Second, BFT protocols are either unresponsive or take quadratic communication complexities under a byzantine leader. Third, they cannot defend against transaction censorship attacks. Finally, nodes do not have enough motivation to follow the protocol and selfish nodes can obtain more rewards through collusive behaviors. A recent study proposes HotStuff – a BFT protocol that achieves linear view-change and optimistic responsiveness. In this paper, we present HotDAG, a hybrid consensus protocol based on HotStuff via sharding in the permissionless model. By employing the parallel Nakamoto consensus protocol, we present a decentralized and bias-resistant sharding mechanism. HotDAG has a linear communication complexity on transaction confirmation by introducing a scalable BFT protocol and an inter-committee consensus mechanism based on blockDAG. By achieving an unpredictable leader rotation, HotDAG prevents the censorship attacks. At the same time, HotDAG provides an incentive mechanism that is compatible with the scalable BFT protocol to encourage nodes to actively participate in the protocol. Finally, we formally prove the security and analyze the performance of HotDAG.