Cryptology ePrint Archive: Report 2020/328

Leveraging Weight Functions for Optimistic Responsiveness in Blockchains

Simon Holmgaard Kamp and Bernardo Magri and Christian Matt and Jesper Buus Nielsen and Søren Eller Thomsen and Daniel Tschudi

Abstract: Existing Nakamoto-style blockchains (NSBs) rely on some sort of synchrony assumption to offer any type of safety guarantees. A basic requirement is that when a party produces a new block, then all previously produced blocks should be known to that party, as otherwise the new block might not append the current head of the chain, creating a fork. In practice, however, the network delay for parties to receive messages is not a known constant, but rather varies over time. The consequence is that the parameters of the blockchain need to be set such that the time between the generation of two blocks is typically larger than the network delay (e.g., $10$ minutes in Bitcoin) to guarantee security even under bad network conditions. This results in lost efficiency for two reasons: (1) Since blocks are produced less often, there is low throughput. Furthermore, (2) blocks can only be considered final, and thus the transactions inside confirmed, once they are extended by sufficiently many other blocks, which incurs a waiting time that is a multiple of 10 minutes. This is true even if the actual network delay is only $1$ second, meaning that NSBs are slow even under good network conditions. We show how the Bitcoin protocol can be adjusted such that we preserve Bitcoin's security guarantees in the worst case, and in addition, our protocol can produce blocks arbitrarily fast and achieve optimistic responsiveness. The latter means that in periods without corruption, the confirmation time only depends on the (unknown) actual network delay instead of the known upper bound. Technically, we propose an approach where blocks are treated differently in the ``longest chain rule''. The crucial parameter of our protocol is a weight function assigning different weight to blocks according to their hash value. We present a framework for analyzing different weight functions, in which we prove all statements at the appropriate level of abstraction. This allows us to quickly derive protocol guarantees for different weight functions. We exemplify the usefulness of our framework by capturing the classical Bitcoin protocol as well as exponentially growing functions as special cases, where the latter provide the above mentioned guarantees, including optimistic responsiveness.

Category / Keywords: cryptographic protocols / blockchain

Date: received 17 Mar 2020

Contact author: kamp at cs au dk,magri@cs au dk,cm@concordium com,jbn@cs au dk,sethomsen@cs au dk,dt@concordium com

Available format(s): PDF | BibTeX Citation

Version: 20200317:183533 (All versions of this report)

Short URL: ia.cr/2020/328


[ Cryptology ePrint archive ]