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

research-article

Blockchain Abstract Data Type

Authors:

Emmanuelle Anceaume,

Antonella Del Pozzo,

Romaric Ludinard,

Maria Potop-Butucaru,

Sara Tucci-PiergiovanniAuthors Info & Claims

SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures

Pages 349 - 358

https://doi.org/10.1145/3323165.3323183

Published: 17 June 2019 Publication History

Abstract

The presented work continues the line of recent distributed computing community efforts dedicated to the theoretical aspects of blockchains. This paper is the first to specify blockchains as a composition of abstract data types all together with a hierarchy of consistency criteria that formally characterizes the histories admissible for distributed programs that use them. Our work is based on an original oracle-based construction that, along with new consistency definitions, captures the eventual convergence process in blockchain systems. The paper presents as well some results on implementability of the presented abstractions and a mapping of representative existing blockchains from both academia and industry in our framework.

References

[1]

I. Abraham and D. Malkhi. The blockchain consensus layer and BFT. Bulletin of the EATCS, 3(123):1--23, 2017.

[2]

E. Anceaume, R. Ludinard, M. Potop-Butucaru, and F. Tronel. Bitcoin a distributed shared register. In Proceedings of the International Symposium on Stabilization, Safety, and Security of Distributed Systems, 2017.

[3]

E. Anceaume, A. D. Pozzo, R. Ludinard, M. Potop-Butucaru, and S. Tucci Piergiovanni. Blockchain abstract data type - full version. https://hal.archives-ouvertes.fr/hal-02113770, 2019.

[4]

E. Androulaki, A. Barger, V. Bortnikov, C. Cachin, K. Christidis, A. D. Caro, D. Enyeart, C. Ferris, G. Laventman, Y. Manevich, S. Muralidharan, C. Murthy, B. Nguyen, M. Sethi, G. Singh, K. Smith, A. Sorniotti, C. Stathakopoulou, M. Vukolic, S. W. Cocco, and J. Yellick. Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains. https://arxiv.org/pdf/1801.10228v1.pdf, 2018.

[5]

A. F. Anta, K. Konwar, C. Georgiou, and N. Nicolaou. Formalizing and implementing distributed ledger objects. ACM SIGACT News, 49(2):58--76, 2018.

[6]

C. Cachin, R. Guerraoui, and L. E. T. Rodrigues. Introduction to Reliable and Secure Distributed Programming (2. ed.). Springer, 2011.

Digital Library

[7]

C. Cachin, K. Kursawe, F. Petzold, and V. Shoup. Secure and efficient asynchronous broadcast protocols. In Proceedings of the Annual International Cryptology Conference on Advances in Cryptology (CRYPTO), 2001.

Digital Library

[8]

T. Crain, V. Gramoli, M. Larrea, and M. Raynal. (Leader/Randomization/Signature)-free Byzantine Consensus for Consortium Blockchains. http://arxiv.org/abs/1702.03068, 2017.

[9]

C. Decker, J. Seidel, and R. Wattenhofer. Bitcoin meets strong consistency. In Proceedings of the 17th International Conference on Distributed Computing and Networking, page 13, New York, NY, USA, 2016. ACM.

Digital Library

[10]

C. Dwork, N. Lynch, and L. Stockmeyer. Consensus in presence of partial synchrony. Journal of the ACM (JACM), 1988.

Digital Library

[11]

C. Dwork and M. Naor. Pricing via processing or combatting junk mail. In Advances in Cryptology - CRYPTO '92, 12th Annual International Cryptology Conference, Santa Barbara, California, USA, August 16--20, 1992, Proceedings, pages 139--147, 1992.

Digital Library

[12]

J. M. Falerio, S. Rajamani, K. Rajan, G. Ramalingam, and K. Vaswani. Generalized lattice agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), 2012.

Digital Library

[13]

Y. Gilad, R. Hemo, S. Micali, G. Vlachos, and N. Zeldovich. Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the Symposium on Operating Systems Principles (SOSP), pages 51--68, New York, NY, USA, 2017. ACM.

Digital Library

