What is Zero-Knowledge (ZK) Proof?
Zero-knowledge (ZK) proof has emerged as the most powerful cryptographic technology allowing more privacy and scalability in blockchain.
The ZK-proof is a protocol in which one party (the prover) can convince another party (the verifier) that the given statement is true, without conveying to the verifier any information beyond the mere fact of that statement’s truth, it’s either a message or computation on the blockchain.
Zero-knowledge protocols are mostly used for these purposes:
- Privacy: A ZK-Proof can prove knowledge of some secret without revealing the secret itself. Nothing about the data (or fact or “knowledge”) you are proving is revealed to the Verifier.
- Security: A ZK-Proof can be used to prove the correctness of some computation or if it was performed.
- Succinctness: A ZK-Proof can be used to prove that the result of a computation is correct without revealing the intermediate steps. It is more efficient to verify the proof than to directly check the original data itself.
There are several illustrations to understand the basics of ZK-proof better.
- The Alibaba Cave
- Two Balls and The Color-Blind Friend
- Where’s Waldo
1) The Alibaba Cave Analogy:
This story is about Peggy (Prover) and Victor (Verifier). Victor finds a ring-shaped cave with the entrance on one side and the magic door blocking the middle of the circle. Peggy claims that she uncovered a secret word that opens that magic door, but she doesn’t want to reveal this word to Victor. At the same time, Victor wants to make sure that Peggy knows the secret word.
So, Peggy and Victor agree on naming both paths (Path A and Path B). Then Peggy enters the cave and takes a random path without Victor. After that, Victor enters the cave and shouts the name of the path he wants her to use to return, either A or B, chosen randomly.
If Peggy really knows the secret word, she has no problem returning to Victor using the correct path. And if she doesn’t know, she still has a 50% percent of chance to go back from the same path she came in, without Victor realizing it. (For instance, Victor yells “A” and she comes back from A, because there is no other way she could use, but Victor doesn’t know if she opened the magic door or not.)
That’s why Peggy and Victor repeat this activity multiple times. After each repetition, Victor becomes more confident that Peggy knows the secret word. Victor’s confidence will rise towards, but never precisely, 100% since there is always a chance that Peggy was lucky in all repetitions.
As soon as Peggy returns using the wrong path, we can prove she didn’t know the secret word. Interestingly, we can make sure that Peggy doesn’t know the secret word, but we can never 100% verify that she does, only that it’s improbable that she doesn’t.
To sum up: The activity that Peggy and Victor repeat is:
- Peggy enters the cave.
- Peggy takes a random path and doesn’t reveal it to the Victor
- Victor enters the cave without any knowledge which side Peggy went
- Victor shouts the name of a random path for Peggy to come back
- Peggy returns using the path Victor shouted (in case she didn’t know the secret word and got unlucky, she returns the same way she came in).
This was an interactive ZK-proof example, which is not so suitable for blockchain, because in blockchain it’s highly cared that any proof should be public to everyone.
2) Two Balls and The Color-Blind Friend Analogy
Imagine you have 2 completely identical balls, but only they are in different colors (let’s say red and green). And your friend “Victor” is color-blind.
To Victor, the balls seem completely identical. Victor is skeptical that the balls are actually distinguishable and he doesn’t trust your word. You want to prove to Victor that the balls are in fact differently colored, but nothing else. You don’t even want to reveal which ball is the red one and which is the green.
Here is how this works: You give the two balls to Victor and he puts them behind his back. He chooses to reveal them by switching hands or not, resulting with equal probability. He will ask you, “Did I switch the ball/hands?” This whole procedure is then repeated as often as necessary.
This is also an interactive ZK-proof example, which is not so suitable for blockchain, because in blockchain it’s highly cared that any proof should be public to everyone
3) Where is Waldo? Analogy
In this example, the prover (Peggy) wants to prove to the verifier (Victor) that he knows where Waldo is on a page in a Where’s Waldo? image, without revealing his exact location to the verifier.
Peggy the Prover starts by taking a large black board with a small hole in it, the size of Waldo. The board is twice the size of the book in both directions, so the verifier cannot see where on the page the prover is placing it. The prover then places the board over the page so that Waldo is in the hole. As a result, Victor the Verifier is now convinced that Peggy the Prover knows where Waldo is but still, he doesn’t have an idea how he can find it in the big picture.
This is a non-interactive ZK-Proof example. It gives more information than interactive ones, therefore less secure, but way quicker because it doesn’t need repetition.
Types of Zero Knowledge Proofs
Interactive Zero Knowledge Proof and Non-Interactive Zero Knowledge Proofs are both important technologies in the field of cryptography, and they have their own advantages and disadvantages. Interactive ZK-Proofs are highly flexible and secure, but can be time-consuming and require a high level of trust between the parties involved. Non-Interactive ZK-Proofs are more efficient and scalable, but may be less flexible and may require a higher level of technical expertise. Non-interactive zero-knowledge proofs have found many applications in the blockchain area due to their transferability. Now, it helps us while we are helping developers building scalable decentralized applications, with our Ditto SDK.
ZK-SNARKs
ZK-SNARK is an abbreviation for “Zero Knowledge Succinct Non-Interactive Argument of Knowledge” which are cryptographic proofs that allow one to validate the claim without repeating lengthy computations and keeping some inputs private.
ZK-SNARKs are non-interactive, where there’s no need for constant interaction between the prover and verifier. Interactive proving requires both parties, which limits its power. Any generated proof couldn’t be independently verified without initiating a new conversation between the prover and verifier, which is not cost-effective. (Remember the analogies above, Alibaba Cave and Color-Blind Friend needed repetition while Where’s Waldo did not)
With a shared key (a.k.a public parameters) between the prover and verifier, these proofs allowed the prover to establish knowledge of certain data without actually revealing it. Non-interactive proofs simplified the process, just one round of communication is sufficient. The prover inputs the secret data into an algorithm to generate a zero-knowledge proof, which the verifier then checks using another algorithm. Once established, this proof can be verified by anyone with a shared key.
To sum up; ZK SNARK technology uses elliptic curve pairing, it’s quickly verifiable, requires a shared key and a trusted setup.
ZK-STARKs
ZK-STARK is an abbreviation for “Zero Knowledge Scalable Transparent Argument of Knowledge,” and it’s a specific type of zk-SNARKs. STARK protocols are ideal when working with witnesses of large size and higher transparency is preferred.
ZK-STARKs have higher verification overhead than zk-SNARK, but they are way more cost-effective when working with big witnesses. In other words, STARK is a great solution when you need scale.
To sum up: ZK STARK technology uses Polynomials, it’s highly transparent therefore no trusted environment is needed and it’s ideal for large scale.
Ditto Network and ZK-Proof
Ditto Execution Layer: A reliable, decentralized keeper network for transactions, enabling automation and intent-centric workflows. Features include a slashing mechanism and zk-proof verifications.
Ditto AVS stands out by offering a fully decentralized solution with disputes resolved through ZK-proofs, ensuring objective and transparent verification.
Enhanced Security with ZK Proofs
Ditto AVS employs zero-knowledge (zk) proofs to validate possibility of execution via storage slot verification. This approach provides:
- On-Chain Verification: As all workflows and the workload distribution are posted on-chain the system utilizes objective slashing via smart contract slashing resolution and compensation enforcement.
- Objective Dispute Resolution: The verification of the historic blockchain state happens via zk proof described in this white paper.
Even though for now we only use ZK-proof to prove the state of the EVM at a particular time/block for slashing reasons, we plan to implement more ZK-proofed functions soon.