forchain
commented
6 years ago I have recorded the transcript by watching the video as pasted below. If you find anything missing in what noted in ScalingBitcoin, you may reference it. However, there may be some mistakes within, so feel free to ask me or check in the video once entering something hard to understand.
okay okay okay thank you so my name is Yonatan Sompolinsky I'm a PhD student in Hebrew University under the supervision of Aviv Zohar which talked previously and also I'm a co-founder and scientist at DAGlabs which is a commercial effort to implement DAG based protocols and I feel comfortable here to say that we're not doing an ICO ---- it's a regular company okay so this proposal was was prepared together with Yoad Lewenberg my colleague both in Hebrew University and in DAG labs okay so a bit of background about DAG based protocols so the the background to this work is a line of works we've done in the Hebrew University my colleagues again Yoad Lewenberg and Aviv Zohar my supervisor and this idea of block dag is a modification of the layer 1 of a Bitcoin, of blockchain thanks and so it's a generalization of the chain structure of the blockchain and as such okay thanks so it's orthogonal to any layer two solutions so lightning Network and all micropayment channel channels etc so we're scaling up layer 1 you guys are scaling out there two these are complementary solutions and this talk will be a focused on an idea that we develop in the inclusive blockchain paper in 2015 and we kind of revisited these ideas now because we're heading up to to scale up to implement these block DAG protocols so roughly what is a blockchain versus the block DAG so the first difference is that in a chain you maintain a single chain and obviously in a dag you maintain an entire graph of blocks the second a difference would be that in a chain you ignore anything that's off chain any any data that wasn't then appear in the chain whereas in the DAG you use all this information of you you harvest all information from all blocks and the third implication is that in a change in a chain paradigm you try to suppress the throughput so that Forks are rare spontaneous Forks are rare in the system whereas in a block that system Forks are the common phenomena of the system the common development of the system is that many many Forks are created in parallel and as you can imagine this this is essentially a matter of information in a chain paradigm you ignore everything that's off chain in a dag paradigm you use in this entire information and this information can be used for more scalability more security more fairness but the fact that is it can be used to these stuff doesn't mean that every block that protocol uses these stuff so just to drop a name Ethereum a ghost version mostly uses ghost for fairness less for scalability cases just to give an example of a dag based protocol that doesn't use these entire features ok so what's the role to
scaling up layer 1 using Dags the first step would be simply to speed up block creation so instead of one block for 10 minutes as in Bitcoin or one block per 21 seconds as in Ethereum imagine 10 blocks per second 50 blocks per second maybe more so that's step number one and of course the immediate implication is that we have spontaneous forks to the chain many many Forks and so then the second step would be to modify the mining protocol and now instead of every block extending a single chain you want every block referencing these entire blocks all the tips that it sees integrating these Folks into one graph so as you can see you have this massive cool graph this is a DAG directed a static graph so everything seems very simple so far
but we haven't reached yet that final step the third step which is the most crucial one namely extracting a consistent set of transactions from this graph so this graph which contains conflicts many conflicts possibly and we must take this graph and somehow extract from it in order this is the main challenge of a block dag effort and we developed a SPECTRE protocol to address this challenge I actually spoke about SPECTRE two years ago in scaling bitcoin Hong Kong we didn't call it Spectre we call it I think a past future past future something like that so this will not be a talk about SPECTRE and just highlighting that this is the main challenge
in developing unblock
that protocol the consistency rule and
in light of that I want to clear some
misconception that block DAG is not a
solution it's merely a framework above
which one could design good protocols
or bad protocols so you can't just say
I'm using a block dag solution this is
not defined well and consequently not
all block DAGs that are created
equal I already mentioned Ethereum uses
some notion of a dag partially and other
you can design other variants and I like
to think of a DAG versus a chain you
know the chain is like a slow one single
lane road in a small town where's the
DAG is a highway super-powerful
highway and the first implication of
this is that if you don't know what
you're doing you'll you'll have a mess
okay so you have to somehow think very
carefully about what what you do with
your DAG hopefully you arrive at a state
where you have this ordered Highway
everything's clear a large throughput a
good utilization of your DAG and if
you're very lucky or very thoughtful you
can arrive at a protocol which also has
fast confirmation times at least for
some some transactions and this will be
the topic of this talk okay so to wrap
up the the preface of this talk scaling
up blockchain users using DAGs opens up
various challenges so the again the
first one in the main one would be
consistency rule but once you solve that
you have to also address confirmation
times storage how much storage do you
want miners or full notes to to store
and for how long so think of a thousand
transactions per second at least 86
gigabytes per day do we want everyone to
store this forever or not these are kind
of challenges we are addressing fee
structure of fairness
how to maintain the Decentralization etc
etc but in this talk I wanted to focus
on just one challenge and this is how to
utilize the DAG
fully so that the entire throughput or at least we are close to
the entire throughput that the DAG can
supply so I will show now why this is
not a trivial challenge okay so we have
two scenarios for that let's say we have
imagine many blocks per second right but
for simplicity let's say we are two
miners in the system just for a moment
you're a miner one and I am miner two - and we have
four transactions to confirm so I'm
creating my block you're creating your
block and we are unaware of each other's
Block because this is in real time ten
blocks per second there's no time to
coordinate and there's there's two
scenarios here right the first scenario
the less optimistic one is the red
scenario where you selected the TX 1 TX
2 from the mempool I selected the TX 1 TX 2
From the mempool and what happens in this case
is because these transactions are not
conflicting they're just a duplication
of the same transaction then no harm was
done in the sense that these both of
these transactions are
approved by the system by the DAG
however we wasted space okay so two
transactions TX 1 TX 2 took the space of
4 transactions over 2 blocks so this is
just a very simple example and of course
the optimistic scenario or the green
scenario on your left hand side would be
that you somehow selected TX 1 TX 2 and
I somehow selected TX 3 T X 4 and now we
have a good division of the four for
transactions covered a spot of four
transactions in the block DAG and the
main question of our research here is
how do we make sure that we are closer
to the green area than to the red area
namely
let's say yes let's assume we have a
good block DAG protocol that has a good
consistency rule how do we make sure and
under what conditions the dag is
utilized and transactions not merely
duplicated across chains
okay so this is the main research
question and just to have that to the
first proposition of this research is if
you don't do anything if you just let
miners mind greedily or naively the top
transactions that they see in their mem
pool then the DAG gains nothing in
terms of throughput okay so what you see
here is the simulation results just a
simple set up generated by Yoad my
colleague so what you see is the green
curve is the throughput of a DAG under a
naive greedy mining policy where
every miner selects the top transactions
from the mem pool and the yellow curve
represents a chain structure
with the same parameters and you can see
that the chain throughput and the dag
throughput are almost identical so if we
miner evilly transactions into blocks
dag gains us nothing in terms of
throughput it does gain us in terms of
confirmation times but I won't touch it
now and of course these you can see that
these two curves are very far from
optimal we can gain much more by the dag
and has much more capacity if we were
more wise and used more sophisticated
schemes to coordinate between miners
okay so here's the good news
and perhaps the the main thing I want to
message to this main message I want to
convey to you is that miners are
incentivized to some extent to avoid
collisions to avoid transaction
duplication and to contribute unique
transactions and increase the throughput
so this is a natural incentive of miners
to to contribute to the healthiness of
the system and the reason is simple
because if we collide on the same
transaction if you both choose the same
transaction for our blocks then the
split will need to split the fee between
us as you will get half of the
fee or or some other portion I will get
the other portion but we can't pay the
fee twice right so if some user said I'm
willing to pay one milliBitcoin for my
transaction and we both embedded this
Transaction
in our block then only one of us will
get a transaction or maybe we can split
it but but we won't be able to to
extract from the user two milliBitcoin so
there is some incentive system to
coordinate and to avoid collisions so
this is a good news and and now we're
heading to a for a more formal a
treatment of this problem so I hope the
chicken game is a is known to at least
most of you the chicken game is a very
famous game to model conflicts so you
have two parties driving towards each
other and heading on collision and the
first one to swerve and
chicken out is the chicken and the one
to stay right ahead on track is the the
Dare and of course if if if I dare and
you chicken out
then I win vice versa you win but if you
both dare then there's a collision not
good
so the inclusive game in the DAG
transaction selection game is quite
similar there is some difference which I
won't touch on now but it's quite
similar right let's
say we have TX 1 TX 2 in the mem pool
and one of the transaction is is more
expensive tx1 it pays us let's say -
Two millibitcoins and TX2 pays us only 1
MilliBitcoin and now we need to decide
how how to let numbers should be
different I'd say tx1 3 milli Bitcoin
and TX 2 would be 2 milli Bitcoin and that
would be better so if we both the select
Tx 1 the most high paying transaction
then we will collide and we will need to
divide the fee between us but if we both
select TX 2 we need to divide a lower
fee between us
so we have to coordinate some how to
select transaction - for you to select TX 1
I will select TX2 - or vice versa this
will be the optimal setup so in the game
theoretic
terminology you have the table the
Matrix of payment to the
players and every seller corresponds to
one scenario and strategies in this game
this is the important point you have in game
theory pure strategies which is simply
which transaction to select and you have
mixed strategies which is using
randomness to select transactions okay
so in a mixed strategy setup I can toss
a coin and using the result of this coin
I will decide which transactions to
select and this is the well established
fact in game theory that using
randomness we can achieve much better
results for all players ok so what this
practically means is that we are looking
at a set up in a DAG where miners will
randomize over the mempool to select the
transactions for their blocks so whereas
in Bitcoin miners simply selects the top
transaction for its block in advance we
will have a situation where the best
thing for you to do is to randomize over
the mem pool according to some
probability distribution and use this to
maximize your throughput okay so how do
we solve this game this this chicken
Or this inclusive game as common
and game theory there several approaches
economic agendas how to approach a game
so that the the top left scenario is
that adversarial setup where you are a
mining pool and you're paranoid and you
think everyone just wants to sabotage
your your profits everyone just wants
you to - your revenues to drop and in
that scenario you have a safety level
solution which is essentially means I
just want to guarantee myself the best
response against everyone else that
wants to sabotage and lower my profits
okay so this is quite adversarial and it
does not fit the loving Bitcoin
community so we we might consider more
more cooperative setups so the selfish
setup is the more common one
this is a corresponds to the famous Nash
equilibrium model where every party
pursues its own interests but somehow
the invisible hand gain brings us into
equilibrium under which no one gains
from deviating yes so so this is a
common concept there's also a very
interesting equilibrium concept invented
by Robert Oman he's a novelist from the
Hebrew University and this is a
correlated equilibrium so still everyone
is selfish but we have some signal that
enables us some coordination so in terms
of mining you can think of a signal as
the randomness from previous blocks
right so perhaps we can use some randomness from previous blocks to select more
wisely transactions to our mempool this
is a hope when hope for our research and
then there's the most altruistic setup
where everyone is playing just for the
sake of of the healthiness of the system
seriously you can think of it of
bitcoins early days as a set up where
the only concern of everyone was a
maximized social welfare so we had mining pools confirms zero
Fee transactions why just to maximize
social welfare there were less
incentives back then okay so we can
visit several of these idea there won't
be time to revisit all these solutions
but let's let's begin with the maximum
Social Welfare this is the most simplest
and also the most optimistic and sort of
kind atmosphere solution so what's so
what would be the maximum Social Welfare
let's just let's say all the miners are
cooperative they just ask us we don't we
don't know how to coordinate but please
design a mechanism under which the dag
is utilized and we won't collide and we
will increase the throughput to the
maximum so actually the solution in
that's in that case is rather simple and
the construction to the miners will be
just select the transaction unit in
random uniformly
from your mem pool so let's say you have
six transactions or of course you can
have thousands you just toss a fair coin
Between them until some threshold and and you
accept all transactions uniformly I
won't touch to the the threshold is
simply what's the capacity of the DAG
you can't you can't of course
overcome this capacity and it's it's a
very famous and very simple result from
queuing theory that says that that
implies actually that you won't have any
collisions in the system so the buckets
the transactions will be sparse enough
that collisions will be very negligible
so essentially you have
maximally utilized dag so again the
take-home message here is if everyone's
cooperating the best thing the
way to utilize the block dag optimally
is to flecked? transactions uniformly but
of course this is a bit naive and what's
the catch so there are two catches first
of all this is strategically unstable
we're assuming everyone's interested in
maximal social welfare this is not
always the case but moreover there's a
more inherent problem with this approach
and this is and this is that it does not
allow for differential service to urgent
transactions so I can't prioritize
transactions as a user I'm unable to
signal to miners you know I really need
the transactions fast I'm willing to pay
more just put it in there I won't be
able because they would just pick
uniformly from the mempool and I will
wait for for a long time so what you see
here is everyone waits the same time
there are some transactions here and
left-hand side area which are never
approved but but all those that are
approved wait at the same time and you can
think of it in the terms of a highway
where everyone is stuck in the same
traffic okay and you're not sure as a
system designer that that's what you
want to achieve okay you are more
opted to choose a system where there are
Express lanes and express lanes simply
allow us for some people to say I'm
willing to pay more I know there's like
taking more riders but assume there's a
payment for the express lane at least in
some areas so I'm willing to pay more in
order to to get to work fast
etc so that's a more healthy design of
the system and then will you have this
curve that says the larger you pay the
the faster you get inside so this this
is a one thing you want to design a
system according to and there's a nice
trade-off here which is unfortunate or
inevitable I always like Thomas Souls
quote there's no there are no solutions
there are only trade-offs so what's a
trade-off here if you have high
utilization of the dag if you if you
avoid collisions then essentially you
can't serve these Express lanes you
can't have prioritized transactions
because you you have to signal
to miners to back off from these
expensive transactions in order not to
collide so this is a this is on the one
hand on the one end and on the other
extreme if you if you allow for if you
allow for fast confirmation times you
will inevitably suffer from collisions
so what you see here is simply the
function of how long have the number of
collisions of a transaction as a
function of the of the of its waiting
time and you see that only transactions
that allow themselves to wait a long
time the buffer suffer no collisions
whereas transaction that want to be
confirmed fast will be confirmed by
various miners in parallel and will
suffer collisions bomb line shorter
waiting times for transactions or at
least for priority transactions implies
more collisions and less utilization of
the DAG and this is inevitable and me?
to trade off it wisely okay so so with
this
let me go on to describe the Nash the
Nash equilibrium solution so what
happens in real world when we have this
chicken state of affairs
so the the problem here is is
intractable so usually in these kinds of
game Nash equilibrium is computationally
hard to find but the spirit of the Nash
equilibrium would be something in the
form of if I see you cooperating then I
will cooperate but if you are greedy and
you always pick the highest-paying
transactions for your blocks
I will retaliate and I will sabotage you
and I will also be greedy and pick the
highest-paying as transactions until you back
off so I apologize for the militaristic
tone but this is a tit-for-tat known
strategy there's a family of strategy
tit-for-tat
and very interesting to understand how
how mining pools will will behave so
just think of the you know mining pool
as long as it's not anonymous if it's
anonymous then of course this is the
question mark I put here if the mine pool
is somehow hiding its identity then it's
it's much it's we're skeptic about
whether you can you can penalize you can
penalize maybe everyone but this this
becomes really very intractable
to understand what happens but
but in a world where mining pools do not
hide their identity then if a mining
pool really will be greedy then the
community of other at least of other
mining pools will will start sabotaging
this pool by colliding with its
transactions so it's a very interesting
game theoretic framework to think of
this sort of situation and also of
general situation in the world
this chicken dare scenario is not is not
unique to two mining a block DAG
transactions okay so I said it's
intractable to to compute the Nash
equilibrium so we did a more modest we
achieve a more modest goal namely we
computed the Nash equilibrium for the
single shot game we only play once
what will be the Nash equilibria we have
a nice formula I won't go over it now
but the good news is it just may be the
qualitative message of the Nash you can
see here that we pick high paying fees
with high probability so if a user wants
us to to embed his transactions very
fast we he will put a large fee and then
we will use we will all sort of collide
but not not necessarily you can see that
the curve does not reach probability one
so even if I'm paying a high fee no one
will be too greedy to pick it with
height with a certain probability so
this is a good feature of the system and
more good news for you is that Nash
performs quite well meaning the
utilization of the dag under a Nash
equilibrium so even if everyone is
selfish the utilization of the dag is
not bad so not that here means around
72% and this on this graph so 70% of the
dag contains unique content unique
transactions so it's a very surprising
result you could have thought that if
everyone were selfish then you know we
will revert back to the greedy scenario
no you won't be you won't be greedy even
if you're selfish because you want to
randomize over your mempool in order to
avoid collisions very good news but
still maybe we can improve
literalization a bit more another
interesting graph that we
must talk about is sorry the quality of
service levels so as I said the problem
with the maximal social welfare solution
is that you can't prioritize
transactions so what you see here is the
tall gray bars represent the maximum
social welfare strategy so everyone
waits equally the same time in a very
long one and then the blue bars
represent the Nash equilibria where you
approve less transactions so only
transactions with a fee from three here
three milli Bitcoin
the precise numbers do not matter of
course it's just a dummy model but as
you as increased the fee you wait less
we want you want this feature right we
want high paying transactions to pay
less and we have other strategies that
exponential allergy and if you can
discern the yellow bars the very little
ones over there they say if everyone's
greedy then you will only approve a very
small set of transactions from 4.30 etc
this is a good a good illustration of
the problem of the challenge two more
points first of all correlated
equilibrium as I said perhaps with
coordination between miners we can
achieve better utilization than Nash and
the the coordination would be using
previous blocks randomness okay so
instead of tossing a coin with the
natural ability we will do something
more sophisticated and preliminary
result results show that indeed we are
able to utilize the dag a better
but this needs to be more investigated
and last point of a general point about
scaling and incentives so selfish mining
and Bitcoin selfish mining is a known
strategic attack on deviation from the
mining protocol and in Bitcoin this
attack is really sophisticated it's
risky
it only works in a long term after two
weeks at least
and so arguably the reason we didn't see
Selfish mining in Bitcoin turn now or at
least not in non negligible amount is
because playing with your mining node
just to withhold your blocks and risking
losing it all is too risky and miners
won't engage in such a behavior
unfortunately in a dag deviating from
the mining protocol is much more
available to you you just need to select
transactions in a certain way or
withhold your blocks for a few seconds
recall that everything is integrated
into the dag right so if if I'm
withholding your my block
and you created two blocks then I'm not
I'm not discarded forever so it's a very
it's a much more granular decision how
to optimize my mining protocol and the
risks are less for the miner but also
the results the harm to the system is is
marginal relatively marginal so this is
in a pointed point and also lazy selfish
mining so I have a pool that let's say
that it occurs to the mining protocol
whatever it is but it doesn't invest in
communication infrastructure so it has a
low bandwidth deliberately or just by
laziness
it doesn't propagate blocks fast enough
so what's the effect at network
again this pool may may not lose too
much profits and other miners might be
harmed this is a very interesting topic
for us so we're investigating it and to
wrap up when implementing block DAG
protocols incentives really matter so
again in Bitcoin the one block for 10
minutes things are are pretty robust at
least in the mining at least as you stay
in the same chain but in DAG things
are very sensitive and with that I will
end my talk thank you
SkyeOreo
A translation project collaborating with NPC. I finished the first two paragraphs, you may try the rest.
https://github.com/npc-network/translator-website/issues/9
Any questions just follow this thread