[{"day":"01","related_material":{"record":[{"id":"21651","status":"public","relation":"dissertation_contains"}]},"author":[{"last_name":"Baig","full_name":"Baig, Mirza Ahad","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654"}],"volume":15752,"publisher":"Springer Nature","project":[{"_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","grant_number":"F8509","name":"Security and Privacy by Design for Complex Systems"}],"alternative_title":["LNCS"],"page":"127-142","publication_status":"published","citation":{"ama":"Baig MA, Pietrzak KZ. On the (in)security of Proofs-of-space based longest-chain blockchains. In: <i>29th International Conference on Financial Cryptography and Data Security</i>. Vol 15752. Springer Nature; 2026:127-142. doi:<a href=\"https://doi.org/10.1007/978-3-032-07035-7_8\">10.1007/978-3-032-07035-7_8</a>","mla":"Baig, Mirza Ahad, and Krzysztof Z. Pietrzak. “On the (in)Security of Proofs-of-Space Based Longest-Chain Blockchains.” <i>29th International Conference on Financial Cryptography and Data Security</i>, vol. 15752, Springer Nature, 2026, pp. 127–42, doi:<a href=\"https://doi.org/10.1007/978-3-032-07035-7_8\">10.1007/978-3-032-07035-7_8</a>.","ista":"Baig MA, Pietrzak KZ. 2026. On the (in)security of Proofs-of-space based longest-chain blockchains. 29th International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 15752, 127–142.","chicago":"Baig, Mirza Ahad, and Krzysztof Z Pietrzak. “On the (in)Security of Proofs-of-Space Based Longest-Chain Blockchains.” In <i>29th International Conference on Financial Cryptography and Data Security</i>, 15752:127–42. Springer Nature, 2026. <a href=\"https://doi.org/10.1007/978-3-032-07035-7_8\">https://doi.org/10.1007/978-3-032-07035-7_8</a>.","apa":"Baig, M. A., &#38; Pietrzak, K. Z. (2026). On the (in)security of Proofs-of-space based longest-chain blockchains. In <i>29th International Conference on Financial Cryptography and Data Security</i> (Vol. 15752, pp. 127–142). Miyakojima, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-07035-7_8\">https://doi.org/10.1007/978-3-032-07035-7_8</a>","short":"M.A. Baig, K.Z. Pietrzak, in:, 29th International Conference on Financial Cryptography and Data Security, Springer Nature, 2026, pp. 127–142.","ieee":"M. A. Baig and K. Z. Pietrzak, “On the (in)security of Proofs-of-space based longest-chain blockchains,” in <i>29th International Conference on Financial Cryptography and Data Security</i>, Miyakojima, Japan, 2026, vol. 15752, pp. 127–142."},"scopus_import":"1","oa_version":"Preprint","conference":{"location":"Miyakojima, Japan","name":"FC: Financial Cryptography and Data Security","start_date":"2025-04-14","end_date":"2025-04-18"},"month":"01","status":"public","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2505.14891","open_access":"1"}],"OA_place":"repository","doi":"10.1007/978-3-032-07035-7_8","quality_controlled":"1","department":[{"_id":"KrPi"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","oa":1,"date_created":"2026-02-01T23:01:43Z","publication":"29th International Conference on Financial Cryptography and Data Security","year":"2026","date_updated":"2026-04-15T08:45:18Z","publication_identifier":{"isbn":["9783032070340"],"issn":["0302-9743"],"eissn":["1611-3349"]},"arxiv":1,"acknowledgement":"This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/F85.","external_id":{"arxiv":["2505.14891"]},"abstract":[{"text":"The Nakamoto consensus protocol underlying the Bitcoin blockchain uses proof of work as a voting mechanism. Honest miners who contribute hashing power towards securing the chain try to extend the longest chain they are aware of. Despite its simplicity, Nakamoto consensus achieves meaningful security guarantees assuming that at any point in time, a majority of the hashing power is controlled by honest parties. This also holds under “resource variability”, i.e., if the total hashing power varies greatly over time.\r\nProofs of space (PoSpace) have been suggested as a more sustainable replacement for proofs of work. Unfortunately, no construction of a “longest-chain” blockchain based on PoSpace, that is secure under dynamic availability, is known. In this work, we prove that without additional assumptions no such protocol exists. We exactly quantify this impossibility result by proving a bound on the length of the fork required for double spending as a function of the adversarial capabilities. This bound holds for any chain selection rule, and we also show a chain selection rule (albeit a very strange one) that almost matches this bound.\r\nThe Nakamoto consensus protocol underlying the Bitcoin blockchain uses proof of work as a voting mechanism. Honest miners who contribute hashing power towards securing the chain try to extend the longest chain they are aware of. Despite its simplicity, Nakamoto consensus achieves meaningful security guarantees assuming that at any point in time, a majority of the hashing power is controlled by honest parties. This also holds under “resource variability”, i.e., if the total hashing power varies greatly over time.\r\n\r\nProofs of space (PoSpace) have been suggested as a more sustainable replacement for proofs of work. Unfortunately, no construction of a “longest-chain” blockchain based on PoSpace, that is secure under dynamic availability, is known. In this work, we prove that without additional assumptions no such protocol exists. We exactly quantify this impossibility result by proving a bound on the length of the fork required for double spending as a function of the adversarial capabilities. This bound holds for any chain selection rule, and we also show a chain selection rule (albeit a very strange one) that almost matches this bound.\r\n\r\nConcretely, we consider a security game in which the honest parties at any point control 0 > 1\r\n times more space than the adversary. The adversary can change the honest space by a factor 1+- E with every block (dynamic availability), and “replotting” the space (which allows answering two challenges using the same space) takes as much time as p blocks.\r\nWe prove that no matter what chain selection rule is used, in this game the adversary can create a fork of length o^2 . p/E that will be picked as the winner by the chain selection rule.\r\nWe also provide an upper bound that matches the lower bound up to a factor o. There exists a chain selection rule (albeit a very strange one) which in the above game requires forks of length at least o . p/E\r\nOur results show the necessity of additional assumptions to create a secure PoSpace based longest-chain blockchain. The Chia network in addition to PoSpace uses a verifiable delay function. Our bounds show that an additional primitive like that is necessary.","lang":"eng"}],"intvolume":"     15752","_id":"21134","type":"conference","language":[{"iso":"eng"}],"OA_type":"green","date_published":"2026-01-01T00:00:00Z","article_processing_charge":"No","title":"On the (in)security of Proofs-of-space based longest-chain blockchains"},{"file_date_updated":"2026-04-15T07:37:25Z","language":[{"iso":"eng"}],"date_published":"2026-03-04T00:00:00Z","title":"On secure chain selection rules from physical resources in a permissionless setting","article_processing_charge":"No","tmp":{"image":"/images/cc_by_nc_sa.png","legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","short":"CC BY-NC-SA (4.0)","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)"},"has_accepted_license":"1","type":"dissertation","_id":"21651","date_created":"2026-04-02T09:31:34Z","date_updated":"2026-04-15T08:45:19Z","year":"2026","publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-078-7"]},"abstract":[{"lang":"eng","text":"Blockchains enable distributed consensus in permissionless settings, where participants\r\nare unknown, dynamically changing, and do not trust each other. While Bitcoin,\r\nbased on Proof-of-Work (PoW), was the first protocol in this model, significant\r\nresearch has focused on permissionless protocols using alternative physical resources,\r\nspecifically Proof-of-Space (PoSpace) and Verifiable Delay Functions (VDFs). This\r\nthesis investigates the theoretical limits and design space of longest-chain protocols in\r\nthe fully permissionless and dynamically available settings using these three resources.\r\nFirst, we address the feasibility of blockchains relying solely on storage as a resource.\r\nWe prove a fundamental impossibility result: there exists no secure longest-chain\r\nprotocol based exclusively on Proof-of-Space in the fully permissionless or dynamically\r\navailable settings. Further, we quantify the adversarial capabilities required to execute\r\na double-spend attack. Our result formally justifies the necessity of coupling PoSpace\r\nwith time-dependent primitives (such as VDFs) or to move to less permissive settings\r\n(quasi-permissionless or permissioned) to ensure security.\r\nSecond, we generalize Nakamoto-like heaviest chain consensus to protocols utilizing\r\ncombinations of multiple physical resources. We analyze chain selection rules governed\r\nby a weight function Γ(S, V,W), which assigns weight to blocks based on recorded\r\nSpace (S), VDF speed (V ), and Work (W). We provide a complete classification\r\nof secure weight functions, proving that a weight function is secure against private\r\ndouble-spend attacks if and only if it is homogeneous in the timed resources (V,W)\r\nand sub-homogeneous in S. This framework unifies existing protocols like Bitcoin and\r\nChia under a single theoretical model and provides a powerful tool for designing new\r\nlongest-chain blockchains from a mix of physical resources."}],"department":[{"_id":"GradSch"},{"_id":"KrPi"}],"supervisor":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z"}],"corr_author":"1","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","oa":1,"OA_place":"publisher","doi":"10.15479/AT-ISTA-21651","oa_version":"Published Version","month":"03","ddc":["000"],"degree_awarded":"PhD","status":"public","alternative_title":["ISTA Thesis"],"publication_status":"published","file":[{"checksum":"c3986dba90653dac97adba662ebff238","creator":"mbaig","content_type":"application/x-zip-compressed","date_created":"2026-04-03T17:28:48Z","date_updated":"2026-04-13T08:24:13Z","file_id":"21655","file_name":"PhD-Thesis-Mirza-Ahad-Baig - Library Submission.zip","file_size":139353434,"relation":"source_file","access_level":"closed"},{"creator":"mbaig","checksum":"292a5989262521f7c145a109d1f348cb","file_name":"2026_Baig_Mirza_Ahad_Thesis.pdf","access_level":"open_access","file_size":1942037,"relation":"main_file","content_type":"application/pdf","date_created":"2026-04-03T17:29:30Z","file_id":"21656","date_updated":"2026-04-15T07:37:25Z"}],"citation":{"ieee":"M. A. Baig, “On secure chain selection rules from physical resources in a permissionless setting,” Institute of Science and Technology Austria, 2026.","ista":"Baig MA. 2026. On secure chain selection rules from physical resources in a permissionless setting. Institute of Science and Technology Austria.","ama":"Baig MA. On secure chain selection rules from physical resources in a permissionless setting. 2026. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-21651\">10.15479/AT-ISTA-21651</a>","mla":"Baig, Mirza Ahad. <i>On Secure Chain Selection Rules from Physical Resources in a Permissionless Setting</i>. Institute of Science and Technology Austria, 2026, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-21651\">10.15479/AT-ISTA-21651</a>.","chicago":"Baig, Mirza Ahad. “On Secure Chain Selection Rules from Physical Resources in a Permissionless Setting.” Institute of Science and Technology Austria, 2026. <a href=\"https://doi.org/10.15479/AT-ISTA-21651\">https://doi.org/10.15479/AT-ISTA-21651</a>.","short":"M.A. Baig, On Secure Chain Selection Rules from Physical Resources in a Permissionless Setting, Institute of Science and Technology Austria, 2026.","apa":"Baig, M. A. (2026). <i>On secure chain selection rules from physical resources in a permissionless setting</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-21651\">https://doi.org/10.15479/AT-ISTA-21651</a>"},"day":"04","related_material":{"record":[{"id":"21134","relation":"part_of_dissertation","status":"public"},{"id":"20587","status":"public","relation":"part_of_dissertation"}]},"author":[{"first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","full_name":"Baig, Mirza Ahad","last_name":"Baig"}],"publisher":"Institute of Science and Technology Austria"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"department":[{"_id":"KrPi"},{"_id":"GradSch"}],"abstract":[{"text":"Garbling is a fundamental cryptographic primitive, with numerous theoretical and practical applications. Since the first construction by Yao (FOCS’82, ’86), a line of work has concerned itself with reducing the communication and computational complexity of that construction. One of the most efficient garbling schemes presently is the ‘Half Gates’ scheme by Zahur, Rosulek, and Evans (Eurocrypt’15). Despite its widespread adoption, the provable security of this scheme has been based on assumptions whose only instantiations are in idealized models. For example, in their original paper, Zahur, Rosulek, and Evans showed that hash functions satisfying a notion called circular correlation robustness (CCR) suffice for this task, and then proved that CCR secure hash functions can be instantiated in the random permutation model.\r\nIn this work, we show how to securely instantiate the Half Gates scheme in the standard model. To this end, we first show how this scheme can be securely instantiated given a (family of) weak CCR hash function, a notion that we introduce. Furthermore, we show how a weak CCR hash function can be used to securely instantiate other efficient garbling schemes, namely the ones by Rosulek and Roy (Crypto’21) and Heath (Eurocrypt’24). Thus we believe this notion to be of independent interest.\r\nFinally, we construct such weak CCR hash functions using indistinguishability obfuscation and one-way functions. The security proof of this construction constitutes our main technical contribution. While our construction is not practical, it serves as a proof of concept supporting the soundness of these garbling schemes, which we regard to be particularly important given the recent initiative by NIST to standardize garbling, and the optimizations in Half Gates being potentially adopted.","lang":"eng"}],"publication":"28th IACR International Conference on Practice and Theory of Public-Key Cryptography","date_created":"2025-05-25T22:17:02Z","year":"2025","date_updated":"2025-06-02T07:01:45Z","publication_identifier":{"isbn":["9783031918285"],"issn":["0302-9743"],"eissn":["1611-3349"]},"_id":"19738","type":"conference","intvolume":"     15677","date_published":"2025-05-05T00:00:00Z","article_processing_charge":"No","title":"Securely instantiating ‘Half Gates’ garbling in the standard model","language":[{"iso":"eng"}],"OA_type":"green","volume":15677,"publisher":"Springer Nature","day":"05","author":[{"last_name":"Acharya","full_name":"Acharya, Anasuya","first_name":"Anasuya"},{"last_name":"Azari","full_name":"Azari, Karen","first_name":"Karen"},{"last_name":"Baig","full_name":"Baig, Mirza Ahad","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425"},{"last_name":"Hofheinz","full_name":"Hofheinz, Dennis","first_name":"Dennis"},{"full_name":"Kamath, Chethan","last_name":"Kamath","first_name":"Chethan"}],"scopus_import":"1","page":"37-75","alternative_title":["LNCS"],"citation":{"apa":"Acharya, A., Azari, K., Baig, M. A., Hofheinz, D., &#38; Kamath, C. (2025). Securely instantiating ‘Half Gates’ garbling in the standard model. In <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i> (Vol. 15677, pp. 37–75). Roros, Norway: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-91829-2_2\">https://doi.org/10.1007/978-3-031-91829-2_2</a>","short":"A. Acharya, K. Azari, M.A. Baig, D. Hofheinz, C. Kamath, in:, 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Springer Nature, 2025, pp. 37–75.","ama":"Acharya A, Azari K, Baig MA, Hofheinz D, Kamath C. Securely instantiating ‘Half Gates’ garbling in the standard model. In: <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>. Vol 15677. Springer Nature; 2025:37-75. doi:<a href=\"https://doi.org/10.1007/978-3-031-91829-2_2\">10.1007/978-3-031-91829-2_2</a>","ista":"Acharya A, Azari K, Baig MA, Hofheinz D, Kamath C. 2025. Securely instantiating ‘Half Gates’ garbling in the standard model. 28th IACR International Conference on Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography, LNCS, vol. 15677, 37–75.","mla":"Acharya, Anasuya, et al. “Securely Instantiating ‘Half Gates’ Garbling in the Standard Model.” <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, vol. 15677, Springer Nature, 2025, pp. 37–75, doi:<a href=\"https://doi.org/10.1007/978-3-031-91829-2_2\">10.1007/978-3-031-91829-2_2</a>.","chicago":"Acharya, Anasuya, Karen Azari, Mirza Ahad Baig, Dennis Hofheinz, and Chethan Kamath. “Securely Instantiating ‘Half Gates’ Garbling in the Standard Model.” In <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, 15677:37–75. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-91829-2_2\">https://doi.org/10.1007/978-3-031-91829-2_2</a>.","ieee":"A. Acharya, K. Azari, M. A. Baig, D. Hofheinz, and C. Kamath, “Securely instantiating ‘Half Gates’ garbling in the standard model,” in <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, Roros, Norway, 2025, vol. 15677, pp. 37–75."},"status":"public","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/281"}],"oa_version":"Preprint","conference":{"location":"Roros, Norway","end_date":"2025-05-15","name":"PKC: Public-Key Cryptography","start_date":"2025-05-12"},"month":"05","doi":"10.1007/978-3-031-91829-2_2","quality_controlled":"1","OA_place":"repository"},{"ddc":["000"],"article_number":"16","status":"public","main_file_link":[{"url":"https://eprint.iacr.org/2025/1410","open_access":"1"}],"oa_version":"Published Version","conference":{"start_date":"2025-10-08","name":"AFT: Conference on Advances in Financial Technologies","end_date":"2025-10-10","location":"Pittsburgh, PA, United States"},"month":"10","quality_controlled":"1","doi":"10.4230/LIPIcs.AFT.2025.16","OA_place":"publisher","volume":354,"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","project":[{"grant_number":"F8512","_id":"34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f","name":"Security and Privacy by Design for Complex Systems"},{"name":"Security and Privacy by Design for Complex Systems","grant_number":"F8509","_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1"}],"day":"06","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"21651"}]},"author":[{"last_name":"Baig","full_name":"Baig, Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","first_name":"Mirza Ahad"},{"id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","first_name":"Christoph Ullrich","last_name":"Günther","full_name":"Günther, Christoph Ullrich"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"scopus_import":"1","alternative_title":["LIPIcs"],"publication_status":"published","citation":{"ieee":"M. A. Baig, C. U. Günther, and K. Z. Pietrzak, “Nakamoto consensus from multiple resources,” in <i>7th Conference on Advances in Financial Technologies</i>, Pittsburgh, PA, United States, 2025, vol. 354.","short":"M.A. Baig, C.U. Günther, K.Z. Pietrzak, in:, 7th Conference on Advances in Financial Technologies, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","apa":"Baig, M. A., Günther, C. U., &#38; Pietrzak, K. Z. (2025). Nakamoto consensus from multiple resources. In <i>7th Conference on Advances in Financial Technologies</i> (Vol. 354). Pittsburgh, PA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">https://doi.org/10.4230/LIPIcs.AFT.2025.16</a>","mla":"Baig, Mirza Ahad, et al. “Nakamoto Consensus from Multiple Resources.” <i>7th Conference on Advances in Financial Technologies</i>, vol. 354, 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">10.4230/LIPIcs.AFT.2025.16</a>.","chicago":"Baig, Mirza Ahad, Christoph Ullrich Günther, and Krzysztof Z Pietrzak. “Nakamoto Consensus from Multiple Resources.” In <i>7th Conference on Advances in Financial Technologies</i>, Vol. 354. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">https://doi.org/10.4230/LIPIcs.AFT.2025.16</a>.","ama":"Baig MA, Günther CU, Pietrzak KZ. Nakamoto consensus from multiple resources. In: <i>7th Conference on Advances in Financial Technologies</i>. Vol 354. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">10.4230/LIPIcs.AFT.2025.16</a>","ista":"Baig MA, Günther CU, Pietrzak KZ. 2025. Nakamoto consensus from multiple resources. 7th Conference on Advances in Financial Technologies. AFT: Conference on Advances in Financial Technologies, LIPIcs, vol. 354, 16."},"file":[{"creator":"dernst","checksum":"b638adcd4fbffa77116c35393e165eb7","success":1,"file_name":"2025_LIPIcsAFT_Baig.pdf","access_level":"open_access","file_size":1061847,"relation":"main_file","content_type":"application/pdf","date_updated":"2025-11-04T08:19:02Z","file_id":"20598","date_created":"2025-11-04T08:19:02Z"}],"has_accepted_license":"1","type":"conference","_id":"20587","intvolume":"       354","date_published":"2025-10-06T00:00:00Z","article_processing_charge":"Yes","title":"Nakamoto consensus from multiple resources","tmp":{"short":"CC BY (4.0)","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode"},"file_date_updated":"2025-11-04T08:19:02Z","language":[{"iso":"eng"}],"OA_type":"gold","corr_author":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa":1,"department":[{"_id":"KrPi"}],"external_id":{"arxiv":["2508.01448"]},"abstract":[{"lang":"eng","text":"The blocks in the Bitcoin blockchain \"record\" the amount of work W that went into creating them through proofs of work. When honest parties control a majority of the work, consensus is achieved by picking the chain with the highest recorded weight. Resources other than work have been considered to secure such longest-chain blockchains. In Chia, blocks record the amount of disk-space S (via a proof of space) and sequential computational steps V (through a VDF).\r\nIn this paper, we ask what weight functions Γ(S,V,W) (that assign a weight to a block as a function of the recorded space, speed, and work) are secure in the sense that whenever the weight of the resources controlled by honest parties is larger than the weight of adversarial parties, the blockchain is secure against private double-spending attacks.\r\nWe completely classify such functions in an idealized \"continuous\" model: Γ(S,V,W) is secure against private double-spending attacks if and only if it is homogeneous of degree one in the \"timed\" resources V and W, i.e., αΓ(S,V,W) = Γ(S,α V, α W). This includes the Bitcoin rule Γ(S,V,W) = W and the Chia rule Γ(S,V,W) = S ⋅ V. In a more realistic model where blocks are created at discrete time-points, one additionally needs some mild assumptions on the dependency on S (basically, the weight should not grow too much if S is slightly increased, say linear as in Chia).\r\nOur classification is more general and allows various instantiations of the same resource. It provides a powerful tool for designing new longest-chain blockchains. E.g., consider combining different PoWs to counter centralization, say the Bitcoin PoW W₁ and a memory-hard PoW W₂. Previous work suggested to use W₁+W₂ as weight. Our results show that using e.g., √{W₁}⋅ √{W₂} or min{W₁,W₂} are also secure, and we argue that in practice these are much better choices."}],"date_created":"2025-11-02T23:01:34Z","publication":"7th Conference on Advances in Financial Technologies","year":"2025","date_updated":"2026-04-15T08:45:18Z","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959774000"]},"arxiv":1,"acknowledgement":"This research was funded in whole or in part by the Austrian Science Fund (FWF)\r\n10.55776/F85. For open access purposes, the author has applied a CC BY public copyright license\r\nto any author-accepted manuscript version arising from this submission."},{"scopus_import":"1","isi":1,"citation":{"ieee":"M. Anastos <i>et al.</i>, “The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging,” in <i>22nd International Conference on Theory of Cryptography</i>, Milan, Italy, 2024, vol. 15364, pp. 413–443.","mla":"Anastos, Michael, et al. “The Cost of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption and Group Messaging.” <i>22nd International Conference on Theory of Cryptography</i>, vol. 15364, Springer Nature, 2024, pp. 413–43, doi:<a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">10.1007/978-3-031-78011-0_14</a>.","ama":"Anastos M, Auerbach B, Baig MA, et al. The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. In: <i>22nd International Conference on Theory of Cryptography</i>. Vol 15364. Springer Nature; 2024:413-443. doi:<a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">10.1007/978-3-031-78011-0_14</a>","chicago":"Anastos, Michael, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Matthew Alan Kwan, Guillermo Pascual Perez, and Krzysztof Z Pietrzak. “The Cost of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption and Group Messaging.” In <i>22nd International Conference on Theory of Cryptography</i>, 15364:413–43. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">https://doi.org/10.1007/978-3-031-78011-0_14</a>.","ista":"Anastos M, Auerbach B, Baig MA, Cueto Noval M, Kwan MA, Pascual Perez G, Pietrzak KZ. 2024. The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. 22nd International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 15364, 413–443.","short":"M. Anastos, B. Auerbach, M.A. Baig, M. Cueto Noval, M.A. Kwan, G. Pascual Perez, K.Z. Pietrzak, in:, 22nd International Conference on Theory of Cryptography, Springer Nature, 2024, pp. 413–443.","apa":"Anastos, M., Auerbach, B., Baig, M. A., Cueto Noval, M., Kwan, M. A., Pascual Perez, G., &#38; Pietrzak, K. Z. (2024). The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. In <i>22nd International Conference on Theory of Cryptography</i> (Vol. 15364, pp. 413–443). Milan, Italy: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">https://doi.org/10.1007/978-3-031-78011-0_14</a>"},"alternative_title":["LNCS"],"publication_status":"published","page":"413-443","publisher":"Springer Nature","volume":15364,"author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","first_name":"Michael","full_name":"Anastos, Michael","last_name":"Anastos"},{"last_name":"Auerbach","full_name":"Auerbach, Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","first_name":"Benedikt","orcid":"0000-0002-7553-6606"},{"full_name":"Baig, Mirza Ahad","last_name":"Baig","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","first_name":"Mirza Ahad"},{"last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel","orcid":"0000-0002-2505-4246","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","first_name":"Miguel"},{"full_name":"Kwan, Matthew Alan","last_name":"Kwan","id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","first_name":"Matthew Alan","orcid":"0000-0002-4003-7567"},{"first_name":"Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo","last_name":"Pascual Perez"},{"last_name":"Pietrzak","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z"}],"day":"02","doi":"10.1007/978-3-031-78011-0_14","quality_controlled":"1","OA_place":"repository","status":"public","main_file_link":[{"url":"https://eprint.iacr.org/2024/1097","open_access":"1"}],"month":"12","conference":{"location":"Milan, Italy","end_date":"2024-12-06","start_date":"2024-12-02","name":"TCC: Theory of Cryptography"},"oa_version":"Preprint","abstract":[{"lang":"eng","text":"In this work we prove lower bounds on the (communication) cost of maintaining a shared key among a dynamic group of users. Being “dynamic” means one can add and remove users from the group. This captures important protocols like multicast encryption (ME) and continuous group-key agreement (CGKA), which is the primitive underlying many group messaging applications. We prove our bounds in a combinatorial setting where the state of the protocol progresses in rounds. The state of the protocol in each round is captured by a set system, with each of its elements specifying a set of users who share a secret key. We show this combinatorial model implies bounds in symbolic models for ME and CGKA that capture, as building blocks, PRGs, PRFs, dual PRFs, secret sharing, and symmetric encryption in the setting of ME, and PRGs, PRFs, dual PRFs, secret sharing, public-key encryption, and key-updatable public-key encryption in the setting of CGKA. The models are related to the ones used by Micciancio and Panjwani (Eurocrypt’04) and Bienstock et al. (TCC’20) to analyze ME and CGKA, respectively. We prove – using the Bollobás’ Set Pairs Inequality – that the cost (number of uploaded ciphertexts) for replacing a set of d users in a group of size n is Ω(dln(n/d)). Our lower bound is asymptotically tight and both improves on a bound of Ω(d) by Bienstock et al. (TCC’20), and generalizes a result by Micciancio and Panjwani (Eurocrypt’04), who proved a lower bound of Ω(log(n)) for d=1. "}],"external_id":{"isi":["001545628900014"]},"publication_identifier":{"isbn":["9783031780103"],"eissn":["1611-3349"],"issn":["0302-9743"]},"publication":"22nd International Conference on Theory of Cryptography","date_created":"2024-12-22T23:01:47Z","year":"2024","date_updated":"2025-12-02T13:55:46Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","oa":1,"department":[{"_id":"MaKw"},{"_id":"KrPi"}],"title":"The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging","article_processing_charge":"No","date_published":"2024-12-02T00:00:00Z","OA_type":"green","language":[{"iso":"eng"}],"type":"conference","_id":"18702","intvolume":"     15364"},{"department":[{"_id":"KrPi"}],"oa":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2023","date_updated":"2023-08-16T08:39:36Z","date_created":"2023-01-12T12:10:08Z","publication":"Distributed Computing","acknowledgement":"A preliminary version of this work appeared in DISC’19. Mirza Ahad Baig, Alessia Milani and Corentin Travers are supported by ANR projects Descartes and FREDDA. Mirza Ahad Baig is supported by UMI Relax. Danny Hendler is supported by the Israel Science Foundation (Grants 380/18 and 1425/22).","publication_identifier":{"issn":["0178-2770"],"eissn":["1432-0452"]},"external_id":{"isi":["000890138700001"]},"abstract":[{"lang":"eng","text":"A shared-memory counter is a widely-used and well-studied concurrent object. It supports two operations: An Inc operation that increases its value by 1 and a Read operation that returns its current value. In Jayanti et al (SIAM J Comput, 30(2), 2000), Jayanti, Tan and Toueg proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read-write registers, of a large class of shared objects that includes counters. The lower bound leaves open the question of finding counter implementations with sub-linear amortized step complexity. In this work, we address this gap. We show that n-process, wait-free and linearizable counters can be implemented from read-write registers with O(log2n) amortized step complexity. This is the first counter algorithm from read-write registers that provides sub-linear amortized step complexity in executions of arbitrary length. Since a logarithmic lower bound on the amortized step complexity of obstruction-free counter implementations exists, our upper bound is within a logarithmic factor of the optimal. The worst-case step complexity of the construction remains linear, which is optimal. This is obtained thanks to a new max register construction with O(logn) amortized step complexity in executions of arbitrary length in which the value stored in the register does not grow too quickly. We then leverage an existing counter algorithm by Aspnes, Attiya and Censor-Hillel [1] in which we “plug” our max register implementation to show that it remains linearizable while achieving O(log2n) amortized step complexity."}],"intvolume":"        36","type":"journal_article","_id":"12164","language":[{"iso":"eng"}],"date_published":"2023-03-01T00:00:00Z","article_processing_charge":"No","title":"Long-lived counters with polylogarithmic amortized step complexity","day":"01","author":[{"full_name":"Baig, Mirza Ahad","last_name":"Baig","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425"},{"full_name":"Hendler, Danny","last_name":"Hendler","first_name":"Danny"},{"last_name":"Milani","full_name":"Milani, Alessia","first_name":"Alessia"},{"first_name":"Corentin","full_name":"Travers, Corentin","last_name":"Travers"}],"volume":36,"publisher":"Springer Nature","publication_status":"published","page":"29-43","citation":{"short":"M.A. Baig, D. Hendler, A. Milani, C. Travers, Distributed Computing 36 (2023) 29–43.","apa":"Baig, M. A., Hendler, D., Milani, A., &#38; Travers, C. (2023). Long-lived counters with polylogarithmic amortized step complexity. <i>Distributed Computing</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00446-022-00439-5\">https://doi.org/10.1007/s00446-022-00439-5</a>","chicago":"Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers. “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” <i>Distributed Computing</i>. Springer Nature, 2023. <a href=\"https://doi.org/10.1007/s00446-022-00439-5\">https://doi.org/10.1007/s00446-022-00439-5</a>.","ista":"Baig MA, Hendler D, Milani A, Travers C. 2023. Long-lived counters with polylogarithmic amortized step complexity. Distributed Computing. 36, 29–43.","ama":"Baig MA, Hendler D, Milani A, Travers C. Long-lived counters with polylogarithmic amortized step complexity. <i>Distributed Computing</i>. 2023;36:29-43. doi:<a href=\"https://doi.org/10.1007/s00446-022-00439-5\">10.1007/s00446-022-00439-5</a>","mla":"Baig, Mirza Ahad, et al. “Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” <i>Distributed Computing</i>, vol. 36, Springer Nature, 2023, pp. 29–43, doi:<a href=\"https://doi.org/10.1007/s00446-022-00439-5\">10.1007/s00446-022-00439-5</a>.","ieee":"M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived counters with polylogarithmic amortized step complexity,” <i>Distributed Computing</i>, vol. 36. Springer Nature, pp. 29–43, 2023."},"isi":1,"scopus_import":"1","oa_version":"Preprint","article_type":"original","month":"03","keyword":["Computational Theory and Mathematics","Computer Networks and Communications","Hardware and Architecture","Theoretical Computer Science"],"main_file_link":[{"open_access":"1","url":"https://drops.dagstuhl.de/opus/volltexte/2019/11310/"}],"status":"public","doi":"10.1007/s00446-022-00439-5","quality_controlled":"1"},{"department":[{"_id":"KrPi"}],"oa":1,"user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","date_updated":"2026-04-07T13:01:26Z","year":"2021","publication":"19th International Conference","date_created":"2021-12-05T23:01:42Z","acknowledgement":"B. Auerbach, M.A. Baig and K. Pietrzak—received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Karen Klein was supported in part by ERC CoG grant 724307 and conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT); Guillermo Pascual-Perez was funded by the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 665385; Michael Walter conducted part of this work at IST Austria, funded by the ERC under the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).","publication_identifier":{"eisbn":["978-3-030-90456-2"],"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9-783-0309-0455-5"]},"external_id":{"isi":["000728363700008"]},"abstract":[{"text":"Key trees are often the best solution in terms of transmission cost and storage requirements for managing keys in a setting where a group needs to share a secret key, while being able to efficiently rotate the key material of users (in order to recover from a potential compromise, or to add or remove users). Applications include multicast encryption protocols like LKH (Logical Key Hierarchies) or group messaging like the current IETF proposal TreeKEM. A key tree is a (typically balanced) binary tree, where each node is identified with a key: leaf nodes hold users’ secret keys while the root is the shared group key. For a group of size N, each user just holds   log(N)  keys (the keys on the path from its leaf to the root) and its entire key material can be rotated by broadcasting   2log(N)  ciphertexts (encrypting each fresh key on the path under the keys of its parents). In this work we consider the natural setting where we have many groups with partially overlapping sets of users, and ask if we can find solutions where the cost of rotating a key is better than in the trivial one where we have a separate key tree for each group. We show that in an asymptotic setting (where the number m of groups is fixed while the number N of users grows) there exist more general key graphs whose cost converges to the cost of a single group, thus saving a factor linear in the number of groups over the trivial solution. As our asymptotic “solution” converges very slowly and performs poorly on concrete examples, we propose an algorithm that uses a natural heuristic to compute a key graph for any given group structure. Our algorithm combines two greedy algorithms, and is thus very efficient: it first converts the group structure into a “lattice graph”, which is then turned into a key graph by repeatedly applying the algorithm for constructing a Huffman code. To better understand how far our proposal is from an optimal solution, we prove lower bounds on the update cost of continuous group-key agreement and multicast encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom generators, and secret sharing as building blocks.","lang":"eng"}],"intvolume":"     13044","type":"conference","_id":"10408","language":[{"iso":"eng"}],"date_published":"2021-11-04T00:00:00Z","article_processing_charge":"No","title":"Grafting key trees: Efficient key management for overlapping groups","related_material":{"record":[{"relation":"dissertation_contains","status":"public","id":"18088"}]},"day":"04","author":[{"full_name":"Alwen, Joel F","last_name":"Alwen","id":"2A8DFA8C-F248-11E8-B48F-1D18A9856A87","first_name":"Joel F"},{"first_name":"Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt","last_name":"Auerbach"},{"full_name":"Baig, Mirza Ahad","last_name":"Baig","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425"},{"first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","orcid":"0000-0002-2505-4246","last_name":"Cueto Noval","full_name":"Cueto Noval, Miguel"},{"last_name":"Klein","full_name":"Klein, Karen","id":"3E83A2F8-F248-11E8-B48F-1D18A9856A87","first_name":"Karen"},{"last_name":"Pascual Perez","full_name":"Pascual Perez, Guillermo","id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","first_name":"Guillermo","orcid":"0000-0001-8630-415X"},{"full_name":"Pietrzak, Krzysztof Z","last_name":"Pietrzak","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9139-1654"},{"first_name":"Michael","id":"488F98B0-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0003-3186-2482","full_name":"Walter, Michael","last_name":"Walter"}],"volume":13044,"project":[{"name":"Teaching Old Crypto New Tricks","grant_number":"682815","call_identifier":"H2020","_id":"258AA5B2-B435-11E9-9278-68D0E5697425"},{"name":"International IST Doctoral Program","_id":"2564DBCA-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"665385"}],"publisher":"Springer Nature","publication_status":"published","page":"222-253","alternative_title":["LNCS"],"isi":1,"citation":{"ista":"Alwen JF, Auerbach B, Baig MA, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ, Walter M. 2021. Grafting key trees: Efficient key management for overlapping groups. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol. 13044, 222–253.","ama":"Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management for overlapping groups. In: <i>19th International Conference</i>. Vol 13044. Springer Nature; 2021:222-253. doi:<a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">10.1007/978-3-030-90456-2_8</a>","mla":"Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” <i>19th International Conference</i>, vol. 13044, Springer Nature, 2021, pp. 222–53, doi:<a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">10.1007/978-3-030-90456-2_8</a>.","chicago":"Alwen, Joel F, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “Grafting Key Trees: Efficient Key Management for Overlapping Groups.” In <i>19th International Conference</i>, 13044:222–53. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">https://doi.org/10.1007/978-3-030-90456-2_8</a>.","short":"J.F. Alwen, B. Auerbach, M.A. Baig, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer Nature, 2021, pp. 222–253.","apa":"Alwen, J. F., Auerbach, B., Baig, M. A., Cueto Noval, M., Klein, K., Pascual Perez, G., … Walter, M. (2021). Grafting key trees: Efficient key management for overlapping groups. In <i>19th International Conference</i> (Vol. 13044, pp. 222–253). Raleigh, NC, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-030-90456-2_8\">https://doi.org/10.1007/978-3-030-90456-2_8</a>","ieee":"J. F. Alwen <i>et al.</i>, “Grafting key trees: Efficient key management for overlapping groups,” in <i>19th International Conference</i>, Raleigh, NC, United States, 2021, vol. 13044, pp. 222–253."},"scopus_import":"1","ec_funded":1,"conference":{"location":"Raleigh, NC, United States","end_date":"2021-11-11","start_date":"2021-11-08","name":"TCC: Theory of Cryptography"},"oa_version":"Preprint","month":"11","status":"public","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1158"}],"doi":"10.1007/978-3-030-90456-2_8","quality_controlled":"1"},{"abstract":[{"lang":"eng","text":"We present the first deterministic wait-free long-lived snapshot algorithm, using only read and write operations, that guarantees polylogarithmic amortized step complexity in all executions. This is the first non-blocking snapshot algorithm, using reads and writes only, that has sub-linear amortized step complexity in executions of arbitrary length. The key to our construction is a novel implementation of a 2-component max array object which may be of independent interest."}],"external_id":{"isi":["001436693500004"]},"scopus_import":"1","citation":{"ieee":"M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived snapshots with polylogarithmic amortized step complexity,” in <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>, Virtual, Italy, 2020, pp. 31–40.","mla":"Baig, Mirza Ahad, et al. “Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity.” <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2020, pp. 31–40, doi:<a href=\"https://doi.org/10.1145/3382734.3406005\">10.1145/3382734.3406005</a>.","ama":"Baig MA, Hendler D, Milani A, Travers C. Long-lived snapshots with polylogarithmic amortized step complexity. In: <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2020:31-40. doi:<a href=\"https://doi.org/10.1145/3382734.3406005\">10.1145/3382734.3406005</a>","ista":"Baig MA, Hendler D, Milani A, Travers C. 2020. Long-lived snapshots with polylogarithmic amortized step complexity. Proceedings of the 39th Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 31–40.","chicago":"Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers. “Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity.” In <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i>, 31–40. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3382734.3406005\">https://doi.org/10.1145/3382734.3406005</a>.","short":"M.A. Baig, D. Hendler, A. Milani, C. Travers, in:, Proceedings of the 39th Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2020, pp. 31–40.","apa":"Baig, M. A., Hendler, D., Milani, A., &#38; Travers, C. (2020). Long-lived snapshots with polylogarithmic amortized step complexity. In <i>Proceedings of the 39th Symposium on Principles of Distributed Computing</i> (pp. 31–40). Virtual, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3382734.3406005\">https://doi.org/10.1145/3382734.3406005</a>"},"isi":1,"publication_identifier":{"isbn":["9781450375825"]},"publication_status":"published","date_updated":"2025-09-10T10:25:23Z","page":"31-40","year":"2020","publication":"Proceedings of the 39th Symposium on Principles of Distributed Computing","date_created":"2020-09-13T22:01:17Z","publisher":"Association for Computing Machinery","oa":1,"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","author":[{"full_name":"Baig, Mirza Ahad","last_name":"Baig","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","first_name":"Mirza Ahad"},{"full_name":"Hendler, Danny","last_name":"Hendler","first_name":"Danny"},{"first_name":"Alessia","full_name":"Milani, Alessia","last_name":"Milani"},{"first_name":"Corentin","last_name":"Travers","full_name":"Travers, Corentin"}],"day":"31","title":"Long-lived snapshots with polylogarithmic amortized step complexity","article_processing_charge":"No","quality_controlled":"1","date_published":"2020-07-31T00:00:00Z","doi":"10.1145/3382734.3406005","language":[{"iso":"eng"}],"_id":"8382","status":"public","main_file_link":[{"open_access":"1","url":"https://hal.archives-ouvertes.fr/hal-02860087/document"}],"type":"conference","month":"07","conference":{"location":"Virtual, Italy","name":"PODC: Principles of Distributed Computing","start_date":"2020-08-03","end_date":"2020-08-07"},"oa_version":"Preprint"}]