How to explain Zero-Knowledge at a dinner party

Co-authored with the Whitepaper Reading Club

Trust, more than money, makes the world go round.

Before you lend money to someone, for example, you’d want assurances that they are not a scammer and that they will be able to pay you back. How can a borrower convince you of both statements without revealing (a) their full identity and (b) their personal net income (income minus expenses)?

Besides, people are inherently untrustworthy. So we bring in middlemen—like banks or escrow services—to bridge that trust gap and pass on the risk of untrusted transactions to them.

To lower these risks, these middlemen demand piles of personal information through the dreaded KYC (Know Your Customer) process, which has spawned issues like high transaction fees and data misuse.

So, what if we could transact without needing to trust the other party or a middleman?

Enter Zero-Knowledge Proofs

Zero-knowledge proofs (ZKPs) solve this conundrum. They allow one party to prove the validity of a statement like the examples above or — “I know where Waldo is”?—without revealing the position of Waldo itself or telling a game master.

If this sounds like magic, well, it almost is. ZKPs work using complex cryptography, which can be summed up as mathematical proofs of truth claims.

It is also worth noting that the original data cannot be reconstructed just from these mathematical poofs.

But I’m not a wizard, so here’s how you would solve the problem without math (or magic) - the video below starts at 0:50 mins. Watch it till 2:30 mins.

By using ZKPs, two parties can confidently transact in an anonymous yet secure manner. They can be sure the other party is legitimate without revealing unnecessary details.

Here, instead of trusting the middleman, we trust the mathematical rigour of ZKPs.

This seemingly simple concept will have massive implications on our world today in the form of:

1. Privacy: Your personal data can’t be misused, sold, or otherwise used against you without your permission if it is not collected in the first place
2. Scalability: A nice bonus effect of ZKPs is that the size of proofs is much smaller than the original data themselves. This means it is computationally much faster and cheaper to verify the proof than the original data.
3. Disintermediation: Removing middlemen from the equation means removing the high transaction fees that they impose.

What can ZKPs be used for?

1. Trust-less KYC: Proving that one is not a sanctioned person of any country without revealing actual identity
2. Trust-less identity provenance: Proving that one is a member of some group or an actual human being and not a bot without revealing actual identity - e.g. Worldcoin
3. Trust-less and secure digital voting system: Prove that one’s votes are legitimate without revealing who they voted for
4. Improve patient privacy in healthcare: Proving the validity of medical conditions for insurance claims without revealing entire medical history. Or proving that one does not have any excluded medical conditions when purchasing insurance plans.
5. Transparent supply chain: Brands can prove that their raw materials are ethically sourced without revealing trade secrets.
6. Transparent bug bounty: White-hat hackers can prove the existence of bugs and vulnerabilities in a software system without revealing the actual solution, protecting them from non-payment by the owner of the software system
7. Scaling blockchains: Because the space for blocks on a Layer 1 (L1) blockchain is limited and expensive, ZK Layer 2 (L2) scaling solutions batch multiple transactions into one and generate a ZKP for independent verification before posting the verified proof back to the L1 blockchainRecall that the size of proofs is much smaller than the original data, so each transaction takes up way less space and is much faster to process

How do ZKPs work under the hood?

In general, there are 2 parties involved in a Zero Knowledge protocol - The prover and the verifier.

The verifier verifies a proof computed by the prover that satisfies the following conditions:

1. Completeness: If the underlying statement is true, then an honest verifier can always be convinced with the proof
2. Soundness: If the underlying statement is false, then it will be near impossible to convince an honest verifier otherwise with the proof
3. Zero-Knowledge: The verifier learns nothing else about the underlying statement from the interaction other than whether it is true or false

How do they interact?

A Zero-Knowledge Proof is made up of 3 components.

1. Witness: This is the underlying statement. It is the secret information that the prover wants to prove that they are in possession of.
2. Challenge: The question(s) a verifier asks a prover to test if they really have the secret information.
3. Response: The prover’s answer to the Challenge questions.

Wait, isn’t this just an interview? Well, not really, because we ask a bunch of questions and request documents that reveal substantial information about the candidate beyond just the statement of “I am qualified for the job”. In other words, it violates the Zero-Knowledge condition.

