-01_edited.png)
This article is a comprehensive introduction to zero-knowledge proofs (ZKPs). We begin by introducing ZKPs and outlining how they work, then explore the advantages and use-cases of the technology, before ending with challenges facing the current state of ZKPs.
The interaction between prover and verifier in a zero-knowledge proof
The Latest Innovation in Blockchain: Zero-Knowledge Proofs
Zero-knowledge proofs (ZKPs) have taken the blockchain space by storm, becoming one of the most highly talked about and researched technologies of 2023 thus far. ZKP is a cryptographic concept used to demonstrate knowledge of a secret without revealing the secret. As shown above, it enables an individual (‘a prover’) to prove to another individual (‘a verifier’) that a statement is valid, without sharing the contents of the statement.
The idea of ZKPs were first introduced in a 1985 MIT paper, The knowledge complexity of interactive proof systems, by authors Shafi Goldwasser and Solvio Micali. ZKPs have recently garnered much attention given widespread concerns over data privacy and identity theft as our lives are increasingly lived in the digital realm.
One of blockchain technology's most celebrated features is the high degree of transparency, allowing all parties to publicly view transactions and its code, creating a trustless system for all to interact. However, as our identities become increasingly prevalent online, and central databases storing our data become increasingly vulnerable to hacking, striking a balance between transparency and user privacy is critical. Blockchain technology needs to enable user confidentiality and data security over sensitive information, and this is where ZKPs come into play.
ZKPs can be used for a variety of purposes that require privacy and security, such as digital currencies, online voting systems, and secure data sharing.
Where's Waldo?
An image from the Where’s Waldo children’s puzzle book series
Many of you may be familiar with Where’s Waldo, a nostalgic picture book that has readers scavenge the page for Waldo, a character known for his distinct red and white striped shirt. How does this relate to zero-knowledge proofs? Well, what if I could convince you where Waldo is located, without spoiling the fun and revealing his true position. That is the power of zero-knowledge proofs.
As shown below, I could grab a large piece of paper with a hole barely large enough to show Waldo. By covering the page, I can prove my knowledge of Waldo’s location without showing more context, such as Waldo’s immediate surroundings. As a result, no information has been leaked about his location, but I have proved my knowledge of it. The Waldo example is a simplified version of how ZK proofs work.
Proof of Waldo’s location without revealing it
Here’s another example. Imagine you and a group of friends are trying to get through a secret door with restricted access. In order to walk through, you must convince the doorkeeper that you know the secret password, but you don’t want to reveal the password in front of everyone. Therefore, you must convince the doorman that you know the password without actually revealing it. This is how you could use zero-knowledge to do so:
Step 1: You and the doorkeeper must agree upon a set of rules for the zero-knowledge proof. This would likely include the specific set of actions you must take to prove your knowledge of the password.
Step 2: Using the agreed-upon rules, the doorkeeper creates a proof for you to solve. This may range from correctly solving a mathematical puzzle to successfully completing a certain action, which demonstrates your knowledge of the secret password.
Step 3: Finally, the doorkeeper will verify the proof, and if it follows the agreed-upon rules, it can be concluded that you know the secret code without actually revealing it to all.
Now that we’ve covered what a zero-knowledge proof looks like, let’s dive into how ZKPs actually work.
How Do Zero-Knowledge Proofs Work?
As mentioned above, each zero-knowledge proof starts with two parties: a prover and a verifier. In each case, the prover attempts to prove something to the verifier without revealing any information other than the validity of their statement. For a true zero-knowledge proof to exist, it must satisfy three inherent properties:
Completeness: If the input is valid, the zero-knowledge protocol must return ‘true.’ This means that once the statement has been verified as true, the proof can be accepted.
Soundness: A lying prover cannot trick an honest verifier into believing an invalid statement is true because it is impossible to fool the zero-knowledge protocol into returning ‘true’ for an invalid input.
Zero-knowledge: The verifier will not obtain any information beyond the validity of the statement. Therefore, the verifier will have ‘zero-knowledge’ of any other information or private data.
In a ZKP, a succinct proof of validity, also known as a ‘witness’, is generated as input. This input simultaneously guarantees that the statement is valid while concealing the information used to construct it. The ‘witness’ is the first of three elements that every basic zero-knowledge proof is made up of. All three elements include:
Witness: The secret information is the “witness” to the proof, which is used to generate a set of questions that can only be answered with knowledge of the “witness.” From there, the prover states calculating answers to the questions and sending them to the verifier.
Challenge: The question that the verifier randomly picks from the set of questions is known as the challenge, which the prover is tasked with answering.
Response: The prover accepts the challenge, calculates the answer, and returns its response to the verifier. From there, the verifier can pick more challenges for the prover to respond to until they are confident the prover isn’t guessing and indeed has knowledge of the witness.
Interactive ZKPs vs. Non-Interactive ZKPs
The two fundamental types of zero-knowledge proofs are interactive and non-interactive ZKPs. In an interactive ZKP, the prover and verifier interact multiple times. In order to fully convince the verifier about the validity of a specific statement, the prover must successfully respond to a series of challenges set forth by the verifier. The amount of challenges can range, but is almost always more than one.
On the other hand, non-interactive proofs only require one round of interaction between the prover and verifier. This type of proof is much more efficient than interactive ZKPs because it reduces the necessary communication between the parties, but requires a lot more computational power than interactive ZKPs.
zkSNARKS vs. zkSTARKS
Another distinction must be made between two of the most compelling ZK technologies: zkSNARKs and zkSTARKs.
zkSNARKs, which stands for zero-knowledge succinct non-interactive arguments of knowledge, is a particularly efficient type of ZKP that proves the legitimacy of large amounts of data without revealing the actual data. Let’s break down how SNARKs work:
Succinct: SNARKs use proofs that are small and easy to verify, regardless of the complexity of the concept being proven. SNARKs generate a cryptographic proof using elliptical curves, also known as elliptic curve cryptography (ECC), which relies on the notion that determining the discrete logarithm of a random element in an elliptic curve from a publicly known base point is theoretically impossible. ECC is a popular choice of encryption for online security, and is often more secure than other forms, like RSA, which makes it more resistant against brute force attacks.
Non-interactive: back and forth communication is not required between the prover and verifier
Argument: cryptography and non-determinism
Of knowledge: refers to the fact that the prover has the evidence
zkSNARKs rely on a “trusted-setup” process, which implies that a group of participants are responsible for generating and destroying a set of public and private keys. If this process is not performed correctly, it may compromise the security of the system. zkSNARKs are often used in high-throughput applications given their efficient and fast process.
On the other hand, zkSTARKs can be used in a wider range of applications because they do not require a trusted setup. zkSTARKs stands for scalable transparent argument of knowledge. Let’s breakdown what scalable and transparent mean:
Scalable: zkSTARK proofs are scalable because the verification times only slightly increase when the witness grows, whereas zkSNARK verification times tend to increase linearly with the witness size.
Transparent: zkSTARKs rely on publicly verifiable randomness which is used to generate public parameters for proving an argument of knowledge.
Instead of using ECC like SNARKs, STARKs rely on computing hash functions, which offers benefits like being quantum resistant. However, STARKs have larger proof sizes than SNARKs which can lead to increased verification times and higher gas fees. Despite the fact that STARKs lack the developer documentation and community held by SNARKs, both are cutting-edge zero-knowledge technologies disrupting the market.
The Benefits of Zero-Knowledge Proofs
Increased Privacy and Security
Zero-knowledge proof is a valuable tool when it comes to protecting privacy and maintaining security across various contexts. Especially when sensitive information needs to remain confidential, ZKPs allow for the verification of information without revealing the underlying data. Specifically when dealing with personal information, one can be confident that using ZKP provides a high degree of security and privacy.
Reduced Data Exposure
Blockchain technology is a highly transparent, publicly accessible ledger that enables any individual the ability to view and download data. That being said, anyone can view the transactions that large corporations, banks, and individuals are making on the blockchain. Implementing ZKP technology will allow users and businesses to reduce the exposure of sensitive data and execute smart contracts while protecting their strategies, advantages, and trade secrets.
Enhance User Confidence
The implementation of zero-knowledge proof can also foster increased trust and loyalty from users. As personal information has become widely collected and stored online, growing concerns over data misuse has troubled users of large centralized internet sites. Organizations can provide their customers with greater confidence in their privacy and security by using ZKP, which is important for building a strong brand reputation.
Zero-Knowledge Proofs in Action
Anonymous Payments
Card payments, whether credit or debit, are increasingly becoming our go-to means for transacting value. With a mindless tap or swipe of a card, we can make money change hands in what appears to be a secure and safe process. What we fail to realize is that our transactions are highly visible to a range of parties, including banks, payment providers, and government agencies. All of this undermines the financial privacy of ordinary citizens.
Cryptocurrencies were the intended solution for this; providing a means by which people could conduct peer-to-peer transactions in a private manner without regulation or surveillance. However, most blockchain-based transactions are openly available to the public, and even with the use of pseudonyms for anonymity, it is possible to link real world identities to on-chain transactions using basic on and off-chain data analysis.
This opens up an avenue for the effective integration of zero-knowledge proofs in anonymous payment processes. By validating transactions without accessing transaction data, ZKPs can create a powerful hacker-proof process that protects the anonymity of both parties involved throughout the transaction. Zcash and Monero, which are digital currencies like Bitcoin, serve as prime examples of the powerful role ZKPs could play in anonymous payments. Unlike most cryptocurrencies, Zcash gives users the option to transact confidentially through the use of shielded addresses, providing complete anonymity and financial privacy. As a result, transactions can be completed without revealing information on the sender, receiver, transaction amount, asset type, and transaction timeline.
Identity Verification and Decentralized Identities
With modern technology, much of our Personally Identifiable Information (PII) shared with third-party services is stored in central databases, which are now increasingly vulnerable to hacking. A growing concern over identity theft and a lack of digital privacy has called for the implementation of greater security measures when handling personal information.
Zero-knowledge proofs can be used in identity management systems to validate credentials, specifically through the use of decentralized identities. A decentralized identity, also known as a self-sovereign identity, allows users to control access to their personal identifiers without revealing details. For example, a ZKP-based identity system could allow individuals to verify their citizenship of a certain country without sharing their passport information. Similarly, bank customers signing up for online services, subscriptions, or payments could validate their account without disclosing specific banking details. As a result, individuals can validate their identity without revealing sensitive details, protecting themselves from the perpetual risk of identity theft and hacking.
Businesses and organizations can also take advantage of zero-knowledge proofs to verify identities. For example, ZKPs can be used to provide secure and private identity verification compliance for regulatory procedures like KYC (know-your-customer) and AML (anti-money laundering). Businesses can ensure that only authorized individuals and users can access their systems, which could prevent fraud and costly data breaches. Furthermore, organizations like banks and hospitals that handle large quantities of personal information, can rely less on third-party services, and instead verify the authenticity of data stored on the blockchain, making it practically impossible for outsiders to access.
Authentication
Much like identity verification, zero-knowledge proof can be used for authentication processes such as logging in to websites. Access to certain websites often requires setting up an account and providing sensitive information such as name, age, address, and birth dates along with private login credentials. When users are juggling multiple passwords and logins, they are at risk of forgetting them, or even worse, being a victim of data leaks/hacks.
ZKPs can simplify the process of authentication by simply requiring users to present a proof of a secret (password, login, or code) to access confidential information. These proofs are generated once using public inputs, such as confirmation of a user’s membership, and private inputs, like a user’s login details. Using ZKPs for authentication would add multiple layers of security to important logins and files, making it harder for hackers and manipulators to retrieve data. Additionally, it alleviates online platforms from the burden and risk of storing large amounts of data.
Electronic Voting and Reducing Collusion
On-chain voting is another area where blockchain technology is making massive strides. In a world where guaranteeing secure and transparent elections has become practically impossible, blockchain voting schemes are becoming popular means of boardroom, member, and public voting for various circumstances. With many benefits of on-chain voting, such as being fully auditable, resistant to censorship, and shielded from attacks, blockchain voting schemes seem too good to be true. However, one crucial vulnerability still remains: collusion.
Collusion, which often takes the form of bribery, limits the effectiveness of seemingly fair processes that use voting to make decisions on governance and the distribution of scarce resources for corporations and DAOs. Given the public nature of the blockchain, bribers can easily inspect a bribee’s on-chain activity to see how they voted, and ultimately devise ways to manipulate their vote and the overall result. ZKPs can eliminate on-chain collusion by verifying the legitimacy of votes and aggregating voting tallies without revealing the actual votes themselves. By protecting voters’ privacy and proving their votes without revealing the data, ZKPs can introduce greater integrity to a process deserving of it.
Challenges facing Zero-Knowledge Proofs
Despite the massive opportunity for zero-knowledge proofs to disrupt the way we transact and share value, it is important to highlight the current limitations facing the technology. Being mindful of the shortcomings of ZKPs can help us pinpoint areas for improvement, and begin using the technology in an informed manner.
Complexity of Implementation
Zero-knowledge proof is a complex cryptographic concept that requires advanced mathematical knowledge to correctly implement. This can make it challenging for organizations and businesses to adopt, as it may require specialized expertise that is not yet readily available.
Computational Intensity and Hardware Costs
Zero-knowledge proofs, specifically interactive ZKPs, use computationally intensive algorithms that require many interactions between the prover and verifier. Interactive ZKPs on the other hand, require a lot of computational capabilities given the increased efficiency. On the Ethereum blockchain for example, it requires about 500,000 Ethereum gas to verify a single zkSNARK proof, with zkSTARKs requiring even higher fees. The significant hardware costs and computational intensity associated with verifying ZKPs make it impractical for many applications and unsuitable for less powerful devices, such as mobile phones.
Additional hardware costs and complexities arise when companies try adopting this technology. ZKPs may not be compatible with existing systems, which complicates the adoption process. ZKPs require its calculations to be performed on highly specialized systems, making it difficult to integrate into existing infrastructure or workflows, and adds to the excessive hardware costs linked with adoption.
Scalability
Related to the issue of computational intensity mentioned above, ZKPs could face difficulty when attempting to scale up for larger applications. The computational complexity of the proof increases as the size of the data set or the number of participants in a proof protocol increases, currently making it difficult to scale for widespread use.
Trust Assumptions and Misuse
Another shortcoming of ZKPs is that the effectiveness of the technology relies on the assumption that both parties, the prover and verifier, are honest parties acting with integrity. There is no way for users to assess the honesty of participants and there is insufficient protection against devious parties deceiving a verifier. As such, zkSNARKs in particular need to develop non-trusted setups, like zkSTARKs, to increase the security of proving mechanisms.
As with any revolutionary technology, there is always the potential for misuse. Zero-knowledge proof can be used for malicious purposes such as hiding illegal activities, collusion, and deceiving others. Without the ability to protect against dishonest actors, there is a risk that ZKPs can be misused or exploited by some.
Moving Forward
Zero-knowledge proofs have the potential to revolutionize the way we handle our data and transact value online. By increasing privacy and reducing data exposure, ZKPs have the potential to improve user confidence in a data driven world. Whether it’s used for finding Waldo or validating the liquidity of a bank, ZKPs have the potential to disrupt the way business is conducted and value is transacted, all while providing a sense of security, privacy, and trust. ZKP is a powerful technological advancement that has taken the blockchain space by storm, but it is still far from reaching its full potential.
Comments