Verifier's Dilemma in Proof-of-Work Public Blockchains: A~Quantitative Analysis

A blockchain is an immutable ledger driven by a distributed consensus protocol. In public blockchains, such as Bitcoin and Ethereum Classic, consensus is established through a computational effort called Proof-of-Work (PoW). Special users called miners contribute to the PoW in exchange for a fee and also verify the data stored in blocks mined by the other miners. Here is where the Verifier's Dilemma emerges. Verification of blocks does not receive a reward, and to maximise their profits, miners may be incentivized to forego verifying blocks and to only invest their resources in PoW. In this paper, we study the Verifier's Dilemma and a possible countermeasure consisting in the injection of invalid blocks using a quantitative model based on a Markovian process algebra. To avoid the state space explosion problem, we study the underlying Markov chain by using a lumping that allows us to derive closed-form solutions for interesting performance indices. The analysis demonstrates the circumstances under which non-verifying miners gain fees higher than those of verifying miners. The model also allows us to derive the optimal rate at which invalid blocks must be injected, so that skipping the verifying phase becomes economically disadvantageous while the throughput of the blockchain is only minimally reduced. The impact on miners' rewards and overall performance is also assessed.