[14]

A. Girault, G. Gössler, R. Guerraoui, J. Hamza, and D.-A. Seredinschi. Monotonic prefix consistency in distributed systems. In International Conference on Formal Techniques for Distributed Objects, Components, and Systems, pages 41--57, Berlin, Germany, 2018. Springer.

[15]

M. Herlihy. Wait-free synchronization. ACM Trans. Program. Lang. Syst., 13(1):124--149, 1991.

Digital Library

[16]

E. Kokoris-Kogias, P. Jovanovic, N. Gailly, I. Khoffi, L. Gasser, and B. Ford. Enhancing bitcoin security and performance with strong consistency via collective signing. In 25th USENIX Security Symposium, USENIX Security 16, Austin, TX, USA, August 10--12, 2016., pages 279--296, Berkeley, CA, USA, 2016. USENIX Association.

Digital Library

[17]

L. Lamport, R. Shostak, and M. Pease. The byzantine generals problem. ACM Transactions on Programming Languages and Systems (TOPLAS), 4(3):382--401, 1982.

Digital Library

[18]

D. Mazieres and D. Shasha. Building secure file systems out of byzantine storage. In Proceedings of the twenty-first annual symposium on Principles of distributed computing, pages 108--117. ACM, 2002.

Digital Library

[19]

S. Nakamoto. Bitcoin: A Peer-to-Peer Electronic Cash System. https://bitcoin.org/bitcoin.pdf, 2008.

[20]

E. Oswald and M. Fischlin, editors. The Bitcoin Backbone Protocol: Analysis and Applications, volume 9057 of Lecture Notes in Computer Science. Springer, 2015.

[21]

R. Pass and E. Shi. Fruitchains: A fair blockchain. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC 2017, pages 315--324, New York, NY, USA, 2017. ACM.

Digital Library

[22]

M. Perrin. Distributed Systems, Concurrency and Consistency. ISTE Press, Elsevier, 2017.

Digital Library

[23]

M. Perrin, A. Mosté faoui, and C. Jard. Causal consistency: beyond memory. In Proceedings of the 21st ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP 2016, Barcelona, Spain, March 12--16, 2016, pages 26:1--26:12, New York, NY, USA, 2016. ACM.

Digital Library

[24]

G. Wood. Ethereum: A secure decentralised generalised transaction ledger. http://gavwood.com/Paper.pdf, 2014.

Cited By

Amoussou-Guenou YHerlihy MPotop-Butucaru MRajsbaum S(2024)Invited Paper: The Smart Contract ModelStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-74498-3_4(55-70)Online publication date: 20-Oct-2024
https://doi.org/10.1007/978-3-031-74498-3_4
Frey DMostefaoui APerrin MRoman PTaïani F(2023)Differentiated Consistency for Worldwide GossipsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.320915034:1(1-15)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TPDS.2022.3209150
Cholvi VFernández Anta AGeorgiou CNicolaou NRaynal MRusso A(2023)Atomic Appends in Asynchronous Byzantine Distributed LedgersJournal of Parallel and Distributed Computing10.1016/j.jpdc.2023.104748182(104748)Online publication date: Dec-2023
https://doi.org/10.1016/j.jpdc.2023.104748
Show More Cited By

Index Terms

Blockchain Abstract Data Type
1. Theory of computation
  1. Models of computation
    1. Concurrency
      1. Distributed computing models

Recommendations

Blockchain abstract data type: poster
PPoPP '19: Proceedings of the 24th Symposium on Principles and Practice of Parallel Programming

This paper is the first to specify blockchains as a composition of abstract data types all together with a hierarchy of consistency criteria that formally characterizes the histories admissible for distributed programs that use them. The paper presents ...
A Flexible Instant Payment System Based on Blockchain
Information Security and Privacy
Abstract
Improving the throughput of blockchain systems such as Bitcoin and Ethereum has been an important research problem. Off-chain payments are one of the most promising technologies to tackle this challenge. Once a payment channel, however, is ...
The effects of individual-level espoused national cultural values on the willingness to use Bitcoin-like blockchain currencies
Abstract
Some have called bitcoin a real bubble, while, according to others, it is the most radical invention of the twenty-first century. Nevertheless, there is a consensus regarding the disruptive potential of blockchain technology, which is ...
Highlights
- Espoused national cultural values affect the use of blockchain currencies.
- ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SPAA '19: The 31st ACM Symposium on Parallelism in Algorithms and Architectures

