Zero-Knowledge Proofs (ZKP): How They Work with Blockchains

ZK proofs allow users to efficiently demonstrate to others that they possess knowledge or ownership of critical data, like a wallet’s private keys, without revealing sensitive, underlying information.

An Introduction to “Moon Math”

The Ethereum community and foundation has been increasingly focused on increasing the network’s capacity to handle more transactions, or its scalability. The popularity of Web3 development in the form of dApps and a cascade of tokens and NFTs have caused gas fees to make the network unusable for many users, prompting them to move to other blockchains. Ethereum is, of course, making efforts to natively scale their network using a concept called sharding in their merger to a proof of stake consensus mechanism. 

Another proposed idea is to push much of Ethereum’s transaction executions onto what is known as layer 2 rollups. This is a term used to describe a number of third-party scaling solutions that operate adjacent to Ethereum’s Mainnet, but still rely on its foundational layer for security. Both Optimistic rollups and Zero-Knowledge rollups have been implemented with varying levels of success, but this article will examine ZK Proofs, which power ZK rollups, more specifically.

A group of MIT researchers first introduced the concept of Zero-Knowledge Proofs in the 1980s, but until recently ZK proofs had been considered incredibly complex, and referred to humorously as “moon math.” Fast forward to Ethereum’s scalability limitations, and we find their ideas incredibly useful for enhancing the scalability, security, and privacy features of Web3. There are now a number of varying strategies for the application of ZK proofs, each intending to capitalize on specific advantages of differing blockchains while working within their respective limitations.

Understanding ZK Proofs

ZK proofs are cryptographic methods used to prove users have knowledge of the wallet’s private keys without revealing the information itself when proving it. That is, the information will prove the knowledge while protecting the data’s privacy. In the case of executing smart contracts, this means that a prover must demonstrate critical knowledge, and a verifier must confirm the validity in a reasonable amount of time. 

Fundamentally, ZK proofs involve verifiers asking provers to perform specific tasks which could only be performed if the prover has knowledge of the wallet’s private keys. If the verifier’s test is robust, and an honest prover can easily perform the required tasks, then the test can verify the prover’s authenticity in such a way that only an honest prover could pass the verification process successfully.

In trusted setups, a key generator takes a secret parameter and a program, and then generates two publicly available keys; one intended for the creation proofs and one for verifying them. The public keys are parameters that only need to be generated once for a given program. Subsequent users simply use the public parameters and trust that the creators of the secret parameter keys acted honestly and adequately protected them. The secret parameter is of course a security risk in trusted setups, since knowledge of the secret parameter could be used to generate fake proofs and thus be used to fool verifiers.

ZK proofs might either be interactive or non-interactive. Interactive ZK proofs are distinguishable as they require the prover to repeatedly perform actions for each verifier, whereas non-interactive ZK proofs are generated by verifiers in a standard fashion and can therefore be confirmed by verifiers by using the same proof de-coding standards. ZK proofs are often evaluated on whether they meet three measures of excellence and to what degree:

1. Completeness: If given an honest answer to a proof by a prover, the verifier is able to determine the prover’s knowledge of critical data with an extremely high degree of confidence.
2. Soundness: Provers will be unable to deceive verifiers by chance or means other than having knowledge of the critical data. 
3. Perfection (of Zero-Knowledge): The prover’s input to the verifier does not reveal knowledge of any critical data, but only demonstrates it indirectly.

Furthermore, ZK proofs can still be classified more granularly by their various implementations for scaling blockchains. For example, SNARKs, STARKs, PLONKs, and DARKs (Bulletproofs) each have certain security strengths and risks for developers to weigh, including the proof’s data footprint, succinctness of the time to prove, verification times, risks of collusion, and so on. A quick comparison of the most common ZK implementations can be clearly seen in the following graphic:

SNARKs

Succinct Non-Interactive Argument of Knowledge

SNARKs depend upon elliptic curves and probabilities for their security. Elliptic curves, in cryptography, assume that finding the discrete logarithm of a random elliptic curve element with respect to a publicly known base point is impracticable. That is, if the probability that the proof could be guessed by random chance is low enough, verifications can be made once the appropriate threshold is reached.

In addition, SNARKs have until recently made use of trusted setups, though they are not required. That is, the key parameters used for creating proofs and verification standards are imposed by one or more users, and subsequent users need to trust to have been honest in the creation and implementation of the proof’s parameters.

Initially, when those key parameters are created, there is a hidden parameter linked between the verification key and the keys sending private transactions. If this sensitive data isn’t destroyed after genesis, the secret parameters could be used to fraudulently execute transactions by fooling verification safeguards. That means hackers could get a copy of the corresponding private keys and could use them to create counterfeit tokens or crypto assets on the network. Fortunately, the attackers couldn’t actually violate the sensitive data of other users nor steal crypto from other wallets.

However, destroying the private key doesn’t necessarily guarantee that counterfeiting is impossible since unknown vulnerabilities unrelated to the destruction of these private key parameters could be present. Actually any protocol which keeps transaction amounts private makes detection of such counterfeiting extremely difficult.

SNARKs are also estimated to utilize much less gas compared to STARKs, meaning that a blockchain using SNARKs would be cheaper and more retail-friendly. Finally, the proof size for SNARKs is much smaller than STARKs, meaning they require less on-chain storage and take up less memory fitting into new blocks, making SNARKs easier to scale as the network gains in users and complexity.

Nevertheless, SNARKs have actually been adopted much more widely than other ZK proofs, despite the trusted setup issue due to an earlier development, placing it further along its adoption curve by nature of its head start. For example, ZCash was the earliest implementation of ZK proofs in the crypto space, which has led to voluminous developer libraries, academic research, and an active community of professional developers utilizing the technology.

