More Web Proxy on the site http://driver.im/

research-article

Open access

Barracuda: The Power of ℓ-polling in Proof-of-Stake Blockchains

Authors:

Pramod ViswanathAuthors Info & Claims

Mobihoc '19: Proceedings of the Twentieth ACM International Symposium on Mobile Ad Hoc Networking and Computing

Pages 351 - 360

https://doi.org/10.1145/3323679.3326533

Published: 02 July 2019 Publication History

Abstract

A blockchain is a database of sequential events that is maintained by a distributed group of nodes. A key consensus problem in blockchains is that of determining the next block (data element) in the sequence. Many blockchains address this by electing a new node to propose each new block. The new block is (typically) appended to the tip of the proposer's local blockchain, and subsequently broadcast to the rest of the network. Without network delay (or adversarial behavior), this procedure would give a perfect chain, since each proposer would have the same view of the blockchain. A major challenge in practice is forking. Due to network delays, a proposer may not yet have the most recent block, and may therefore create a side chain that branches from the middle of the main chain. Forking reduces throughput, since only one a single main chain can survive, and all other blocks are discarded. We propose a new P2P protocol for blockchains called Barracuda, in which each proposer, prior to proposing a block, polls ℓ other nodes for their local blocktree information. Under a stochastic network model, we prove that this lightweight primitive improves throughput as if the entire network were a factor of ℓ faster. We provide guidelines on how to implement Barracuda in practice, guaranteeing robustness against several real-world factors.

References

[1]

Mohammed Amin Abdullah and Moez Draief. 2015. Global majority consensus by local majority polling on graphs of a given degree sequence. Discrete Applied Mathematics 180 (2015), 1--10.

Digital Library

[2]

Vivek Bagaria, Sreeram Kannan, David Tse, Giulia Fanti, and Pramod Viswanath. {n. d.}. Deconstructing the Blockchain to Approach Physical Limits. https://arxiv.org/abs/1810.08092.

[3]

S Basu, Ittay Eyal, and EG Sirer. {n. d.}. The Falcon Network.

[4]

Alex Biryukov, Dmitry Khovratovich, and Ivan Pustogarov. 2014. Deanonymisation of clients in Bitcoin P2P network. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. ACM, 15--29.

Digital Library

[5]

Vitalik Buterin and Virgil Griffith. 2017. Casper the friendly finality gadget. arXiv preprint arXiv:1710.09437 (2017).

[6]

Cardano. {n. d.}. Cardano Settlement Layer Documentation. https://cardanodocs.com/technical/.

[7]

James Cruise and Ayalvadi Ganesh. 2014. Probabilistic consensus via polling and majority rules. Queueing Systems 78, 2 (2014), 99--120.

Digital Library

[8]

Christian Decker and Roger Wattenhofer. 2013. Information propagation in the bitcoin network. In Peer-to-Peer Computing (P2P), 2013 IEEE Thirteenth International Conference on. IEEE, 1--10.

[9]

Ittay Eyal, Adem Efe Gencer, Emin Gün Sirer, and Robbert Van Renesse. 2016. Bitcoin-NG: A Scalable Blockchain Protocol. In NSDI. 45--59.

Digital Library

[10]

Ittay Eyal and Emin Gün Sirer. 2018. Majority is not enough: Bitcoin mining is vulnerable. Commun. ACM 61, 7 (2018), 95--102.

Digital Library

[11]

Giulia Fanti, Jiantao Jiao, Ashok Makkuva, Sewoong Oh, Ranvir Rana, and Pramod Viswanath. 2018. Barracuda: the Power of &ell;-polling in Proof-of-Stake Blockchains. (2018). available at http://swoh.web.engr.illinois.edu/polling.pdf and arXiv.

[12]

MJ Fischer, N Lynch, and MS Paterson. 1985. Impossibility of Distributed Consensus with One Faulty Process.

[13]

Juan Garay, Aggelos Kiayias, and Nikos Leonardos. 2015. The bitcoin backbone protocol: Analysis and applications. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 281--310.

[14]

Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. 2017. Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles. ACM, 51--68.

Digital Library

[15]

Johannes Göbel, Holger Paul Keeler, Anthony E Krzesinski, and Peter G Taylor. 2016. Bitcoin blockchain dynamics: The selfish-mine strategy in the presence of propagation delay. Performance Evaluation 104 (2016), 23--41.

[16]

