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

research-article

Flash: efficient dynamic routing for offchain networks

Authors:

Tao WangAuthors Info & Claims

CoNEXT '19: Proceedings of the 15th International Conference on Emerging Networking Experiments And Technologies

Pages 370 - 381

https://doi.org/10.1145/3359989.3365411

Published: 03 December 2019 Publication History

Abstract

Offchain networks emerge as a promising solution to address the scalability challenge of blockchain. Participants make payments through offchain networks instead of committing transactions on-chain. Routing is critical to the performance of offchain networks. Existing solutions use either static routing with poor performance or dynamic routing with high overhead to obtain the dynamic channel balance information. In this paper, we propose Flash, a new dynamic routing solution that leverages the unique transactions characteristics in offchain networks to strike a better tradeoff between path optimality and probing overhead. By studying the traces of real offchain networks, we find that the payment sizes are heavy-tailed, and most payments are highly recurrent. Flash thus differentiates the treatment of elephant payments from that of mice payments. It uses a modified max-flow algorithm for elephant payments to find paths with sufficient capacity, and strategically routes the payment across paths to minimize the transaction fees. Mice payments are sent directly by looking up a routing table with a few precomputed paths to reduce probing overhead. Testbed experiments and trace-driven simulations show that Flash improves the success volume of payments by up to 2.3x compared to the state-of-the-art routing algorithm.

References

[1]

2018. Atomic Multi-path Payment. https://lists.linuxfoundation.org/pipermail/lightning-dev/2018-February/000993.html.

[2]

2018. Ripple transaction trace. https://crysp.uwaterloo.ca/software/speedymurmurs/.

[3]

2019. Bitcoin. https://bitcoin.org/en/.

[4]

2019. c-lightning Daemon. https://github.com/ElementsProject/lightning/tree/master/lightningd.

[5]

2019. Lightning Network Daemon. https://github.com/lightningnetwork/lnd.

[6]

2019. NetworkX. https://networkx.github.io/.

[7]

2019. Raiden Network Daemon. https://github.com/raiden-network/raiden.

[8]

2019. Real-Time Lightning Network Statistics. https://1ml.com/statistics.

[9]

2019. Ripple. https://ripple.com/.

[10]

2019. The Lightning Network. https://lightning.network/.

[11]

2019. The Raiden Network. https://raiden.network/.

[12]

2019. Transaction Rate of Bitcoin. https://www.blockchain.com/en/charts/transactions-per-second.

[13]

Mohammad Al-Fares, Sivasankar Radhakrishnan, Barath Raghavan, Nelson Huang, and Amin Vahdat. 2010. Hedera: Dynamic Flow Scheduling for Data Center Networks. In Proc. USENIX NSDI.

Digital Library

[14]

Mohammad Alizadeh, Tom Edsall, Sarang Dharmapurikar, Ramanan Vaidyanathan, Kevin Chu, Andy Fingerhut, Vinh The Lam, Francis Matus, Rong Pan, Navindra Yadav, and George Varghese. 2014. CONGA: Distributed Congestion-Aware Load Balancing for Datacenters. In Proc. ACM SIGCOMM.

Digital Library

[15]

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms. MIT Press.

[16]

Andrew R. Curtis, Jeffrey C. Mogul, Jean Tourrilhes, Praveen Yalagandula, Puneet Sharma, and Sujata Banerjee. 2011. DevoFlow: Scaling Flow Management for High-performance Networks. In Proc. ACM SIGCOMM.

Digital Library

[17]

Lester Randolph Ford and Delbert R Fulkerson. 1956. Maximal flow through a network. Canadian Journal of Mathematics 8 (1956), 399--404.

[18]

Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. 2017. Algorand: Scaling byzantine agreements for cryptocurrencies. In Proc. ACM SOSP.

Digital Library

[19]

Keqiang He, Eric Rozner, Kanak Agarwal, Wes Felter, John Carter, and Aditya Akella. 2015. Presto: Edge-based Load Balancing for Fast Datacenter Networks. In Proc. ACM SIGCOMM.

Digital Library

[20]

Chi-Yao Hong, Srikanth Kandula, Ratul Mahajan, Ming Zhang, Vijay Gill, Mohan Nanduri, and Roger Wattenhofer. 2013. Achieving High Utilization with Software-Driven WAN. In Proc. ACM SIGCOMM.

Digital Library

[21]

