Zero Knowledge Proofs (ZKP)

Zero Knowledge Proofs are a way to assert that you know something without revealing that you know it.

A canonical explaination is the “where’s Waldo?” example. In this example, you take a large piece of paper (like.. something big enough to fully obscure the book) that has a tiny cutout. You place the tiny cutout over the location of Waldo. They can then see that you know where it is.. but b/c they can’t see the context of the paper relative to the book.. but they don’t know where Waldo is.

This is a simplified example that was generated by Claude. It uses a different metaphor called “Ali Baba cave”. Someone says they know how to traverse a cave system. You put them at one of the entrances. Ask them to come out of a random exit of your choosing. If they can traverse the path, they’ll approach 100% success rate.

This is an example of an Interactive ZKP. It allows for multiple iterations of back and forth with the caller. There are also non-interactive versions which require no chatter back and forth.

import random
 
def zero_knowledge_proof_example():
    # The secret: which path the prover knows (0 or 1)
    secret_path = 1  # This is what the prover knows but won't reveal
 
    # Run multiple verification rounds
    verification_rounds = 5
    successful_verifications = 0
 
    print("ZKP Cave Example - Prover knows a secret path but won't reveal which one")
    print("Secret path known to prover:", secret_path, "(verifier doesn't know this)\n")
 
    for round in range(verification_rounds):
        print(f"Round {round + 1}:")
 
        # Prover enters the cave randomly through either path 0 or path 1
        entrance_path = random.randint(0, 1)
        print(f"Prover enters through random path: {entrance_path}")
 
        # Verifier randomly requests prover to exit from path 0 or 1
        exit_request = random.randint(0, 1)
        print(f"Verifier requests exit from path: {exit_request}")
 
        # The prover can only successfully exit from the requested path if:
        # 1. They happened to enter from that path, or
        # 2. They know the secret path to cross through the cave
        can_exit_successfully = (entrance_path == exit_request) or (secret_path is not None)
 
        if can_exit_successfully:
            print("Prover successfully exited as requested!")
            successful_verifications += 1
        else:
            print("Prover couldn't exit as requested (would fail)")
        print()
 
    # Calculate probability that prover knows the secret
    success_rate = successful_verifications / verification_rounds
    probability_knows_secret = 2 * success_rate - 1  # Adjusted for 50% random chance
 
    print(f"After {verification_rounds} rounds:")
    print(f"Success rate: {success_rate * 100:.0f}%")
    print(f"Probability prover knows the secret: {max(0, probability_knows_secret * 100):.0f}%")
    print("\nNote: With more rounds, this probability approaches 100% if prover knows the secret")
    print("      or 50% if they're just guessing")
 
# Run the example
zero_knowledge_proof_example()