F3 and GossipBFT: Fast Finality on Longest-Chain Protocols | Alejandro Ranchal-Pedrosa - Filecoin

[Music] hello everyone you hear me well yep yeah I'm Alejandro ranal from protocol labs and I'm going to be talking about uh how to get fast finality on longest chain protocols so this is uh the outline of the presentation first um a little bit of the status quo of how longest chain protocols work uh particularly for the case of fcoin and our first take at providing faster finality uh with the EC finality calculator then we kind of reach the kind of the lower bound of uh architectures that only have a longest chain protocol so then we look at architectural options to provide even faster finality and uh we came up with a architecture that we call F3 and I'm going to be detailing the architecture and how we integrate it in fcoin with the longest chain protocol at the core of the architecture there is a a new consensus protocol that we call gossip bft and yeah I'm also going to prend a little bit of that one plus the finality exchange protocol in order to get saxing verifiable proofs uh finally a bit of the implications that F3 brings to longest chain protocols and the road map for the case of fcoin so longest chain protocols um as probably everyone here knows longer chain protocols assume probably St synchrony so the a confidence in a block not being reverted as a result of a fork uh grows over time right with more uh blocks appended to the chain um in FAL and until 2023 this meant um 900 EPO not every longest chain protocol prescribes a particular finalization time or confirmation time uh in the case of Falcon it is prescribed because the power table of the system is part of the state of the system and this power table is assumed to be final uh therefore actually there is a a number that is embedded in the implementation which is 7 and a half hours um it is so much because Falcon is not really a chain of blocks it's a chain of tip sets and tip sets are uh sets of blocks of the same Epoch and the same parent tip Set uh Epoch so in Falco and time is discarded into 30 second slots that we call EPO um so what 7 and a half hours means for an example of uh gaming platform uh would be for example if you know you're uh launching this gaming platform and you have multiple games you do not want your users to have to wait 7 and a half hours every time they want to buy a game so maybe you when you can do is something like a subscription based system where a token is issued and they only have to wait 7 and a half hours at the first time that they join the system and then they you have kind of like a L2 for multiple games and so in your L2 you can run your own consensus that doesn't have to be longest chain and maybe it takes about 10 minutes and suppose Alice and Bob want to play a game of chess they can spawn maybe their own stage Channel and just play within seconds right uh so this is how it should be done uh given the longan finalization time in the main chain our first stake on providing fast finality is what we call the E EC finality calculator EC stands for expected consensus which is the main consensus at the longest chain so the basically the longest chain type of consensus at filecoin the principle is that not all tip sets are the same so in filecoin every Epoch in expectation selects five proposers and so in expectation a tip set per EPO will have five blocks so if you see multiple EO with suppos two blocks you do not have the same level of confidence in that uh chain as the one that you can have if you see three consecutive eugs with five blocks right uh in the tip sets so using this during the good case on the normal case uh we can actually provide finality within 15 minutes which kind of like reaches the lower bound of long exchain protocols um we actually have PR the Falco the F FRC in the Falco Improvement proposal uh repo and we also want to provide the functionality directly at the API of the clients the Falon clients but uh it's not even needed like if you want to build an application you can like all the information is available for you to do the analysis and the risk assessment of analization thanks to the um EC FAL calculator the gaming platform doesn't anymore need to spawn a layer two but still 10 15 minutes you know you do not want every move of Chess to take that amount of time so you probably still like Alice and B probably still want to spawn a state Channel or something of the sort and play directly with with one another right of chain so that kind of showcase is that is not perfect right the easy ID calculator and the lower bound longest chain protocols is better than ours um and and in the case of the Ean ID calculator is great that we don't even need to modify the protocol it's just an information that is readily available um but it's still tens of minutes and ideally we'll get something better right but even um even I mean that's that's an idea but even in the case of ethereum the finality Gadget that they implemented takes about six minutes for fantization which is not ideal it's much better than hours right but it's not not good enough what we want is seconds right we want finalization within seconds and we also want to be able to prove to um observers that are not necessarily fetching all the data from filecoin that a particular block or a particular transaction has been finalized so we want sucing verifiable finality certificates and the immediate solution the immediate uh outcome of this is that we need a new architecture we cannot do this just with long exchain so we we look at multiple architectures that we could we of course the first uh the immediate reaction was let's look at the state-of-the-art let's see how others do it maybe we maybe we don't need to create a new architecture and we set a a set of goals of course fast finality but we don't want faster finality at the cost of robustness right you can already get that if you just uh lower the finalization time you're just going to have less confidence in the result uh we also normally if you fix robustness and fast finality you what suffers is the assumptions right you just have a uh a stronger set of assumptions on the adversary that you tolerate we also don't want that we want or put differently we don't want the assumptions that we make in order to introduce this newer finality uh module onto the system if there are assumptions we don't want them to come from this module they could come from different parts in the system and also we are looking at this in the scope of providing faster finality for a chain for a longer chain protocol that or system that has been running around for years that is Battle tested so we want to change it as little as possible so so that you know it doesn't uh spark too much uh angs in the community so some options we looked at already went through longest chain or FK Choice protocols not fast enough we want faster finality uh for fast finality one that was very interesting was Avalanches type of subsample voting uh because it finalizes within seconds and it scales very well the problem is it has a very strong synchron assumption that we felt we didn't want to have and it only tolerates 20% of uh an adversary controlling 20% of the of the power table 20% is actually not that bad when you have a lot really a lot of notes um but if we're looking at us we think we can do better than that if we're looking at a a membership in the scope of thousands of notes um another immediate uh state-of-the-art project to look at the finality Gadget of ethereum or other best E4 finality gadgets the advantage of course is the small refactoring but there are some security concerns in particular I have no seen yet a formal proof of the security of the cper refy and also it assumes stor syn is not fast enough we still want within seconds and C Refuge takes about six minutes to finalize anything and of course the Holy Grail of distributed systems that have been started for decades bft protocols we know that fast we know that resilient but it's you know changing a longest chain protocol into a bft protocol is too is too much refactoring is definitely not the path of Lee resistance so looking at the last two there's an immediate um uh idea why don't we combine them right can we provide maybe a bft protocol as a finality Gadget right just as an additional module that provid finality and what we claim is that what we get is we get fast finality resilient optimal security we don't need to assume synchrony and we refactor well so we basically follow the path of lead resistance because we barely touch the main code we just add a new model so a bit of how this is what we call F3 which stands for fast finality in fcoin but it's completely modular and can be applied to any other longest chain protocol so the way it works this is how a longest chain like a very abstract schematic of a longest chain protocol works so some blocks come from the network and there's some process that we're going to call the LC Sinker that has the blocks to the local view of the chain and then there's some Fork Choice rule that selects the heaviest chain right in this case this one here with a with a head block uh so what we do is we add a new component that simply reads the head of the chain and this component propos poses as input to a new vft consensus protocol this head to finalize then the vft consensus protocol runs consensus and eventually it outputs some block that that is final that it needs to be finalized once this output comes out the F3 component marks that pre the prefix up to that head new new that new head block as final which in this case would be B so up to B will be final and you know the Block H even though it was proposed by this note it didn't get finalized in iteration of the bft consensus protocol in terms of the integration really the only changes that are necessary are the ones shown here uh and these ones in the case of fcoin for example are already available we didn't need uh we wouldn't necessarily do we wouldn't need to do any changes necessarily to the API in order to integrate this model however for pragmatism we did we are doing now at the implementation phase we're doing some changes uh but they and essentially don't only thing you need to do is to read ahead and then to finalize uh some block uh in the finalize chain which is what we call checkpointed in fcoin and then of course implement the new model the new F3 model completely independent though uh some changes that we do we actually uh create a new function to finalize rather than checkpointing because checkpointing is more something for the user to do so we actually change the Frog Choice rule to always select the heaviest suffix of the finalized chain um and instead of pulling from F3 we actually push the heads to F3 but those are minor differences um we don't do this in the case of Falon but we you could also change the block header format in order for the longest chain protocol itself to update the power table if you have a longer chain protocol that uh whose power table is part of the state of the system as is the cas of of Fon but we actually don't do this we leave the power table untouch and still is taken 900 e in the past um in terms of the folk Choice rule uh so yeah very small modification the heaviest chain is not anymore the one with the most weight is the suffix with the most weight out of the heaviest finalized prefix so suppose all the blocks here have the same weight normally of course the heaviest chain will be GA B1 C D1 but um suppose that b 0 was finalized this means that the heaviest finalized prefix is g0 and so the new Fork rule selects the heaviest suffix out of this heaviest finalized prefix which would be there's two suffices POS possible one the empty one and the other one is the zero so that would be the heaviest chain once b z is finalized so now a little bit into why we design a new consensus protocol uh which also of course needs to be justified it's not necessarily the path of Le resistance good news is we call it gosip pvft is not a brand new consensus protocol it inherit this a bunch of ideas and basically it's a generalization of Brasher's bisontine agreement protocol that was proposed uh like decades ago and it has been battle tested for ages um and it also of course inherits ideas from pbft that's why hence the name going back to the goals we want the bft consensus protocol to be fast so low latency we want it to be robust and that translates to resistance to the now of service attacks censorship attacks Eclipse attacks uh we don't want strong assumptions no synchrony optimal resilience and of Le resistance it needs to be a simple protocol um there is a trade-off because if you don't assume synchrony then you have less resilience to an adversary that's why we look at both actually we look at synchronous protocols and a pass synchronous protocols there are very fast synchronous protocols and also this like strong tolerance to an adversary it's very interesting but actually the fast synchronous protocols need to assume a single leader which in the scope of open systems if you want to uh tolerate Deni of service attacks would mean implementing single secret leader election and those Protocols are not that simple anymore and even in terms of the latency they wouldn't be that fast anymore uh plus I haven't seen any single secret SSL protocol that uh tolerates an Adaptive adversary yet so it wouldn't really be that denial service system uh the best known leaderless variant that doesn't assume a single leader is the Infinities but now it takes nine times the synchronous bound and the synchronous bound is important for safety so it will be a pretty long bound so it wouldn't be really low latency that's what we ended up going for Pally synchronous protocols um that in particular go vft is a little less protocol and that means that we tolerate about a 33% adversary but I'm going to show later that we actually tolerate a stronger adversary for some attacks that are of concern for filecoin and I'm surely for other systems so cbft is a resilient optimal par synchronous protocol resilient optimal meaning tolerating as I said um an adversary controlling up to a third of the power table of the membership it's a very simple protocol so everybody every node that runs the protocol executes exactly the same code there's no leader uh it's round based and every round has three steps and there's one extra step at the end so once termination happens all the rounds have the same message format a very similar message validation and L and it tolerates uh Eclipse attacks as I mentioned the N service resistant as well um and against in the particular case of censorship attacks and long range attacks we tolerate an adversary controlling 66% of the power table uh in terms of fast finality low latency uh the good news is uh gosip pvft only needs for for a termination it only needs to exchange a linear number of Le P2P messages of uh a linear size in bits this can be improved with some trade-offs I get into that you could do constant number of bits um and of course if you use committies at some point if your power Dev becomes too big um this could be made scalable by Chang in just a constant number of lip2p messages and in good cases actually you only really need uh two steps to finalize uh both asynchronous by the way we do four at the moment uh because this is an optimization where uh probably going to implement later but you will see in a minute why you only need to actually you will see it right now so in the good case we have other steps but these are the key steps of any bft protocol right so if you get lucky suppose we have a membership a power table with four participants assume everybody has the same weight um one of them is bisontine and in this case this bisontine just doesn't communicate with anybody the other three suppos they start this iteration of gosip bft with the same input which is this purple block so they get very lucky Everybody by the way receives the messages pretty fast in this good case example and so the next phase the next step of the round that's called commit also everybody proposes the same block and at that point you can already decide we add a new Step at the very end that we call the decide step just so that uh we can create a finality certificate so the decide step is the one that um after termination a note can aggregate these signatures from the decide messages and prove to people outside the system that this block has been final and I will get into that in a minute and without this step we could still provide a fite certificate with a commit but then we will only tolerate a long range attack against a 33% adversary so there are incentives in the case of Fon to create this extra step to have a tolerance against a greater adversary um now suppose we're not we're not as lucky right we still have this buy something that doesn't communicate and one of the notes that is correct unfortunately proposes a different block the Yellow Block so what happens is in the commit phase we cannot we cannot um terminate by the rules of the protocol so in this case everybody suggest hey we cannot terminate you know empty block so what happens in this case is we go to a new round in the new round there's a new Step that we call the converge step which is the purpose of the converge step is to bring uh to converge to one of the two or multiple values that could be proposed you know because the question is who should change should the people who propose purple change to Yellow so the one who that propos yellow or orange actually uh changeed to purple so what happens in the converge St this is a synchron step is that everybody runs a vrf ticket result and shares inex converge phase their proposed value with their ticket and so at the end of the synchronous timeout uh every note selects the lowest ticket the Associated to the lowest ticket they saw so suppose in this case the lowest ticket is belongs to the note that proposed yellow everybody's going to switch to yellow and then we can actually have termination the same way we had in the good case um this will be everything that's needed as I said even the decide phase is not necessary unless you want to tolerate a 66% adversary against a long range attack so an attack trying to fake certificates from old rounds um but we also want to tolerate uh censorship attack against a very strong adversary the reason being that a censorship attack becomes quite it's kind of incentivized in fcoin because if you censor somebody for long enough they eventually get penalized and out of the membership So eventually you can take control of the system if you censor for long enough so we felt like 33% wasn't good enough and we wanted to toate a great adversary here's a bit of the example of how this attack would work it's very simplified but suppose the longest chain will be the one that finishes with the head in the purple block the a rational adversary like these two notes at the bottom can propose yellow and basically prevent a decision and keep going into new rounds up until they receive the lowest brf ticket and in that moment they can force everybody to switch to their proposal forcing a decision on a different Fork that is not the heaviest one and obviously we don't want that right we want to make that as difficult as possible so it turns out the most the yeah this this how theack will work um the way we do that is in the first round only uh so you remember the first round didn't have the converge step it only had prepared commit and if there is a decision de side so now we have a new Step that is executed at the very beginning called quality with quality step you can actually enforce many things uh it depends on the requirements of your system but in the case of the tolerating a censorship attack against an adversary controlling 66% of the power table what we do is we enforce that a quality value as we call it must have been proposed by at least more than 2/3 of the notes 2/3 of the weight in the quality estad so for example in this execution only purple will be decided so yellow essentially cannot be decided anymore even if somebody holds the lowest ticket in a m in a future round and proposes yellow everybody will be able to see yellow did not pass the quality phase so yellow is not a valid block anymore it's not a valid proposal anymore so of course you could say you know what if it what if two people people propose yellow two people propose purple well then the only decision is not to finalize anything right now let's just go to a new iteration and hopefully by the new iteration some people have changed to a different chain and like in this case this rational now essentially reaches to purple um so essentially a liveness attack is still possible but that's essentially what we do convert a censorship attack into aess P so it's not rationally motivated anymore because sensoring someone else become sensoring yourself as well um yep so that's how it will work in the good case and this is the actual implementation thanks to the Quality step um yes yeah so something I kind of went over about is the fact that um how do we make sure that everybody sees the same messages so how do we make sure that people have agreement on which blocks pass quality a step right what if a participant propos yellow to some people and purple to others and they have different views of what is a quality value um so the way we do this is actually messages in gosip bft needs to be justified um there are two flavors of this justification one of them is literally attaching the strong quarum of messages from previous phes that justify this value so in the case of uh in this case for example a prepare uh so a message sent by this note that contains purple as prepare will need to also attach a certificate uh of signatures of people that propose the same value in the quality step so we aggregate them of course uh but yeah that would be necessary otherwise this value is not valid this message is not valid that's one flavor that's what we call explicit justification the other flavor is to essentially make it so that everybody receives all the messages eventually that that's what we call assuming reliable broadcast there are some trade-offs reliable broadcast is really good because uh the size of the message doesn't increase with the size of participants because you don't need to attach any signature um but you need to change the network layer and because of that we decided uh in the case of the implementation we're doing at the moment for filecoin to just uh go with the implicit justification uh so that we don't need to touch other parts of the system and we just attach explicitly the aggregated signature of just messages that justify the value of the particular message um as for the properties I already went through them I feel but of course the class call agreement validity and termination with some variations but basically the same properties and then we also prove have a property we call proof of finality that relates to the finality certificate and being able to uh to prove to people outside the system that uh a particular blog or a transaction or a prefix of the chain has been finalized and I will get into the particular protocol that does that in a minute then we prove progress proving termination of an iteration of goip pvft doesn't necessarily prove that that there will be anything finalized because you can terminate not finalizing anything right the agreement could be we haven't reached agreement we the agreement could be which we try again next time so we actually prove that during synchronous periods with probability more than half we will finalize something and actually not just something so the heaviest common pref at least the heaviest common prefix of the inputs of of all the correct participants so we finalized the best case scenario with probability more than half during synchronous periods and incentive compatibility in the sense this relates also to the quality of Step nobody switches their proposal unless they see a strong quum of prop of of uh of support for that other proposal so finality certificate um finalizing um a prefix of the chain is good but it's not ideal if we can approve that to other systems that not necessarily not fetching all the data of of the particular longest chain protocol so for for example smart contracts or other chains for chain Bridges or uh l2s that you might be running in your system so what an immediate uh you know uh side protocol of the F3 is the finality exchange protocol that actually proves in a suxing way that that particular chain has been finalized it also we also use it for new notes that join the system to catch up yeah so in naturell the F exchange protocol needs to receive needs to so we assume the whoever's verifying these F certificates knows the public keys of the of the signers so he must have received something he must have received that uh perhaps in that Genesis certificate or something of the sort and the previous output and with that what we essentially sign in the decide phase is the power table Deltas so the changes that occurred in the power table as a result of finalization of that new prefix and also explicit Des sign the tip sets that have been finalized by by this new iteration of Gossip bft um the power table Deltas we don't want to have a very big fite certificate that would that wouldn't be suent which is one of the requirements for the certificate so we actually trate the modifications to the power table by one bite uh in a cumulative way so you know if somebody makes a small changes to their power eventually when the exchanges to the power are big enough they are uh they become effective for the purpose of F3 and as I mentioned thanks to the decide phase we tolerate for this certificates a 66% adversary and thanks to accountability even if there's an adversary that a crazy adversary that controls basically the entire system even more than 66% uh because these messages assign uh there's eventual detection and Punishment if if the outputs it there's like you know a disagreeing outputs it's a g finality certificates okay okay so in terms of the implications for long exchain protocols that F3 brings and the immediate one we provide very fast finality we're talking about tens of seconds uh which is uh unheard of in the context of longest chain protocols and it can be done for any uh longer chain protocol this again we do it in a very modular way um of course on top of that we also provide sxin verifiable finality certificates that uh enables applications to build l2s uh smart contast also to verify finality also for chain Bridges with other chains and even like clients to they don't need to fetch the is the chain the longest chain data they can just fetch the finality certificates in order to verify the finality of a block or a transaction uh because of that we think F3 is a game changer for filecoin and in general for uh longest chain protocols and going back to the G gaming example that I showed at the beginning uh where um in the well okay that's un efficient yes so before we had a very long finality in filecoin and so this gaming platform will require to create its own L2 uh and have users deposit some tokens once and wait this seven and a half hours but once they do that they can change and pay for games in their L2 within like 10 of minutes and then you know they they should still probably create a state channel to actually play the with somebody else then thanks to the finality calculator and faster finality within tens of minutes the gaming platform doesn't need to create an L2 anymore you could just have users pay for the games directly at the main chain because it's going to take tens of minutes which is kind of acceptable but still to play Alis and Bob will still need to create a state Channel something play offchain basically because it's too too costly in terms of time to play in the main chain and now thanks to the final uh the to F3 and fast finality within tense of seconds you know it's still tens of seconds not every game will uh assume that amount will accept that amount of latency but maybe you're playing chess in a like you know with one move every 30 minutes and every move gives you a plus 10 seconds is completely acceptable then to in terms of latency maybe not in terms of uh how much it cost or what not but it's completely acceptable for Al and Bob to play directly in the main chain and not only that but the all every move is actually provable to other chains or you know they could connect it to some other chains and have some conditional payments or something of the sort um or even like cines could fetch this data directly without having to sync to uh to filecoin so in terms of road map where we stand the finality calculator has been PRD and as I mentioned at the beginning we expect to provide this uh functionality directly as an API call in the reference uh fcoin client the reference implementations of the fcoin clients um in this function call will be in the form of some sort of a risk assessment so you basically get a probability of a particular transaction getting reverted based on some standard assumptions that probably uh will provide also some options to tweak them depending on how much security you want um but it would be kind of like a FY result it wouldn't be it's final or not because that's not what a calculator is about anyways um in the case of F3 however uh we have already merged the entire design as a fon Improvement proposal uh so the design is kind of there's going to be minor changes but it's kind of like finalized and we're at the moment working on the implementation we have been working for a few months already and actually it's kind of like finished uh the internal audit is undergoing at the end of this week end of February external audit going mid- March and we're going to integrate it into the code Base by mv23 which is going to be at the end of Q2 uh in a deactivated State the code and then will be activating no later than a month from that moment uh that is in the case of lotus uh and the other reference fcoin client implementations are closely following and also uh doing their part on it and again we have done an effort on modularity um there has been some pragmatism that probably not just for filecoin but for other long chain protocols will be interesting as well but either way it's a very modular protocol that can easily be plugged into any other uh long chain type of protocol so that's it um in the end it took me half the amount of time it needed I can Reon I went a bit fast um but yeah so thank you and uh yeah now faster finality in F in Falco and in long chain protoc is a reality and you can use it as well to get finalized so if anybody has some questions now I guess I'm open for it or if not I I can't get off the stage thank you