Survey of Zero-Knowledge Proofs: Advancements, Techniques, and Applications

Source:https://chatgpt.com/share/67a50084-3a30-8011-a808-6b3c76d3caab

I'll review the collection of papers listed in the Awesome Zero-Knowledge (ZK) repository and summarize their key findings in the style of a survey paper. This will include an overview of major advancements, categorizations of techniques, comparisons of methodologies, and insights into emerging trends in the field of Zero-Knowledge Proofs.I'll get back to you with a well-structured summary soon.

Survey of Zero-Knowledge Proofs: Advancements, Techniques, and Applications

Overview of Major Advancements in ZKPs

Zero-Knowledge Proofs (ZKPs) have evolved from a theoretical concept in the 1980s into a cornerstone of modern cryptography and blockchain security. Zero-knowledge protocols were first defined by Goldwasser, Micali, and Rackoff (GMR) in 1985, introducing interactive proofs where a prover convinces a verifier of a statement's truth without leaking any other informationeprint.iacr.org. By 1988, researchers found ways to remove interaction (non-interactive ZK) in the random oracle modeleprint.iacr.org. However, early ZKP protocols were not succinct – the proof sizes and verification effort grew with the complexity of the statement, limiting practical use.

A major goal in the 1990s was achieving succinct proofs where verification cost is sublinear in the original computation. Kilian (1992) and Micali (1994) pioneered the idea of using probabilistically checkable proofs (PCPs) to achieve very short proofs (sometimes called CS proofs)eprint.iacr.org. These works were mostly theoretical, relying on strong assumptions or oracles. For nearly two decades, the existence of general succinct non-interactive arguments remained an open question, with only heuristic constructions like Micali’s CS proofs (1994) and a specific protocol by Di Crescenzo and Lipmaa (2008)eprint.iacr.org. In 2011, Bitansky et al. formalized the notion of SNARKs (Succinct Non-interactive Arguments of Knowledge) and showed that if a new cryptographic primitive called extractable collision-resistant hash functions exists, then general-purpose SNARKs for NP are possibleeprint.iacr.org. This work (BCCT11) essentially coined the term zk-SNARK and laid the theoretical groundwork for practical constructions.

Practical Breakthroughs (2013–2016): The early 2010s saw rapid progress in making ZKPs efficient. In 2013, Pinocchio (Parno et al.) introduced the first nearly practical general-purpose zk-SNARK systemeprint.iacr.org. Pinocchio demonstrated that one can produce a proof of arbitrary program execution that is constant-size (only 288 bytes regardless of the computation) and verify it in about 10 ms, orders-of-magnitude faster than prior approacheseprint.iacr.org. This was a breakthrough in verifiable computation, proving that succinct, non-interactive proofs can be efficient in practice. Subsequent refinements led to even shorter proofs: by 2016, Groth’s construction (Groth16) achieved a zk-SNARK with a proof consisting of only 3 group elements (roughly 128 bytes) and verification needing just 3 pairingseprint.iacr.org. Groth16 proved essentially optimal in proof size for pairing-based schemes, establishing that such succinct proofs can be made both tiny and fast to verify. These advancements relied on structured reference strings (see below) and pairing-based cryptography, but demonstrated real feasibility – for example, the Zerocash project adopted zk-SNARKs to enable private cryptocurrency transactions, launching Zcash in 2016 as the first major real-world applicationhacken.io.

