Dialogue on zero-knowledge in the Wolfram model
Dialogue on zero-knowledge in the Wolfram model
by José Manuel Rodríguez Caballero
January 30, 2021
Abstract. Roughly speaking, the proof of a statement is zero-knowledge if it reveals the claim's validity, but it does not disclose any more information about it. Zero-knowledge proofs play a fundamental role in cryptography, e.g., in cryptocurrencies such as bitcoin. It is well-known that, under some natural hypothesis, any mathematical proof, e.g., the proof that the square root of two is irrational, can be transformed into a zero-knowledge proof. The present expository computational essay illustrates this idea in the Wolfram model by proposing a zero-knowledge proof that our universe is generated by a given set of rules and a given initial condition. For educational purposes, the ideas will be expressed in fictional dialogue, inspired by dialogue from Leibniz's Theodicy, which was itself inspired by Valla's dialogue De libero arbitrio.
An old Roman legend
An old Roman legend
According to an ancient legend, mentioned in Valla's De libero arbitrio and in Leibnitz's Theodicy, a handsome and happy teenager went to Delphi's Oracle, curious to know his future. He was the son of Rome's kind, and his dream was to be remembered in the history of humanity as a glorious wise king. His name was Sextus Tarquinius. Many influential philosophers, writers, and painters have represented fragments of his life history throughout the centuries.
Inside the temple, fascinated by the mystery and beauty, Sextus meets Apollo, manifested himself as a shining presence possessing the body of his high priestess, the Pithia. With a big smile on his face, Sextus asked: "how will I be remembered for posterity?" Apollo answered throughout the lips of the Pythia: "humanity will feel disgusted by you."
The smile disappeared in the middle of a vast silence. Experiencing problems to articulate words, Sextus accused the Pythia: "Olympian gods do not exist, you are lying, you have no idea about what my future is!"
Spatial hypergraph
Spatial hypergraph
After the confrontation, Sextus heard mysterious sound coming from ... nowhere???
In[]:=
Sound[SoundNote["G",3,"Harp"]]
Out[]=
Sextus took a look at the wall, and it was not there anymore. In a panic, he took a look at the floor and the ceil, but everything has disappeared. Instead, Sextus saw this...
In[]:=
ResourceFunction["WolframModel"][{{x,y},{x,z}}->{{x,z},{x,w},{y,w},{z,w}},{{1,2},{2,3},{3,4},{2,4}},14,"FinalStatePlot"]
Out[]=
that is called spatial hypergraph, evolving according to the rules
In[]:=
RulePlot[ResourceFunction["WolframModel"][{{{x,y},{x,z}}{{x,z},{x,w},{y,w},{z,w}}}],"RulePartsAspectRatio"0.25]
Out[]=
Confused, Sextus asked: "Just what on earth is going on here?"
"You see the universe as it is at its fundamental level,"— answered an ethereal voice.
"Apollo, are you?" — Sextus asked in fear.
"Yes, I have given you a temporary power that only Gods have: to see how the world as it is," — replied the God of Sun — "in this hypergraph you can see your future"
Sextus glanced at the evolving hypergraph and saw many portraits at a museum; people looked at these pictures with disgust.
"You are lying, Apollo; I would never do what is represented about me in these pieces of art" — claimed Sextus with hubris — "the spatial hypergraphs that you are presenting to me did not evolve from the spatial hypergraph in which I was born. It is a fake."
Multiway system
Multiway system
Sextus heard another mysterious sound... emanated from Apollo
In[]:=
Sound[SoundNote[DeleteCases[3Range[21]Reverse[#],0]-24,.1,"Harp"]&/@Transpose[CellularAutomaton[90,{{1},0},20]]]
Out[]=
In front of Sextus, an infinite tree just appeared.
In[]:=
ResourceFunction["MultiwaySystem"]["WolframModel"{{{x,y},{x,z}}{{x,z},{x,w},{y,w},{z,w}}},{{{1,2},{2,3},{3,4},{2,4}}},3,"EvolutionGraphStructure",VertexSizeAutomatic]//LayeredGraphPlot
Out[]=
Each vertex in the tree was a spatial hypergraph, and there was an arrow from vertex x to vertex y anytime that it was possible to go from x to y by applying a rule. Sextus saw that the root of this tree was the universe at the moment when he was born. The complexity of this structure was overwhelmed to Sextus's mortal mind. The name of this tree is multiway system.
Then Apollo told him: "Now, that you are in the root, I will show you a path from your position to the vertex that I just show you, and you did not believe me that it belongs to a branch of your multiway evolution."
"Don't do it!" — commanded Jupiter's voice — "a mortal must not know all the details of his future, otherwise he can change the prophecies."
Commitment
Commitment
"Don't worry, dad?" — said Pallas to Jupiter — I will do it myself in a way that this unbeliever will verify by himself that Apollo told him the truth about his future. Still, he will not be able to know anything else.
"Ok, my daughter" — replied Jupiter calmed down — "show me, but please, first explain it with a numeric multiway system so that the mortal that is among us could understand it."
"Ok" — said Pallas, speaking as a good teacher — "for simplicity, instead of the multiway system of the hypergraph, consider the following numeric multiway system, where 1 is at the root and any state n evolves to both Floor[Sqrt[GoldenRatio n]]^2 and Ceiling[Sqrt[GoldenRatio n]]^2".
In[]:=
G=TransitiveReductionGraph[Graph[EdgeList[ResourceFunction["MultiwayFunctionSystem"][{Floor[Sqrt[GoldenRatio#]]^2,Ceiling[Sqrt[GoldenRatio#]]^2}&,1,15,"StatesGraph"]],VertexLabelsAutomatic]];
"Here, is the transitive reduction of this multiway system"
In[]:=
G//LayeredGraphPlot
Out[]=
"We can imagine 1 as the state of the universe when Sextus was born" — Pallas explained — "Let's imagine that the spatial hypergraph that Apollo showed to him corresponds to the number 7921. Somewhere in between 1 and 7921, Sextus becomes a disgrace for humanity, but we will not reveal this information to him."
"Notice that" — Pallas continued her explanation — "because of his computational limitations, Sextus is not able to efficiently compute a path from 1 to 7921. There are too many possibilities to check for him."
"Now" — said Pallas — "I will rename all the vertices in the graph in a 1-1 way, using Rabin's one-way permutation of quadratic residues with respect to some modulus 62 857. Sextus does not know the factorization of this number."
"For example I transform 4 into 16, 9 into 81, and so on, changing the vertex n into PowerMod[n,2,62857]. Notice that 1 is remains the same, 7921 becomes 10955 (this information is revealed to Sextus), indeed,"
"Notice that, although both graphs G and H are isomorphic, their adjacency matrices look rather different."
Zero-knowledge
Zero-knowledge
"Now, Sextus" — said Pallas — "I will give you two options. Either:"
"(i) I will show you the inverse of PowerMod[n,2,62857] for all quadratic residue n (this is easy to check) and that G and H have the same arrows. In this case, you can convince yourself that I honestly followed the protocol."
"(ii) I will show you a path from 1 to 10955 in H. From this information, you can deduce that there is a path from 1 to 7921 in G provided that I did not tick you during my construction of H, e.g., by dishonestly changing the numbers, putting arrows in H that are not in G."
"What if you are just lucky, but you are lying" — replied Sextus to Pallas.
"If you are not convinced," — answered Pallas — "we can repeat the protocol several times with different modulus for the Rabin's permutation. Notice that the probability that I lied and I succeed the test just by luck will exponentially decrease with the number of tests."
End of the legend
End of the legend
Finally, using a zero-knowledge proof, Pallas convinced Sextus that Apollo's vision of his future was indeed part of his multiway evolution, without revealing why people will hate him so much. After the sad confirmation, Sextus returned to reality and woke up in the temple.
Angry with Jupiter for causing such a horrible fate for him, Sextus went to His temple in Dodona, where he meets Theodorus, but to know that happened, you need to read Leibniz's Theodicy...
References
References
M. Blum, "How to prove a theorem so no one else can claim it." Proceedings of the International Congress of Mathematicians. Vol. 1. 1986.
S.Goldwasser, S. Micali, and C. Rackoff, The knowledge complexity of interactive proof-systems, Proc. 17th ACM Sympos. on Theory of Computing, 1985, pp. 291-304.
O. Goldreich, S. Micali, and A. Wigderson, Proofs that yield nothing but the validity of the assertion, and the methodology of cryptographic protocol design, presented at a Workshop on Probabilistic Algorithms (Marseille, March 1986) organized by C. P. Schnorr; Proc. 27th IEEE Sympos. on the Found, of Computer Science, 1986, pp. 174-187.
R. Impagliazzo, A collection of direct zero-knowledge protocols for NP-complete problems, Berkeley Computer Science Division Rept., Univ. of Calif., Berkeley, Calif., 1986.
G. W. Leibniz, "Theodicy: Essays on the Goodness of God, the Freedom of Man and the Origin of Evil". Wipf and Stock Publishers, 2000.
L. Valla , "Dialogue on free will.".
S. Wolfram, A New Kind of Science. Vol. 5. Champaign, IL: Wolfram media, 2002.
https://www.wolframscience.com
https://www.wolframscience.com
S. Wolfram, "Music, Mathematica, and the Computational Universe"
https://writings.stephenwolfram.com/2011/06/music-mathematica-and-the-computational-universe/
https://writings.stephenwolfram.com/2011/06/music-mathematica-and-the-computational-universe/
S. Wolfram, “A Class of Models with the Potential to Represent Fundamental Physics,” Complex Systems, 29(2), 2020 pp. 107–536.
https://doi.org/10.25088/ComplexSystems.29.2.107
https://doi.org/10.25088/ComplexSystems.29.2.107
S. Wolfram,. A Project to Find the Fundamental Theory of Physics. Wolfram Media, 2020.
https://www.amazon.com/Project-Find-Fundamental-Theory-Physics/dp/1579550355/?source=sw-writings
https://www.amazon.com/Project-Find-Fundamental-Theory-Physics/dp/1579550355/?source=sw-writings