Paper 2021/805

Practical Settlement Bounds for Proof-of-Work Blockchains

Peter Gaži and Ling Ren and Alexander Russell

Abstract

Nakamoto proof-of-work ledger consensus currently underlies the majority of deployed cryptocurrencies and smart-contract blockchains, especially when measured in carried value. While a long and fruitful line of work studying the provable security guarantees of this mechanism has succeeded to identify its exact security region---that is, the set of parametrizations under which it possesses asymptotic security---the existing theory does not provide concrete settlement time guarantees that are tight enough to inform practice. In this work we provide a new approach for obtaining such settlement-time guarantees that provides strong, concrete bounds suitable for reasoning about deployed systems. This rigorous framework furthermore yields an efficient computational method for computing explicit bounds on settlement time as a function of honest and adversarial computational power and a bound on network delays. Our framework simultaneously provides upper and lower bounds, which permits an immediate means for evaluating the strength of the results. We implement this computational method and provide a comprehensive sample of concrete bounds for several settings of interest. For Bitcoin, for example, our explicit upper and lower bounds are within 70 seconds of each other after 1 hour of settlement delay with 10 second networking delays and a 10% adversary. In comparison, the best prior result has a gap of 2 hours in the upper and lower bounds with the same parameters.