Long-range Attacks on Proof-of-Stake (PoS) Blockchains w/ Valeria Nikolaenko | a16z crypto research

Transcript

all right good morning everyone um welcome to a16 crypto research seminar um part two proof-of-stake blockchains by our own there at nicolenko on tuesday we know about kind of like a general lance the general landscape and then today she's gonna drill down onto long-range attacks and some other issues so thank yeah so today we're gonna deep dive into one particular attack on proof of stake blockchains that's not possible in proof of work blockchain and that's i guess in my view the hardest attack to combat and there are different approaches and we'll see different tradeoffs that they offer and maybe if there is time at the end we can have a little bit of brainstorming

maybe you guys have other ideas of how this can be mitigated but yeah we'll start with the definition again of the long range attack just to remind you i will not redefine the proof of stake hope everybody kind of has the mental model in mind and then i will discuss different mitigation approaches so proof-of-stake blockchains that are typically approved to be safe when a threshold of validating notes is honest and when you violate this threshold then you lose safety and then you can create forks and and double spent on this forks so um you break the finality guarantee when you um when the number of byzantine violators

kind of go over threshold and um when i will be talking about corrupting a validator or corrupting a validating note what i will mean is corrupting a signing key of that note so what i'm saying you know just think about a signing key corrupting a notice corrupting its signing key so during the time that validator is active and participating in kind of producing blocks for consensus it has some stake locked and in case of a deviation from the protocol if it is observable typically you can slash the validator stake so um get it penalized for misbehaving for not following the

protocol and causing the blockchain to work effectively so for ethereum 2.0 for example slashing conditions can can be very harsh so for ethereum consensus layer slash validator can lose um potentially it's his own deposit so three to a hundred percent um it will immediately forcibly be ejected from the validator set and will additionally has the remainder of his coins locked uh for 36 days before they can withdraw if there are any coins left if he wasn't slashed completely so violators have really really strong incentives to stay honest while they're validating

and there's even some lock-up period after they stopped validating to make sure that if they were misbehaving while they were validating somebody have enough time to kind of collect this data and maybe present it back to the protocol to get their stakes slashed in any case so there is a little bit of window when the stake continues to be locked but the validator is not validating the chain anymore so it's just idling there lock up periods can vary for example for ethereum that's one day uh the status continues to be locked and for but we've seen much larger local periods for cosmos for example it's 21 days that the state continues to be locked so the high level idea of all of that is

that active validators they stay honest due to incentives if the protocol is designed well and let's look at kind of the lifetime of a validator so while there will have to hold some assets on the blockchain to be able to lock them up to participate in the consensus there will be some period when he holds some assets on the blockchain then there will be some period when he has taken this assets to indicate that he is willing to participate as a validating note typically there is a window before before he is let into the validator set and for example ethereum kind of does some speed limiting of how many validators can join at the time so they

create some q and you're waiting the skew to start validating so they want to make sure that the validating set is not changing drastically um in an instant so you will have gradual increase and gradual decrease kind of down some dampering of the size so the stake period is a subset of the holding asset period and then the validating period is even smaller but the validator has even if he was holding some assets in the past as time kind of progresses he can just exit the chain completely he can use an exchange and just get rid of all of his assets and kind of not be incentivized in this blockchain anymore

so after he sold his assets and exited the blockchain there are essentially no incentives for the swagger to keep his old keys that were kind of guarding all of the stake secure so when there's no incentives um yeah so those keys are going to be different just confused in the valley or could they be the same or yeah typically they are different yeah good question um there's three different keys all this taking all right so sorry the first key is just like your normal you know private key for your account i guess yeah being able to move the assets around and you're saying

so the statement key will be used only to like withdraw your state or it doesn't reduces so withdraw your stake exactly yeah so you will kind of sign with this key you will sign your staking key and then well effectively through transactions and then sign kind of validating consensus key so you're saying you'll cast your votes and it says qualities of your validation yes exactly all right so you you can compromise either the asset key and then you will be compromising the stake then the valdering key or you can be compromising the welding key along and just causing disruption to consensus yeah great question we'll discuss keys a lot

so if all validators become corrupt then safety can be violated as well it's not only that the active validators you need to grab the activators to break safety you can also corrupt historical validators so for example if your chain was growing nicely and it was not working or at least was not didn't have any deep works again certainly for nakamura consensus it can be working at the tip but usually the longest chain wins so you don't have deep forks so if your chain was growing nicely everybody was staying honest but then at some point maybe this validators who were finalizing one of the blocks or epochs