Ethan Heilman, Alison Kendler, Aviv Zohar, and Sharon Goldberg. 2015. Eclipse Attacks on Bitcoin's Peer-to-Peer Network. In USENIX Security Symposium. 129--144.

Digital Library

[17]

Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. 2017. Ouroboros: A provably secure proof-of-stake blockchain protocol. In Annual International Cryptology Conference. Springer, 357--388.

[18]

Eleftherios Kokoris Kogias, Philipp Jovanovic, Nicolas Gailly, Ismail Khoffi, Linus Gasser, and Bryan Ford. 2016. Enhancing bitcoin security and performance with strong consistency via collective signing. In 25th USENIX Security Symposium (USENIX Security 16). 279--296.

Digital Library

[19]

Timothy Lee. 2017. Bitcoin?s insane energy consumption, explained. (2017).

[20]

Yoad Lewenberg, Yonatan Sompolinsky, and Aviv Zohar. 2015. Inclusive block chain protocols. In International Conference on Financial Cryptography and Data Security. Springer, 528--547.

[21]

Chenxing Li, Peilun Li, Wei Xu, Fan Long, and Andrew Chi-chih Yao. 2018. Scaling Nakamoto Consensus to Thousands of Transactions per Second. arXiv preprint arXiv:1805.03870 (2018).

[22]

David Mazieres. 2015. The stellar consensus protocol: A federated model for internet-level consensus. Stellar Development Foundation (2015).

[23]

Andrew Miller, James Litton, Andrew Pachulski, Neal Gupta, Dave Levin, Neil Spring, and Bobby Bhattacharjee. 2015. Discovering bitcoin?s public topology and influential nodes. et al. (2015).

[24]

Michael Mitzenmacher and Eli Upfal. 2005. Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge university press.

Digital Library

[25]

Nikolaos Papadis, Sem Borst, Anwar Walid, Mohamed Grissa, and Leandros Tassiulas. 2018. Stochastic Models and Wide-Area Network Measurements for Blockchain Design and Analysis. In IEEE INFOCOM 2018-IEEE Conference on Computer Communications. IEEE, 2546--2554.

[26]

Rafael Pass and Elaine Shi. 2017. Hybrid consensus: Efficient consensus in the permissionless model. In LIPIcs-Leibniz International Proceedings in Informatics, Vol. 91. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[27]

Rafael Pass and Elaine Shi. 2018. Thunderella: Blockchains with optimistic instant confirmation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 3--33.

[28]

Team Rocket. 2018. Snowflake to avalanche: A novel metastable consensus protocol family for cryptocurrencies,?

[29]

Yonatan Sompolinsky, Yoad Lewenberg, and Aviv Zohar. 2016. SPECTRE: A Fast and Scalable Cryptocurrency Protocol. IACR ePrint Archive 2016 (2016), 1159.

[30]

Yonatan Sompolinsky and Aviv Zohar. {n. d.}. PHANTOM. ({n. d.}).

[31]

Yonatan Sompolinsky and Aviv Zohar. 2015. Secure high-rate transaction processing in bitcoin. In International Conference on Financial Cryptography and Data Security. Springer, 507--527.

Cited By

Niu JWang CFeng CXu H(2022)When Power-of-d-Choices Meets Priority2022 IEEE/ACM 30th International Symposium on Quality of Service (IWQoS)10.1109/IWQoS54832.2022.9812880(1-10)Online publication date: 10-Jun-2022
https://doi.org/10.1109/IWQoS54832.2022.9812880
Asheralieva ANiyato D(2021)Learning-Based Mobile Edge Computing Resource Management to Support Public Blockchain NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2019.295977220:3(1092-1109)Online publication date: 1-Mar-2021
https://doi.org/10.1109/TMC.2019.2959772
Li Y(2021)Layout Optimization of Landscape Architecture based on Intelligent Visual Scene Recognition and Saliency Analysis2021 Third International Conference on Intelligent Communication Technologies and Virtual Mobile Networks (ICICV)10.1109/ICICV50876.2021.9388435(859-862)Online publication date: 4-Feb-2021
https://doi.org/10.1109/ICICV50876.2021.9388435
Show More Cited By

Index Terms

Barracuda: The Power of ℓ-polling in Proof-of-Stake Blockchains

Recommendations

Probabilistic flooding in stochastic networks: Analysis of global information outreach

