WolframAlpha.com
WolframCloud.com
All Sites & Public Resources...
Products & Services
WolframOne
Mathematica
WolframAlpha Notebook Edition
Programming Lab
Finance Platform
System Modeler
Wolfram Player
Wolfram Engine
WolframScript
Enterprise Private Cloud
Application Server
Enterprise Mathematica
WolframAlpha Appliance
Enterprise Solutions
Corporate Consulting
Technical Consulting
WolframAlpha Business Solutions
Resource System
Data Repository
Neural Net Repository
Function Repository
WolframAlpha
WolframAlpha Pro
Problem Generator
API
Data Drop
Products for Education
Mobile Apps
Wolfram Player
Wolfram Cloud App
WolframAlpha for Mobile
WolframAlphaPowered Apps
Services
Paid Project Support
Wolfram U
Summer Programs
All Products & Services »
Technologies
Wolfram Language
Revolutionary knowledgebased programming language.
Wolfram Cloud
Central infrastructure for Wolfram's cloud products & services.
Wolfram Science
Technologyenabling science of the computational universe.
Wolfram Notebooks
The preeminent environment for any technical workflows.
Wolfram Engine
Software engine implementing the Wolfram Language.
Wolfram Natural Language Understanding System
Knowledgebased broadly deployed natural language.
Wolfram Data Framework
Semantic framework for realworld data.
Wolfram Universal Deployment System
Instant deployment across cloud, desktop, mobile, and more.
Wolfram Knowledgebase
Curated computable knowledge powering WolframAlpha.
All Technologies »
Solutions
Engineering, R&D
Aerospace & Defense
Chemical Engineering
Control Systems
Electrical Engineering
Image Processing
Industrial Engineering
Mechanical Engineering
Operations Research
More...
Finance, Statistics & Business Analysis
Actuarial Sciences
Bioinformatics
Data Science
Econometrics
Financial Risk Management
Statistics
More...
Education
All Solutions for Education
Trends
Machine Learning
Multiparadigm Data Science
Internet of Things
HighPerformance Computing
Hackathons
Software & Web
Software Development
Authoring & Publishing
Interface Development
Web Development
Sciences
Astronomy
Biology
Chemistry
More...
All Solutions »
Learning & Support
Learning
Wolfram Language Documentation
Fast Introduction for Programmers
Wolfram U
Videos & Screencasts
Wolfram Language Introductory Book
Webinars & Training
Summer Programs
Books
Need Help?
Support FAQ
Wolfram Community
Contact Support
Premium Support
Paid Project Support
Technical Consulting
All Learning & Support »
Company
About
Company Background
Wolfram Blog
Events
Contact Us
Work with Us
Careers at Wolfram
Internships
Other Wolfram Language Jobs
Initiatives
Wolfram Foundation
MathWorld
ComputerBased Math
A New Kind of Science
Wolfram Technology for Hackathons
Student Ambassador Program
Wolfram for Startups
Demonstrations Project
Wolfram Innovator Awards
Wolfram + Raspberry Pi
Summer Programs
More...
All Company »
Search
WOLFRAM COMMUNITY
Connect with users of Wolfram technologies to learn, solve problems and share ideas
Join
Sign In
Dashboard
Groups
People
Message Boards
Answer
(
Unmark
)
Mark as an Answer
GROUPS:
Wolfram Science
Audio, Sound and Music
Physics
Graphics and Visualization
Graphs and Networks
Wolfram Function Repository
Wolfram Fundamental Physics Project
1
José Manuel Rodríguez Caballero
Dialogue on zeroknowledge in the Wolfram model
José Manuel Rodríguez Caballero, University of Tartu
Posted
8 months ago
860 Views

0 Replies

1 Total Likes
Follow this post

