Document Open Access Logo

Atomic Appends: Selling Cars and Coordinating Armies with Multiple Distributed Ledgers

Authors Antonio Fernández Anta, Chryssis Georgiou, Nicolas Nicolaou

PDF
Thumbnail PDF

File

OASIcs.Tokenomics.2019.5.pdf
  • Filesize: 0.51 MB
  • 16 pages

Document Identifiers

Author Details

Antonio Fernández Anta
  • IMDEA Networks Institute, Madrid, Spain
Chryssis Georgiou
  • Dept. of Computer Science, University of Cyprus, Nicosia, Cyprus
Nicolas Nicolaou
  • Algolysis Ltd, Cyprus

Funding

Partially supported by the Spanish Ministry of Science, Innovation and Universities grant DiscoEdge (TIN2017-88749-R), the Comunidad de Madrid grant EdgeData-CM (P2018/TCS-4499), the NSF of China grant 61520106005, and research funds from the University of Cyprus (CG-RA2019).

Acknowledgements

We would like to thank Kishori Konwar, Michel Raynal, and Gregory Chockler for insightful discussions.

Cite As Get BibTex

Antonio Fernández Anta, Chryssis Georgiou, and Nicolas Nicolaou. Atomic Appends: Selling Cars and Coordinating Armies with Multiple Distributed Ledgers. In International Conference on Blockchain Economics, Security and Protocols (Tokenomics 2019). Open Access Series in Informatics (OASIcs), Volume 71, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/OASIcs.Tokenomics.2019.5

Abstract

The various applications using Distributed Ledger Technologies (DLT) or blockchains, have led to the introduction of a new "marketplace" where multiple types of digital assets may be exchanged. As each blockchain is designed to support specific types of assets and transactions, and no blockchain will prevail, the need to perform interblockchain transactions is already pressing.

In this work we examine the fundamental problem of interoperable and interconnected blockchains. In particular, we begin by introducing the Multi-Distributed Ledger Objects (MDLO), which is the result of aggregating multiple Distributed Ledger Objects - DLO (a DLO is a formalization of the blockchain) and that supports append and get operations of records (e.g., transactions) in them from multiple clients concurrently. Next we define the AtomicAppends problem, which emerges when the exchange of digital assets between multiple clients may involve appending records in more than one DLO. Specifically, AtomicAppend requires that either all records will be appended on the involved DLOs or none. We examine the solvability of this problem assuming rational and risk-averse clients that may fail by crashing, and under different client utility and append models, timing models, and client failure scenarios. We show that for some cases the existence of an intermediary is necessary for the problem solution. We propose the implementation of such intermediary over a specialized blockchain, we term Smart DLO (SDLO), and we show how this can be used to solve the AtomicAppends problem even in an asynchronous, client competitive environment, where all the clients may crash.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
Keywords
  • DLO
  • Interoperability
  • Atomic Appends
  • Rational Clients
  • Fault-tolerance

Metrics

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