just exited the system completely and then sold their case to the attacker and the attacker now kind of got hold of all of the consensus keys it can although this is a point in the past it can still create like an alternative block and due to costly simulation of proof of state blockchain kind of continue this work onwards and grow it very fast so that it's about the same length of the honest chain and the poor user who was not online was not following maybe he just entered the blockchain he cannot differentiate between the two forks or at least that target has the potential to make it indistinguishable from the top one

let's see let's kind of discuss the keys a little bit so you can kind of map the number of validation keys depending on time and your blockchain can at certain times have a lot of validators while dating sometimes it will drop and so of course when the number of validators is really low that's a kind of nice point for the attacker to try to collect all of that keys typically the blockchains have low number of validators in the beginning so till it catches up but sometimes it can have kind of drops in the number of keys as it goes all right so hope that gives you a high level idea

and we will discuss um now mitigations for this problem so i will show you five different approaches and then maybe we can brainstorm their ideas on more stuff to explore um so the first is the most simplest one is checkpointing so the idea is that you have some centralized checkpointing mechanism and for example you can hardcore the checkpoint checkpoint being just the hash of the block so it's super small doesn't have to be the whole state of the blockchain can just be commitment to that state like a hash of the block so you can hardcore the checkpoint into

the github code base for example when everybody is downloading that github code base and they're using it to synchronize to the blockchain the github just the code base will just kind of figure out which chain you need to pick if there are any deep forks in there so for example genesis is hard coded into the github of all the clients and oh you think maybe this is an undesirable kind of because it's centralized but if you look at the kind of blockchains today it's kind of pretty centralized in terms of what clients everybody client is everybody is using for execution client the most popular is gif and it's taking about 83 84 percent of the total nodes so

80 of nodes are running yet client from the github and for consensus clients then most of them are using prism so 60 of them and that's data from january 2022 and another idea of what you can do with the checkpointing is you can checkpoint to proof of work blockchain of course and then uh there you don't have the problem of it being susceptible to long-range attacks so if you put your checkpoint there you can be sure it will not be rewarded by some deep fork um and actually some of the projects even not related to blockchain are using proof of work

chains to check points of their stuff um to put some hashes in under their accounts yeah so the problem is the top approach is kind of centralized because you um rely on the fact that everybody will be downloading the client that ha all the clients will have the same checkpoint so you either have a centralized place to download your client or the clients still have to consent on what you which checkpoints should be there um and of course the other approach has a problem that it's proof of work blockchain the whole point of proof-of-stake is to get rid of proof-of-work so kind of

you're back to the original problem you're trying to solve which is not great so are there any existing systems which do this like i think only as a precaution not like as a main part of the protocol but so some do do well actually i'm not 100 sure like for the um blockchain we're thinking of doing it because it's they created it for a ride on time but they removed it in 2016 2017. and so how did they implement what was the it was just exactly like this this isn't bitcoin core claim they just have a line to say this heart should be in the blockchain good yeah

so the genesis fly out because it has maybe some other things too so yeah that people they haven't said maybe six or seven different checkpoints at all time before they actually moved because it was heterozygous nice yeah also if there is a hard fork then and you want your client to follow one of them you'll have to put a checkpoint in there so that it synchronizes to the correct fork um yeah so joel's understanding the checkpoint exists more as a social convention rather than an automated protocol step right yeah good point i i don't know if that was clear what i wrote and i'll get a little out of it but yeah i mean i think a lot of this is my understanding anyway i've seen some

projects that they don't have like a sort of an automated checkpointing system but they sort of like manually put them in code or uh you know like clients enforce them anyway and they're sort of established by some undefined like human level protocol basically which i think is mostly because people don't want to sort of admit that this is what they're doing yeah great comment thanks joe yeah okay let's discuss the second approach for key evolving cryptography so it's a good practice for validators and

essentially for everybody on the blockchain to kind of rotate their keys once in a while because the attacker can kind of be slowly crawling to get your key there and if you rotate it you kind of push that attacker back um also yeah but you need to be careful because the moment you wrote this time when you rotate your key you make yourself a little bit vulnerable to attack um so rotate i mean um you have you sign a transaction that basically moves you from this key to a fresh key yeah you just change the key yeah right and let's see like if say the set of values are is growing and at some point you

have you're compromising say two values out of the big set then although you cannot attack the chain at this point if validators were not rotating their keys that immediately means that you're compromising the values from the sets prior to that so if at some point you start getting say two-thirds of violators compromised then that's the point when you can start forking the blockchain so although it seems like you're not compromising enough if the welders were keeping the same keys compromising them for the last epoch is essentially the same as compromising them for some previous epoch where you would have a super majority of them