These non-trivial conditions imposed on a ZK protocol mean that there is a cost to prove?and a cost to verify. Moreover, these costs from the ZKP interaction will need to be replicated if another person wants to verify the prover’s claim.

The cutting edge: Non-Interactive ZKPs

Now let’s make this even more exciting - what if we only have a single round of interaction (instead of multiple rounds) between the prover and the verifier to complete the ZKP process?

This is made possible using a shared key, a proving algorithm, and a verification algorithm.

With non-interactive proofs, the prover only has to compute the proof once, and anyone else will be able to verify it using the shared key and the verification algorithm - greatly reducing the cost of using the ZK protocol.

SNARKs & STARKs

The 2 leading implementations of non-interactive ZKPs are zk-SNARKs and zk-STARKs. To begin understanding each of them, let’s first define the acronyms in simple terms and their key characteristics.

zk-SNARKs

1. Zero-knowledge (zk) - no other information needs to be provided other than proof that the prover’s statement is true
2. Succinct (S) - the size of the proof is very small compared to the original raw data
3. Non-interactive (N) - does not require multiple rounds of interaction between the prover and the verifier. i.e. no further questions are asked when the first proof is provided and verified
4. Argument (AR) - A prover can make the verifier believe a lie if the prover has enough computational resources - i.e. it is a probabilistic process. This is in contrast with an actual proof where a prover can never convince a verifier of a lie even with unbounded computational resources
5. of Knowledge (K); Or knowledge-soundness (Ks) - A prover must know the solution to prove his/her statement. In simpler terms, it ensures that the prover isn’t just bluffing or producing proofs for false statements

The most important property of some SNARKs is the requirement for a trusted setup ceremony. Recall that a shared key is necessary for non-interactive ZKPs - this ceremony is where this shared key is created.

The secrets used during these ceremonies will need to be destroyed after the shared keys are created. Otherwise, these secrets can be used to create false proofs, and it would be impossible to verify that these false proofs are indeed false.

Fortunately, having just one person out of everyone who participated in such ceremonies destroying their secret will greatly increase the security of trusted setups. On the same note, the security level also increases with each additional secret destroyed, which is why trusted setup ceremonies are usually run with many participants.

SNARKs uses pairings-based cryptography (vs hash-based) that generate proof sizes orders of magnitude smaller than those of STARKs, leading to faster and cheaper verification of SNARK proofs.

The trade-off of using pairings-based cryptography is that they are not quantum resistant and result in slower and more expensive proof generation across all throughput levels.

zk-STARKs

1. Zero-knowledge (zk) - no other information needs to be provided other than proof that the prover’s statement is true
2. Scalable (S) - Used in a blockchain scaling context - the proving computation and data storage can be done off-chain to circumvent block space constraints. Zk proofs of these off-chain activities are then submitted on-chain for interested parties to verify.
3. Transparent (T) - Uses publicly available randomness to generate parameters, removing the need for a trusted setup.
4. Argument (AR) - Same as SNARKs above.
5. of Knowledge (K); Or knowledge-soundness (Ks) - Same as SNARKs above but uses quantum-resistant algorithms.

STARKs, on the other hand, do not require a trusted ceremony setup to generate a shared key.

Instead, they make use of publicly verifiable sources of randomness that are used by both the proving and the verification algorithms so that both can arrive at the same output. This means that we don’t need to trust STARKs for it to work.

STARKs uses hash-based cryptography (vs pairings-based), which is quantum resistant, enables lower cost to generate proofs, but result in larger proof sizes. Larger proof sizes leads to a higher cost to verify at low throughput levels.

Summarising SNARKs vs STARKs in a table

Conclusion

This wraps up our ZK dinner party!

For my next issue, we will dive deeper into how Zero-Knowledge Proofs help blockchains to scale (this is a Web3 newsletter after all ??) alongside other types of Layer 2 scaling solutions.

Credits

This newsletter issue is co-authored with the Whitepaper Reading Club - a high-signal collective of who are enthusiastic about understanding how Web3 technologies work under the hood. We read whitepapers and meet up to debate our understanding once every two weeks.

This is an open initiative where anyone is welcome to join us. DM if you are keen!

Zero-knowledge makes the world go round,

Sam