Document Open Access Logo

On Payment Channels in Asynchronous Money Transfer Systems

Authors Oded Naor, Idit Keidar

PDF
Thumbnail PDF

File

LIPIcs.DISC.2022.29.pdf
  • Filesize: 0.79 MB
  • 20 pages

Document Identifiers

Author Details

Oded Naor
  • Technion, Haifa, Israel
Idit Keidar
  • Technion, Haifa, Israel

Funding

  • Naor, Oded: Oded Naor is grateful to the Azrieli Foundation for the award of an Azrieli Fellowship, and to the Technion Hiroshi Fujiwara Cyber-Security Research Center for providing a research grant.

Cite AsGet BibTex

Oded Naor and Idit Keidar. On Payment Channels in Asynchronous Money Transfer Systems. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.DISC.2022.29

Abstract

Money transfer is an abstraction that realizes the core of cryptocurrencies. It has been shown that, contrary to common belief, money transfer in the presence of Byzantine faults can be implemented in asynchronous networks and does not require consensus. Nonetheless, existing implementations of money transfer still require a quadratic message complexity per payment, making attempts to scale hard. In common blockchains, such as Bitcoin and Ethereum, this cost is mitigated by payment channels implemented as a second layer on top of the blockchain allowing to make many off-chain payments between two users who share a channel. Such channels require only on-chain transactions for channel opening and closing, while the intermediate payments are done off-chain with constant message complexity. But payment channels in-use today require synchrony; therefore, they are inadequate for asynchronous money transfer systems. In this paper, we provide a series of possibility and impossibility results for payment channels in asynchronous money transfer systems. We first prove a quadratic lower bound on the message complexity of on-chain transfers. Then, we explore two types of payment channels, unidirectional and bidirectional. We define them as shared memory abstractions and prove that in certain cases they can be implemented as a second layer on top of an asynchronous money transfer system whereas in other cases it is impossible.

Subject Classification

ACM Subject Classification
  • Computing methodologies → Distributed algorithms
Keywords
  • Blockchains
  • Asynchrony
  • Byzantine faults
  • Payment channels

Metrics

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

Related Versions

