Navigating the ZK ecosystem: A taxonomy.

ZKbridge research by UC Berkeley

PS: Although this article is apt for readers who are somewhat familiar with zero knowledge proofs (hence referred to ZKP/ ZK in the article), I will be sharing relevant resources in order to ease the burden for people who want to learn in depth about the various domains and concepts.

About

Given the ZK technology has been coming into mainstream in Web3 there has been for addressing challenges about claims verification or whether scaling throughput of verifications of transactions, thanks to the significant strides of improvement in the:

• Performance metrics (proving schemes, proofsize ,computation benchmark, circuit generation, signature generation benchmarks, etc).
• And the developer tooling / infrastructure (modular tech stack) developed to onboard these toolings on-chain.

Here I will give you the current state of the art description about the progress on all of the above categories of ZKP(Zero Knowledge Proof) categorisation, by describing the various solutions developed by different firms, and comparing with the use cases that developers will be able to develop in the future based on ZK.

I will be consulting various resources for compiling the report (and i’d recommend be absolutely subscribed by the enthusiasts) (PS: this is updated subsequently since first publishing the article, just to keep up to pace with good quality articles):

1. Zkhack.dev
2. Zkproof.org (for their community resource defining the basics of the domain).
3. ZPrize (DARPA program to significantly speed up the performance and adoption of the various cryptographic schemes on top of the ZKProofs).
4. A16z crypto (1, 2).
5. Awesome ZKP

1.Performance Metrics:

1. Counterparties: The most visible difference is based on the counterparties (Prover and Verifier). They are defined as follows (based on the number of interactions between the counterparties):

• Interactive Proof protocol: In this case, both prover and verifier interact with the public stream of input statement (say it as x encoded in the form of algebraic field operations) in order to prove that the statement belongs to the set of the Language L of proofs (for instance prover verifying that he/she is compliant to open bank account , thus it will have conditions like X1(age) > 18, X2(exists identity card) = true … and so on). without revealing the actual detail (ie Xi ). It gives a probabilistic result with high accuracy once the interactions between the counterparties is significant.

Credits : interactive ZK Proofs, Panther Protocol blog.

Since the first paper published by [GMR85] paper (inspired by Elgamal encryption scheme released in the same year), they are efficient vis a vis non interactive proofs (SNARK’s) in terms of space complexity (in GB’s) as there is no need of setup ceremony, but at same time having disadvantages (namely the increase time needed to significantly verify, potential man in the middle attacks if proving scheme is not sufficiently padded, etc…)

But since then there has been significant progress in these category of protocols , some of the latest protocols in the space like:

• Sigma Protocol: reduces the number of interactions needed to validate the statement to 3 steps (namely commitment, challenge and response). This made it easier for applications that need multiple connections with on-chain contracts (for instance, oracles for verifying off-chain compute) to scalably verify the data to be used for smart contracts.
• Commit and Proof Schemes: these further optimize the space complexity of interactive zk protocol scheme by proving every gate operation in the circuit without storing the commitments to all of these components (more about the circuits explained in 2nd section). They have been first proposed in 1989 by kilian et al, but since there has been various schemes developed like Vole(Vector obvious linear evaluation) based ZK (Weng 2020) for allowing the creation of message authentication codes scalably and thus increasing the performance for ZK schemes for use cases like message passing or oracle based price feeds generation with verifiability etc.

Currently various protocols in web3 use these schemes like:

• Sismo’s Pythia scheme for assigning attestation to wallets based on certain groups of actions.
• Chainlink DECO protocol to verify the certificates (aka decentralized TLS) for future cross-chain communication and verification securely .

Thus even though they are not discussed as much as the non interactive proofs, they will be consequential for various use cases to provide more secure message authentication schemes.

• Non Interactive Validity Proofs: In brief, this scheme the verifier has to assert the validation of the statement via the single message transfer from prover to verifier. Based on the steps for generation of the message (ie proof string in common terminology), there are the following categories of protocols:
• SNARKS (non interactive arguments of knowledge): these protocols use setup phase to generate the secure reference string, and then it validates any given generated proof by the circuit in the linear time using elliptical curves. This allows creation of on-chain proofs as elliptical curves are more compatible vis hashing functions. There have been progress in setting up efficient zk proof schemes by optimizing on:

1. Backend Schemes (1): these consist of the cryptographic schemes that allow the prover to generate the proof strings of fixed size. Current benchmarks like Groth16, plonk are allowing the creation of the optimized signatures with size under 1kb and proving time under 100ms.
2. Nature of reference string : Whether the setup string needs to be upgradable for each change in the circuit, currently there are various protocols (sonic, marlin) to verify in constant proof size but with expensive verification size (which is optimized by putting proofs in batches).

