►
Description
Explanation of the main ideas behind STARKs.
Slides (with updates): https://docs.google.com/presentation/d/1KuNRQ0IcGc8qO0RASmrwvwiRmzH-Et5LEXTFvQmQCeg
Recording and editing by https://twitter.com/alexboerger
A
This
I
will
try
to
explain
to
you
how
it
is
possible
to
verify
the
correct
execution
of
a
computation
without
re
executing.
Of
course,
just
so
a
computation
is,
in
this
sense,
a
fixed
procedure
that
runs
on
a
certain
input
and
and
results
in
a
certain
output
and
the
the
computation
itself
is
deterministic.
So
whenever
you
run
it
on
the
same
input,
you
always
get
the
same
output
and,
of
course,
the
obvious
way
to
do.
That
is
to
just
run
the
program
again,
and
that
is
what
is
currently
done
in
blockchains.
A
If
you
sink
a
blockchain,
you
just
rerun
all
the
computation
that
the
miners
have
already
done.
I
mean
you,
don't
rerun
the
search
that
is
done
in
mining,
but
you
rerun
executing
the
transactions
and
on
the
horizon
there
is.
There
are
new
research
results
which
might
allow
you
to
do
some
things,
which
then
result
in
checking
a
computation
and
being
reasonably
sure
that
it's
correct
faster
than
re
executing
them.
A
Okay
and
as
an
outline
of
this
talk,
I
will
start
with
explaining
why
that
might
be
useful
for
block
chains
already
started
a
little
on
that,
and
then
there
are
yeah.
Basically
two
popular
approaches
to
that
problem.
One
of
them
is
called
snark
and
the
other
one
is
called
Stark
and
they
share
some
properties
and
they
tend
in
some
other
regards.
A
First,
two
already
board
can
understand
that,
and
this
is
used
for
low
degree
testing
and
then,
in
the
end,
we'll
see
how
you
can
add.
Zero
knowledge
to
the
whole
thing.
I
am
in
no
way
responsible
for
any
of
the
results
explained
here,
and
this
is
a
long
line
of
research
that
started
in
the
90s,
and
the
names
here
are
just
some
of
the
contributors
and
I
already
warned
you
that
I
will
leave
out
some
details.
Quite
a
lot
actually,
but
I
hope.
It's
still.
A
A
When
you
look
at
a
blockchain,
it
always
starts
with
a
block
with
a
number
0
which
contains
the
Genesis
state
which
might
be
completely
empty
or
contains
some
pre
allocated
funds.
And
then
you
add
a
new
block,
and
this
block
number
1
then
contains
a
list
of
transactions
and
sometimes
also
something
called
a
post,
State
Route.
So
this
is
you
you
take
the
the
state
of
the
blockchain,
so
kind
of
the
account
balances
and
create
a
local
tree
of
it
and
in
in
the
block
or
in
the
block
header.
A
You
don't
react,
secure
the
transactions-
and
this
is
little
boring,
but
it
gets
more
exciting
when
we
add
block
number
to
this
block
number
two
looks
similar.
It
also
has
transactions
and
it
also
has
a
post
state
route.
It
also
has
a
proof,
but
now
the
proof
does
not
only
prove
that
the
transactions
took
the
state
from
the
state
in
block
number
one
to
the
state
in
block
number
two,
but
it
also
proves
that
the
verification
of
the
proof
in
block
number
one
was
done
correctly.
A
Ok,
so
this
proof
does
not
prove
that
the
transition
from
Genesis
state
to
block
number
one
was
correct.
It
only
proves
that
the
proof
in
block
number
one
was
verified
correctly
and
that's
a
big
big
difference,
because,
especially
as
the
blockchain
grows,
the
amount
of
work
that
is
required,
there
stays
the
same.
A
So
we
only
verify
the
transition
from
block
two
to
block
3
and
the
checking
of
the
proof
in
block.
We
don't
verify
the
checking
of
the
proof
in
block
number
one
and
the
transition
from
zero
to
one.
So
what
we
only
do
is
we
have
a
proof
that
the
state
transition
from
the
previous
block
to
the
current
was
correct
and
the
previous
proof
is
correct,
and
this
means
that
syncing,
a
blockchain,
if
you
have
the
technology,
then
seeking
a
blockchain
just
means
download
the
state
and
verifying
the
proof
in
the
highest
block.
That's
it!
A
A
You
don't
know
whether
it's
the
highest
or
the
one
with
with
the
most
proof
work
so
that
that's
similar
to
data
world
ability
so
somewhere
out
there,
so
you
might
be
disconnected
from
the
network
and
the
rest
of
the
network
might
see
a
much
longer
chain
and
you're
on
the
wrong
block.
That's
something
you
can't
do
here.
You
can
only
see
that
the
block
you
have
is
correct
and
the
whole
history
is
correct.
A
Okay,
so
that's
what
might
be
possible
in
the
future
and
now,
how
does
how
do
these
yeah
computation
verifiers
work?
Almost
always
those
start
with
something
that
is
called
an
interactive
protocol
in
the
native
protocol.
You
always
have
two
parties,
one
party
or
yeah.
You
might
also
have
more
parties,
but
most
of
the
time
you
have
two
parties,
one
of
them
is
called
approver
and
the
other
one
is
called
a
verifier.
A
The
prover
is
usually
much
more
powerful
than
the
verify,
so
think
of
that
prover
is
someone
who
creates
a
transaction,
and
the
verifier
is
just
a
smart
contract
on
the
blockchain.
So
the
prover
has
a
tremendous
amount
of
memory.
Tremendous
amount
of
disk
space,
access
to
network
and
verify
is
extremely
limited
and
they
exchange
messages.
Approvers
enter
message.
The
verifier
verify
reach
that
message.
A
Answers
with
her
own
message
prove
a
reach
that
message
again
answers
with
with
her
own
message
and
so
on,
and
the
verifier
is
allowed
to
use,
runs
and
so
on,
correct
input,
so
think
of
it
as
for
a
fixed
computation
input
and
output
pair,
and
this
this
is
correct
if
the
computation
on
that
input
yields
that
output.
If
that's
the
case,
then
the
verify
has
to
accept
after
the
exchange
for
messages
and
on
incorrect
input.
If
the
computation
was
wrong,
then
the
verify
has
to
reject
with
high
probabilities
the
verify
uses
randomness.
A
We
might
take
a
look
at
that
later,
okay
and
now,
let's
compare
snarks
and
Stark
so
just
name
the
the
acronym
snarks
is
succinctly.
Non-Interactive
arguments
of
knowledge
and
Starks
is
six
inked
arguments
of
knowledge,
although
Starks
are
also
not
active
most
of
the
time,
but
it
doesn't
really
matter
what
these
acronyms
mean.
A
The
thing
is
that
the
proof
size
so
proof
size
means
the
length
of
the
exchanged
messages
and
usually
when
they
are
non
interactive.
This
means
the
prove
it
just
sends
one
single
message
to
the
verifier,
the
verifier
processes,
this
message
and
says:
I
accept
or
I
reject,
and
since
it's
just
a
silly
message,
it's
also
called
proof
for
snarks.
They
are
very
short,
so
something
like
188
bytes,
mostly
regardless
of
the
size
of
the
computation
and
for
Starks.
They
are
longer
currently
in
the
range
of
400
kilobytes.
Something
like
that.
A
Snarks
are
not
run
once
this
means.
Snarks
require
a
quite
costly
setup
phase,
but
the
setup
phase
has
only
has
to
be
done
once
for
one
type
of
computation
and
then
it's
extremely
fast.
So
you
have
to
invest
a
little
in
the
setup.
Then
you
can
repeat
it
multiple
times
and
for
stocks,
that's
not
the
case,
there's
no
setup!
So
it's
it
generates
a
little
slower,
but
you
can
do
it
multiple
times
on
different
functions,
transparent,
that's
quite
important!
That
means
that
for
snarks
you
need
random
numbers
and
you
need
to
keep
them
secret.
A
So
in
this
so-called
trusted
setup
setup
face
that
you
just
do
once
in
the
beginning.
Random
numbers
are
generated
and
they
have
to
be
kept
secret
or
you
have
to
pick
it
secret
kept
secret
at
all
cost,
but
they
are
not
lead
needed
anymore
later,
so
you
can
also
destroy
them.
That's
why
you
might
have
seen
videos
of
people
drilling
holes
and
their
computers,
and
things
like
that
for
starts.
That's
not
the
case.
A
Anything
that
happens
in
Starks
is
public,
so
of
course,
Starks
can
also
have
zero
knowledge,
but
so
there
are
private
parts,
but
you
don't
need
this
trusted
setup.
You
don't
need
the
the
toxic
waste,
the
random
numbers
that
you
need
to
destroy
and
snarks
rely
on
some
assumptions
about
cryptography,
for
example,
that
elliptic
curves
are
secure
and
also
something
like
knowledge
of
exponent,
which
is
in
practice
not
true
anymore.
Once
we
have
scalable.
A
Yeah
scalable
actual
quantum
computers
so
because
quantum
computers
can
break
elliptic
curve
cryptography
for
Starks,
that's
also
better
because
they
only
rely
on
the
existence
of
collision,
resistant,
hash
functions
and
I
think
this
is
something
that
is
reasonably
true
for
yeah.
Quite
a
long
time.
Okay,.
A
Both
technologies
here
and
many
others
start
with
encoding
computations
as
statements
about
the
Equality
of
polynomials,
and
this
is
so
encoding
computations
as
polynomials
is
quite
useful
because
you
can
easily
check
whether
two
polynomials
are
equal
or
not,
by
evaluating
on
them
on
some
points,
and
the
reason
is
that
if
two
polynomials
are
not
equal,
then
they
are
different
at
almost
all
points.
So
in
the
rest
of
the
talk
we
will
always
talk
about
polynomials
over
finite
fields,
and
this
means
you
can
actually
have
numbers
there.
A
A
The
problem
is
that
we
want
to
avoid
the
proof
of
having
to
send
the
full
polynomial
to
the
verify,
because
the
polynomial
is
usually
rather
large
and
we
want
the
messages
to
keep
small,
because
these
messages
are
stuff,
then
it's
then
to
be
encoded
into
the
blockchain.
So
the
verifier
wants
to
check
that
two
polynomials,
the
prover
claims
something
about,
are
equal
and
has
to
evaluate
them
for
that,
but
she
doesn't
know
the
polynomial.
So
she
kind
of
has
to
ask
the
prover
to
evaluate
the
polynomial
for
her
and
then
check
that.
A
Then
the
numbers
are
equal,
but
she
has
to
kind
of
trust
the
prover
that
this
even
evaluation
was
done
correctly
or
the
prover
has
to
convince
her
that
she
did
it
correctly
and
snarks
in
stark.
Take
two
different
approaches:
there
snarks
use
partially
homomorphic
encryption
for
that
and
it
works
by
the
prover
evaluating
the
polynomial
at
an
unknown
point
or
an
encrypted
point,
and
this
encrypted
point
is
the
thing
that
is
generated
during
this
trusted
set
up.
A
Since
so
this
is
home,
morphic
encryption.
So
if
the,
if
the
value
at
the
encrypted
point,
which
is
the
encryption
of
the
value
at
the
point,
so
if
those
are
different,
then
also
the
decrypted
versions
are
different,
and
because
of
that,
you
can
throw
away
the
randomness.
So
you
don't
need
the
decrypted
point
anymore.
You
can
just
work
with
the
encrypted
point.
A
It
starts
with
an
input,
so
let
us
simplify
computations
here
rather
strongly
and
let's
assume
we
have
a
computer
that
only
has
three
registers.
These
registers
are
a
1,
a
2
and
a
3.
The
input
at
the
beginning
of
computation
is
present
in
these
registers
at
step
0.
This
is
1
4
and
2,
and
then
we
have
a
fixed
program
that
does
something
on
these
registers.
So,
for
example,
at
step
1
we
take
the
value
of
a
2
and
a
3
at
them
and
store
it
in
a
3
and
then
at
step
2.
A
A
Now
yeah
we
wanted
to
encode
that
in
polynomials,
so
what
the
prove
it
does
is
she
takes
the
sequence
of
values
for
a1
and
turns
that
into
a
function.
So
the
function,
a
one
at
point:
zero
is
1
a
1
at
point,
1
is
1,
a
1
and
point:
2
is
10
a
1
and
point
3
is
40
and
so
on.
These
are
8001
points
and
because
of
that
you
can
create
a
degree
8000
polynomial
that
behaves
exactly
as
that
function.
At
these
points,
so
the
polynomial
at
0
is
1.
A
A
Yeah
I
mean
in
the
paper
they
actually
go
to
degree,
I,
think
10
million
or
something
like
that.
I
mean
number
of
steps
of
a
computation
yeah,
and
we
do
that
with
all
three
registers,
and
now
there
is
another
polynomial
called
C
and
this
kind
of
encodes
the
the
program
so
and
it
can
be
used
to
check
the
correctness
of
a
single
step
in
the
following
way.
Okay,
so
this
is
the
first
complicated
formula:
I'm
sorry
about
that,
so
the
computation
is
correct.
If
and
only
if
the
inputs
and
the
outputs
are
correct.
A
A
So
these
steps
we
run
C
or
we
evaluate
see
the
which
is
the
step
correctness,
checker
and
as
inputs,
it
gets
X
the
step
and
then
a
1
of
X,
a
2
of
X,
a
3
of
X,
the
values
of
the
register
that
registers
at
the
beginning
of
the
step
and
the
values
of
the
registers
after
the
step.
So
that
is
all
you
need
if
you
know
the
program,
that
is
all
you
need
to
verify
the
correctness
of
a
single
step
and
it
has
to
be
0
and
yeah.
A
A
Good
there
was
graphics
here:
okay,
that's
there's
a
table
and
has
actual
numbers.
Okay,
let's
continue
so
that's
again:
repetition
of
what
we
had
in
the
bottom,
the
condition
for
computation
being
correct.
Now
something
happens,
that's
a
simplification,
but
you
might
not
think
of
it
as
a
simplification,
simplification,
let's
see
so
we
have
these
three
registers
and
what
we
do.
So
we
have
three
registers
and
one
polynomial
per
register,
and
we
combine
these
three
polynomials
into
a
single
polynomial
by
just
kind
of
stretching
it.
A
So
we
call
this
single
polynomial
a
and
so
perhaps
it's
better
to
explain
it
on
the
table
again,
we
build
it
such
that
a
at
zero
is
this
one
here.
This
is
a
at
one,
a
at
three,
a
at
four
a
at
5
at
6,
at
7
and
so
on.
So
it's
basically
just
encoding
the
whole
table
into
a
single
sequence
of
values
and.
A
B
A
A
So
this
is
so
yeah
this
is
stuff
to
prove
has
to
do,
but
that
stuff,
the
verifier
does
not
have
to
do
right
so
and
the
idea
is
verifying.
The
computation
is
faster
than
re
executing
it,
but
generating
the
proof,
of
course,
takes
longer
than
just
reacts,
acute
it
or
just
executing
it.
The
downside,
a
question
little
or
not
yet,
okay,
I
will
I
will
have
an
overview
of
the
whole
protocol
later.
Perhaps
it
gets
clearer,
then,
okay
and
now
so
what
the
statement
here.
A
What
we
do
is
so
we
say
that
the
the
polynomial
on
the
left
hand,
side
here,
is
0
at
these
points,
and
this
means,
on
the
right
hand,
side.
If
you
want
to
have
a
polynomial
here,
at
the
right
hand,
side
we
have
to
find
a
polynomial
that
is
0
at
these
points,
and
that
is
this
polynomial
here
the
polynomial
Z
is
0
at
exactly
the
point:
zero
one,
two
until
seven,
nine
and
nowhere
else
and.
A
If
you
just
put
Z
here,
then
this
will
not
capture
the
full
polynomial
here.
So
we
need
to
add
another
polynomial
factor
or
multiply
a
different
explanation.
Is
we
take
this
polynomial
and
it
has
some
zeros.
We
know
that
it
has
zeros
here.
So
if
we
have
a
field
that
is
algebraically
closed,
like
the
complex
number
or
a
proper
finite
field,
then
we
can
factor
out
these
factors:
X
minus
0-
and
if
we
do
that,
then
these
factors
we
removed
are
Z
and
the
rest
is
d.
A
A
Okay-
and
the
important
thing
here
is
that
so
we
have
the
same
left-hand
side
here
and
replace
the
0
by
a
product
of
two
polynomials,
and
now
we
can
say
that
this
equality
is
not
only
hold
for
all
X
in
this
discrete
set,
but
for
all
X
in
the
whole
field.
So
we
have
actual
polynomial
identity
everywhere,
and
because
of
that,
we
can
apply
the
stuff.
We
talked
about
earlier
checking
equality
of
two
polynomials
by
evaluating
them
at
some
points
and
checking
that
the
value
is
the
same.
A
A
This
will
be
important
later.
Okay,
now
we've
come
unto
here
and
I
see
still
see
some
open
eyes,
that's
great,
because
now
I
will
describe
the
full
interactive
protocol.
That
is
run
now
between
prove
and
verify,
and
as
a
reminder,
this
is
the
property
you
want
to
show
at
the
end,
okay,
given
so
this
means
this
is
a
shared
input
that
is
available
both
through
the
prove
ER
and
the
verifier
C
is
available
to
both,
because
this
is
kind
of
encoded
in
the
program.
That's
the
the
function,
the
program
they
want
to
verify.
A
Then
these
a
1,
a
2,
a
3.
These
are
simple
functions:
3x
plus
2,
or
something
like
that
and
then
Z,
that's
the
polynomial
that
has
zeros
exactly
at
the
point:
0
1,
2
and
so
on.
This
is
a
polynomial
of
rather
high
degree,
especially
for
the
verifier,
but
it
has
a
very
simple
structure:
ok,
the
prover
now
computes
the
polynomials
int.
A
These
are
gigantic
beasts
and
we
do
not
want
to
send
them
to
the
verifier
she
computes
a
by
basically
running
the
computation
and
looking
at
the
values
of
the
registers
running
polynomial,
interpolation
and
yeah.
That's
how
she
gets
a
and
then
D
is
obtained
by
evaluating
this
expression
here
and
dividing
it
by
Z,
using
polynomial
division
or
yeah,
something
like
it
was
fast
Fourier
transform.
There
are
quite
efficient
algorithms
to
that,
and
now.
A
The
proof
actually
wants
to
send
the
full
a
and
the
full
D
to
the
verifier,
but
that
is
way
too
long.
So
we
do
something
that
is
almost
like
sending
the
full
thing
to
the
verifier,
and
it's
that
this
is
creating
a
miracle
tree
of
all
these
8,000
or
yeah
of
all
these
values
and
sending
the
Merkel
route
to
the
verify
yeah
I.
A
Actually,
we
have
to
evaluate
a
and
T
not
only
on
these
8,000
points,
but
actually
on
way
more
and
the
reason
for
that
is
if
we
compare
polynomials
by
evaluating
them
at
some
points,
and
these
these
points
can
only
be
points
can
only
be
from
this
set
of
8,000
points,
then
they
will
always
match.
So
we
have
to
evaluate
the
polynomials
on
way
more
points.
A
A
Okay
polynomials
of
degree
8,000
that
are
different,
can
still
be
equal
at
8,000
points.
Because
of
that
we
need
way
more
than
a
thousand
points
to
get
the
right
probability.
So
if
the
verifier
is
unlucky,
she
might
hit
one
of
these
points
where
the
different
polynomials
are
actually
equal.
And
but
if
there
are
1
million
points
to
choose
from
and
only
8,000
are
unlucky,
then
the
probability
is
rather
low.
So
we
probably
want
to
ramp
that
up
to
10
million.
A
A
A
Okay
and
then
the
next
step
is
the
prove,
of
course,
provides
these
values
again.
Don't
remove
this
minus
1
here
and
she
provides
his
valid
together
with
a
Mercker
proof
inside
the
Merkel
tree,
where
the
the
root
of
which
she
sent
earlier
and
the
verify
of
course,
checks
the
the
Merkur
proofs
and
also
checks
that
yeah.
Basically,
this
equation
adds
up
when
you're
in
when
you
insert
the
values
that
the
prover
just
provided.
A
A
A
So
it's
it's
just
I
mean
the
the
verify
code
also
just
sent
this
X
Prime
and
then
check
that
the
prover
computed
these
things
correctly
so,
and
it
is
also
important
that
this
random
number
is
public,
so
the
the
variant
the
prover
can
have
access
to
the
random
number,
because
the
prover
pre-committed
to
the
root
of
the
marquetry.
So
and
if
the
proof
of
first
commits
the
root
of
remote
country
and
then
gets
the
randomness,
then
she
cannot
modify
the
mo
country
anymore
and
the
way
you
remove
both
interaction
remembers.
Now.
Is
you
so?
A
If
it's
not
interactive,
then
this
means
the
prove.
It
just
generates.
A
single
string,
a
single
message,
and
then
this
is
verified
once
on
the
blockchain,
for
example-
and
this
means
this
message
is
basically
everything
to
send
to
the
proof
as
to
the
verifier,
so
the
the
roots
of
the
milky
trees
and
then
to
get
randomness.
You
basically
just
evaluate
a
hash
function
on
these
two
routes
and
take
the
randomness
from
there,
because
this
is
the
same
thing.
A
D
A
A
A
Yeah,
it
might
be
that
you
need
to
assume
stronger
hash
functions,
but
usually
this
is
what
should
suffice
and
just
there
was
another
question.
But
let
me
just
finish
now:
we
have
this
random
number
and
then
the
the
prove
I
can
just
use
that
random
number
and
continue
and
provide
that
stuff
and
then
perform
this
check
and
now
the
verify
which
and
then
this
proof
is
complete.
We
sell
it.
The
blockchain
and
the
blockchain
just
reruns
the
steps
of
the
verifier
and
that's
how
we
remove
both
into
action
runs
questions.
A
C
C
C
E
A
F
A
Otherwise,
the
prover
can
just
I
mean
the
proof
of
computes
this
a
and
creates
a
miracle
tree
of
the
values,
and
these
values
can
just
be
anything
they
doesn't.
They
don't
have
to
be
so
just
just
from
the
Merkel
root.
You
don't
really
see
whether
the
values
are
the
values
of
a
polynomial
and
if
they
are
not
the
values
of
a
polynomial,
we
lose
this
property.
That
two
different
functions
are
different
at
almost
all
points.
A
The
I
OPP
will
solve
that
and
yeah
the
as
I
already
said.
The
proof
I
can
cheat
unless
a
and
T
are
polynomials
of
low
degree
and
low
degree
in
this
case
is
8000
and
the
interactive
Oracle
proof
of
proximity
will
help
us.
I
will
actually
give
a
very
simplified
presentation
of
I
OPP,
especially
we
will
just
ignore
the
proximity
part
in
our
simplified
version.
We
have
a
Merkle
tree
of
the
values
of
a
function,
and
you
want
to
prove
that
this
function
is
a
polynomial
of
degree.
A
At
most
e
we
actually
don't
care
which
polynomial
and
that's
also
important,
that
the
prover
doesn't
have
to
prove
that
this
is
it
that
this
a
is
a
certain
polynomial.
You
just
need
to
prove
that
is
some
polynomial,
and
if
we
do
it
properly,
then
we
are
so
we
add.
If
we
add
this
proximity
thing,
then
we
actually
show
that
it's
either
a
polynomial
of
degree
at
most
D
or
it's.
A
Far
away
from
all
polynomials
of
degree,
D
and
far
away
here
means
it
differs
at
many
points
at
many
values,
but
that's
a
little
bit
more
complicated.
So
we'll
do
the
simplified
thing,
the
main
idea,
so
we
will
also.
This
will
also
be
an
interactive
protocol
because
inside
an
entire
interactive
protocol
we
can
invoke
another
interactive
protocol
as
subroutine,
and
the
main
idea
is
divided
conquer
here.
So
we
what
we
do
is
so
we
assume,
of
course,
that
F
is
a
polynomial,
so
it
has.
A
We
take
these
powers
of
K
and
regroup
them
into
art
and
even
once
in
the
following
way,
so
we
have
our
polynomial
f
of
X
and
we
state
that
it's
equal
to
G
of
X
square.
These
are
the
even
coefficients
plus
X
time
H
of
X
square.
These
are
the
odd
coefficients
and
then
G
and
H
are
again
polynomials,
but
the
degree
is
D
1/2.
Now
it's
d
1/2,
because
the
input
is
already
x,
squared.
A
So
we
just
move
all
even
coefficients
to
the
left
group
them
and
interpret
them
as
expressions
in
X
square
instead
of
X
and
move
all
or
to
the
right
factor
out.
1,
X
and
also
important
interpret
them
as
coefficients
in
X
square
and
what
is
also
important
that
the
domain
size
so
that
the
domain
is
always
a
finite
field,
and
this
is
also
1/2,
because
we
only
have
squares
here.
A
Ok
and
now.
What
we
do
is
again.
The
prover
commits
to
a
marquetry
of
all
values
of
G
and
H,
and
the
verifier
requests
a
random
check
that
this
equality
actually
holds.
We
already
have
the
proved
already
committed
to
all
values
of
X.
She
does
the
same
for
G
and
H,
and
then
we
just
evaluate
this
equality
at
a
single
point
at
a
single
random
point,
and
so
we
know
that
this
actually
holds
with
high
probability.
A
A
A
A
What
is
your
knowledge
there
have
been,
so
you
can
have
a
different
talk
about
the
whole
concept
of
knowledge.
A
very
simple
explanation
is
that
in
such
an
interactive
protocol,
the
prover
convinces
the
verifier
about
the
fact
that
the
computation
is
true
without
revealing
anything
else
about
the
computation.
So
in
our
specific
example,
the
verifier
never
learns
these
intermediate
values
in
the
computation.
Of
course,
the
verifies
yeah
it's
a
bit
more
to
the,
since
the
verifying
can
actually
compute
these
intermediate
values.
A
This
is
not
really
true
here,
so
the
actual
concepts
a
bit
more
complex
because
you
can
add
hidden
inputs
but
yeah.
Let's
take
a
look
at
pseudocode,
for
example,
there's
an
interactive
protocol
for
Sudoku,
where
I
can
prove
to
you
that
I
know
that
this
pseudo
is
solvable
without
you
actually
learn
learning
the
actual
solution.
I
can
do
it
now,
but
because
I
don't
know
the
solution,
there
is
a
protocol
that
does
that.
So
at
the
end,
you're
convinced
that
it
is
solvable
without
knowing
how
to
solve
it.
A
A
A
It
just
suffice
us
to
show
that
they
are
arbitrary,
polynomials
of
a
certain
maximum
degree,
and
so
if
we
say
that
P
is
the
set
of
all
polynomials
of
degree
at
most
D,
then
the
following
is
true
for
any
polynomial
you
in
P,
so
for
any
polynomial
of
degree
at
most
D
and
any
function
f
F
is
in
P.
If
and
only
if,
F
plus
U
is
in
P.
A
A
Then
you
can
subtract
U
and
this
will
yield
F
and,
of
course,
a
polynomial
with
degree
at
most
D
minus
a
polynomial
with
degree
at
most
D
years,
a
polynomial
with
degree
at
most
e
good,
and
we
use
that
now
to
show
how
we
can
get
an
IO
P
P
with
zero
knowledge
and
yeah.
We
will
almost
show
that
there's
some
tiny
point
that
doesn't
really
work
out
the
prover
chooses.
A
So
we
want
to
show
that
a
is
a
polynomial
with
degree
at
most
D
and
but
what
we
do
is
instead
the
proved
it
uses
randomness
here
and
chooses
a
random
polynomial
with
degree
at
most
D
and
adds
it
to
a
and
then
we
creates
the
mercury
of
values
for
a
plus
U
and
then
both
run
the
IOP
p4a
Prime.
And
the
thing
is
now,
since
you
was
chosen
uniformly
at
random
from
P.
A
A
Alright
again
something
I
forgot,
of
course
the
Provost
still
has
to
convince
the
verifier
that
this
equality
here
holds.
This
is
the
kind
of
small
hole
here
and
the
zero-knowledge
thing,
because
for
that
we
again
have
to
evaluate
them
at
a
random
point,
and
because
of
that,
the
verifier
learns
at
least
a
single
point
of
e.
A
Actually,
the
verify
also
learns
the
root
hash
of
the
values
of
a
but
in
the
full
star
construction.
This.
So
the
reason
why
this
doesn't
matter
in
the
full
star
construction
is
that
it
has
a
property
that
if
you
learn
up
to
T
bits
of
the
proof
for
a
certain
small,
constant
T,
you
learn
nothing
about
the
the
actual
witness,
and
this
is
because
of
that
you
can.
It
actually
is
fine
to
evaluate
this
at
one
point.
This
will
not
yield
anything
about
the
actual
thing.
The
proof
is
about.
A
Actually,
it's
the
opposite,
so
snarks
are
already
possible
in
the
theorem,
because
we
have
these
pre
compiles
and
also
because
the
proofs
are
only
800
and
188
bytes,
which
is
which
fits
easily
into
transaction
and
for
starts.
We
have
proofs
of
size,
I,
don't
know
five
hundred
kilobytes,
which
is
way
too
large
for
a
transaction,
so
I
could
think
of
a
specialist
blockchain
that
only
has
Starks
where
500
bytes
is
not
that
large,
because
we
have
1
megabyte
blocks
in
Bitcoin,
but
I,
don't
think
it's
practical
for
if
you
at
the
current
point
in
time.
A
E
A
What
else
did
I
say?
Yeah
yeah,
quantum
resistant,
transparent
I
mean
that
means
no
trusted
set
up
and
that's
about
it
yeah
and
they
also
they.
They
don't
make
any
unproven
assumptions.
So
I
mean
crypto.
Sanctions
does
not
only
mean
not
quantum
resistant,
but
I
mean
snarks,
assume
this
knowledge
of
exponent
thingy,
which
might
just
turn
out
to
be
not
true.
A
A
A
It's
not,
as
so
snarks
for
snarks
usually
have
to
create
arithmetic
circuits
and
then
compile
them
and
for
starks
they
start
with
register
machines,
so
they
actually
use
computation
traces,
and
the
paper
says
that
it
is
better
to
run
on
register
machines
then
create
our
thematic
circuits,
because
when
you
start
with
automatic
circuits,
you
end
up
with
polynomials
of
degree
two,
and
this
is
important
for
snarks,
because
they
can
only
handle
polynomials
of
degree.
Two,
but
starks
can
handle
polynomials
with
higher
degree.
B
A
Not
really
up
to
date,
but
I
doubt
that
they
can
handle
50
cubits
right.
So
there
might
so
there's
so
in
popular
articles,
they
usually
say
quite
a
computer's
part,
but
actually
there
are
two
vastly
different
types
of
frontal
computers
and
one
of
them
is
adiabatic
quantum
computers
and
they
kind
of
break
discrete
logarithm.
A
They
can
just
do
some
optimization
problems,
probably
quite
fast,
but
actually
there's
not
a
lowering
of
theory
about
that
and
I
think
they
always
have
40
or
50
cubits
and
the
others
I
think
might
have
10
or
something
like
that,
and
so
the
number
of
qubits
you
need
is
basically
the
key
size.
If
you
have
a
full
quantum
computer
with
a
key
size
up
to
your
private
key,
then
you
can
recover
that
just
from
a
popular
public
key,
whether
you
can
switch
from
snarks
to
Starks
I
mean
they
are
fundamentally
different
things.
A
But
if
you
build
your
system
flexible
enough,
then
of
course
you
can
switch.
I
mean
yeah
and
I
mean.
If
you
start
with
the
system
like
etherium,
then
you
can
have
smart
contracts
and
I
kind
of
both
at
the
same
time,
if
Starks,
if
either
the
EVM
is
performed
enough
to
implement,
Starks
or
Starks,
are
improved
as
much
as
such
that
they
are
can
be
run
on
the
VM.