Beyond Pairings – Transparency and Post-Quantum (2016–2019): In parallel, researchers sought alternatives that remove the need for a trusted setup and strengthen security assumptions. A notable direction is the development of zk-STARKs (Scalable Transparent ARguments of Knowledge). Proposed by Ben-Sasson et al. (2018), zk-STARKs avoid structured trapdoors entirely by using lightweight cryptographic primitives (hash functions and error-correcting codes)crypto.stackexchange.com. STARKs are transparent (no secret setup needed) and built from quantum-secure assumptions, at the cost of larger proofs and higher verification time. Around the same time, the Bulletproofs protocol (Bünz et al., 2017) emerged as another alternative with no trusted setup. Bulletproofs introduced very short proofs (logarithmic size) for proving statements like range proofs and general arithmetic circuits, relying only on the discrete logarithm assumptioneprint.iacr.org. A Bulletproof for a typical statement is on the order of a couple of kilobytes, much smaller than prior non-SNARK proofs, and it supports aggregating multiple proofs efficientlyeprint.iacr.orgeprint.iacr.org. However, Bulletproofs sacrifice verifier efficiency – the verification cost grows linearly with the statement size (more on trade-offs later). Despite that, Bulletproofs found immediate use in cryptocurrencies (e.g. Monero adopted them for confidential transactions) due to their short size and lack of a setup requirementeprint.iacr.org.

Modern Innovations (2019–Present): As ZKPs gained adoption, new requirements led to further innovations. One focus was making SNARKs more universal and updatable, reducing the trust in setup ceremonies. Sonic (MBKM19) and PLONK (Gabizon et al., 2019) introduced universal structured reference strings, meaning a single setup can support all circuits up to a certain size and can be safely updated by multiple partieseprint.iacr.org. PLONK in particular demonstrated a SNARK with universal setup and significantly lower proving overhead than Sonic, while retaining fully succinct verification (constant verify time)eprint.iacr.orgeprint.iacr.org. Another important advance was recursive proof composition. Techniques like Halo (Bowe 2019) and Nova enabled proofs that can attest to the correctness of other proofs, allowing for incrementally verifiable computation. For example, Halo showed how to aggregate many inner-product (IPA) based proofs into one, enabling a form of recursion without a trusted setupvitalik.eth.limo. This opens the door to scalable ZKPs that can handle very large computations by chaining proofs, and even to proof-of-proof systems (a crucial component in layer-2 rollups and blockchain compression). Today, research and engineering in ZKPs continue at breakneck pace – with faster prover algorithms, specialized hardware acceleration, and new proving systems (Marlin, Halo 2, Plonkish protocols, etc.) all contributing to making ZKPs more practical for a wide range of applications.

Categorization of ZKP Techniques and Methodologies