Frontend Schemes (2): these allow the developers to define the conditions from higher level description of the statement verified into the intermediate circuit representation. There are primary following categories (3):

1. Rank1 Constraint Satisfaction(R1CS): Described intuitively by Vitalik in his intro of Zk-SNARK series, this scheme allows conversion of the linear algebraic constraint defined in the higher level into the following condition (where A,B,C are the points generated in elliptical field). They are used in Zcash and Zokrates to create on-chain proovers for given higher level constraints. But they are only constraint on very specific general computation.

2. Algebraic Intermediate representation(AIR): this works on general programs running on VM (or EVM in case of ZkVM) in two step process:

1. Creating execution trace (ie the set of instructions to be proven in the program) with corresponding low level polynomial constraints
2. And then converting into the simplistic univariate polynomial by the series of transformations, and eventually proving that the resulting execution of the instruction is valid.

This representation is extensively used for ZkEVM to verify the equivalency of execution of the rollup and its EVM equivalent, while significantly optimizing the storage of aggregated computed proofs. They can proof smart contract proofs worth millions of gates within constant block time.

1. STARKS(scalable transparent argument of knowledge): these require least interaction between prover and verifier and use hash based commitment schemes in order to make it post quantum resistant. Starkware was the pioneer of this technology which started with the StarkDEX in 2018 in order to scale the verification of the mainnet transactions by creating highly optimized proof commitments of millions of transactions based on validium. since then they have also developed Starknet, an L2 allowing development of smart contracts and creation of security guarantees thanks to Voiliton scheme (ie combining the rollup and validium proofs into single state, thus keeping immutable proofs of execution in case if there is malicious attack on ), thus allowing various applications (like Immutable X , Sorare) to develop their application specific rollups which are independent from each other , but at the same time allowing interoperability thanks to the ZKproofs.
2. Proof Systems components : Proofs along with the counterparties combined comprise the proof system. As defined in the (QEDIT etal, chainlink) paper, there are various parameters that are to be considered in order to build the proof system for your use case,defined as follows:
3. Computational and memory complexity : this consist of representation complexity (information needed to store to remember the computation), or space needed to perform the computation.
4. Nature of statements: this consists of the nature of proofs to be done (whether these are binary verification of certain claims like authentication, range proofs , proof of commitments).
5. Nature of execution of protocol: whether the protocol can be parallelized(on the physical hardware like ASIC/GPU’s) and distributed(like DIZK) in order to scale the application of zk-proofs for use cases needing billions of gates and large throughputs, something that we will see in Zprize description.
6. Support for instruction set: based on the program that is using ZK computations under the hood are for constraint uses (ie only for transfer , identity claims) or more advance use cases (like general purpose computation like AI etc), there have been various projects developed (like RISC Zero, nil foundation ZkLLVM ) allow the support of ZK equivalence of every possible compilable program via LLVM.

2. ZK infrastructure, present and future :

Given the above categorisation of the various schemes developed in the last 20 years of research, there has been significant progress in the last 4 yrs thanks to the increased performance of hardware , but also the efficient software and algorithms in order to generate the ZK circuits . one of the major competition that was moonshot in this approach was ZPrize , with aim of exponential folds by building ZK based services on current benchmark compute infrastructure (GPU, ASIC’s , FPGA’s, mobile hardware etc) across various runtimes like (VM’s , WASM’s) etc.

With the major projects (Polygon, Aleo, manta, scroll etc…) build their respective solutions in 12 different prize categories. The aim was to improve manyfold the benchmark performance of various signature schemes, increasing adoption of low level cryptographic libraries along with onboarding this technology as a significant gamechanger in the future of applied cryptography.

The result was significant acceleration on some of the categories of signature schemes and hardwares that will be significant for large scale adaptation of the ZKP for the various use cases as follows:

Credits: ZPrize

This will be a major boost for boosting the performance of the current L2 based validity services (based on rollups, Validium and volition )

TL;DR

I can go in depth regarding the current use cases and the detailed description but in interest of keeping the description of the article relatively accessible, I have described the various schemes and characteristics at higher level for people to know better, and would like to list the following main use cases / innovations to watch-out in the upcoming time:

• AI: thanks to the scalable implementation of feasible DIZK schemes along with more generic frontends , we will eventually see exotic use cases for AI (like verifiability of federated learning, privacy based learning of large language models (ref) without the need of centralized).
• Trusted proof markets (aka ZK proof marketplace): instead of having to develop your own circuits or marketplace, services like nil foundation will allow the creation of audited and high performance ZK protocols on service, which will be interoperable for any web3 application and use cases.

And that’s it for now. Thanks for reading my article till the end and keep following my channel (twitter, substack) to share feedback about this article and write the future articles on the latest progress in the field and the use cases.