▲ 334 points
back
160 comments
Scientists used to use anagrams to register scientific discoveries without revealing them. Hooke registered his law of elastic extension using the letters "ceiiinosssttuv”, which he later revealed to unscramble into "ut tensio, sic vis" ("as the tension, so the force").
People did try to brute-force the anagrams. On two occasions, Kepler unscrambled analgrams from Galileo into the statements that (i) Mars has two moons and (ii) Jupiter has red spots. Bizaarely, both turned out to be true facts, but not what Galileo's anagrams were about!
Nice story, however the second message he deciphered was not about Jupiter's spots, but something else.
https://www.mathpages.com/home/kmath151/kmath151.htm
This reminds me of fixing a bug that causes your problem but then you discover the problem persists after the fix and that you actually had two independent bugs causing the same problem.
Should have padded the anagrams with a known string of nonsense words. I’m going to have to have a chat with Galileo.
I used to play a social deduction game on IRC, and this was one method to reveal things without revealing them.... but it was too powerful so was banned sort of.
That's more like publishing a cryptographic hash, and then later when the answer is revealed, others can verify you knew it earlier.
Zero-knowledge proofs let others perform that verification before the full answer is revealed (and it might never be).
Today, you'd register a SHA256 sum of a sentence, or public-key encrypted sentence, etc.
you said "analgrams"
According to school professors, the only way to prove that a person knows something is to lock them in a room for an hour or two and have them write down the entire thing on a piece of paper while being watched intently.
Well, most of the time I attempted a zero-knowledge proof in school I couldn’t convince the teacher ;)
I think the difference is that the teacher already has the full knowledge and learning isn’t as easy as telling a secret once and then the learner can quickly parse it and keep it forever.
Despite that, I’d also prefer to proof I know a topic by writing an essay at home rather than under pressure within an hour under supervision.
Best intro paper on the subject (IMNSHO)
How to Explain Zero-Knowledge Protocols to Your Children
https://www.researchgate.net/publication/221355016_How_to_Ex...
At the beginning, where the hidden passage is explained, isn't there a "race condition", where Ali Baba would eventually (across 40 repetitions) run into the thief? The thief picks one branch, Ali Baba the other. The thief uses the passage, then walks right into Ali Baba?
I don't understand how the thief can be sure to never walk into Ali Baba coming down the other path at some time.
What am I missing?
I recently published a fairly detailed blog post about how to formulate expressive provable programs in Lurk (https://github.com/lurk-lang/lurk-rs). Although this post goes into no details about the underlying proving mechanism, it does build to some pretty powerful ideas. If you haven't thought about the implications of being able to prove correctness of a computation without revealing some or all details of what the computation actually was, you might enjoy it. https://blog.lurk-lang.org/posts/prog-intro/
As a functional programmer it's easy for me to understand the code, so I actually made it until the end where a neat example is given.
In general though I think the example problem might be worth mentioning in the beginning:
"by the end of this article you will understand how to ..."
There was a recent podcast by ZK Knowledge about homomorphic encryption and how this is different and complementary to ZK proofs. The founder of Zama had some surprising things to say (from my perspective) about how ZK is not something that can be used to guarantee privacy when used with blockchain tech. I'm sure that will be exciting news to everyone on HN. :)
https://zeroknowledge.fm/248-2/
Transcript, look for the timestamp with 28:55 to see that discussion:
https://assets.fireside.fm/file/fireside-images/podcasts/tra...
I'm confused about the maze example in the article: I can "prove" that I know the path to exit as I traverse the maze in limited time, okay. But interactive proofs have many iterations to sufficiently convince the verifier, however if I found the exit by luck in first try, I've already found it and I can simply follow the same path in the next iterations.
How does the interactivity exactly work with the maze example?
Imagine the maze is large and complicated, so that it would be very unlikely you could find the exit by luck. Not impossible, but like winning the lottery odds. You could brute force the search but you don't have time. The probability of finding a path by luck is called "soundness error". When the verifier sees you appear at the exit, they know you either knew the path, or with a soundness error probability, you were just lucky.
Now imagine the maze has a large number of exits, all hard to find by luck, and the verifier tells you before you go in which exit they want to see you come out of. You don't know in advance which exit they will ask for. After you come out, they ask you for another one, and again you don't know in advance which one. These rounds are the interactivity.
Each time through, you have a soundness error's probability of finding the requested path by luck, i.e. winning the lottery kind of odds. The probability that you found all the exits the verifier asked for, is like winning the lottery multiple times in a row. Because you don't know which the verifier will ask for in advance, you can't take advantage of patterns in those requests to skew the combined probability in your favour. They are like independent random events: The probabilities multiply.
After N rounds, your probability of finding all the requested exits by luck is lottery kind of odds raised to the power of N. Pick a sufficiently large N and you have extreme probabilities like those used in other cryptography, numbers like 2⁻¹⁰⁰ or 2⁻²⁵⁶, which are so infeasibly unlikely they are similar to the probability of guessing someone's private key or guessing a SHA-256 hash preimage. We trust this demonstrates you know the maze, even though there's an astronomically unlikely possibility that you guessed right every time.
Yeah, this article tries too hard to appeal to all audiences in a way that ends up making it confusing for everyone. Starts off with the clumsy maze example, then hops over into graph theory and NP-complete proofs, then hand waves something about sharing bits and quantum computing... But enough about that, it turns out blockchain will prevent nuclear war!
The “magic door in a cave” game might’ve been a better example of interactivity.
If you complete the maze by luck and can repeat yourself, then you have gained the information you claimed to have!
If interested in playing around with zero-knowledge proofs, recently was at a workshop with Ying Tong who has an exercise (and long associated slide deck) to walk through them using halo2 ( https://electriccoin.co/blog/explaining-halo-2/ ) to build your own zero knowledge proof https://github.com/therealyingtong/halo2-hope
There's a pretty good section on this in Applied Cryptography. Still an incredible book for a field that supposedly moves pretty fast.
It's a good almanac. It's never been a good reference. It's extremely outdated now, and has been for at least a decade and a half.
For explaining the concepts, maybe. Please don’t implement any protocols from that book!
This tweet illustrates the idea of showing that you know where is Waldo without revealing Waldo's position: https://twitter.com/cronokirby/status/1571824060513796099
That's just giving Waldo's coordinates with extra steps
> For a simple way to understand this idea, let’s suppose you want to show your friend that you know how to get through a maze, without divulging any details about the path. You could simply traverse the maze within a time limit, while your friend was forbidden from watching. (The time limit is necessary because given enough time, anyone can eventually find their way out through trial and error.) Your friend would know you could do it, but they wouldn’t know how.
How would your friend know you solved it though? Does he have to take your word for it? Doesn't that defeat the purpose? This analogy seems flawed, correct me if I'm wrong
Edit: I misunderstood the kind of maze the article is talking about. Apparently it's not the pen and paper version.
The friend sees you enter the maze at the entrance. They don't watch you traverse the maze, instead they run around the outside of the maze to the exit. They see you leave by the exit 2 minutes later.
They don't know the path you took and they can be reasonably sure you didn't brute-force it in that time.
If it's a big maze where you can pass through, you can enter and exit in that time limit
a hypothetical real life maze (eg. in a fancy park), not the paper version?
If you want to play around with zero-knowledge proofs, I work on a typescript DSL called SnarkyJS. It’s easy to pick up and runs in the browser.
I haven't used SnarkyJs, but I've heard good things! Big props.
How can you use zero knowledge proofs to show that your nuclear weapons are inactive? Also... couldn't you just reactivate them after?
FWIW the linked paper on nuclear warheads is fairly accessible. You don’t need to understand nuclear physics to grok the algorithm.
ZK proofs only demonstrate knowledge of some fact. So, you could prove that you know the way through the maze, but then immediately forget it afterward.
Maybe the nuclear inspectors inspect the warheads frequently enough that rearming them would be detected? Or perhaps there is just some level of trust and you have to rely on the country to play by the rules.
Isn't this the point of the article? You wouldn't prove if they're active or not, only that YOU know if they're active or not?
Yup, this would only work if some central authority had exclusive control to activate/deactivate the warheads.
I would like to know this too
zero-knowledge proof is very nice... and could be used to prove election results: https://eprint.iacr.org/2018/466.pdf
As demonstrated in central north america recently the real challenge isn't in proving election results .. it's in the greater social challenge of propagating belief and trust in the results in the face of concerted efforts to widely undermine such.
That's a whole other kettle of fish.
In the paper the authors describe using a blockchain to store the results. The blockchain is only mined in private, by an administrator, where voter id information is removed after the election. What is the benefit of a blockchain over a table (csv, JSON, database, excel etc) to store the data? Blockchains application is when you need to reach shared consensus without trust. We’re not in this situation that the paper describes.
Is it true that given enough such proofs, I can reconstruct the original thing, so I do leak something?
Like doing an HMAC reveals a tiny piece of information every time…
Side topic, but why does something relatively respectable like Quanta Magazine need a reading progress bar? These odd decisions truly amaze me sometimes.
...... share a hash?
Isn't it enough no show a hash?
"How do you let go of a secret without telling the wrong person? You tell everyone at once."
> How to prove you know a secret without giving it away
This is the best use case for blockchain. Put the secret on the blockchain and show others that transaction. Since it's on blockchain, no one can deny your claim about knowing the secret. This is why blockchain was invented.
Before blockchain, I was miserable. There was no way for me to prove to my girlfriends that I knew a secret, without telling the secret. Now with blockchain, my life is so easy - I just show them the blockchain transaction and they know that I know.