A professor I know once gave me the most beautiful example of a zero knowledge proof: she said “Imagine I want to prove to you that I can count the leaves on a tree, but I don’t want to reveal how I do it. I start by telling you there are e.g. 756,912 of them. Then I close my eyes and I let you remove as many as you want. We can keep going until you are convinced, and you still won’t know how I did it.”
Okay, but I wouldn't be convinced until I've counted up to 756,912 myself and seen that there are no more leaves left after that. Isn't it supposed to be less computationally intensive to verify the proof than to complete the original calculation?
I tried learning about zero knowledge proofs during the crypto craze, but I never understood the basic idea of how it was supposed to work, much less the math involved. I'd appreciate an ELI5 from anyone who has one.
The proof is that they can tell you the number of leaves (again) after you have secretly removed some. Since only you know the number you removed, if the difference between their counts matches your number, it is likely that they can indeed count the leaves on the tree. It is possible they have correctly guessed, which is why you repeat the challenge until you are convinced.
Edit: From another comment, it starts do make sense. So you let them remove a number of leaves secretly, and then you tell them the new number again, and they can check if your answer makes sense because of the difference between the two numbers.
