An Understandable Explanation About Zero Knowledge Proofs (ZPK), Plus More Including Blockchain, AI
Dr. Lance B. Eliot, AI Insider
I recently had an opportunity to attend ZK Day 2019 at the Simons Institute for the Theory of Computing at the University of California Berkeley, an all-day symposium entitled “Blockchains, Micropayments and Zero Knowledge.” Luminaries of the field were there, and the stellar event was moderated by Dr. Shafi Goldwasser, Director of the Simons Institute and a pioneer and co-founder of the field.
Those of you in the AI field might not be particularly versed in ZKP, perhaps you have heard of it, distantly, faintly, yet you are unsure of what it consists of.
I’ll go ahead and provide you with a layman’s explanation and include some handy references of salient works on the topic. The mathematics of ZKP can be daunting, which if you relish “pure” computer science offers a richness of a high order, while if you are less-so mathematically focused and more-so software engineering inclined, there are ways to make use of ZKP and do so by reviewing open source code and ZKP programs that are available on GitHub.
Let’s start at the beginning. Suppose you want to prove to someone that you know something, a particular something. You could just tell them the something, but in so doing, you have completely revealed it. There might be situations whereby you don’t want to have to reveal the something, and yet nonetheless be able to somehow validate or “prove” that you really do know it.
Seems like a conundrum. How might I convince you that I know something, and yet not reveal the actual something in the process of doing so?
ZKP AND THE CASE OF THE SECRET PIN
This reminds me of a kind of real-world use case when I was in college getting my degree in computer science. I was working in the campus computer center to cover my tuition.
We had a manager that worked full-time as a regular administrative job in the computer center, and she kept a tight rein on the potential antics of me and the other computer science types that were laboring in the computer lab, allegedly helping newbies. She had an office that was enclosed within the computer center and had windows that viewed into the area where the computer stations were provided for students doing labs.
She would open her blinds when she got to work, watching us like hawks, making sure that those sometimes lazy or inattentive student-workers manning the lab were keeping on their toes.
One day, on a Thursday, she indicated to me that she was going on vacation the next day, and would lock-up her office, but she also realized that she kept spare equipment in her office, which might be needed while she was away camping. She told me the PIN to the numeric lock on her office door. It was quite an honor, since she seemed to distrust nearly all of us, and she was giving me the key to the kingdom, as it were.
But she also didn’t want others to know that she had given me the PIN. She worried that word would spread about her doing so, and I might get picked-on for being a favored son, as they say, and she also figured that it would get me into a pickle of having to say yes or no whenever spare equipment requests might arise. All in all, she was giving me the PIN as a last resort option and for a contingency use only, which she hoped and assumed would not need to be invoked while she was gone for just one measly day.
Friday morning, I came into the computer center, and was immediately confronted by a pal of mine. He had heard a rumor that the manager had given me the PIN. He was flabbergasted. Why didn’t he get the PIN? The idea of my having the PIN was so outlandish that he dismissed the rumor entirely. It made no sense to him that I would have the vaunted PIN.
I realize that I probably should have remained mum, but, hey, I felt that my honor was at stake, namely why couldn’t I have been chosen to have the PIN? So, I whispered to him quietly, and swore him to utter secrecy, yes, I did indeed possess the PIN. It was locked away in my mind, like a steel vault, never to be opened, never to be revealed.
Of course, he did not believe me. I was saying that I had the PIN to merely fuel the rumors and to make myself look important, at least that’s what he retorted. We are now at the crucial point of my story.
Are you ready?
Prove it, he said.
How was I to prove that I had the PIN? I could have told him the PIN number straight out, but I had been sworn to keep it private and only I was to have it. Telling him the PIN was not the way to go.
I could have walked him over to her door, which was on the other side of the lab area and not readily visible and used the PIN to open the door. He might though get a glance of the PIN, and I didn’t want that to happen. Also, he would be able to later on tattletale to the manager and say that I had actually shown him my entering into her office. Something that might have gotten me fired from my dream job.
Here’s what I did. I told him to wait right where he was. He could see the windows of her office and the blinds were closed, since she was not present in the office. I instructed him to carefully watch the windows of her office.
I then walked around to where her office door was, let myself into her office, quietly, unseen, and turned on the lights. I left them on for about ten seconds, and then turned them off. I snuck out of her office, making sure that I had not been observed.
When I got back to my pal, I asked him what he had seen. He reported that the lights in her office had come on and then gone off. It was me, I did it, I explained. This was my proof that I had the PIN.
He pondered this. Well, it was the case that the manager wasn’t at work, and it was the case that I had seemingly disappeared for a few moments, and it was the case that the lights mysteriously came on and went off, which logically should not have occurred, therefore my claim was plausible.
Notice that I had not told him the PIN number. He could have asked me about the PIN number, such as how many digits in length it is, which might have been a means for me to try and prove that I knew the PIN, but if I told him the number of digits, it would be tantamount to giving a clue about the PIN. I did not want to tell him the PIN and nor provide any clues whatsoever about the PIN.
I had wanted to provide zero-knowledge about the PIN, not even a scrap of knowledge about it.
I had wanted to provide proof-of-knowledge that I actually did know the PIN.
Thusly, I had performed a zero-knowledge proof-of-knowledge, doing so about my claimed in-hand PIN.
Since saying “zero-knowledge proof-of-knowledge” is a somewhat lengthy statement, a mouthful, we abbreviate it to simply Zero Knowledge Proof. I mention this because it can be confusing to make sense of just the three words, Zero, Knowledge, Proof, and you aren’t sure what the word zero applies to and nor the word knowledge and nor the word proof. I hope you can see the sensibility of it, using the long form, it is zero-knowledge revealed, in the act of providing a proof-of-knowledge.
Wait a second, you might be saying, did my pal really believe that I had the PIN, due to the lights on and off evidence?
No, he did not. Being a suspicious person, he pointed out that I might have had an external means to turn her office lights on and off, maybe a remote button of some kind. Or, maybe it was a fluke that the lights perchance went on and off at that particular time. Or, maybe I knew beforehand that the lights were set to run on a timer and would go on and off at just that precise moment.
I shook my head. Really? I would go to that kind of trouble to falsely try to prove that I had the PIN? Well, anyway, I decided that perhaps I could deal with his doubting ways. I told him to once again wait and watch the office window. Away I went, and this time I entered in her office, using the PIN again, and twisted the blinds so they flipped one way and to the other way, doing so very fast, fast enough that no one could see into the office.
I came back to my waiting and formerly doubting pal. He admitted that it sure seemed like I must have the PIN. He had witnessed two events, one after the other, and the first one gave him a kind of probability or certainty level about my having the PIN, which got further reinforced upon my second alleged visit that flipped the blinds.
You could say that I was the Prover, having to prove something that I claimed to know. You could say that my pal was the Verifier, trying to verify the veracity of my claim that I know something. When you read the literature and research on ZKP, you’ll find that it is customary to label the Prover as a thing or person labeled as “A” and the Verifier as a thing or person labeled “B” — allowing you to then portray the situation in a mathematical way of using A and B.
The letters A and B are somewhat unassuming and so there are those that like to refer to A as being “Alice” and B to being “Bob,” providing a bit more catchiness to the matter. Since it might be hard to remember which is which, whether Alice is the prover or the verifier, or whether Bob is the prover of the verifier, some like to use the word “Peggy” as representing the Prover and the word “Victor” as representing the Verifier, an easier alignment of the letters that start the respective words.
You now know the rudiments of ZKP. There is a Prover that claims to have some kind of knowledge, which the Prover does not want to reveal per se, including not even offering clues that might reveal it, and there is a Verifier that is trying to assert the veracity of the Prover’s claim, which the Prover then uses some kind of proof to try and convince the Verifier about the Prover’s veracity.
I think you can directly discern the privacy value of such an approach.
ZKP HANDY FOR CRYPTOCURRENCIES
Take the advent of cryptocurrency as an example.
When using blockchain and a cryptocurrency such as bitcoin, the traditional approach involves making openly available the history of a given bitcoin, allowing you to trace it from its origins and to each of the times that it was spent on something. When you ponder this, you realize that the cash you carry in your wallet or purse is not that way. Pull out a five-dollar bill. Can you tell me where it has been, prior to arriving in your hands? Not likely.
The cash you use every day is considered fungible. That five-dollar bill is the same as any other and there is no ready way to trace where any of them have come and gone. Sure, there is a minted number on the bill that you can use to identify its origins, but the path thereafter is pretty much a mystery. You likely know where you got the five-dollar bill, and when you spend it you’ll know what you did with it, but anything else in-between is unknown to you and pretty much unknown to everyone else too.
In the case of cryptocurrencies, the ease of traceability comes with being digital. You might like the traceability and it gives you comfort to know where a particular cryptocurrency item has been. On the other hand, it opens the door to allow knowing who had it, what they used it for, when they used, etc.
I’m guessing you’ve had a moment when you were about to use on your normal credit cards, realized that by using it you could be traced, and perhaps switched over to cash, doing so to keep away prying eyes (if that’s never occurred to you, perhaps I’ve just triggered you, sorry). Generally, any use of a “traditional” cryptocurrency is going to be similar to the notion of using a credit card that can be traced, though in some ways even less private, since your credit card info might be known mainly by your issuing bank, while the blockchain you are using might be available to anyone on planet Earth.
One of the presenters at the ZK Day event was Dr. Alessandro Chiesa, a Senior Advisor at the Simons Institute and a faculty member at UC Berkeley. He is a co-inventor of the Zerocash protocol, which endeavors to use ZKP for blockchain and cryptocurrencies. This adds a capability of privacy that otherwise is not inherent in traditional cryptocurrencies. For a handy foundational paper from 2014, which also covers the zk-SNARKS (Succinct Non-interactive Arguments of Knowledge), see: http://zerocash-project.org/media/pdf/zerocash-extended-20140518.pdf
In terms of classic reading on ZKP, you might want to look at this groundbreaking paper that essentially got ZKP rolling: https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Proof%20Systems/The_Knowledge_Complexity_Of_Interactive_Proof_Systems.pdf The paper was co-authored by Shafi Goldwasser, Silvio Micali, and Charles Rackoff. Dr. Silvio Micali was also a presenter at the ZK Day event, providing insights about a version of blockchain called Algorand: https://www.algorand.com/
I’ll soon herein be discussing the ZKP as it applies to AI self-driving cars, and meanwhile some devoted readers will remember this piece on blockchain for AI self-driving cars that I wrote for my column: https://www.aitrends.com/selfdrivingcars/blockchain-self-driving-cars-using-p2p-distributed-ledgers-bitcoin/
SOME MORE ZKP ASPECTS OF INTEREST
You might have a Prover that is genuine (let me use the letter G to mean being genuine), which I’ll call P-G for ease of reference. You might also have a Verifier that is genuine, which we’ll call as V-G. But we might have spies, adversaries are what they are usually called in ZKP research, which I’ll label with the letter “A” for adversarial and thus we could have a P-A (a Prover that’s an adversary) and we could have a V-A that’s a Verifier that’s an adversary.
To be clear, we have four instances, two types of a Prover and two types of a Verifier:
- P-G: Prover Genuine
- V-G: Verifier Genuine
- P-A: Prover Adversary (spy)
- V-A: Verifier Adversary (spy)
Let’s make the safest assumption about things, namely that a genuine Prover does not necessarily know that the Verifier is genuine, and nor does the genuine Verifier know that the Prover is genuine. A spy, or adversary, might be standing in place and trying to act like they are genuine. One never knows.
Thus, we have these four circumstances when an event occurs:
- P-G parlays with V-G (this is the usual expected parlay)
- P-G parlays with V-A (the Verifier is an adversary, a spy in our midst)
- P-A parlays with V-G (the Prover is an adversary, trying to trick a genuine Verifier)
- P-A parlays with V-A (it’s classic spy-versus-spy, though neither might realize it!)
These circumstances are important because the Prover should be cautious about revealing anything about the secret when trying to prove the veracity of the claim about the Prover knowing the secret, since otherwise they might be revealing something to an adversary (a spy!), the no-good evil V-A. Don’t want to do that.
Generally, with ZKP, you want to avoid having to pre-establish trust between the Prover and the Verifier, if you can avoid it (this is considered a trustless setup, meaning they don’t need to particularly trust each other per se, which reduces other potential burdens). If feasible, the Prover and Verifier should be able to come upon each other, transact their business, and yet feel relatively safe that the Prover did not give away something, and they were in essence complete strangers when they came together. If they have to be trusted buddies beforehand to make things work, it’s going to create potential holes in the robustness and make the scheme more arduous to employ (you can do it that way, I’m just saying it is perhaps less parsimonious).
I’ll make things even harder.
Let’s assume that you have an observer, O, which might be one or more others that are watching the Prover and the Verifier. The observers might be prying adversaries, spies, bent on finding out the secret that the Prover possesses. Once again, the Prover is not supposed to reveal the secret, and nor any clues about it, such that then any adversarial observers are still in-the-dark about the secret itself.
Consider too the Verifier. The Verifier might know the secret already, and they are merely trying to find out whether the Prover knows it too, such as if my pal at the computer center had already known the PIN, he might have wanted to discover whether I really know it too. In fact, it just so happened that he did not know the PIN, and it was only me that knew it. The point is that the Verifier can be in one of two conditions, they know the secret, or they do not know the secret.
This is worthy of consideration since sometimes people get confused about ZKP and assume that both parties, the Prover and the Verifier, both know the secret. This does not need to be the case. My pal did not know the PIN. He was solely interested in knowing whether I knew the PIN. I’m sure he would have gladly wished that I might have divulged the PIN, either accidentally or intentionally, but that would have gotten me into great trouble.
REVEALING YOUR HAND
The mere act of asking questions can be a tell.
Suppose you have planned a surprise birthday party for a friend of yours. Nobody leaks the secret. The day before the event, you see your friend, and you ask them pointedly what they are doing tomorrow at noon. Your friend, not having previously suspected that a surprise birthday party might be planned, gets highly suspicious that you would ask such a question. You have revealed a clue about a secret.
When you have a Prover that is trying to prove the veracity of a claim of a secret, I’ve emphasized that the Prover is not to reveal the secret and nor any clues about it. You might have a Verifier that rather than merely receiving your proof, might instead be asking a question or series of questions, doing so to essentially manufacture the proof by the answers that you provide. If so, the Verifier has to be mindful of not asking questions that could either reveal the secret and nor any clues about the secret, assuming that the Verifier knows what the secret is.
In ZKP, there are interactive proof-of-knowledge processes and there are non-interactive proof-of-knowledge processes. As you can likely see, the interactive approach has the potential for either the Prover leaking the something, or for the Verifier leaking the something. They both need to be quite careful in what they say or do. You don’t want happenstance of loose lips to sink the ship.
This brings up another variant that sometimes is considered. Should you consider using potential falsehoods or extraneous elements in your proof-of-knowledge to possibly throw-off an adversary that is playing the role of a Prover or Verifier, or to throw-off any observers (spies) that are watching the matter?
Putting on your spy hat, think of the clue’s aspects of ZKP in terms of a set of clues, which I’ll call C. So far, I’ve emphasized that the set C is supposed to be the null set, namely there aren’t any clues provided. That’s the conventional wisdom, and likely the more facile way to go.
There might though be a tradeoff involving reducing computational expense or time-effort if you are willing to reveal some clues in the course of displaying the proof (or, as I’ll mention in a moment, maybe raise the bar on your adversaries).
I might be willing to showcase some genuine clues, refer to them as C-G, depending upon the payoff involved in doing so. Meanwhile, I might also be willing to offer some false clues, which I’ll refer to as adversarial clues, C-A, doing so to distract or confound any adversaries that might be immersed in the matter.
I could have a set C that has only C-A members, meaning it is entirely fake clues, or I might have a set C that has only C-G members, meaning all bona fide clues, or I might have a mixture of both C-G and C-A, doing so to potentially hide the genuine ones, the C-G’s, among the fake ones, C-A’s. This set will be ascertained for any particular instance of a Prover and Verifier encounter.
Notice that the use of clues is going to hopefully make life harder for any adversaries, since they are now needing to contend with clues, for which they aren’t sure which are genuine, and which are not. That’s handy. The downside potentially is that the clues might undermine the efforts of a P-G parlaying with a V-G, making it more arduous for them to achieve their goals. Again, it’s a balance of the need to make life hard for adversaries, and still get to the desired proof-of-knowledge.
Some would say this is heresy since the core principle is “zero knowledge” revealed, and the use of clues would potentially undercut that notion, though if the clues are all C-A, you could claim that it is still a zero knowledge reveal in terms of not having revealed any genuine facets.
I presumably would only reveal any minimal C-G’s, if any at all, and so you might say this is a “zero-min knowledge” threshold (that’s my own verbiage, not a standard), meaning that I might provide zero knowledge or some minimal amount of knowledge, doing so as a variant of trying to confound adversaries and also if it might provide some other worthy payoff such as reductions in computational expense or time.
USING SUBTERFUGE AS AN EXPLOIT
This brings up a related matter. If an observer were watching me and my pal, and they watched as I disappeared, and they saw the light go on and off, and the blinds getting flipped, what would they now know? They still do not know the PIN, and nor have any clues about the PIN.
You might say though that the observers do know that I apparently have the PIN, which in of itself might be a bad thing for them to be able to ascertain. Imagine if other student-workers in the computer center were watching me and my pal, they could now potentially confront me and claim that they believe I have the PIN, maybe asking me to grab some spare keyboards and printer cartridges from the manager’s office.
There is a chance though that me and my pal had actually colluded all along, neither of us having the PIN. Maybe beforehand, we prearranged to have a timer or switch on the lights, and we had a contraption that would flip the blinds. The whole demonstration might be a ruse. We could simply tell the other student-workers that challenged us that we did the whole thing as an April Fool’s prank, and they would not have any means per se to disprove the claim.
THE ROLE OF CERTAINTY AND PROBABILITIES
Recall that I had earlier stated that upon turning the light on and off, my pal was somewhat convinced that I had the PIN, but he was not entirely convinced. I offered to make a second visit, which then added to his level of confidence that I likely did have the PIN. I might have done a similar act a third time, a fourth time, and so on, and in so doing the odds that I really did have the PIN would seemingly continue to increase, assuming that I was each time able to do something that showcased the likelihood that I did have the PIN.
Typically, with ZKP, the Prover is demonstrating that they likely know the secret and yet it is not necessarily to a one-hundred percent degree certainty that the Prover does know the secret. The Verifier has to decide what degree of certainty or probability they are willing to accept as sufficient for the proof-of-knowledge. For my pal, the apparent fact that I had seemingly turned the lights on and off, well, it alone would or could have been sufficient proof that I have the PIN.
The Verifier though might want to be more assured about the chances of the Prover really possessing the secret. If you can setup a set of challenges, doing so in a savvy statistical way, it allows the certainty to be so high, assuming the Prover attains the challenges, you can be relatively assured that the Prover does have the knowledge claimed. You might still have a bit of nagging doubt, but it is hopefully so small that you are willing to absorb it and not feel you are taking an excessive risk at believing the claim.
In that sense, Zero Knowledge Proofs are probabilistic verification.
There are some that say they don’t want to use something that provides any chance of risk or uncertainty. Not even if the risk is infinitesimal. For them, a one-in-a-zillion chance that you are perhaps falsely accepting the proof-of-knowledge is too much for them. The usual retort is that they likely already are absorbing risk that they don’t even realize they are, and they are blind to the risk and uncertainties of things that do have uncertainty and yet they are unaware that they do.
Remember, the only “certain” things in life are death and taxes.
WAYS TO EXPLAIN ZKP
There are several instructive stories or tales that are often used to explain the nature of ZKP.
One of the classic ones involves the fictional variant of the folk story of Ali Baba, used in a paper published in 1998 and entitled “How to Explain Zero-Knowledge Protocols to Your Children” (see the paper at http://pages.cs.wisc.edu/~mkowalcz/628.pdf ).
The Ali Baba version for ZKP has evolved over time. I’ll give you a quick recap as illustrative further about the nature of ZKP.
Imagine a cave that is a circular tunnel, consisting of one entrance, and from that entrance you can take a path to the right or a path to the left, all of which leads you back to the entrance. In the middle of the circular tunnel, we’ll put a door. It’s an impressive door. There is no means to open the door, unless you know the secret phrase. Okay, you twisted my arm, it’s the phrase “Open Sesame” (SPOILER ALERT!).
Anyway, we have Peggy (remember, she’s our Prover), and we have Victor (he’s our Verifier), and Peggy knows the secret phrase, but Victor does not. Please do not reveal the secret phrase since I’ll get in trouble with Peggy, thanks. Victor wants to have Peggy prove or provide proof-of-knowledge about the secret phrase that opens the door, meanwhile Peggy does not want to reveal what the phrase is (she’s a zero-knowledge non-revealer). This should seem familiar as a setup by now.
Here’s what they do. Peggy goes to the entrance, steps inside, and unseen by anyone else, she chooses either the path to the right or the path to the left. Victor then comes up to the entrance. He stands just inside and yells out the word “right” or the word “left” which means he wants Peggy to come to the entrance from that respective side (as based on facing the tunnel entrance).
Peggy indeed complies and let’s say Victor yelled out “left” and she shows up from that side of the tunnel. Did she do so because she happened to have gone to the left, but got stuck at the door, and waited until she heard Victor yell, or did she perhaps go to the right and had to use the secret phrase to open the door and come along to the entrance via the path on the left?
You don’t know for sure which way she did it, but if she did come out to the left, you are at least at a 50/50 chance. Victor steps out of the entrance. Peggy once again picks a choice of either right or left, whichever suits her fancy. Victor steps in. He yells out say “left” again. Peggy comes out via the left side. If she can keep succeeding, you eventually are going to be statistically pretty certain that she must be using the door and she must therefore know the secret phrase (assuming that there aren’t ways to cheat, like having a superpower of being able to walk through magical locked doors).
That’s a handy example of ZKP.
For those of you into complexity theory and computer science, you likely know about the famous 3-color graphs problem. Whether you happen to know the 3-color problem or not, you might enjoy the online interactive demonstrator that MIT has setup, allowing you to learn about ZKP by playing a game as a Verifier and using a 3-color graph (it’s easy to play and, most importantly, there isn’t any homework, nor grades assigned, nor any mandatory final exam), here’s the link: http://web.mit.edu/~ezyang/Public/graph/svg.html
A handy paper on ZKP that provides mathematical formulations that you might find of interest is this one: https://www.cs.princeton.edu/courses/archive/fall07/cos433/lec15.pdf The author, Boaz Barak, uses a Coke versus Pepsi challenge, now a popular ZKP example, as illustration.
Rather than using the Coke versus Pepsi challenge, some like to use an example of presenting you with two balls, one let’s say is red in color, the other is blue in color, and there is nothing else to distinguish one ball from the other. Maybe I’m color blind and both balls look the same to me. You inform me that you are not color blind and can discern which ball is which. I doubt you. I show you the balls, put them behind my back, maybe switch them or not, and I present the two balls, asking you to say which is red or which is blue. We do these enough times, until I believe you are in fact not color blind.
Back to the Coke versus Pepsi challenge, Barak provides two essentials about ZKP that I’ve somewhat implied, one about the soundness and the other about completeness, though I didn’t yet formally tell you about those important criteria, he says (see page 2 of his paper):
“A proof system is sound if you can never derive false statements using it. Soundness is a minimal condition, in the sense that unsound proof systems are not very interesting.”
“A proof system is complete if you can prove all true statements using it. Similarly, we say it is complete for a family L of true statements, if you can prove all statements in L using it.”
One aspect to keep in mind is that there is not just one way to do Zero Knowledge Proofs. This means that somebody might approach you and say they have a means of achieving ZKP, but you should be cautious in assuming they really do. You would want to know how they came upon their approach, and as a minimum you would ask:
- Is it sound or does it exhibit soundness to a sufficient degree?
- Is it complete or does it exhibit completeness to a sufficient degree?
- Is it truly zero-knowledge in that it reveals nothing about the core knowledge at hand and nor any clues, whether overt, subtle, or by happenstance, about the core knowledge?
One of my favorite watchable videos on ZKP is Michael Rabin’s talk for the Ada Lovelace Lecture on Computability (the lecture series is in honor of August Ada Lovelace): https://www.youtube.com/watch?v=N_LG5Hcc8mM Rabin is a well-known mathematician and computer scientist, and received the Turing Award with Dana Scott for their paper entitled “Finite Automata and Their Decision Problems,” which laid out the foundation for nondeterministic machines. It’s a classic paper:https://web.archive.org/web/20160304191722/http://www.cse.chalmers.se/~coquand/AUTOMATA/rs.pdf
In the video, Rabin uses the Where’s Waldo example, which has become popular as an example of ZKP.
Essentially, as you likely know, Where’s Waldo typically consists of trying to find the character Waldo on a page that has lots and lots of other characters and images, thus, he is there but “hidden” by obscurity. The ZKP version is that you take a sheet of paper, cut out a hole, just large enough to showcase Waldo, you then place the paper over the book page, making sure that the hole you’ve made reveals Waldo.
Assuming you do this well enough, you have not revealed the location of Waldo, which is the secret, and yet “proved” that you have the knowledge of where Waldo is.
Another popular example consists of using Sudoku, the numbers game typically involving nine of 3×3 subgrids, resulting in a 9×9 overarching grid, and a kind of mathematical puzzle requiring you to use only the digits 1 to 9 to fill-in the cells. Suppose that you are able to solve the puzzle, of which there are various ways to solve it, and want to convince someone else that you did indeed find a true solution, but you don’t want to show them the solution per se. Once again, you can use ZKP to essentially prove that you likely do have a solution in-hand.
You’ll be happy to know that there are lots of examples involving a myriad of mathematical puzzles, such as using Hamiltonian cycles, using discrete logs, and so on. You can take a look at the papers I’ve already mentioned and there is a plethora of such in-depth mathematical examples.
A practical consideration about Zero Knowledge Proofs is to consider the amount of effort or time required to undertake the proof. It’s handy to be able to avoid revealing your secret, but suppose it takes a lot of back-and-forth to convince the Verifier, consuming time in doing so, along with the potential for lots of computations by either or both of the Prover and Verifier in their own respective right.
For a real-time system making use of ZKP, you’d want to be relatively confident that the time crunch does not otherwise undermine what the system needs to accomplish. I’m not saying that ZKP is a computational or time-consuming beast, only pointing out that it is an important aspect to tune when implementing ZKP, as would be the case with any kind of cryptographic approach. Likewise, you’d want to ensure that there is error detecting and mitigating features included, in case there is any disruption or difficulties encountered during the course of the proof process.
One thought is that perhaps a ZKP can be done in a one-step or one-shot manner, which would obviously cut down on the back-and-forth of a multi-step approach. This is a keen idea, though difficult or hard to do under certain situations and desired thresholds. I’ve mentioned in my writings that one-shot Machine Learning or Deep Learning is a hoped for aspiration, yet continues to be something outside of our grasp to-date in any generalizable way.
Here’s a classic paper that discusses one-step ZKP: http://www.wisdom.weizmann.ac.il/~/oded/PSX/oren.pdf
Speaking of practical aspects, I’ve already noted that the Zero Knowledge Proof approach can be used for blockchain and cryptocurrencies, which I’d bet will gradually become a wider realization of the value that such an approach provides. To me, this is a great applied example. Blockchain and cryptocurrencies though still in an infancy stage of maturation, will likely take a while to gain the kind of acceptance and widespread use of ZKP, but inexorably it makes sense to do so.
Another practical example that I like to cite involves the use of Zero Knowledge Proofs for nuclear warhead verification. In a study done for the U.S. Department of Energy, one of the difficulties about verifying whether a nuclear warhead has been made inert or not, or the magnitude of the warhead, involves having to potentially reveal secrets about the warheads themselves.
Given the distrust between the counting parties, generally the US and Russia, there is naturally resistance to do verifications if you also need to show your secrets. Here’s the study: https://www.osti.gov/servlets/purl/1127356
You’ll be glad to know that it does not involve putting red and blue colored balls behind your back. Instead, it involves irradiating two or more putative warheads, using high-energy neutrons, and capturing a kind of radiation result fingerprint, consisting of the neutron transmissions and emission counts. Doing so in a ZKP manner appears to keep secret the design of the nuclear warhead and the composition of the warhead hidden and therefore avoids the touchy sticking point about such verifications. The approach could be used for deployed nuclear arms and for non-deployed ones.
Throughout these examples, the manifestation of the proof is typically:
- The Prover takes some action that showcases they likely know the secret (such as my turning the lights on and off in the office managers office, or Peggy showing up at the correct path in Ali Baba when called by Victor, or showing Waldo), yet does not reveal the secret itself (I didn’t reveal the PIN, Peggy didn’t reveal “Open Sesame,” and Waldo’s location is not revealed).
- The Prover calculates something, reveals the calculated result, suggesting they likely know the secret (as done for mathematical puzzles and the like), yet the calculated result does not reveal the secret and no clues about the secret. This is the cornerstone of computer-based ZKP.
Some in the ZKP arena have explored whether you might relax some of these characteristics, and if so, what implications arise due to the relaxation. For example, suppose you sternly cling to not revealing the secret itself, but are willing to providing clues about the secret (as per my earlier discussion herein), perhaps doing so in a manner that the clues are quite difficult for others to discern or exploit. These are variants worthy of exploration as to strengths versus weaknesses of a desired approach to ZKP.
AI SYSTEMS AND ZKP
Now that you are up-to-speed about ZKP, let’s consider how this applies to systems development and also AI systems.
As a rule-of-thumb, when exploring opportunities for the application of ZKP, you should consider as part of your an that you are most likely seeking a situation involving two parties (or possibly more) that want to or need to confer with each other and do so without revealing a something of interest to both parties, yet allow the parties to be comfortable that the something is known to (at least) one and believed by the other (or proven) that it is known by the one (or more).
In a straightforward manner of speaking, if you have a potential Prover and a potential Verifier, and you are concerned about what is communicated between the two, namely you don’t want any secret traffic that might get broken into, you should be thinking about ZKP. It is not axiomatic that you would always choose ZKP in such a situation, but it certainly is a tool you should have in your toolkit. If it’s the only tool you have, that’s probably not good, since as they say, when you only have a hammer, the whole world looks like a nail.
A savvy computer scientist has an entire bag full of tricks, or tools, upon which the appropriate tool should be considered for the appropriate circumstance. If you don’t yet have ZKP in your toolkit, you ought to bone-up and make sure it is included.
If you are developing an AI system involving situations of two (or more) parties carrying on a transaction of some kind, and you are at first tempted to have them exchange a password or some means of establishing trust, you might want to rethink the matter and ponder whether ZKP might be a handy option.
I’ll also mention that there is not anything mutually exclusive about using ZKP and also using a more secret-based exchange-style cryptographic method, since sometimes the more the merrier. A cybersecurity mantra is to normally have multiple layers of security, similar to how your house might have locks on the doors (one layer), be in a gated community (another layer), and you have a guard dog that barks at strangers (a scary sounding all-powerful dachshund in the house).
LANDSCAPE OF POSSIBILITIES
In the case of AI self-driving cars, I’ll outline some key circumstances that fit the notion of having a Prover and a Verifier, of which they might want to preserve privacy about some aspects of the matter at-hand that causes them to communicate with each other.
- V2V (vehicle-to-vehicle) electronic communication, say car to car
- V2I (vehicle-to-infrastructure) electronic communication, say car to roadway infrastructure
- V2P (vehicle-to-pedestrian) electronic communication, say car to pedestrian
- OTA (over-the-air) electronic communications, say car to auto maker cloud
- GPS (global positioning system) electronic communications, say car to GPS cloud
- In-Car NLP (natural language processing), human to car interaction
In each of these above use cases, there is a potential Prover and a potential Verifier, and they want to have some kind of discourse with each other.
Privacy though is a serious concern and AI self-driving cars have a doozy of a privacy matter. If your AI self-driving car is continually transmitting messages with other cars (V2V), and with the roadway such as traffic signals and bridges (V2I), and with pedestrians (V2P), or any variant thereof (referred to as V2X), you are effectively leaving a trail of where your AI self-driving car has been, assuming that each such message is accompanied by an identifier of the AI self-driving car.
Would you want to go riding in your AI self-driving car and find out later on that someone could reconstruct your trip? Spooky. As such, each of these AI self-driving car messaging matters could potentially make use of ZKP.
You might be thinking that you can just strip out any identifier and send such messages, and thus there appears at first glance to be little need to do ZKP. The problem though is that imagine if someone untoward decides to send out V2V, V2I, V2P, etc., and yet they are not sincere about it, they are playing tricks on other cars, on the roadway, and on pedestrians. You want the parties to indicate they have a genuine stake in their messaging, requiring a type of verification, and prefer to do so without also conveying private info such as an identifier.
That’s where ZKP can come to the rescue.
In a somewhat similar manner, consider the situation of your AI self-driving car using a GPS system to navigate around town. Assume that there is a GPS system in the cloud that your self-driving car is using. When your self-driving car asks the GPS system for the path to your destination, the reveal tells the GPS system where you are going. Once again, this is a potential privacy invasion.
I realize you might suggest that the self-driving car should merely download the GPS info, whole hog, and therefore there is no need to tattle on the location of where you are and where you are going. This though presents other problems, including the need to have sufficient memory on-board the car, plus this suggests you might not get needed real-time updates about road conditions, etc.
There is quite interesting work going on about GPS and preserving your privacy.
One such notable paper is entitled “Privacy-Preserving Shortest Path Computation” by David Wu, Joe Zimmerman, Jeremy Planul, and John Mitchell, see: https://arxiv.org/pdf/1601.02281.pdfThe focus in their research is mainly about using compression techniques for next-hop routing matrices, but the potential for using ZKP is also a consideration. Touching more so on ZKP in this domain, the papers of “Privacy and Integrity Considerations in Hyperconnected Autonomous Vehicles” (http://www.fkerschbaum.org/pieee18.pdf), and “Plug-in Privacy for Smart Metering Billing” (https://www.fkerschbaum.org/pets11.pdf) are of keen relevance.
For more overall work on Location-Based Services (LBS) and privacy, including Mutually Obfuscating Paths (MOP), and ZKP, see the paper entitled “Preserving Location Privacy of Connected Vehicles With Highly Accurate Location Updates” (https://www.researchgate.net/publication/311549622_Preserving_Location_Privacy_of_Connected_Vehicles_With_Highly_Accurate_Location_Updates).
You might say that I’ve offered you a proof of sorts, a proof about the viability of ZKP, and for which there’s actually no need for me to keep the secret that it has viability, I’m willing to openly divulge that. But I won’t though tell you the PIN number to the door of the office manager that I once worked for, some years ago. I’ll never tell that.
For free podcast of this story, visit: http://ai-selfdriving-cars.libsyn.com/website
The podcasts are also available on Spotify, iTunes, iHeartRadio, etc.
More info about AI self-driving cars, see: www.ai-selfdriving-cars.guru
To follow Lance Eliot on Twitter: @LanceEliot
For my Forbes.com blog, see: https://forbes.com/sites/lanceeliot/
Copyright © 2019 Dr. Lance B. Eliot