Sushant Jain, Alok Kumar, Subhasree Mandal, Joon Ong, Leon Poutievski, Arjun Singh, Subbaiah Venkata, Jim Wanderer, Junlan Zhou, Min Zhu, Jon Zolla, Urs Hölzle, Stephen Stuart, and Amin Vahdat. 2013. B4: Experience with a Globally-Deployed Software Defined WAN. In Proc. ACM SIGCOMM.

Digital Library

[22]

Rami Khalil and Arthur Gervais. 2017. Revive: Rebalancing off-blockchain payment networks. In Proc. ACM CCS.

Digital Library

[23]

Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena. 2016. A secure sharding protocol for open blockchains. In Proc. ACM CCS.

Digital Library

[24]

Pedro Moreno-Sanchez, Aniket Kate, and Matteo Maffei. 2017. SilentWhispers: Enforcing Security and Privacy in Decentralized Credit Networks. In Proc. NDSS.

[25]

Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. Technical Report (2008). https://bitcoin.org/bitcoin.pdf

[26]

J. Perry, H. Balakrishnan, and D. Shah. 2017. Flowtune: Flowlet Control for Datacenter Networks. In Proc. USENIX NSDI.

[27]

Joseph Poon and Thaddeus Dryja. 2016. The bitcoin lightning network: Scalable off-chain instant payments. Technical Report (2016). https://lightning.network/lightning-network-paper.pdf

[28]

Pavel Prihodko, Slava Zhigulin, Mykola Sahno, Aleksei Ostrovskiy, and Olaoluwa Osuntokun. 2016. Flare:An approach to routing in lightning network. White Paper (2016). https://bitfury.com/content/downloads/whitepaper_flare_an_approach_to_routing_in_lightning_network_7_7_2016.pdf

[29]

Stefanie Roos, Pedro Moreno-Sanchez, Aniket Kate, and Ian Goldberg. 2018. Settling Payments Fast and Private: Efficient Decentralized Routing for Path-Based Transactions. In Proc. NDSS.

[30]

Vibhaalakshmi Sivaraman, Shaileshh Bojja Venkatakrishnan, Mohammad Alizadeh, Giulia Fanti, and Pramod Viswanath. 2018. Routing Cryptocurrency with the Spider Network. In Proc. ACM HotNets.

Digital Library

[31]

Erico Vanini, Rong Pan, Mohammad Alizadeh, Parvin Taheri, and Tom Edsall. 2017. Let It Flow: Resilient Asymmetric Load Balancing with Flowlet Switching. In Proc. USENIX NSDI.

[32]

Jiaping Wang and Hao Wang. 2019. Monoxide: Scale Out Blockchain with Asynchronized Consensus Zones. In Proc. USENIX NSDI.

[33]

Peng Wang, Hong Xu, Zhixiong Niu, Dongsu Han, and Yongqiang Xiong. 2016. Expeditus: Congestion-aware Load Balancing in Clos Data Center Networks. In Proc. ACM SoCC.

Digital Library

[34]

Duncan J Watts and Steven H Strogatz. 1998. Collective dynamics of 'small-world' networks. Nature 393, 6684 (1998), 440.

[35]

Gavin Wood. 2014. Ethereum: a secure decentralized transaction ledger. http://gavwood.com/paper.pdf.

[36]

Jin Y Yen. 1971. Finding the k shortest loopless paths in a network. Management Science 17, 11 (1971), 712--716.

Digital Library

[37]

Mahdi Zamani, Mahnush Movahedi, and Mariana Raykova. 2018. RapidChain: scaling blockchain via full sharding. In Proc. ACM CCS.

Digital Library

Cited By

Jin AYe YLee BLi XQiao Y(2025)PaySwitch: Smart Contract-Based Payment Switch for Off-Chain Payment Channel NetworksIEEE Access10.1109/ACCESS.2025.352774613(14837-14856)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2025.3527746
Lobmaier DKonlechner RSchulte SWeber I(2024)Assessing Routing Algorithms for Payment Channel NetworksDistributed Ledger Technologies: Research and Practice10.1145/36435663:1(1-27)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1145/3643566
Ababneh MKolachala KVishwanathan RQuek TGao DZhou JCardenas A(2024)Auroch: Auction-Based Multipath Routing for Payment Channel NetworksProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3657021(1861-1877)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3657021
Show More Cited By

Index Terms

Flash: efficient dynamic routing for offchain networks
1. Networks
  1. Network protocols
    1. Network protocol design
  2. Network types
    1. Overlay and other logical network structures
      1. Peer-to-peer networks

Recommendations

Revive: Rebalancing Off-Blockchain Payment Networks
CCS '17: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security

