You are looking at a specific version 20200317:183533 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
blockchain
Contact author(s)
kamp @ cs au dk,magri @ cs au dk,cm @ concordium com,jbn @ cs au dk,sethomsen @ cs au dk,dt @ concordium com
History
2021-07-22: last of 2 revisions
2020-03-17: received
See all versions
Short URL
https://ia.cr/2020/328
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.