OverChain: Building a robust overlay with a blockchain

Blockchains use peer-to-peer networks for disseminating information among peers, but these networks currently do not have any provable guarantees for desirable properties such as Byzantine fault tolerance, good connectivity and small diameter. This is not just a theoretical problem, as recent works...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-01
Main Authors: Aradhya, Vijeth, Gilbert, Seth, Hobor, Aquinas
Format: Article
Language:English
Subjects:
Algorithms
Blockchain
Cryptography
Digital currencies
Fault tolerance
Information dissemination
Lower bounds
Peer to peer computing
Safety critical
Social networks
Synchronism
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Blockchains use peer-to-peer networks for disseminating information among peers, but these networks currently do not have any provable guarantees for desirable properties such as Byzantine fault tolerance, good connectivity and small diameter. This is not just a theoretical problem, as recent works have exploited unsafe peer connection policies and weak network synchronization to mount partitioning attacks on Bitcoin. Cryptocurrency blockchains are safety critical systems, so we need principled algorithms to maintain their networks. Our key insight is that we can leverage the blockchain itself to share information among the peers, and thus simplify the network maintenance process. Given that the peers have restricted computational resources, and at most a constant fraction of them are Byzantine, we provide communication-efficient protocols to maintain a hypercubic network for blockchains, where peers can join and leave over time. Interestingly, we discover that our design can \emph{recover} from substantial adversarial failures. Moreover, these properties hold despite significant churn. A key contribution is a secure mechanism for joining the network that uses the blockchain to help new peers to contact existing peers. Furthermore, by examining how peers join the network, i.e., the "bootstrapping service," we give a lower bound showing that (within log factors) our network tolerates the maximum churn rate possible. In fact, we can give a lower bound on churn for any fully distributed service that requires connectivity.
ISSN:2331-8422