Progress in Blockchain Solutions Based on Zero-Knowledge Proof

doi:10.3969/j.issn.1671-1122.2022.12.006

Abstract

Abstract:

Anonymity is an important characteristic in blockchain, with the application of blockchain in many fields such as traceability systems, identity authentication, auction system, and the Internet of things, the risk of blockchain de-anonymization has increased greatly, and the privacy protection and audit supervision of data need to be addressed. Researchers have found advanced encryption primitive zero-knowledge proof in the field of cryptography to enhance the anonymity and privacy of blockchain, and there have been breakthroughs. This paper started from the blockchain scheme of zero-knowledge proof, firstly explained the principle mechanism of zero-knowledge proof, then comprehensively analyzed and compared the relevant schemes, divided the three research priorities of privacy payment, privacy computing, and audit supervision, and analyzed the research objectives and progress of each scheme in three priorities, summarized the advantages and shortcomings of the existing work, and finally analyzed the existing limitations and challenges based on the current research status and elaborates the future research directions.

Key words: blockchain, zero-knowledge proof, encryption, anonymity, privacy

CLC Number:

TP309

WANG Yong, CHEN Lijie, ZHONG Meiling. Progress in Blockchain Solutions Based on Zero-Knowledge Proof[J]. Netinfo Security, 2022, 22(12): 47-56.

Figures/Tables 3

方案	原理机制	模型	优点
Zerocoin^[34]（2013）	ZKP	UTXO	内部不可链接性、防盗窃、防DoS攻击
Zerocash^[35]（2014）	zk-SNARKs	UTXO	隐藏所有交易信息，强匿名性
Hawk^[39]（2015）	MPC+zk-SNARKs	UTXO	自动编译加密协议、惩戒机制、独立隐私性
zKLedger^[47]（2018）	NIZK+MapReduce	UTXO	提供快速和丰富的审计，具有完整性
ZeeStar^[45]（2022）	NIZK+ 同态加密	账户	结合多方的私有价值和外部价值，性能良好且实用性强
FabZK^[48]（2019）	NIZK+ 范围证明	账户	支持自动审计、轻量级、可编程性强
Quisquis^[36]（2019）	DDH^[50]+NIZK	UTXO+账户	交易小、验证快、防盗、安全性高
Zether^[37]（2020）	zk-SNARKs	账户	隐藏交易金额、不可链接性
BlockMaze^[41]（2020）	NIZK+Bulletproofs	账户	支持多领域应用，平衡了透明性和隐私性
smartFHE^[44]（2021）	NIZK+Bulletproofs	账户	不会发生用户过载情况，执行速度快
Zexe^[42]（2020）	zk-SNARKs	UTXO	隐藏脚本和脚本本身的输入，实现了离线计算
Zkay^[40]（2019）	NIZK	账户	可编程智能合约，动态映射和公共循环的显式函数编码
zkrpChain^[49]（2020）	Bulletproofs	UTXO	证明可批量验证，适用于审计监管系统
Kachina^[43]（2021）	NIZK	账户	实现了智能合约的并发交互，预测用户信息泄露行为
方案	匿名性	可信设置	缺点
Zerocoin^[34]（2013）	较低	√	金额不能任意拆分和组合，不能隐藏交易金额和接收地址，验证时间长
Zerocash^[35]（2014）	较高	√	匿名交易花费时间长
Hawk^[39]（2015）	较高	√	打破了去中心化特性，合约成本高
zKLedger^[47]（2018）	中等	?	不能实现事务回滚，交易吞吐量低、延迟高
ZeeStar^[45]（2022）	中等	√	不适用实际应用场景，加密和解密成本较高
FabZK^[48]（2019）	较高	?	易发生无效交易、证明成本高、交易延迟高
Quisquis^[36]（2019）	较低	?	交易生成速度慢、通信成本高
Zether^[37]（2020）	较高	√	存储和时间成本高
BlockMaze^[41]（2020）	中等	?	交易成本较高，证明被接收之前需要锁定账户
smartFHE^[44]（2021）	中等	?	交易成本较高
Zexe^[42]（2020）	中等	√	生成证明成本高，只能面向密码学专业人员操作
Zkay^[40]（2019）	较低	√	操作复杂，容易使用户过载
zkrpChain^[49]（2020）	中等	?	易受到安全攻击
Kachina^[43]（2021）	较高	?	目前不适用于实际场景

References 62

[1]	NAKAMOTO S. Bitcoin: A Peer-to-Peer Electronic Cash System[EB/OL]. (2008-11-01) [2022-07-20]. https://bitcoin.org/bitcoin.pdf.
[2]	KELLERMANN T, MURPHY R. Modern Bank Heists 5.0[EB/OL]. (2022-05-06) [2022-07-20]. https://vmware.com/content/dam/learn/en/pdf/carbonblack/Modern%20Bank%20Heists%205.0%20Report.pdf.
[3]	ERMILOV D, PANOV M, YANOVICH Y. Automatic Bitcoin Address Clustering[C]// IEEE. 2017 16th IEEE International Conference on Machine Learning and Applications(ICMLA). New York: IEEE, 2017: 461-466.
[4]	NOETHER S, NOETHER S. Monero is not that Mysterious[EB/OL]. (2014-09-25) [2022-07-20]. https://web.getmonero.org/ru/resources/research-lab/pubs/MRL-0003.pdf.
[5]	HOPWOOD D, BOWE S, HORNBY T, et al. Zcash Protocol Specification[EB/OL]. (2014-05-18) [2022-07-20]. https://zips.z.cash/protocol/protocol.pdf.
[6]	GOLDWASSER S, MICALI S, RACKOFF C. The Knowledge Complexity of Interactive Proof Systems[C]// ACM. 17th ACM Symposium on Theory of Computing. New York: ACM, 1985: 291-304.
[7]	ABDALLA M, AN J H, BELLARE M, et al. From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security[C]// Springer. International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2002: 418-433.
[8]	BLUM M, FELDMAN P, MICALI S. Non-Interactive Zero-Knowledge and Its Applications[C]// ACM. The Twentieth Annual ACM Symposium on Theory of Computing. New York: ACM, 1988: 103-112.
[9]	MEIKLEJOHN S, POMAROLE M, JORDAN G, et al. A Fistful of Bitcoins: Characterizing Payments Among Men with no Names[C]// ACM. 2013 Conference on Internet Measurement Conference. New York: ACM, 2013: 127-140.
[10]	SHAO Jun, CAO Zhenfu. CCA-Secure Proxy Re-Encryption without Pairings[C]// Springer. International Workshop on Public Key Cryptography. Heidelberg: Springer, 2009: 357-376.
[11]	BOUDOT F. Efficient Proofs that A Committed Number Lies in An Interval[C]// Springer. International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2000: 431-444.
[12]	PEDERSEN T P. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing[C]// Springer. Annual International Cryptology Conference. Heidelberg: Springer, 1991: 129-140.
[13]	BÜNZ B, BOOTLE J, BONEH D, et al. Bulletproofs: Short Proofs for Confidential Transactions and More[C]// IEEE. 2018 IEEE Symposium on Security and Privacy(SP). New York: IEEE, 2018: 315-334.
[14]	WANG Ting. A Review of Secure Multiparty Computation Theory Research[J]. Information Security and Technology, 2014, 5(5): 41-44.
[15]	GROTH J. Short Pairing-Based Non-Interactive Zero-Knowledge Arguments[C]// Springer. International Conference on the Theory and Application of Cryptology and Information Security. Heidelberg: Springer, 2010: 321-340.
[16]	GENNARO R, GENTRY C, PARNO B, et al. Quadratic Span Programs and Succinct NIZKs without PCPs[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2013: 626-645.
[17]	SIMPSON W. The Quadratic Assignment Procedure(QAP)[C]// Stata. North American STATA Users’ Group Meeting. Texas: Stata, 2001: 12-13.
[18]	MALLER M, BOWE S, KOHLWEISS M, et al. Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings[C]// ACM. 2019 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2019: 2111-2128.
[19]	GABIZON A, WILLIAMSON Z J, CIOBOTARU O. Plonk: Permutations over Lagrange-Bases for Oecumenical Noninteractive Arguments of Knowledge[EB/OL]. (2019-08-21) [2022-07-20]. https://eprint.iacr.org/2019/953.pdf.
[20]	GROTH J. On the Size of Pairing-Based Non-Interactive Arguments[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2016: 305-326.
[21]	RAHIMI A, MA MADDAH-ALI. Multi-Party Proof Generation in Qap-Based zk-Snarks[C]// IEEE. 2021 IEEE Journal on Selected Areas in Information Theory. New York: IEEE, 2021: 931-941.
[22]	LIPMAA H. Succinct non-Interactive Zero Knowledge Arguments from Span Programs and Linear Error-Correcting Codes[C]// Springer. International Conference on the Theory and Application of Cryptology and Information Security. Heidelberg: Springer, 2013: 41-60.
[23]	BITANSKY N, CHIESA A, ISHAI Y, et al. Succinct non-Interactive Arguments via Linear Interactive Proofs[C]// Springer. Theory of Cryptography Conference. Heidelberg: Springer, 2013: 315-333.
[24]	PARNO B, HOWELL J, GENTRY C, et al. Pinocchio: Nearly Practical Verifiable Computation[C]// IEEE. 2013 IEEE Symposium on Security and Privacy. New York: IEEE, 2013: 238-252.
[25]	BEN-SASSON E, CHIESA A, GENKIN D, et al. SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge[C]// Springer. Annual Cryptology Conference. Heidelberg: Springer, 2013: 90-108.
[26]	BEN-SASSON E, CHIESA A, TROMER E, et al. Succinct non-Interactive Arguments for a von Neumann Architecture[EB/OL]. (2013-12-30) [2022-07-20]. https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.650.9468&rep=rep1&type=pdf.
[27]	BEN-SASSON E, BENTOV I, HORESH Y, et al. Scalable, Transparent, and Post-Quantum Secure Computational Integrity[EB/OL]. (2018-03-06) [2022-07-20]. https://eprint.iacr.org/2018/046.pdf.
[28]	MCCURLEY K S. The Discrete Logarithm Problem[C]// American Mathematical Society. Symposia in Applied Mathematics. Washington: American Mathematical Society, 1990: 49-74.
[29]	CANETTI R, CHEN Y, HOLMGREN J, et al. Fiat-Shamir: from Practice to Theory[C]// ACM. The 51st Annual ACM SIGACT Symposium on Theory of Computing. New York: ACM, 2019: 1082-1090.
[30]	MONTGOMERY P L. A Survey of Modern Integer Factorization Algorithms[J]. CWI Quarterly, 1994, 7(4): 337-366.
[31]	HUANG Xueyuan. The Use of Chinese Residue Theorem In Cryptography[D]. Hangzhou: Zhejiang University, 2006.
	黄学渊. 中国剩余定理在密码技术中的运用[D]. 杭州: 浙江大学, 2006.
[32]	PEDERSEN T P. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing[C]// Springer. Annual International Cryptology Conference. Heidelberg: Springer, 1991: 129-140.
[33]	BOOTLE J, CERULLI A, CHAIDOS P, et al. Efficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2016: 327-357.
[34]	MIERS I, GARMAN C, GREEN M, et al. Zerocoin: Anonymous Distributed E-Cash from Bitcoin[C]// IEEE. 2013 IEEE Symposium on Security and Privacy. New York: IEEE, 2013: 397-411.
[35]	SASSON E B, CHIESA A, GARMAN C, et al. Zerocash: Decentralized Anonymous Payments from Bitcoin[C]// IEEE. 2014 IEEE Symposium on Security and Privacy. New York: IEEE, 2014: 459-474.
[36]	FAUZI P, MEIKLEJOHN S, MERCER R, et al. Quisquis: A New Design for Anonymous Cryptocurrencies[C]// Springer. International Conference on the Theory and Application of Cryptology and Information Security. New York: Springer, 2019: 649-678.
[37]	BÜNZ B, AGRAWAL S, ZAMANI M, et al. Zether: Towards Privacy in a Smart Contract World[C]// Springer. International Conference on Financial Cryptography and Data Security. Heidelberg: Springer, 2020: 423-443.
[38]	CORRADINI F, MOSTARDA L, SCALA E. ZeroMT: Multi-Transfer Protocol for Enabling Privacy in off-Chain Payments[C]// Springer. International Conference on Advanced Information Networking and Applications. Heidelberg: Springer, 2022: 611-623.
[39]	DELGADO P, DINU F, KERMARREC A M, et al. Hawk: Hybrid Datacenter Scheduling[C]// USENIX. 2015 USENIX Annual Technical Conference(USENIX ATC 15). Berkeley: USENIX, 2015: 499-510.
[40]	STEFFEN S, BICHSEL B, GERSBACH M, et al. Zkay: Specifying and Enforcing Data Privacy in Smart Contracts[C]// ACM. The 2019 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2019: 1759-1776.
[41]	GUAN Zhangshuang, WAN Zhiguo, YANG Yang, et al. BlockMaze: An Efficient Privacy-Preserving Account-Model Blockchain Based on zk-SNARKs[J]. IEEE Transactions on Dependable and Secure Computing, 2020, 19(3): 1446-1463. doi: 10.1109/TDSC.2020.3025129 URL
[42]	BOWE S, CHIESA A, GREEN M, et al. Zexe: Enabling Decentralized Private Computation[C]// IEEE. 2020 IEEE Symposium on Security and Privacy(SP). New York: IEEE, 2020: 947-964.
[43]	KERBER T, KIAYIAS A, KOHLWEISS M. Kachina-Foundations of Private Smart Contracts[C]// IEEE. 2021 IEEE 34th Computer Security Foundations Symposium(CSF). New York: IEEE, 2021: 1-16.
[44]	SOLOMON R, ALMASHAQBEH G. SmartFHE: Privacy-Preserving Smart Contracts from Fully Homomorphic Encryption[EB/OL].(2021-02-10) [2022-07-20]. https://eprint.iacr.org/2021/133.pdf.
[45]	STEFFEN S, BICHSEL B, BAUMGARTNER R, et al. ZeeStar: Private Smart Contracts by Homomorphic Encryption and Zero-Knowledge Proofs[C]// IEEE. 2022 IEEE Symposium on Security and Privacy(SP). New York: IEEE, 2022: 1543-1543.
[46]	GJØSTEEN K, RAIKWAR M, WU Shuang. PriBank: Confidential Blockchain Scaling Using Short Commit-and-Proof NIZK Argument[C]// Springer. Cryptographers’ Track at the RSA Conference. Heidelberg: Springer, 2022: 589-619.
[47]	NARULA N, VASQUEZ W, VIRZA M. zkLedger: Privacy-Preserving Auditing for Distributed Ledgers[C]// USENIX. 15th USENIX Symposium on Networked Systems Design and Implementation(NSDI 18). Berkeley:USENIX, 2018: 65-80.
[48]	KANG Hui, DAI Ting, JEAN-LOUIS N, et al. Fabzk: Supporting Privacy-Preserving, Auditable Smart Contracts in Hyperledger Fabric[C]// IEEE. 2019 49th Annual IEEE/IFIP International Conference on Dependable Systems and Networks(DSN). New York: IEEE, 2019: 543-555.
[49]	XU Shiwei, CAI Xiaowen, ZHAO Yizhi, et al. zkrpChain: Towards Multi-Party Privacy-Preserving Data Auditing for Consortium Blockchains Based on Zero-Knowledge Range Proofs[J]. Future Generation Computer Systems, 2022, 128: 490-504. doi: 10.1016/j.future.2021.09.034 URL
[50]	BONEH D. The Decision Diffie-Hellman Problem[C]// Springer. International Algorithmic Number Theory Symposium. Heidelberg: Springer, 1998: 48-63.
[51]	WATERS B R, FELTEN E W, SAHAI A. Receiver Anonymity via Incomparable Public Keys[C]// ACM. The 10th ACM Conference on Computer and Communications Security. New York: ACM, 2003: 112-121.
[52]	LV Haifeng, DING Yong, DAI Hongyan, et al. Survey on LWE-Based Fully Homomorphic Encryption Scheme[J]. Netinfo Security, 2015, 15(1): 32-38.
	吕海峰, 丁勇, 代洪艳, 等. LWE上的全同态加密方案研究[J]. 信息网络安全, 2015, 15(1):32-38.
[53]	CHIESA A, HU Yuncong, MALLER M, et al. Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2020: 738-768.
[54]	CAMENISCH J, KIAYIAS A, YUNG M. On the Portability of Generalized Schnorr Proofs[C]// Springer. Annual International Conference on the Theory and Applications of Cryptographic Techniques. Heidelberg: Springer, 2009: 425-442.
[55]	ANDROULAKI E, KARAME G O, ROESCHLIN M, et al. Evaluating User Privacy in Bitcoin[C]// Springer. International Conference on Financial Cryptography and Data Security. Heidelberg: Springer, 2013: 34-51.
[56]	REID F, HARRIGAN M. Security and Privacy in Social Networks[M]. Heidelberg: Springer, 2013.
[57]	LIAO K, ZHAO Ziming, DOUPÉ A, et al. Behind Closed Doors: Measurement and Analysis of CryptoLocker Ransoms in Bitcoin[C]// IEEE. 2016 APWG Symposium on Electronic Crime Research(eCrime). New York: IEEE, 2016: 1-13.
[58]	BIRYUKOV A, PUSTOGAROV I. Bitcoin over Tor isn’t a Good Idea[C]// IEEE. 2015 IEEE Symposium on Security and Privacy. New York: IEEE, 2015: 122-134.
[59]	BISSIAS G, OZISIK A P, LEVINE B N, et al. Sybil-Resistant Mixing for Bitcoin[C]// ACM. The 13th Workshop on Privacy in the Electronic Society. New York: ACM, 2014: 149-158.
[60]	THOMAS S, SCHWARTZ E. A Protocol for Interledger Payments[EB/OL]. (2018-10-05) [2022-07-20]. https://interledger.org/interledger.pdf.
[61]	FRAUENTHALER P, SIGWART M, SPANRING C, et al. ETH Relay: A Cost-Efficient Relay for Ethereum-Based Blockchains[C]// IEEE. 2020 IEEE International Conference on Blockchain(Blockchain). New York: IEEE, 2020: 204-213.
[62]	POON J, DRYJA T. The Bitcoin Lightning Network: Scalable off-Chain Instant Payments[EB/OL]. (2016-01-14) [2022-07-20]. https://www.bitcoinlightning.com/wp-content/uploads/2018/03/lightning-network-paper.pdf.

方案	密码学假设	可信设置	证明时间	验证时间	证明尺寸	后量子安全
zk-SNARKs^[15]	算术电路+指数知识	√	nlog₂n	l	1	?
zk-STARKs^[27]	抗冲突哈希函数	?	nploylog₂n	ploylog₂n	log₂n	√
Bulletproofs^[13]	离散对数	√	n	n	log₂n	?
Sonic^[18]	数组模型	√	nlog₂n	l	1	?
Plonk^[19]	算术电路+指数知识	√	nploylog₂n	l	1	?