compromised and can work so that to mitigate that like people were proposing to use key evolving cryptography so and you will rely on the assumption that honest nodes will regularly rotate their keys and honestly forget the old ones so you can either do this with on-chain transactions when you sign a transaction directly that kind of moves you from public one to public e2 and secret key two is completely independent of secret key one but if that's expensive if you don't want to submit a transaction pay the fees for every key rotation

you can use some clearer tricks around time evolving secret keys and the team from algrand was proposing the pixel signatures the idea there is the public key stays the same so you don't need to rotate it because only the public key is their own chain so the public key is the same but the secret key kind of is evolving with time so with every epoch number you're kind of shaving a little bit of information from your secret key so that it starts to be more and more restrictive and you cannot go backwards so your secret key one is the most powerful from that you can evolve all the next

ones but you from secret key to say you cannot go backwards and figure out what was the secret key one and the signature that you verify it also will take an index i so you cannot produce um say sigma one using secret key two that will not be possible now so you cannot kind of go back and compromise kind of forge sigma one using c secret key two so that's a very nice trick i know they were proposing to use it at algorand i don't know if they ended up using it it's kind of um quite elaborate scheme it involves some hierarchical hierarchical identity-based

encryption based on bls signatures but anyway that's a nice approach if you're not comfortable with the kind of complicated cryptography you can always just ask evaluators to rotate the key frequently okay so the problem of course with this approach is um it's incentive incompatible so why would honest validators forget their old keys if um you know if there is incentive for them to keep the old keys and then when they exit the system kind of sell this old keys to the adversary then it's unlike well it's a little bit maybe naive to expect all of them to behave honestly and just keep forgetting information especially since you cannot check whether they

forgot the information or not i think the way i think about it it may actually be a little bit of a pain to truly delete old keys and so it's just that it's not so much that they want to keep that it's just like they don't want to put in the effort to make sure that they don't keep them you know yeah exactly like even if you like wipe out the memory how can you be sure that it's been wiped out there is an argument for why you would want to erase your old keys which uh i haven't seen maine very widely but i think it's pretty simple if people believe that you're erasing your old keys then you're not a target it's kind of like when you park in san francisco and open your glove box to show that there's nothing to steal

because if people break into your system to steal your old algorand key they might steal other stuff too you probably have like pooled things um so like if you don't want to attack the system there's there isn't like at least some incentive if you can convince other people you've erased your old keys because then then you're not a target yeah i guess the question is how would you convince somebody that you've erased it how can how in your analogy kind of how do you show that you have nothing in the trunk of it yeah i mean that is i mean like fundamentally we don't really have any way to do it like you you could do it using sgx or something like that uh

but yeah there isn't like a cryptographic way to prove you've deleted anything yeah yeah and interestingly a good point that this gx can help if you willing to rely on your trusted hardware assumptions okay so that's the second idea and it kind of it's not perfect as well so the other idea is how about we keep everybody online and if everybody is online all the time kind of checks in with the chain very frequently there is no way you you're gonna fool them into believing some deep fork because they've been just following the correct work all the way um so for example ethereum consensus layer

which is a combination of casper finality gadgets and lmg ghost fork selection rule that i was describing in the last talk in their paper they also discussed long-range attack and that's exactly kind of the approach that they propose just to cite them they say in the paper each client will log on and gain a complete up-to-date view of the chain at some regular frequencies say once uh per one to two months so that's a very strong assumption to swallow red because there can be clients who never been active on ethereum but who want to join like they need to figure out what's the correct chain or at least maybe who are the active clients who've been monitoring

this chain and then you're back to the same problem um yeah so the problem is that clients can be sleepy and you still want to give them some way to sink to the correct chain even if they were sleeping um okay so the fourth approach is finality gadgets of the nakamura consensus so the casper ffg here is the finality gadget and some people kind of think that they help with long-range attacks somehow but i'll explain what they do and you'll see that um they're solving a different problem actually

so the examples of find kind of some prominent finality gadgets is of course ethereum consensus layer which is casper finality gadget um and grandpa that's a finality gadget on top of polka dot uh nakamoto consensus so their idea is to use validator committees to vote on e-books to finalize them so you'll be just running based bft chain on top of your longest chain to guarantee deterministic finality so casper yeah let's look at casper protocol very briefly like just i'll describe the high level idea um

it's based on tender mint although maybe reading it it's kind of hard to figure out what what this consensus protocol is but it's essentially tender tendermint um each so in lmd ghost and the underlying nakamoto consensus you have each validator vote once per epoch so validators are shuffled into committees and in each slot a leader is proposing a block and the committee of that slot is voting for the bloc so validator is assigned to exactly the member of one committee he can be at most one leader there so so sorry he be assigned to a committee and then he can be selected as a leader from that committee or not so

