Practical Settlement Bounds for Proof-of-Work Blockchains

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---the set of parametrizations under which it possesses asymptotic security---the existing understanding falls short of providing practical settlement-time guarantees backed by this theory. This gap is most noticable for blockchains that are parametrized to maximize throughput by selecting block-creation time commesurate with network delays.

In this work we provide a new approach for obtaining such settlement-time guarantees. Our results give a rigorous framework for analyzing consistency that 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 on settlement times, which permits an immediate evaluation of the strength of the bounds. We implement this computational method and provide example results for several settings of interest. For Bitcoin, for example, the explicit upper and lower bounds are within 100 seconds of each other with 1 hour of settlement delay, 10 second networking delays, and a 20% adversary.