OrderlessChain: A CRDT-based BFT Coordination-free Blockchain Without Global Order of Transactions
Pages 137 - 150
Abstract
Existing permissioned blockchains often rely on coordination-based consensus protocols to ensure the safe execution of applications in a Byzantine environment. Furthermore, the protocols serialize the transactions by ordering them in a global order. The serializ-ability preserves the correctness of the application's state stored on the blockchain. However, coordination-based protocols limit the throughput and scalability and induce high latency. In contrast, application-level correctness requirements exist that are not dependent on the order of transactions, known as invariant-confluence (I-confluence). The I-confluent applications can execute transactions in a coordination-free manner, benefiting from the improved scalability compared to the coordination-based approaches. The safety and liveness of I-confluent applications are studied in non-Byzantine environments, but the correct execution of such applications remains a challenge in Byzantine coordination-free environments. We introduce OrderlessChain, a novel permissioned blockchain based on a novel BFT coordination-free protocol for the safe and live execution of I-confluent applications in a Byzantine environment. We implemented a prototype of our system, and our evaluation results show that our coordination-free approach performs significantly better than coordination-based blockchains.
References
[1]
I. Abraham, D. Malkhi, K. Nayak, L. Ren, and M. Yin. 2020. Sync HotStuff: Simple and Practical Synchronous State Machine Replication. In 2020 IEEE Symposium on Security and Privacy. IEEE, 106--118. https://doi.org/10.1109/SP40000.2020.00044
[2]
E. Androulaki, A. Barger, V. Bortnikov, C. Cachin, K. Christidis, A. De 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. Vukolić, S. W. Cocco, and J. Yellick. 2018. Hyperledger Fabric: A Distributed Operating System for Permissioned Blockchains. In Proceedings of the Thirteenth EuroSys Conference. ACM, 30:1--30:15. https://doi.org/10.1145/3190508.3190538
[3]
The Go Authors. 2023. Golang, Go Programming Language. https://golang.org/Accessed: 2023-09-12.
[4]
P. Bailis, A. Fekete, M.J. Franklin, A. Ghodsi, J. M. Hellerstein, and I. Stoica. 2014. Coordination Avoidance in Database Systems. Proc. VLDB Endow. (2014), 185--196. https://doi.org/10.14778/2735508.2735509
[5]
V. Balegas, S. Duarte, C. Ferreira, R. Rodrigues, N. Preguiça, M. Najafzadeh, and M. Shapiro. 2015. Putting Consistency Back into Eventual Consistency. In Proceedings of the Tenth European Conference on Computer Systems. ACM. https://doi.org/10.1145/2741948.2741972
[6]
V. Balegas, D. Serra, S. Duarte, C. Ferreira, M. Shapiro, R. Rodrigues, and N. Preguiça. 2015. Extending Eventually Consistent Cloud Databases for Enforcing Numeric Invariants. In 2015 IEEE 34th Symposium on Reliable Distributed Systems. IEEE, 31--36. https://doi.org/10.1109/SRDS.2015.32
[7]
A. Barger, Y. Manevich, H. Meir, and Y. Tock. 2021. A Byzantine Fault-Tolerant Consensus Library for Hyperledger Fabric. In 2021 IEEE International Conference on Blockchain and Cryptocurrency. IEEE, 1--9. https://doi.org/10.1109/ICBC51069.2021.9461099
[8]
J. Bauwens and E. Gonzalez Boix. 2019. Memory Efficient CRDTs in Dynamic Environments. In Proceedings of the 11th ACM SIGPLAN International Workshop on Virtual Machines and Intermediate Languages. ACM, 48--57. https://doi.org/10.1145/3358504.3361231
[9]
A. Bessani, J. Sousa, and M. Vukolić. 2017. A Byzantine Fault-Tolerant Ordering Service for the Hyperledger Fabric Blockchain Platform. In Proceedings of the 1st Workshop on Scalable and Resilient Infrastructures for Distributed Ledgers. ACM. https://doi.org/10.1145/3152824.3152830
[10]
R. Brown, S. Cribbs, C. Meiklejohn, and S. Elliott. 2014. RiakDTMap: A Composable, Convergent Replicated Dictionary. In Proceedings of the First Workshop on Principles and Practice of Eventual Consistency. ACM, 1--1. https://doi.org/10.1145/2596631.2596633
[11]
C. Cachin and M. Vukolic. 2017. Blockchain Consensus Protocols in the Wild. CoRR (2017). arXiv:1707.01873
[12]
M. Capretto, M. Ceresa, A. F. Anta, A. Russo, and C. Sánchez. 2022. Setchain: Improving Blockchain Scalability with Byzantine Distributed Sets and Barriers. arXiv:2206.11845
[13]
S. J. Castiñeira and A. Bieniusa. 2015. Collaborative Offline Web Applications Using Conflict-free Replicated Data Types. In Proceedings of the First Workshop on Principles and Practice of Consistency for Distributed Data. ACM. https://doi.org/10.1145/2745947.2745952
[14]
J. A. Chacko, R. Mayer, and H-A. Jacobsen. 2021. Why Do My Blockchain Transactions Fail? A Study of Hyperledger Fabric. ACM, 221--234. https://doi.org/10.1145/3448016.3452823
[15]
J. A. Chacko, R. Mayer, and H.-A. Jacobsen. 2023. How To Optimize My Blockchain? A Multi-Level Recommendation Approach. Proc. ACM Manag. Data (2023). https://doi.org/10.1145/3588704
[16]
R. Chaganti, B. Bhushan, and V. Ravi. 2022. The Role of Blockchain in DDoS Attacks Mitigation: Techniques, Open Challenges and Future Directions. arXiv:2202.03617
[17]
B. Chandramouli, G. Prasaad, D. Kossmann, J. Levandoski, J. Hunter, and M. Barnett. 2018. FASTER: A Concurrent Key-Value Store with In-Place Updates. In SIGMOD. ACM, 275--290. https://doi.org/10.1145/3183713.3196898
[18]
G. A.Di Luna, E. Anceaume, and L. Querzoni. 2020. Byzantine Generalized Lattice Agreement. In IEEE IPDPS.
[19]
S. Duan, M. K. Reiter, and H. Zhang. 2017. Secure Causal Atomic Broadcast, Revisited. In 2017 47th Annual IEEE/IFIP International Conference on Dependable Systems and Networks. IEEE, 61--72. https://doi.org/10.1109/DSN.2017.64
[20]
Cloud Native Computing Foundation. 2023. gRPC, a High Performance, Open-Source Universal RPC Framework. https://grpc.io/ Accessed: 2023-10-10.
[21]
R.Friedman and K.Birman. 1996. Trading Consistency for Availability in Distributed Systems. Technical Report.
[22]
H. S. Galal and A. M. Youssef. 2019. Verifiable Sealed-Bid Auction on the Ethereum Blockchain. In Financial Cryptography and Data Security. Springer Berlin Heidelberg, 265--278.
[23]
S. Gilbert and N. Lynch. 2012. Perspectives on the CAP Theorem. Computer 45 (2012), 30--36. https://doi.org/10.1109/MC.2011.389
[24]
Google. 2021. LevelDB. https://github.com/google/leveldb Accessed: 2023-10-08.
[25]
C. Gorenflo, S. Lee, L. Golab, and S. Keshav. 2019. FastFabric: Scaling Hyperledger Fabric to 20,000 Transactions per Second. (2019), 455--463. https://doi.org/10.1109/BLOC.2019.8751452
[26]
G. Greenspan. 2015. Multichain Private Blockchainm White Paper. 57--60 pages. http://www.multichain.com/download/MultiChain-White-Paper.pdf Accessed: 2023-08-28.
[27]
R. Guerraoui, P. Kuznetsov, M. Monti, M. Pavlovič, and D.-A. Seredinschi. 2019. The Consensus Number of a Cryptocurrency. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. ACM, 307--316. https://doi.org/10.1145/3293611.3331589
[28]
M. Hearn and R. G. Brown. 2016. Corda: A Distributed Ledger. Corda Technical White Paper 2016 (2016).
[29]
J. M. Hellerstein. 2010. The Declarative Imperative: Experiences and Conjectures in Distributed Logic. SIGMOD Rec. (2010), 5--19. https://doi.org/10.1145/1860702.1860704
[30]
J. Huang, D. He, M. S. Obaidat, P. Vijayakumar, M. Luo, and Kim-Kwang R. Choo. 2021. The Application of the Blockchain Technology in Voting Systems: A Review. ACM Comput. Surv. (2021). https://doi.org/10.1145/3439725
[31]
M. Imam, S. Takiar, and J. Wang. 2017. RAMBLE: Reliable Asynchronous Messaging for Byzantine Linked Entities. (2017).
[32]
K. Jannes, B. Lagaisse, and W Joosen. 2021. OWebSync: Seamless Synchronization of Distributed Web Clients. IEEE Transactions on Parallel and Distributed Systems (2021), 2338--2351. https://doi.org/10.1109/TPDS.2021.3066276
[33]
T. Jungnickel and L. Oldenburg. 2017. Pluto: The CRDT-Driven IMAP Server. In Proceedings of the 3rd International Workshop on Principles and Practice of Consistency for Distributed Data. ACM. https://doi.org/10.1145/3064889.3064891
[34]
K. Karlsson, W. Jiang, S. Wicker, D. Adams, E. Ma, R. van Renesse, and H. Weather-spoon. 2018. Vegvisir: A Partition-Tolerant Blockchain for the Internet-of-Things. In 2018 IEEE 38th International Conference on Distributed Computing Systems. IEEE, 1150--1158. https://doi.org/10.1109/ICDCS.2018.00114
[35]
S. Kim, Y. Kwon, and S. Cho. 2018. A Survey of Scalability Solutions on Blockchain. In 2018 International Conference on Information and Communication Technology Convergence. 1204--1207. https://doi.org/10.1109/ICTC.2018.8539529
[36]
M. Kleppmann. 2020. Automerge, A JSON-like CRDT. https://github.com/automerge/automerge Accessed: 2023-10-11.
[37]
M. Kleppmann and A. R. Beresford. 2017. A Conflict-Free Replicated JSON Datatype. IEEE Transactions on Parallel and Distributed Systems (2017), 2733--2746. https://doi.org/10.1109/TPDS.2017.2697382
[38]
M. Kleppmann and H. Howard. 2020. Byzantine Eventual Consistency and the Fundamental Limits of Peer-to-Peer Databases. CoRR (2020). arXiv:2012.00472
[39]
M. Kleppmann, A. Wiggins, P. van Hardenberg, and M. McGranaghan. 2019. Local-First Software: You Own Your Data, in Spite of the Cloud. In Proceedings of the 2019 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software. ACM, 154--178. https://doi.org/10.1145/3359591.3359737
[40]
S. Laddad, C. Power, M. Milano, A. Cheung, and J. M. Hellerstein. 2022. Katara: Synthesizing CRDTs with Verified Lifting. Proc. ACM Program. Lang. (2022). https://doi.org/10.1145/3563336
[41]
L. Lamport. 1978. Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21, 7 (1978), 558--565. https://doi.org/10.1145/359545.359563
[42]
L. Lamport. 2005. Generalized Consensus and Paxos. (2005).
[43]
L. Lamport. 2006. Lower Bounds for Asynchronous Consensus. Distributed Computing (2006), 104--125. https://doi.org/10.1007/s00446-006-0155-x
[44]
C. Li, D. Porto, A. Clement, J. Gehrke, N. Preguiça, and R. Rodrigues. 2012. Making Geo-Replicated Systems Fast as Possible, Consistent When Necessary. In OSDI. USENIX Association, 265--278.
[45]
J. Liu, T. Magrino, O. Arden, M. D. George, and A. C. Myers. 2014. Warranties for Faster Strong Consistency. In USENIX NSDI. USENIX Association, 503--517.
[46]
W. Lloyd, M.J. Freedman, M. Kaminsky, and D. G. Andersen. 2011. Don't Settle for Eventual: Scalable Causal Consistency for Wide-Area Storage with COPS. In Proceedings of the Twenty-Third ACM Symposium on Operating Systems Principles. ACM, 401--416. https://doi.org/10.1145/2043556.2043593
[47]
Y.Mao, Z.Liu, and H.-A. Jacobsen. 2022. Reversible Conflict-Free Replicated Data Types. In Proceedings of the 23rd ACM/IFIP International Middleware Conference. ACM, 295--307. https://doi.org/10.1145/3528535.3565252
[48]
J.-P. Martin and L. Alvisi. 2006. Fast Byzantine Consensus. (2006), 402--411. https://doi.org/10.1109/DSN.2005.48
[49]
U. Maurer. 1996. Modelling a Public-Key Infrastructure. In European Symposium on Research in Computer Security. Springer, 325--350.
[50]
D. Mealha, N. Preguiça, M. C. Gomes, and J. Leitão. 2019. Data Replication on the Cloud/Edge. In Proceedings of the 6th Workshop on Principles and Practice of Consistency for Distributed Data. ACM. https://doi.org/10.1145/3301419.3323973
[51]
J. P. Morgan Chase. 2018. A Permissioned Implementation of Ethereum. https://github.com/ConsenSys/quorum Accessed: 2023-10-08.
[52]
M. Najafzadeh, M. Shapiro, and P. Eugster. 2018. Co-Design and Verification of an Available File System. In Verification, Model Checking, and Abstract Interpretation. Springer International Publishing, 358--381.
[53]
S. Nakamoto. 2008. Bitcoin: A Peer-to-Peer Electronic Cash System.
[54]
P. Nasirifard, R. Mayer, and H.-A. Jacobsen. 2019. FabricCRDT: A Conflict-Free Replicated Datatypes Approach to Permissioned Blockchains. In Proceedings of the 20th International Middleware Conference. ACM, 110--122. https://doi.org/10.1145/3361525.3361540
[55]
P. Nasirifard, R. Mayer, and H.-A. Jacobsen. 2022. OrderlessChain: A CRDT-Enabled Blockchain without Total Global Order of Transactions: Poster Abstract. In Proceedings of the 23rd International Middleware Conference Demos and Posters. ACM, 5--6. https://doi.org/10.1145/3565386.3565486
[56]
P. Nasirifard, R. Mayer, and H.-A. Jacobsen. 2022. OrderlessFile: A CRDT-Enabled Permissioned Blockchain for File Storage: Poster Abstract. In Proceedings of the 23rd International Middleware Conference Demos and Posters. ACM, 15--16. https://doi.org/10.1145/3565386.3565491
[57]
P. Nasirifard, R. Mayer, and H.-A. Jacobsen. 2022. OrderlessFL: A CRDT-Enabled Permissioned Blockchain for Federated Learning: Poster Abstract. In Proceedings of the 23rd International Middleware Conference Demos and Posters. ACM, 7--8. https://doi.org/10.1145/3565386.3565487
[58]
P. Nicolaescu, K.Jahns, M. Derntl, and R. Klamma. 2016. Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types. In Proceedings of the 2016 ACM International Conference on Supporting Group Work. ACM, 39--49. https://doi.org/10.1145/2957276.2957310
[59]
D. Ongaro and J. Ousterhout. 2014. In Search of an Understandable Consensus Algorithm. In 2014 USENIX Annual Technical Conference. USENIX Association, 305--319.
[60]
Oracle. 2021. Read-Your-Writes Consistency. https://bit.ly/3dIAXOp Accessed: 2023-09-20.
[61]
P. E. O'Neil. 1986. The Escrow Transactional Method. ACM Trans. Database Syst. (1986), 405--430. https://doi.org/10.1145/7239.7265
[62]
F. Pedone and A. Schiper. 1999. Generic Broadcast. In Distributed Computing. Springer-Verlag, 94--108.
[63]
M. Pires, S. Ravi, and R. Rodrigues. 2017. Generalized Paxos Made Byzantine (and Less Complex). In Stabilization, Safety, and Security of Distributed Systems. Springer International Publishing, 203--218.
[64]
N. Preguiça. 2018. Conflict-free Replicated Data Types: An Overview. arXiv:1806.10254
[65]
Hyperledger Project. 2023. Hyperledger Caliper. https://hyperledger.github.io/caliper/ Accessed: 2023-10-02.
[66]
J. Qi, X. Chen, Y. Jiang, J. Jiang, T. Shen, S. Zhao, S. Wang, G. Zhang, L. Chen, M. H. Au, and H. Cui. 2021. BIDL: AHigh-Throughput, Low-Latency Permissioned Blockchain Frame work for Datacenter Networks. In Proceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles. ACM, 18--34. https://doi.org/10.1145/3477132.3483574
[67]
P. Raykov, N. Schiper, and F. Pedone. 2011. Byzantine Fault-Tolerance with Commutative Commands. In Principles of Distributed Systems. 329--342.
[68]
L. S. Sankar, M. Sindhu, and M. Sethumadhavan. 2017. Survey of Consensus Protocols on Blockchain Applications. In 2017 4th International Conference on Advanced Computing and Communication Systems. 1--5. https://doi.org/10.1109/ICACCS.2017.8014672
[69]
M. Shapiro, A. Bieniusa, N. M. Preguiça, V. Balegas, and C. Meiklejohn. 2018. Just-Right Consistency: Reconciling Availability and Safety. CoRR (2018). arXiv:1801.06340
[70]
M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. 2011. Conflict-Free Replicated Data Types. In Symposium on Self-Stabilizing Systems. Springer, 386--400.
[71]
A. Sharma, F. M. Schuhknecht, D. Agrawal, and J. Dittrich. 2019. Blurring the Lines Between Blockchains and Database Systems: The Case of Hyperledger Fabric. In Proceedings of the 2019 International Conference on Management of Data. ACM, 105--122. https://doi.org/10.1145/3299869.3319883
[72]
A. Shoker, H. Yactine, and C. Baquero. 2017. As Secure as Possible Eventual Consistency: Work in Progress. In Proceedings of the 3rd International Workshop on Principles and Practice of Consistency for Distributed Data. ACM. https://doi.org/10.1145/3064889.3064895
[73]
D. Sun, S. Xia, C. Sun, andD. Chen. 2004. Operational Transformation for Collaborative Word Processing. In Proceedings of the 2004 ACM Conference on Computer Supported Cooperative Work. ACM, 437--446. https://doi.org/10.1145/1031607.1031681
[74]
V. Tao, M. Shapiro, and V. Rancurel. 2015. Merging Semantics for Conflict Updates in Geo-Distributed File Systems. In Proceedings of the 8th ACM International Systems and Storage Conference. ACM. https://doi.org/10.1145/2757667.2757683
[75]
A. van der Linde, P. Fouto, J. Leitão, N. Preguiça, S. Castiñeira, and A. Bieniusa. 2017. Legion: Enriching Internet Services with Peer-to-Peer Interactions. In Proceedings of the 26th International Conference on World Wide Web. ACM. https://doi.org/10.1145/3038912.3052673
[76]
P. van Hardenberg and M. Kleppmann. 2020. PushPin: Towards Production-Quality Peer-to-Peer Collaboration. In Proceedings of the 7th Workshop on Principles and Practice of Consistency for Distributed Data. ACM. https://doi.org/10.1145/3380787.3393683
[77]
S. Weiss, P. Urso, and P. Molli. 2009. Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks. In 2009 29th IEEE International Conference on Distributed Computing Systems. IEEE, 404--412. https://doi.org/10.1109/ICDCS.2009.75
[78]
M. Whittaker and J. M. Hellerstein. 2020. Checking Invariant Confluence, In Whole or In Parts. SIGMOD (2020), 7--14. https://doi.org/10.1145/3422648.3422651
[79]
H. Y. Wu, L. Jie Li, H.-Y. Paik, and S. S. Kanhere. 2021. MEChain: A Multi-layer Blockchain Structure with Hierarchical Consensus for Secure EHR System. In 2021 IEEE 20th International Conference on Trust, Security and Privacy in Computing and Communications. IEEE, 976--987. https://doi.org/10.1109/TrustCom53373.2021.00136
[80]
M. Yin, D. Malkhi, M. K. Reiter, G. G. Gueta, and I. Abraham. 2019. HotStuff: BFT Consensus with Linearity and Responsiveness. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing. ACM, 347--356. https://doi.org/10.1145/3293611.3331591
[81]
G. Younes, A. Shoker, P. S. Almeida, and C. Baquero. 2016. Integration Challenges of Pure Operation-based CRDTs in Redis. In First Workshop on Programming Models and Languages for Distributed Computing. ACM, 7:1--7:4. https://doi.org/10.1145/2957319.2957375
[82]
M. Zawirski, N. Preguiça, S. Duarte, A. Bieniusa, V. Balegas, and M. Shapiro. 2015. Write Fast, Read in the Past: Causal Consistency for Client-Side Applications. In Proceedings of the 16th Annual Middleware Conference. ACM, 75--87. https://doi.org/10.1145/2814576.2814733
[83]
W. Zhao, M. Babi, W. Yang, X. Luo, Y. Zhu, J. Yang, C. Luo, and Mary Y. 2016. Byzantine Fault Tolerance for Collaborative Editing with Commutative Operations. In 2016 IEEE International Conference on Electro Information Technology. IEEE, 246--251. https://doi.org/10.1109/EIT.2016.7535248
Index Terms
- OrderlessChain: A CRDT-based BFT Coordination-free Blockchain Without Global Order of Transactions
Recommendations
Making CRDTs Byzantine fault tolerant
PaPoC '22: Proceedings of the 9th Workshop on Principles and Practice of Consistency for Distributed DataIt is often claimed that Conflict-free Replicated Data Types (CRDTs) ensure consistency of replicated data in peer-to-peer systems. However, peer-to-peer systems usually consist of untrusted nodes that may deviate from the specified protocol (i.e. ...
OrderlessChain: a CRDT-enabled blockchain without total global order of transactions: poster abstract
Middleware Demos and Posters '22: Proceedings of the 23rd International Middleware Conference Demos and PostersBlockchains often use coordination-based consensus protocols to offer trust in a Byzantine environment and to serialize transactions to preserve the application's invariants. However, coordination can be a performance bottleneck. There exist application-...
MBFT: A Modular Byzantine Fault Tolerance Protocol for high adaptability
AbstractWith the substantial increase in permissioned blockchain applications, various application scenarios for Byzantine Fault Tolerance (BFT) protocols are emerging. However, due to the inherent complexity of BFT, the performance improvement of BFT ...
Highlights- Modular methods be utilized to quickly construct satisfactory BFT protocols.
- Deconstruct the single-layer leader-based BFT protocol into three phases.
- Two typical modules with different characteristics were provided for each phase.
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2023
334 pages
ISBN:9798400701771
DOI:10.1145/3590140
Copyright © 2023 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 the author(s) 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
- IFIP: International Federation for Information Processing
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 27 November 2023
Check for updates
Badges
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
Middleware '23
Sponsor:
Acceptance Rates
Overall Acceptance Rate 203 of 948 submissions, 21%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 270Total Downloads
- Downloads (Last 12 months)189
- Downloads (Last 6 weeks)23
Reflects downloads up to 17 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in