Modern zero-knowledge proof schemes can be categorized by their approach and underlying cryptographic techniques. The two most prominent classes are zk-SNARKs and zk-STARKs, distinguished by whether they require a trusted setup and by their scalability properties. (Note: “SNARK” stands for Succinct Non-interactive Argument of Knowledge, while “STARK” stands for Scalable Transparent ARgument of Knowledge)crypto.stackexchange.com.

  • Pairing-based zk-SNARKs (Structured Reference String): These are SNARK protocols that require a structured reference string (SRS), often generated in a one-time trusted setup ceremony. Examples include Pinocchio, Groth16, and PLONK. They typically use elliptic curve pairings and polynomial commitment schemes (e.g. KZG commitments) to achieve succinctness. The structured setup allows the prover to commit to polynomials representing the computation and use cryptographic pairings to prove correctness with a few group elements. This yields very short proofs (usually a constant number of curve points, e.g. 3 in Groth16) and fast verification (a few pairing checks)eprint.iacr.org. The downside is the need for trust in the setup parameters – if the trapdoor from the setup is not destroyed, a malicious party could forge proofschain.link. Pairing-based SNARKs are not transparent and rely on algebraic assumptions that are not post-quantum safe. Despite this, they have been extremely popular due to their efficiency and were the first to be deployed (e.g., Zcash’s shielded transactions use a variant of Groth16). Recent “universal” SNARKs like Sonic and PLONK fall in this category but improve the setup process by making the SRS reusable across many computationseprint.iacr.org.

  • Transparent Proofs (zk-STARKs and PCP-based IOPs): Transparent protocols avoid any secret setup; their public parameters contain no trapdoor. zk-STARKs are the leading example, using only lightweight primitives (hash functions and error-correcting codes) in an Interactive Oracle Proof (IOP) framework that is compiled via Fiat-Shamir to non-interactive. STARKs leverage techniques like polynomial IOPs (e.g. the FRI protocol for Fast Reed-Solomon Interactive Oracle Proofs) to check computation integrity. Because they use only hashing, STARKs are post-quantum secure and do not require assuming elliptic curve hardnesscrypto.stackexchange.com. They are also scalable: capable of proving very large computations. The trade-off is that STARK proofs are larger – on the order of tens or hundreds of kilobytes – and the verification is slower (typically quasi-linear or polylogarithmic in the statement size, rather than strictly constant)vitalik.eth.limo. Another transparent approach uses MPC-in-the-head protocols (like ZK-Boo and Ligero), which also avoid a trusted setup by having the prover essentially simulate a multiparty computation and reveal only some parts as a proof. These tend to produce proof sizes in between STARKs and SNARKs and have longer verification times, so they are currently less common in practical systems than STARKs. Transparent proofs are especially attractive for applications needing long-term security (against quantum attacks) or where conducting a trusted ceremony is impractical.

  • Discrete Log-Based Proofs (e.g. Bulletproofs): A separate category uses commitment schemes based on elliptic curves without pairings, such as the inner-product argument (IPA) approach. Bulletproofs are a prime example, building on the idea of recursively compressing many logical checks into an inner product verificationeprint.iacr.org. These schemes do not require a trusted setup and have much smaller proofs than STARKs (Bulletproof proofs are typically a few kilobytes and grow logarithmically with the circuit size)eprint.iacr.org. They rely on standard discrete log assumptions. However, as a consequence of using IPA commitments, their verification time is linear in the size of the computation (each proof requires checking many curve operations)vitalik.eth.limo. In practice this means that while Bulletproofs greatly reduce proof size for e.g. range proofs in cryptocurrencies, verifying those proofs is slower than SNARK or STARK verification. This category is useful when proof size is at a premium (e.g., blockchain space) and the statement sizes are moderate, so that linear verification is acceptable. Recent research has also explored hybrid approaches that combine merits of different categories, as well as recursive techniques (like Halo) to mitigate the linear verification cost by merging many such proofs into onevitalik.eth.limo. Each category of ZKP comes with its own methodology and use cases, but at a high level, all modern approaches use some form of arithmetization: the original problem (say, a program execution or a statement about data) is reduced to algebraic conditions (polynomial equations or matrix equations) that a prover can satisfy with secret witnesses. Then cryptographic commitments (whether via pairings, Merkle trees, or inner-product proofs) are used to allow the verifier to check those conditions with significantly less effort than performing the computation itself. This arithmetization paradigm underlies zk-SNARKs, zk-STARKs, and Bulletproof-style protocols alikevitalik.eth.limo, and is a key unifying methodology across seemingly disparate ZKP schemes.

Comparisons of ZKP Approaches and Their Trade-offs

