hello everyone that's great to see so
many people on our purely mathematical
and cryptographically talk so I try to
rule out as many foreign laws as
possible but so many of them are left
here so this talk is of course
intentionally scientific to show up that
we are doing something serious but there
will be also like important numbers will
be on the very last slides that like
this slide before last
so like number of constraints and this
sort of stuff will be in the very end so
if you are just coming just for that you
can wait so this is a joint work of the
companies I'm involved with every Manta
BDK consulting and also our colleagues
from universities of Britain grads are
now Florence a Christian Sebastian and
Marcus so this kind of work that was
conducted a bit independently and then
later merged and still it's kind of work
in progress we even haven't invented the
proper name for the hash function so
that's okay so you'll probably remember
what the head function is what property
should have the good hash function
should process arbitrary large input
well up to some extent but pretty like
that you get by it should handle it
should be collision resistant meaning
that it should be difficult to find X&Y
difference so that the hashes of them
are identical
well as long as hash function converts
arbitrary large inputs to fixed sized
outputs collisions are unavoidable but
there must be difficult to find per
image resistant means that given Y it
must be difficult to find X so that H of
X is y well hash functions theorem
everything is hedge funds everywhere of
course mainly Shah 303 or ketchup the
hash function designed by Belgian de
Belgian team in lead by Yann diamond in
about ten years ago so sherry is built
is used to build a patricia tree to
construct the wrists out of the public
key and so on and so forth so if it's
not like the best like terms often not
the fastest hash function in the world
but it still can handle up to
like 500 baits per megabytes per second
well to understand why we need a
different hash function I'll go a bit to
the introduction how hash functions are
used in snarks so this is some sort of a
petition a bit of the previous stark
talk well in Bitcoin we sign because
usually I still have to start with
Bitcoin unfortunately because there has
the zeroes proofs apply usually to a
transaction output you take so based
systems so we sign the transaction with
some output and hash function of
production is glued it's in the block
and after some point we spent the out
but by signing the transaction and the
output with the private key that was in
the hash and the crucial point here is
that the hash of the transaction is
referred in clear-text
when you want introduces their knowledge
payment system
this is concealed the hash is concealed
to break up the link between the
original transaction to send and the
direction to spend so when the
transaction is sent it's not only
included in a block but also added to
especially crafted Merkel treaty and
when you want to spend it you prove that
there is you know a transaction age
which is in the miracle treaty that it
has special structure and you know the
private key that is that corresponds to
the public key that is is in this
transaction and here the transaction age
is referred to in zero knowledge and the
most computational expensive part in all
protocols is to prove that the hash is
part of the miracle tree so all the
others parts of the proof are rather
fast they all even with previous the
original Z cache they can be managed
within one second but when you have like
29 or 32 layers in the miracle tree this
becomes difficult to to prove because
their performance of zero-knowledge
proving protocols they
scale linearly or even super linearly
with the number of invocations of a hash
function and it turns out turned out
very quickly that traditional hash
function like regular hash function are
not quite suited for snarks starks or
bulletproof because their circuits they
are optimized for Intel or AMD
processors for modern architecture but
they are not optimized for for the
environment where Starks or snarks
operate in this environments are big
fields so the fields are either prime
fields
meaning that all now all kind of our
state is a vector of integers models and
prime number this prime number is 256
bit or 384-bit depends how afraid you
are of recent discoveries and complexity
estimates this for snarks and
bulletproof and for Starks they are most
helpful filled most better operators and
stent is a binary field but not that big
so it's like to the 32 to the 64 that's
like the easiest to construct
reed-solomon proofs so we can say we can
simplify and say that in snarks a
trusted party just kind of applies a
secret input to the circuit and we can
say that like all intermediate states
are hashed true but still and all of
them are published as a proven key and
then bulletproof Starks this secret
input does not need it so the proven key
is just the circuit itself and for each
proof there to Kunda to present to prove
the creative proof you have to kind of
match your execution your computation
with the proven key so with a circuit or
with the circuit on secretin so you have
to like combine the two traces and
that's why the bigger the circuit is
that longer it takes to construct the
proof and it depends on the circuit size
it also depends on like if it's a break
trace like
can snarks like a starch then and
depends on the width of the size of the
state operates with on the degree if you
permit arbitrary degree so different
parameters are invoked and the foremost
might not be very simple but there
there's still some metric to to optimize
and we know this metrics approximately
for snarks we know such metrics for
bullet proof so no such metrics for
starks so the question is the question
that should have been put
when snarks and tark's were designed so
kind of we cryptographic community bit
missed this question this requirement
that we there is a need in hash
functions that operate in big prime
fields or big binary fields that are
best in certain metrics like circuit
size or degree size products like in
Starks and that there of course secure
because the first two are easy to
construct it's difficult to create a
secure one and fortunately our
cryptographic encryption oolitic
experience allows us to create really
fast hash functions because we know
certain constructions that are
reasonably that certainly fast and that
we have analyzed them with crypto noses
for years for decades and we know like
the methods that could work the methods
that usually do not work and we can
quickly make a hash function that is
secure and that satisfies this
requirements so one the first approach
was mi mc3 years ago and there the ideas
from my MC was pretty simple so in the
core of the mind see there is a
permutation so originally it appears as
a cipher but if you want hash function
decide the key can be a random number
it's okay here so the idea is very
simple so you have you add some constant
then you and you operate in a big field
by default some prime field and then you
raise your result of the power of three
in this field so you Square and then
multiply again then you add the constant
then use then you
put to the power raised to the power of
three then at constant to the power of
three and so on and each time they'd
agree so if you express actually it's
easy to show that typical Cryptologic
attacks are differential linear kernels
don't work here because of algebraic
structure because the state is very wide
but algebraic attacks work and the thing
is we have to make our the degree of the
polynomial that corresponds to this to
the output of the function you have to
make that the polynomial is of high
degree to prevent various sorts of
attacks and the degree increases like
degree multiplies by three each time and
the maximum possible degree is actually
two to the n when n is their width or
the state and we have to execute like a
bit less than n steps to achieve maximum
degree well actually actually a bit more
but this is like the order so that you
understand like if you if you if your
permutation is I know 250 bits wide then
you need kind of at least 100 sounds and
steps to achieve maximum degree okay so
there were also Patterson hash proposals
but we can directly go to our
contributions because the others are not
exact so they're in different paradigm
constructed and kind of not so
interesting for us so our contributions
consist of two parts so the first part
as more generic so it's about it's about
miracle trees and it turns out that we
can do we can handle miracle tree
substantially better than before recall
well this is like three layer miracle
trees vertical tree that handles eight
messages well suppose for simplicity
that the hash function it takes like two
we consider a compression function that
compresses with the ratio two to one and
every message is of the size of the hash
function output and then in this case
you need any layers to hash to the end
messages okay and the thing is the very
nice thing is
you can do better because you can when
you have form when you have two layers
you can process more than four messages
you can take fifth one and then jet
carefully we XOR in several hash
function outputs in three and well you
have two and using that you can for
every like two layers you can process
not four messages about five messages
and that's give you well not so big but
something like 20% in 15-20 percent
increase in performance should give and
this works for every hash function and
collisions are pretty much resistance if
it decreases but collision resistance
remains at the same point so generalize
birth defect also doesn't seem to work
and this construction works for any hash
function even more efficiently if we
have a hash function that takes that can
consume our bit very large input well
with regular hash functions we already
have that like we can we can feed very
big input to sha-3 but it will be yes a
sort of sequential on vacation and here
suppose that our hash function is
tailored to where large input size so
the output size is small but what the
input size is big and we use this large
with to achieve cryptographic security
thing is we can then decrease the number
of layers of course so if for example
you process the ratio is four to one
that you need to twice fewer layers and
what do we need how can we do that so
what's the most optimal way of Parisian
and it turns out that if we want to
process some very wide input with a hash
function then a very secure and
construction is the framework it's a
cold spawns mode of operation and it's
based on permutations very wide
permutation means permutation I mean
that it's transformation is the
invertible transformation that applies
to very wide block here the blur the
permutation is of with like 768 bits or
more thousand bits to thousand bits four
thousand bits we know how such
permutations can be constructed and the
idea of how they operate is very simple
so message is sort not on to the entire
state but all the state but some
so-called capacity bits capacities twice
the security level here if you security
level is 128-bit that capacity should be
206 and the rest risks orcs or sort then
they call permutation Authority called
permutation story called permutation ten
messages consumed and then you output
this with the same rate as you consume
in messages and of course permutation
should be like ideal permutation the
sense that issued this to some extent
and essential from a random permutation
well it's a constant function but you
should understand what this means okay
so the question is how to construct the
permutation so that it will be starts
narcho start friendly okay and the goal
is to come up with with the design that
will be both stark and snark friendly to
some extent because the difference we
know that in snarks we optimize we work
in the prime field in stark we optimize
on we work in binary fields but part on
that our permutation can be built very
similarly the first attempt what if we
modify my MC and replace the power of 3
with an inversion and this is of course
a very tempting step and it's not it's
not actually trivial so when the MC
wasn't was invented the author's tried
this approach and it doesn't work let's
work why because it's actually very
interesting exercise that you can
demonstrate that if that no matter how
many rounds you have if you do in just
the constant addition
between the inversions that the
resultant function would be a rational
function of the input of degree 1 the
thing is you can interpret your state as
a fraction of like a little too linear
one linear over another X plus B over
six plus D and of course when you invert
then the nominator and denominator that
just swaps and when you add the constant
the nominator changes but the degree
doesn't change and unfortunately the
state will be raised in a function of
degree one and collisions are easy
because they're like simple linear
equations or even quadratics but they
can be solved easily so and there isn't
design Jarvis they decided to put some
additional linear transformations after
the inversion but it's yet not unclear
for me if this is secure enough but I
haven't managed to break it yet the
solution that is still obvious to me
because I would like to work with wide
permutation because I would like to
leverage the permutation with to get a
more efficient circuit for a tree
not for one hash function for a tree
because that's the bottleneck and that
is that why wouldn't we use multiple as
boxes and use a very wide permutation
then our function will be very similar
to what we already have for example in a
es or other designs and well let's call
it for example inversion hash and if
this inversion hash the parades as
follows so it's you see like there are
rounds and in this rounds we alternate
nonlinear transformations which are
denoted by s so each s is an inversion
in some field it's not actually
important for the design which filled it
is because many attacks they apply
similarly so of course you substitute as
a parameter the field size and in some
cases the binary for binder filled some
attacks work just a bit differently but
not tremendously different so generally
if your function is
this construction is secure for binary
felt it will be like almost secure with
the prime field unless your primes or
benefit is very small but the
construction is like this so HS is an
inversion in the field and each a is a
fine is enough fine transformation in
this field that's basically a linear
combination of inputs invertible one its
and the another very nice idea is that
for the middle of this construction we
do not need full as box layer because
the degree so the algebraic functions
their algebraic attacks will work with
they they can be kind of mitigated they
can be controlled even when with one s
box in the middle or two but with one is
fine and the parameters of this design
are of course the width of an S box and
I say that this S box can be prime
Filton version for snarks or this can be
binary field inversion for starks
and each by you can take whatever binary
field to one so if you realize that if
you think now that two to two binary
field is good for stark you can use it
if later you realize that for like root
zone on performance you need 128-bit you
can choose a bit different function they
will work fine and then Ellis's analysis
remains well at the most extent so of
course we conducted like mainly my
colleagues conducted a number of
different sorts of attacks on this
design because we already know this
design from like 20 years old just this
s boxes were smaller and apparently
algebraic attacks become the most
effective here but when you are six
ourselves for example to 128-bit
security you don't need many rounds here
so we are talking about like six to
eight rounds four outer rounds with
fullest boxes fourth box layers and I'd
know 5 10 15 middle rounds so the total
number of S boxes is not terribly big
but it's interesting to optimize it it's
interesting to try to expand our
permutation to see how big it should be
to give us the best circuits for trees
and for Starks I think what we have so
in our inversion hash here in the left
column there's width and we can
calculate the formula
Bertie much the same formula that
alabanza son is used has used for
approximating stark approver performance
and the resultant performance
predictable performance is on the
rightmost column and its logarithm of
time formula so this should be read that
if you use sha-256 for a tree of two to
32 elements then and you need 100
because resistance then I your that
proven time should be about to the 32:3
of something if you use Patterson hash
then it should be like to the 22 so you
see like almost thousand times faster
but of course unfortunately in the real
in the real world per for the
performance increase from chapter 56 is
not that big because astrophysicist
circuit is very sparse but still if we
use our inversion hash we can if we use
like default width of 1000 bits we can
still be like four times faster should
be four times faster than Patterson hash
if we if we use and interesting we if we
increase the width then we can do better
and for 1500 bits and to two hundred two
thousand bits we can get best results so
1536 is the best we can get it's like
60% faster than the smaller one so our
current proposal is to use this with how
many like not very big number of rounds
like eight outer rounds and not that big
number of
rounds and the tree will be twice as
smaller for snarks we can estimate the
number of constraints which is also
interesting so suppose that we use 255
bit as boxes if you want to use snarks
on elliptic curves with 255 bit primes
if you want 3384 bit primes then you
should kind of substitute them and it
will be somewhat similar and we can
calculate the number of constraints and
we can compare with paterson hash which
is like 40,000 constraints for the
entire trees and if I counted correctly
and for this sort of hash for the entire
tree if we use if we use 6 s boxes in
parallel and for 127 bit collision
resistance then we should have only 666
constraints well maybe indeed for a fair
comparison we should use bigger prime
but I think the order of fact order will
be the same so I think this is quite
promising
and well of course we advocate some
additions to a VM or whatever will be
used to support natively support the
operations in the field basically for
verifiers because verifiers in stars and
bulletproof they need some parts of the
circuit and some some field operations
should be supported and optional I don't
know if the inter entire permutation
should be as a precompiled contract
maybe it's not necessary but we will see
those depending on whether some checks
against the entire permutation are
performed to the performance in the
contract and if so then indeed a per
compile contract would help so this is
just the beginning just begin that's
kind of the hash function that we
cryptographers can design within a short
time period but I think there can be
designed better or better ones can be
found so we can try
start friendly fields we can work better
with algebraic attacks for example the
corner burger burger business attacks
are sort of an offender explored and
because and as far as they claim to be
the best and in the settings should be
very interesting to apply exist in
Grosvenor best labor a libraries to
attacks and see if the indeed kind of
perform as we expect and it would be
also cool have some to fix some metrics
and have some kind of competition that
like everyone can suggest hash function
that optimize the number of constraints
somewhere and withstands security
attacks up to know 2 to the 128th maybe
designs a miracle tree oriented hashing
they already exist to based hashing but
maybe there can be something more
optimal and also for example maybe
128-bit security is not need that much
maybe if the hash function if the proof
should be like secure for only short
period of time then maybe a lower
security level would be nice for example
64-bit security level I'd know maybe 56
bit security level that's like this than
we have we can have much again more
compact designs and maybe with faster
proofs and since first certifications
thank you very much
[Applause]
we have time for maybe one question so
I'm sure you've heard about the new
designs coming out for the Starks with
Jarvis and Friday although they're
confined to the binary field how would
you describe the relationship between
your work in that hmm
how what how would you describe the
relationship between your work and that
how do you see them
I've just seen them two days ago and
basically their idea is in the am IMC
with only one register to insert a fine
layer and that's not yet clear for me if
this and it withstands algebraic tax
because I have some doubt but I haven't
found an actual attack so maybe maybe
it's indeed secure but I would be very
careful I think that third-party reviews
I needed another round of applause
please
[Applause]
you