[Music]
hello uh can you all hear me okay uh I'm
Gabriel and today we're going to be
talking fraud proofs you know like
another session about fraud proofs uh we
will present a new technique uh that
we've just published in fact so it's
been in the oven for quite a while and
I'm quite excited to show it to you all
but the bottom line is that we weren't
quite happy uh on the current set of
fraud proof so we created a new
algorithm uh so first I like to thank
caresia for all the grants provided and
also my co-authors austo who is here on
the audience and Diego uh so thank you
all and also to all the organizers of
this amazing event um yeah so first I
want to get this question out of the way
the Zeki question uh it may feel that
when we're talking about fraud proofs
that we're trying to figure out the best
grass to feed our horses uh and I want
to push back against that notion you
know because there are no silver bullets
you know ZK is not panaca uh when you
compare them with front proofs there's a
sharp contrast in throughput and costs
uh which means that depending on the
application you're going to prefer the
different algorithms you know there
going to be trade-offs in the end
there's no silver bullets that's the
point I wanted to get across so now
let's focus on fraud proofs
yeah the agenda today is that they're
actually quite hard to get I hope you
got that notion from Lucas St uh all the
previous attempts were either unsafe
centralized or slow and Dave is
not yeah so fraud proofs are in a diff
uh difficult position right now so we
have the pressure you know on the top
there's vitalic Suite essentially
calling for stricter standards but if we
look at L2 beat we don't see full pizzas
right so we have the pressure but we
don't have implementations coming and
the reason for that is because it's
actually quite hard to get fraud proofs
right and by right I mean essentially
three properties the first who are there
um I want you to be able to become a
validator I want you to be able to go
there without a supercomputer without
huge ons and be able to participate in
the consensus in the protocol and the
second property is that I want that you
be able to defeat anyone by yourself
even if you're facing against a nation
state so if you get those two properties
to defend an optimistic roll up all you
have to do is set up a note on your own
infrastructure you don't need to
delegate trust to anybody else we
inherit the security of the base layer
uh so those are like the two like uh
oneof end property and we want it to be
decentralized uh and the next one is
that we want settlement to happen
without large delays we want settlement
to happen quickly so let me run
all the three of them together uh they
kind of look like this you know
decentralization I want you to be able
to participate without a supercomputer
or huge bonds there is security which
means that tvl cannot be stolen even if
you're facing against this nation state
uh and liess no large delays and you
might be getting some flashbacks you
know like some PTSD like oh no do we
have another trma and yeah kind of you
know it's actually quite hard to get the
three of them at the same time uh and
you can always naively go from one
vertex to the other um but you sacrifice
one to gain the other you know so you
can take this straight off so it does
look like a a real
trma and the reason for that is Cil
attacks uh I will zoom in on only the
first one which is resource exhaustion
attacks it's like a Spam attack where
you create like a huge number of sibbles
and you just drain the funds of the Hest
validator until they can no longer
participate in the game and then you can
steal the tvl uh so this is a Cil attack
that targets the security of the
algorithm and there are mitigation um
strategies but they end up restricting
participation and thus harming
decentralization uh so there are three
main uh solutions that we will talk
today there are several others but we'll
talk about these two the first two is by
optimism optimism fault proof uh there's
also arbitrum bold and our own
permissionless referee tournaments PRT
for short this is the previous algorithm
we did that was our first attempt at
cracking this uh and I want to highlight
the very important fact that the top two
you know the first two uh if you look at
the tvl Distribution on L2 beat pretty
much most of it is being protected by
those first two you know it's either an
OP chain or an arbitrum chain so we need
to keep this in mind because we need to
take the analysis of these algorithms
quite seriously uh so this is the sneak
peek comparison between you know those
three and the one we're going to present
today and the columns they map directly
to those three properties so for example
bonds uh if you look at bold you need
3,600 eth to become a validator so it's
a very high Bond uh value and this has a
centralization effect so the bond colum
is related to centralization
decentralization now expenses oh just to
you know highlight this uh this is a 1
million ether attack scenario so we
assume that the adversary is willing to
burn that amount of money uh in that
case uh if it's a op uh fault proof the
defender has to match those funds so if
you don't have also 1 million ether you
will lose the tvl so that colume
expenses maps to security and finally we
have delay uh if you look at our own if
there's this 1 million ether attack
civil attack
um you get 20 weeks delay which is also
quite high so you know none of the three
we feel are quite adequate
and today we will present Dave which is
on the bottom which strikes a good
balance across all three of
them cool so let's talk about some basic
concepts of fraud
proofs uh okay so first our threat model
uh we assume that the layer one works
however we also assume that it can be
censored for up to one week so think
like a censorship budget that the
adversary has and they can spend it at
will and we also assume there is one ons
validator which we're going to say it's
Willie And Willie has a laptop a few
ether and values uh hard
values so we begin with the basic
primitive which is a pairwise reputation
so the goal is that well you have uh two
players we have Willie the
adversary and the blockchain acting as a
referee in the middle and those two will
engage in a dispute to prove that the
other is wrong uh and they want to in
the end the the goal is to prove the
result of a program to the referee and
it's interesting because they don't
prove the correct result directly they
prove that the other is incorrect and
since we assume will is there he's the
one who's going to enforce the right
result because he's the honest one you
know uh yeah so they're going to fight
to prove the correct result of a program
now what do we mean by
program the computation model has an
initial State and a state transition
function agreed by everyone and then we
apply the state transition function over
and over the initial State until we get
the final State and that final state is
the result of the program that's what we
are trying to prove to the blockchain
and the intuition of a reputation game
is that first we're going to perform a
binary search on this computation and
try to pinpoint the exact State
transition that they first disagreed on
because if they agree before and
disagree after somewhere in the middle
they start started disagreeing and we
want to pinpoint exactly that and once
you find that Divergence you can execute
a single state transition function you
know the refere the blockchain and
figure out who's lying and eliminate
this liar uh so this is the basic
intuition but we're going to make a
slight change to this uh so instead of
committing just to the final state which
is really what we're interested about we
are going instead to make a commitment
on the whole history of the computation
so we have all these transient States
and we're going to commit to that so
it's like a Merk tree where the leaves
are all the transient States we meriz
that we get the claim so we turn the
dispute not just on the final state but
also on the history and this change is
important because we remove the
possibility of false flag attacks which
are quite annoying you know so we can
join a s claims that are the same
together on the same team and this
enables a whole bunch of algorithms
including PRT because we introduce this
technique on PRT and and Dave which
we're going to present
today now the
final piece to get all like The
Primitives is deadlines because it's an
interactive protocol so players acting
turns uh and if they refuse to act we
need to do something so we need to set
deadlines to eliminate players who are
not
cooperating but remember we have the
onewe censorship in our threat model so
naively we would have to set a one week
for each interaction which would kill
the liveness of any
protocol so what we instead do this is a
technique that many protocols use is
something like a chess clock so this
allows you to amortize this one week
across many interactions instead of
having to pay it for every single
interaction so you turn from like the
sday multiplying each interaction for it
to being like an additive uh part of the
expression and then you only need to pay
for each interaction the real time of
that interaction in the absence of
censorship because an interaction is
quite fast you know it's like 5 minutes
uh and we don't want to play pay on top
of that five minutes seven days so we
use the chess clock to amortize
that now let's generalize this this is a
pawise reputation first now let's do a
multiparty
reputation and there are two high level
approaches one is the parallel approach
which is more like what bold uses
uh and the good part of it is that it
finishes fast so we have Willie engaging
every other claim in parallel at the
same time but the problem is that we
incurred a chance of overwhelming Willie
right so imagine that instead of only
five we had like one million sibl would
have Willie trying to fight everybody at
the same time and he could get
overwhelmed and lose and lose a tvl so
we have this you know oh it's fast but
it might overwhelm Willie
and we can mitigate that by increasing
bonds but then we start centralizing the
algorithm uh with PR2 which is our
previous algorithm we went a different
route uh we use this tournament idea
right so we put sybl to fight against
other cbbls so the number of round is
logarithmic the expenses are logarithmic
and the delay is logarithmic so this all
means exponential Advantage willly has
an exponential advantage on delay and
resources but each round takes a week
because of the censorship you know even
amortising the week across a match every
match every round still has to last at
least a week so if we imagine this the
analogous uh of 1 million sibles here
there will be 20 rounds so it will take
20 weeks which is high you know uh but
matches only take two hours in practice
you know in the absence of censorship
they would take two hours but because
there could be censorship we need to add
the week
so we were thinking oh why don't we try
to amortize this one week not only
inside a single round but across the
entire dispute so this is what we'll try
to do so what I present now is an
attempt to accomplish
that okay so the algorithm is called
Dave uh and it's just
Dave it's not an
acronym uh it's based on the D versus
Goliath
archetype uh because anyway um so the
first change we make uh is we change the
tournament to a repage
tournament this is a fancy name just to
mean matches are not eliminatory you
don't eliminate um a claim as soon as it
loses you give it a while you know it
has to lose multiple times before it's
finally eliminated so this is what repes
Char means now don't try to think about
how long this will take forget that
let's just think on the soundness of it
I want on this slide to convince you
that Willie won't lose and he will
defeat everybody let's think about time
later um yeah so imagine that we have
the censorship of one week but we reduce
the rounds the matches to one day so
every one day they rematches everybody
including Willie uh and then they fight
the next day rematches everybody again
and so on when know that Willie can't
lose unless there's censorship but even
if there's censorship we know that
Willie can't lose more than seven times
because the budget is only seven days so
it's like Willie has age hit eight hit
points but the adversary has only seven
bullets so the best the adversary can do
is spend his whole budget and force
Willie to lose seven hit points and then
he's out of budget and now will is very
angry indeed and he going to kill
everybody else
now this may seem a bit abstract so
let's get it more concrete so this is a
different example the previous one was
with eight hit points this one is just
three uh the optimal value is more like
21 you know but it's it's hard to
visualize that so let's go with three
first uh yeah so everybody everybody's
on the same bucket in the beginning
everyone has three HP and the uh white
arrows point to the matchmaking so
Willie is spared against red
and green is spared against gray so red
and green lose so they're demoted then
we rematch again now this time Willie is
against gray red is against Green so
green loses gray loses and he keeps
going like this you know this logic uh
of bearing whoever loses gets demoted uh
and eventually Willie wins you know he
kills
everyone uh but on this example note
that we assume there's no censorship so
will didn't lose any hearts he could
have lost Hearts uh but it's you know it
would take more images to do that so
we're just assuming that you know
there's no censorship for this figure
but there could be uh so Willie could
lose two rounds but not the third
one but we didn't talk about how this
matchmaking is done uh and this is quite
delicate in fact this is at the heart of
Dave the matchmaking we can't do it
randomly we cannot do this uh
adversarially bus
you know it has to be done in a very
specific way which is we need to do
matchmaking by hit point so we want to
match the same hit point with same hit
point or at least as close as possible
so looking back it's the same image you
know we did the correct matchmaking so
on the second round Dave is matched not
Dave Willie Willie is matched against
the gray one he's not matched against
red or green has to be matched with gray
third round is not possible to do a
perfect pairing uh so we do our best and
our best would be either gray or red and
so on so like abstractly it's like as if
we sorted every Claim by hit point
highest to lowest and then we match them
left to
right yeah and when we do that we
actually get exactly what we wanted you
know if it was random uh there will be
no um uh improvements over PRT but if we
do the rematching with similar HP we
actually dilute the set 7 Days across
the whole dispute we get exactly what we
wanted there's some constants there you
know that's why I said proportional it's
not exactly that but the idea is really
we are amortizing seven days across the
whole dispute and we're only playing
paying one day in that 7-Day example you
know that I gave earlier uh times
logarithmic of
sios uh I mean the real values uh is
actually more like 10 hours you know
then there's a constant we go on all of
that with a lot more nuance and
discussions on the paper so we can check
it
out uh yeah so this finishes the
description of Dave so it's a repage
tournament where we do the match making
with similar HP and when we do that we
amortise the seven days across the whole
dispute instead of over a single
round uh so concluding you can be with
you only need a laptop and about a three
e collat room you can defeat anyone
because you have this exponential
Advantage so this means that a rollup
that uses Dave inherits the security of
L1 and for any realistic Cil attacks
it's going to take no more than four
weeks it's going to be within four weeks
and thus Dave triumphed over the sibbles
with a laptop and a small collector but
Dave had no supercomputers on his
hands and we get those results yeah
that's all I had to present to you today
thank you very much for coming
[Applause]
great talk uh love the name Dave um
thank you it's got a few few Q&A
questions you can still add some of the
questions um while we're going through
some of these and up vote them uh but
the first question is is a one that I've
been thinking too um what if there's
multiple Willies defending won't they
eliminate each other yeah so that's a
good question uh when we did the
computation hash which is that
commitment it means that everybody
that's honest is going to be on the same
team so if there are many Willies they
will fight together against the sibl not
against each other because the claim the
same thing so we have this uniqueness of
claims when we do the computation hash
and we allow all the honest validators
to join teams so we consider this single
ton hero know it's just Willie but in
practice there going to be many Willies
and they all fight together pushing in
the same
direction cool uh next question is about
your censorship model is your censorship
model hard censorship and do inclusion
lists improve these things yeah so the
inclusion lists I don't think they help
exactly on that uh so the censorship
model you know luk um gave a very good
uh intuition of it is that 7 days is the
time we can try to organize a hard Fork
so Suppose there is hard censorship my
transactions are not getting to the
blockchain so what's going to happen is
that you know Twitter's going to catch
on fire I'm going to scream to everybody
look I'm being sensored for already 4
days is everybody's going to get uh you
know iffy about this and we are going to
together
organize uh like a hard work or
something to fix this so the point is
not that there can't be a 7-Day
censorship it is that if there is a
seven week censorship the Ean Community
will together realize and say that this
is a problem and then hard Fork away and
if we put like a one- day censorship I
would convince nobody seven days it's
the threshold that we consider to be
easy to
convince cool uh the next question what
happens to levels in the current PRT uh
will your plans be to eliminate it with
ZK yeah exactly so PRT uh if you look at
our current implementation we are doing
it with three levels uh we think with
some really good engineering effort we
can do it in two uh we want to do it in
one using ZK exactly that and this is a
prerequisite of Dave so Dave already
assumes that we manage to reduce this to
one
level cool so what happens if you mix
algorithms together would that increase
security do you see it working yeah so
uh there are two ways to mix algorithms
uh one of them is to improve liveness
actually so
PRT finishes faster if there are very
few number of sybl so what we could do
is launch PRT in parallel with Dave if
there are no like very few sibl PRT
finishes first if there are a lot of
sibl they finishes first so then we take
whoever answers first so this is an
approach to improve on liveness now to
improve on security we can also mix them
with the goal of uh you know reducing
the risk of bug so we could have like a
a Consortium like a quorum of four
members one member could be PRT but
permissioned so permissioned PRT has no
problems of liveness so we could have
that one of the members in the Forum
then we could have Dave as another
member in the Forum then we could have I
don't know a te or a quarum of T and
then we could have a a multisig you know
so if we have this Quorum of like
many um you know it it would take a lot
of effort to try to corrupt all of them
at the same time so we reduce the risk
uh by reducing you know the chance of
there being a bug so that's how you
could mix
protocols cool so um what if the goal is
not to disrupt the chain but just to
delay the chain yeah how large would the
cost be if the attack presuming the only
goal is to delay by four weeks so if you
want to delay by four weeks I think you
need more than10 billion or something
you know we have to burn the GDP of
Japan it's crazy you know we sometimes
lose sight of like exponential or
logarithmic uh so really if you burn
like trillions you can't even fit that
on the blockchain then you you couldn't
really push pass like this four or five
weeks uh the next one ASM totically is
um is it still logarith Matic delay
right yeah exactly what we did is we
reduced the constant multiplying it by
about one order of
magnitude okay um you have multiple
Willies that are good but then I decide
to go bad they can't because um they
when they do a bisection they need to
provide the merco proof and the proof
w't won't just match yeah will just not
match cool all right everyone clap your
hands for Gabriel and thank him for his
time he spent
on the next session will be at 11:30