Event
Ph.D. Proposal Examination: Mustafa Doger
Tuesday, February 4, 2025
2:30 p.m.
AVW 2328
Maria Hoo
301 405 3681
mch@umd.edu
ANNOUNCEMENT: Ph.D. Proposal Examination
Name: Mustafa Doger
Name: Mustafa Doger
Committee:
Prof. Sennur Ulukus, Chair/Advisor
Prof. Adrian Papamarcou
Prof. Ang Li
Date/Time: Tuesday, February 4, 2025 at 2:30 pm
Location: AVW 2328
Title: Security Problems of Proof-of-Work Blockchains
Date/Time: Tuesday, February 4, 2025 at 2:30 pm
Location: AVW 2328
Title: Security Problems of Proof-of-Work Blockchains
Abstract:
We consider the problems of theoretical guarantees for double spending probabilities for the Nakamoto consensus under the $k$-deep confirmation rule for different mining rates and network delay models. Nakamoto consensus has been proposed to solve the double spending problem, or more generally Byzantine Generals Problem, in distributed permissionless settings. In essence, Nakamoto's solution combines the longest chain protocol with a Proof of Work mechanism to ensure that a malicious agent is unlikely to undermine the consensus as long as the fraction of computational power it possesses is less than a half. Since the hash functions associated with Proof of Work mechanism behave similar to the random oracles, the double spending problems can be modeled as complicated random walks depending on adversarial strategies, peer to peer network delays and mining rates. In this proposal, we focus on double spending problems and study bounds as well as trade-offs associated with it under different network delay models and mining strategies. We provide novel tight bounds that extend the state-of-the-art results and explore trade-offs and connections to other fundamental blockchain mechanisms.
In our first completed work, we investigate the problem of security-latency bounds for Nakamoto consensus under bounded network delay, i.e., how secure a block is after it becomes $k$-deep in the chain given each block is subject to a peer-to-peer delay between $[0,\Delta]$. We improve the state-of-the-art bounds by analyzing the race between adversarial and honest chains in three different phases. We find the probability distribution of the growth of the adversarial chains under models similar to those in [Guo, Ren; AFT 2022] when a target block becomes $k$-deep in the chain. We analyze certain properties of this race to model each phase with random walks that provide tighter bounds than the existing results. Combining all three phases provides novel upper and lower bounds for blockchains with small $\lambda\Delta$.
In our second completed work, we analyze how secure a block is after the block becomes $k$-deep, for Nakamoto consensus under an exponential network delay model. We give parameter regimes for which transactions are safe when sufficiently deep in the chain. We compare our results for Nakamoto consensus under bounded network delay models and obtain analogous bounds for safety violation threshold. Next, modeling the blockchain system as a batch service queue with exponential network delay, we connect the security-latency analysis to the sustainable transaction rate of the queue system. As our model assumes exponential network delay, batch service queue models give a meaningful trade-off between transaction capacity, security and latency. As adversaries can attack the queue service to hamper the service process, we consider two different attacks for adversary. In an extreme scenario, we modify the selfish-mining attack for this purpose and consider its effect on the sustainable transaction rate of the queue.
In our third completed work, we analyze the security-latency problem under general random delay distributions. We provide tight and explicit bounds which only require determining the distribution of the number of Poisson arrivals during the random delay. As miners of Bitcoin increasingly depend on transaction fees rather than coinbase transactions, a mechanism intended to suppress inflation, mining gap situations are likely to happen in future. Thus, we further consider potential effects of recent Bitcoin halving on the security-latency problem by extending our results.
Next, we propose three works for future research. In our first proposed work, we consider a ruin-theoretical model of double spending for Nakamoto consensus under the $k$-deep confirmation rule when the honest mining rate is allowed to be an arbitrary function of time including the block delivery periods, i.e., time periods during which mined blocks are being delivered to all other participants of the network. Time-varying mining rates are considered to capture the intrinsic characteristics of the peer to peer network delays as well as dynamic participation of miners such as the gap game and switching between different cryptocurrencies. We aim to leverage ruin theory to obtain the double spend probabilities and provide numerical examples to validate the effectiveness of the proposed analytical method.
In our second proposed work, we consider a framework that combines the problem of double-spending and selfish mining attack. Although both problems have been extensively studied since the ``Bitcoin'' whitepaper of Nakamoto and the ``majority is not enough'' paper of Eyal and Sirer, there has been no rigorous stochastic analysis of an attack that combines the two, except for the complicated MDP models. We first aim to provide a combination of stubborn and selfish mining attacks and argue a connection between the level of stubbornness and the $k$-confirmation rule. This in turn is expected to create a risk of double spending which may come at no-cost to the adversary, which we aim to analyze rigorously. The result can be seen as a guide for picking the $k$-confirmation rule in blockchain design. As a case study, i.e., Bitcoins $6$ block confirmation rule, we aim to provide the revenue and the double spending risk of the attacks for each pool parameter.
In our third proposed work, we consider the parallel PoW protocol which is proposed to fix the vulnerabilities of Nakamoto consensus stemming from the high variance of the block mining times and high variance of the reward distribution among the miners. However, most of the proposed parallel PoW protocols are vulnerable to adversarial withholding attacks even more than the original Nakamoto consensus. In this work, we propose to use a leader election mechanism inspired from Bitcoin-NG which decreases the overall communication overhead associated with the previous works in the literature. We handcraft adversarial withholding attacks to show the vulnerabilities of the previous works on parallel PoW and propose to fix these issues in our protocol by taking inspiration from the $k$-cluster rule of PHANTOM. By analyzing the transaction inclusion and longest chain extension attacks similar to the analysis of Bitcoin-NG, we aim to determine how transaction fees should be shared between the leader and the subsequent voters.
In our first completed work, we investigate the problem of security-latency bounds for Nakamoto consensus under bounded network delay, i.e., how secure a block is after it becomes $k$-deep in the chain given each block is subject to a peer-to-peer delay between $[0,\Delta]$. We improve the state-of-the-art bounds by analyzing the race between adversarial and honest chains in three different phases. We find the probability distribution of the growth of the adversarial chains under models similar to those in [Guo, Ren; AFT 2022] when a target block becomes $k$-deep in the chain. We analyze certain properties of this race to model each phase with random walks that provide tighter bounds than the existing results. Combining all three phases provides novel upper and lower bounds for blockchains with small $\lambda\Delta$.
In our second completed work, we analyze how secure a block is after the block becomes $k$-deep, for Nakamoto consensus under an exponential network delay model. We give parameter regimes for which transactions are safe when sufficiently deep in the chain. We compare our results for Nakamoto consensus under bounded network delay models and obtain analogous bounds for safety violation threshold. Next, modeling the blockchain system as a batch service queue with exponential network delay, we connect the security-latency analysis to the sustainable transaction rate of the queue system. As our model assumes exponential network delay, batch service queue models give a meaningful trade-off between transaction capacity, security and latency. As adversaries can attack the queue service to hamper the service process, we consider two different attacks for adversary. In an extreme scenario, we modify the selfish-mining attack for this purpose and consider its effect on the sustainable transaction rate of the queue.
In our third completed work, we analyze the security-latency problem under general random delay distributions. We provide tight and explicit bounds which only require determining the distribution of the number of Poisson arrivals during the random delay. As miners of Bitcoin increasingly depend on transaction fees rather than coinbase transactions, a mechanism intended to suppress inflation, mining gap situations are likely to happen in future. Thus, we further consider potential effects of recent Bitcoin halving on the security-latency problem by extending our results.
Next, we propose three works for future research. In our first proposed work, we consider a ruin-theoretical model of double spending for Nakamoto consensus under the $k$-deep confirmation rule when the honest mining rate is allowed to be an arbitrary function of time including the block delivery periods, i.e., time periods during which mined blocks are being delivered to all other participants of the network. Time-varying mining rates are considered to capture the intrinsic characteristics of the peer to peer network delays as well as dynamic participation of miners such as the gap game and switching between different cryptocurrencies. We aim to leverage ruin theory to obtain the double spend probabilities and provide numerical examples to validate the effectiveness of the proposed analytical method.
In our second proposed work, we consider a framework that combines the problem of double-spending and selfish mining attack. Although both problems have been extensively studied since the ``Bitcoin'' whitepaper of Nakamoto and the ``majority is not enough'' paper of Eyal and Sirer, there has been no rigorous stochastic analysis of an attack that combines the two, except for the complicated MDP models. We first aim to provide a combination of stubborn and selfish mining attacks and argue a connection between the level of stubbornness and the $k$-confirmation rule. This in turn is expected to create a risk of double spending which may come at no-cost to the adversary, which we aim to analyze rigorously. The result can be seen as a guide for picking the $k$-confirmation rule in blockchain design. As a case study, i.e., Bitcoins $6$ block confirmation rule, we aim to provide the revenue and the double spending risk of the attacks for each pool parameter.
In our third proposed work, we consider the parallel PoW protocol which is proposed to fix the vulnerabilities of Nakamoto consensus stemming from the high variance of the block mining times and high variance of the reward distribution among the miners. However, most of the proposed parallel PoW protocols are vulnerable to adversarial withholding attacks even more than the original Nakamoto consensus. In this work, we propose to use a leader election mechanism inspired from Bitcoin-NG which decreases the overall communication overhead associated with the previous works in the literature. We handcraft adversarial withholding attacks to show the vulnerabilities of the previous works on parallel PoW and propose to fix these issues in our protocol by taking inspiration from the $k$-cluster rule of PHANTOM. By analyzing the transaction inclusion and longest chain extension attacks similar to the analysis of Bitcoin-NG, we aim to determine how transaction fees should be shared between the leader and the subsequent voters.