This article investigates probabilistic information dissemination in stochastic networks. The following problem is studied: A source node intends to deliver a message to all other network nodes using probabilistic flooding, i.e., each node forwards a ...
The Gap Game
CCS '18: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security

Blockchain-based cryptocurrencies secure a decentralized consensus protocol by incentives. The protocol participants, called miners, generate (mine) a series of blocks, each containing monetary transactions created by system users. As incentive for ...
Permissionless and permissioned blockchain diffusion
Highlights
- A study of permissionless and permissioned blockchain diffusion.
- Permissioned blockchain diffusion is lagging well behind the diffusion of permissionless blockchains.
- Barriers and drivers of diffusion are different for each type of ...
Abstract
This paper explores the barriers and drivers of diffusion associated with permissionless and permissioned blockchains, seeking to establish whether they are the same or different and whether barriers and drivers change over time. The study was ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

Mobihoc '19: Proceedings of the Twentieth ACM International Symposium on Mobile Ad Hoc Networking and Computing

July 2019

419 pages

ISBN:9781450367646

DOI:10.1145/3323679

Copyright © 2019 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGMOBILE: ACM Special Interest Group on Mobility of Systems, Users, Data and Computing

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 July 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Best Paper

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Funding Sources

Conference

Mobihoc '19

Sponsor:

SIGMOBILE

Mobihoc '19: The Twentieth ACM International Symposium on Mobile Ad Hoc Networking and Computing

July 2 - 5, 2019

Catania, Italy

Acceptance Rates

Overall Acceptance Rate 296 of 1,843 submissions, 16%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
644
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)6

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Niu JWang CFeng CXu H(2022)When Power-of-d-Choices Meets Priority2022 IEEE/ACM 30th International Symposium on Quality of Service (IWQoS)10.1109/IWQoS54832.2022.9812880(1-10)Online publication date: 10-Jun-2022
https://doi.org/10.1109/IWQoS54832.2022.9812880
Asheralieva ANiyato D(2021)Learning-Based Mobile Edge Computing Resource Management to Support Public Blockchain NetworksIEEE Transactions on Mobile Computing10.1109/TMC.2019.295977220:3(1092-1109)Online publication date: 1-Mar-2021
https://doi.org/10.1109/TMC.2019.2959772
Li Y(2021)Layout Optimization of Landscape Architecture based on Intelligent Visual Scene Recognition and Saliency Analysis2021 Third International Conference on Intelligent Communication Technologies and Virtual Mobile Networks (ICICV)10.1109/ICICV50876.2021.9388435(859-862)Online publication date: 4-Feb-2021
https://doi.org/10.1109/ICICV50876.2021.9388435
Pokhrel SChoi J(2020)Federated Learning With Blockchain for Autonomous Vehicles: Analysis and Design ChallengesIEEE Transactions on Communications10.1109/TCOMM.2020.299068668:8(4734-4746)Online publication date: Aug-2020
https://doi.org/10.1109/TCOMM.2020.2990686
Yan J(2020)AIPL: The Theoretical Framework of Artificial Intelligence for Proportional Liability in China from Data Mining Perspectives2020 Fourth International Conference on Computing Methodologies and Communication (ICCMC)10.1109/ICCMC48092.2020.ICCMC-00075(399-403)Online publication date: Mar-2020
https://doi.org/10.1109/ICCMC48092.2020.ICCMC-00075
Cai YLi DWang Y(2020)Intelligent Crime Prevention and Control Big Data Analysis System Based on Imaging and Capsule Network ModelNeural Processing Letters10.1007/s11063-020-10256-1Online publication date: 30-Apr-2020
https://doi.org/10.1007/s11063-020-10256-1
Garcia-Carballeira FCalderon ACarretero J(2020)Enhancing the power of two choices load balancing algorithm using round robin policyCluster Computing10.1007/s10586-020-03139-6Online publication date: 22-Jun-2020
https://doi.org/10.1007/s10586-020-03139-6
Li Z(2020)Visual analysis framework for network abnormal data based on multi-agent modelSoft Computing10.1007/s00500-020-05257-0Online publication date: 19-Aug-2020
https://doi.org/10.1007/s00500-020-05257-0
Liu Z(2020) Retracted: Construction of urban agricultural health informatics safety supervision system based on imaging and deep learning Concurrency and Computation: Practice and Experience10.1002/cpe.583433:12Online publication date: 17-Jun-2020
https://doi.org/10.1002/cpe.5834

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents