A zero-knowledge proof for the existence of God
13 Nov 2017
Judeo-Christian God was in trouble. The latest polls were in, and belief in him was down, especially amongst the key millennial demographic. He needed to come up with a punchy viral marketing campaign to regain control of the conversation.
The easiest thing to do would be to heal a few leopards, send down a plagiarizing locust, and make sure that the major TV networks were around to see. This had always done it back in the day. But he had also made some inconvenient, on-the-record statements about wanting relationships based on trust and faith rather than proof. John 20:29 - “Then Jesus told him, ‘Because you have seen me, you have believed; blessed are those who have not seen and yet have believed.’” These ideals were meant for another, simpler time and culture, but there’s no telling the biblical literalists.
He didn’t usually like to do this kind of thing, but he needed to do just one tiny miracle, and disseminate just one tiny bit of proof of his existence to kick start his brand. As humanity had become more technologically advanced, the things they were willing to accept as miracles had changed. They knew enough medicine to be dangerous, and had all seen those TV shows where they show you how magic tricks are done. Parting the Red Sea? The Sea was in on it. Abraham and Sarah conceiving when they were like 100 years old? Isn’t IVF great. And yet they were still bizarrely eager to read far too much into pieces of toast. If you make enough toast, some of it will look kind of like Jesus! It would be a miracle if Jesus’s face never appeared in a jam sandwich!
Since humanity was transferring their faith into science and mathematics, Judeo-Christian God would perform mathematical miracles. He would prove the impossible, solve the intractable. You think graph 3-coloring is NP-Complete? He’d solve graph 2-coloring without breaking a sweat.
He had identified the perfect Instagram celebrity influencer to partner with to get his message out - particle physicist Otekah Wendleton. Wendleton began her career as a celebrity chef who used unnecessarily complex science to do her cooking. One day she was seized by the idea to instead use cooking to do science. Cooking was of no help whatsoever in her PhD, but she still turned out to be an extremely skilled theoretician and public communicator. She was now head of Antiproton Cell Experiment research group at CERN and wrote a popular weekly science-cooking crossover column for Buzzfeed.
Judeo-Christian God reasoned that if he could use just a teeny bit of proof to get Otekah Wendleton over to his side, then her fervent online proselytizing would spread trust and faith in him throughout the world, especially amongst the key millennial demographic.
However, he couldn’t just send out an angel to meet her after ping-pong practice, hit her with a few miraculous theorems and give her the good news. The angel might be overheard or its proofs captured on CERN’s cameras, and then the proof would get out, destroying the point or possibility of faith. Wendleton would also no doubt do everything she could to dissect and figure out how the miracles were done, again ruining everything. A miracle is no mere magic trick, but it does still have a complex celestial mechanism by which it “works”. And Wendleton was a very good scientist.
Judeo-Christian God needed a way to prove his existence and miraculous nature to Otekah Wendleton, without giving anyone else any proof, and without showing her anything about how miracles work.
Two bandits cross paths in a dark forest. The moon is behind a cloud; they can’t see a thing. “Who goes there? What’s the password?” demands the first. “Disco sucks” replies the second. The first bandit slits his throat. She’s from the FBI, and now that she knows the password she goes on to bust the entire bandit ring. A smarter second bandit might instead reply “How do I know that you know the password?” and devise a way to prove that he knows the password, without giving it away to the first bandit if she does turn out to be from the FBI. This would be a zero-knowledge proof.
The notion of a zero-knowledge proof was first proposed in the 1980s by three researchers at MIT, who may or may not also have been bandits. They considered how bandits (and others) could prove statements like “I know the password” or “I have solved this sudoku” to other bandits they didn’t trust, without revealing any extra details like what the password is, or what the actual sudoku solution they’ve found is. The bandit verifying the statement learns nothing new, other than the fact that the statement is true. They are therefore completely unable to re-prove the statement to a third-party, meaning that they can’t get into the camp, and they can’t steal sudoku solutions they didn’t come up with themselves.
This sounded perfect. Never showing Otekah Wrigglesworth the actual solutions to the impossible problems would also reduce the chance of her brain exploding. Being omniscient, Judeo-Christian God had a hard time understanding the fundamental concept behind zero-knowledge proofs, but being omniscient he also managed to figure it out after reading a few blog posts.
Performing a zero-knowledge proof of his miraculous nature for Otekah Wendleton would require a lot of divine ingenuity, but also a lot of manual labor. The spirit of Judeo-Christian God entered and possessed another scientist at CERN to help out. Judeo-Christian God felt terrible about this, since he cared deeply about preserving humanity’s free will, but he made sure to chose someone who thought that free will was just an illusion created to repress the foolish, which made him feel a bit better.
His disciple/mind-zombie, whose name was Darryl, kidnapped Otekah Wendleton and drove her out to an abandoned warehouse in a suburb of Geneva. Once in the warehouse, Otekah eventually stopped swearing at Darryl and accepted the primacy of his assault rifle. They started with some of the basic Zero-Knowledge proofs to get Otekah warmed up and familiar with the concept. Darryl the Mind-Zombie proved that he had solved a sudoku without revealing the solution, proved that he knew how to make McDonalds burger sauce without revealing the recipe, and proved that he could walk through a seemingly impenetrable wall without revealing how he did it.
Otekah Wendleton was not impressed. I can solve sudoku and I never go to McDonalds since I object to the inhumane way in which they treat their chickens. The thing with the wall was definitely neat but it’s really not enough to make me believe in Judeo-Christian God.
OK OK, we’re just warming up, said Judeo-Christian God via Darryl the Mind-Zombie. He unrolled a huge, blank parchment across the floor of the warehouse. Draw an arbitrary graph of nodes and edges joining them, he boasted, and I will devise a way to color these nodes using only three colors, such that no two nodes of the same color are joined by an edge. Otekah Wendleton figured that the quickest way for her to get home was to co-operate with the strange man with the assault rifle, and so obediently drew an arbitrary graph. Once she had finished she began to cuss him out, but suddenly everything went dark and chloroformy.
When she awoke, every node on the graph was covered by a black hat. Under each of these hats I have placed a colored cube, said Darryl the Mind-Zombie. You may select two adjacent hats connected by an edge. I will reveal the cubes under those hats and you will see that they are indeed not of the same color! Otekah Wendleton selected two adjacent hats. Darryl the Mind-Zombie triumphantly hurled them across the room. Underneath, one cube was red, the other blue. Everything went dark again for Otekah Wendleton.
When she awoke again, the scene had been reset. I have kept the same underlying pattern, but have swapped the colors around, said Darryl the Mind-Zombie. You may once again select two adjacent hats connected by an edge, and I will once again show you that the cubes beneath them are not of the same color! We will repeat this process a large number of times, and with each iteration you will become more and more convinced that I have devised a genuine solution.
Otekah Wendleton had seen this particular zero-knowledge proof before. I know, I know, and since any NP problem can be mapped to the graph 3-coloring problem, that proves that you are capable of solving any NP problem in what appears to be a tractable amount of time. That’s kind of miraculous, wouldn’t you say? said Judeo-Christian God via Darryl the Mind-Zombie. Not really, said Otekah Wendleton, although it is impressive. I don’t want to fall victim to the common misconception that quantum computers can solve NP-hard problems in polynomial time, but…do you have a quantum computer?
Judeo-Christian God had prepared for this. You are a tough disciple, he said via Darryl the Mind-Zombie, with very challenging Bayesian priors. But what if I told you that I could color the nodes of this graph using only two colors, such that no two nodes of the same color were joined by an edge? That’s not possible, said Otekah Wendleton. Let me show you the power of Judeo-Christian God, said Darryl, walking over to Otekah, a pungent rag outstretched. No, no it’s fine, said Otekah, I’ll just look the other way whilst you fiddle with your hats.
And so Judeo-Christian God demonstrated to Otekah Wendleton a zero-knowledge proof of his claim that he knew a way to 2-color this graph. He showed that he knew a solution to a normal Sudoku using only the numbers 3 and 7. He successfully distinguished between two quantumly identical bosons.
It’s probably a miracle! gasped Otekah Wendleton. It probably is, my child, said Judeo-Christian God via Darryl the Mind-Zombie. Now go forth and spread the good word via your Instagram and other social feeds, especially to the key millennial demographic. I’m sorry Lord, I can’t do that, said Otekah Wendleton. Why not? said Judeo-Christian God. Well, she said, I have no reproducible evidence and no way to re-prove your existence to anyone else. It’s the classic zero-knowledge proof curse. Even though I’ve been recording this whole…episode on my Google Glass, none of the video footage proves anything to anyone other than me. Anyone without my private knowledge can just claim that I was in on it and this was all a set-up.
Darryl the Mind-Zombie on behalf of Judeo-Christian God rubbed his temples. But you see the bind this puts me in? he said. I can’t go around just proving to everyone that I exist - that would totally defeat the point of what I’m trying to do here. I really just need them to see a shareable photo on your Instagram account showing how cool Judeo-Christian God is, share it with 10 of their friends, and if those 10 friends each share it with 10 of their friends then I’ll have rebuilt humanity’s belief, trust and genuine, unseen faith in me in no time.
I think I have a compromise, said Otekah Wendleton.
And so it came to pass that Otekah Wendleton was given the power to perform one round per person of a zero-knowledge proof that she knew a way to color a graph using only 2 colors, such that no adjacent nodes had the same color. This ceremony, performed on a child’s sixth birthday, gave them a baseline confidence of around fifty percent that Judeo-Christian God existed and could perform miracles, but didn’t want to show you how. Since no one knew whether any ceremony other than their own was a sham, no one could intellectually honestly increase their confidence in God’s existence beyond this roughly fifty percent baseline. Judeo-Christian God saw a statistically significant lift in his numbers for months after the campaign was launched.
Judeo-Christian God looked down upon the earth, and saw that it was probably good.
Judeo-Christian God was in trouble. The latest polls were in, and belief in him was down, especially amongst the key millennial demographic. He needed to come up with a punchy viral marketing campaign to regain control of the conversation.
The easiest thing to do would be to heal a few leopards, send down a plagiarizing locust, and make sure that the major TV networks were around to see. This had always done it back in the day. But he had also made some inconvenient, on-the-record statements about wanting relationships based on trust and faith rather than proof. John 20:29 - “Then Jesus told him, ‘Because you have seen me, you have believed; blessed are those who have not seen and yet have believed.’” These ideals were meant for another, simpler time and culture, but there’s no telling the biblical literalists.
He didn’t usually like to do this kind of thing, but he needed to do just one tiny miracle, and disseminate just one tiny bit of proof of his existence to kick start his brand. As humanity had become more technologically advanced, the things they were willing to accept as miracles had changed. They knew enough medicine to be dangerous, and had all seen those TV shows where they show you how magic tricks are done. Parting the Red Sea? The Sea was in on it. Abraham and Sarah conceiving when they were like 100 years old? Isn’t IVF great. And yet they were still bizarrely eager to read far too much into pieces of toast. If you make enough toast, some of it will look kind of like Jesus! It would be a miracle if Jesus’s face never appeared in a jam sandwich!
Since humanity was transferring their faith into science and mathematics, Judeo-Christian God would perform mathematical miracles. He would prove the impossible, solve the intractable. You think graph 3-coloring is NP-Complete? He’d solve graph 2-coloring without breaking a sweat.
He had identified the perfect Instagram celebrity influencer to partner with to get his message out - particle physicist Otekah Wendleton. Wendleton began her career as a celebrity chef who used unnecessarily complex science to do her cooking. One day she was seized by the idea to instead use cooking to do science. Cooking was of no help whatsoever in her PhD, but she still turned out to be an extremely skilled theoretician and public communicator. She was now head of Antiproton Cell Experiment research group at CERN and wrote a popular weekly science-cooking crossover column for Buzzfeed.
Judeo-Christian God reasoned that if he could use just a teeny bit of proof to get Otekah Wendleton over to his side, then her fervent online proselytizing would spread trust and faith in him throughout the world, especially amongst the key millennial demographic.
However, he couldn’t just send out an angel to meet her after ping-pong practice, hit her with a few miraculous theorems and give her the good news. The angel might be overheard or its proofs captured on CERN’s cameras, and then the proof would get out, destroying the point or possibility of faith. Wendleton would also no doubt do everything she could to dissect and figure out how the miracles were done, again ruining everything. A miracle is no mere magic trick, but it does still have a complex celestial mechanism by which it “works”. And Wendleton was a very good scientist.
Judeo-Christian God needed a way to prove his existence and miraculous nature to Otekah Wendleton, without giving anyone else any proof, and without showing her anything about how miracles work.
Two bandits cross paths in a dark forest. The moon is behind a cloud; they can’t see a thing. “Who goes there? What’s the password?” demands the first. “Disco sucks” replies the second. The first bandit slits his throat. She’s from the FBI, and now that she knows the password she goes on to bust the entire bandit ring. A smarter second bandit might instead reply “How do I know that you know the password?” and devise a way to prove that he knows the password, without giving it away to the first bandit if she does turn out to be from the FBI. This would be a zero-knowledge proof.
The notion of a zero-knowledge proof was first proposed in the 1980s by three researchers at MIT, who may or may not also have been bandits. They considered how bandits (and others) could prove statements like “I know the password” or “I have solved this sudoku” to other bandits they didn’t trust, without revealing any extra details like what the password is, or what the actual sudoku solution they’ve found is. The bandit verifying the statement learns nothing new, other than the fact that the statement is true. They are therefore completely unable to re-prove the statement to a third-party, meaning that they can’t get into the camp, and they can’t steal sudoku solutions they didn’t come up with themselves.
This sounded perfect. Never showing Otekah Wrigglesworth the actual solutions to the impossible problems would also reduce the chance of her brain exploding. Being omniscient, Judeo-Christian God had a hard time understanding the fundamental concept behind zero-knowledge proofs, but being omniscient he also managed to figure it out after reading a few blog posts.
Performing a zero-knowledge proof of his miraculous nature for Otekah Wendleton would require a lot of divine ingenuity, but also a lot of manual labor. The spirit of Judeo-Christian God entered and possessed another scientist at CERN to help out. Judeo-Christian God felt terrible about this, since he cared deeply about preserving humanity’s free will, but he made sure to chose someone who thought that free will was just an illusion created to repress the foolish, which made him feel a bit better.
His disciple/mind-zombie, whose name was Darryl, kidnapped Otekah Wendleton and drove her out to an abandoned warehouse in a suburb of Geneva. Once in the warehouse, Otekah eventually stopped swearing at Darryl and accepted the primacy of his assault rifle. They started with some of the basic Zero-Knowledge proofs to get Otekah warmed up and familiar with the concept. Darryl the Mind-Zombie proved that he had solved a sudoku without revealing the solution, proved that he knew how to make McDonalds burger sauce without revealing the recipe, and proved that he could walk through a seemingly impenetrable wall without revealing how he did it.
Otekah Wendleton was not impressed. I can solve sudoku and I never go to McDonalds since I object to the inhumane way in which they treat their chickens. The thing with the wall was definitely neat but it’s really not enough to make me believe in Judeo-Christian God.
OK OK, we’re just warming up, said Judeo-Christian God via Darryl the Mind-Zombie. He unrolled a huge, blank parchment across the floor of the warehouse. Draw an arbitrary graph of nodes and edges joining them, he boasted, and I will devise a way to color these nodes using only three colors, such that no two nodes of the same color are joined by an edge. Otekah Wendleton figured that the quickest way for her to get home was to co-operate with the strange man with the assault rifle, and so obediently drew an arbitrary graph. Once she had finished she began to cuss him out, but suddenly everything went dark and chloroformy.
When she awoke, every node on the graph was covered by a black hat. Under each of these hats I have placed a colored cube, said Darryl the Mind-Zombie. You may select two adjacent hats connected by an edge. I will reveal the cubes under those hats and you will see that they are indeed not of the same color! Otekah Wendleton selected two adjacent hats. Darryl the Mind-Zombie triumphantly hurled them across the room. Underneath, one cube was red, the other blue. Everything went dark again for Otekah Wendleton.
When she awoke again, the scene had been reset. I have kept the same underlying pattern, but have swapped the colors around, said Darryl the Mind-Zombie. You may once again select two adjacent hats connected by an edge, and I will once again show you that the cubes beneath them are not of the same color! We will repeat this process a large number of times, and with each iteration you will become more and more convinced that I have devised a genuine solution.
Otekah Wendleton had seen this particular zero-knowledge proof before. I know, I know, and since any NP problem can be mapped to the graph 3-coloring problem, that proves that you are capable of solving any NP problem in what appears to be a tractable amount of time. That’s kind of miraculous, wouldn’t you say? said Judeo-Christian God via Darryl the Mind-Zombie. Not really, said Otekah Wendleton, although it is impressive. I don’t want to fall victim to the common misconception that quantum computers can solve NP-hard problems in polynomial time, but…do you have a quantum computer?
Judeo-Christian God had prepared for this. You are a tough disciple, he said via Darryl the Mind-Zombie, with very challenging Bayesian priors. But what if I told you that I could color the nodes of this graph using only two colors, such that no two nodes of the same color were joined by an edge? That’s not possible, said Otekah Wendleton. Let me show you the power of Judeo-Christian God, said Darryl, walking over to Otekah, a pungent rag outstretched. No, no it’s fine, said Otekah, I’ll just look the other way whilst you fiddle with your hats.
And so Judeo-Christian God demonstrated to Otekah Wendleton a zero-knowledge proof of his claim that he knew a way to 2-color this graph. He showed that he knew a solution to a normal Sudoku using only the numbers 3 and 7. He successfully distinguished between two quantumly identical bosons.
It’s probably a miracle! gasped Otekah Wendleton. It probably is, my child, said Judeo-Christian God via Darryl the Mind-Zombie. Now go forth and spread the good word via your Instagram and other social feeds, especially to the key millennial demographic. I’m sorry Lord, I can’t do that, said Otekah Wendleton. Why not? said Judeo-Christian God. Well, she said, I have no reproducible evidence and no way to re-prove your existence to anyone else. It’s the classic zero-knowledge proof curse. Even though I’ve been recording this whole…episode on my Google Glass, none of the video footage proves anything to anyone other than me. Anyone without my private knowledge can just claim that I was in on it and this was all a set-up.
Darryl the Mind-Zombie on behalf of Judeo-Christian God rubbed his temples. But you see the bind this puts me in? he said. I can’t go around just proving to everyone that I exist - that would totally defeat the point of what I’m trying to do here. I really just need them to see a shareable photo on your Instagram account showing how cool Judeo-Christian God is, share it with 10 of their friends, and if those 10 friends each share it with 10 of their friends then I’ll have rebuilt humanity’s belief, trust and genuine, unseen faith in me in no time.
I think I have a compromise, said Otekah Wendleton.
And so it came to pass that Otekah Wendleton was given the power to perform one round per person of a zero-knowledge proof that she knew a way to color a graph using only 2 colors, such that no adjacent nodes had the same color. This ceremony, performed on a child’s sixth birthday, gave them a baseline confidence of around fifty percent that Judeo-Christian God existed and could perform miracles, but didn’t want to show you how. Since no one knew whether any ceremony other than their own was a sham, no one could intellectually honestly increase their confidence in God’s existence beyond this roughly fifty percent baseline. Judeo-Christian God saw a statistically significant lift in his numbers for months after the campaign was launched.
Judeo-Christian God looked down upon the earth, and saw that it was probably good.