►
From YouTube: ZK Circuits for Elliptic Curve Operations in Halo2
Description
Visit the https://archive.devcon.org/ to gain access to the entire library of Devcon talks with the ease of filtering, playlists, personalized suggestions, decentralized access on IPFS and more.
https://archive.devcon.org/archive/watch/6/zk-circuits-for-elliptic-curve-operations-in-halo2/index
We present halo2-ecc, a ZK circuit library for elliptic curve operations in halo2. Our library implements multi-scalar multiplication, optimal Ate pairing, and ECDSA verification on curves including BN254 and Secp256k1. We will show benchmarks for these operations as well as applications to recursion and aggregation of halo2 proofs. This is joint work with Jonathan Wang.
Speaker(s): Yi Sun
Skill level: Beginner
Track: ZKPs: Privacy, Identity, Infrastructure, & More
Keywords: zk
Follow us: https://twitter.com/efdevcon, https://twitter.com/ethereum
Learn more about devcon: https://www.devcon.org/
Learn more about ethereum: https://ethereum.org/
Devcon is the Ethereum conference for developers, researchers, thinkers, and makers.
Devcon 6 was held in Bogotá, Colombia on Oct 11 - 14, 2022.
Devcon is organized and presented by the Ethereum Foundation, with the support of our sponsors. To find out more, please visit https://ethereum.foundation/
A
A
Welcome
everyone,
and
thanks
to
Barry
and
yingtong
for
the
great
introductions,
so
today,
I'm
excited
to
tell
you
about
this
elliptic
curve.
Library
we've
been
building
in
Halo
2.,
okay,
so
first
let
me
tell
you
what
the
library
can
do,
so
it's
a
Halo,
2
library
for
doing
various
elliptic
curve
operations.
That,
in
particular,
has
a
configurable
trade-off
between
the
proving
time
and
verifier
cost.
A
So
the
operations
we
can
support
is
that
for
generic
elliptic
curve
you
have
to
put
in
a
few
constants.
We
can
do
addition
doubling
multi-scaler
multiplication
and
then
for
pairing
friendly
curves.
We
can
do
optimal,
eight
pairing
verification
and
we
can
also
do
ecdsa
signature
check.
So
we've
also
put
this
Library
into
the
scroll
and
PSC
aggregation
circuits
for
the
kzg
back
end
of
Halo
2..
A
Okay,
so
before
I
tell
you
more,
let
me
show
you
some
numbers
so
for
ecd
ACS
for
ecdsa
signature
verification.
You
can
see
that
if
we
have
a
small
proof
size
at
the
top,
we
have
a
longer
time
around
10
seconds
a
little
over
and
then,
if
we
increase
the
proof
size
we're
able
to
get
things
down
to
around
three
seconds
on
a
MacBook
Air
weirdly.
We
found
that
on
the
CPU,
the
MacBook
Air
beats
a
fancy
AWS
box
for
a
multi-scaler
multiplication
with
100
base
points.
A
A
Okay,
so
let
me
tell
you
how
we
build
all
of
these
circuits,
so
we
have
a
very
modular
approach,
so
in
Halo,
2
you're
allowed
to
use
a
lot
of
custom
Gates,
but
we're
very
simple
minded.
So
we
use
a
single
custom
gate.
Our
gate
is,
has
four
vertical
cells
and
unfortunately,
I
forgot
to
highlight
them,
but
starting
from
the
top,
our
gate
is
just
a
plus
b
times.
C
equals
d.
A
So
in
this
example
on
the
right,
if
we
want
to
compute
a
DOT
product
of
one
comma
3
with
2
comma
four
we're
first
going
to
apply
a
gate
on
the
top
four
cells,
so
that
will
say
0
plus
1
times
2
equals
two
and
then
we're
going
to
overlap
it
with
a
gate
on
the
bottom
four
cells.
So
that
would
say
that
2
plus
3
times
4
equals
fourteen.
A
So
this
simple
overlap:
optimization
gains
us
about
a
25
gain
for
all
dot
product
operations,
which
turn
out
to
make
up.
Maybe
eighty
percent
of
all
of
the
operations
we
do
so
our
setup
is
that
we
have
a
number
of
advice.
Columns
with
this
custom
get
enabled
we
have
a
single
lookup
table
for
range
checks,
and
then
we
have
a
bunch
of
selector
columns.
A
Okay,
so
we
set
wrote
a
pseudo
layout
or
in
halotube,
which
allows
us
to
configure
where
these
columns
are
placed
in
different
regions.
So,
as
a
configuration
to
our
circuit,
we
allow
a
fixed
number
of
advice
and
fixed
columns
and
we
sort
of
Tetris
these
vertical
concatenations
of
our
basic
gate
into
the
columns.
A
On
top
of
this,
we
built
a
basic
Library
called
Halo
2
base
of
basic
gadgets
like
inner
product
range
check,
indexing
into
an
array,
doing
various
bitwise
operations
and
doing
comparisons
on
top
of
the
skates,
and
that
allows
us
to
almost
completely
abstract
away
the
manual
signing
of
cells
that
you
may
be
familiar
with
if
you've
written
some
Halo
2..
So
on
top
of
that,
we
build
our
elliptic
curve,
Library,
mostly
maybe
95,
only
using
these
abstractions.
A
Finally,
I
wanted
to
mention
one
very
critical,
optimization
that
we
made,
which
is
that
we
previously
enabled
lookup
arguments
on
every
single
column,
and
that
was
crucial
in
doing
our
range
checks.
We
did
one
optimization
to
have
special
columns
whose
only
purpose
is
to
hold
cells
that
are
looked
up
and
we
copy
all
cells.
We
want
to
look
up
to
those
columns.
Although
this
sounds
a
bit
trivial,
it
actually
reduces
the
proving
speed
by
about
the
approving
Time.
A
By
about
50
percent
and
again,
we
can
configure
how
many
of
these
special
lookup
columns
we
need,
depending
on
the
circuit,
okay,
so
just
to
show
some
plots
on
the
results.
If
we're.
If
we
vary
the
number
of
columns,
the
as
the
number
of
columns
grows,
the
proof
size
grows
and,
typically
speaking,
the
proving
speed
will
increase.
So
you
can
see
for
the
optimal
eight
pairing
for
a
single
column.
A
A
All
right,
finally,
I
want
to
tell
you
how
we
plug
this
in
to
the
existing
aggregation
circuits.
So
if
you
have
a
kzg,
backend,
Halo
2
proof,
then
to
recursively
verify
the
proof.
You
need
to
do
two
things.
First,
you
need
to
do
a
bunch
of
multi-scalar
multiplication
on
the
kcg
commitments
that
comprise
the
proof,
so
these
would
be
multi-scalar
multiplications
on
the
BN
254
curve
and,
secondly,
you
need
to
do
a
pairing
check.
A
A
So
to
our
knowledge,
there
are
two
one
is
out
of
PSC
it's,
this
Planck
verifier
repo
and
one
is
out
of
scroll,
which
is
Halo,
2
snark
aggregator.
The
way
that
both
of
these
work
is
that
there
are
various
generic
traits
for
an
elliptic
curve,
library
that
they
use
and
they
sort
of
abstractly
write
on
top
of
these
elliptic
curve
traits
so
very
nicely
that
that
allows
us
to
plug
our
library
into
these
aggregators
simply
by
you,
know,
re-implementing.
A
So
here's
the
results.
So
in
a
setting
where
we
have
seven
advice,
columns
and
eight
fixed
columns
so
of
the
advice,
columns,
six
are
standard
columns
with
this
basic
gate
enabled
and
one
is
a
lookup
column,
we're
able
to
verify
at
the
actual
zkvm
circuits
recursively.
So
we
just
tried
out
the
evm
opcode
circuit
and
then
the
combination
of
the
evm
and
state
opcode
circuit,
and
so
even
on
a
MacBook
Air.
We're
able
to
do
the
recursive
aggregation
of
the
evm
circuit
in
a
little
bit
over.
A
You
know
around
10
minutes
note
that
the
scroll
and
PSC
numbers
are
not
precisely
comparable
because
we
have
slightly
different
versions
of
the
state
circuit
inside.
Unfortunately,
when
we
aggregate
the
evm
and
state
circuit
together,
it
exceeds
the
memory
con
constraints
of
our
MacBook
Air,
but
we'll
try
it
on
the
server
soon
enough.
B
A
If
you
ask
me
for
two
things,
the
first
thing
would
probably
be,
and
this
might
be
very
difficult
to
change
so
Halo
2
has
a
function
called
synthesize
which
constructs
your
circuit,
but
the
design
of
the
library
is
that
synthesize
is
called
multiple
times
with
different
purposes
and
different
interpretations
of
the
input.
So
when
we're
developing,
that's
actually
the
biggest
source
of
bugs,
because
we
sort
of
forget
that
on
one
of
the
times
the
mean
semantic
meaning
of
some
of
the
inputs
is
a
little
bit
different.
B
A
We
really
like
the
configurability
and
that's
why
we're
spending
so
much
time
in
the
Halo
2
ecosystem.
The
way
we
found
initially,
we
found
it
very
difficult
to
manage,
but
the
way
we
found
to
be
productive
in
it
is
to
sort
of
really
restrict
ourselves
as
you've
seen
here
and
then
slowly
add
on
more
complexity,
almost
as
not
really
a
pre-compile's,
not
the
right
word,
but
just
almost
as
a
special
addition
to
our
library
and
then
restrict
ourselves
to
only
work
within
this
sort
of
constrained
universe
of
the
freedom
that
Halo
2
offers.