Scaling the transaction throughput of decentralized blockchain ledgers such as Bitcoin and Ethereum has been an ongoing challenge. Two-party duplex payment channels have been designed and used as building blocks to construct linked payment networks, ...
Gnocchi: Multiplexed Payment Channels for Cryptocurrencies
Network and System Security
Abstract
As the underlying technology of mainstream cryptocurrencies such as Bitcoin and Ethereum, blockchain builds a decentralized payment system. However, the security and consistency of such system derive from the wide replication of transaction data ...
LApps: Technological, Legal and Market Potentials of Blockchain Lightning Network Applications
ICISDM '19: Proceedings of the 2019 3rd International Conference on Information System and Data Mining

Following in the footsteps of pioneer Bitcoin, many altcoins as well as coloured coins have been being developed and merchandised adopting blockchain as the core enabling technology. However, since interoperability and scalability, due to high and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CoNEXT '19: Proceedings of the 15th International Conference on Emerging Networking Experiments And Technologies

December 2019

395 pages

ISBN:9781450369985

DOI:10.1145/3359989

General Chairs:
Aziz Mohaisen
University of Central Florida
,
Zhi-Li Zhang
University of Minnesota

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

SIGCOMM: ACM Special Interest Group on Data Communication

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 December 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Hong Kong RGC GRF

Conference

CoNEXT '19

Sponsor:

SIGCOMM

CoNEXT '19: The 15th International Conference on emerging Networking EXperiments and Technologies

December 9 - 12, 2019

Florida, Orlando

Acceptance Rates

Overall Acceptance Rate 198 of 789 submissions, 25%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

73
Total Citations
View Citations
758
Total Downloads

Downloads (Last 12 months)68
Downloads (Last 6 weeks)15

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Jin AYe YLee BLi XQiao Y(2025)PaySwitch: Smart Contract-Based Payment Switch for Off-Chain Payment Channel NetworksIEEE Access10.1109/ACCESS.2025.352774613(14837-14856)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2025.3527746
Lobmaier DKonlechner RSchulte SWeber I(2024)Assessing Routing Algorithms for Payment Channel NetworksDistributed Ledger Technologies: Research and Practice10.1145/36435663:1(1-27)Online publication date: 18-Mar-2024
https://dl.acm.org/doi/10.1145/3643566
Ababneh MKolachala KVishwanathan RQuek TGao DZhou JCardenas A(2024)Auroch: Auction-Based Multipath Routing for Payment Channel NetworksProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3657021(1861-1877)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3657021
Panwar GVishwanathan RTorres GMisra SQuek TGao DZhou JCardenas A(2024)SPRITE: Secure and Private Routing in Payment Channel NetworksProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3644995(1878-1894)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3644995
Kolachala KAbabneh MVishwanathan RQuek TGao DZhou JCardenas A(2024)RACED: Routing in Payment Channel Networks Using Distributed Hash TablesProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3637653(1895-1910)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3637653
Podiatchev YOrda ARottenstreich O(2024)Survivable Payment Channel NetworksIEEE Transactions on Network and Service Management10.1109/TNSM.2024.345622921:6(6218-6232)Online publication date: Dec-2024
https://doi.org/10.1109/TNSM.2024.3456229
Camilo GRebello Gde Souza LCampista MCosta L(2024)ProfitPilot: Enabling Rebalancing in Payment Channel Networks Through Profitable Cycle CreationIEEE Transactions on Network and Service Management10.1109/TNSM.2024.336125021:3(3167-3178)Online publication date: Jun-2024
https://doi.org/10.1109/TNSM.2024.3361250
Khamis JKotzer ARottenstreich O(2024)Topologies for Blockchain Payment Channel Networks: Models and ConstructionsIEEE/ACM Transactions on Networking10.1109/TNET.2024.344527432:6(4781-4797)Online publication date: Dec-2024
https://doi.org/10.1109/TNET.2024.3445274
Zhang XQian C(2024)Toward Aggregated Payment Channel NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2024.342300032:5(4333-4348)Online publication date: Oct-2024
https://doi.org/10.1109/TNET.2024.3423000
Wang XYu RYang DXue GGu HLi ZZhou F(2024)Fence: Fee-Based Online Balance-Aware Routing in Payment Channel NetworksIEEE/ACM Transactions on Networking10.1109/TNET.2023.332413632:2(1661-1676)Online publication date: Apr-2024
https://doi.org/10.1109/TNET.2023.3324136
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten