A Survey on Recursive and Composite Techniques of Zero-Knowledge Proofs
Zero-knowledge proofs,as a fundamental cryptographic primitive,allow one party in a communication to prove the validity of a certain statement to another party without revealing any additional information.They are pivotal technologies for the secure circulation of data and play an extremely important role in cryptography and security.They are not only critical components of many cryptographic protocols,such as authentication,digital signature,and public-key encryption,but also provide significant privacy protection and performance enhancement for various practical applications,including anonymous transactions,smart contracts,machine learning,and more.In general,the statements to be proven by zero-knowledge proofs are categorized into three types:algebraic statements,non-algebraic statements,and composite statements involving both algebraic and non-algebraic statements.Although zero-knowledge proof protocols for these statements have made significant progress in terms of performance,functionality,etc.,there remain challenges in practical applications,such as insufficient efficiency,poor scalability,and specialized functionality.To effectively address these bottleneck issues,the techniques of recursion and composition in zero-knowledge proofs have received extensive attention in recent years.In this paper,we conduct a systematic and comprehensive survey on the recursive and composite techniques of zero-knowledge proofs.Firstly,regarding recursive zero-knowledge proofs for algebraic statements,inner product arguments,a kind of ∑-protocols proving that the inner product of two committed vectors equals a public scalar,firstly rely on recursive techniques to achieve a breakthrough in communication complexity,reducing it from linear to logarithmic.We extensively survey inner product arguments,comparing and analyzing them in detail,particularly those based on the Pedersen commitment scheme.This analysis is conducted from the perspectives of prover complexity,communication complexity,verifier complexity,and more.Secondly,regarding recursive zero-knowledge proofs for non-algebraic statements,the key idea is to express the verifier's algorithm as an arithmetic circuit and generate a new proof for this new circuit,which in turn proves the validity of the original proof.This recursive technique is primarily used to aggregate proofs,construct incrementally verifiable computation schemes and combine proof systems.We thoroughly examine the research landscape of these predominant applications,specifically focusing on incrementally verifiable computation schemes and the circuit-based composition of proof systems.We conduct an in-depth comparative analysis of the complexity,key technologies,and implementation skills associated with incrementally verifiable computation schemes.Thirdly,regarding composite zero-knowledge proofs for composite statements,the key idea is to prove the algebraic part using ∑-protocols,prove the non-algebraic part using general-purpose zero-knowledge proofs,and optionally prove the consistency of variables that appear in both the algebraic and non-algebraic parts using some linking protocols.Among composite statements,a basic and common form is that"the openings of some algebraic commitments satisfy an arithmetic/Boolean circuit."Zero-knowledge proofs for this type of statement are also known as commit-and-prove zero-knowledge proofs(CP-ZKPs).We provide a granular comparative analysis of CP-ZKPs from various perspectives,including complexity,the setup phase,key modules,and more.Finally,we outline future research directions for recursive and composite techniques of zero-knowledge proofs,from the aspects of algebraic statements,non-algebraic statements,and composite statements.
NETL
NSTL
万方数据
