区块链上的零知识证明技术及其典型算法、工具综述
收稿日期: 2024-01-30
录用日期: 2024-04-14
网络出版日期: 2024-07-03
基金资助
中国科学院网络安全和信息化专项(CAS-WX2022GC-04)
An Overview of Zero-Knowledge Proof Technology and Its Typical Algorithms and Tools
Received date: 2024-01-30
Accepted date: 2024-04-14
Online published: 2024-07-03
在数据安全和隐私保护日益重要的背景下，零知识证明（Zero-Knowledge Proofs, ZKPs）为保护隐私提供了强有力的工具，成为最具应用潜力的核心技术之一。本文综合探讨了零知识证明技术及其在区块链中的应用。首先，详细介绍了零知识证明的相关概念以及三种典型的技术，对ZK-Snarks进行了深入探讨，并讨论了ZK-Stark和Bulletproofs等其他证明机制，深入对比分析了各自的设计、技术特点、性能和应用场景的差异。在此基础上，重点介绍了ZKPs在区块链环境下的应用，并分析整理了编写零知识证明的相关工具，这些工具在提升具体应用的性能方面尤为重要。最后，指出了一些潜在的问题和未来的研究方向。
万巍, 刘建伟, 龙春, 李婧, 杨帆, 付豫豪, 袁梓萌 . 区块链上的零知识证明技术及其典型算法、工具综述[J]. 农业大数据学报, 2024 , 6(2) : 205 -219 . DOI: 10.19788/j.issn.2096-6369.200002
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.
| [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. |
| [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. |
/
| 〈 |
|
〉 |