DSpace Repository

Randomized View Reconciliation in Permissionless Distributed Systems

Show simple item record

dc.contributor.author HOU, Ruomu
dc.contributor.author JAHJA, Irvan
dc.contributor.author LUU, Loi
dc.contributor.author SAXENA, Prateek
dc.contributor.author YU, Haifeng
dc.date.accessioned 2017-12-28T10:02:53Z
dc.date.available 2017-12-28T10:02:53Z
dc.identifier.uri https://dl.comp.nus.edu.sg/handle/1900.100/6863
dc.description Technical Report en_US
dc.description.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 O (N) time complexity, with N being the number of honest nodes in the system. All existing view reconciliation protocols so far have a similar O(N) time complexity. As this paper’s main contribution, we propose a novel view reconciliation protocol with a time complexity of only O( ln N/ ln ln N ). To achieve such an exponential improvement, we aggressively exploit randomization. en_US
dc.relation.ispartofseries TR12/17 en_US
dc.title Randomized View Reconciliation in Permissionless Distributed Systems en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search DSpace


My Account