References

  1. Atomic swap. URL: https://en.bitcoin.it/wiki/Atomic_cross-chain_trading.
  2. Cosmos. URL: https://cosmos.network.
  3. Oraclize. URL: http://www.oraclize.it.
  4. PolkaDot. URL: https://polkadot.network.
  5. Elli Androulaki et al. Channels: Horizontal Scaling and Confidentiality on Permissioned Blockchains. In ESORICS 2018, pages 111-131, 2018. URL: https://doi.org/10.1007/978-3-319-99073-6_6.
  6. Elli Androulaki et al. Hyperledger fabric: a distributed operating system for permissioned blockchains. In EuroSys 2018, pages 30:1-30:15, 2018. URL: https://doi.org/10.1145/3190508.3190538.
  7. Antonio Fernandez Anta, Chryssis Georgiou, Kishori Konwar, and Nicolas Nicolaou. Formalizing and Implementing Distributed Ledger Objects. In NETYS 2018, 2018. Also, in SIGACT News, 49(2):58-76, June 2018. Google Scholar
  8. Matthew K. Franklin and Gene Tsudik. Secure Group Barter: Multi-party Fair Exchange with Semi-Trusted Neutral Parties. In FC 1998, pages 90-102, 1998. URL: https://doi.org/10.1007/BFb0055475.
  9. Mimi Gentz and Johnny Dude. Tunable data consistency levels in Microsoft Azure Cosmos DB. https://docs.microsoft.com/en-us/azure/cosmos-db/consistency-levels, June 2017.
  10. Piotr J. Gmytrasiewicz and Edmund H. Durfee. Decision-theoretic recursive modeling and the coordinated attack problem. In Proc.of 1992 Conference on AI Planning Systems, pages 88-95. Morgan Kaufmann Publ Inc, 1992. Google Scholar
  11. Interledger W3C Community Group. Interledger. URL: https://interledger.org/.
  12. Thomas Hardjono, Alexander Lipton, and Alex Pentland. Towards a Design Philosophy for Interoperable Blockchain Systems. CoRR, abs/1805.05934, 2018. URL: http://arxiv.org/abs/1805.05934.
  13. Maurice Herlihy. Atomic Cross-Chain Swaps. In PODC 2018, pages 245-254, 2018. URL: https://doi.org/10.1145/3212734.3212736.
  14. Maurice Herlihy and Jeannette M. Wing. Linearizability: A Correctness Condition for Concurrent Objects. ACM Transactions on Programming Languages and Systems, 12(3):463-–492, 1990. Google Scholar
  15. Leslie Lamport. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE Transactions on Computers, C-28(9):690-–691, 1979. Google Scholar
  16. N.A. Lynch. Distributed Algorithms. Morgan Kaufmann Publishers, 1996. Google Scholar
  17. Silvio Micali, Michael O. Rabin, and Joe Kilian. Zero-Knowledge Sets. In FOCS 2003, pages 80-91, 2003. URL: https://doi.org/10.1109/SFCS.2003.1238183.
  18. Andrew Miller, Iddo Bentov, Ranjit Kumaresan, Christopher Cordi, and Patrick McCorry. Sprites and State Channels: Payment Networks that Go Faster than Lightning. arXiv preprint arXiv:1702.05812, 2017. Google Scholar
  19. Aybek Mukhamedov, Steve Kremer, and Eike Ritter. Analysis of a Multi-party Fair Exchange Protocol and Formal Proof of Correctness in the Strand Space Model. In FC 2005, 2005. URL: https://doi.org/10.1007/11507840_23.
  20. Arvind Narayanan et al. Bitcoin and Cryptocurrency Technologies - A Comprehensive Introduction. Princeton University Press, 2016. URL: http://press.princeton.edu/titles/10908.html.
  21. Martin J Osborne et al. An introduction to game theory, volume 3. Oxford university press New York, 2004. Google Scholar
  22. Joseph Poon and Thaddeus Dryja. The bitcoin lightning network: Scalable off-chain instant payments, 2016. See URL: https://lightning.network/lightning-network-paper.pdf.
  23. M. Raynal. Concurrent Programming: Algorithms, Principles, and Foundations. Springer, 2013. Google Scholar
  24. Michel Raynal. Distributed Algorithms for Message-Passing Systems. Springer, 2013. URL: https://doi.org/10.1007/978-3-642-38123-2.
  25. Ron van der Meyden. On the specification and verification of atomic swap smart contracts. CoRR, abs/1811.06099, 2018. URL: http://arxiv.org/abs/1811.06099.
  26. Matteo Gianpietro Zago. 50+ Examples of How Blockchains are Taking Over the World. Medium, 2018. URL: https://medium.com/@matteozago/50-examples-of-how-blockchains-are-taking-over-the-world-4276bf488a4b.
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 About DROPS Imprint Privacy Contact