With multiple classes of zero-knowledge proving systems available, it’s important to compare their characteristics and understand the trade-offs for different use cases. The following are key dimensions along which ZKP approaches differ:

  • Trust Model (Setup): One of the clearest distinctions is whether a trusted setup is required. SNARKs like Groth16 and PLONK need a setup phase to generate proving and verification keys (a structured reference string). If the setup’s secret trapdoor is not destroyed, security can be compromised (allowing false proofs)chain.link. STARKs and other transparent proofs require no special setup – only public random strings or hash functions – which gives them a stronger trust modelcrypto.stackexchange.com. This transparency is a major advantage of STARKs, eliminating the “ceremony” and associated trust assumptions. Bulletproofs and IPA-based systems are also transparent (no trapdoors). The trade-off is that SNARKs with a structured setup can leverage that structure for greater efficiency. Recent “universal” SNARKs try to get the best of both worlds by requiring only a one-time setup that can be reused and securely updatedeprint.iacr.org.

  • Proof Size: Proof size varies dramatically. Pairing-based SNARKs produce the smallest proofs – e.g. Groth16 proofs are about 3 elements ≈ under 1 KBeprint.iacr.org, and PLONK proofs are on the order of a couple of hundred bytes. STARKs have much larger proofs, typically tens of kilobytes (since they include many hash commitments and low-degree test proofs)vitalik.eth.limo. Bulletproofs are in between: proof size grows logarithmically with the statement, roughly 1–3 KB for typical circuitsvitalik.eth.limo. In contexts like blockchain, smaller proofs are highly valuable to minimize on-chain data and verification gas. SNARKs excel here with their succinctness. STARKs sacrifice proof size for other benefits, though techniques like compression and proof aggregation (batching many transactions) can amortize the cost.

  • Verification Cost: Perhaps more important than absolute size is the verifier’s time complexity. Succinct proofs aim for very fast verification – ideally constant time regardless of the original computation size (or at worst sub-linear). SNARKs achieve this: verifying a SNARK involves a small number of cryptographic operations (a few pairings and multi-exponentiations), often running in millisecondseprint.iacr.org. STARK verification is slower; while asymptotically sublinear, it involves iterating over polynomial commitments with Merkle trees and performing FFTs, leading to a higher constant overhead (typically tens of milliseconds, depending on proof length). Bulletproof verification is the slowest in theory – it requires work linear in the circuit size, which for large computations can mean verifying the proof is actually more work than simply re-executing the computation! As Vitalik Buterin notes, an IPA-based proof can take longer to verify than to run the computation, making it “non-viable for scalability-related use cases” like blockchain state proofsvitalik.eth.limo. In practice, for moderate sizes (e.g. a confidential transaction), Bulletproof verification is still manageable, but this linear scaling is a key drawback of that approach. Recent advances in recursive proof composition partly address this: for instance, Halo’s technique of merging IPA proofs shows that one can verify many proofs by checking just one, effectively bringing down verifier time per statementvitalik.eth.limo.

  • Security Assumptions: Different ZKP systems rest on different cryptographic assumptions. Pairing-based SNARKs rely on the hardness of problems in elliptic curve bilinear groups (e.g., elliptic curve discrete log and pairing product equations) and also on the toxic waste (trapdoor) being unknown. These are not post-quantum safe – a sufficiently large quantum computer could break the elliptic curve cryptography. In contrast, STARKs use only hash functions and information-theoretic soundness via PCPs, so they are post-quantum secure by designcrypto.stackexchange.com. Bulletproofs use standard elliptic curve discrete log assumptions (without pairings); they are not quantum-safe but do at least avoid the extra pairing structure. Another aspect of assumptions is whether the proof system is an argument (computational soundness) or proof (statistical soundness). All succinct schemes (SNARK/STARK/Bulletproof) are arguments of knowledge – they assume the prover is computationally bounded. Finally, transparency vs setup is also a security consideration: STARKs’ avoidance of a trapdoor removes the risk of setup toxicity and makes the system easier to auditchain.link. On the other hand, one might argue pairing-based SNARKs have been studied longer and more deployed, so their security (under classical assumptions) is well vetted.

  • Prover Efficiency: While verifiers benefit from succinctness, the prover’s workload to generate a proof can be heavy. SNARK provers must perform large multiplications in finite fields and FFTs to encode the witness, which can take seconds or even minutes for large circuits (billions of constraints). STARK provers typically have even larger overhead (due to producing many Merkle tree layers and polynomial IOP proofs), but they scale better with very large statements because they avoid expensive cryptographic group operations. Bulletproof provers have to perform a number of multi-exponentiations linear in the witness size, which is considerable but often easier to parallelize. There is a spectrum: for small statements, any approach is fast, but for very large statements (e.g., proving all transactions in a block), pairing SNARKs currently tend to have the shortest proving time for a given level of security, whereas STARKs might handle massive statements more scalably at the cost of time. Prover performance is an active area of optimization (with new algorithms, FFT improvements, and GPU acceleration significantly reducing proving times in recent years). In summary, there is no one-size-fits-all ZKP – there is a trade-off triad among proof size, verification time, and setup/assumption hardness. zk-SNARKs offer ultra-short proofs and quick verifies but demand a trusted setup and are not post-quantumchain.link. zk-STARKs remove the need for trust and are future-proof against quantum attacks, but produce larger proofs and slower verificationchain.linkvitalik.eth.limo. Bulletproofs sit between, minimizing proof size without a trusted setup, but suffering in verifier costvitalik.eth.limo. The appropriate choice depends on the application’s priorities – e.g., a blockchain rollup might prioritize verify speed and proof size (favoring SNARKs or STARKs) whereas an application like confidential asset transfers might prioritize no trusted setup and small proofs (favoring Bulletproofs for short statements). Table 1 (in Vitalik’s analysisvitalik.eth.limovitalik.eth.limo) concisely captures these trade-offs: hash-based (STARK) proofs are largest but most robust, pairing-based (SNARK) proofs are smallest and fastest to verify but need setup, and IPA-based proofs are small but slow to verify. These trade-offs are fundamental, although ongoing research (like recursive SNARKs, polynomial commitments without trust, and hardware advances) continues to push the boundaries of each dimension.

