►
From YouTube: NEAR Lunch and Learn Ep. 07: Nightshade: Finality Gadget
Description
In this episode, Alexander Skidanov gives an overview of the Finality Gadget, safety proof and implementation details.
~~~ABOUT Lunch and Learns~~~
This is a new series of videos exploring a concept on the NEAR protocol blockchain discussed in the NEAR office at lunch. Grab a sandwich and settle in!
Follow the latest from NEAR Protocol on,
Website: https://nearprotocol.com/
Discord: https://near.ai/discord
Medium: https://near.ai/medium
Twitter: https://near.ai/twitter
GitHub: https://near.ai/github
A
So
the
way
the
schedule
on
which
blocks
are
produced
is
quite
our
toggle
onto
the
finality
gadget.
So
is
different.
The
four-cheese
rule
specifically
for
the
Casper
nmg.
It
is
important
that
every
block
has
an
Associated
weight,
so
the
concept
of
a
weight
is
external
to
the
finality
gadget.
It
could
be
amount
of
proof-of-work.
It
could
be
something
a
little
to
prefer
stake,
but
it
should
be.
Some
integer
does
have
to
be
integer,
but
it
should
be
some
some
number
which
increases
with
every
block
cool.
A
We
will
define
another
property
of
a
block,
so
we
already
defined
the
weight
of
a
block,
or
rather
we
did
not
define
it.
What
we
said
it's
external
to
the
to
the
phonology
gadget
in
a
second,
we
will
define
another
concept,
called
the
score
of
a
block
which
is
another
integer
associated
with
the
block
which
is
not
decreasing
between
blocks.
So
for
two
approvals
of
a
particular
witness.
A
There
are
two
rules,
rule
number
one.
If
two
approvals
have
the
same
reference
block,
then
the
blocks,
the
parent
blocks
must
be
on
the
same
chain
or
otherwise
it's
a
/hreul
behavior.
So
what
I
just
drew
is
a
slash,
a
slash,
whole
behavior,
because
there
are
two
blocks
to
give
two
parent
blocks
which
are
not
on
the
same
chain
with
the
same
reference
block.
That's
a
slash,
whole
behavior.
You
cannot
do
that,
but,
for
example,
something
like
this
would
have
been
appropriate
for
the
same
for
the
same
witness.
If
the.
A
A
The
score
of
T
1
is
less
than
the
score
of
our
toe
or
the
other
way
around
make
sense.
So
two
approvals
must
not
intersect
in
either
score
or
or
weight
and,
moreover,
they
have
to
be
waitin
score
have
to
be
on
the
same
side.
So
it
is
not
okay
not
to
intersect
on
weight
in
y
direction
and
not
intersect
on
score
in
another.
It
has
to
be
in
the
same
right
so
either
both
as
a
score
and
weight
of
one
parent
look
bigger
than
of
another
reference
or
the
other
way
around.
A
So
those
are
two
conditions:
the
behavior
of
an
owner's
block
producer.
The
expected
behavior
is
the
following:
they
maintain
for
every
chain,
then
they
maintain
the
last
approval
they've
made,
and
they
also
maintain
the
largest
weight
and
the
largest
score
that
they
ever
had
on
their
parent
block,
and
so
their
behavior
is
when
they
see
a
new
block.
If
the
largest
weight
on
score
that
they
ever
approved
happens
to
be
the
weight
on
the
score
of
the
last
approval
on
this
chain.
A
A
We
call
a
particular
block,
so
we
always
look
from
perspective
of
a
particular
chain.
So
there
is
a
tip
we
call
we're
going
to
call
T
so
from
perspective
of
a
tip.
There
is
a
chain.
We
say
that
a
particular
block
has
a
quorum
provoke
quorum,
promote
if
there
is
more
than
two-thirds
of
witnesses,
for
whom
there
is
an
approval
where
the
parent
block
is
this
block
or
something
in
the
future
and
the
reference
look.
A
A
Went
through
that
write,
a
reference
block
is
a
property
of
an
approval.
A
reference
book
of
approval
is
chosen
by
the
block
by
the
witness.
If
the
last
approval
they
made
was
on
the
same
chain,
they
will
choose
the
same
reference
block
as
last
time
if
it
was
on
a
different
chain
that
will
choose
yeah.
B
A
A
We
say
let
let's
move
to
a
little
bit
to
the
right.
We
say
that
a
particular
block
has
a
quorum
pre-commit
on
B.
If
there
are
two
thirds
of
approvals
such
that
the
approval
surrounds
both
B
and
Q
V
of
B
okay.
So
it's
not
enough
to
have
two
thirds
of
approval
just
around
in
Q
and
B.
That
would
not
create
a
quorum
pre-commit
on
B.
Let's
make
sense,
we
need
to
have
two-thirds
of
a
proof
which
which
run
both
okay
and
there's
normal
circumstances.
A
If
the,
if
the
approvals
are
not
skipped,
what
would
it
mean
is
that
this
block
is
pretty
produced?
The
very
next
block
will
have
two
thirds
of
people
having
approvals
with
parent
look
here
and
reference
doesn't
matter
where,
so
the
block
will
immediately
get
quorum.
Pre
vote
right
and
on
the
very
next
block,
they're
going
to
be
2/3
of
off
approvals.
Going
like
this,
this
is
going
to
be
a
quorum
people.
This
is
the
block,
so
you
get
quorum,
pre-commit
onto
blocks
and
the
block
that
has
a
quorum.
Pre-Commit
is
final
right.
A
Okay,
what
we
did
not
define
is
the
score
of
the
chain.
The
score
is
defined
very
very
easily
for
a
particular
block.
Are
you
identify?
The
right
must
block
the
most.
The
most
recent
block,
which
has
a
quorum
pre
both
on
it
and
the
weight
of
that
block
is
the
score
of
the
chain,
make
sense
so
from
perspective
of
this
block.
A
C
A
We're
not
going
to
go
through
how
it
can
become
here
it.
It
can
right,
it's
easier
to
prove
safety
when
it
exists
and
not
then
to
prove
lack
of
safety
when
it
doesn't,
but
there's
no
safety
without
unless
something
is
finalized,
so
Sam
chain
becomes
haver.
You
do
want
to
start
creating
approvals
on
this
chain,
because
this
chain
is
going
to
win.
A
Your
approval
on
this
chain
will
not
give
you
any
reward
now,
but
you
cannot
go
all
the
way
back
to
Genesis
because
you
will
trigger
special
behavior
Europe
robots
will
have
the
same
reference
block
or
they
will
intersect
right.
At
that
point,
you
you
will
like
your
first
approval
will
go
here,
and
every
consecutive
approval
will
also
go
here
right
so
effectively.
You
will
always
go
as
far
to
the
past
not
to
trigger
slash
double
behavior
with
another
chain
that
exists
where
you
created
on
a
probe
before
right.
Okay,.
C
A
But
for
that
the
second
chain
already
had
to
start
winning
for
some
reason
right.
Okay,
so
let's
prove
that.
So
let's
say
this
block
is
final:
let's
prove
that
never
a
block
with
the
higher
weight
will
get
a
quorum
pre
vote
right
so
that
so
this
block.
Let's
call
it
v1,
let's
say:
there's
another
block
b2,
which
has
a
higher
weight
and
let's
say
it
did
get
a
quorum
P
vote.
So
if
it
got
the
quorum
P
vote,
this
chain
will
get
a
higher
score
hypothetically.
A
It
could
get
a
higher
score
if
never
a
block
with
a
higher
way.
It
gets
a
quorum
pre
boat.
You
will
never
get
the
score
higher
than
than
this
chain
because
by
definition,
if
you
one
has
quorum
pre-commit,
that
means
that
there
was
a
block
with
quorum,
P
vote
right,
Q,
V
and
then
2/3
of
people
saw
that
blog
because
they
proved
something
to
the
right.
So
from
perspective
of
those
people.
A
The
score
of
this
chain
is
at
least
the
of
v1,
because
this
so
quorum
provoked
on
v1,
right
and
so
for
this
chain
to
overtake
its
core
need
to
be
higher
than
b1.
For
that
another
block
with
a
score
higher
than
score
of
d1,
you
still
get
the
quorum
people.
So
let's
show
that
another
block
cannot
get
a
quorum,
pre
volt.
Let's
say
it's
not
the
case.
Let's
say
this
is
actually
a
block
Q
V
on
on
b2.
Sorry.
A
This
one
is
a
Q
V,
1,
V
1,
and
also
this
somewhere
block,
which
is
QC
on
V
1,
because
V
1
is
final.
So
consider
all
the
approvals
which
made
me
want
to
be
a
quorum,
pre-commit
write.
Those
approvals
surround
both
and,
let's
just
look
at
one
approval
right
so
from
perspective
of
these
at
least
one
witness,
because
these
two
thirds
of
more
than
2/3
of
witnesses
who
surround
both
QV
and
be
one
with
an
approval
and
more
than
2/3
of
witnesses
who
surround
b2
with
an
approval.
A
There
is
at
least
one
assuming
less
than
1/3
is
malicious.
That
has
both,
let's
just
consider
them
right,
so
they
have
some
approval
here,
and
so
my
pictures
are
very,
very
good,
but
it
doesn't
have
to
be
that
this
is
to
the
left
from
here
from
this.
It
could
be
that
they,
moreover,
if
they
must
be
separated
right,
let
me
actually
change
it
so
that
it's
clear,
so
this
is
B
2.
A
The
notice
that,
because
because
this
approval
for
quorum,
pre-commit
surrounds
both
quorum
people
and
and
the
block
itself,
then
the
score
of
the
parent
block
is
at
least
weight
of
d1
make
sense
right.
So
let's
call
this
p1
p
r1
to
r2,
so
we
know
that
score
of
p1
is
at
least
it's
greater
or
equal
to
the
weight
of
of
d1
right.
A
We
also
know
because
there
is
no
/,
we'll
behavior
happening.
We
know
that
weight
of
the
two
is
greater
than
weight
of
B
of
the
one.
That's
best
sumption
right.
That's
what
we're
proving
that
this
is
impossible,
so
to
prove
to
proof
by
contradiction.
We
assuming
that
this
is
the
case.
That
means
that,
because
P
2,
because
B
2
is
the
in
the
ancestry
of
people,
that
means
that
weight
of
P
2
is
greater
and
R
1,
isn't
the
ancestor
of
B
1
and
greater
than
weight
of
R
1?
A
A
A
Okay,
let
me
think
again
for
a
second
from
that.
It
means
that
again
from
because
for
approval,
weights
and
scores
have
to
be
on
the
same
side.
It
also
means
that
the
score
over
two
is
greater
than
the
score
of
P
1.
So
the
last
thing
we
discovered
is
that
score
of
R
2
should
be
strictly
greater
than
score
of
Q
1,
but
we
also
know
that
the
score
of
T
1
we
started
from
that
is
at
least
the
weight
of
D
1,
and
so
this
is.
A
But
that
means
that
there
is
a
block
that,
from
perspective
of
r2
from
perspective
of
this
block,
this
is
a
block
in
its
ancestry,
with
the
quorum
pre
vote,
which
has
a
weight
bigger
than
V
1.
So
there's
another
block
like
b2
somewhere
here
and
at
you
understand
it
cannot
happen
infinitely
right
like
by
induction.
We
will
say,
oh
that
that
means
that
in
the
entity
there
is
another
block
like
that
in
density.
There
is
another
block
like
that
right
or
like
even
easier.
A
We
could
have
said
that
V
2
is
this:
the
bloke
with
the
smallest
weight
right
and
then
would
immediately
reacted
to
the
contradiction
that
the
block,
with
the
smallest
weight,
bigger
than
the
one,
has
another
block
in
its
ancestry,
with
clearly
weight,
even
smaller
right.
Okay.
So
that's
that's
the
safety
proof
effectively,
which
shows
that
if
a
block
has
colon
pre-commit,
it
cannot
get
I
know
how
the
block
will
ever
have
a
coram
pre
vote
with
the
higher
weight
cool.
C
A
Yesterday
running
a
lot
of
stress
tests
and
I
was
trying
to
replace
small
pieces
so,
for
example,
if
I
replace
so
I
have
a
test
which,
which
would
stress
lot
of
graphs
and
make
sure
finality
safety
never
violate
if
I
replace
the
score
with
with
the
with
the
weight
of
quorum
pre-commit,
it
immediately
finds
the
graph
personal
safety
would
be
violated
if
you
like,
if
you're
playing
a
small
park
safety
gets
violated,
but
with
this
particular
rule
suits
it
works.
Okay.
So
now
quick
implementation
details
effectively,
we
need
few
things
to
implement
that
to
work.
A
So
one
I
already
discussed
right.
How
do
we
give?
How
do
we
compute
our
approval
right
so
for
every
chain
for
every
chain?
We
remember
the
last
approval
on
the
chain
right
so
for
every
block
with
the
block.
We
just
store
the
last
approval
from
us
on
that
chain
that
ever
that
ever
happened,
and
when
we
achieve
a
new
block,
the
choose,
an
approval.
We
look
at
the
last
Pearl
happened
on
this
chain.
A
We
also
note
the
last
approval
over
all
that
we've
ever
made,
and
we
see
if
our
last
approval
overall
is
on
this
chain.
We
use
the
same
reference
block
and
if
it's
on
a
different
chain,
we
know
the
weight
and
height
the
weight
and
score
of
the
last
block
right,
and
we
just
use
the
largest
block
on
this
chain,
the
sorry
the
most
the
least
recent
lock
on
this
chain,
which
has
higher
weight
and
higher
score.
A
Okay,
second
thing
we
need
to
do
is
we
need
to
slash
people
when
they,
when
they
create
double
double
double
signs,
so
the
way
I
do
that
is
for
every.
Whenever
we
see
an
effectively.
The
goal
here
is
not
to
slash
for
any
special
behavior
go.
Here's
2/4
every
behavior
which
might
temper
with
finality
right
because
slashing
in
the
first
place
exists
so
that
people
cannot
do
damage.
If
some
action
is
flashable
but
could
not
possibly
do
damage,
we
don't
have
to
slash
for
that.
A
It
wouldn't
hurt
to
slash
for
that,
but
we
don't
need
to
help
that
logic.
So
the
way
I
do
that
is
well
assuming,
assuming
that
you
know
that
safety
never
actually
gets
violated
and
the
finalize
looks
actually
form
a
chain
for
every
final
block.
When
that,
whenever
I
see
a
new
block
are
getting
finalized,
it
will
always
be
built
on
top
of
some
other
finalized
block
for
every
approval
which
contributed
to
this
blog,
getting
finalist
so
for
every
approval
that
surrounds
was
both
the
block
and
the
end.
The
key
view
of
that
block.
A
They
clearly
need
an
approval
which
conflicts
with
the
with
the
light
latest
or
the
latest
approval
I
received
from
them.
So
that's
how
it's
built
right
now!
Well,
I!
Guess:
that's
how
its
planned
to
be
built
right
now.
Ok!
Finally,
the
most
interesting
part
is
how
to
actually
compute
quorum,
cravat
and
quorum
pre-commit.
The
way
I
do
that
is
I.
A
What
is
very
simple
first
thing
we
need
to
observe
is
that
it
is
impossible
for
the
same
participant
to
have
to
approvals
of
this
form
that
make
sense
right
such
that
one
is
fully
encompassing
another
where
these
are
not
equal
to
each
other
right.
So
that's
that's
the
first
observation,
and
if
this
does
happen,
I
have
like
some
protection
in
case
someone
maliciously
created
such
thing
but
enjoy.
Let's
assume
it
never
happens
right.
A
Let's
call
it
a
witness
to
hide
where,
for
every
witness,
I'll
I
know
the
the
the
least
distant
right
to
which
their
approval
goes
and
so
and
also
for
every
height,
I
I
know
all
the
witnesses
who
go
all
the
way
down
to
the
kite
right
and
then
finally,
I
maintain
and
effectively
an
integer
which
says
like
how
many,
how
many
approvals
are
surrounding
the
current
block
make
sense.
That's
called
a
total
approvals.
A
Okay,
so
quick,
quick,
quick
revolt
is
trivial.
We
go
from
the
block
for
every
approval.
We
update.
First
of
all,
you've
already
had
some
approval
before
we
will
remove
it
from
both
of
those
mappings.
That's
easy.
We
will
edit
to
those
mappings
and
if
we
didn't
have
approval
for
that
person,
and
now
we
do
it
with
increased
total
approvals
right
and
then
for
every
approval,
which
was
going
only
all
the
way
to
this
height.
A
We
will
remove
them
from
the
from
the
proof
and
decrease
total
approvals
by
that
number,
and
if
that
number
is
more
than
two-thirds
of
witnesses,
that
the
block
has
quorum.
Pre
vote
because
effectively
will
maintain
the
number
of
total
approvals
that
surround
the
block.
I
think
sense:
cool
Corin
pre-commit
is
a
little
harder,
but
also
not
very
hard
effectively
as
I
go
to
the
left
hand
from
the
last
block.
I
maintain
a
pointer
to
the
to
the
first
block,
for
which
I
do
not
have
two-thirds
of
of
approval
surrounding
it.
A
Okay,
so
so
so,
if
total
approvals
is
less
than
two-thirds,
that
would
be
the
current
block
that
make
sense
right,
because
no
block
has
2/3
surrounding
right.
So
at
the
beginning,
I
start
I
call
it
h/h
points
to
the
current
block,
because
there's
no
approvals,
but
the
moment
I
have
2/3
of
them.
H/H
will
be
pointing
so
like
that.
Could
the
current
block-
let's
call
it
c
@h-
could
be
pointing
to
something
before
the
current
block.
That
means
that,
for
every
block
for
current
for
this
one,
there
are
two
thirds
of
approvals.
A
A
You
can
easily
show
that
as
long
as
approvals
are
nevertheless
that
H
can
only
go
to
the
left
right,
because
I
would
only
whenever
like
if,
for
some
participant,
there
is
an
approval
that
goes
to
the
left,
because
there
are
no
nest
at
the
Provos
as
I
go
to
the
left.
For
that
participant
approval
can
only
go
further.
It
can
never
go
closer.
A
So
all
the
all
the
approvals
that
current
is
around
the
block
right
after
H,
they
can
only
only
become
longer
they
can
never
become
shorter,
and
so
this
block,
if
it
has
right
now
two-thirds
of
approval
surrounding
it,
it
will
never
have
less
than
two-thirds
right
answer,
which
can
only
go
to
the
left
and
maintaining
H
is
not
super
hard
effectively.
Whenever
I
process
an
approval
is
before
it
was
ending
to
the
right
from
H,
and
now
it
ends
to
the
left
from
H.
A
Then
H
then
I
increase
the
number
of
over
prove
of
surrounding
this
block
right
and
then,
if
it
takes
its
two-thirds,
I
move
I
move
H
to
the
left
does
make
sense
and
when
we
move
H
to
the
left,
so
here's
one
so
so,
let's
say
so,
for
this
block,
so
I
know
for
H.
So
I
have
another
question
which
says
total
surrounding
H.
A
So
the
moment
total
surrounding
HS
exceeds
two-thirds.
That
means
that
H
is
not
properly
pointing
I
need
to
move
it
to
the
right,
but
I
also
need
to
compute
the
new
total
surrounding
H,
but
that's
very
easy
because
I
know
exactly
how
many
approvals
end
here
right,
I
have
it
in
this
h2
are
two
witnesses.
I
will
need
to
remove
so
I
just
subtract
this
into
this
number
from
total
surrounding
H
I
get
the
new
Toto
surrounding
H,
as
H
moves
one
one
spot
to
the
right.
So
this
way
I
can
maintain
H.
A
So
how
H
helps
me
well
whenever
observer
block?
If
that
block
has
a
quorum,
promote
right
choice,
so
total
surrounding
is
2/3
I,
say
from
perspective
of
this
block.
What
was
the
latest
record
for
core
improve
alt
right
and
if
that
light,
this
quorum
free
vote
is
after
H.
Well,
that
block
gets
colon
pre-commit,
let's
make
sense
so
for
this
work.
In
a
day
when
this
look
was
processed,
we
computed
the
quote:
improve
the
the
latest
blog,
the
most
recent
blog,
which
has
quote
unquote
from
its
perspective
right.
A
So
for
this
blog,
like
in
the
header,
it
has
like
sort
of
most
recent,
let's
go
at
most
recent
quorum,
pre
vote,
which
points
to
sunblock
like
what
is
when
this
block
was
the
tip.
What
was
the
most
recent
block,
which
had
the
quorum
pre
vote
right,
and
so,
whenever
I
go
whenever
compute
quorum,
most
recent
quorum
Prevotella
most
recent
quorum
pre-commit
for
this
block,
I
go
to
from
from
right
to
left
and
whenever
for
a
particular
block,
I
get
porn
P,
both
meaning
the
total
total
approvals.
A
That
of
surrounding
approvals
is
two
thirds
plus
one
I
say:
is
this
most
recent
quorum
pre
boat
from
perspective
of
this
block?
To
the
right
or
to
the
left
from
H,
if
it's
to
the
right
from
H,
that
means
that
right
now,
I
have
two
thirds
of
approvals
that
surround
both
this
block
and
this
block,
because
they
all
I
didn't
I
didn't
adhere
approvals
which,
which
are
to
the
right
to
do
to
the
left.
I
will
add
them
as
I
go
to
the
left
right.
A
I'd
only
think
that
is
left
to
show
is
that
the
very
first
court
became
it
I
find
is
actually
the
most
recent
one
right
so
like
something
that
that
could
happen
is
that
if
I,
if
I
look
from
perspective
of
this
block,
then
coram
pre-commit
will
be
here.
But
if
I
go
to
the
left,
maybe
coram
pre-commit
will
be
somewhere
closer
right.
A
That
can
never
happen,
because
that
would
imply
that
some
block
to
the
left
from
this
block
has
a
quorum
pre,
both
which
is
more
recent
I,
but
it's
very
easy
to
show
that
quorum,
pre
votes
they
only.
They
only
go
to
the
left
right,
because
I
mean
it's
obviously
from
perspective
of
this
block.
This
block
had
two-thirds
of
approval
surrounding
it,
obviously
from
perspective
of
any
future
block
it.
It
also
has
two
thirds
of
approval
surrounding
it
all
right.
Okay,
so
that's
all
the
implementation
details,
that's
it
for
the
phonology
gadget,
any
immediate
questions.
A
Okay,
so
the
question
is:
what's
the
difference
between
proton
pic
image,
so
let's
very
quickly
go
through
them
again
from
perspective
of
a
particular
tip.
So
this
is
tip
a
particular
sunblock
has
:
p
vote?
If
so?
So,
if
you
consider
all
the
approvals
which
exist
in
the
in
the
ancestor
of
the
block,
so
the
block
has
a
quorum
P
vote
if
it
has
2/3
of
witnesses
having
a
probe
which
surrounds
it
effectively
right
and
we
will
call
the
first
block
from
perspective
of
which
we
had
quorum,
people
to
skew
D
of
B.
A
If
every
consecutive
Block
B
will
also
have
coronary
boat,
but
we
will
refer
to
PV
of
B
as
the
first
block
which
which
had
quorum,
pre
vote
on,
be
something
has
a
quorum
pre-commit
if
both
the
block
itself
and
the
first
block,
which
had
come
pre
boat
or
any
block
which
has
called
people,
don't
be,
have
two-thirds
of
approvals
approved
from
two
thirds
plus
one
witnesses
surrounding
both
of
them
simultaneously.
So
you
need
like
pretty
wide
approvals
which
surround
both
of
them
right.
A
So
then
the
block
is
called
to
have
a
quorum,
pre-commit
right
and
so
quorum
provoke
is,
is
very
trivial
to
compute,
because
all
you
need
to
say,
like
you,
have
those
intervals
right
and
you
just
need
to
like
it.
Just
look
at
this.
What
is
called
swiping
sweeping
yes,
sweeping
sweeping
line
whatever
sweeping
pointer
yeah
just
have
the
sweeping
pointer,
which
goes
from
from
the
most
recent
look
to
the
list.
Isn't
one
maintaining
those
approvals
and
for
a
block.