Security-Performance Tradeoff in DAG-based Proof-of-Work Blockchain Protocols
Shichen Wu, Puwen Wei, Ren Zhang, Bowen Jiang · 2024
Proof-of-work (PoW) blockchain protocols based on directed acyclic graphs (DAGs) have demonstrated superior transaction confirmation performance compared to their chainbased predecessors.However, it is uncertain whether their security deteriorates in high-throughput settings similar to their predecessors, because their acceptance of simultaneous blocks and complex block dependencies presents challenges for rigorous security analysis.We address these challenges by analyzing DAG-based protocols via a congestible blockchain model (CBM), a general model that allows case-by-case upper bounds on the block propagation delay, rather than a uniform upper bound as in most previous analyses.CBM allows us to capture two key phenomena of highthroughput settings: (1) simultaneous blocks increase each other's propagation delay, and (2) a block can be processed only after receiving all the blocks it refers to.We further devise a reasonable adversarial block propagation strategy in CBM, called the latepredecessor attack, which exploits block dependencies to delay the processing of honest blocks.We then evaluate the security and performance of Prism and OHIE, two DAG-based protocols that aim to break the security-performance tradeoff, in the presence of an attacker capable of launching the late predecessor attack.Our results show that these protocols suffer from reduced security and extended latency in high-throughput settings similar to their chain-based predecessors. * Corresponding authors.Although NC is widely recognized as a technical breakthrough, its poor performance-low throughput and high transaction confirmation latency-prevents it from processing transactions on a global level.These limitations are rooted in NC's security demands, which require that most blocks be mined after the majority of miners have received the blocks' predecessors [12], [29], [38].This requirement can only be guaranteed by upper-bounding the block size and lower-bounding the block interval.These bounds prevent NC from reaching the networks' physical limits of throughput and latency [4], which are the throughput reaching the network's capacity and the latency proportional to the transaction propagation delay.A popular approach to breaking the security-performance tradeoff and reaching the physical limits is the DAG-based protocols.These protocols allow a block to refer to multiple predecessor blocks, thus replacing the single-chain-based ledger structure with a directed acyclic graph (DAG).As simultaneous blocks can all contribute to transaction confirmation, these protocols [4], [5], [20], [21], [36], [37], [44] loosen the limit on the block interval and thus outperform NC in their throughput.However, it is uncertain whether most of them can maintain the same-if not stronger-level of security as NC, because they only offer weak security guarantees or even flawed security analyses (Sect.II).This situation renders it difficult to evaluate how security and performance interact with each other.The only two exceptions are Prism [4] and OHIE [44], who, in addition to their outstanding performance, prove their security following NC's properties.Concretely, both designs prove that they can tolerate an adversarial mining power share of close to 50%-same as NC, and this threshold-unlike NC's-is (almost) independent of the throughput.These encouraging results make us wonder: are Prism and OHIE completely exempt from the security-performance tradeoff, even when executing at the physical limits?In this paper, we show that this is not the case.We observe that both designs implicitly rely on the following key assumption in their proofs to decouple security and performance:Assumption of Decoupling.If some types of blocks are small enough and enjoy a priority propagation policy, i.e., they are propagated before all other blocks in network congestion, then (1) they can be propagated within a fixed and short network propagation delay D, and (2) all miners can accept these blocks, i.e., include them in their working puzzle, immediately after receiving them.These special blocks, which we call priority blocks, are