{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T18:00:43Z","timestamp":1773511243530,"version":"3.50.1"},"publisher-location":"Cham","reference-count":45,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031159787","type":"print"},{"value":"9783031159794","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-15979-4_12","type":"book-chapter","created":{"date-parts":[[2022,10,12]],"date-time":"2022-10-12T16:25:31Z","timestamp":1665591931000},"page":"339-369","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Ofelimos: Combinatorial Optimization via\u00a0Proof-of-Useful-Work"],"prefix":"10.1007","author":[{"given":"Matthias","family":"Fitzi","sequence":"first","affiliation":[]},{"given":"Aggelos","family":"Kiayias","sequence":"additional","affiliation":[]},{"given":"Giorgos","family":"Panagiotakos","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Russell","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,13]]},"reference":[{"issue":"1","key":"12_CR1","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(90)90188-N","volume":"71","author":"A Aggarwal","year":"1990","unstructured":"Aggarwal, A., Chandra, A.K., Snir, M.: Communication complexity of prams. Theor. Comput. Sci. 71(1), 3\u201328 (1990)","journal-title":"Theor. Comput. Sci."},{"issue":"1\u20133","key":"12_CR2","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1016\/S0166-218X(01)00338-9","volume":"123","author":"RK Ahuja","year":"2002","unstructured":"Ahuja, R.K., Ergun, \u00d6., Orlin, J.B., Punnen, A.P.: A survey of very large-scale neighborhood search techniques. Discret. Appl. Math. 123(1\u20133), 75\u2013102 (2002)","journal-title":"Discret. Appl. Math."},{"key":"12_CR3","unstructured":"Aldous, D., Fill, J.A.: Reversible Markov chains and random walks on graphs (2002, Unfinished monograph). http:\/\/www.stat.berkeley.edu\/~aldous\/RWG\/book.html"},{"key":"12_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/978-3-662-48000-7_19","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"M Andrychowicz","year":"2015","unstructured":"Andrychowicz, M., Dziembowski, S.: PoW-based distributed cryptography with no trusted setup. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 379\u2013399. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48000-7_19"},{"key":"12_CR5","unstructured":"Badertscher, C., Gazi, P., Kiayias, A., Russell, A., Zikas, V.: Consensus redux: distributed ledgers in the face of adversarial supremacy. IACR Cryptology ePrint Archive, Report 2020\/1021 (2020)"},{"key":"12_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"324","DOI":"10.1007\/978-3-319-63688-7_11","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"C Badertscher","year":"2017","unstructured":"Badertscher, C., Maurer, U., Tschudi, D., Zikas, V.: Bitcoin as a transaction ledger: a composable treatment. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 324\u2013356. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_11"},{"key":"12_CR7","doi-asserted-by":"crossref","unstructured":"Baldominos, A., Saez, Y.: Coin. AI: a proof-of-useful-work scheme for blockchain-based distributed deep learning. Entropy 21(8), 723 (2019)","DOI":"10.3390\/e21080723"},{"key":"12_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1007\/978-3-319-96884-1_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"M Ball","year":"2018","unstructured":"Ball, M., Rosen, A., Sabin, M., Vasudevan, P.N.: Proofs of work from worst-case assumptions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 789\u2013819. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96884-1_26"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: CCS 1993, Fairfax, Virginia, USA, pp. 62\u201373 (1993)","DOI":"10.1145\/168588.168596"},{"key":"12_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1007\/978-3-319-96884-1_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"D Boneh","year":"2018","unstructured":"Boneh, D., Bonneau, J., B\u00fcnz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 757\u2013788. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96884-1_25"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Goharshady, A.K., Pourdamghani, A.: Hybrid mining: exploiting blockchain\u2019s computational power for distributed problem solving. In: Proceedings of the 34th ACM\/SIGAPP Symposium on Applied Computing (2019)","DOI":"10.1145\/3297280.3297319"},{"key":"12_CR12","unstructured":"Coelho, F.: An (almost) constant-effort solution-verification proof-of-work protocol based on Merkle trees. Cryptology ePrint Archive, Report 2007\/433 (2007)"},{"key":"12_CR13","unstructured":"Coventry, A.: Nooshare: a decentralized ledger of shared computational resources (2012). https:\/\/web.archive.org\/web\/20220620105201\/. http:\/\/web.mit.edu\/alex_c\/www\/nooshare.pdf"},{"key":"12_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-3-030-32101-7_2","volume-title":"Financial Cryptography and Data Security","author":"P Daian","year":"2019","unstructured":"Daian, P., Pass, R., Shi, E.: Snow white: robustly reconfigurable consensus and applications to provably secure proof of stake. In: Goldberg, I., Moore, T. (eds.) FC 2019. LNCS, vol. 11598, pp. 23\u201341. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-32101-7_2"},{"key":"12_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-319-78375-8_3","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"B David","year":"2018","unstructured":"David, B., Ga\u017ei, P., Kiayias, A., Russell, A.: Ouroboros praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 66\u201398. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78375-8_3"},{"key":"12_CR16","unstructured":"Dotan, M., Tochner, S.: Proofs of useless work-positive and negative results for wasteless mining systems. arXiv preprint arXiv:2007.01046 (2020)"},{"key":"12_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"585","DOI":"10.1007\/978-3-662-48000-7_29","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"S Dziembowski","year":"2015","unstructured":"Dziembowski, S., Faust, S., Kolmogorov, V., Pietrzak, K.: Proofs of space. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 585\u2013605. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48000-7_29"},{"key":"12_CR18","doi-asserted-by":"crossref","unstructured":"Fitzi, M., Kiayias, A., Panagiotakos, G., Russell, A.: Ofelimos: combinatorial optimization via proof-of-useful-work\u2013a provably secure blockchain protocol. Cryptology ePrint Archive, Paper 2021\/1379 (2021)","DOI":"10.1007\/978-3-031-15979-4_12"},{"key":"12_CR19","unstructured":"Gapcoin. Gapcoin (2014). https:\/\/gapcoin.org\/"},{"key":"12_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/978-3-662-46803-6_10","volume-title":"Advances in Cryptology - EUROCRYPT 2015","author":"J Garay","year":"2015","unstructured":"Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 281\u2013310. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46803-6_10"},{"key":"12_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/978-3-030-40186-3_14","volume-title":"Topics in Cryptology \u2013 CT-RSA 2020","author":"JA Garay","year":"2020","unstructured":"Garay, J.A., Kiayias, A., Panagiotakos, G.: Consensus from signatures of work. In: Jarecki, S. (ed.) CT-RSA 2020. LNCS, vol. 12006, pp. 319\u2013344. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-40186-3_14"},{"key":"12_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/978-3-030-64375-1_11","volume-title":"Theory of Cryptography","author":"JA Garay","year":"2020","unstructured":"Garay, J.A., Kiayias, A., Panagiotakos, G.: Blockchains from non-idealized hash functions. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12550, pp. 291\u2013321. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64375-1_11"},{"key":"12_CR23","doi-asserted-by":"crossref","unstructured":"Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles, pp. 51\u201368 (2017)","DOI":"10.1145\/3132747.3132757"},{"key":"12_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-662-49896-5_11","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"J Groth","year":"2016","unstructured":"Groth, J.: On the size of pairing-based non-interactive arguments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 305\u2013326. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49896-5_11"},{"key":"12_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1007\/978-3-319-96878-0_24","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"J Groth","year":"2018","unstructured":"Groth, J., Kohlweiss, M., Maller, M., Meiklejohn, S., Miers, I.: Updatable and universal common reference strings with applications to\u00a0zk-SNARKs. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 698\u2013728. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96878-0_24"},{"issue":"2\u20133","key":"12_CR26","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/0004-3702(92)90028-V","volume":"56","author":"N Gupta","year":"1992","unstructured":"Gupta, N., Nau, D.S.: On the complexity of blocks-world planning. Artif. Intell. 56(2\u20133), 223\u2013254 (1992)","journal-title":"Artif. Intell."},{"key":"12_CR27","volume-title":"Stochastic Local Search: Foundations and Applications","author":"HH Hoos","year":"2004","unstructured":"Hoos, H.H., St\u00fctzle, T.: Stochastic Local Search: Foundations and Applications. Elsevier, Amsterdam (2004)"},{"key":"12_CR28","unstructured":"Kautz, H., Selman, B., McAllester, D.: Walksat in the 2004 SAT competition. In: Proceedings of the International Conference on Theory and Applications of Satisfiability Testing (2004)"},{"key":"12_CR29","doi-asserted-by":"crossref","unstructured":"Kerber, T., Kiayias, A., Kohlweiss, M.: Mining for privacy: how to bootstrap a snarky blockchain. Cryptology ePrint Archive, Report 2020\/401 (2020)","DOI":"10.1007\/978-3-662-64322-8_24"},{"key":"12_CR30","doi-asserted-by":"crossref","unstructured":"Kiayias, A., Quader, S., Russell, A.: Consistency of proof-of-stake blockchains with concurrent honest slot leaders. IACR Cryptology ePrint Archive, Report 2020\/041 (2020)","DOI":"10.1109\/ICDCS47774.2020.00065"},{"key":"12_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/978-3-319-63688-7_12","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"A Kiayias","year":"2017","unstructured":"Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: a provably secure proof-of-stake blockchain protocol. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 357\u2013388. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_12"},{"key":"12_CR32","unstructured":"King, S.: Primecoin: cryptocurrency with prime number proof-of-work (2013)"},{"key":"12_CR33","unstructured":"Lihu, A., Du, J., Barjaktarevic, I., Gerzanics, P., Harvilla, M.: A proof of useful work for artificial intelligence on the blockchain. arXiv:2001.09244 preprint (2020)"},{"key":"12_CR34","doi-asserted-by":"crossref","unstructured":"Loe, A.F., Quaglia, E.A.: Conquering generals: an NP-hard proof of useful work. In: Proceedings of the 1st Workshop on Cryptocurrencies and Blockchains for Distributed Systems, pp. 54\u201359 (2018)","DOI":"10.1145\/3211933.3211943"},{"key":"12_CR35","doi-asserted-by":"crossref","unstructured":"Maller, M., Bowe, S., Kohlweiss, M., Meiklejohn, S.: Sonic: zero-knowledge snarks from linear-size universal and updatable structured reference strings. In: ACM CCS 2019, London, UK, pp. 2111\u20132128 (2019)","DOI":"10.1145\/3319535.3339817"},{"key":"12_CR36","doi-asserted-by":"crossref","unstructured":"Miller, A., Juels, A., Shi, E., Parno, B., Katz, J.: Permacoin: repurposing bitcoin work for data preservation. In: 2014 IEEE S &P, pp. 475\u2013490. IEEE (2014)","DOI":"10.1109\/SP.2014.37"},{"key":"12_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1007\/978-3-030-26948-7_14","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"T Moran","year":"2019","unstructured":"Moran, T., Orlov, I.: Simple proofs of space-time and rational proofs of storage. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 381\u2013409. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26948-7_14"},{"key":"12_CR38","unstructured":"Oliver, C.G., Ricottone, A., Philippopoulos, P.: Proposal for a fully decentralized blockchain and proof-of-work algorithm for solving NP-complete problems. arXiv preprint arXiv:1708.09419 (2017)"},{"issue":"4","key":"12_CR39","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1137\/0216044","volume":"16","author":"CH Papadimitriou","year":"1987","unstructured":"Papadimitriou, C.H., Ullman, J.D.: A communication-time tradeoff. SIAM J. Comput. 16(4), 639\u2013646 (1987)","journal-title":"SIAM J. Comput."},{"key":"12_CR40","doi-asserted-by":"crossref","unstructured":"Park, S., Kwon, A., Fuchsbauer, G., Ga\u017ei, P., Alwen, J., Pietrzak, K.: SpaceMint: a cryptocurrency based on proofs of space. In: International Conference on Financial Cryptography and Data Security (2018)","DOI":"10.1007\/978-3-662-58387-6_26"},{"key":"12_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-319-56614-6_22","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"R Pass","year":"2017","unstructured":"Pass, R., Seeman, L., Shelat, A.: Analysis of the blockchain protocol in asynchronous networks. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 643\u2013673. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56614-6_22"},{"key":"12_CR42","doi-asserted-by":"crossref","unstructured":"Pass, R., Shi, E.: FruitChains: a fair blockchain. In: Schiller, E.M., Schwarzmann, A.A. (eds.) ACM PODC 2017, Washington, DC, USA, 25\u201327 July 2017, pp. 315\u2013324. ACM (2017)","DOI":"10.1145\/3087801.3087809"},{"key":"12_CR43","unstructured":"Selman, B., Kautz, H.A., Cohen, B.: Noise strategies for improving local search. In: Proceedings of the Twelfth National Conference on Artificial Intelligence, AAAI 1994, USA, vol. 1, pp. 337\u2013343 (1994)"},{"key":"12_CR44","unstructured":"Zhang, F., Eyal, I., Escriva, R., Juels, A., Van Renesse, R.: REM: resource-efficient mining for blockchains. In: 26th USENIX Security Symposium USENIX Security 2017, pp. 1427\u20131444 (2017)"},{"key":"12_CR45","unstructured":"Zheng, W., Chen, X., Zheng, Z., Luo, X., Cui, J.: AxeChain: a secure and decentralized blockchain for solving easily-verifiable problems. arXiv preprint arXiv:2003.13999 (2020)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2022"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-15979-4_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:03:23Z","timestamp":1760220203000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-15979-4_12"}},"subtitle":["A Provably Secure Blockchain Protocol"],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031159787","9783031159794"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-15979-4_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"13 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"42","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}