in any case he is voting once per epoch and casper so it's voting on that block and casper in addition to that voting it asks the valder also to vote on the previous epochs so you are trying to finalize the previous e-books and together with voting on your current blog you will also be working on what are the epochs that you believe should be finalized so each validity will be submitting two votes there's essentially thundermint votes if you remember how tendermint works one vote will be saying that i want to finalize this epoch in um kind of in form of a prepare phase of

the tendermint and some previous epoch that already collected a quorum certificate of prepare votes to commit it so just to remind you can the tender mean has the three stages where the block is proposed and this block proposition proposition in our case is epoch proposition and that's happening from the underlying consensus layer so the consent sorry the underlying uh nakamoto consumption it proposes an epoch to finalize and then all validators kind of vote in two stages they submit their prepare votes and commit votes just the difference here is that it's a different committee that is

voting on the epochs so this committee this last committee here is voting on epoch i plus one and then the committee after that one will be casting a second vote on this epoch so you are changing the committees that are voting uh so there's just a nice pipelining idea that they had but actually i think the casper papers from 2017 at least when they had the original idea and um that's why it's kind of very similar to tendermint but i don't think maybe they've reconsidered maybe there is a way of just thinking to simplify their protocol with ideas that um appeared in hot stuff because hot stuff was later and hot

stuff has this really nice pipelining of uh of voting so that maybe you don't need to vote twice you can just vote once and this kind of help helps you confirm all the previous epochs so anyway um maybe there is a way for improvement there for casper protocol to simplify their voting mechanism all right but you see that still you have this problem that if the committee if the old committee is compromised your bft gadget does not guarantee you safety so you can still fork the epoch voting and create an alternative fork of epochs so you have to rely on the committee

staying kind of honest in perpetuity so you're back to the same problem so overall i just want to say that this is these are great ideas and um but they solve a different problem so it these gadgets are turning probabilistic finality into deterministic finality but it doesn't solve the long-range attack yeah and then the rest of the talk i will spend kind of describing the paper that we wrote with sara zubi and george danezes when we were working on the dm blockchain was called no uh yeah what's called different names but dm was the last one um

so we were exactly trying to figure out if there are better ways to prevent long-range attacks um and the idea that we had that kind of summarizes winkle in one sentence is make users vote inside their transactions on the current state of the blockchain so you not only have kind of violators voting your bft consensus and dm was bfg consensus but you also make the users who participate in the system also participate in your consensus so we'll see how it plays out uh it will be easiest for me to describe the protocol uh on top of bft consensus that has deterministic finality

but you can this doesn't have to apply to bft consensus only it can also apply to bfg consensus that's a finality gadget on top of nakamoto so you can add this on top of on top of your finality gadget for example if you have motor consensus underneath or you can maybe adapt winkle to directly vote directly work with nakamoto consensus but we haven't done that since dm was a bft blockchain so we're focusing on bft blockchain so um yeah let's start from the beginning so blockchain is you start with genesis and then you produce blocks of transactions your block

is the parent hash of the previous block and list of transactions and then validators kind of work to finalize this um block and at the end they get some certificate that think of it as an aggregate signature that is a proof that they have all consented to to append this block to the blockchain and the single block commits to the full history up to genesis because it contains the part hash so it has this nice chain but the purpose of this talk will be focusing on epochs instead of blocks so when i show you this rectangle with a list of transactions think of an ebook of transactions because anyway the bfd

blockchain orders all of the transactions totally so you can just think about these blocks as epochs so values work on finalizing the next epoch of transactions and they stay honest when active so the typical bft assumption is that you have a three f plus one valid leaders and that most f can be cropped so while there is kind of figure out if they want to consent on this block and then they produce a certificate they move to the next local epoch and they so that's how they evolve the chain so yeah

well think of validators not the rising ebooks here so while there's effectively just the set of public signature verification keys as i was saying and the certificate is an aggregate signature and validators are typically implied by the previous e-book so you so validators notarizing through the first epoch are retrieved from the genesis so the genesis will just define okay this is the first set of values that we're going to start with and then from the previous epoch you retrieve kind of the next set of validators that will be finalizing so moderators to finalize e2 are retrieved from e1 epoch and so on and to finalize e3 you need to retrieve violators from e2

yeah and that was explained in the beginning that if everybody is honest uh you have a single chain but if others um past violators are corrupted they can fork and create an alternative chain that will totally confuse the user about which is the correct one so we will i will oversimplify a little bit and that's what we do in the paper uh in that we view transactions at are simple money transfers and that makes the overall model much simpler but it can be adjusted to work with more elaborate transactions as well so the transaction will be just of the form at the sender a

