Unraveling SNARKs: From Succinct Non-Interactive Proofs to Interactive Proofs and Beyond
Structure:
Introduction:
SNARKs, or Succinct Non-Interactive Arguments of Knowledge, stand as a significant component of modern cryptographic schemes. This technology allows for brief, quickly verifiable proofs of a statement's truth. SNARKs’ potential extends to a plethora of applications, such as hashing large files and facilitating efficient interactions on blockchains. Although often compared to their cousin, interactive proofs, SNARKs exhibit unique properties that warrant exploration. This article dives into the nuanced distinctions between SNARKs and interactive proofs, elucidates the characteristics of interactive proofs and arguments, and delves into the concept of public verifiability.
Recall: What is a SNARK?
A SNARK stands for Succinct Non-Interactive Argument of Knowledge. In essence, it's a brief proof that a certain statement is true, with 'succinct' implying that the proof is short and quick to verify. For example, consider a claim that a certain message M hashes to the value zero. In this case, a trivial proof would be to specify the message M that the prover claims to know, then the verifier can verify this by applying the hash function to the message and confirm if the output is indeed zero. However, if the message is a large file, applying the hash function would be time-consuming and not succinct. This is where SNARK comes in, providing a proof that is shorter and faster to verify than the trivial proof. The non-interactive part means that the proof can be written down and posted to a blockchain, without requiring any exchange of messages between the prover and the verifier.
Interactive Proofs
An interactive proof is related to SNARKs but not the same. An interactive proof is a conversation between a prover and a verifier where the prover attempts to convince the verifier that a certain claim is correct. The prover in this case solves a problem and provides an answer to the verifier who doesn't directly trust the claim but instead challenges the prover. If the prover is honest and returns the correct answer while following the prescribed protocol, the verifier will accept. However, if the prover provides an incorrect answer, the verifier, with high probability, will reject. Interactive proofs are required to be statistically sound, meaning they are sound no matter how hard the prover works to convince the verifier. This is in contrast to interactive arguments which are only sound against polynomial time cheating provers.
Interactive Proofs and Arguments
There's a difference between knowledge soundness and soundness. In a knowledge sound protocol, the prover claims to know a witness w such that evaluating the circuit on x followed by w results in the output 0. In a sound protocol for circuit satisfiability, the prover is only establishing the existence of such a witness w, not that it necessarily knows that witness w. There are situations where standard soundness is meaningful but knowledge soundness isn't and vice versa. For example, if the prover claims to know a secret key that controls a certain Bitcoin wallet, standard soundness is not meaningful but knowledge soundness is. In summary, while both notions can be meaningful, in many cryptographic contexts, knowledge soundness is what's desired, hence the focus on SNARKs (with a k) in this lecture.
Public Verifiability
The unique difference that sets apart zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) from interactive proofs is its non-interactive nature, as indicated by the 'N' in the abbreviation. On the contrary, interactive proofs and arguments, as the name implies, require interaction.
领英推荐
This interactivity entails that interactive proofs and arguments are convincing only to the verifier who selects and sends challenges to the prover. The process is somewhat like a dialogue, where the verifier poses a challenge, and the prover responds with a suitable answer. A bystander, watching this back-and-forth process unfold, cannot ascertain the authenticity of the challenges nor their randomness. It becomes impossible to rule out the possibility of prior collusion between the verifier and prover, leading to pre-arranged challenges and responses.
In effect, interactive proofs and arguments can only persuade the specific verifier interacting with the prover at that time. If there are numerous parties needing to verify a claim, the prover would have to interact with each one separately to convince them. This proves impractical, especially in blockchain applications, where these proofs need to be posted on-chain for multiple nodes across the world to verify.
A saving grace exists in the form of the Fiat-Shamir transformation. This cryptographic tool is employed to transform public coin protocols, a type of interactive proof, into non-interactive and publicly verifiable protocols. The process involves designing an interactive public coin protocol and subsequently applying the Fiat-Shamir transformation to make it non-interactive and publicly verifiable.
In essence, the Fiat-Shamir transformation replaces the verifier's random challenges in the interactive protocol with hashes of the messages the prover has sent until that point in the protocol. This means that the verifier doesn't have to actively send any challenges to the prover. Instead, these challenges are determined via hashing, and the prover can manage the hashing independently.
This provides a way to emulate random challenges from the verifier, despite the verifier not actually selecting them, offering a rough intuition for how the Fiat-Shamir transformation works. We will dive deeper into the Fiat-Shamir transformation later in this course.
Having laid out the differences between interactive proofs and zk-SNARKs, we can summarize them into three primary distinctions. Firstly, interactive proofs are interactive, while zk-SNARKs are non-interactive. Secondly, interactive proofs are information-theoretically secure (also known as statistically secure), while zk-SNARKs are arguments, implying computational soundness. Lastly, zk-SNARKs are knowledge sound, a property that is not required for interactive proofs.
The first two differences, i.e., interactivity versus non-interactivity and computational soundness versus statistical soundness, can be largely eliminated if we employ the Fiat-Shamir transformation to make an interactive proof non-interactive.
With the definition of interactive proof established and its comparison to zk-SNARKs clarified, we can proceed to discuss how to develop a zk-SNARK starting from an interactive proof.
Conclusion:
In the realm of cryptography, SNARKs and interactive proofs serve as two distinct tools with unique strengths. Despite their differences—interactive versus non-interactive and computational soundness versus statistical soundness—these distinctions can be minimized through the Fiat-Shamir transformation, making an interactive proof non-interactive. Moreover, SNARKs are designed to be knowledge sound, a property not inherently required for interactive proofs. As we delve deeper into this fascinating field, the Fiat-Shamir transformation proves to be an indispensable tool, offering a promising route towards designing efficient, non-interactive, and publicly verifiable protocols. As we continue our exploration of this complex field, we inch closer to the goal of leveraging these technologies to build secure and efficient cryptographic systems.
P.S.
I believe that constructive feedback is essential for personal and professional growth, and I welcome any comments or thoughts you may have regarding my article. Your feedback will help me improve my writing and provide better content for you in the future.
If you found this article valuable, I encourage you to follow me on LinkedIn to stay updated on my latest posts. Your support and engagement mean a lot to me, and I am grateful for every like, comment, and share.
Thank you for your time, and I look forward to connecting with you.