PLONKs

Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

A newer ZK proof design is known as PLONK. PLONKs are technically classified as a SNORK, another non-interactive type of SNARK which requires a trusted setup. However, the genesis trusted setup is universal and updateable, meaning that is universally compatible with subsequent programs using the same proof schemes, and that multiple parties can take part in the trusted setup, providing better security guarantees so long as one of the original participants is honest.

The second distinguishing, and perhaps most profound characteristic, is the modularity of its standardized, polynomial commitments. PLONKs use what is known as Kate commitments, which is based upon similar mathematics as SNARKs, but can be substituted for other proofs like FRI. This is actually more reminiscent of STARKs or DARKs, which will be covered in more detail below. The significance of PLONK modularity cannot be overstated since this theoretically makes the scheme more flexible in terms of its design and implementation. 

For instance, certain developers might need to prioritize security guarantees over proof size, most likely meaning proofs will take longer to complete, require larger data packets, increase network fees, and affect network scalability more broadly. Regardless, since its Kate commitments are standardized, the majority of the fundamental tooling can still be shared no matter which polynomial commitments are chosen to verify that the prover has demonstrated knowledge of the critical data adequately so that the relevant smart contracts will execute accordingly.

STARKs

Scalable Transparent Argument of Knowledge

Unlike SNARKs, STARKs rely on hash functions, similar to proof-of-work blockchains, offering more significant quantum resistance and thus future-proofing protocols implementing STARKs. Consequently, STARKs have larger proof sizes, an increased electrical demand to power the network and longer timeframes in terms of verifying the proofs. 

Contrasting with previously discussed SNARKs and PLONKs, STARKs do not use the same trusted private key setup at the program’s genesis. Furthermore, STARKs are considered to be a more efficient variant of zero knowledge technology, relying on leaner cryptography in the form of collision-resistant hash functions, as previously mentioned.

Devs will also find a bit more difficulty in terms of building protocols using zk-STARKs due to a smaller community and consequently, fewer resources like libraries or other forums of discussion. While there are several projects creating STARK-based scaling solutions like Miden from Polygon, and Starkware’s Starknet, the SNARKs community has had far more time to flourish and is, therefore, more ample in terms of available resources.

DARKs

Diophantine Arguments of Knowledge

Finally, a new scheme called Diophantine Arguments of Knowledge, or DARK, uses something known as hidden order groups. DARKs use a subset of hidden groups called class groups to implement different kinds of polynomial commitments than SNARKs or STARKs (remember Kate commitments). Hidden order groups are unique in that they compress arbitrarily large integers into group elements to guard against spoofing. Many types of proofs can be built atop these polynomial commitment structures. 

Another option when using DARKs is to use Bulletproofs. Bulletproofs are short, non-interactive ZK proofs without requiring a trusted setup like SNARKs. In fact, Bulletproofs are rather small in that they often require less than 1kB for individual proofs, compared with over 10kB when using other ZK proofs. Bulletproofs also make use of elliptic curve groups, though this results in a slower verification process and higher fees in comparison. 

To put it into perspective, SNARKs can be thousands of times smaller than STARKs, while Bulletproofs offer performant compromises between the two. Due to their smaller size and simplicity, Bulletproofs and similar polynomial commitments are likely to proliferate in certain areas of Web3 where their strengths and tradeoffs make the most sense, for example on Monero’s blockchain.

Takeaways

ZK proofs not only benefit DeFi users, but also enable traditional institutions and data providers to confidentially monetize their sensitive or proprietary data. Instead of posting critical information directly on-chain, ZK proofs will be all that’s necessary to verify a prover’s knowledge of the data to be published or executed with greater confidentiality. 

Despite the benefits, it cannot be ignored that a trusted setup is not ideal, though blockchains like ZCash went to great pains to demonstrate their goodwill and honesty via an elaborate private key destruction ceremony when upgrading the protocol.

By combining the transparency of blockchains with the privacy and security of ZK proofs, mainstream and enterprise institutions can have their cake and eat it too, as they say. Why not maintain the privacy of our data while simultaneously leveraging the transparency inherent to Web3?

References

1. Bitansky, N., Kalai, Y. T., & Paneth, O. (2017). Multi-collision resistance: A paradigm for keyless hash functions. Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing.
2. Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., & Maxwell, G. (2018). Bulletproofs: Short proofs for confidential transactions and more. 2018 IEEE Symposium on Security and Privacy, 315-334.
3. Feige, U., Fiat, A., & Shamir, A. (1988). Zero-knowledge proofs of identity. Journal of Cryptology 1, 77–94.
4. Gabizon, A., Zachary J. Williamson, Z. J., & Ciobotaru, O. (2019). PLONK: Permutations over Lagrange-bases for oecumenical non-interactive arguments of knowledge. Cryptology ePrint Archive, Report 2019/953. 
5. Goldwasser, S., Micali, S., & Rackoff, C. (1989). The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1), 186-208.
6. Kate, A., Zaverucha, G. M., Goldberg, I. (2010). Constant-size commitments to polynomials and their applications. In M. Abe (Ed.), Advances in Cryptology – ASIACRYPT 2010. Lecture Notes in Computer Science, vol 6477.
7. Sarang, N. (2020, 24 Dec.). Bulletproofs+ in Monero. Monero Blog.

Related Articles

• Ethereum’s Proof of Stake, Explained
• Cryptographic Proof: Oracles & Stablecoins
• The Importance of Proof of Reserve Audits for DeFi and Crypto

Learn More

• What is Decentralized Finance?
• What are Smart Contracts?
• Risky Business: What is Yield Farming?