I explained what foot proofs are I'm
gonna motivate why we actually need them
and what is the problem that we're
trying to solve so as we all know at the
moment there's a really huge trade off
or it's thought to be there's a huge
trade off between how much
decentralization that your blockchain
system has and how much Unchained
throughput you can get and effectively
the argument goes that the more the
bigger the block size the bigger the
blockchain the more expensive it is to
run a full node and so everyone will
have to run a like client instead and
the problem with like clients is that
they accept blocks that are invalid so
if a block contains invalid transactions
and they will happily accept that block
if the majority of the consensus has
actually sort of gain consensus on that
block so for example if there's a 51%
attack then you could trick a light
client into accepting blocks that
effectively generate money out of tener
or double spend and or break the
protocol rules and so on and so forth
because they effectively a Jew assume
that the majority of the consensus is
honest which is a really bad assumption
though should we should we should try to
eliminate so the big question that we
might want to ask ourselves is how could
we actually make it possible for like
clients to reject these invalid blocks
just like full nodes do because if full
node receives an invalid block they will
reject it so how can we make a light
client do the same thing so that they
two don't have to trust the miners and
they don't have to assume that the
majority of the consensus is honest so
the solution to this is that we could
use fraud and data availability proofs
and this is what I'm going to be
presenting today is based on a paper
that we released last month and this is
a joint work with Albert vary from UCL
and Vitalik from a Syrian research we
also have the link is on the screen and
also we have code as well so the basic
idea of food proofs is effectively that
you have like clients and you have full
nodes and like clients only download
headers and fullness also download the
entire block including the transaction
there and if a full mode detects that
there is some invalid transaction in
that block then they will effectively
send send that likely and a compact
proof that that block contains invalid
transaction and that the size of that
proof should be significantly lower than
the size of that block so the big the
original Bitcoin white paper actually
and briefly mentions a concept like this
called alerts
I wished in a single sentence and the
idea of alerts as Satoshi proposed them
was that a full mode could send a light
client a message to alert them that the
block is invalid and that would cause
the light client to have to redownload
the block and validate that block again
but the problem with is with this is
that as a full node I could just lie to
all the light clients and say all the
blocks are invalid and so effectively
the were in the worst case scenario the
efficiency of the system for lack
clients is no better than downloading
the whole block chain again so it boils
down to running a full mode again so it
doesn't really work also has been some
discussions in the Bitcoin space about
having compact for troops which is what
I just discussed but some of these
earlier proposals they propose a
different fraud proof for every single
way to violate the rules of the protocol
so for example you might have one for
three for double spends one for proof
for utx is no existing and so on and so
forth so what we can do here and what
we're going to do here is simplify
everything so that you only need one for
proof and to understand how this could
work is we have to remind ourselves that
we could generalize the blockchain as a
state-transition system which is what
aetherium actually does so effectively
you have a transition function you have
that takes in as input the state of the
blockchain and some transaction and then
every transaction modifies the state of
the blockchain
in some way and then so between block X
I'm block X plus 1 you have a number of
transactions and they modify the state
in some way and in between those
transactions if you apply those
transactions sequentially you have many
intermediate states as you can see in
the diagram so what happens if there's a
one transaction is included in the in
the block that has an invalid that is
invalid and modifies the state an
invalid way that is illegal or not
allowed so if this is 50 51 percent
attack the minor could do this and
insert this malicious block into the
chain and like clients I'm sorry
malicious transaction into the chain and
light clients would happily accept it so
we need a way to prove we need a way for
full nerves to prove that this has
happened so that so that light clients
can reject the block as well and we need
to do this in a compact way so to do
this we needed some way to commit to the
state of the block chain in the in in
the block headers so at the moment a
theorem uses petrushka Sri to
effectively represent the entire state
of the blockchain in a single route and
you can effectively represent the entire
state of the blockchain as a key value
store ie the accounts in the blockchain
and values but recently and one of the
proposed changes in certain serenity is
to actually change this structure to
something a much simpler structure
called the sparse Merkle tree which is a
much simpler way to actually store the
entire represent the entire state as a
single metal rule and the basic idea of
response memory is that it's basically a
normal map with tree but with an
insanely large number of leaves so if
you want it for example to represent
every single possible sha-256 hash then
the size of your Merkle tree would have
it would have 2 to the power of 256
leaves and you might be asking how is it
even possible to actually compute this
macro tree and actually there's some
neat tricks that you can do such as for
example and if you consider the fact
that most of the leaves in this tree
will be empty
No we'll have a zero or default value
then then you can effectively assume
that the vast majority of the
intermediate nodes in this tree will
have the same value so you don't have to
come you don't have to recompute every
single node in the tree you can just
because you know that the vast majority
of these nodes only contain children
with zero values so effectively it is
pretty much as efficient as a standard
map will be and so if we do this then we
could effectively do this concept called
stateless or clients so and instead of
imagining the blockchain as a state
transit state transition system
imagine the blockchain as a State Route
transition system because if we use this
map called if you use this bus Merkle
tree to represent the state of the
entire blockchain as a single merkel
root and you include this medical route
in every block header which is what a
theorem is doing right now using a
patrasche we then you could also imagine
that there are many intermediate routes
between block X and block X plus one or
the previous and next books and so if
you effectively have this execution
trace between every for every single
transaction in a block and so what you
can do is you can not just include the
final state food in the block header you
can also include the intermediate state
foods in the block header so for example
if you wanted to you could include after
every single transaction you could
include the new state route which is the
newest 80 80 bytes state route or you
could do after every few transactions
it's basically a trade-off between how
big the for proof is and how much extra
unchained there that you that you want
to put in chain so if you want so so
then you could easily generate a full
proof if you have this intermediate
state routes in the blocks effectively
the fourth proof would consist of the
pre state routes of a transaction the
post State Route transaction itself and
also the witnesses of that transaction
then the witnesses of a transaction are
simply all the Merkel proofs of all of
the state keys that a transaction
accesses in the state Merkle tree and
then you will also need the malko proofs
for the transaction itself and the free
and post a tweet so then this is what
effectively what the fourth proof would
look like and so that's all good so now
we have a working unified foolproof
system that only requires one single for
proof rather than many different for
proofs like some of the earlier ideas
were proposing but the problem with this
the biggest problem with this is
something called the data availability
problem and the data availability
problem it effectively says that okay so
what if a miner only distributes the
block headers to the like clients so
like clients or you know the block
headers but what if no one knows the
actual transaction data of the book so
just because in the merkel route for the
transactions doesn't mean you know what
the data behind that my fluid is so if a
miner does this then that means a full
node wouldn't be able to generate afford
proof because they simply would not have
the data for that they would not have
the data to generate that for proof so
so we need a way somehow to guarantee
the data availability or availability of
the data in the blockchain and
Vitalik proposed neat way to do this
called an array using array geocoding
and the the idea of region coding is
that let's suppose that you have some
data that is X pieces long what you can
do is you can blow up that data to two x
pieces long and then if you lose any X
pieces in that data you can recover the
entire data from any of those X pieces
so what that effectively means is that
this no longer becomes a 100% data
availability problem
it only becomes a 50% if they develop a
problem because you can recover 100%
data just from 50% of their so what that
means is that miners if they wanted to
hide a single even a single bit or
single byte in data they will have to
hide at least 50% over there or not
release 50% of that they are so what we
can do with this is we can require
miners to commit to the medical route of
the of this blown up or a coded
version of the blood layer that is
extended to X pieces instead of X pieces
and then clients could use this
construction to have a guarantee that
the data is available and so what I
could do is they could randomly sample
different pieces of that block of the
original block and if we can assume if
we assume that the miner is trying to do
this attack and has hidden 50% of their
then there is a 50% chance in the first
sample that you will end up in a part of
the block that is unavailable and so if
you sample a part of the block that is
unavailable ie you request from network
to give you the part of the block that
is available and you don't receive a
response then you would then you don't
accept that block because because you
think you might because because you
haven't received the response to your
sample and so if you keep doing more
samples you can get a very high
probability guarantee and that the block
is actually available because so there's
an there's there would be a 1 minus 2 to
the power of minus s chance of landing
on an unavailable block if the block is
largely or 50% unavailable so and if you
don't and again if you learned
unavailable block you don't receive a
response and then you don't accept the
block problem with this tied to this is
that it's not a problem with this yet
also the problem of this is in this
slide but just as I noted this is
for this to work you need a sufficient
number of light clients to make enough
samples to be able to reconstruct the
entire data so for example like if you
only have like one client then there's
not enough clients to make enough
samples for 50% to sample 50% of the
blog so then the scheme we didn't work
now there are ways to kind of and also
there are ways to get around this or
well also make it more possible so that
you can't fool the first number of
clients but I'm not gonna mention it in
this talk it will be in the it's in the
full version of the paper and there's
also more analysis and graphs in the
papers that show how many light clients
you need exactly so the problem with the
schema I've described the problem with
the scheme that I've described so far is
that what if the miner actually
incorrectly applies the erasure code so
what if they just insert gibberish in
the extended part of the data right so
then that's not that wouldn't be useful
to anyone because then if you actually
lose 50% of the blog then that gibberish
data is not going to help you to
reconstruct the entire block so if you
wanted to prove to prove this to lack
clients then you would basically have to
give them the entire original data and
then they would have to recompute area
code themselves to check that is correct
and this is going back to square one
because you need the entire block to do
this check so the full proof it could
will be equivalent to the size of the
block itself and that's what we're
trying to avoid in the first place so
the way to fix this is that you could
use a multi-dimensional array geocoding
and the idea of multi-dimensional image
coding is that you have you basically
arranged your block data into a square
so you cut it up into a number of pieces
and the you arrange those pieces in
interior Square and then you apply the
erasure coding one by one on each row
and column of this Square until you can
extend
into a bigger square and so if one of
these rows and columns were incorrectly
extended then the size of the foot proof
would be limited to a single row or
column because only the lifelines would
only have to make these proofs at one or
one row or column is incorrectly
computed to be able to know that the
block is invalid and this is much better
because this has efficiency of a square
root of the block size rather than a
block size and with muscle damage with
this 2d coding scheme so you can so in
the example here I'm using two
dimensional encoding but you could go
higher you could use higher dimensions
if you wanted to although personally I
don't think it's worth it because there
are other trade-offs so with this scheme
you a minor would have to hide 25% of
the data to hide the whole square so
here's a graph showing given a light
client that makes s samples what is the
probability that they will land on an
unavailable part of the block
if the miner has hidden 25% of the
square the height and the higher the
probability than the higher the
probability of a light client detecting
that block is not available so we won't
probably be high and you can see here
that if you do say if he after three
samples the probability is about sixty
percent for 15 samples the probability
is about 99% so so you can get you can
get very high probabilities
just from a reasonable number of samples
so some people might consider that 99
percent is too low it's like if you
wanted 99.99% you would need say samples
but I think nine nine percent is
reasonable because what that would
basically mean is that if you are a
minor and you wanted to do this attack
against someone you would effectively on
average need to mind about 100 blocks in
order to get a chance of mining of
fooling the like lion that you want to
or to block into thinking that block is
available when it's not so that
increases the cost of the attack 100x
which which i think is quite make it
unreasonably expensive yeah we have some
performance measurements I'm not going
to go into details to them because I
want to take questions but everything is
quite efficient so this parameter is I'm
assuming that you have an intermediate
state route after every ten transactions
so the slides of the for proof the state
for proof will be about 14 kilobytes
everything is less than a few kilobytes
basically and the biggest trader of them
is that if you're like client that wants
to have to have a guarantee that the
data's available then you also have to
actually download something called the
access routes we are basically every
single row and column in this in this
square has its own medical route that
you have to download and that does
increase the header by about 10x but you
don't have to do this if you do want the
data availability guarantees you can
still run like superlight clients which
have no guarantees but I think like I
think this is quite reasonable trade-off
and in terms of computation it's all
it's all quite efficient the generating
the state for proof look quite expensive
here but us because my spouse medical
tree implementation is quite inefficient
verifying for proofs verifying sample
responses verifying availability for
proofs or all in Slab many second times
so it's all PI efficient so if we look
at the paper the link is there code is
codes in github we have the code for the
date availability code they read using a
rigid coding also a sparse metallurgy
implementation and go and a prototype
for the full proofs itself thank you
I'll take some questions now
the reason for not adding another
dimension is just simply is just the
right amount that they can the minor
needs to fake so actually if you if you
add more dimensions the minor it makes
it worse from a mystic perspective
because the minor has to hide less but
of the pieces of block block it's like
with the one dimensional scheme you have
to hide 50% with the two dimensional
scheme you only have to hide 25% with a
few dimensional scheme you have to hire
12.5% so that means that that means you
have to sample more slices to get the
same sample more pieces to get the same
guarantee bility of guarantees and also
the other problem with having higher
dimensions is that it dramatically
increases the number of milk routes that
my client has download so I don't really
think it's worth it unless you have
insanely large block size I like incent
insanely large intervals between blocks
yes so this scheme be used in the
context of plasma to force essentially
operating party to essentially like
either they provide the proof or they
get slashed because as far as I'm
concerned this allows somebody just you
cannot know if they so I'm not an expert
on plasma but there was a threat on my
theorem research to ask that question
and a response was from metallic said
that it would be quite reasonable to do
that it's like if you wanted to sorry
yeah we deposit I think would be quite
reasonable to do that and if you wanted
to make the plasma operators evasion
code dead blocks and then make the
clients have to do have to do samples
and maybe you could even actually make
it on the main chain they have that yeah
after some amount of time or some delay
you have the main chain sample some of
the pieces as well for extra security
yeah yeah I think would be quite
reasonable question yes works so so I
just wondering if you change one entry
in the state then how big part of the of
the racial coding data structure will
change so how does do changes like
propagate so how so what happens if you
changed the structure of the state okay
so so our data structures are based on
like three hushing which means we we
just change a few entries but each state
right just changes as a single entry and
the logarithmic number of intermediate
try nodes so how much data will change
in the racial code after each state
right okay so let's go back so this is
version of the transaction there so what
you're asking is if you change a single
transaction how much of the erasure code
would change well first of all I'm not
sure why it would matter because that
would change the medical roots as well
so so I don't think there's a specific
attack he can be from that but it would
actually change it would change a
significant portion it wouldn't change
the entire original code I think at
least yeah it wouldn't change the entire
ridgid code but I would say it would
change a significant portion of it so it
would change at least for example the
entire fourth quadrants of the of the
square
all right doesn't really matter because
that would we also change the medical
roots of the rows and columns
do you write here do you write
hello I was wondering if you guys
explored more succinct ways of
generating about verifying the proof
seems to me that it could allow you to
go to a higher dimensional yeah and have
some blog posts on using things like
proximity to make it possible to verify
that the erasure code was constructed
correctly without having to rely on for
proofs and so this is like something
completely different like this would be
like if you wanted to completely
eliminate four proofs
then you would need a way for like
clients to succeed me verify that the
state transitions in the block were
valid and also successfully verify that
the erasure code was constructed
correctly and there are some ideas that
I had to do that and explore but there
are currently some trade-offs something
be ironed out if I recall correctly and
one of the ideas had the drawback of
potentially requiring medical making
Michael branches a hundred times bigger
in the worst case scenario but it's
definitely something that people are
looking into
excuse me stuff another round of
applause please
you