Algorithmic Channel Design

Authors Georgia Avarikioti, Yuyi Wang, Roger Wattenhofer



PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.16.pdf
  • Filesize: 408 kB
  • 12 pages

Document Identifiers

Author Details

Georgia Avarikioti
  • ETH Zurich, Switzerland
Yuyi Wang
  • ETH Zurich, Switzerland
Roger Wattenhofer
  • ETH Zurich, Switzerland

Cite AsGet BibTex

Georgia Avarikioti, Yuyi Wang, and Roger Wattenhofer. Algorithmic Channel Design. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.16

Abstract

Payment networks, also known as channels, are a most promising solution to the throughput problem of cryptocurrencies. In this paper we study the design of capital-efficient payment networks, offline as well as online variants. We want to know how to compute an efficient payment network topology, how capital should be assigned to the individual edges, and how to decide which transactions to accept. Towards this end, we present a flurry of interesting results, basic but generally applicable insights on the one hand, and hardness results and approximation algorithms on the other hand.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • blockchain
  • payment channels
  • layer 2 solution
  • network design
  • payment hubs
  • routing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Ethereum white paper. URL: https://github.com/ethereum/wiki/wiki/White-Paper.
  2. Raiden network, 2017. URL: http://raiden.network/.
  3. Georgia Avarikioti, Gerrit Janssen, Yuyi Wang, and Roger Wattenhofer. Payment Network Design with Fees, 2018. URL: https://github.com/zetavar/Payment-Network-Design-with-Fees/blob/master/Payment_Network_Design_with_Fees-Full_Version.pdf.
  4. Adam Back, Matt Corallo, Luke Dashjr, Mark Friedenbach, Gregory Maxwell, Andrew Miller, Andrew Poelstra, Jorge Timón, and Pieter Wuille. Enabling Blockchain Innovations with Pegged Sidechains, 2014. URL: https://www.blockstream.com/sidechains.pdf.
  5. Conrad Burchert, Christian Decker, and Roger Wattenhofer. Scalable Funding of Bitcoin Micropayment Channel Networks. In 19th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Boston, Massachusetts, USA, November 2017. Google Scholar
  6. Kyle Croman, Christian Decker, Ittay Eyal, Adem Efe Gencer, Ari Juels, Ahmed Kosba, Andrew Miller, Prateek Saxena, Elaine Shi, Emin Gün Sirer, Dawn Song, and Roger Wattenhofer. On Scaling Decentralized Blockchains. In Financial Cryptography and Data Security, pages 106-125. Springer Berlin Heidelberg, 2016. Google Scholar
  7. Christian Decker and Roger Wattenhofer. A Fast and Scalable Payment Network with Bitcoin Duplex Micropayment Channels. In Andrzej Pelc and Alexander A. Schwarzmann, editors, Stabilization, Safety, and Security of Distributed Systems, pages 3-18, Cham, 2015. Springer International Publishing. Google Scholar
  8. Matthew Green and Ian Miers. Bolt: Anonymous Payment Channels for Decentralized Currencies. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS '17, pages 473-489. ACM, 2017. Google Scholar
  9. Ethan Heilman, Leen Alshenibr, Foteini Baldimtsi, Alessandra Scafuro, and Sharon Goldberg. TumbleBit: An Untrusted Bitcoin-Compatible Anonymous Payment Hub. In Network and Distributed Systems Security Symposium 2017 (NDSS), February 2017, 2017. Google Scholar
  10. T. Hu. Optimum Communication Spanning Trees. SIAM Journal on Computing, 3(3):188-195, 1974. URL: http://dx.doi.org/10.1137/0203015.
  11. D. S. Johnson, J. K. Lenstra, and A. H. G. Kan Rinnooy. The complexity of the network design problem. Networks, 8(4):279-285, 1978. URL: http://dx.doi.org/10.1002/net.3230080402.
  12. Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly, Ewa Syta, and Bryan Ford. OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding, 2017. Google Scholar
  13. Loi Luu, Viswesh Narayanan, Chaodong Zheng, Kunal Baweja, Seth Gilbert, and Prateek Saxena. A secure sharding protocol for open blockchains. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 17-30. ACM, 2016. Google Scholar
  14. Giulio Malavolta, Pedro Moreno-Sanchez, Aniket Kate, and Matteo Maffei. SilentWhispers: Enforcing Security and Privacy in Decentralized Credit Networks. In Network and Distributed Systems Security Symposium 2017 (NDSS), 2017. Google Scholar
  15. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system, 2008. Google Scholar
  16. Joseph Poon and Thaddeus Dryja. The Bitcoin lightning network: Scalable off-chain instant payments, 2015. URL: https://lightning.network.
  17. Pavel Prihodko, Slava Zhigulin, Mykola Sahno, Aleksei Ostrovskiy, and Olaoluwa Osuntokun. Flare: An Approach to Routing in Lightning Network, 2016. URL: https://bitfury.com/content/downloads/whitepaper_flare_an_approach_to_routing_in_lightning_network_7_7_2016.pdf.
  18. Stefanie Roos, Pedro Moreno-Sanchez, Aniket Kate, and Ian Goldberg. Settling Payments Fast and Private: Efficient Decentralized Routing for Path-Based Transactions. In Network and Distributed Systems Security Symposium 2018 (NDSS), 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail