区块链上的零知识证明技术及其典型算法、工具综述

doi:10.19788/j.issn.2096-6369.200002

Abstract

Abstract:

In the context of the increasing importance of data security and privacy protection, Zero-Knowledge Proofs (ZKPs) have provided a powerful tool for protecting privacy. This article comprehensively discusses the technology of zero-knowledge proofs and their application in modern cryptography. First, the article introduces the basic concepts of zero-knowledge proofs, as well as different types of ZKPs such as Snarks and Starks, along with their technical characteristics and application scenarios. In particular, the article conducts an in-depth study of ZK-Snarks. At the same time, the article also discusses other proof mechanisms such as ZK-Stark and Bulletproofs, comparing their differences in design and performance. Then, it focuses on the application of ZKPs in the blockchain environment and analyzes the related tools for writing zero-knowledge proofs. Finally, it points out some potential problems and future research directions in the field of zero-knowledge proofs.

Key words: zero-knowledge proof, privacy protection, blockchain applications

WAN Wei, LIU JianWei, LONG Chun, LI Jing, YANG Fan, FU YuHao, YUAN ZiMeng. An Overview of Zero-Knowledge Proof Technology and Its Typical Algorithms and Tools[J].Journal of Agricultural Big Data, 2024, 6(2): 205-219.

Figures/Tables 1

References 63

[1]	Nakamoto S. Bitcoin: A peer-to-peer electronic cash system[J]. Computer Science, 2008. DOI:10.2139/ssrn.3440802.
[2]	Buterin V. A next-generation smart contract and decentralized application platform[J]. White Paper, 2014, 3(37): 2-1.
[3]	Badreddine W, Zhang K, Talhi C. Monetization using blockchains for IoT data marketplace[C]// 2020 IEEE International Conference on Blockchain and Cryptocurrency. IEEE, 2020: 1-9. DOI:10.1109/ICBC48266.2020.9169424.
[4]	Rivest R L, Adleman L, Dertouzos M L. On data banks and privacy homomorphisms[J]. Foundations of Secure Computation, 1978, 4(11): 169-180.
[5]	Rivest R L, Shamir A, Tauman Y. How to leak a secret[C]// Advances in Cryptology—ASIACRYPT 2001: 7th International Conference on the Theory and Application of Cryptology and Information Security Gold Coast, Australia, December 9-13, 2001 Proceedings 7. Springer Berlin Heidelberg, 2001: 552-565.
[6]	Yao A C. Protocols for secure computations[C]// 23rd Annual Symposium on Foundations of Computer Science.IEEE, 1982: 160-164.
[7]	李一聪, 周宽久, 王梓仲. 基于零知识证明的区块链隐私保护研究[J]. 空间控制技术与应用, 2022, 48(1):44-52.
[8]	Goldwasser S, Micali S, Rackoff C. The knowledge complexity of interactive proof systems[J]. SIAM Journal on Computing, 1989, 18(1): 186-208.
[9]	Ben-Sasson E, Bentov I, Horesh Y, et al. Scalable zero knowledge with no trusted setup[C]// Advances in Cryptology-CRYPTO 2019: 39th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2019, Proceedings, Part III 39. Springer International Publishing, 2019: 701-732.
[10]	Gong Y, Jin Y, Li Y, et al. Analysis and comparison of the main zero-knowledge proof scheme[C]// 2022 International Conference on Big Data, Information and Computer Network (BDICN). IEEE, 2022: 366-372.
[11]	Bünz B, Bootle J, Boneh D, et al. Bulletproofs: Short proofs for confidential transactions and more[C]// 2018 IEEE symposium on security and privacy (SP). IEEE, 2018: 315-334.
[12]	Goldreich O. Foundations of Cryptography, Volume 2[M]. Cambridge: Cambridge University Press, 2004.
[13]	Nitulescu A. zk-SNARKs: a gentle introduction[J]. Computer Science, 2020.
[14]	李威翰, 张宗洋, 周子博. 简洁非交互零知识证明综述[J]. 密码学报, 2022, 9(3): 379-447. doi: 10.13868/j.cnki.jcr.000525
[15]	Babai L, Fortnow L, Levin L A, et al. Checking computations in polylogarithmic time[C]// Proceedings of the twenty-third annual ACM symposium on Theory of computing[J]. Computer Science, 1991: 21-32.
[16]	Arora S, Safra S. Probabilistic checking of proofs: A new characterization of NP[J]. Journal of the ACM (JACM), 1998, 45(1): 70-122.
[17]	Bellare M, Rogaway P. Random oracles are practical: A paradigm for designing efficient protocols[C]// Proceedings of the 1st ACM Conference on Computer and Communications Security. 1993: 62-73.
[18]	Fiat A, Shamir A. How to prove yourself: Practical solutions to identification and signature problems[C]// Conference on the theory and application of cryptographic techniques. Berlin, Heidelberg: Springer Berlin Heidelberg, 1986: 186-194.
[19]	Kilian J. A note on efficient zero-knowledge proofs and arguments[C] // Proceedings of the twenty-fourth annual ACM symposium on Theory of computing. 1992: 723-732.
[20]	Di Crescenzo G, Lipmaa H. Succinct NP proofs from an extractability assumption[C]// Logic and Theory of Algorithms:4th Conference on Computability in Europe, CiE 2008, Athens, Greece, June 15-20, 2008 Proceedings 4. Springer Berlin Heidelberg, 2008: 175-185.
[21]	Micali S. CS proofs[C]// Proceedings 35th Annual Symposium on Foundations of Computer Science. IEEE, 1994: 436-453.
[22]	Valiant P. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency[C]// Theory of Cryptography: Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19-21, 2008. Proceedings 5. Springer Berlin Heidelberg, 2008: 1-18.
[23]	Giacomelli I, Madsen J, Orlandi C. {ZKBoo}: Faster {Zero- Knowledge} for Boolean Circuits[C]// 25th USENIX Security Symposium (USENIX Security 16). 2016: 1069-1083.
[24]	Chase M, Derler D, Goldfeder S, et al. Post-quantum zero-knowledge and signatures from symmetric-key primitives[C]// Proceedings of the 2017 ACM Sigsac Conference on Computer and Communications Security. 2017: 1825-1842.
[25]	Bitansky N, Canetti R, Chiesa A, et al. The hunting of the SNARK[J]. Journal of Cryptology, 2017, 30(4): 989-1066.
[26]	Sasson E B, Chiesa A, Garman C, et al. Zerocash: Decentralized anonymous payments from bitcoin[C]// 2014 IEEE symposium on security and privacy. IEEE, 2014: 459-474.
[27]	Groth J. Short pairing-based non-interactive zero-knowledge arguments[C]// Advances in Cryptology-ASIACRYPT 2010: 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 5-9, 2010. Proceedings 16. Springer Berlin Heidelberg, 2010: 321-340.
[28]	Lipmaa H. Progression-free sets and sublinear pairing-based non- interactive zero-knowledge arguments[C]// Theory of Cryptography:9th Theory of Cryptography Conference, TCC 2012, Taormina, Sicily, Italy, March 19-21, 2012. Proceedings 9. Springer Berlin Heidelberg, 2012: 169-189.
[29]	Gennaro R, Gentry C, Parno B, et al. Quadratic span programs and succinct NIZKs without PCPs[C]// Advances in Cryptology- EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings 32. Springer Berlin Heidelberg, 2013: 626-645.
[30]	Karchmer M, Wigderson A. On span programs[C]// [1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference. IEEE, 1993: 102-111.
[31]	Lipmaa H. Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes[C]// Advances in Cryptology-ASIACRYPT 2013: 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, December 1-5, 2013, Proceedings, Part I 19. Springer Berlin Heidelberg, 2013: 41-60.
[32]	Parno B, Howell J, Gentry C, et al. Pinocchio: Nearly practical verifiable computation[J]. Communications of the ACM, 2016, 59(2): 103-112.
[33]	Danezis G, Fournet C, Groth J, et al. Square span programs with applications to succinct NIZK arguments[C]// International Conference on the Theory and Application of Cryptology and Information Security. Berlin, Heidelberg: Springer Berlin Heidelberg, 2014: 532-550.
[34]	Groth J, Maller M. Snarky signatures: Minimal signatures of knowledge from simulation-extractable SNARKs[C]// Annual International Cryptology Conference. Cham: Springer International Publishing, 2017: 581-612.
[35]	Groth J. On the size of pairing-based non-interactive arguments[C] // Advances in Cryptology-EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35. Springer Berlin Heidelberg, 2016: 305-326.
[36]	Shoup V. Lower bounds for discrete logarithms and related problems[C]// Advances in Cryptology-EUROCRYPT’97:International Conference on the Theory and Application of Cryptographic Techniques Konstanz, Germany, May 11-15, 1997 Proceedings 16. Springer Berlin Heidelberg, 1997: 256-266.
[37]	Maurer U. Abstract models of computation in cryptography[C] // Cryptography and Coding:10th IMA International Conference, Cirencester, UK, December 19-21, 2005. Proceedings 10. Springer Berlin Heidelberg, 2005: 1-12.
[38]	Ben-Sasson E, Chiesa A, Green M, et al. Secure sampling of public parameters for succinct zero knowledge proofs[C]// 2015 IEEE Symposium on Security and Privacy. IEEE, 2015: 287-304.
[39]	Bowe S, Gabizon A, Miers I. Scalable multi-party computation for zk-SNARK parameters in the random beacon model[J]. Cryptology ePrint Archive, 2017.
[40]	Groth J, Kohlweiss M, Maller M, et al. Updatable and universal common reference strings with applications to zk-SNARKs[C] // Annual International Cryptology Conference. Cham: Springer International Publishing, 2018: 698-728.
[41]	Maller M, Bowe S, Kohlweiss M, et al. Sonic: Zero-knowledge SNARKs from linear-size universal and updatable structured reference strings[C]// Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019: 2111-2128.
[42]	Gabizon A, Williamson Z J, Ciobotaru O. Plonk: Permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge[J]. Cryptology ePrint Archive, 2019.
[43]	https://github.com/AztecProtocol
[44]	Schwartz J T. Fast probabilistic algorithms for verification of polynomial identities[J]. Journal of the ACM (JACM), 1980, 27(4): 701-717.
[45]	Bootle J, Cerulli A, Chaidos P, et al. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting[C] // Advances in Cryptology-EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35. Springer Berlin Heidelberg, 2016: 327-357.
[46]	Bootle J, Cerulli A, Chaidos P, et al. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting[C]// Advances in Cryptology-EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35. Springer Berlin Heidelberg, 2016: 327-357.
[47]	Hoffmann M, Klooß M, Rupp A. Efficient zero-knowledge arguments in the discrete log setting, revisited[C]// Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. 2019: 2093-2110.
[48]	Daza V, Ràfols C, Zacharakis A. Updateable inner product argument with logarithmic verifier and applications[C]// Public-Key Cryptography- PKC 2020: 23rd IACR International Conference on Practice and Theory of Public-Key Cryptography, Edinburgh, UK, May 4-7, 2020, Proceedings, Part I 23. Springer International Publishing, 2020: 527-557.
[49]	宋英齐, 冯荣权. 零知识证明在区块链中的应用综述[J]. 广州大学学报(自然科学版), 2022, 21(04):21-36.
[50]	https://www.getmonero.org/
[51]	https://github.com/scroll-tech
[52]	https://github.com/starknet-io
[53]	https://github.com/taikoxyz
[54]	https://github.com/succinctlabs
[55]	https://github.com/Electron-Labs
[56]	https://www.zkibc.com/
[57]	https://github.com/topics/polyhedra
[58]	https://zkbridge.com/
[59]	Setty S. Spartan: Efficient and general-purpose zkSNARKs without trusted setup[C]// Annual International Cryptology Conference. Cham: Springer International Publishing, 2020: 704-737.
[60]	Xie T, Zhang Y, Song D. Orion: Zero knowledge proof with linear prover time[C]// Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2022: 299-328.
[61]	Yang K, Sarkar P, Weng C, et al. Quicksilver: Efficient and affordable zero-knowledge proofs for circuits and polynomials over any field[C]// Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. 2021: 2986-3001.
[62]	Lyubashevsky V, Nguyen N K, Plançon M. Lattice-based zero- knowledge proofs and applications: shorter, simpler, and more general[C]// Annual International Cryptology Conference. Cham: Springer Nature Switzerland, 2022: 71-101.
[63]	Lu T, Wei C, Yu R, et al. Cuzk: Accelerating zero-knowledge proof with a faster parallel multi-scalar multiplication algorithm on gpus[J]. Cryptology ePrint Archive, 2022.

	SNARKs	STARKs	Bulletproofs
证明者复杂度	O(N * log(N))	O(N * poly-log(N))	O(N * log(N))
验证者复杂度	~O(1)	O(poly-log(N))	O(N)
通信复杂度	~O(1)	O(poly-log(N))	O(log(N))
需要可信设置	是	否	否
后量子安全	否	是	否

An Overview of Zero-Knowledge Proof Technology and Its Typical Algorithms and Tools

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 1

References 63

Related Articles 0

Metrics

Comments

Recommended 0