Zero-knowledge proofs have rapidly transitioned from a pure research topic into real-world deployments. Here we outline some of the emerging trends and novel applications driving the ZKP field forward:

  • Blockchain Scaling (ZK-Rollups and zkEVMs): One of the most active areas is using ZKPs to scale blockchains by offloading computation off-chain and verifying it on-chain succinctly. So-called ZK-Rollups bundle hundreds of Layer-2 transactions into a single SNARK (or STARK) proof that is posted to the Layer-1 chain, drastically reducing per-transaction cost. Projects like Loopring, zkSync, StarkNet, and Polygon Hermez use zkSNARK or zkSTARK proofs to validate batched transactions without revealing user datahacken.io. A closely related effort is building zkEVMs – zero-knowledge Ethereum Virtual Machines – which can prove the correct execution of Ethereum-like smart contracts. There are multiple approaches to zkEVMs (from fully bytecode-compatible to high-level circuit reimplementations), but all leverage improvements in ZKP proving systems to handle the complex logic of a virtual machine. These innovations directly tackle the blockchain scalability trilemma by providing higher throughput and security (since the proofs are verifiable by anyone) without sacrificing privacyhacken.iohacken.io. As of 2023, we have seen the launch of several ZK-rollup networks and even prototype Layer-1s that use recursive proofs to compress entire blocks (e.g., Mina protocol). This trend demonstrates ZKPs' power to enable trustless scalability: Ethereum’s roadmap, for instance, envisions major reliance on zkRollups for scaling.

  • Privacy-Preserving Applications: ZKPs are a natural fit for privacy in cryptocurrency and beyond. The prime example is private digital currency – Zcash’s use of zk-SNARKs allows transactions to be fully encrypted on a public ledger while still validated by all nodeshacken.io. Beyond cryptocurrencies, ZKPs enable privacy-preserving smart contracts and decentralized applications. Projects like Aztec are exploring confidential DeFi using ZKPs to hide transaction details. Other examples include Zether/Quisquis protocols for private transfers on Ethereum using zero-knowledge proofsgithub.comgithub.com. Crucially, ZKPs can prove compliance or facts about data without revealing the data. This has huge implications for areas like financial regulation (e.g., proving an exchange is solvent without exposing its books), private auctions (proving bids without revealing them), or healthcare (proving someone meets criteria without exposing medical records). We are beginning to see proof-of-reserves implementations by cryptocurrency exchanges, where an exchange proves cryptographically that its assets exceed its liabilities to customers, all via ZKPs that preserve user privacy.

  • Digital Identity and Authentication: An emerging use case is self-sovereign identity and authentication via zero-knowledge proofs. Instead of sharing copies of identity documents or personal data, users can prove statements about their identity attributes with ZKPs. For example, one can prove “I am over 18” or “I am a citizen of country X” without revealing any other details or the actual ID document. This concept is gaining urgency as online platforms grapple with verifying users (to combat bots or comply with KYC regulations) while preserving user privacywww.protocol.ai. Several projects and standards (e.g., DID + verifiable credentials with zk-SNARK proofs, or protocols like iden3 and Polygon ID) are implementing this. In the Protocol Labs 2023 report, industry experts identified the identity space as “one of the most mature and promising markets for zk proofs,” especially as AI-generated content and deepfakes make verification harderwww.protocol.ai. ZKPs can also strengthen authentication schemes – e.g., enabling login systems where the server verifies a zero-knowledge proof of your credentials (like a hash of your password or biometric) instead of ever seeing the secret itself, reducing the risk of leaks.

  • Verifiable Computation & Web2 Integration: ZKPs are expanding beyond blockchain into general verifiable computing services. We see verifiable cloud computing platforms emerging, where a cloud provider can produce a proof that it executed a computation correctly (clients can trust results without re-computation). This is essentially the original vision of Pinocchio and following works, now being productized for things like outsourced machine learning or data processing. Another trend is ZK in machine learning (ZK-ML) – proving properties of ML models and their inferences without revealing the model or input data. For instance, a model owner can prove that a prediction was done correctly according to a trained model, or that a model has certain accuracy on a secret test set, etc., all without exposing the model parameters. ZK-ML is still a nascent field, but it’s growing, intersecting with AI safety and federated learning. There is even exploration of using ZKPs to prove things about generative AI outputs (to authenticate that some content was produced by a known model, for example).

  • Performance Improvements and Tooling: On the infrastructure side, there is a clear trend of improving the efficiency and accessibility of ZKP technology. Academic and industry teams are working on faster prover algorithms (e.g., using FFT optimizations, multi-exponentiation improvements, better parallelization). Specialized hardware is also in development – GPUs are already widely used for proving, and now ASICs/FPGAs are being designed to accelerate proving systems (for example, to speed up the hash computations in STARKs or the multi-scalar multiplications in SNARKs). There’s also a flourishing ecosystem of ZKP languages and tools: languages like Circom, ZoKrates, Noir, and Cairo (StarkWare’s VM language) allow developers to write programs that compile down to ZK circuits or arithmetizations more easily. These tools, along with “ZK-friendly” primitives (hash functions and elliptic curves optimized for circuits), are lowering the barrier for engineers to integrate ZKPs into applications. As a result, the community of ZK practitioners is growing fast, and knowledge sharing through resources like the Awesome ZK collection is helping to educate new engineers and researchers. Looking forward, zero-knowledge proofs are poised to move from niche use-cases to mainstream tech stacks. Independent research even projects that by 2030, there could be on the order of 90 billion zk proofs performed per year, powering an industry worth $10 billionwww.protocol.ai. Whether or not those specific numbers materialize, the trajectory is clear: ZKPs are becoming more efficient, more essential, and more ubiquitous across various industries. From securing blockchain scalability to protecting user privacy and enabling new forms of trust-minimized interaction, the advancements surveyed here illustrate a rich landscape of techniques. Ongoing research continues to refine these methods – perhaps achieving even shorter proofs (or no-trusted-setup proofs with SNARK-level efficiency), and expanding the range of what can be proven zero-knowledge. The convergence of academic breakthroughs with practical deployment is accelerating, making now an exceptionally exciting time in the evolution of zero-knowledge proofswww.protocol.ai.