[{"date_created":"2021-12-16T13:20:19Z","article_processing_charge":"No","quality_controlled":"1","page":"187-190","department":[{"_id":"ElKo"}],"language":[{"iso":"eng"}],"publication_status":"published","month":"07","publication_identifier":{"isbn":["9-781-4503-8548-0"]},"title":"Brief announcement: Be prepared when network goes bad: An asynchronous view-change protocol","oa":1,"doi":"10.1145/3465084.3467941","main_file_link":[{"url":"https://arxiv.org/abs/2103.03181","open_access":"1"}],"type":"conference","conference":{"start_date":"2021-07-26","end_date":"2021-07-30","name":"PODC: Principles of Distributed Computing","location":"Virtual, Italy"},"scopus_import":"1","publication":"Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing","author":[{"last_name":"Gelashvili","full_name":"Gelashvili, Rati","first_name":"Rati"},{"first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","last_name":"Kokoris Kogias"},{"first_name":"Alexander","last_name":"Spiegelman","full_name":"Spiegelman, Alexander"},{"full_name":"Xiang, Zhuolun","last_name":"Xiang","first_name":"Zhuolun"}],"external_id":{"isi":["000744439800018"],"arxiv":["2103.03181"]},"status":"public","_id":"10553","oa_version":"Preprint","arxiv":1,"day":"21","isi":1,"year":"2021","citation":{"ieee":"R. Gelashvili, E. Kokoris Kogias, A. Spiegelman, and Z. Xiang, “Brief announcement: Be prepared when network goes bad: An asynchronous view-change protocol,” in <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Virtual, Italy, 2021, pp. 187–190.","apa":"Gelashvili, R., Kokoris Kogias, E., Spiegelman, A., &#38; Xiang, Z. (2021). Brief announcement: Be prepared when network goes bad: An asynchronous view-change protocol. In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i> (pp. 187–190). Virtual, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3465084.3467941\">https://doi.org/10.1145/3465084.3467941</a>","ama":"Gelashvili R, Kokoris Kogias E, Spiegelman A, Xiang Z. Brief announcement: Be prepared when network goes bad: An asynchronous view-change protocol. In: <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2021:187-190. doi:<a href=\"https://doi.org/10.1145/3465084.3467941\">10.1145/3465084.3467941</a>","ista":"Gelashvili R, Kokoris Kogias E, Spiegelman A, Xiang Z. 2021. Brief announcement: Be prepared when network goes bad: An asynchronous view-change protocol. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 187–190.","mla":"Gelashvili, Rati, et al. “Brief Announcement: Be Prepared When Network Goes Bad: An Asynchronous View-Change Protocol.” <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2021, pp. 187–90, doi:<a href=\"https://doi.org/10.1145/3465084.3467941\">10.1145/3465084.3467941</a>.","short":"R. Gelashvili, E. Kokoris Kogias, A. Spiegelman, Z. Xiang, in:, Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2021, pp. 187–190.","chicago":"Gelashvili, Rati, Eleftherios Kokoris Kogias, Alexander Spiegelman, and Zhuolun Xiang. “Brief Announcement: Be Prepared When Network Goes Bad: An Asynchronous View-Change Protocol.” In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, 187–90. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3465084.3467941\">https://doi.org/10.1145/3465084.3467941</a>."},"publisher":"Association for Computing Machinery","date_published":"2021-07-21T00:00:00Z","fulldoi":"https://doi.org/10.1145/3465084.3467941","keyword":["optimal","state machine replication","fallback","asynchrony","byzantine faults"],"date_updated":"2023-09-04T11:42:10Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"The popularity of permissioned blockchain systems demands BFT SMR protocols that are efficient under good network conditions (synchrony) and robust under bad network conditions (asynchrony). The state-of-the-art partially synchronous BFT SMR protocols provide optimal linear communication cost per decision under synchrony and good leaders, but lose liveness under asynchrony. On the other hand, the state-of-the-art asynchronous BFT SMR protocols are live even under asynchrony, but always pay quadratic cost even under synchrony. In this paper, we propose a BFT SMR protocol that achieves the best of both worlds -- optimal linear cost per decision under good networks and leaders, optimal quadratic cost per decision under bad networks, and remains always live."}]},{"external_id":{"arxiv":["2102.08325"],"isi":["000744439800016"]},"isi":1,"day":"21","arxiv":1,"publisher":"Association for Computing Machinery","year":"2021","citation":{"ama":"Keidar I, Kokoris Kogias E, Naor O, Spiegelman A. All You Need is DAG. In: <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2021:165-175. doi:<a href=\"https://doi.org/10.1145/3465084.3467905\">10.1145/3465084.3467905</a>","ista":"Keidar I, Kokoris Kogias E, Naor O, Spiegelman A. 2021. All You Need is DAG. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing. PODC: Principles of Distributed Computing, 165–175.","apa":"Keidar, I., Kokoris Kogias, E., Naor, O., &#38; Spiegelman, A. (2021). All You Need is DAG. In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i> (pp. 165–175). Virtual, Italy: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3465084.3467905\">https://doi.org/10.1145/3465084.3467905</a>","ieee":"I. Keidar, E. Kokoris Kogias, O. Naor, and A. Spiegelman, “All You Need is DAG,” in <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Virtual, Italy, 2021, pp. 165–175.","chicago":"Keidar, Idit, Eleftherios Kokoris Kogias, Oded Naor, and Alexander Spiegelman. “All You Need Is DAG.” In <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, 165–75. Association for Computing Machinery, 2021. <a href=\"https://doi.org/10.1145/3465084.3467905\">https://doi.org/10.1145/3465084.3467905</a>.","mla":"Keidar, Idit, et al. “All You Need Is DAG.” <i>Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2021, pp. 165–75, doi:<a href=\"https://doi.org/10.1145/3465084.3467905\">10.1145/3465084.3467905</a>.","short":"I. Keidar, E. Kokoris Kogias, O. Naor, A. Spiegelman, in:, Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2021, pp. 165–175."},"acknowledgement":"Oded Naor is grateful to the Technion Hiroshi Fujiwara Cyber-Security Research Center for providing a research grant. Part of Oded’s work was done while at Novi Research. This work was funded by the Novi team at Facebook. We also wish to thank the Novi Research team for valuable feedback, and in particular George Danezis, Alberto Sonnino, and Dahlia Malkhi.\r\n","_id":"10554","status":"public","oa_version":"Preprint","date_published":"2021-07-21T00:00:00Z","fulldoi":"https://doi.org/10.1145/3465084.3467905","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","abstract":[{"lang":"eng","text":"We present DAG-Rider, the first asynchronous Byzantine Atomic Broadcast protocol that achieves optimal resilience, optimal amortized communication complexity, and optimal time complexity. DAG-Rider is post-quantum safe and ensures that all values proposed by correct processes eventually get delivered. We construct DAG-Rider in two layers: In the first layer, processes reliably broadcast their proposals and build a structured Directed Acyclic Graph (DAG) of the communication among them. In the second layer, processes locally observe their DAGs and totally order all proposals with no extra communication."}],"date_updated":"2023-08-17T06:24:44Z","quality_controlled":"1","article_processing_charge":"No","date_created":"2021-12-16T13:21:13Z","month":"07","page":"165-175","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"ElKo"}],"title":"All You Need is DAG","oa":1,"publication_identifier":{"isbn":["978-1-4503-8548-0"]},"type":"conference","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2102.08325"}],"doi":"10.1145/3465084.3467905","publication":"Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing","author":[{"full_name":"Keidar, Idit","last_name":"Keidar","first_name":"Idit"},{"first_name":"Eleftherios","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","last_name":"Kokoris Kogias","full_name":"Kokoris Kogias, Eleftherios"},{"full_name":"Naor, Oded","last_name":"Naor","first_name":"Oded"},{"first_name":"Alexander","last_name":"Spiegelman","full_name":"Spiegelman, Alexander"}],"conference":{"start_date":"2021-07-26","location":"Virtual, Italy","name":"PODC: Principles of Distributed Computing","end_date":"2021-07-30"},"scopus_import":"1"},{"quality_controlled":"1","related_material":{"record":[{"status":"public","id":"8304","relation":"earlier_version"}]},"article_processing_charge":"No","date_created":"2021-11-21T23:01:29Z","month":"10","publication_status":"published","volume":"12675 ","language":[{"iso":"eng"}],"department":[{"_id":"ElKo"}],"page":"3-36","type":"conference","main_file_link":[{"url":"https://eprint.iacr.org/2019/1128","open_access":"1"}],"doi":"10.1007/978-3-662-64331-0_1","title":"SoK: Communication across distributed ledgers","oa":1,"publication_identifier":{"issn":["0302-9743"],"isbn":["9-783-6626-4330-3"],"eissn":["1611-3349"],"eisbn":["978-3-662-64331-0"]},"cryptoeprintid":1,"author":[{"first_name":"Alexei","full_name":"Zamyatin, Alexei","last_name":"Zamyatin"},{"first_name":"Mustafa","full_name":"Al-Bassam, Mustafa","last_name":"Al-Bassam"},{"full_name":"Zindros, Dionysis","last_name":"Zindros","first_name":"Dionysis"},{"orcid":"0000-0002-8827-3382","first_name":"Eleftherios","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","last_name":"Kokoris Kogias","full_name":"Kokoris Kogias, Eleftherios"},{"first_name":"Pedro","full_name":"Moreno-Sanchez, Pedro","last_name":"Moreno-Sanchez"},{"first_name":"Aggelos","last_name":"Kiayias","full_name":"Kiayias, Aggelos"},{"full_name":"Knottenbelt, William J.","last_name":"Knottenbelt","first_name":"William J."}],"publication":"25th International Conference on Financial Cryptography and Data Security","scopus_import":"1","conference":{"start_date":"2021-03-01","name":"FC: Financial Cryptography","end_date":"2021-03-05","location":"Virtual"},"external_id":{"isi":["000712016200001"],"cryptoeprintid":["2019/1128"]},"publisher":"Springer Nature","citation":{"short":"A. Zamyatin, M. Al-Bassam, D. Zindros, E. Kokoris Kogias, P. Moreno-Sanchez, A. Kiayias, W.J. Knottenbelt, in:, 25th International Conference on Financial Cryptography and Data Security, Springer Nature, 2021, pp. 3–36.","mla":"Zamyatin, Alexei, et al. “SoK: Communication across Distributed Ledgers.” <i>25th International Conference on Financial Cryptography and Data Security</i>, vol. 12675, Springer Nature, 2021, pp. 3–36, doi:<a href=\"https://doi.org/10.1007/978-3-662-64331-0_1\">10.1007/978-3-662-64331-0_1</a>.","chicago":"Zamyatin, Alexei, Mustafa Al-Bassam, Dionysis Zindros, Eleftherios Kokoris Kogias, Pedro Moreno-Sanchez, Aggelos Kiayias, and William J. Knottenbelt. “SoK: Communication across Distributed Ledgers.” In <i>25th International Conference on Financial Cryptography and Data Security</i>, 12675:3–36. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/978-3-662-64331-0_1\">https://doi.org/10.1007/978-3-662-64331-0_1</a>.","ieee":"A. Zamyatin <i>et al.</i>, “SoK: Communication across distributed ledgers,” in <i>25th International Conference on Financial Cryptography and Data Security</i>, Virtual, 2021, vol. 12675, pp. 3–36.","apa":"Zamyatin, A., Al-Bassam, M., Zindros, D., Kokoris Kogias, E., Moreno-Sanchez, P., Kiayias, A., &#38; Knottenbelt, W. J. (2021). SoK: Communication across distributed ledgers. In <i>25th International Conference on Financial Cryptography and Data Security</i> (Vol. 12675, pp. 3–36). Virtual: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-662-64331-0_1\">https://doi.org/10.1007/978-3-662-64331-0_1</a>","ama":"Zamyatin A, Al-Bassam M, Zindros D, et al. SoK: Communication across distributed ledgers. In: <i>25th International Conference on Financial Cryptography and Data Security</i>. Vol 12675. Springer Nature; 2021:3-36. doi:<a href=\"https://doi.org/10.1007/978-3-662-64331-0_1\">10.1007/978-3-662-64331-0_1</a>","ista":"Zamyatin A, Al-Bassam M, Zindros D, Kokoris Kogias E, Moreno-Sanchez P, Kiayias A, Knottenbelt WJ. 2021. SoK: Communication across distributed ledgers. 25th International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography, LNCS, vol. 12675, 3–36."},"acknowledgement":"We would like express our gratitude to Georgia Avarikioti, Daniel Perez and Dominik Harz for helpful comments and feedback on earlier versions of this manuscript. We also thank Nicholas Stifter, Aljosha Judmayer, Philipp Schindler, Edgar Weippl, and Alistair Stewart for insightful discussions during the early stages of this research. We also wish to thank the anonymous reviewers for their valuable comments that helped improve the presentation of our results. This research was funded by Bridge 1 858561 SESC; Bridge 1 864738 PR4DLT (all FFG); the Christian Doppler Laboratory for Security and Quality Improvement in the Production System Lifecycle (CDL-SQI); the competence center SBA-K1 funded by COMET; Chaincode Labs through the project SLN: Scalability for the Lightning Network; and by the Austrian Science Fund (FWF) through the Meitner program (project M-2608). Mustafa Al-Bassam is funded by a scholarship from the Alan Turing Institute. Alexei Zamyatin conducted the early stages of this work during his time at SBA Research, and was supported by a Binance Research Fellowship.","year":"2021","isi":1,"day":"23","oa_version":"Preprint","status":"public","_id":"10325","fulldoi":"https://doi.org/10.1007/978-3-662-64331-0_1","date_published":"2021-10-23T00:00:00Z","abstract":[{"lang":"eng","text":"Since the inception of Bitcoin, a plethora of distributed ledgers differing in design and purpose has been created. While by design, blockchains provide no means to securely communicate with external systems, numerous attempts towards trustless cross-chain communication have been proposed over the years. Today, cross-chain communication (CCC) plays a fundamental role in cryptocurrency exchanges, scalability efforts via sharding, extension of existing systems through sidechains, and bootstrapping of new blockchains. Unfortunately, existing proposals are designed ad-hoc for specific use-cases, making it hard to gain confidence in their correctness and composability. We provide the first systematic exposition of cross-chain communication protocols. We formalize the underlying research problem and show that CCC is impossible without a trusted third party, contrary to common beliefs in the blockchain community. With this result in mind, we develop a framework to design new and evaluate existing CCC protocols, focusing on the inherent trust assumptions thereof, and derive a classification covering the field of cross-chain communication to date. We conclude by discussing open challenges for CCC research and the implications of interoperability on the security and privacy of blockchains."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-08-11T08:05:29Z","alternative_title":["LNCS"]},{"date_created":"2021-12-16T13:23:27Z","article_processing_charge":"No","quality_controlled":"1","department":[{"_id":"ElKo"}],"language":[{"iso":"eng"}],"publication_status":"published","page":"1751–1767","month":"10","doi":"10.1145/3372297.3423364","main_file_link":[{"url":"https://eprint.iacr.org/2019/1015","open_access":"1"}],"type":"conference","publication_identifier":{"isbn":["978-1-4503-7089-9"]},"title":"Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures","oa":1,"scopus_import":"1","conference":{"location":"Virtual, United States","end_date":"2020-11-13","name":"CCS: Conference on Computer and Communications Security","start_date":"2020-11-09"},"author":[{"id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","last_name":"Kokoris Kogias","full_name":"Kokoris Kogias, Eleftherios","first_name":"Eleftherios"},{"last_name":"Malkhi","full_name":"Malkhi, Dahlia","first_name":"Dahlia"},{"first_name":"Alexander","last_name":"Spiegelman","full_name":"Spiegelman, Alexander"}],"publication":"Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security","external_id":{"isi":["000768470400104"]},"oa_version":"Preprint","status":"public","_id":"10556","acknowledgement":"We would like to thank Ittai Abraham for the discussions and guidance during the initial conception of the project, especially for HAVSS. Furthermore, we would like to thank the anonymous reviewers for pointing out the relevance of this work to MPC protocols.","year":"2020","citation":{"short":"E. Kokoris Kogias, D. Malkhi, A. Spiegelman, in:, Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, Association for Computing Machinery, 2020, pp. 1751–1767.","mla":"Kokoris Kogias, Eleftherios, et al. “Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures.” <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i>, Association for Computing Machinery, 2020, pp. 1751–1767, doi:<a href=\"https://doi.org/10.1145/3372297.3423364\">10.1145/3372297.3423364</a>.","chicago":"Kokoris Kogias, Eleftherios, Dahlia Malkhi, and Alexander Spiegelman. “Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures.” In <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i>, 1751–1767. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.1145/3372297.3423364\">https://doi.org/10.1145/3372297.3423364</a>.","ieee":"E. Kokoris Kogias, D. Malkhi, and A. Spiegelman, “Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures,” in <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i>, Virtual, United States, 2020, pp. 1751–1767.","apa":"Kokoris Kogias, E., Malkhi, D., &#38; Spiegelman, A. (2020). Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures. In <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i> (pp. 1751–1767). Virtual, United States: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3372297.3423364\">https://doi.org/10.1145/3372297.3423364</a>","ama":"Kokoris Kogias E, Malkhi D, Spiegelman A. Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures. In: <i>Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security</i>. Association for Computing Machinery; 2020:1751–1767. doi:<a href=\"https://doi.org/10.1145/3372297.3423364\">10.1145/3372297.3423364</a>","ista":"Kokoris Kogias E, Malkhi D, Spiegelman A. 2020. Asynchronous distributed key generation for computationally-secure randomness, consensus, and threshold signatures. Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. CCS: Conference on Computer and Communications Security, 1751–1767."},"publisher":"Association for Computing Machinery","day":"30","isi":1,"fulldoi":"https://doi.org/10.1145/3372297.3423364","date_published":"2020-10-30T00:00:00Z","date_updated":"2025-07-10T11:49:52Z","abstract":[{"lang":"eng","text":"In this paper, we present the first Asynchronous Distributed Key Generation (ADKG) algorithm which is also the first distributed key generation algorithm that can generate cryptographic keys with a dual (f,2f+1)-threshold (where f is the number of faulty parties). As a result, using our ADKG we remove the trusted setup assumption that the most scalable consensus algorithms make. In order to create a DKG with a dual (f,2f+1)- threshold we first answer in the affirmative the open question posed by Cachin et al. [7] on how to create an Asynchronous Verifiable Secret Sharing (AVSS) protocol with a reconstruction threshold of f+1<k łe 2f+1, which is of independent interest. Our High-threshold-AVSS (HAVSS) uses an asymmetric bivariate polynomial to encode the secret. This enables the reconstruction of the secret only if a set of k nodes contribute while allowing an honest node that did not participate in the sharing phase to recover his share with the help of f+1 honest parties. Once we have HAVSS we can use it to bootstrap scalable partially synchronous consensus protocols, but the question on how to get a DKG in asynchrony remains as we need a way to produce common randomness. The solution comes from a novel Eventually Perfect Common Coin (EPCC) abstraction that enables the generation of a common coin from n concurrent HAVSS invocations. EPCC's key property is that it is eventually reliable, as it might fail to agree at most f times (even if invoked a polynomial number of times). Using EPCC we implement an Eventually Efficient Asynchronous Binary Agreement (EEABA) which is optimal when the EPCC agrees and protects safety when EPCC fails. Finally, using EEABA we construct the first ADKG which has the same overhead and expected runtime as the best partially-synchronous DKG (O(n4) words, O(f) rounds). As a corollary of our ADKG, we can also create the first Validated Asynchronous Byzantine Agreement (VABA) that does not need a trusted dealer to setup threshold signatures of degree n-f. Our VABA has an overhead of expected O(n2) words and O(1) time per instance, after an initial O(n4) words and O(f) time bootstrap via ADKG."}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"related_material":{"link":[{"relation":"earlier_version","url":"https://patents.google.com/patent/US20180359096A1/en"}]},"ipn":"10581613","date_created":"2021-12-16T13:28:59Z","article_processing_charge":"No","applicant":["Ecole Polytechnique Federale de Lausanne"],"day":"03","month":"03","citation":{"apa":"Ford, B., Gasse, L., Kokoris Kogias, E., &#38; Jovanovic, P. (2020). Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods.","ieee":"B. Ford, L. Gasse, E. Kokoris Kogias, and P. Jovanovic, “Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods.” 2020.","ama":"Ford B, Gasse L, Kokoris Kogias E, Jovanovic P. Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods. 2020.","ista":"Ford B, Gasse L, Kokoris Kogias E, Jovanovic P. 2020. Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods.","mla":"Ford, Bryan, et al. <i>Cryptographically Verifiable Data Structure Having Multi-Hop Forward and Backwards Links and Associated Systems and Methods</i>. 2020.","short":"B. Ford, L. Gasse, E. Kokoris Kogias, P. Jovanovic, (2020).","chicago":"Ford, Bryan, Linus Gasse, Eleftherios Kokoris Kogias, and Philipp Jovanovic. “Cryptographically Verifiable Data Structure Having Multi-Hop Forward and Backwards Links and Associated Systems and Methods,” 2020."},"year":"2020","status":"public","_id":"10557","application_date":"2017-06-09","department":[{"_id":"ElKo"}],"oa_version":"Published Version","ipc":" H04L9/3247 ; G06Q20/29 ; G06Q20/382 ; H04L9/3236","extern":"1","date_published":"2020-03-03T00:00:00Z","title":"Cryptographically verifiable data structure having multi-hop forward and backwards links and associated systems and methods","oa":1,"main_file_link":[{"url":"https://patents.google.com/patent/US10581613B2/en","open_access":"1"}],"type":"patent","publication_date":"2020-03-03","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","author":[{"first_name":"Bryan","full_name":"Ford, Bryan","last_name":"Ford"},{"last_name":"Gasse","full_name":"Gasse, Linus","first_name":"Linus"},{"full_name":"Kokoris Kogias, Eleftherios","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","last_name":"Kokoris Kogias","first_name":"Eleftherios"},{"first_name":"Philipp","last_name":"Jovanovic","full_name":"Jovanovic, Philipp"}],"abstract":[{"lang":"eng","text":"Data storage and retrieval systems, methods, and computer-readable media utilize a cryptographically verifiable data structure that facilitates verification of a transaction in a decentralized peer-to-peer environment using multi-hop backwards and forwards links. Backward links are cryptographic hashes of past records. Forward links are cryptographic signatures of future records that are added retroactively to records once the target block has been appended to the data structure."}],"date_updated":"2021-12-21T10:04:50Z"},{"issue":"4","external_id":{"isi":["000658495400012"]},"intvolume":"        14","status":"public","_id":"9011","oa_version":"Published Version","isi":1,"day":"01","publisher":"Association for Computing Machinery","year":"2020","acknowledgement":"We thank Nicolas Gailly, Vincent Graf, Jean-Pierre Hubaux, Wouter Lueks, Massimo Marelli, Carmela Troncoso, Juan-Ramón Troncoso Pastoriza, Frédéric Pont, and Sandra Siby for their valuable feedback. This project was supported in part by the ETH domain under PHRT grant #2017−201, and by the AXA Research Fund, Byzgen, DFINITY, and the Swiss Data Science Center (SDSC).","citation":{"chicago":"Kokoris Kogias, Eleftherios, Enis Ceyhun Alp, Linus Gasser, Philipp Jovanovic, Ewa Syta, and Bryan Ford. “CALYPSO: Private Data Management for Decentralized Ledgers.” <i>Proceedings of the VLDB Endowment</i>. Association for Computing Machinery, 2020. <a href=\"https://doi.org/10.14778/3436905.3436917\">https://doi.org/10.14778/3436905.3436917</a>.","mla":"Kokoris Kogias, Eleftherios, et al. “CALYPSO: Private Data Management for Decentralized Ledgers.” <i>Proceedings of the VLDB Endowment</i>, vol. 14, no. 4, Association for Computing Machinery, 2020, pp. 586–99, doi:<a href=\"https://doi.org/10.14778/3436905.3436917\">10.14778/3436905.3436917</a>.","short":"E. Kokoris Kogias, E.C. Alp, L. Gasser, P. Jovanovic, E. Syta, B. Ford, Proceedings of the VLDB Endowment 14 (2020) 586–599.","ista":"Kokoris Kogias E, Alp EC, Gasser L, Jovanovic P, Syta E, Ford B. 2020. CALYPSO: Private data management for decentralized ledgers. Proceedings of the VLDB Endowment. 14(4), 586–599.","ama":"Kokoris Kogias E, Alp EC, Gasser L, Jovanovic P, Syta E, Ford B. CALYPSO: Private data management for decentralized ledgers. <i>Proceedings of the VLDB Endowment</i>. 2020;14(4):586-599. doi:<a href=\"https://doi.org/10.14778/3436905.3436917\">10.14778/3436905.3436917</a>","ieee":"E. Kokoris Kogias, E. C. Alp, L. Gasser, P. Jovanovic, E. Syta, and B. Ford, “CALYPSO: Private data management for decentralized ledgers,” <i>Proceedings of the VLDB Endowment</i>, vol. 14, no. 4. Association for Computing Machinery, pp. 586–599, 2020.","apa":"Kokoris Kogias, E., Alp, E. C., Gasser, L., Jovanovic, P., Syta, E., &#38; Ford, B. (2020). CALYPSO: Private data management for decentralized ledgers. <i>Proceedings of the VLDB Endowment</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.14778/3436905.3436917\">https://doi.org/10.14778/3436905.3436917</a>"},"date_published":"2020-12-01T00:00:00Z","ddc":["000"],"tmp":{"image":"/images/cc_by_nc_nd.png","short":"CC BY-NC-ND (4.0)","legal_code_url":"https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode","name":"Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0)"},"fulldoi":"https://doi.org/10.14778/3436905.3436917","article_type":"original","date_updated":"2026-06-18T19:40:17Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"Distributed ledgers provide high availability and integrity, making them a key enabler for practical and secure computation of distributed workloads among mutually distrustful parties. Many practical applications also require strong confidentiality, however. This work enhances permissioned and permissionless blockchains with the ability to manage confidential data without forfeiting availability or decentralization. The proposed Calypso architecture addresses two orthogonal challenges confronting modern distributed ledgers: (a) enabling the auditable management of secrets and (b) protecting distributed computations against arbitrage attacks when their results depend on the ordering and secrecy of inputs.\r\n\r\nCalypso introduces on-chain secrets, a novel abstraction that enforces atomic deposition of an auditable trace whenever users access confidential data. Calypso provides user-controlled consent management that ensures revocation atomicity and accountable anonymity. To enable permissionless deployment, we introduce an incentive scheme and provide users with the option to select their preferred trustees. We evaluated our Calypso prototype with a confidential document-sharing application and a decentralized lottery. Our benchmarks show that transaction-processing latency increases linearly in terms of security (number of trustees) and is in the range of 0.2 to 8 seconds for 16 to 128 trustees.","lang":"eng"}],"article_processing_charge":"No","date_created":"2021-01-17T23:01:13Z","quality_controlled":"1","page":"586-599","publication_status":"published","language":[{"iso":"eng"}],"department":[{"_id":"ElKo"}],"volume":14,"month":"12","license":"https://creativecommons.org/licenses/by-nc-nd/4.0/","title":"CALYPSO: Private data management for decentralized ledgers","oa":1,"publication_identifier":{"eissn":["2150-8097"]},"type":"journal_article","main_file_link":[{"open_access":"1","url":"https://dl.acm.org/doi/10.14778/3436905.3436917"}],"doi":"10.14778/3436905.3436917","corr_author":"1","scopus_import":"1","publication":"Proceedings of the VLDB Endowment","author":[{"first_name":"Eleftherios","orcid":"0000-0002-8827-3382","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","last_name":"Kokoris Kogias","full_name":"Kokoris Kogias, Eleftherios"},{"first_name":"Enis Ceyhun","last_name":"Alp","full_name":"Alp, Enis Ceyhun"},{"full_name":"Gasser, Linus","last_name":"Gasser","first_name":"Linus"},{"first_name":"Philipp","full_name":"Jovanovic, Philipp","last_name":"Jovanovic"},{"last_name":"Syta","full_name":"Syta, Ewa","first_name":"Ewa"},{"first_name":"Bryan","last_name":"Ford","full_name":"Ford, Bryan"}]},{"external_id":{"cryptoeprintid":["2019/1015"]},"date_created":"2020-08-26T12:18:00Z","article_processing_charge":"No","citation":{"ista":"Kokoris Kogias E, Spiegelman A, Malkhi D, Abraham I. Bootstrapping consensus without trusted setup: Fully asynchronous distributed key generation. Cryptology ePrint Archive, 2019/1015.","ama":"Kokoris Kogias E, Spiegelman A, Malkhi D, Abraham I. Bootstrapping consensus without trusted setup: Fully asynchronous distributed key generation. <i>Cryptology ePrint Archive</i>.","ieee":"E. Kokoris Kogias, A. Spiegelman, D. Malkhi, and I. Abraham, “Bootstrapping consensus without trusted setup: Fully asynchronous distributed key generation,” <i>Cryptology ePrint Archive</i>. .","apa":"Kokoris Kogias, E., Spiegelman, A., Malkhi, D., &#38; Abraham, I. (n.d.). Bootstrapping consensus without trusted setup: Fully asynchronous distributed key generation. <i>Cryptology ePrint Archive</i>.","chicago":"Kokoris Kogias, Eleftherios, Alexander Spiegelman, Dahlia Malkhi, and Ittai Abraham. “Bootstrapping Consensus without Trusted Setup: Fully Asynchronous Distributed Key Generation.” <i>Cryptology EPrint Archive</i>, n.d.","mla":"Kokoris Kogias, Eleftherios, et al. “Bootstrapping Consensus without Trusted Setup: Fully Asynchronous Distributed Key Generation.” <i>Cryptology EPrint Archive</i>, 2019/1015.","short":"E. Kokoris Kogias, A. Spiegelman, D. Malkhi, I. Abraham, Cryptology EPrint Archive (n.d.)."},"year":"2019","das_tickbox":"1","day":"10","month":"09","department":[{"_id":"ElKo"}],"language":[{"iso":"eng"}],"publication_status":"submitted","oa_version":"Preprint","_id":"8305","status":"public","OA_place":"repository","article_number":"2019/1015","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2019/1015"}],"type":"preprint","date_published":"2019-09-10T00:00:00Z","title":"Bootstrapping consensus without trusted setup: Fully asynchronous distributed key generation","OA_type":"green","oa":1,"cryptoeprintid":1,"author":[{"first_name":"Eleftherios","orcid":"0000-0002-8827-3382","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30","last_name":"KOKORIS KOGIAS","full_name":"KOKORIS KOGIAS, Eleftherios"},{"first_name":"Alexander","full_name":"Spiegelman, Alexander","last_name":"Spiegelman"},{"first_name":"Dahlia","last_name":"Malkhi","full_name":"Malkhi, Dahlia"},{"first_name":"Ittai","full_name":"Abraham, Ittai","last_name":"Abraham"}],"abstract":[{"text":"In this paper, we present the first fully asynchronous distributed key generation (ADKG) algorithm as well as the first distributed key generation algorithm that can create keys with a dual (f,2f+1)−threshold that are necessary for scalable consensus (which so far needs a trusted dealer assumption). In order to create a DKG with a dual (f,2f+1)− threshold we first answer in the affirmative the open question posed by Cachin et al. how to create an AVSS protocol with recovery thresholds f+1<k≤2f+1, which is of independent interest. Our High-threshold-AVSS (HAVSS) uses an asymmetric bi-variate polynomial, where the secret shared is hidden from any set of k nodes but an honest node that did not participate in the sharing phase can still recover his share with only n−2f shares, hence be able to contribute in the secret reconstruction. Another building block for ADKG is a novel Eventually Perfect Common Coin (EPCC) abstraction and protocol that enables the participants to create a common coin that might fail to agree at most f+1 times (even if invoked a polynomial number of times). Using EPCC we implement an Eventually Efficient Asynchronous Binary Agreement (EEABA) in which each instance takes O(n2) bits and O(1) rounds in expectation, except for at most f+1 instances which may take O(n4) bits and O(n) rounds in total. Using EEABA we construct the first fully Asynchronous Distributed Key Generation (ADKG) which has the same overhead and expected runtime as the best partially-synchronous DKG (O(n4) words, O(n) rounds). As a corollary of our ADKG we can also create the first Validated Asynchronous Byzantine Agreement (VABA) in the authenticated setting that does not need a trusted dealer to setup threshold signatures of degree n−f. Our VABA has an overhead of expected O(n2) words and O(1) time per instance after an initial O(n4) words and O(n) time bootstrap via ADKG.","lang":"eng"}],"publication":"Cryptology ePrint Archive","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","date_updated":"2026-07-22T06:28:46Z"}]