receiver and the amount and the signature will be a signature of the sender on this triple so genesis block assumes it gives some initial allocation of coins between the accounts and an epoch of a transaction modifies this allocation right so if you have transactions that sends a one coin from alice to bob signed by alice you your next state of the database will be that alice will have one coin plus and one will have two one point more and uh yeah so you process your transaction sequentially kind of redistributing the coins uh between accounts okay this is

over simplification of course uh most of the blockchain have some scripting or programming language that makes it a little bit more complicated than this model but we'll be focusing on this model just to understand the high level idea so let's see what the corrupt values may do so when they have corrupted the valid reset and they're trying to create an alternative fork what they cannot absolutely do is they cannot forge signatures from honest accounts so if you were for example if you had your funds in genesis and you were not moving them anywhere and you still keep your

account key to yourself the adversary will not be able to suddenly steal your funds um so it can not forge transactions from honest users but it can definitely censor it can drop transactions of honest users and for itself it can double spend it can create new transactions from corrupt accounts so it's uh kind of good if you're idle then and not transacting then the attacker will not be able to do anything to do much with you but if you say big exchange and all the time you would have a lot of money coming in and a lot of money coming out and that's

happening in every epoch then the attacker can just attack your exchange by censoring all the transactions that were coming in and so it will very quickly in his alternative work kind of deplete all of your funds all of the funds of the exchange so the idea is to change that the whole idea of wrinkle is to change the transaction format and to also ask users to vote on the last epoch that's sort of a natural thing i feel to do i'm a little bit surprised that none of the blockchains they're thinking about doing that but it definitely will kind of involve a little bit more work on the validator side because now

they will need to make sure that the last epoch that the transaction is voting on it conforms kind of um with the with a fork at which you're finalizing the transaction so you need to make sure that the transactions in the epoch are voting on some ebook that was there on this chain on the same chain um so when the transaction additionally kind of has this last epoch it will be voting with the sender account on this epoch so be like a second layer of consensus or voting happening where users themselves by just transacting on the blockchain will be voting on the

state of the blockchain so it's a little bit kind of uh maybe hard to implement because it will also involve changes to account states for example if you're a receiver and you're receiving uh money with different votes you need to kind of to keep track which of your coins have been voting for which ebooks and so as a result coins will sort of have a non-fungibility flavor start having this non-flangeability flavor and that some points will be voting for one ebooks and some coins will be voting for other ebooks so just to give an example here

suppose um there are three accounts alice bob and charlie each of them has one coin and this coin is voting on some first epoch e0 then if the transaction moves coins from bob to charlie save from bob to charlie one coin moves and uh its vote is e1 then the coin moving to charlie will now be stored in charlie account but it will have a different vote from the other point that charlie has and then if alice bob sends bob one point will also get the vote on the coin updated um yes think even the first one i think solana does something like this it's called proof of history and so in your transaction you can either make the

block cops or whatever off the previous block so i think i think i don't know if they use it for consensus but they're doing something along these lines you're just saying somebody's right they call it the history i found it really weird but then it doesn't make more sense uh the second question was what happens if alice's things coined to yourself so now sanji wallace says to another account that belongs to her what does that mean she can update her vote this way yeah yeah so that way she's sort of just uh you know voting but it doesn't cost for anybody to do that yeah exactly right you consider using transaction fees for this so the more transaction fees you pay is you're the weight of your vote uh

say it again so you would be depleting my understanding is that if i send one coin charge that one coin is sort of used for the vote yes no no actually sorry maybe i wasn't explaining it right but the whole account of a sender will get the um their coins updated and only sends one to charlie her all hundred points will get updated to that vote every time she yeah every time she sends a transaction she kind of votes on the with all of her stake have you consider using transaction fees so there's a cost they always do that so instead of using your balance you can just use maybe you have to pay a dollar

as a transaction fee and validators then you can add a real cost to your vote oh yes you think of lowering transaction fees if the only thing you're doing is just updating the vote what i mean is that like right now the move is weighted by the balance have you considered the vote just being the quality of transaction fees that they pay oh but that will be lower than the balance well it just means it causes them money to vote because right now it doesn't cost them anything necessary well you still have the transaction fees right oh you're saying that the more transaction fees you pay the kind of the stronger your vote is

i don't know if you can save it yeah maybe that's a good idea like to express how strong you believe the chain um yeah we haven't explored that but the way there is i know maybe i'm not sure many users will be willing to pay transaction fees to kind of strongly express their vote they would rather probably well there's just a lot of doing this anyway so the theory maintained 10 million dollars a day or something on fees basically transaction fees would turn