References

  1. Ittai Abraham, Dahlia Malkhi, and Alexander Spiegelman. Asymptotically optimal validated asynchronous byzantine agreement. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 337-346, 2019. Google Scholar
  2. Frederik Armknecht, Ghassan O Karame, Avikarsha Mandal, Franck Youssef, and Erik Zenner. Ripple: Overview and outlook. In International Conference on Trust and Trustworthy Computing, pages 163-180. Springer, 2015. Google Scholar
  3. Hagit Attiya and Jennifer L Welch. Sequential consistency versus linearizability. ACM Transactions on Computer Systems (TOCS), 12(2):91-122, 1994. Google Scholar
  4. Alex Auvolat, Davide Frey, Michel Raynal, and François Taïani. Money transfer made simple: a specification, a generic algorithm, and its proof. Bull. EATCS, 132, 2020. URL: http://eatcs.org/beatcs/index.php/beatcs/article/view/629.
  5. Zeta Avarikioti, Eleftherios Kokoris-Kogias, Roger Wattenhofer, and Dionysis Zindros. Brick: Asynchronous incentive-compatible payment channels. In International Conference on Financial Cryptography and Data Security, pages 209-230. Springer, 2021. Google Scholar
  6. Mihir Bellare and Gregory Neven. Identity-based multi-signatures from rsa. In Cryptographers’ Track at the RSA Conference, pages 145-162. Springer, 2007. Google Scholar
  7. Shai Ben-David, Allan Borodin, Richard Karp, Gabor Tardos, and Avi Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11(1):2-14, 1994. Google Scholar
  8. Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptol. ePrint Arch., 2018:46, 2018. Google Scholar
  9. Gabriel Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2):130-143, 1987. Google Scholar
  10. Shir Cohen and Idit Keidar. Tame the Wild with Byzantine Linearizability: Reliable Broadcast, Snapshots, and Asset Transfer. In Seth Gilbert, editor, 35th International Symposium on Distributed Computing (DISC 2021), volume 209 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1-18:18, Dagstuhl, Germany, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.DISC.2021.18.
  11. Shir Cohen, Idit Keidar, and Alexander Spiegelman. Not a coincidence: Sub-quadratic asynchronous byzantine agreement whp. In 34th International Symposium on Distributed Computing (DISC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  12. Daniel Collins, Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Matteo Monti, Matej Pavlovic, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, Andrei Tonkikh, and Athanasios Xygkis. Online payments by merely broadcasting messages. In 2020 50th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN), pages 26-38. IEEE, 2020. Google Scholar
  13. Christian Decker and Roger Wattenhofer. A fast and scalable payment network with bitcoin duplex micropayment channels. In Symposium on Self-Stabilizing Systems, pages 3-18. Springer, 2015. Google Scholar
  14. Danny Dolev and Ruediger Reischuk. Bounds on information exchange for byzantine agreement. In Proceedings of the First ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC '82, pages 132-140, New York, NY, USA, 1982. Association for Computing Machinery. Google Scholar
  15. Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer. Consensus in the presence of partial synchrony. Journal of the ACM (JACM), 35(2):288-323, 1988. Google Scholar
  16. Stefan Dziembowski, Lisa Eckey, Sebastian Faust, and Daniel Malinowski. Perun: Virtual payment channels over cryptographic currencies. IACR Cryptol. ePrint Arch., 2017:635, 2017. Google Scholar
  17. Ittay Eyal, Adem Efe Gencer, Emin Gün Sirer, and Robbert Van Renesse. Bitcoin-ng: A scalable blockchain protocol. In 13th USENIX symposium on networked systems design and implementation (NSDI 16), pages 45-59, 2016. Google Scholar
  18. Michael J Fischer, Nancy A Lynch, and Michael S Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM (JACM), 32(2):374-382, 1985. Google Scholar
  19. 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, pages 473-489, 2017. Google Scholar
  20. Rachid Guerraoui, Petr Kuznetsov, Matteo Monti, Matej Pavlovič, and Dragos-Adrian Seredinschi. The consensus number of a cryptocurrency. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, pages 307-316, 2019. Google Scholar
  21. Bingyong Guo, Zhenliang Lu, Qiang Tang, Jing Xu, and Zhenfeng Zhang. Dumbo: Faster asynchronous bft protocols. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 803-818, 2020. Google Scholar
  22. Saurabh Gupta. A non-consensus based decentralized financial transaction processing model with support for efficient auditing. Arizona State University, 2016. Google Scholar
  23. Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS), 13(1):124-149, 1991. Google Scholar
  24. Maurice P Herlihy and Jeannette M Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS), 12(3):463-492, 1990. Google Scholar
  25. HTLC. Hash time locked contracts. Accessed: 2022-02-05. URL: https://en.bitcoin.it/wiki/Hash_Time_Locked_Contracts.
  26. Harry Kalodner, Steven Goldfeder, Xiaoqi Chen, S Matthew Weinberg, and Edward W Felten. Arbitrum: Scalable, private smart contracts. In 27th USENIX Security Symposium 18, pages 1353-1370, 2018. Google Scholar
  27. Idit Keidar, Eleftherios Kokoris-Kogias, Oded Naor, and Alexander Spiegelman. All you need is dag. In Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, pages 165-175, 2021. Google Scholar
  28. Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382-401, 1982. Google Scholar
  29. Joshua Lind, Oded Naor, Ittay Eyal, Florian Kelbert, Emin Gün Sirer, and Peter Pietzuch. Teechain: a secure payment network with asynchronous blockchain access. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, pages 63-79, 2019. Google Scholar
  30. Dahlia Malkhi and Michael Reiter. A high-throughput secure reliable multicast protocol. Journal of Computer Security, 5(2):113-127, 1997. Google Scholar
  31. Andrew Miller, Iddo Bentov, Ranjit Kumaresan, and Patrick McCorry. Sprites: Payment channels that go faster than lightning. CoRR, abs/1702.05812, 2017. URL: http://arxiv.org/abs/1702.05812.
  32. Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of bft protocols. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 31-42, 2016. Google Scholar
  33. Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. Decentralized Business Review, page 21260, 2008. Google Scholar
  34. Oded Naor and Idit Keidar. Expected linear round synchronization: The missing link for linear byzantine smr. In 34th International Symposium on Distributed Computing (DISC 2020). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  35. Fernando Pedone and André Schiper. Handling message semantics with generic broadcast protocols. Distributed Computing, 15(2):97-107, 2002. Google Scholar
  36. Joseph Poon and Thaddeus Dryja. The bitcoin lightning network: Scalable off-chain instant payments, 2016. Google Scholar
  37. Michael O Rabin. Randomized byzantine generals. In 24th annual symposium on foundations of computer science (sfcs 1983), pages 403-409. IEEE, 1983. Google Scholar
  38. Raiden. Raiden network, 2020. Accessed: 2022-02-05. URL: https://raiden.network/.
  39. Jeremy Spilman. Anti dos for tx replacement, April 2013. URL: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2013-April/002433.html.
  40. Lightning Network Statistics. Real-time lightning network statistics. Accessed: 2022-02-01. URL: https://1ml.com/statistics.
  41. Optimism website. Accessed: 2022-02-01. URL: https://www.optimism.io/.
  42. Gavin Wood et al. Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper, 151(2014):1-32, 2014. Google Scholar
  43. Maofan Yin, Dahlia Malkhi, MK Reiter and, Guy Golan Gueta, and Ittai Abraham. HotStuff: BFT consensus with linearity and responsiveness. In 38th ACM symposium on Principles of Distributed Computing (PODC'19), 2019. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact