Please use this identifier to cite or link to this item:
Title: Randomized View Reconciliation in Permissionless Distributed Systems
Authors: I. Jahja 
H. Yu 
R. Hou 
Loi Luu 
Prateek Saxena 
Issue Date: 2018
Publisher: Institute of Electrical and Electronics Engineers Inc.
Citation: I. Jahja, H. Yu, R. Hou, Loi Luu, Prateek Saxena (2018). Randomized View Reconciliation in Permissionless Distributed Systems. Proceedings - IEEE INFOCOM 2018-April : 2528 - 2536. ScholarBank@NUS Repository.
Abstract: In a sybil attack, an adversary creates a large number of fake identities/nodes and have them join the system. Computational puzzles have long been investigated as a possible sybil defense: If a node fails to solve the puzzle in a timely fashion, it will no longer be accepted by other nodes. However, it is still possible for a malicious node to behave in such a way that it is accepted by some honest nodes but not other honest nodes. This results in different honest nodes having different views on which set of nodes should form the system. Such view divergence, unfortunately, breaks the overarching assumption required by many existing security protocols. Partly spurred by the growing popularity of Bitcoin, researchers have recently formalized the above view divergence problem and proposed interesting solutions (which we call view reconciliation protocols). For example, in CRYPTO 2015, Andrychowicz and Dziembowski proposed a view reconciliation protocol with Theta(N) time complexity, with N being the number of honest nodes in the system. All existing view reconciliation protocols so far have a similar Theta(N) time complexity. As this paper's main contribution, we propose a novel view reconciliation protocol with a time complexity of only Theta(frac{ln N}{lnln N}). To achieve such an exponential improvement, we aggressively exploit randomization.
Source Title: Proceedings - IEEE INFOCOM
ISBN: 9781538641286
ISSN: 0743166X
DOI: 10.1109/INFOCOM.2018.8486394
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
File Description SizeFormatAccess SettingsVersion 
6. infocom18-tr.pdf366.85 kBAdobe PDF




checked on Feb 1, 2023

Page view(s)

checked on Feb 2, 2023


checked on Feb 2, 2023

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.