into this kind of non-transferable governance token effect so yeah exactly um cool can i could i ask him maybe i'll get to this but why doesn't a long-range attack apply for these types of votes too because like uh seems like people making transactions once they've once they're not using their keys anymore they also be compromised right yeah absolutely you're absolutely right i'm gonna talk about that next so just to maybe briefly uh briefly say that the stake of the overall system is of course

protected by many many more keys than you have on the valdera set and so the argument of course that you are not like solving the problem completely you're just making it better so that more keys are protecting now the blockchain not just validators keys but now also the user's keys but i'll get to that with some numbers that's a good point um yeah so coins will be voting on apex so if you consider the state of the accounts on your last epoch you will just see what the coins are voting on kind of retrospectively and you will see which and this transitive like if you if um a coin

is voting on an epoch after um after the bug that you're interested in you you will also count its vote towards the previous one so kind of if you are voting on some subsequent epoch it kind of transitively translates to the voting on all of the previous chain so you will see which of the epochs gets about two-thirds of the votes and this threshold is flexible we are showing that maybe it does have to be two-thirds depending on the assumption that you want to have but you can also go with bft assumptions and consider the checkpoint finalized if it's voted by two thirds of

coins according to the state of the accounts on the last epoch cool so essentially we are kind of showing a security theorem saying that if the adversary has a max f fraction of stake to begin with and that's the accounts that it has compromised and can double spend from and at maximum some s take moves within an epoch then if if you can bound the this f plus s over two um by one third then you can prove that the adversary cannot accumulate more than two thirds of stake to create a checkpoint on the

fork so for user to see which chain is the correct one it will kind of observe the chain for a while and if it's not producing any checkpoints or if it's if it doesn't have any checkpoints at all and the last in the last interval that's sufficiently big you will be suspicious of this chain and think that you are synchronizing to the wrong one so the adversarial uh chain will not be able to produce checkpoints and that's kind of the the core secure security argument the core theorem that we prove and for in if you're attentive enough you have this

additional assumption that the maximum s stake moves within an epoch and that's essentially to prevent kind of this exchange attack that i was describing so if you can reroute by censoring transactions if you can reroute too much stake so that you end up with a lot of stake at the end you can make it so that you have more than two-thirds but if you bind then about the number of stake that moves within an epoch uh you should not be able to do so but of course that will require um so first s is really really large and it's super unlikely that any chain will within an epoch have like a sort of

stake moving but if you still anticipate this scenario then you can potentially just end the epoch a little earlier and then start the next one so what the approach is to bound against like your vision that you would want to modify your protocol so that you could have an upper bound on s or is it more just kind of empirical i think you just sort of see how much what s was in hindsight and then conclude what the security was you're you're asking about how in practice will you pick yeah like how would you get any control grass like in practice yeah yeah

so in practice i guess you will pick your assumptions with which you are comfortable like how many byzantine notes you want to tolerate and how many sleepy notes you accept i think we just think of it as like same as that and then yeah if you're kind of your ebook starts approaching that as you can just uh stop producing new blocks within the cpu or maybe you can do something with transaction fees that they will climb up and kind of disincentivize people to submit more right an transactions at least you can observe from watching yeah okay so yeah so just to summarize the

security theorem saying that checkpoint and ebooks cannot be forked so we're kind of changing the assumption we're making it a little better um so before we were relying on violators to stay honest and i think perpetuity was staying honest and alert and now we're changing that into users staying honest and alert and the argument to joe's point is that the valdez are typically up to a thousand sometimes up to two thousand but in any case it's not a super big number and all blockchains users can run from million to a billion so usually it's a much much bigger population and you have much more keys protecting users

funds rather than what kind of validating keys i mean the pushback i would give you on this point is that the number doesn't really matter you care about the distribution and there are like a coin base i mean has millions of those keys right like there are like really concentrated places that have a lot of them i mean hopefully those are also places with really good security that are hard to compromise but i guess it's not like the fact that the number's bigger doesn't make it obvious to me that it's harder to compromise enough of them to comprise a majority of mistake yeah yeah great point and so we were

trying to study the distribution of this keys and how much stick they uh have and i'll show you some graphs hopefully you're just talking yeah it's perfect you're like ahead of the talk so we those experiments that we carry this paper of 2019 uh this is pretty old of course it would be super nice and somebody redoes the experiments i i bet the just overall dynamic of the chains have changed a lot in the last three years but that's the graphs um from 2019 that i'm going to be showing you so this graph shows the fraction of stake and then how many keys are