June 2019

410 pages

ISBN:9781450361842

DOI:10.1145/3323165

General Chair:
Christian Scheideler
Paderborn University, Germany
,
Program Chair:
Petra Berenbrink
University of Hamburg, Germany

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

In-Cooperation

EATCS: European Association for Theoretical Computer Science

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2019

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SPAA '19

Sponsor:

SPAA '19: 31st ACM Symposium on Parallelism in Algorithms and Architectures

June 22 - 24, 2019

AZ, Phoenix, USA

Acceptance Rates

SPAA '19 Paper Acceptance Rate 34 of 109 submissions, 31%;

Overall Acceptance Rate 447 of 1,461 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
427
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)4

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Amoussou-Guenou YHerlihy MPotop-Butucaru MRajsbaum S(2024)Invited Paper: The Smart Contract ModelStabilization, Safety, and Security of Distributed Systems10.1007/978-3-031-74498-3_4(55-70)Online publication date: 20-Oct-2024
https://doi.org/10.1007/978-3-031-74498-3_4
Frey DMostefaoui APerrin MRoman PTaïani F(2023)Differentiated Consistency for Worldwide GossipsIEEE Transactions on Parallel and Distributed Systems10.1109/TPDS.2022.320915034:1(1-15)Online publication date: 1-Jan-2023
https://doi.org/10.1109/TPDS.2022.3209150
Cholvi VFernández Anta AGeorgiou CNicolaou NRaynal MRusso A(2023)Atomic Appends in Asynchronous Byzantine Distributed LedgersJournal of Parallel and Distributed Computing10.1016/j.jpdc.2023.104748182(104748)Online publication date: Dec-2023
https://doi.org/10.1016/j.jpdc.2023.104748
Caldarelli G(2022)Overview of Blockchain Oracle ResearchFuture Internet10.3390/fi1406017514:6(175)Online publication date: 8-Jun-2022
https://doi.org/10.3390/fi14060175
Pillai BBiswas KHou ZMuthukkumarasamy V(2022)Cross-Blockchain Technology: Integration Framework and Security AssumptionsIEEE Access10.1109/ACCESS.2022.316717210(41239-41259)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3167172
Roussille HGürcan ÖMichel F(2021)AGR4BS: A Generic Multi-Agent Organizational Model for Blockchain SystemsBig Data and Cognitive Computing10.3390/bdcc60100016:1(1)Online publication date: 21-Dec-2021
https://doi.org/10.3390/bdcc6010001
Potop-Butucaru M(2021)Blockchains and the CommonsNetworked Systems10.1007/978-3-030-67087-0_3(28-44)Online publication date: 14-Jan-2021
https://doi.org/10.1007/978-3-030-67087-0_3
Bénassy GOoshita FInoue M(2021)Eventually consistent distributed ledger despite degraded atomic broadcastConcurrency and Computation: Practice and Experience10.1002/cpe.619935:11Online publication date: 26-Jan-2021
https://doi.org/10.1002/cpe.6199
Tseng LYao XOtoum SAloqaily MJararweh Y(2020)Blockchain-based database in an IoT environment: challenges, opportunities, and analysisCluster Computing10.1007/s10586-020-03138-7Online publication date: 9-Jul-2020
https://doi.org/10.1007/s10586-020-03138-7
Tucci-Piergiovanni S(2019)Invited Paper: On the Characterization of Blockchain Consensus Under IncentivesStabilization, Safety, and Security of Distributed Systems10.1007/978-3-030-34992-9_1(1-15)Online publication date: 14-Nov-2019
https://doi.org/10.1007/978-3-030-34992-9_1
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.

Media

Figures

Other

Tables

View Table of Contents