Compilation: Cindy, SophonLabs
With the continuous development of computer technology, we can easily store, transmit and process large amounts of personal and business data on the Internet. However, in this Crypto age, concerns about data privacy and security are also increasing. In order to protect the privacy of data, cryptographers have developed many technologies, among which Zero-Knowledge Proof (ZKP) is one of the core technologies. In this article, we break down the implementation differences in zero-knowledge proofs.
Interactive and non-interactive zero-knowledge proofs
The two main types of zero-knowledge proofs are interactive and non-interactive. Both interactive zero-knowledge proof and non-interactive zero-knowledge proof are processes between a prover and a verifier, but they differ in the interactive process of the proof.
Interactive zero-knowledge proofs (IZKP) require a prover and verifier to engage in a back-and-forth dialogue in which the prover responds to the verifier’s queries. This interaction can take place in person or over a network such as the Internet. Multiple rounds of interaction with the verifier are required so that the verifier can ask additional information about the statement being proved. In each round, the prover needs to provide an answer to the verifier’s query.
This interactive proof method is feasible for some complex problems, but may introduce time and computational cost issues, and requires all participants to communicate. On the other hand, non-interactive zero-knowledge proofs (NIZKP) do not require any interaction between the prover and verifier. Non-interactive zero-knowledge proof means that the prover can generate the proof once and send it to the verifier without multiple rounds of interaction. Non-interactive proofs are faster and require less computation and communication than interactive proofs. However, it may not be a viable solution at times, such as when a proof involving additional information is required, or when a very complex statement needs to be proved. Instead, the prover creates a single, self-contained proof that the verifier can independently verify without further communication. This is more convenient and efficient than interactive proofs because it does not require the prover and verifier to be online or exchange multiple messages at the same time.
One of the most classic ways to achieve this is to use the Fiat-Shamir heuristic based on Crypto signatures. One of the main differences between interactive and non-interactive zero-knowledge proofs is the level of trust required between the prover and verifier. In interactive proofs, the verifier must trust the prover to abide by the protocol and provide honest responses to their queries. In non-interactive proofs, on the other hand, the verifier does not need to trust the prover at all, since they can independently verify the proof without relying on any information provided by the prover. Another difference between the two types of zero-knowledge proofs is the level of computational complexity required.
Interactive proofs tend to be more computationally intensive than non-interactive proofs because they require the prover and verifier to exchange multiple messages and perform additional computations. On the other hand, non-interactive proofs require only one computation from the verifier, making them more efficient and scalable. Both interactive and non-interactive zero-knowledge proofs have pros and cons, and the best choice for a given scenario will depend on specific requirements and constraints. Interactive proofs may be more suitable for situations where the prover and verifier are online at the same time and can communicate easily. In contrast, non-interactive proofs may be more suitable for situations where the prover and verifier are not online at the same time or the credibility of the prover is uncertain. In conclusion, interactive zero-knowledge proofs and non-interactive zero-knowledge proofs are usually chosen according to specific problems and application scenarios.
Limitations of Interactive Zero-Knowledge Proofs (IZKPs)
Interactive zero-knowledge proof is one of the earliest researched and widely used zero-knowledge proof types. In this proof process, there will be multiple rounds of interaction between the prover and the verifier. These interactions are designed to allow the verifier to ask the prover for specific information in order to verify what is being proved. This interactive nature makes interactive proofs very effective for solving complex problems.
A simple example is the famous “colored graph problem”, which is about how to color any graph. If the prover claims that he can color every node in any graph, and adjacent nodes must use different colors, then the verifier can adopt an interactive zero-knowledge proof method to judge whether this claim is true. In the proof process, the prover first colors the graph in a certain way, then the verifier chooses any two nodes and asks the prover whether they are colored the same color. The prover needs to answer this question, but cannot reveal why he chose that way. This process goes on for several rounds where the verifier can check some random data about how the prover colored the graph. If the prover answers the question reliably, the prover can be considered correct. Interactive zero-knowledge proofs (IZKPs) have several limitations, thus making them more expensive and complex.
IZKP requires interactions between provers and verifiers, which can be inefficient and time-consuming. To complete a proof, the prover must send multiple messages back and forth with the verifier. This can take a lot of time, especially if the proof is complex or involves large amounts of data. This can be a problem when speed is critical, such as in high-frequency trading or real-time decision-making.
IZKP does not scale well. As the data to be proved increases, the complexity of the proof also increases, and it is difficult to complete the proof in a reasonable time. This can be a problem when large amounts of data need to be justified, such as in supply chain management or healthcare.
IZKP relies on the assumption that the prover and verifier are honest and will not try to cheat or manipulate the proof. However, this assumption is not always valid and the prover can try to fool the verifier by sending false messages or manipulating the proof in some way. This could compromise the integrity of the proof and undermine its usefulness.
IZKP requires specialized encryption techniques, which can be difficult to implement and require a high level of technical expertise. This may make it difficult for non-technical users to use IZKPs, and may limit their adoption in some cases.
Overall, while IZKPs have the potential to provide strong security and privacy guarantees, the aforementioned limitations have historically hindered their widespread use. But it has some disadvantages. In particular, such proofs require multiple rounds of interaction between the prover and verifier, which introduces time and computational cost issues and requires communication among all participants. Second, some applications may need to process information so complex that multiple rounds of interaction between the prover and verifier are necessary to obtain a complete proof, which makes interactive proof methods less feasible. Once you understand the difference between interactive and non-interactive ZKPs, it’s time to delve into the most popular blockchain and crypto industry implementations — zkSNARKs. While zkSync uses zkSNARKs, arguably the most popular L2 using ZKPs, Starkware’s zkSTARKs are a close second. Let’s understand how these two implementations differ and the pros and cons of each.
zkSNARKs and zkSTARKs
Both zkSNARKs and zkSTARKs are zero-knowledge proof (ZKP) systems that allow one party (the prover) to prove to another party (the verifier) that a statement is true without revealing any information about the statement itself. ZKPs have many applications, including privacy-preserving transactions on blockchains, secure multi-party computation, and anonymous communications. They are both used to protect privacy in data transactions and calculations, but their application scenarios and technical solutions are quite different. The technical advantage of zkSNARKs lies in highly compressed small proofs, which support high privacy protection and efficient transactions while ensuring computational security. The technical advantage of zkSTARKs lies in the optimization of complex algorithms and large-scale data processing performance, which can achieve higher levels of protection and proof.
zkSNARKs
zkSNARKs are a method of using highly compressed algorithms to provide very small proofs that can be used to prove arbitrary computations that satisfy certain conditions. By using zkSNARKs technology, it is possible to obtain a verified proof that the specific values and detailed steps of the described calculation are unknown. The advantage of zkSNARKs is that the proof size is very small. Only a proof of about 200 bytes is needed to verify a result after millions of calculations, and the computational cost of the proof is relatively low. At the same time, they allow for efficient privacy protection of cryptography-based computations, especially useful when verification is required but information is unwilling to be revealed. Therefore, zkSNARKs are widely used in the fields of transactions, encryption, authentication and privacy protection in a trustless environment. zkSNARKs (Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge) were first proposed in a 2014 paper by Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. They are based on “non-interactive proofs”, which means that the prover and verifier do not need to communicate with each other during the proof process. This makes zkSNARKs ideal for use in blockchains where communication between parties is limited by the need to reach consensus. zkSNARKs use a combination of public and private keys to create proofs. Provers have access to the private key, which they use to generate proofs of statements they wish to make. The verifier has access to the corresponding public key, which is used to verify the proof. If the proof is valid, the verifier can be confident that the statement is true, even if they don’t have any information about the statement itself.
-
Advantages of zkSNARKs
One of the main advantages of zkSNARKs is their efficiency. The proof process is very fast, making it possible to use zkSNARKs in high-throughput systems such as blockchains.
-
Disadvantages of zkSNARKs
They rely on a “trusted setup” process in which a set of actors generates and destroys a set of public and private keys. If this procedure is not performed correctly, the security of the system may be compromised. Therefore need to be able to set up and participate in trusted third parties, have different performance depending on the data, and their proofs can be attacked by various attack techniques.
Additionally, zkSNARKs are not transparent, meaning the proof cannot be verified to be correct without access to the private key.
zkSTARKs
zkSTARKs are another zero-knowledge proof technology designed to handle complex algorithms and large-scale data. In contrast, zkSTARKs can provide greater security without the need for an intermediary, as they do not require the participation and setup of a trusted third party. The advantages of zkSTARKs include not needing to select a specific curve for calculation, prove to be more general, and have good scalability and attack resistance. They also do not have any secret keys or public parameters, which makes them ideal for key-based computation in a trustless environment. However, zkSTARKs technology requires higher computational cost and larger proof size than zkSNARKs technology, so it may not be suitable for use in some scenarios.
-
Advantages of zkSTARKs
One of the main advantages of zkSTARKs is their transparency. With zkSNARKs, the correctness of the proof cannot be verified without access to the private key. Using zkSTARKs, it is possible to create a “proof of verification” that allows anyone to verify the correctness of the proof without accessing any secret information. This makes zkSTARKs a more secure and transparent option for applications where trust is essential.
Another advantage of zkSTARKs is their scalability. zkSNARKs rely on complex mathematical operations that are resource-intensive, and they become less efficient as the proof size increases.
-
Disadvantages of zkSTARKs
A major drawback is that zkSTARKs are only suitable for proving the authenticity of certain types of claims. In particular, they can only be used to prove the truth of statements expressed in polynomials, which limits their applicability.
Another disadvantage is that zkSTARKs are not fully non-interactive and require a trusted setup phase where a common reference string (CRS) is generated. This CRS must be kept private and secure for zkSTARK proofs to be considered valid. If the CRS is compromised, the security of the proof is also compromised.
Additionally, zkSTARKs are not yet widely used or well understood, so potential vulnerabilities may not have been discovered yet. The lack of widespread adoption and understanding also means a lack of tools and resources to use zkSTARKs, making it more difficult to implement and use them in practice.
Finally, zkSTARKs are still relatively new and untested compared to other zero-knowledge proof systems, meaning their long-term security and reliability are not yet fully understood. This uncertainty can be a drawback for organizations or individuals looking for a proven and reliable method to verify the truthfulness of claims.
Summarize
While zkSTARKs offer some benefits in terms of efficiency and security, there are also some drawbacks to consider when deciding whether to use them. These disadvantages include limited applicability, the need for a trusted setup phase, lack of widespread adoption and understanding, and uncertainty about its long-term safety and reliability. zkSNARKs are based on the broken line algorithm on the curve, which can be used to prove that some calculation results are correct without revealing the calculation input and key. This technology can be applied in fields such as blockchain, cryptocurrency and cryptography.
Unlike zkSNARKs, zkSTARKs are built within the framework of succinct interactive proofs, which means proofs can be easily verified without involving any interaction between the prover and verifier. Therefore, zkSTARKs have greater advantages in both security and scalability.
With the development of technology, zero-knowledge proof technology will continue to develop and apply. In terms of privacy protection and security verification, zero-knowledge proof technology has a very broad application prospect. At the same time, with the development and optimization of the protocol, the computational efficiency and proof size of the zero-knowledge proof technology will also be improved, thereby further promoting its popularization and application in practical applications.