protecting that stake for bitcoin which is red on top and ethereum and the bottom um so two thirds of stake for example in bitcoin is protected by uh 15 000 keys and an ethereum only 800 keys i know maybe the numbers have changed drastically i'm not sure but that's what was the state in 2019 and so it was really nice that kind of our paper was allowing flexible threshold thresholds and you can kind of balance your byzantine assumptions with or whatever other bounds say what things you have to bound so you can go you can kind of raise your threshold um from two-thirds to something higher and

of course if you go higher for example 90 percent of the stake is protected in bitcoin by 125 000 keys and ethereum by 12 000 keys and then if you go higher of course that starts climbing up really really rapidly but would be nice to see what situation is now so of course the more users stake votes the higher is the assurance so you would probably just analyze this graphs for your current blockchain and determine your threshold to make sure that you have protection of more keys than your validator set

and then we're also analyzing wrinkles efficiency so we were saying okay let's take ethereum a bitcoin and see how quickly will they be checkpointing if we have every user uh vote on the latest available block and this graphs a sort of indication of how frequently the stake is moving in the system whether because if stake is moving really really fast then you will have um time time to checkpoint uh to be really low if stake is idle and it's not moving it's not voting um then the time to checkpoint will be really high and of course in 2019 i

don't know people weren't transacting much low and for example for ethereum blocks were checkpointing about 200 days and for bitcoin about 600 days so that's how much it takes for two thirds of the of two thirds of the stake to move but of course you can also add incentives if you are to switch to wrinkle and reduce wrinkle you'll have to maybe incentivize people to vote more frequently so maybe they are not moving their funds but at least they are a little bit more active on the blockchain if you want to incentivize them to support the security of the blockchain so that with incentives you can get these numbers to be lower but without incentives of course these

numbers are too high uh you cannot afford your values to stay honest for three years to get a checkpoint that's too long and so our idea was at that time to introduce delegation and you can i guess the argument here is that there are a lot of cold wallets there there's a holding funds and they don't want to touch their keys at all never like they have it uh stored somewhere securely and they only in kind of exceptional circumstances they want to pull it out of the storage so but typically these cold wallets also have some worm or hot wallets that are transacting more frequently

so maybe just a cold wallet can designate a hot wallet to vote for it um and so it would be natural to have this delegation mechanism where more idle accounts are delegating to more active accounts um but of course the argument is that you now start adding back the centralization but with proper economic incentives you can make sure that your delegates are not growing to be too big like not everybody is delegating to coinbase or something so you will incentivize people to redistribute the delegation but of course if we if we had to take the most frequently transacting accounts

and use that as our delegates then depending on the number of delegates that you get that you have um the uh the time to checkpoint will drop significantly so even for a million delegates those are the most actively transacting accounts on bitcoin and ethereum your time to checkpoint will be less than four days which is uh which is great because you can afford probably to keep violators take locked for four days and just keep them honest while being incentivized so that you're you have enough time to produce a checkpoint overall what winkle is doing is it's um

building on top of validator consensus layer where you need to have two sort of values to vote at most one third can be byzantine but that consensus layer is kind of complicated it's interactive it's computationally intensive the validators should run expensive nodes should have some infrastructure usually so and this consensus layer is safe while validators keys stay secure but on top of that you can add user-based kind of consensus or checkpointing with flexible thresholds you can play with the number of votes that you

want to collect and the byzantine threshold that you want to tolerate and it's very simple for users it's not interactive the only thing they do is just they include an additional hash inside their transactions to vote on some ebook yeah and users don't need anything else they don't need additional infrastructure probably each user has a good understanding of what is the current chain because i would imagine users should be syncing with the chain once in a while just to figure out how much money they have in their account or what's the current value set so that they can verify the signatures on their transactions from the sud and such so users should already have some idea of what the state of the blockchain

so maybe it's not asking too much for them to include this hash of the epoch inside the transaction and yeah and this with this new layer the whole blockchain stays secure as long as users keys keep it secure and arguably it's like philosophically a better model maybe you don't have just values guarding the chain but you also have the whole population of the blockchain kind of helping it to stay safe yeah to summarize um the main part so we were discussing broad range attacks and we were looking at different approaches to mitigate them so checkpointing

is done in practice but it's too centralized key evolving cryptography i guess it's the best it's a good practice for any blockchain to implement um but it's not incentive compatible so if there are strong incentives to sell the key afterwards to the adversary then you might not be honestly deleting your old keys so that will not help but that's definitely a good still thing to have keep everybody online seems like a recurring theme for protecting long-range attacks because in wrinkle also you have users kind of to check in what's the latest state of the blockchain so either way they're also kind of keeping themselves online and we're also discussing finality gadgets that are helping the nakamoto

