►
From YouTube: A Hybrid VDF Prover - Benjamin Wesolowski
A
So
the
input
of
your
VD
F
would
be
an
element
G
from
the
group
and
then
you
have
to
square
it
T
times
until
you
obtain
the
final
element
G
to
the
power
2
to
the
power
T,
which
is
the
output
of
your
VD
F.
So
you
could
just
pick
that
I've
as
your
VD
f.
But
then
the
problem
is:
can
you
efficiently
verify
that
the
output
has
been
computed
correctly
so
say,
you're,
given
a
pair
G
and
H?
That
Alice
claims
is
the
out
is
H.
A
A
So
here's
the
primal
trying
to
solve
Alice
wants
to
prove
that
H
is
the
correct
output
and
other
way
is
going
to
be
done.
Is
thanks
to
some
auxiliary
proof,
so
Alice
when
she's
evaluating
the
vdf,
not
only
she's
exponentiating
g
ET
times
to
obtain
h,
she's
also
computing,
some
kind
of
proof
which
is
a
helper
for
everyone
else
to
verify
that
the
computation
has
been
done
improperly.
A
We
will
call
this
by
the
proof
and
now,
given
the
triple
G
H
and
by
anyone
can
efficiently
verify
that
H
is
G
to
the
power
2
Authority,
so
to
mostly
two
methods
have
been
proposed
to
provide
efficient
proofs
of
the
statement,
one
which
will
call
the
Vasilevsky
prover
provides
very
small
proof
spy.
So
the
proof
is
essentially
one
element
from
the
group
G
and
the
verification
is
very
efficient.
It's
going
to
be
too
small
explanations
in
the
group.
A
That's
computing!
The
proof
by
we'll
take
a
little
bit
of
time.
It's
going
to
add
some
overhead
to
the
whole
video
computation.
So
it's
not
going
to
be
as
long
as
the
vdf
computation
itself,
so
you're
going
to
have
to
do
t
sequential
squarings
to
compute
your
VD,
f
and
then
you're
going
to
have
a
little
bit
of
extra
work,
which
will
be
around
maybe
10%
of
the
time
it
took
you
to
evaluate
the
video.
Then
person
can
be
a
lot.
Maybe
reduce
that.
A
So
a
second
construction
proposed
by
AP
attract
proposes
proofs
that
are
longer
around
40
times
longer
for
reasonable
parameters,
and
the
verification
is
also
slower
by
the
same
order
of
magnitude
but
computing.
The
proof
by
is
extremely
efficient.
It
adds
pretty
much
no
overhead.
So
you
do
your
vdf
computation,
you
do
your
t
squarings
and
then
the
proof
comes
pretty
much
for
free
with
a
negligible
cost.
A
So
for
generating
the
Paycheck
proof
efficiently,
you're
going
to
need
square
root
of
T,
around
square
root
of
t
memory
and
for
the
velocity
proof
it's
more
tricky.
It
depends
on
how
fast
how
optimal
you
want.
Your
prove
it
to
be.
You
can
get
pretty
close
to
the
best
speed
apasa
with
square
root
of
T
group
elements.
A
Ya-Ya-Ya-Ya-Ya,
it's
a
square
root,
T
pre,
computed
values,
so
values
that
you've
encountered
during
the
computation
I'm
going
to
say
a
bit
more
on
this.
When
we
go
into
the
technical
details,
so
your
question,
a
natural
question
is:
can
we
gates?
Can
we
get
somehow
the
best
of
both
worlds?
Can
we
combine
these
constructions
in
the
way
that
we
get
small
proofs,
efficient
verification,
but
also
computing?
The
proof
is
fast.
A
For
do
you
simplify
the
presentation
I'm
going
to
present
everything
in
an
interactive
approach.
So
originally
we
say
we
have
Alice
that
wants
to
evaluate
the
vdf
and
convince
the
rest
of
the
world
in
an
interactive
setting.
She
just
wants
to
convince
a
verifier
Bob
and
they
are
allowed
to
interact.
A
So
first
the
vessel
of
ski
prover
so
presented
in
this
interactive
setting.
So
it's
a
discussion
between
Alice
and
Bob
Alice
claims
that
this
pair
G
H
satisfies
H
equals
the
correct
output
of
the
vdf
and
now
there's
going
to
be
an
exchange
between
Alice
and
Bob.
Alice
tries
to
convince
Bob.
That
is
correct.
So
it's
going
to
be
a
challenge
response
exchange.
The
challenge
will
be
random,
rather
large.
Prime
number
L
large
means
not
as
large
as
RSA
parameters,
but
something
like
100
bits
or
200
bits.
A
So
Bob
sends
this
random
prime
number
to
Alice.
Now
alice
is
going
to
compute
the
Euclidean
division
of
2
to
the
power
T
by
this
random
prime
L.
So
you
get
the
2
to
the
power.
T
is
the
quotient
Q
times
the
random
prime
L,
plus
some
remainder
and
Alice
sends
to
Bob
the
proof
by
which
is
the
element
G
raised
to
the
power
Q.
The
quotient
now
Bob
can
easily
compute
the
remainder
of
this
division
by
L,
which
is
R
and
then
he's
going
to
accept.
A
The
proof
is
this:
equality
is
satisfied,
so
the
proof
Pike,
the
power
L
times-
element
G
to
the
power
the
remainder
equals
H.
So
it's
very
easy
to
see
that
if
everything
went
correctly
and
everything
everyone
did
his
job
honestly,
then
the
Equality
is
satisfied
just
have
to
replace
by
by
G
to
the
Q.
And
then
you
see
that
you
get
g
to
the
power,
the
Q
times,
L
plus
R,
which
is
just
e
to
the
T.
A
So
then
it's
correct
it's
a
little
bit
more
tricky
to
see
that
it
would
be
difficult
for
Alice
to
produce
the
proof
that
satisfies
this
equation.
If
the
initial
statement
is
wrong,
I'm
not
going
to
go
into
the
the
security
reduction,
but
we
can
say
something
like
if
alice
is
capable
of
producing
misleading
proofs
she's
able
to
solve
some
supposedly
difficult
problems
in
groups
of
unknown
order.
A
A
Yeah
yeah
yeah
yeah,
exactly
you
have
to
you,
have
to
repeat
only
once,
because
the
soundness
is
very
low.
It's
very
good,
so
just
to
sum
up
the
construction
in
an
in
non
interactive
fashion.
So
if
Alice
wants
to
evaluate
the
video
phone
in
PG,
first
she's
going
to
compute
H
by
T
sequential
squaring
this
is
the
slow
part
and
then
she's
going
to
have
to
compute
the
proof
and
to
do
so
she's
generating
the
next
prime
of
the
hash
of
everything
she
computed.
A
A
A
So
you
get
a
small
output
only
to
group
elements
and
the
first
verification,
because
you
essentially
have
two
small
exponentiation
x'
in
the
group.
Now
the
big
question
is:
how
can
you
compute
this
proof
efficiently,
because
it's
D
to
the
power
of
Q
and
Q
has
a
pretty
big
bit
length.
It
looks
like
it's
going
to
be
as
expensive
to
compute
PI
as
it
was
to
compute
H.
Now
you
want
to
go
a
little
bit
faster.
So
what
are
the
main
methods
to
compute
PI?
A
So
the
trivial
method
would
be
to
just
do
a
long
division
to
compute
your
equation,
Q
and
then
you
compute
Pi,
which
is
the
Q,
but
this
will
take
essentially
time
and
space
Big
O
of
T,
because
Q
is
of
bigger
of
T
bits.
So
it's
going
to
take
a
while
and
a
lot
of
memory.
So
first
you
have
a
no
memory
variant.
A
So
now
no
memory,
but
still
time,
Big
O
of
T.
Now
you
are
faster
variants
if
you
use
some
pre
computed
values.
So
when
you're
computing
H,
which
is
G
to
the
two
to
the
T,
you
encounter
a
lot
of
powers
of
G
on
the
way
you
encounter
all
the
powers
of
the
form
G
to
the
two
to
the
I,
where
I
is
between
zero
and
T,
as
you
can
store
a
bunch
of
them
and
they
are
going
to
help
you
in
computing,
the
exponentiation
by
Q
much
faster.
A
A
So
our
first
question
is:
can
you
go
faster
and
the
second
can
you
go
wellmaybe
as
fast,
but
with
less
pre
computed
values?
This
is
a
pretty
fun,
pretty
fun
challenge.
If
you
liked
you,
if
you
like
all
kinds
of
tricks
to
do
very
fast
computations
so
now,
the
second,
the
second
prover
is
a
PHX
prover,
still
I'm
going
to
present
it
in
an
interactive
setup.
So
the
idea
behind
the
pH
activist
you
take
a
recursive
approach.
A
We're
going
to
let
Bob
choose
how
to
combine
them,
so
Bob
chooses
a
random
integer
R,
and
then
we
consider
the
two
new
elements:
G
1,
which
is
G
to
the
power
R
times
G
Prime
and
H
1,
which
is
G
prime
to
the
power
R
times
H
and
now.
The
statement
that
ice
is
supposed
to
prove
is
the
linear
combination
of
these
two
statements:
very
recursive
things.
A
You
have
to
store
a
bunch
of
values
and
essentially,
in
the
end,
you
can
see
that
by
storing
square
root
of
T
intermediate
values,
the
whole
proof
can
be
computed
in
square
root
of
T
group
operations.
So
a
square
root
of
T
group
operations,
it's
totally
negligible
next
to
the
Big
O
of
T
cost
of
computing,
the
VD
F.
So
the
proof
comes
almost
for
free,
so
completing
the
proof
is
very
efficient,
but
the
proofs
are
longer
why?
A
Because
each
round
of
the
of
the
of
the
of
the
proof
every
every
recursive
round,
you
increase
the
length
of
the
proof
by
one
group
element.
So
in
the
end
the
proof
consists
in
around
log
of
T
group
elements
so
for
realistic
parameters.
Log
of
T
will
be
around
40
and,
if
you're,
using
an
RSA
group
of
2,000
bits
in
the
end,
you
get
a
proof
that
is
around
10
kilobytes,
which
is
a
bit
a
bit
more
than
what
you
would
like.
A
So
the
hybrid
construction
is
pretty
straightforward.
It's
not
so
difficult
to
figure
out
a
still
same
problem.
Alice
wants
to
prove
the
statement
to
Bob.
They
can
first
do
a
few
rounds
of
the
pH
approver
and
after
K
rounds.
They
end
up
with
proving
a
statement
of
the
form
h
prime
equals
G
prime,
to
the
power
2
to
the
power
T
divided
by
2
to
the
K,
because
it's
round
divides
by
2
the
length
the
statement
you're
trying
to
prove.
A
A
So
that's
the
length
of
the
proof
and
now
how
difficult
is
it
to
compute
it?
So
we
can
neglect
the
cost
of
the
pH
I
crowns
because
they
are
very
efficient
and
if
we
look
only
at
the
cost
of
computing,
the
final
vessel
of
ski
proof,
it
will
be
bigger
of
T,
divided
by
2
to
the
K.
So
you
can
tune
your
parameters
like
it
like
this,
depending
on
how
fast
you
want
to
be,
you
can
go
faster
by
having
longer
proofs.
So
it's
a
trade-off.
A
Now
you
can
use
some
optimizations
using
pre
computed
values
for
the
visit,
Alaska
proof,
and
essentially,
if
the
number
of
rounds
you
consider
it
a
constant,
then
the
cost
of
computing,
the
visible
ski
proof,
is
essentially
bigger
of
this
fraction
there,
when
I
say
it,
K
are
constant.
I
mean
that
in
the
bigger
you
have
some
dependencies
in
K,
the
constants
in
the
bigger.
A
It's
because
do
you
compute
the
visible
skew
proof
say
for
the
statement:
H
equals
G
to
the
T
to
the
T
as
fast
as
possible.
If
you
want
to
use
all
the
optimizations,
you
need
to
use
the
pre
computed
value
of
the
forum
GT
the
tree
to
the
eye,
and
these
are
readily
available.
You
encountered
them
during
your
initial
computation,
but
now,
once
you've
done
a
few
rounds
off
your
checks,
proof
you
don't
have
GNH
anymore.
We
have
H
Prime
and
G
prime,
which
are
new,
so
you
need
to
update
all
your
pre
computed
values.
A
A
Essentially,
the
conversation
that
you
have
to
do
is
something
like
this.
So
this
is
another
challenge.
Try
to
compute
this
as
far
as
possible,
so
you're,
given
K
integers,
are
0
or
1
up
to
RK
minus
1.
These
are
the
random
numbers
that
are
issued
by
Bob
in
the
interaction
and
then
you're
given
2
to
the
power
K
group
elements,
C
zeroes.
A
You
want
to
see
this
type
of
there,
C
2
to
the
power
K
minus
1,
and
then
you
have
to
compute
this
big
product
which
are
a
product
of
it's
the
product
of
all
the
values.
C
n
raised
to
the
power
products
of
our
eyes,
where
you
pick
your
needy
our
eyes
where
the
ice
bits
of
n
is
1.
Now,
if
you
can
compute
this
super
fast,
then
you
can
update
all
your
pre
computed
values
super
fast.
So
this
is
another
challenge
to
you
this
as
fast
as
possible.
A
A
B
A
B
B
A
B
A
A
Yeah,
so
the
question
is:
can
you
like
do
a
velocity
proof
or
say
the
first
half
and
then
a
visible
ski
proof
for
half
of
what
remains
and
then
something
like
this
using
the
fact
that
computing,
the
proof
is
anyway
shorter
than
the
entire
the
whole
computation
I
guess.
This
is
an
approach
that
we
explored.
A
A
A
Yeah,
so
the
question
is
it's
not
Bob's
job
to
generate
a
random
L
because
we're
going
to
use
a
non
interactive
version
anyway.
So
it's
it
will
be
Alice's
job
but
in
any
case
generating
an
enormous
prime
will
be
so
costly.
You
cannot
and
the
verification
becomes
expensive
if
L
is
too
big
because
you
have
an
expression
of
shake
and
exponentiation
by
L
to
do
yeah.