{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T17:33:55Z","timestamp":1770744835034,"version":"3.49.0"},"reference-count":67,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T00:00:00Z","timestamp":1734566400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T00:00:00Z","timestamp":1734566400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006115","name":"Institute for Research in Fundamental Sciences","doi-asserted-by":"publisher","award":["CS1401-4-201"],"award-info":[{"award-number":["CS1401-4-201"]}],"id":[{"id":"10.13039\/501100006115","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Hong Kong Research Grants Council","award":["26208122"],"award-info":[{"award-number":["26208122"]}]},{"DOI":"10.13039\/501100005950","name":"Hong Kong University of Science and Technology","doi-asserted-by":"publisher","award":["HKJRI3A-055"],"award-info":[{"award-number":["HKJRI3A-055"]}],"id":[{"id":"10.13039\/501100005950","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005950","name":"Hong Kong University of Science and Technology","doi-asserted-by":"publisher","award":["R9272"],"award-info":[{"award-number":["R9272"]}],"id":[{"id":"10.13039\/501100005950","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100015595","name":"Ethereum Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100015595","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005950","name":"Hong Kong University of Science and Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100005950","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2025,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In this work, we consider a combinatorial optimization problem with direct applications in blockchain mining, namely finding the most lucrative blocks for Bitcoin miners, and propose optimal algorithmic solutions. Our experiments show that our algorithms increase the miners\u2019 revenues by more than a million dollars per month. Modern blockchains reward their miners in two ways: (i)\u00a0a base reward for each block that is mined, and (ii)\u00a0the transaction fees of those transactions that are included in the mined block. The base reward is fixed by the respective blockchain\u2019s protocol and is not under the miner\u2019s control. Hence, for a miner who wishes to maximize earnings, the fundamental problem is to form a valid block with maximal total transaction fees and then try to mine it. Moreover, in many protocols, including Bitcoin itself, the base reward halves at predetermined intervals, hence increasing the importance of maximizing transaction fees and mining an optimal block. This problem is further complicated by the fact that transactions can be prerequisites of each other or have conflicts (in case of double-spending). In this work, we consider the problem of forming an optimal block, i.e.\u00a0a valid block with maximal total transaction fees, given a set of unmined transactions. On the theoretical side, we first formally model our problem as an extension of <jats:sc>Knapsack<\/jats:sc> and then show that, unlike classical <jats:sc>Knapsack<\/jats:sc>, our problem is strongly NP-hard. We also show a hardness-of-approximation result. As such, there is no hope in solving it efficiently for general instances. However, we observe that its real-world instances are quite sparse, i.e.\u00a0the transactions have very few dependencies and conflicts. Using this fact, and exploiting three well-known graph sparsity parameters, namely treedepth, treewidth and pathwidth, we present exact linear-time parameterized algorithms that are applicable to the real-world instances and obtain optimal results. On the practical side, we provide an extensive experimental evaluation demonstrating that our approach vastly outperforms the current Bitcoin miners in practice, obtaining a significant per-block average increase of 11.34 percent in transaction fee revenues which amounts to almost one million dollars per month.\n<\/jats:p>","DOI":"10.1007\/s10878-024-01249-0","type":"journal-article","created":{"date-parts":[[2024,12,19]],"date-time":"2024-12-19T19:33:52Z","timestamp":1734636832000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Optimal blocks for maximizing the transaction fee revenue of Bitcoin miners"],"prefix":"10.1007","volume":"49","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2089-0250","authenticated-orcid":false,"given":"Mohsen","family":"Alambardar Meybodi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1702-6584","authenticated-orcid":false,"given":"Amir","family":"Goharshady","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3834-3610","authenticated-orcid":false,"given":"Mohammad Reza","family":"Hooshmandasl","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2253-1166","authenticated-orcid":false,"given":"Ali","family":"Shakiba","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,12,19]]},"reference":[{"key":"1249_CR1","doi-asserted-by":"crossref","unstructured":"Ahmadi A, Daliri M, Goharshady AK, Pavlogiannis A (2022) Efficient approximations for cache-conscious data placement. In: PLDI, pp 857\u2013871","DOI":"10.1145\/3519939.3523436"},{"key":"1249_CR2","doi-asserted-by":"publisher","DOI":"10.1016\/j.frl.2024.105057","volume":"61","author":"J An","year":"2024","unstructured":"An J, Mikhaylov A, Chang T (2024) Relationship between the popularity of a platform and the price of NFT assets. Financ Res Lett 61:105057","journal-title":"Financ Res Lett"},{"key":"1249_CR3","doi-asserted-by":"publisher","first-page":"2491","DOI":"10.3390\/en13102491","volume":"13","author":"J An","year":"2020","unstructured":"An J, Mikhaylov A, Jung S-U (2020) The strategy of South Korea in the global oil market. Energies 13:2491","journal-title":"Energies"},{"key":"1249_CR4","volume-title":"Mastering ethereum: building smart contracts and dapps","author":"AM Antonopoulos","year":"2018","unstructured":"Antonopoulos AM, Wood G (2018) Mastering ethereum: building smart contracts and dapps. O\u2019reilly Media"},{"key":"1249_CR5","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1137\/0608024","volume":"8","author":"S Arnborg","year":"1987","unstructured":"Arnborg S, Corneil DG, Proskurowski A (1987) Complexity of finding embeddings in a k-tree. SIAM J Algebr Discret Methods 8:277\u2013284","journal-title":"SIAM J Algebr Discret Methods"},{"key":"1249_CR6","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora S, Lund C, Motwani R, Sudan M, Szegedy M (1998) Proof verification and the hardness of approximation problems. J ACM 45:501\u2013555","journal-title":"J ACM"},{"key":"1249_CR7","first-page":"253","volume":"2020","author":"A Asadi","year":"2020","unstructured":"Asadi A, Chatterjee K, Goharshady AK, Mohammadi K, Pavlogiannis A (2020) Faster algorithms for quantitative analysis of MCs and MDPs with small treewidth. ATVA 2020:253\u2013270","journal-title":"ATVA"},{"key":"1249_CR8","doi-asserted-by":"publisher","first-page":"484","DOI":"10.1007\/BF01934264","volume":"34","author":"B Aspvall","year":"1994","unstructured":"Aspvall B, Heggernes P (1994) Finding minimum height elimination trees for interval graphs in polynomial time. BIT Numer Math 34:484\u2013509","journal-title":"BIT Numer Math"},{"key":"1249_CR9","doi-asserted-by":"crossref","unstructured":"Baz\u00e1n-Palomino W (2020) How are Bitcoin forks related to Bitcoin?. Financ Res Lett 101723","DOI":"10.1016\/j.frl.2020.101723"},{"key":"1249_CR10","doi-asserted-by":"crossref","unstructured":"Bhaskar ND, Chuen DLK (2015) Bitcoin mining technology. In: Handbook of digital currency. Elsevier, pp 45\u201365","DOI":"10.1016\/B978-0-12-802117-0.00003-5"},{"key":"1249_CR11","unstructured":"Blockstream Corporation Inc, Esplora block explorer (2021). https:\/\/github.com\/Blockstream\/esplora"},{"key":"1249_CR12","doi-asserted-by":"crossref","unstructured":"Bodlaender HL (1988) Dynamic programming on graphs with bounded treewidth. In: ICALP, pp 105\u2013118","DOI":"10.1007\/3-540-19488-6_110"},{"key":"1249_CR13","doi-asserted-by":"publisher","first-page":"1305","DOI":"10.1137\/S0097539793251219","volume":"25","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender HL (1996) A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J Comput 25:1305\u20131317","journal-title":"SIAM J Comput"},{"key":"1249_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender HL (1998) A partial k-arboretum of graphs with bounded treewidth. Theor Comput Sci 209:1\u201345","journal-title":"Theor Comput Sci"},{"key":"1249_CR15","doi-asserted-by":"publisher","first-page":"358","DOI":"10.1006\/jagm.1996.0049","volume":"21","author":"HL Bodlaender","year":"1996","unstructured":"Bodlaender HL, Kloks T (1996) Efficient and constructive algorithms for the pathwidth and treewidth of graphs. J Algorithms 21:358\u2013402","journal-title":"J Algorithms"},{"key":"1249_CR16","unstructured":"Bonneau J (2014) Bitcoin mining is NP-hard, tech. report. https:\/\/freedom-to-tinker.com\/2014\/10\/27\/bitcoin-mining-is-np-hard\/"},{"key":"1249_CR17","doi-asserted-by":"crossref","unstructured":"Cai X, Goharshady AK (2024) Faster lifetime-optimal speculative partial redundancy elimination for goto-free programs. In: SETTA","DOI":"10.1007\/978-981-96-0602-3_21"},{"key":"1249_CR18","unstructured":"Cai X, Goharshady AK, Hitarth S, Lam CK (2025) Faster register allocation via grammatical decompositions of control-flow graphs. In: ASPLOS"},{"key":"1249_CR19","doi-asserted-by":"crossref","unstructured":"Chatterjee K, Goharshady AK, Goharshady EK (2019) The treewidth of smart contracts. In: SAC, pp 400\u2013408","DOI":"10.1145\/3297280.3297322"},{"key":"1249_CR20","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/3363525","volume":"41","author":"K Chatterjee","year":"2019","unstructured":"Chatterjee K, Goharshady AK, Goyal P, Ibsen-Jensen R, Pavlogiannis A (2019) Faster algorithms for dynamic algebraic queries in basic RSMs with constant treewidth. ACM Trans Program Lang Syst 41:23:1-23:46","journal-title":"ACM Trans Program Lang Syst"},{"key":"1249_CR21","doi-asserted-by":"crossref","unstructured":"Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A (2016) Algorithms for algebraic path properties in concurrent systems of constant treewidth components. In: POPL, pp 733\u2013747","DOI":"10.1145\/2837614.2837624"},{"key":"1249_CR22","doi-asserted-by":"crossref","unstructured":"Chatterjee K, Goharshady AK, Ibsen-Jensen R, Pavlogiannis A (2020) Optimal and perfectly parallel algorithms for on-demand data-flow analysis. In: ESOP, pp 112\u2013140","DOI":"10.1007\/978-3-030-44914-8_5"},{"key":"1249_CR23","unstructured":"Chatterjee K, Goharshady AK, Ibsen-Jensen R, Velner Y (2018) Ergodic mean-payoff games for the analysis of attacks in crypto-currencies. In: CONCUR"},{"key":"1249_CR24","doi-asserted-by":"crossref","unstructured":"Chatterjee K, Goharshady AK, Okati N, Pavlogiannis A (2019) Efficient parameterized algorithms for data packing. In: POPL, pp 53:1\u201353:28","DOI":"10.1145\/3290366"},{"key":"1249_CR25","unstructured":"Cohen B, Pietrzak K (2019) The Chia network blockchain. https:\/\/www.chia.net\/assets\/ChiaGreenPaper.pdf"},{"key":"1249_CR26","unstructured":"Conrado GK, Goharshady AK, Hudec P, Li P, Motwani HJ (2024) Faster treewidth-based approximations for Wiener index. In: SEA"},{"key":"1249_CR27","doi-asserted-by":"publisher","first-page":"1993","DOI":"10.1145\/3622868","volume":"7","author":"GK Conrado","year":"2023","unstructured":"Conrado GK, Goharshady AK, Kochekov K, Tsai YC, Zaher AK (2023) Exploiting the sparseness of control-flow and call graphs for efficient and on-demand algebraic program analysis. Proc ACM Program Lang 7:1993\u20132022","journal-title":"Proc ACM Program Lang"},{"key":"1249_CR28","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1145\/3622807","volume":"7","author":"GK Conrado","year":"2023","unstructured":"Conrado GK, Goharshady AK, Lam CK (2023) The bounded pathwidth of control-flow graphs. Proc ACM Program Lang 7:292\u2013317","journal-title":"Proc ACM Program Lang"},{"key":"1249_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-21275-3","volume-title":"Parameterized algorithms","author":"M Cygan","year":"2015","unstructured":"Cygan M, Fomin FV, Kowalik \u0141, Lokshtanov D, Marx D, Pilipczuk M, Pilipczuk M, Saurabh S (2015) Parameterized algorithms. Springer"},{"key":"1249_CR30","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1109\/99.660313","volume":"5","author":"L Dagum","year":"1998","unstructured":"Dagum L, Menon R (1998) OpenMP: an industry-standard API for shared-memory programming. IEEE Comput Sci Eng 5:46\u201355","journal-title":"IEEE Comput Sci Eng"},{"key":"1249_CR31","doi-asserted-by":"crossref","unstructured":"Dev JA (2014) Bitcoin mining acceleration and performance quantification. In: CCECE, pp 1\u20136","DOI":"10.1109\/CCECE.2014.6900989"},{"key":"1249_CR32","unstructured":"Ethereum Foundation (2021) Stake your ETH to become an Ethereum validator. https:\/\/ethereum.org\/en\/eth2\/staking\/"},{"key":"1249_CR33","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1145\/3212998","volume":"61","author":"I Eyal","year":"2018","unstructured":"Eyal I, Sirer EG (2018) Majority is not enough: Bitcoin mining is vulnerable. Commun ACM 61:95\u2013102","journal-title":"Commun ACM"},{"key":"1249_CR34","first-page":"1","volume":"14","author":"FV Fomin","year":"2018","unstructured":"Fomin FV, Lokshtanov D, Saurabh S, Pilipczuk M, Wrochna M (2018) Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. ACM Trans Algorithms (TALG) 14:1\u201345","journal-title":"ACM Trans Algorithms (TALG)"},{"key":"1249_CR35","doi-asserted-by":"crossref","unstructured":"Gilad Y, Hemo R, Micali S, Vlachos G, Zeldovich N (2017) Algorand: scaling byzantine agreements for cryptocurrencies. In: SOSP, pp 51\u201368","DOI":"10.1145\/3132747.3132757"},{"key":"1249_CR36","unstructured":"Goharshady AK (2020) Parameterized and Algebro-geometric Advances in Static Program Analysis, PhD thesis, Institute of Science and Technology Austria"},{"key":"1249_CR37","doi-asserted-by":"publisher","first-page":"2551","DOI":"10.1145\/3689801","volume":"8","author":"AK Goharshady","year":"2024","unstructured":"Goharshady AK, Lam CK, Parreaux L (2024) Fast and optimal extraction for sparse equality graphs. Proc ACM Program Lang 8:2551\u20132577","journal-title":"Proc ACM Program Lang"},{"key":"1249_CR38","doi-asserted-by":"publisher","DOI":"10.1016\/j.ress.2019.106665","volume":"193","author":"AK Goharshady","year":"2020","unstructured":"Goharshady AK, Mohammadi F (2020) An efficient algorithm for computing network reliability in small treewidth. Reliab Eng Syst Saf 193:106665","journal-title":"Reliab Eng Syst Saf"},{"key":"1249_CR39","doi-asserted-by":"crossref","unstructured":"Goharshady AK, Zaher AK (2023) Efficient interprocedural data-flow analysis using treedepth and treewidth. In: VMCAI, vol 3881, pp 177\u2013202","DOI":"10.1007\/978-3-031-24950-1_9"},{"key":"1249_CR40","doi-asserted-by":"publisher","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad J (2001) Some optimal inapproximability results. J ACM 48:798\u2013859","journal-title":"J ACM"},{"key":"1249_CR41","doi-asserted-by":"crossref","unstructured":"Javarone MA, Wright CS (2018) From Bitcoin to Bitcoin cash: a network analysis. In: Workshop on Cryptocurrencies and Blockchains for Distributed Systems, pp 77\u201381","DOI":"10.1145\/3211933.3211947"},{"key":"1249_CR42","doi-asserted-by":"crossref","unstructured":"Kiayias A, Russell A, David B, Oliynykov R (2017) Ouroboros: a provably secure proof-of-stake blockchain protocol. In: CRYPTO, pp 357\u2013388","DOI":"10.1007\/978-3-319-63688-7_12"},{"key":"1249_CR43","unstructured":"King S, Nadal S (2012) Ppcoin: peer-to-peer crypto-currency with proof-of-stake, tech. report"},{"key":"1249_CR44","doi-asserted-by":"crossref","unstructured":"Kwon Y, Kim H, Shin J, Kim Y (2019) Bitcoin vs. Bitcoin cash: Coexistence or downfall of Bitcoin cash?. In: SP, pp 935\u2013951","DOI":"10.1109\/SP.2019.00075"},{"key":"1249_CR45","doi-asserted-by":"crossref","unstructured":"Laszka A, Johnson B, Grossklags J (2015) When Bitcoin mining pools run dry. In: FC, pp 63\u201377","DOI":"10.1007\/978-3-662-48051-9_5"},{"key":"1249_CR46","unstructured":"Lewenberg Y, Bachrach Y, Sompolinsky Y, Zohar A, Rosenschein JS (2015) Bitcoin mining pools: a cooperative game theoretic analysis. In: AAMAS, pp 919\u2013927"},{"key":"1249_CR47","unstructured":"Lombrozo E, Lau J, Wuille P (2015) Segregated witness (consensus layer), Bitcoin Core Develop. Team, Tech. Rep. BIP, p 141"},{"key":"1249_CR48","doi-asserted-by":"crossref","unstructured":"McCorry P, Hicks A, Meiklejohn S (2018) Smart contracts for bribing miners. In: FC, vol 10958, pp 3\u201318","DOI":"10.1007\/978-3-662-58820-8_1"},{"key":"1249_CR49","doi-asserted-by":"crossref","unstructured":"Meybodi MA, Goharshady AK, Hooshmandasl MR, Shakiba A (2022) Optimal mining: Maximizing bitcoin miners\u2019 revenues from transaction fees. In: Blockchain. IEEE, pp 266\u2013273","DOI":"10.1109\/Blockchain55522.2022.00044"},{"key":"1249_CR50","doi-asserted-by":"publisher","first-page":"2223","DOI":"10.24294\/jipd.v7i3.2223","volume":"7","author":"A Mikhaylov","year":"2023","unstructured":"Mikhaylov A (2023) Understanding the risks associated with wallets, depository services, trading, lending, and borrowing in the crypto space. J Infrastruct Policy Dev 7:2223","journal-title":"J Infrastruct Policy Dev"},{"key":"1249_CR51","unstructured":"Miner Fees (2020) In Bitcoin Wiki . https:\/\/en.bitcoin.it\/wiki\/Miner_fees#Priority_transactions"},{"key":"1249_CR52","first-page":"119","volume":"9","author":"V Mutalimov","year":"2021","unstructured":"Mutalimov V, Kovaleva I, Mikhaylov A, Stepanova D (2021) Assessing regional growth of small business in Russia. Entrep Bus Econ Rev 9:119\u2013133","journal-title":"Entrep Bus Econ Rev"},{"key":"1249_CR53","unstructured":"Nakamoto S (2008) Bitcoin: A peer-to-peer electronic cash system, tech. report"},{"key":"1249_CR54","doi-asserted-by":"publisher","first-page":"1022","DOI":"10.1016\/j.ejc.2005.01.010","volume":"27","author":"J Ne\u0161et\u0159il","year":"2006","unstructured":"Ne\u0161et\u0159il J, De Mendez PO (2006) Tree-depth, subgraph coloring and homomorphism bounds. Eur J Comb 27:1022\u20131041","journal-title":"Eur J Comb"},{"key":"1249_CR55","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-27875-4","volume-title":"Sparsity: graphs, structures, and algorithms","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il J, De Mendez PO (2012) Sparsity: graphs, structures, and algorithms, vol 28. Springer"},{"key":"1249_CR56","doi-asserted-by":"publisher","first-page":"675","DOI":"10.1109\/TCS.1979.1084695","volume":"26","author":"T Ohtsuki","year":"1979","unstructured":"Ohtsuki T, Mori H, Kuh E, Kashiwabara T, Fujisawa T (1979) One-dimensional logic gate assignment and interval graphs. IEEE Trans Circuits Syst 26:675\u2013684","journal-title":"IEEE Trans Circuits Syst"},{"key":"1249_CR57","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N Robertson","year":"1983","unstructured":"Robertson N, Seymour PD (1983) Graph minors. i. excluding a forest. J Comb Theory Ser B 35:39\u201361","journal-title":"J Comb Theory Ser B"},{"key":"1249_CR58","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0095-8956(84)90013-3","volume":"36","author":"N Robertson","year":"1984","unstructured":"Robertson N, Seymour PD (1984) Graph minors. iii. planar tree-width. J Comb Theory Ser B 36:49\u201364","journal-title":"J Comb Theory Ser B"},{"key":"1249_CR59","doi-asserted-by":"publisher","first-page":"4803","DOI":"10.24294\/jipd.v8i7.4803","volume":"8","author":"D Stepanova","year":"2024","unstructured":"Stepanova D, Yousif N, Karlibaeva R, Mikhaylov A (2024) Current analysis of cryptocurrency mining industry. J Infrastruct Policy Dev 8:4803","journal-title":"J Infrastruct Policy Dev"},{"key":"1249_CR60","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1109\/MC.2017.3571056","volume":"50","author":"MB Taylor","year":"2017","unstructured":"Taylor MB (2017) The evolution of Bitcoin hardware. Computer 50:58\u201366","journal-title":"Computer"},{"key":"1249_CR61","unstructured":"The Sage Developers (2020) SageMath, the Sage Mathematics Software System"},{"key":"1249_CR62","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1006\/inco.1997.2697","volume":"142","author":"M Thorup","year":"1998","unstructured":"Thorup M (1998) All structured programs have small tree width and good register allocation. Inf Comput 142:159\u2013181","journal-title":"Inf Comput"},{"key":"1249_CR63","unstructured":"van Dijk T, van den Heuvel J-P, Slob W (2006) Computing treewidth with LibTW, tech. report, University of Utrecht"},{"key":"1249_CR64","doi-asserted-by":"crossref","unstructured":"Velner Y, Teutsch J, Luu L (2017) Smart contracts make Bitcoin mining pools vulnerable. In: FC, pp 298\u2013316","DOI":"10.1007\/978-3-319-70278-0_19"},{"key":"1249_CR65","doi-asserted-by":"crossref","unstructured":"Wang C, Chu X, Qin Y (2020) Measurement and analysis of the Bitcoin networks: A view from mining pools. In: BIGCOM, pp 180\u2013188","DOI":"10.1109\/BigCom51056.2020.00032"},{"key":"1249_CR66","unstructured":"Zhang F, Eyal I, Escriva R, Juels A, van Renesse R (2017) REM: resource-efficient mining for blockchains. In: USENIX Security, pp 1427\u20131444"},{"key":"1249_CR67","doi-asserted-by":"crossref","unstructured":"Zur RB, Eyal I, Tamar A (2020) Efficient MDP analysis for selfish-mining in blockchains. In: AFT, pp 113\u2013131","DOI":"10.1145\/3419614.3423264"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01249-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01249-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01249-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T19:03:37Z","timestamp":1737745417000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01249-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,19]]},"references-count":67,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,1]]}},"alternative-id":["1249"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01249-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,12,19]]},"assertion":[{"value":"12 December 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"15"}}