consensus to have the deterministic finality that bft gives of course the time to finality will still be the time to deterministic finality will be very large for this combination of nakamoto and finality gadget so so it's not a way to kind of speed up finality to speed up finality you need to move to bft but that's a way to just make it deterministic instead of eventually and then we discussed wrinkle that kind of argues why it's a good thing to maybe have a user-based consensus on top of your blockchain yeah that's all i have

um and maybe you can discuss a little bit if people have ideas about what else can be done so are people looking at pdfs at all to sort of help with long range attacks or yeah i think they do the problem is kind of with vdf you can still pre-compute multiple forks of your pdf and then kind of keep one of the video forks secret kind of with selfish money approach and then release it when you

want to attack so tim are you suggesting the idea that like you can you can tell a fork hasn't existed for very long because it doesn't have a long vdf computed on top of it that's right it's almost like using bdf is the proof of work surrogate except it's sort of uh certified not really a proof of work it's like a it's a time stamp surrogate yeah there there's a there's a paper that does a whole bunch of formal modeling about this it's called like a computational time stamping um [Music] i'm not sure anyone's seriously trying it and i'm not sure it's a great idea just because the like the attacker's speed advantage

kind of uh over time will always be able to make their chain look longer than the honest chain if you assume that they have like some 2x speed up you know or some non-trivial speed up over the honest parties so uh yeah i think it's a it's a good theoretical idea that doesn't it is not that attractive in practice the other ideas are kind of a bit naive as well maybe you can keep rewarding old validators give them a little bit of a diminishing reward maybe to maintain security to just keep them incentivized that's not a great solution or maybe you can do some kind of

perpetual liquid staking so that their stake kind of continues to be subject to slashing forever but you can still get some liquidity through liquid staking but i think maybe yeah true definitely most of the

projects just uh think they're gonna solve it somehow with social consensus if this attack arises yeah we are still to to see how this works does none of the existing group of state chains include anything in protocol designed explicitly to protect against long-range attacks is that right or like you said they all just are sort of implicitly assuming that it will be equal to the social player if it ever happens yeah most of them well they had sort of mitigations which is key evolving crypto for checkpointing but none of them is perfect and and you see that winkle is also kind of it it kind of

makes your assumption weaker and that you now rely on the bigger population of keys but it's not solving also if if all the past users have exited the chain for some reason and they have an incentive to sell their old keys then you can also kind of fork user consensus as well so definitely people are concerned and trying to figure out how to solve it and they just have mitigations but none of them solves the problem completely but in general i'm struggling to have an opinion about whether this attack is based mostly theoretically or whether you know this kind of thing it was theoretical then i'd feel more comfortable with this idea that i was

like okay we have this ad-hoc backup of like you know social checkpointing or something whereas if we thought it was like an inevitable sort of attack then but then starts feeling like you might want more in protocol protections against it yeah do you have any thoughts on that like yeah did you expect to receive attacks yeah i definitely had like a concrete thought for an attack just i didn't want to feed it to anybody to implement but oftentimes for example ethereum consensus has access to validator keys so your execution layer because you need slashing to be done there your execution layer has access to other keys and so in principle somebody can write a

smart contract that was will be saying you know here is a bounty and you can claim this bounty if you provide a secret key to the smart contract now you can not provide it in the career but you can encrypt it and you know prove that it's correct so you need some complicated cryptography to do that but it's not impossible and you know there's such there's some smart contract with a large bounty for collecting other keys you would imagine maybe validators will just use it especially if they want to abuse the chain um and that's threat right i don't know how they will be putting this contract down for example

like so for this thing i like validators selling keys though like wouldn't they then lose like any rewards they got like on the main chain like if the like forks the chain or something while you're detecting like they also stand to lose from losing whatever things they've like done right yeah right well yeah you need to trust a little bit um you have to trust the attacker to not attack during some windows so that you have the time to cash out yeah so yeah there is some trust relation will be there i think i think if you do like the way

cool stuff i knew uh you didn't transact with this board it might be interesting for combating okay trying to call that selfies minded so like the problem is like a short-term range attack in a way that may be interesting to see if i could talk with stoppage mining in general ah your idea of kind of waiting by transaction yeah the transaction fee then you pick the one with the heaviest fees then maybe that could also cover selfish mining because now as a selfish miner i'd have to

pay you know equal or more transaction fees to beat them so it's not just i see interesting so you're saying the selfish minor will have to pay more yeah because in 1.59 like the validators or the popularity and there's a minimum payment students the police office now yeah yeah that's definitely an area direction to explore transaction fees we haven't talked about it much sounds good then um well send any ideas if you

get one my way and we can see if we can do something better here [Applause] you