Dialogue on zeroknowledge in the Wolfram model
by José Manuel Rodríguez Caballero
January 30, 2021
Abstract.
Roughly speaking, the proof of a statement is zeroknowledge if it reveals the claim's validity, but it does not disclose any more information about it. Zeroknowledge proofs play a fundamental role in cryptography, e.g., in cryptocurrencies such as bitcoin. It is wellknown 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 zeroknowledge proof. The present expository computational essay illustrates this idea in the Wolfram model by proposing a zeroknowledge 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
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
After the confrontation, Sextus heard mysterious sound coming from ... nowhere???
I
n
[
]
:
=
S
o
u
n
d
[
S
o
u
n
d
N
o
t
e
[
"
G
"
,
3
,
"
H
a
r
p
"
]
]
O
u
t
[
]
=
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...
I
n
[
]
:
=
R
e
s
o
u
r
c
e
F
u
n
c
t
i
o
n
[
"
W
o
l
f
r
a
m
M
o
d
e
l
"
]
[
{
{
x
,
y
}
,
{
x
,
z
}
}

>
{
{
x
,
z
}
,
{
x
,
w
}
,
{
y
,
w
}
,
{
z
,
w
}
}
,
{
{
1
,
2
}
,
{
2
,
3
}
,
{
3
,
4
}
,
{
2
,
4
}
}
,
1
4
,
"
F
i
n
a
l
S
t
a
t
e
P
l
o
t
"
]
O
u
t
[
]
=
that is called
spatial hypergraph
, evolving according to the rules
I
n
[
]
:
=
R
u
l
e
P
l
o
t
[
R
e
s
o
u
r
c
e
F
u
n
c
t
i
o
n
[
"
W
o
l
f
r
a
m
M
o
d
e
l
"
]
[
{
{
{
x
,
y
}
,
{
x
,
z
}
}
{
{
x
,
z
}
,
{
x
,
w
}
,
{
y
,
w
}
,
{
z
,
w
}
}
}
]
,
"
R
u
l
e
P
a
r
t
s
A
s
p
e
c
t
R
a
t
i
o
"
0
.
2
5
]
O
u
t
[
]
=
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
Sextus heard another mysterious sound... emanated from Apollo
I
n
[
]
:
=
S
o
u
n
d
[
S
o
u
n
d
N
o
t
e
[
D
e
l
e
t
e
C
a
s
e
s
[
3
R
a
n
g
e
[
2
1
]
R
e
v
e
r
s
e
[
#
]
,
0
]

2
4
,
.
1
,
"
H
a
r
p
"
]
&
/
@
T
r
a
n
s
p
o
s
e
[
C
e
l
l
u
l
a
r
A
u
t
o
m
a
t
o
n
[
9
0
,
{
{
1
}
,
0
}
,
2
0
]
]
]
O
u
t
[
]
=
In front of Sextus, an infinite tree just appeared.
I
n
[
]
:
=
R
e
s
o
u
r
c
e
F
u
n
c
t
i
o
n
[
"
M
u
l
t
i
w
a
y
S
y
s
t
e
m
"
]
[
"
W
o
l
f
r
a
m
M
o
d
e
l
"
{
{
{
x
,
y
}
,
{
x
,
z
}
}
{
{
x
,
z
}
,
{
x
,
w
}
,
{
y
,
w
}
,
{
z
,
w
}
}
}
,
{
{
{
1
,
2
}
,
{
2
,
3
}
,
{
3
,
4
}
,
{
2
,
4
}
}
}
,
3
,
"
E
v
o
l
u
t
i
o
n
G
r
a
p
h
S
t
r
u
c
t
u
r
e
"
,
V
e
r
t
e
x
S
i
z
e
A
u
t
o
m
a
t
i
c
]
/
/
L
a
y
e
r
e
d
G
r
a
p
h
P
l
o
t
P
a
r
a
l
l
e
l
C
o
m
b
i
n
e
:
N
o
p
a
r
a
l
l
e
l
k
e
r
n
e
l
s
a
v
a
i
l
a
b
l
e
;
p
r
o
c
e
e
d
i
n
g
w
i
t
h
s
e
q
u
e
n
t
i
a
l
e
v
a
l
u
a
t
i
o
n
.
P
a
r
a
l
l
e
l
C
o
m
b
i
n
e
:
N
o
p
a
r
a
l
l
e
l
k
e
r
n
e
l
s
a
v
a
i
l
a
b
l
e
;
p
r
o
c
e
e
d
i
n
g
w
i
t
h
s
e
q
u
e
n
t
i
a
l
e
v
a
l
u
a
t
i
o
n
.
P
a
r
a
l
l
e
l
C
o
m
b
i
n
e
:
N
o
p
a
r
a
l
l
e
l
k
e
r
n
e
l
s
a
v
a
i
l
a
b
l
e
;
p
r
o
c
e
e
d
i
n
g
w
i
t
h
s
e
q
u
e
n
t
i
a
l
e
v
a
l
u
a
t
i
o
n
.
G
e
n
e
r
a
l
:
F
u
r
t
h
e
r
o
u
t
p
u
t
o
f
P
a
r
a
l
l
e
l
C
o
m
b
i
n
e
:
:
n
o
p
a
r
w
i
l
l
b
e
s
u
p
p
r
e
s
s
e
d
d
u
r
i
n
g
t
h
i
s
c
a
l
c
u
l
a
t
i
o
n
.
O
u
t
[
]
=
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
"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".
I
n
[
]
:
=
G
=
T
r
a
n
s
i
t
i
v
e
R
e
d
u
c
t
i
o
n
G
r
a
p
h
[
G
r
a
p
h
[
E
d
g
e
L
i
s
t
[
R
e
s
o
u
r
c
e
F
u
n
c
t
i
o
n
[
"
M
u
l
t
i
w
a
y
F
u
n
c
t
i
o
n
S
y
s
t
e
m
"
]
[
{
F
l
o
o
r
[
S
q
r
t
[
G
o
l
d
e
n
R
a
t
i
o
#
]
]
^
2
,
C
e
i
l
i
n
g
[
S
q
r
t
[
G
o
l
d
e
n
R
a
t
i
o
#
]
]
^
2
}
&
,
1
,
1
5
,
"
S
t
a
t
e
s
G
r
a
p
h
"
]
]
,
V
e
r
t
e
x
L
a
b
e
l
s
A
u
t
o
m
a
t
i
c
]
]
;
"Here, is the transitive reduction of this multiway system"
I
n
[
]
:
=
G
/
/
L
a
y
e
r
e
d
G
r
a
p
h
P
l
o
t
O
u
t
[
]
=
"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 11 way, using Rabin's oneway permutation of quadratic residues with respect to some modulus 62 857. Sextus does not know the factorization of this number."
I
n
[
]
:
=
H
=
G
r
a
p
h
[
T
o
S
t
r
i
n
g
[
P
o
w
e
r
M
o
d
[
T
o
E
x
p
r
e
s
s
i
o
n
[
F
i
r
s
t
[
#
]
]
,
2
,
6
2
8
5
7
]
]
T
o
S
t
r
i
n
g
[
P
o
w
e
r
M
o
d
[
T
o
E
x
p
r
e
s
s
i
o
n
[
L
a
s
t
[
#
]
]
,
2
,
6
2
8
5
7
]
]
&
/
@
E
d
g
e
L
i
s
t
[
G
]
,
V
e
r
t
e
x
L
a
b
e
l
s
A
u
t
o
m
a
t
i
c
]
;
I
n
[
]
:
=
H
/
/
L
a
y
e
r
e
d
G
r
a
p
h
P
l
o
t
O
u
t
[
]
=
"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,"
I
n
[
]
:
=
P
o
w
e
r
M
o
d
[
7
9
2
1
,
2
,
6
2
8
5
7
]
O
u
t
[
]
=
1
0
9
5
5
"The trick is that, in general, knowing
2
n
m
o
d
6
2
8
5
7
it is extremely hard for Sextus to guess n, unless Sextus knows the factorization of the modulus."
"Notice that, although both graphs G and H are isomorphic, their adjacency matrices look rather different."
I
n
[
]
:
=
G
r
a
p
h
i
c
s
R
o
w
[
{
A
d
j
a
c
e
n
c
y
M
a
t
r
i
x
[
G
]
/
/
M
a
t
r
i
x
P
l
o
t
,
A
d
j
a
c
e
n
c
y
M
a
t
r
i
x
[
H
]
/
/
M
a
t
r
i
x
P
l
o
t
}
]
O
u
t
[
]
=
I
n
[
]
:
=
I
s
o
m
o
r
p
h
i
c
G
r
a
p
h
Q
[
G
,
H
]
O
u
t
[
]
=
T
r
u
e
Zeroknowledge
"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."
I
n
[
]
:
=
H
i
g
h
l
i
g
h
t
G
r
a
p
h
[
H
,
P
a
t
h
G
r
a
p
h
[
F
i
r
s
t
[
F
i
n
d
P
a
t
h
[
H
,
"
1
"
,
"
1
0
9
5
5
"
]
]
]
]
/
/
L
a
y
e
r
e
d
G
r
a
p
h
P
l
o
t
O
u
t
[
]
=
"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
Finally, using a zeroknowledge 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
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 proofsystems, Proc. 17th ACM Sympos. on Theory of Computing, 1985, pp. 291304.
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. 174187.
R. Impagliazzo, A collection of direct zeroknowledge protocols for NPcomplete 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
S. Wolfram, "Music,
Mathematica, and the Computational Universe"
https://writings.stephenwolfram.com/2011/06/musicmathematicaandthecomputationaluniverse/
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
S. Wolfram,.
A Project to Find the Fundamental Theory of Physics. Wolfram Media, 2020.
https://www.amazon.com/ProjectFindFundamentalTheoryPhysics/dp/1579550355/?source=swwritings
POSTED BY:
José Manuel Rodríguez Caballero
Answer
Mark as an Answer
Reply

Flag
Reply to this discussion
in reply to
Add Notebook
Community posts can be styled and formatted using the
Markdown syntax
.
Tag limit exceeded
Note: Only the first five people you tag will receive an email notification; the other tagged names will appear as links to their profiles.
Publish anyway
Cancel
Reply Preview
Attachments
Remove
Add a file to this post
Follow this discussion
or
Discard
Group Abstract
Be respectful. Review our
Community Guidelines
to understand your role and responsibilities.
Community Terms of Use
Feedback
Enable JavaScript to interact with content and submit forms on Wolfram websites.
Learn how »