{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,31]],"date-time":"2025-03-31T22:27:18Z","timestamp":1743460038349},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T00:00:00Z","timestamp":1714608000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T00:00:00Z","timestamp":1714608000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Supercomput"],"published-print":{"date-parts":[[2024,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Blockchain received a vast amount of attention in recent years and is still growing. The second generation of blockchain, such as Ethereum, allows execution of almost any program in EVM, making it a global protocol for distributed applications. The code deployment and each operation performed in EVM cost the network fee called gas, whose price varies and can be significant. That is why code optimization and well-chosen algorithms are crucial in programming on the blockchain. This paper evaluates the gas usage of several exact pattern matching algorithms on the EVM. We also propose an efficient implementation of the algorithms in the Solidity\/YUL language. We evaluate the gas fees of all the algorithms for different parameters (such as pattern length, alphabet size, and text size). We show a significant gas fee and execution time reduction with up to 22-fold lower gas usage and 55-fold speed-up compared to StringUtils (a popular Solidity string library).<\/jats:p>","DOI":"10.1007\/s11227-024-06115-8","type":"journal-article","created":{"date-parts":[[2024,5,2]],"date-time":"2024-05-02T06:01:41Z","timestamp":1714629701000},"page":"17741-17759","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Pattern matching algorithms in blockchain for network fees reduction"],"prefix":"10.1007","volume":"80","author":[{"given":"Robert","family":"Susik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Nowotniak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,2]]},"reference":[{"key":"6115_CR1","unstructured":"Nakamoto S (2008) Bitcoin: a peer-to-peer electronic cash system. https:\/\/bitcoin.org\/bitcoin.pdf. Accessed 15 Apr 2022"},{"key":"6115_CR2","first-page":"6719","volume":"34","author":"AG Gad","year":"2022","unstructured":"Gad AG, Mosa DT, Abualigah L, Abohany AA (2022) Emerging trends in blockchain technology and applications: a review and outlook. J King Saud Univ-Comput Inf Sci 34:6719\u20136742","journal-title":"J King Saud Univ-Comput Inf Sci"},{"key":"6115_CR3","unstructured":"Buterin V (2013) Ethereum white paper: a next generation smart contract & decentralized application platform. https:\/\/ethereum.org\/en\/whitepaper. Accessed 15 Apr 2022"},{"key":"6115_CR4","doi-asserted-by":"publisher","DOI":"10.1016\/j.bcra.2022.100067","volume":"3","author":"H Guo","year":"2022","unstructured":"Guo H, Yu X (2022) A survey on blockchain technology and its security. Blockchain Res Appl 3:100067","journal-title":"Blockchain Res Appl"},{"issue":"345\u2013363","key":"6115_CR5","first-page":"5","volume":"58","author":"AM Turing","year":"1936","unstructured":"Turing AM (1936) On computable numbers, with an application to the entscheidungsproblem. J Math 58(345\u2013363):5","journal-title":"J Math"},{"issue":"2","key":"6115_CR6","first-page":"28","volume":"18","author":"N Szabo","year":"1996","unstructured":"Szabo N (1996) Smart contracts: building blocks for digital markets. EXTROPY J Transhumanist Thought (16) 18(2):28","journal-title":"EXTROPY J Transhumanist Thought (16)"},{"key":"6115_CR7","unstructured":"Wu K (2019) An empirical study of blockchain-based decentralized applications. arXiv preprint arXiv:1902.04969"},{"key":"6115_CR8","doi-asserted-by":"publisher","first-page":"118433","DOI":"10.1109\/ACCESS.2020.3004790","volume":"8","author":"A Kumar","year":"2020","unstructured":"Kumar A, Krishnamurthi R, Nayyar A, Sharma K, Grover V, Hossain E (2020) A novel smart healthcare design, simulation, and implementation using healthcare 4.0 processes. IEEE Access 8:118433\u2013118471","journal-title":"IEEE Access"},{"key":"6115_CR9","doi-asserted-by":"publisher","first-page":"100139","DOI":"10.1016\/j.array.2022.100139","volume":"14","author":"EM Adere","year":"2022","unstructured":"Adere EM (2022) Blockchain in healthcare and IoT: a systematic literature review. Array 14:100139","journal-title":"Array"},{"key":"6115_CR10","doi-asserted-by":"crossref","unstructured":"Sober M, Scaffino G, Spanring C, Schulte S (2021) A voting-based blockchain interoperability oracle. In: 2021 IEEE International Conference on Blockchain (Blockchain). IEEE, pp 160\u2013169","DOI":"10.1109\/Blockchain53845.2021.00030"},{"issue":"6","key":"6115_CR11","doi-asserted-by":"publisher","first-page":"4157","DOI":"10.1109\/JIOT.2020.3028368","volume":"8","author":"MB Mollah","year":"2020","unstructured":"Mollah MB, Zhao J, Niyato D, Guan YL, Yuen C, Sun S, Lam K-Y, Koh LH (2020) Blockchain for the internet of vehicles towards intelligent transportation systems: a survey. IEEE Internet Things J 8(6):4157\u20134185","journal-title":"IEEE Internet Things J"},{"key":"6115_CR12","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1016\/j.procs.2021.04.084","volume":"187","author":"Y Li","year":"2021","unstructured":"Li Y, Wei J, Yuan J, Xu Q, He C (2021) A decentralized music copyright operation management system based on blockchain technology. Procedia Comput Sci 187:458\u2013463","journal-title":"Procedia Comput Sci"},{"key":"6115_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tifs.2022.03.030","volume":"124","author":"Y Zhang","year":"2022","unstructured":"Zhang Y, Chen L, Battino M, Farag MA, Xiao J, Simal-Gandara J, Gao H, Jiang W (2022) Blockchain: an emerging novel technology to upgrade the current fresh fruit supply chain. Trends Food Sci Technol 124:1\u201312","journal-title":"Trends Food Sci Technol"},{"key":"6115_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jnca.2020.102814","volume":"170","author":"AS Almasoud","year":"2020","unstructured":"Almasoud AS, Hussain FK, Hussain OK (2020) Smart contracts for blockchain-based reputation systems: a systematic literature review. J Netw Comput Appl 170:102814","journal-title":"J Netw Comput Appl"},{"key":"6115_CR15","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/j.compeleceng.2019.03.014","volume":"76","author":"N Nizamuddin","year":"2019","unstructured":"Nizamuddin N, Salah K, Azad MA, Arshad J, Rehman M (2019) Decentralized document version control using ethereum blockchain and ipfs. Comput Electr Eng 76:183\u2013197","journal-title":"Comput Electr Eng"},{"key":"6115_CR16","doi-asserted-by":"crossref","unstructured":"Amler H, Eckey L, Faust S, Kaiser M, Sandner P, Schlosser B (2021) Defi-ning defi: challenges & pathway. In: 2021 3rd Conference on Blockchain Research & Applications for Innovative Networks and Services (BRAINS). IEEE, pp 181\u2013184","DOI":"10.1109\/BRAINS52497.2021.9569795"},{"issue":"8","key":"6115_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3471140","volume":"54","author":"R Belchior","year":"2021","unstructured":"Belchior R, Vasconcelos A, Guerreiro S, Correia M (2021) A survey on blockchain interoperability: past, present, and future trends. ACM Comput Surv (CSUR) 54(8):1\u201341","journal-title":"ACM Comput Surv (CSUR)"},{"key":"6115_CR18","doi-asserted-by":"crossref","unstructured":"Marchesi L, Marchesi M, Destefanis G, Barabino G, Tigano D (2020) Design patterns for gas optimization in ethereum. In: 2020 IEEE International Workshop on Blockchain Oriented Software Engineering (IWBOSE). IEEE, pp 9\u201315","DOI":"10.1109\/IWBOSE50093.2020.9050163"},{"key":"6115_CR19","doi-asserted-by":"crossref","unstructured":"Mars R, Abid A, Cheikhrouhou S, Kallel S (2021) A machine learning approach for gas price prediction in ethereum blockchain. In: 2021 IEEE 45th Annual Computers, Software, and Applications Conference (COMPSAC). IEEE, pp 156\u2013165","DOI":"10.1109\/COMPSAC51774.2021.00033"},{"key":"6115_CR20","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2021.115480","volume":"184","author":"H-M Kim","year":"2021","unstructured":"Kim H-M, Bock G-W, Lee G (2021) Predicting ethereum prices with machine learning based on blockchain information. Expert Syst Appl 184:115480","journal-title":"Expert Syst Appl"},{"key":"6115_CR21","unstructured":"King S, Nadal S (2012) Ppcoin: peer-to-peer crypto-currency with proof-of-stake. Self-published paper, August 19(1)"},{"issue":"11","key":"6115_CR22","doi-asserted-by":"publisher","first-page":"3423","DOI":"10.1080\/00207543.2020.1754487","volume":"58","author":"A Jabbar","year":"2020","unstructured":"Jabbar A, Dani S (2020) Investigating the link between transaction and computational costs in a blockchain environment. Int J Prod Res 58(11):3423\u20133436","journal-title":"Int J Prod Res"},{"key":"6115_CR23","doi-asserted-by":"publisher","first-page":"142","DOI":"10.1016\/j.future.2021.09.021","volume":"128","author":"GA Pierro","year":"2022","unstructured":"Pierro GA, Rocha H, Ducasse S, Marchesi M, Tonelli R (2022) A user-oriented model for oracles\u2019 gas price prediction. Future Gener Comput Syst 128:142\u2013157","journal-title":"Future Gener Comput Syst"},{"key":"6115_CR24","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1109\/OJCS.2020.3039991","volume":"1","author":"C Li","year":"2020","unstructured":"Li C, Nie S, Cao Y, Yu Y, Hu Z (2020) Trace-based dynamic gas estimation of loops in smart contracts. IEEE Open J Comput Soc 1:295\u2013306","journal-title":"IEEE Open J Comput Soc"},{"key":"6115_CR25","doi-asserted-by":"publisher","DOI":"10.1016\/j.jss.2021.111193","volume":"186","author":"A Di Sorbo","year":"2022","unstructured":"Di Sorbo A, Laudanna S, Vacca A, Visaggio CA, Canfora G (2022) Profiling gas consumption in solidity smart contracts. J Syst Softw 186:111193","journal-title":"J Syst Softw"},{"issue":"4","key":"6115_CR26","doi-asserted-by":"publisher","first-page":"6679","DOI":"10.1002\/cpe.6679","volume":"34","author":"MMA Khan","year":"2022","unstructured":"Khan MMA, Sarwar HMA, Awais M (2022) Gas consumption analysis of ethereum blockchain transactions. Concurr Comput Pract Exp 34(4):6679","journal-title":"Concurr Comput Pract Exp"},{"key":"6115_CR27","volume-title":"Handbook of exact string matching algorithms","author":"C Charras","year":"2004","unstructured":"Charras C, Lecroq T (2004) Handbook of exact string matching algorithms. King\u2019s College, London"},{"key":"6115_CR28","unstructured":"Grabowski S (2009) New algorithms for exact and approximate text matching. Technical University of Lodz Publisher"},{"key":"6115_CR29","doi-asserted-by":"publisher","DOI":"10.1145\/2431211.2431212","author":"S Faro","year":"2013","unstructured":"Faro S, Lecroq T (2013) The exact online string matching problem: a review of the most recent results. ACM Comput Surv (CSUR). https:\/\/doi.org\/10.1145\/2431211.2431212","journal-title":"ACM Comput Surv (CSUR)"},{"issue":"11","key":"6115_CR30","doi-asserted-by":"publisher","first-page":"1221","DOI":"10.1002\/spe.4380211105","volume":"21","author":"A Hume","year":"1991","unstructured":"Hume A, Sunday D (1991) Fast string searching. Softw Pract Exp 21(11):1221\u20131248","journal-title":"Softw Pract Exp"},{"issue":"1","key":"6115_CR31","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth DE, Morris JH, Pratt VR (1977) Fast pattern matching in strings. SIAM J Comput 6(1):323\u2013350","journal-title":"SIAM J Comput"},{"issue":"6","key":"6115_CR32","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1002\/spe.4380100608","volume":"10","author":"RN Horspool","year":"1980","unstructured":"Horspool RN (1980) Practical fast searching in strings. Softw Pract Exp 10(6):501\u2013506","journal-title":"Softw Pract Exp"},{"issue":"10","key":"6115_CR33","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"RS Boyer","year":"1977","unstructured":"Boyer RS, Moore JS (1977) A fast string searching algorithm. Commun ACM 20(10):762\u2013772","journal-title":"Commun ACM"},{"issue":"2","key":"6115_CR34","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"RM Karp","year":"1987","unstructured":"Karp RM, Rabin MO (1987) Efficient randomized pattern-matching algorithms. IBM J Res Dev 31(2):249\u2013260","journal-title":"IBM J Res Dev"},{"issue":"10","key":"6115_CR35","doi-asserted-by":"publisher","first-page":"74","DOI":"10.1145\/135239.135243","volume":"35","author":"RA Baeza-Yates","year":"1992","unstructured":"Baeza-Yates RA, Gonnet GH (1992) A new approach to text searching. Commun ACM 35(10):74\u201382","journal-title":"Commun ACM"},{"issue":"2","key":"6115_CR36","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1147\/rd.32.0114","volume":"3","author":"MO Rabin","year":"1959","unstructured":"Rabin MO, Scott D (1959) Finite automata and their decision problems. IBM J Res Dev 3(2):114\u2013125","journal-title":"IBM J Res Dev"},{"issue":"4","key":"6115_CR37","doi-asserted-by":"publisher","first-page":"937","DOI":"10.31577\/cai_2019_4_937","volume":"38","author":"R Susik","year":"2019","unstructured":"Susik R, Grabowski S, Fredriksson K (2019) Revisiting multiple pattern matching. Comput Inform 38(4):937\u2013962","journal-title":"Comput Inform"},{"key":"6115_CR38","doi-asserted-by":"crossref","unstructured":"Brisaboa N, Iglesias E, Navarro G, Param\u00e1 JL (2003) An efficient compression code for text databases. In: Proceedings of 25th European Conference on Information Retrieval Research (ECIR\u201903). LNCS 2633. Springer, Berlin, pp 468\u2013481","DOI":"10.1007\/3-540-36618-0_33"},{"key":"6115_CR39","doi-asserted-by":"crossref","unstructured":"Susik R, Grabowski S, Deorowicz S (2014) Fast and simple circular pattern matching. In: Man\u2013Machine Interactions, vol 3. Springer, pp 537\u2013544","DOI":"10.1007\/978-3-319-02309-0_59"},{"key":"6115_CR40","doi-asserted-by":"crossref","unstructured":"Navarro G, Raffinot M (1998) A bit-parallel approach to suffix automata: fast extended string matching. In: Proceedings of Annual Symposium on Combinatorial Pattern Matching (CPM). Springer, Berlin, pp 14\u201333","DOI":"10.1007\/BFb0030778"},{"key":"6115_CR41","unstructured":"StringUtils. https:\/\/github.com\/Arachnid\/solidity-stringutils. Accessed 15 Apr 2022"},{"key":"6115_CR42","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4842-3492-1","volume-title":"Building games with ethereum smart contracts","author":"K Iyer","year":"2018","unstructured":"Iyer K, Dannen C (2018) Building games with ethereum smart contracts. Springer, Berlin"}],"container-title":["The Journal of Supercomputing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-024-06115-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11227-024-06115-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11227-024-06115-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T12:19:29Z","timestamp":1720441169000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11227-024-06115-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,2]]},"references-count":42,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2024,8]]}},"alternative-id":["6115"],"URL":"https:\/\/doi.org\/10.1007\/s11227-024-06115-8","relation":{},"ISSN":["0920-8542","1573-0484"],"issn-type":[{"value":"0920-8542","type":"print"},{"value":"1573-0484","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,2]]},"assertion":[{"value":"28 March 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Ethical approval"}}]}}