RIAN DATTA (L6)
Zero-knowledge proofs (ZKPs) are a powerful asset used in the field of cryptography that allow a party (the prover) to demonstrate to another party (the verifier) that they have access to a certain piece of information, without having to reveal the information itself. Since its first appearance in an MIT paper titled “The knowledge complexity of interactive proof systems” (written by Shafi Goldwasser and Silvio Micali in 1985), ZKPs have quickly become one of the most commonly used methods for keeping data secure online; even being implemented by companies ranging from Visa to Apple. But, why? In this article, the mystery of ZKPs will be unveiled as you learn the fundamentals of how they function, what they’re currently used for - including potential future applications - and their drawbacks.
You’re probably wondering how something so counterintuitive can actually exist and, although it may seem like technology straight out of a science-fiction movie, ZKPs use real mathematics in combination with cryptography principles to keep confidential data private. To fully understand the process algorithms go through to generate these ZKPs, you need to recognize that humans can carry out these proofs (without the complicated calculations) and you almost certainly have done before. A classic example of a common ZKP protocol is proving that Coke and Pepsi are 2 different drinks, despite their similar appearance. One approach is to do a blind taste test: you hand me cups of dark carbonated beverages that you poured yourself, and I tell you whether they are Coke or Pepsi. Since you poured them out, you know the drink that’s in each cup and so have the ability to verify whether I am correct or not. Assuming my answer is correct, we can repeat this process a few times until I have convinced you that 1) there is a noticeable difference between Pepsi and Coke, 2) you have no idea what this difference is! Another instance of a ZKP that humans can perform could be when trying to prove to a verifier that you know the answer to a particular Maths problem, without directly revealing the answer. To do this, you can convey the method used as well as the calculations carried out to find the answer. And behold! You have carried out a simple zero-knowledge proof. The verifier can then check your working to confirm whether the answer you have obtained is valid or not.
But what makes these proofs zero-knowledge? For a proof to be classified as a ZKP, there are a few basic requirements that need to be fulfilled:
- Completeness - the prover must be able to demonstrate knowledge of the information in question to a high level of accuracy.
- Soundness - the proof must be robust, meaning that it is not possible for the prover to cheat without being detected.
- Zero-Knowledge - the information being proved must not be communicated between the prover and verifier whatsoever.
- Verifiability - the verifier should be able to check the proof easily, without having to trust the prover or any other third-party.
Now that you understand the fundamentals of ZKPs, let's explore how they are implemented in computer systems. The 3 main steps of a ZKP involve the “witness”, the “challenge” and the “response”. The witness is the secret information that the prover claims they know. The prover’s hypothetical knowledge of the witness allows for a number of questions to be constructed that can only be answered by an entity with the required understanding of the witness. Thus, the prover initiates the process by randomly choosing a question, calculating the answer, and sending it to the verifier. The second stage consists of the verifier randomly choosing another question from the set and the prover is asked (or challenged) to answer it. The final phase includes the prover responding to the verifier by calculating the answer and subsequently sending it to the verifier to confirm whether the prover has access to the relevant knowledge. This process repeats as the likelihood of the prover lying gradually decreases until the verifier is satisfied.
It is important to note that the steps described above are for a special form of ZKP called an interactive ZKP. However, many leading companies now use non-interactive ZKPs, as they are more efficient and require less communication between parties. The main difference between non-interactive and interactive ZKPs is the use of a shared key, which is provided to both the verifier and the prover, allowing for data to be relayed directly between them in non-interactive ZKPs. Because of this key, only 1 round of communication is needed in which the prover passes the confidential information into a unique algorithm to compute a ZKP. This proof is sent to the verifier, who checks if the prover’s input is correct through the use of another algorithm. This means that, once a proof has been generated, it is available for any third-party to use if they want to verify whether a different prover has knowledge of the same witness (as long as the third-party has access to the shared key and the correct verification algorithm).
This innovative way of exchanging data between different parties has made sharing Personally Identifiable Information (PII) like biometrics, credit card numbers and passport numbers with third-party services unnecessary. Prior to the implementation of ZKPs, this was a key security issue with many different online platforms since the PII was stored in databases that could be hacked, leading to a data breach. From this, more serious problems could arise such as identity theft and, with the internet being more accessible than ever, cyber crime rates are ever-increasing. Consequently, exchanging private data with external companies was a risk few were willing to take. However, with the use of ZKPs, user data is no longer at risk as the host company themselves don’t even have access to it, reducing the users' vulnerability to cybercrime.
Because of this unique characteristic, ZKPs are well-suited for a variety of applications. For example, ZKPs are commonly utilised in authentication systems to verify credentials without users needing to reveal the specific details themselves e.g a user can prove they are an adult without the necessity of explicitly stating their age. Similarly, companies can prove that they have a certain amount of assets without specifying their exact financial details. This opens up a wide range of potential applications for ZKPs, such as secure voting systems, digital identity verification, and protected financial transactions.
Another implementation of ZKPs resides in the world of cryptocurrency. Since payments made on a credit card are usually visible to multiple parties like banks and payment providers, digital currencies are increasingly being used to perform anonymous payments. This is done through the use of “private coins” and “privatised blockchains”, which conceal all transaction details from sender and receiver addresses to asset type/quantity. One of the most popular privatised blockchains used is called Zcash. Zcash makes use of a special type of proof known as a “zero-knowledge Succinct Non-Interactive Argument of Knowledge” (zk-SNARK) in its protocols to permit nodes in the network to validate purchases without the need for transaction data. In this way, ZKPs are used in combination with many different types of modern technology because of the widespread demand for security.
Nonetheless, ZKPs do come with their own downsides as all forms of technology do. One of the most significant disadvantages of ZKPs is the hardware costs. The generation of ZKPs requires a plethora of complex mathematical calculations to be carried out on specialised machines. These machines tend to be much more computationally powerful than your average Dell computer so that they can withstand such processor-intensive tasks. Consequently, these devices are extremely expensive and so inaccessible for regular people. To add to this, proof verification costs are also high, with up to $1,000,000 being paid to verify a single zk-SNARK proof for Ethereum.
Another problematic issue is that most ZKP algorithms use a technique called elliptic curve cryptography to encrypt data being shared between the prover and verifier. However, this security model is now at risk due to the rapid development of quantum computers, which have shown to be quite efficient at bypassing models built using similar techniques. As a result, anyone with a quantum computer (and the correct skills) could potentially access private data being passed through ZKP algorithms in the future. Additionally, ZKPs are heavily reliant on the robustness of their underlying assumptions, on which the verification algorithms are created. If these assumptions are not met, the proof may not be sound, meaning that the prover could cheat the system without being detected. These same algorithms are the reason for the lack of versatility when it comes to ZKPs. Each proof is designed for a specific scenario and cannot be adapted to other situations, eventuating in another ZKP having to be generated, which we already know to be an expensive and time-consuming process.
To conclude, zero-knowledge proofs are a relatively new and developing technology that is actively being researched. One of the main challenges in the field is to find ways to make ZKPs more efficient and practical, as well as to find new applications for them. However, it's a promising technology that has the potential to revolutionise the way we think about privacy and security in the digital age.
Sources (last accessed 21st January 2023):
[1] https://uxplanet.org/zkproof-4509f8c83959
[2] https://academy.binance.com/en/glossary/zero-knowledge-proofs
[3] https://www.youtube.com/watch?v=fOGdb1CTu5c
[4] https://ethereum.org/en/zero-knowledge-proofs/#drawbacks-of-using-zero-knowledge-proofs
[5] https://youtu.be/OcmvMs4AMbM