NEAR Lunch and Learn Ep. 07: Nightshade: Finality Gadget

Captions as YouTube publishes them, usually machine-generated, so product and people names can be misheard.

1. 0:05

   hi everyone this is the next episode of life series today were going to be talking about the finality gadget that we call Casper Energy which stands for a nitrate nitrate finality gadget a quick introduction on what finality gadget is and why we need it say we have a blockchain where block up roadblocks are produced 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

2. 0:37

   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 whenever a block is produced we also define a set of let's call them

3. 1:01

   witnesses or we call them block producers but for the sake of this video we're going to call them witnesses participants who observe the network and and sign on the blocks whenever a there's a total of n witnesses and whenever a witness observes a new block they can create an approval where approval I usually draw it as an arc has a parent block so the block which or rather like the block

4. 1:31

   which is being approved we call it a parent look and it also has another block called the reference block the semantics of the reference block we will cover in a second so right now in our in our current implementation the parent block must immediately precede the block that contains the pool but that that requirement we don't rely anywhere in that requirement is just an implementation detail so in general in the future it could be that approvals with a particular parent block another

5. 1:57

   included in the in the block that immediately followed by the included later there are a few requirements for the in the second 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

6. 2:24

   particular witness 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

7. 2:53

   have been appropriate for the same for the same witness if the if the reference blocks are different then we require that for two approvals the so let's call it R 2 so we call we call the parent block P a reference block R so this is R 2 P 2 this is R 1 P 1 we require that either P 1 the weight of P 1 is less than weight of art R 2 and the score of T 1 is less than the score of our toe or the other way around make sense so two

8. 3:32

   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 so those are two conditions the behavior

9. 3:57

   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 that could that

10. 4:21

    would only be the case if if that was their if this is their last approval they cannot possibly have another problem on another chain which I wish which has a bigger wait or score that makes sense right otherwise it would be the largest in this case they just get to probably the same reference block and if the last approval on this chain has a has a weight on score of a parent parent block which are less than the largest the the

11. 4:45

    witness ever created then they would only approve if the parent they would only create on a pro first of all if the parent block has a weight and score higher than the last that they created and they will just choose the the right must block that has weight and score higher than the largest they approved make sense right cool okay now the we introduced two concepts concept number

12. 5:08

    one 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 is this block or something in the past make

13. 5:40

    sense so effectively effectively whenever you issue an approval with some parent block and some reference block you are testing - all the blocks in this range inclusive and so if a particular block has more than 2/3 of its stations it has a quorum pre vote and we specifically we call a block so let's call it so let's say this is block B the block the first block which has quorum to vote on B we're going to call it Q D of B so qvo FB is the first block with

14. 6:10

    Erics cuz reference block chosen for like a given broad I just 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 but it is a reason that you if it's in the same chain you would

15. 6:35

    choose the same reference so you might you might choose like the parent look so you can introduce an economic incentives to choose that what is I guess they're like is it like sort of random or is it like a good reason to prefer to use the well well let's say your reward is proportional to the length of your approval okay so if you have some incentive to choose reference block as far to the past as possible

16. 7:00

    cool so we call the block the first block which has a quorum pre-wrote on b QV of be quorum people to be a particular 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

17. 7:32

    to have two-thirds of a proof which which run both okay and there's normal circumstances 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

18. 7:54

    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 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

19. 8:18

    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 if this is block if B is the larger if the if the most in is the most useful block for which quorum people it exists and then the score of this block the score of T is the weight only makes sense okay so let's quickly go through the safety proof so let's say like every

20. 8:48

    member of the quorum is supposed to vote on approvals like I allowed to vote for approvals on every block yes they don't have a cave they skip an approval right but they they are expected to provide the Provos as frequently as possible going into the past or you cannot so right now in the current implementation you can only provide approval for the very previous block reference if you if you go ideally yes ideally if there's only

21. 9:25

    one chain you will always use Genesis as your reference but if there are multiple chains if there is another chain and at some point that let's say this is Genesis and like for a while people who are creating approvals and at some point this chain becomes failure 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

22. 9:51

    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 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

23. 10:08

    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 yes 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

24. 10:37

    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 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

25. 10:59

    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 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

26. 11:24

    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 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

27. 12:00

    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 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

