Distributed Key Generation with Smart Contracts using zk-SNARKs
Authors: 
Michael Sober, Max Kobelt, Giulia Scaffino, Dominik Kaaser, Stefan SchulteAuthors Info & Claims
Pages 231 - 240
Abstract
Distributed Key Generation (DKG) is an extensively researched topic as it is fundamental to threshold cryptosystems. Emerging technologies such as blockchains benefit massively from applying threshold cryptography in consensus protocols, randomness beacons, and threshold signatures. However, blockchains and smart contracts also enable further improvements of DKG protocols by providing a decentralized computation and communication platform. For that reason, we propose a DKG protocol that uses smart contracts to ensure the correct execution of the protocol, allow dynamic participation, and provide crypto-economic incentives to encourage honest behavior. The DKG protocol uses a dispute and key derivation mechanism based on Zero-Knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs) to reduce the costs of applying smart contracts by moving the computations off-chain, where the smart contract only verifies the correctness of the computation.
References
[1]
Ittai Abraham, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu. 2021. Reaching consensus for asynchronous distributed key generation. In 2021 ACM Symposium on Principles of Distributed Computing. ACM, 363--373.
[2]
Martin Albrecht, Lorenzo Grassi, Christian Rechberger, Arnab Roy, and Tyge Tiessen. 2016. MiMC: Efficient encryption and cryptographic hashing with minimal multiplicative complexity. In International Conference on the Theory and Application of Cryptology and Information Security. Springer, 191--219.
[3]
Marta Bellés-Muñoz, Barry Whitehat, Jordi Baylina, Vanesa Daza, and Jose Luis Muñoz-Tapia. 2021. Twisted Edwards elliptic curves for zero-knowledge circuits. Mathematics 9, 23 (2021), 3022.
[4]
Marianna Belotti, Nikola Božić, Guy Pujolle, and Stefano Secci. 2019. A vademecum on blockchain technologies: When, which, and how. IEEE Communications Surveys & Tutorials 21, 4 (2019), 3796--3838.
[5]
Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, and Michael Riabzev. 2019. Scalable zero knowledge with no trusted setup. In 39th Annual International Cryptology Conference. Springer, 701--732.
[6]
Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. 2014. Succinct {Non-Interactive} zero knowledge for a von neumann architecture. In 23rd USENIX Security Symposium. USENIX Association, 781--796.
[7]
Joseph Bonneau, Izaak Meckler, Vanishree Rao, and Evan Shapiro. 2020. Mina: Decentralized Cryptocurrency at Scale. https://minaprotocol.com/wp-content/uploads/technicalWhitepaper.pdf Accessed: 2022-06-24.
[8]
Sean Bowe, Ariel Gabizon, and Matthew D Green. 2018. A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK. In International Conference on Financial Cryptography and Data Security. Springer, 64--77.
[9]
Sean Bowe, Ariel Gabizon, and Ian Miers. 2017. Scalable multi-party computation for zk-SNARK parameters in the random beacon model. Cryptology ePrint Archive (2017).
[10]
Tamara Brandstätter, Stefan Schulte, Jürgen Cito, and Michael Borkowski. 2020. Characterizing Efficiency Optimizations in Solidity Smart Contracts. In 2020 IEEE International Conference on Blockchain (Blockchain). 281--290.
[11]
Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. 2018. Bulletproofs: Short proofs for confidential transactions and more. In 2018 IEEE Symposium on Security and Privacy. IEEE, 315--334.
[12]
Benny Chor, Shafi Goldwasser, Silvio Micali, and Baruch Awerbuch. 1985. Verifiable secret sharing and achieving simultaneity in the presence of faults. In 26th Annual Symposium on Foundations of Computer Science. IEEE, 383--395.
[13]
Hong-Ning Dai, Zibin Zheng, and Yan Zhang. 2019. Blockchain for Internet of Things: A survey. IEEE Internet of Things 6, 5 (2019), 8076--8094.
[14]
Sourav Das, Thomas Yurek, Zhuolun Xiang, Andrew Miller, Lefteris Kokoris-Kogias, and Ling Ren. 2021. Practical asynchronous distributed key generation. Cryptology ePrint Archive (2021).
[15]
Marina Dehez-Clementi, Jérôme Lacan, Jean-Christophe Deneuville, Hassan Asghar, and Dali Kaafar. 2021. A Blockchain-enabled Anonymous-yet-Traceable Distributed Key Generation. In 2021 IEEE International Conference on Blockchain. IEEE, 257--265.
[16]
Yvo G Desmedt. 1994. Threshold cryptography. European Transactions on Telecommunications 5, 4 (1994), 449--458.
[17]
John R Douceur. 2002. The sybil attack. In International workshop on peer-to-peer systems. Springer, 251--260.
[18]
Jacob Eberhardt and Stefan Tai. 2018. Zokrates-scalable privacy-preserving off-chain computations. In 2018 IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData). IEEE, 1084--1091.
[19]
Paul Feldman. 1987. A practical scheme for non-interactive verifiable secret sharing. In 28th Annual Symposium on Foundations of Computer Science. IEEE, 427--438.
[20]
Rosario Gennaro, Stanisław Jarecki, Hugo Krawczyk, and Tal Rabin. 1999. Secure distributed key generation for discrete-log based cryptosystems. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 295--310.
[21]
Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. 2002. Revisiting the distributed key generation for discrete-log based Cryptosystems. RSA Security'03 (2002).
[22]
Rosario Gennaro, Stanislaw Jarecki, Hugo Krawczyk, and Tal Rabin. 2003. Secure applications of Pedersen's distributed key generation protocol. In Cryptographers' Track at the RSA Conference. Springer, 373--390.
[23]
Shafi Goldwasser, Silvio Micali, and Charles Rackoff. 1989. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 1 (1989), 186--208.
[24]
Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, and Markus Schofnegger. 2021. Poseidon: A New Hash Function for Zero-Knowledge Proof Systems. In 30th USENIX Security Symposium. USENIX Association, 519--535.
[25]
Jens Groth. 2016. On the size of pairing-based non-interactive arguments. In Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 305--326.
[26]
Daira Hopwood, Sean Bowe, Taylor Hornby, and Nathan Wilcox. 2016. Zcash Protocol Specication. https://raw.githubusercontent.com/zcash/zips/master/protocol/protocol.pdf Accessed: 2022-06-24.
[27]
Aniket Kate and Ian Goldberg. 2009. Distributed key generation for the internet. In 2009 29th IEEE International Conference on Distributed Computing Systems. IEEE, 119--128.
[28]
Aniket Kate, Yizhou Huang, and Ian Goldberg. 2012. Distributed key generation in the wild. Cryptology ePrint Archive (2012).
[29]
Jonathan Katz and Yehuda Lindell. 2020. Introduction to modern cryptography. CRC press.
[30]
Aggelos Kiayias, Alexander Russell, Bernardo David, and Roman Oliynykov. 2017. Ouroboros: A Provably Secure Proof-of-Stake Blockchain Protocol. In Annual International Cryptology Conference. Springer, 357--388.
[31]
Eleftherios Kokoris Kogias, Dahlia Malkhi, and Alexander Spiegelman. 2020. Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures. In 2020 ACM SIGSAC Conference on Computer and Communications Security. ACM, 1751--1767.
[32]
Benjamin Körbel, Marten Sigwart, Philip Frauenthaler, Michael Sober, and Stefan Schulte. 2021. Blockchain-based result verification for computation offloading. In International Conference on Service-Oriented Computing. Springer, 99--115.
[33]
Ahmed Kosba, Dimitrios Papadopoulos, Charalampos Papamanthou, and Dawn Song. 2020. {MIRAGE}: Succinct Arguments for Randomized Algorithms with Applications to Universal {zk-SNARKs}. In 29th USENIX Security Symposium (USENIX Security 20). 2129--2146.
[34]
Muhammad Baqer Mollah, Jun Zhao, Dusit Niyato, Kwok-Yan Lam, Xin Zhang, Amer MYM Ghias, Leong Hai Koh, and Lei Yang. 2020. Blockchain for future smart grid: A comprehensive survey. IEEE Internet of Things 8, 1 (2020), 18--43.
[35]
Satoshi Nakamoto. 2008. Bitcoin: A peer-to-peer electronic cash system. http://www.bitcoin.org/bitcoin.pdf Accessed 2022-07-02.
[36]
Wafa Neji, Kaouther Blibech, and Narjes Ben Rajeb. 2016. Distributed key generation protocol with a new complaint management strategy. Security and Communication Networks 9, 17 (2016), 4585--4595.
[37]
Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. 2013. Pinocchio: Nearly practical verifiable computation. In 2013 IEEE Symposium on Security and Privacy. IEEE, 238--252.
[38]
Torben Pryds Pedersen. 1991. Non-interactive and information-theoretic secure verifiable secret sharing. In Annual International Cryptology Conference. Springer, 129--140.
[39]
Torben Pryds Pedersen. 1991. A threshold cryptosystem without a trusted party. In Workshop on the Theory and Application of of Cryptographic Techniques. Springer, 522--526.
[40]
Tal Rabin and Michael Ben-Or. 1989. Verifiable secret sharing and multiparty protocols with honest majority. In Twenty-first Annual ACM Symposium on Theory of Computing. ACM, 73--85.
[41]
Philipp Schindler, Aljosha Judmayer, Nicholas Stifter, and Edgar Weippl. 2019. Ethdkg: Distributed key generation with ethereum smart contracts. Cryptology ePrint Archive (2019).
[42]
Berry Schoenmakers. 1999. A simple publicly verifiable secret sharing scheme and its application to electronic voting. In Annual International Cryptology Conference. Springer, 148--164.
[43]
Adi Shamir. 1979. How to share a secret. Commun. ACM 22, 11 (1979), 612--613.
[44]
Markus Stadler. 1996. Publicly verifiable secret sharing. In International Conference on the Theory and Applications of Cryptographic Techniques. Springer, 190--199.
[45]
Oliver Stengele, Markus Raiber, Jörn Müller-Quade, and Hannes Hartenstein. 2021. ETHTID: Deployable threshold information disclosure on Ethereum. In 2021 Third International Conference on Blockchain Computing and Applications. IEEE, 127--134.
[46]
Alan Szepieniec, Tomer Ashur, and Siemen Dhooghe. 2020. Rescue-prime: a standard specification (SoK). Cryptology ePrint Archive (2020).
[47]
Gavin Wood et al. 2014. Ethereum: A secure decentralised generalised transaction ledger. Ethereum project yellow paper 151, 2014 (2014), 1--32.
[48]
Liang Zhang, Feiyang Qiu, Feng Hao, and Haibin Kan. 2022. 1-Round Distributed Key Generation With Efficient Reconstruction Using Decentralized CP-ABE. IEEE Transactions on Information Forensics and Security 17 (2022), 894--907.
Index Terms
- Distributed Key Generation with Smart Contracts using zk-SNARKs
Recommendations
Reaching Consensus for Asynchronous Distributed Key Generation
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed ComputingWe give a protocol for Asynchronous Distributed Key Generation (A-DKG) that is optimally resilient (can withstand f < n over 3 faulty parties), has a constant expected number of rounds, has Õ (n3) expected communication complexity, and assumes only the ...
Asynchronous Distributed Key Generation for Computationally-Secure Randomness, Consensus, and Threshold Signatures.
CCS '20: Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications SecurityIn 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 ...
Fair Private Set Intersection Using Smart Contracts
Applied Cryptography and Network SecurityAbstractA mutual private set intersection protocol (PSI) allows two parties to find the intersection of their private sets without leaking any other information. A mutual PSI protocol achieves complete fairness if a malicious party cannot disadvantage the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 2023
1932 pages
ISBN:9781450395175
DOI:10.1145/3555776
- Conference Chairs:
- Jiman Hong,
- Maart Lanperne,
- Program Chairs:
- Juw Won Park,
- Tomas Cerny,
- Publication Chair:
- Hossain Shahriar
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 June 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Christian Doppler Research Association
Conference
SAC '23
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,650 of 6,669 submissions, 25%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 189Total Downloads
- Downloads (Last 12 months)66
- Downloads (Last 6 weeks)8
Reflects downloads up to 30 Nov 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in