Zero-knowledge Proof: IZKs, NIZKs, SNARKS, STARKS Explained.
Decoding the Cryptographic Symphony of IZKs, NIZKs, SNARKs, and STARKs.
Introduction to Proof-of-Knowledge
Proof of Knowledge (PoK) is a cryptographic protocol that allows a prover to demonstrate to a verifier that they possess certain knowledge or information without revealing the knowledge itself. The protocol ensures the correctness and reliability of the prover’s claims by requiring two essential characteristics: soundness and completeness.
Soundness means that if the prover does not possess the knowledge or information they claims to possess, then the protocol should not convince the verifier otherwise. Completeness means that if the prover possesses the knowledge or information, the protocol should convince the verifier of this fact. These two characteristics are essential to ensure the security and accuracy of PoK protocols.
In the Schnorr protocol, the prover starts by selecting a secret value x and computing a value g^x, where g is a publicly known generator of a cyclic group G. The prover then sends a commitment to the value g^x, typically in the form of a digital signature using x as the signing key.
The verifier then sends a random challenge e to the prover. The prover responds by computing a value r = x + e * w, where w is a random value chosen by the prover. The prover then sends the value r as evidence of their knowledge to the verifier.
The verifier checks that g^r = (commitment) * g^e, where (commitment) is the value previously sent by the prover. If the equation is true, the verifier accepts the proof and is convinced of the prover’s knowledge.
import random
import hashlib
# Define the parameters of the Schnorr protocol
q = 2**256–2**32–977
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
g = (Gx, Gy)
# Generate a random secret value x
x = random.randint(1, q-1)
# Compute the commitment to the value g^x
commitment = hashlib.sha256(str(g).encode() + str(pow(g, x, q)).encode()).hexdigest()
# Send the commitment to the verifier
# Verifier generates a random challenge value e
e = random.randint(1, q-1)
# Prover computes r = x + e*w
w = random.randint(1, q-1)
r = (x + e*w) % q
# Prover sends r to verifier
# Verifier checks that g^r = commitment * g^e
if pow(g, r, q) == (int(commitment, 16) * pow(g, e, q)) % q:
print("Proof is valid!")
else:
print("Proof is invalid.")In the context of Bitcoin, the Schnorr protocol is used to implement digital signatures for transactions. When a user wants to spend some Bitcoin, they create a transaction that includes a digital signature of the transaction data. The signature is computed using the Schnorr protocol, with the user’s private key x as the secret value. The signature serves as proof that the user is authorized to spend the Bitcoin without revealing their private key.
What is Zero-knowledge-proof?
In addition to soundness and completeness, PoK protocols can also be designed to have zero- Knowledge, where the prover can convince the verifier of their knowledge without revealing any information beyond the fact that they possess the knowledge.
Hence Zero-Knowledge Proof (ZKP) is a subset of PoK that provides an even stronger level of privacy, as the verifier is convinced of the prover’s knowledge without gaining any additional information beyond the fact that the prover has the required knowledge.
Zero-knowledge proofs first appeared in an MIT 1985 paper, “The knowledge complexity of interactive proof systems, But it has seen rapid real-world application in recent years. As the popularity of blockchain technology continues to grow, it has become increasingly clear that ensuring the privacy and confidentiality of user data is paramount to the success of many blockchain use cases. Hence ZKP has gained wide adoption among many blockchain networks.
The technical implementation of PoK and ZKP involves advanced cryptographic techniques such as interactive protocols, commitment schemes, and homomorphic encryption. The efficient execution of these protocols is also a crucial consideration. Various optimization techniques, such as non-interactive zero-knowledge proofs (NIZK) and succinct zero-knowledge proofs (SZK), have been developed to reduce computational effort.
How Do Zero-Knowledge Proofs Work?
A zero-knowledge proof operates through the verifier posing a set of actions for the prover to perform that can only be executed correctly if the prover has knowledge of the underlying information. Should the prover merely guesses at the result of these actions, the verifier’s test will ultimately demonstrate the inaccuracy with a high probability?
Beyond the innate features (soundness, completeness, & Zero-knowledge) of zero-knowledge-proof, the primary form of a ZKP consists of three elements: witness, challenge, and response.
The witness is the secret information that the prover wants to prove knowledge of. This information is the basis for the set of questions that the verifier will ask the prover. The prover begins the proving process by randomly selecting a question from the set, calculating the answer based on their assumed knowledge of the witness, and sending it to the verifier.
The verifier then randomly selects another question from the set and asks the prover to answer it. The prover accepts the question, calculates the answer based on their assumed knowledge of the witness, and returns it to the verifier. This process of challenge and response continues, with the verifier selecting additional questions from the set and the prover providing answers until the verifier is satisfied that the prover truly has knowledge of the witness.
To ensure that the prover isn’t just guessing blindly and getting the correct answers by chance, the verifier selects more questions to ask. By repeating this interaction many times, the possibility of the prover faking knowledge of the witness drops significantly until the verifier is satisfied.
The Interactive & Non-Interactive Zero-Knowledge-Proof.
The two fundamental types of Zero-Knowledge Proof (ZKP) are interactive zero-knowledge proofs and non-interactive zero-knowledge proofs.
Interactive zero-knowledge proofs
Require communication between the prover and verifier. In interactive zero-knowledge proofs, the prover and verifier engage in a back-and-forth protocol to establish the proof.
Interactive proving was the earliest method used for implementing zero-knowledge proofs, but it had several limitations. One of the significant limitations was that both the prover and verifier needed to be present and repeatedly interact to establish the proof. This requirement made it impractical for many applications, as it was not possible to pre-compute the proof, and the verifier had to be involved in every proof validation.
Moreover, the proof generated by the interaction could not be used for independent verification, as computing a new proof required a new set of messages between the prover and verifier. As a result, interactive proving was not scalable, making it unsuitable for many real-world applications.
Non-interactive zero-knowledge
Address the limitations of interactive ZKPs, as they do not require any interaction after the initial setup. The NIZKP uses a precomputed setup to allow the verifier to check the proof without further interacting with the prover.
NIZKs have a wide range of applications, including secure multi-party computation, digital signatures, and anonymous credentials.
The development of NIZKs was a significant breakthrough for cryptography, as they provide a more efficient and flexible method for proving knowledge without interaction. In a NIZK, the prover generates a single proof that anyone can verify without the need for additional interaction. This makes NIZKs highly useful in situations where parties cannot interact or where interaction is expensive or impractical.
A key component of NIZKPs is the use of public parameters or a Common Reference String (CRS) that a trusted third party generates. The CRS is a set of public values that both the prover and verifier agree to use during the proving and verification process.
The generation of the CRS is a crucial and sensitive operation, as any compromise in its randomness or security can lead to false proofs being generated by a malicious prover. Therefore, the generation of the CRS is typically performed by a trusted setup ceremony, where a group of participants collectively generate the parameters securely and randomly. This helps to ensure that no single participant can manipulate the parameters to generate false proofs.
Once the CRS is generated, the prover uses it along with their witness to generate proof without any interaction with the verifier. The verifier then checks the proof using only the CRS and their own inputs without interacting with the prover. This enables NIZKPs to be used in situations where interactive proving is not practical or feasible.
The Non-interactive zero-knowledge proofs (NIZKPs) have several technical components that enable them to function, which include:
Commitment scheme: A commitment scheme is used to allow the prover to commit to their witness in a way that cannot be changed later. This allows the verifier to check the prover’s claim without revealing the witness.
Hash functions: Hash functions are used to generate a random seed for the commitment scheme and to compress the size of the proof.
Public parameters: NIZKP schemes typically require a set of public parameters, which are generated during a one-time setup phase. These parameters are used in the verification process to ensure that the proof is valid.
Trapdoor function: A trapdoor function is used to ensure that the prover cannot generate false proof without knowing a secret key. This allows the verifier to trust that the proof is valid even if the prover is trying to cheat.
Fiat-Shamir heuristic: The Fiat-Shamir heuristic is used to convert an interactive proof into a non-interactive proof. This involves using a hash function to generate a random value from the verifier’s challenges, which the prover can use to complete the proof without interacting with the verifier.
Public reference string or common setup: A set of public parameters generated through a trusted setup process that is used by all parties to generate and verify proofs. This enables NIZKPs to achieve highly efficient proofs while still providing a high degree of security.
zk-SNARKs & zk-STARKs; The two main types of Zero-Knowledge Proofs.
zk-SNARKs
Stands for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge, which implies the type of zero-knowledge proof protocol that allows for the efficient verification of computational integrity without requiring interaction between the prover and verifier.
Succinctness implies that the proof is smaller than the witness and can be verified quickly, which is useful for blockchain applications.
This efficiency is particularly important for blockchain systems, as it enables the network to process large numbers of transactions quickly and with minimal computational overhead. In addition, the low storage requirements of zk-SNARKs make them suitable for use in resource-constrained environments, such as mobile devices or IoT devices, where storage space is limited.
Non-interactivity means that the prover and verifier only interact once, unlike interactive proofs that require multiple rounds of communication, making zk-SNARKs efficient.
Argumentation means that the proof satisfies the soundness requirement, making cheating extremely unlikely.
Of Knowledge refers to the fact that without knowing the secret information or witness, it is nearly impossible for a prover to produce valid proof. In other words, the prover must have access to the witness to construct valid proof; otherwise, they would not be able to demonstrate knowledge of the information being proven.
zk-STARKs
zk-STARKs stands for Zero-Knowledge Scalable Transparent Argument of Knowledge. The name provides insight into the technical key components and implications of this type of zero-knowledge proof.
Zero-knowledge: As with zk-SNARKs, zk-STARKs also provide zero-knowledge proofs. Verifiers can validate the integrity of a statement without learning anything else about the statement.
Scalable: Unlike zk-SNARKs, which have a fixed size and cannot scale, zk-STARKs are highly scalable, meaning they can handle larger computational tasks while maintaining a low degree of complexity. This makes zk-STARKs ideal for blockchain and other decentralized systems where scalability is critical.
Transparent: Unlike zk-SNARKs, which require a trusted setup phase to generate the public parameters used to create the proof, zk-STARKs are transparent, meaning they do not require a trusted setup. This makes zk-STARKs more resistant to attacks and reduces the risk of centralization.
Argument: Similar to zk-SNARKs, zk-STARKs also satisfy the soundness requirement, ensuring that cheating is highly unlikely.
(Of) Knowledge: As with all zero-knowledge proofs, zk-STARKs require access to secret information, which is called the “witness.” Without access to the witness, it is difficult if not impossible, for a prover to construct a valid zk-STARK.
Zero-Knowledge Proof Use Cases
Zero-knowledge proofs (ZKPs) have a variety of use cases across industries. They provide a method of proving knowledge without revealing sensitive information, making them ideal for applications that require privacy and security. Here are five common use cases for ZKPs:
Anonymous payments:
ZKPs can be used for anonymous transactions, which can be valuable in situations where parties want to protect their identities. One example is the cryptocurrency Zcash, which uses ZKPs to shield the details of transactions while still allowing them to be verified.
Another example is the AZTEC Protocol, which uses ZKPs to enable private transactions on Ethereum. This allows users to transfer ERC20 tokens without revealing the amounts or addresses involved.
Decentralized identity and authentication:
ZKPs can also be used for decentralized identity and authentication. They allow users to prove their identity without revealing any personally identifiable information. One example is the Sovrin Network, which uses ZKPs to enable self-sovereign identity on a public blockchain. Civic, which uses ZKPs, provides a more secure and privacy-focused alternative to traditional identity verification methods that rely on centralized databases storing sensitive personal information.
Verifiable computation:
ZKPs can be used for verifiable computation, where computation is performed on sensitive data without actually revealing the data. One example is Enigma, a decentralized data marketplace that uses ZKPs to allow computations to be performed on encrypted data.
StarkWare uses ZKPs to develop two distinct products: StarkEx, which is a permissioned Validity-Rollup that can function on its own, and StarkNet, a permissionless decentralized ZK-Rollup.
Highly scalable and secure layer 2s:
KPs can be used for highly scalable and secure layer 2 solutions, which are needed for blockchain networks to scale to support large numbers of users. One example is the company Loopring, which uses ZKPs to enable high-throughput, non-custodial trading on Ethereum.
Limitations of Zero-Knowledge-Poofs
- The setup of ZK-SNARKs and ZK-STARKs requires a trusted setup, which means that a group of individuals has to come together to generate and distribute the initial parameters of the system. If the trusted setup is not executed correctly, it can lead to a compromise of the entire system.
- ZK-SNARKs and ZK-STARKs are computationally intensive and require a lot of processing power to generate and verify the proofs. This can make them impractical for use in certain scenarios.
- While ZK-SNARKs and ZK-STARKs can prove the validity of a statement in constant time, they have a high overhead cost for small computations, which makes them unsuitable for some use cases.
- ZK-SNARKs and ZK-STARKs are not completely transparent, as they require a significant amount of specialized knowledge to understand and verify the proofs.
- Even though ZKPs are designed to operate in a trustless environment, they still require trust in the underlying mathematical assumptions and the integrity of the individuals involved in the setup process.
- ZK-STARKs are still in the early stages of development, and their scalability has yet to be fully demonstrated.