28. 12:26

    actually change it so that it's clear so this is B 2 this is Q V of B 2 and there's an approval which goes something this ok 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

29. 13:12

    least it's greater or equal to the weight of of d1 right 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

30. 13:47

    isn't the ancestor of B 1 and greater than weight of R 1 does this make sense like because the weight of B 2 is greater than weight of B 1 that natural implies that weight of P 2 is greater than than weight of P 1 now because those two intervals do not intersect that also implies that weight of R 2 is greater than weight of P 1 right we reduce weight and monotonically non-increasing yeah some of those could

31. 14:22

    be greater equal that's they could be they could be off by one errors okay so so weight of R 2 is bigger than then weight of P 1 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

32. 14:55

    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 this is strictly greater which means that the score over to score over 2 is strictly greater than the weight of D 1 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

33. 15:27

    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 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

34. 15:50

    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 so the finality is having quorum pre-commit but coram people defines the score and so I spent quite a bit of time yesterday running a lot of stress tests and I was trying to replace small pieces

35. 16:20

    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

36. 16:43

    implement that to work 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 we also note the last approval over all that we've ever

37. 17:08

    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 so this is not how this implemented right now right now if I switch chants I just use parent lock as a reference block which that doesn't hurt much but

38. 17:34

    you missing on your words right 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 it wouldn't hurt to slash

39. 18:07

    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

40. 18:30

    finalist so for every approval that surrounds was both the block and the end the key view of that block I memorize I remember for that particular participant that approval so I have a have a table index by the participant by the witness where for every witness I remember the last approval that I used from them to finalize a block and whenever receive a new approval from them I will always I will only create a challenge if the new

41. 18:53

    approval I receive conflicts to disapproval and I don't care if it conflicts with any approach from the past does make sense because they would only they would only tamper with finality if they managed with some of their approvals to revert this block divert this block 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

42. 19:17

    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 do it in linear time which i think is a slightly suboptimal so effectively whenever receive a new block in the worst case I will traverse all the way back to Genesis so I will explain how it works right now and then we can quickly cover how it can be sped up so

43. 19:43

    effectively to find quorum pre 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

44. 20:08

    let's assume it never happens right so what I do is I go from right to left and for every participant for every witness I remember the the the furthest height to which they approved right so I have this cache map 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

45. 20:41

    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 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

46. 21:11

    it with increased total approvals right and then for every approval which was going only all the way to this height 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

47. 21:36

    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 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

48. 22:00

    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 it also means that all of them will have quorum pre vote on them but this is the first block for which from perspective of C D is not 2/3 of approves maybe as I go to the left and that add more approvals eh we'll get

49. 22:23

    two-thirds of oppose but right now it doesn't okay so H 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 so all the all the approvals that current is around the block right after H they can only only become

50. 22:55

    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 then H then I increase the number of over prove of surrounding this block

51. 23:19

    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 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

52. 23:52

    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 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

53. 24:21

    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 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

54. 24:46

    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 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

55. 25:12

    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 so only only from the approvals which I edit on the right I have two thirds which surround all the blocks to the right from H does make sense right and

56. 25:36

    so whichever block has most recent quorum free both from perspective of this block if it's to the right from H that block has couldn't be commit 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

57. 25:59

    maybe coram pre-commit will be somewhere closer right 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

58. 26:29

    that's it for the phonology gadget any immediate questions 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

59. 27:04

    effectively right and we will call the first block from perspective of which we had quorum people to skew D of B so when this block was a tip we did not have quorum free boat but when this blog became a tip now B had a quorum pre boat right and so from person 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

60. 27:35

    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 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

61. 27:59

    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 you can very easily say if it has 2/3 of approval surrounding it right but to complete quorum click commit when for some block you you recognized has grand prix vote he need

62. 28:23

    to say of those two-thirds of approvals more than two-thirds of applause that's around this block is it the case that at least 2/3 plus one of them also surround the most recent quorum people from perspective of this block right and so to do that you just maintain the pointer to the first block in the ancestry which does not have to third surrounding it right and if the most using quorum pre both from perspective of this book is to the right from the pointer then you know

63. 28:46

    that block has corn picking it because you know that there are two thirds of the approval that the surrounding currently this block 2/3 plus one of them or of number of witnesses Provost rounding also this block cool any other questions hey thank you thank you for watching