Consensus in blockchains: Overview and recent results with Christian Cachin

Transcript

thanks a lot for uh the invitation and for the opportunity first a bit of personal history and a bit of history in the field who remembers what this is okay what is it you don't know Victor shupa said he doesn't know it's IBM from the mid90s uh who started the EB business wave because IBM almost collapsed in the early '90s and then re rebound and came back uh by inventing and pushing e business I got this from the official IBM uh history website where they claimed they that they focused on this for the next decade at the time I was just joining IBM research IBM was inventing e business at the time and the researchers at IBM were making it secure and secure e electronic

Commerce on the internet that meant first and foremost that you could not be cheated by by the potentially malicious Merchant and the merchant could not be cheated by you the potentially malicious customer so it's about a fair exchange right you have to pay you want to pay on the Internet only when you also get get the goods right and this led to research at the time like optimistic Fair exchange optimistic Fair exchange is a is a is a secure protocol but it is requires a third party because it's otherwise if you're not optimistic uh you need many many rounds of interactions for a fair exchange then if uh this is optimistic it means that if one of the party cheats you have to go

to trust a third party and this Tross the third party will will resolve the exchange or the dispute and this is a cryptographically sound version of doing this and uh then there was just the question of how to actually implement this just the third party in the real world and that's when uh we started to look at Distributing this trusted third party right and along came work our first work joined with Victor also here and Claus gav on Byzantine agreement because we wanted to make this trust the third party more secure and that's how I started to do distributed protocols and consensus protocols uh and and remember this was around 2,000 consensus protocols at the time already had a

longer history we had looked into what was available what was done what was actually State machine replication this was not clear to us at the beginning what is the difference between State machine replication and and consensus uh and so we realized oh there's a deep history there has been Theory research from the 80s onwards actually also at IBM at the time the 1980s papers Olaf and strong were also an IBM researchers but were lots of theory and no systems and not even implementations of prototypes yeah and then um around 2000 this was there was a new generation of researchers we were perhaps also part of this approaching it from a practical Viewpoint the MIT uh Lis barbal lisov and Miguel at MIT called it practical

Byzantine fault tolerance I was the first protocol taking these consensus ideas uh into a somewhat practical thing they started to build a system okay they built a system that was actually a prototype system an academic prototype system and in the following decade from 2000 2010 there was like a little arms race who can make their pbfd uh version a bit faster and so on but there was no one interested in the actual system in practice okay and at the end of the decade we had a workshop at the distrib Computing conference where um researchers came together and were wondering why nobody actually was using the thing okay because we had this great research and nobody was using it and it

was really depressing yeah because we said uh who is going to use it has the moment for widespread deployment actually arrived or not there was even uh better KET office also still working on this demand I said H wrote a summary of it later industrial software it tends to ignore bft related research and hence for the less consistent crash tolerant and simpler versions and it was it okay and we were all depressed and said going to go something else okay little did we know that at the same time Satoshi had just mind the Genesis block yeah so the question in the audience that's exactly what I was going to ask did no little did we know about Satoshi at the time nobody mentioned Bitcoin at this paper

at this conference and nobody knew about Bitcoin I think nobody knew about k and this is what I'm going to say nobody in the research field knew about Bitcoin until maybe 5 years later because from a cryptographic Viewpoint the cryptographers were more like oh there's a payment protocol a secure payment protocol but we can we can trace every single transaction so it's trivial they're not interested and uh the the the the distributed computing people did maybe not understand it or maybe they would have said it doesn't not formulate in a way why should it do consensus it's probabilistic and synchronous we know how to do this yeah so nobody was interested however the model became then viable with the cryptocurrencies and the reason why this was not used before is

just because it's a model right it's an assumption and a security system does not make sense unless your uh customers as so in practice a security system does not make sense unless your customers also believe in the assumptions that are underneath that they're also buying to your assumptions and that's what the cryptocurrencies have done make these assumptions viable for many people in practice and to come around full circle now we're working again on making electronic Commerce more secure but in a different way then it was Enis envisaged at the past and one could definitely also give a similar story about why the original digital cache schemes from CH in the 80s and '90s didn't make it and now there are more elaborate ones okay

so today um we are in full swing in more research but also deployment in practice in consensus protocols so and the rest of this talk on the main body of of this talk I would like to go here through a list of models that I just discerned today or I Define today in which uh you can you can categorize uh the protocols that are used in today's blockchains yeah it's not not so much academic but more from the field from those models that are actually used going back to the Moto that the models are more important than the actual protocols and then I would like to focus on two models the generalized TR trust model and also on the asymmetric trust model and uh and

and discuss those yeah so threshold trust symmetric threshold trust is what is perhaps best known this is the model like the academics started they said let there be n nodes and some number F of them are faulty yeah and this is the model that we used we have used most exclusively for maybe 25 years or 20 years in consensus research which is a good simplification of uh what one can do but today there are other things yeah um there are certain issues with this model that are have not have been found not to be the case in the cryptocurrency world for example so there are nend noes and we say some number of f of them are

faulty and we need n bigger than 3F for the asynchronous protocols or for the partially synchronous protocols we have textbooks here is my favorite textbook textbook on the topic so it's all very well established and there are some chains that used this model or actually actually has have started to use this model when they were at the outset based and they based largely they based their uh prototypes or their actual deployment and practical softwares their production softwares on the existing literature I would say tender is Cosmos is part of this not that they just literally took it from the textbook but they were definitely coming from the corresponding academic environment internet computer hyper Fabric and some others are also

following this model where they're just simply votes yeah this model has also be called proof of authority sometimes uh because you have to assign these votes and of course the system could uh replace the set of Voters as it goes along but it's clear who has there's a global notion of who has the authority to um vote here there's a model that I would call generalized trust it's a model when you are departing from The View that everybody has the same influence and it's even more General uh than saying you have weighted votes it's more General because you can say either three of those over here plus one of them or two of them plus five from the 700 over here have the power to approve

yeah these models have been looked at um under the topic of generalized Quorum systems for example these models have been studied very deeply in Secure multipod computation where uh one has shown that one can do Secret sharing from it and from models that are formulated in the particular way I'm I'm going to focus on this uh later not yet here um in the simplest case you could just have a monotone Boolean formula that enumerates uh your quorums your your power sets or or also describes the comp the complement of your quorums which would be the parts or the the the the

collusions you're trying to tolerate which is called a fail prone set then and together they make up a fail prone system so in this case here we have a heterogeneous uh model where not all nodes are the same some of them can be more important in certain combinations it has been recognized all along that there is this concept of Byzantine Quorum systems from uh the '90s also Maly Ryder and hton maer formalized this under the notion of a Byzantine Quorum system interestingly this is not used by any cryptocurrency not used by any consens protocol this this type of model yes question well I I I think Yehuda lindel's company at coinbase is now doing oh Victor Victor yes Victor says

that yo the coinbase uses it and I was also at his talk the other day so I'm going to mention exactly the access structure they're using in the second part okay they're using for threshold cryptography actually not for a consensus protocol it's used for a threshold cryptography so this model is also playing into threshhold cryptography right yes thank you for the comment yes was this the model in Stellar too is this the model instellar no the model instellar is uh not a symmetric is as is the model inell is not symmetric okay it's asymmetric the model inell is asymmetric uh the model installer is you have your quorums and I have mine and maybe have consensus and maybe not symmetric means everybody has the same oh okay this is asymmetric this

is you see Stellar here as well Stellar is listed here Ripple actually started this I'm going to focus on this also more later take a step back this here is a quorum system okay it means strictly speaking that we can have we are prepared we all are prepared to tolerate certain nodes from failing like two two red ones here yeah the special case of of uh two uh being less than 7 by 3 divided by three in the Stellar world in the asymmetric world every participant now comes with their own search Quorum system they I've only depicted three of them here instead of uh the seven that I

would have needed actually I can also move things I can show things here there are only three rings here but in principle every seven every one of the seven participants would have to declare such an assumption on the Trust on the others it's representing a certain social trust and it's also heterogeneous and it's also asymmetric yeah Ripple and Stellar start started this and I'm going to focus more on those in the second part of the talk so um and I'm going to leave them for the moment okay and I'm going to go on towards other chains and all other models that have been used by other chains there is a model where you are not asking a strict subset that is

somehow derived from a majority or so for votes yeah and this model I would call it unstructured voting or probabilistic voting where we are not getting votes uh and and decisions with certainty but only probabilistically the Avalanche protocol is maybe the prime example today of this type of protocol and uh we heard it talk yesterday also about this so maybe I'm not going to take say too much of this except that the these protocols interestingly they have come with a dag most often it seems to be not strictly required that you use a Dak for this type of protocols but initially the aalan protocol used the DC the early um uh I think it was called

Phantom and Phantom dag later from from uh zolinski and Zohar and so they used similar ideas uh unstructured voting probabilistic voting asking some some number of other nodes for their opinion and then switching to the other opinion and getting not getting the strict overlap guarantees of quum systems there has also been been the the Iota tangle which is another dag based system that has been around and is also a chain so these systems um also have have a long history I think they are probably the least well understood today they're not that prominent either uh compared to the uh if you would take the market cap of the cryptocurrencies and and divide them

into the type of protocol assumptions here then they're not uh not among the most prominent ones but they're definitely interesting for their features the technical features you know but I haven't mentioned it yet that in the cryptocurrency world we want to be permissionless right the protocols I have mentioned so far they were permissioned in the sense that there had to be a Global Knowledge on a list of notes ahead of time this is certainly the case for the protocols that uh the researchers started with the BFD protocols so everybody has to know who can vote yeah and this type of assumption uh has not been very like say favored in the cryptocurrency world because you wanted to be able that

everybody can participate in a protocol just like Bitcoin allowed yes and that was a question so in in this model so the quum is defined on the Fly that parties are participating and then there will be a at one point they'll do a random sampling and then in this case I think there wouldn't be a quorum but there needs to be a list from whom you can sample uh there needs to be some kind of membership thing so that you know whom to talk talk to and I think this would this is typically established by uh stake nowadays Yeah by by holding of of cryptocurrency among a validator noes and that brings me that will also bring me to my next uh uh types of families of of assumptions yeah so in the in the

previous case it felt more like a mechanism the original model is let's say in the previous case yeah you're right by saying I'm not clearly distinguishing here between assumptions and and protocol structures and it's it's by choice yeah it's by choice because um I wanted to get an overview or present to you an overview of how we could understand these protocols and if you now say Avalanche protocol that uses some probabilistic voting thing has the same trust assumption and the same mechanism as say the actual tender Min which uses voting with with Stak it's both elements right I am going to focus now a bit more on stake stake is hold holding of

cryptocurrency uh that makes you eligible to vote okay the more you hold the more power you have to vote in a protocol and this can be understood as a generalization of the threshold bft model at the same time also as a simp as a specific special case of the generalized model right because here one unit of stake is one unit of stake regardless of who this holds so it's only a special case here but nevertheless you can understand many of the existing protocols here in this model where we just vote based on on stake and we can use the a lot of the type of bft literature in this mod um it still requires that the system follows the certain Properties or the protocols

follow the properties of voting because we have quorums we have rounds uh we need an over overlap of a certain majorities between two quorums and so on yeah a new element that can come in here is the so-called slashing yeah this is when there is a demonstr A demonstratable or provable misbehavior by a participant we can take their coins away and that's a new element that's why it's not exactly the same as the voting from before because there nobody was was losing their vote this was just abstracted away was not part of the picture so this is perhaps one of the most popular models that is used today certainly if you look at the the new chains here like opos sui and and so on yeah but it's not only this

because uh the bigger chains are using different protocols namely with randomization added some some of them there is a model where you can have a pure randomization effort which is like select a node at random according to their stake with the idea in the back of your mind of the mining protocol from Bitcoin that there is like a lottery that selects a note to write the next block with a certain probability and you do this according to your stake Holdings and this is mainly the idea that comes with the cryptographic vrf that has been pioneered by algorand even though I don't list algorand here I'm just going to say why um I'm uh but I'm mentioning here cardano and the uroboros protocols uh as in my understanding the the purest

representatives of this class of um protocols so you have a probabilistic choice the actually most popular protocols nowadays are combining votes with probabilistic choices yeah uh in stake based voting so they would use randomization to select certain knows they would use also votes to approve certain random choices that have been made as the algorthm protocol itself does picking some notes or maybe randomly electing some notes into a committee or the ethereum protocol that came along with ethereum 2 yeah the one that um also has now divided the protocol mechanism into like two components one that is randomized and

and based and and and more responsible for the liveness and the second component that is more using a quorum based approach uh using stake for voting but that is slower yeah so the the the what are they called ghost lmd ghost and and the Casper but there is also poka do this is something similar and I will put algor here it's probably the most um one of the most popular protocols today then there is also other assumptions that people have started to make namely I can demonstrate my voting power I can I can gain voting power by investing some resource other than work yeah work will come as the ninth model some resource

like time I have to wait long enough or some resource like like um uh storage space yeah so the storage based protocols like file coin they are using voting power based on how much storage you contribute to the network and then give you corresponding power interestingly there is always in this um storage resource based uh consensus protocols at time delay at time components so the verifiable delay functions the vdfs they play also an important role in these protocols Shia also has a combination of vdf and some storage component yeah so this is another interesting compon another interesting design where voting power is not gained by an onchain resource by a

coin but by some in resource that you invest externally and now last but not least but I guess you're all aware of it there's the proof of work that's the furthest away now my line of models from the original voting based protocol that's maybe also why the um it was hardest to understand for the traditional protocol researchers what happens here right there is a resource like work proof of work in the Bitcoin protocol being invested and many coins many cryptocurrencies have followed on this model where the resource by itself the resource investment is otherwise pointless right it's otherwise a waste of work instead of a proof of work and and I think nowadays the biggest um

investors of work for the Bitcoin chain are in the US and still in China but uh the biggest mining Farm here I looked this up the other day biggest mining Farm in the US has about 400 megawatts of installed power and this is like one of the smaller nuclear reactors in Switzerland yeah and uh this is constantly running and burning electricity so these are these are the nine families of protocol assumptions that have been used that could be dis distinguished here and if you know another one uh yes let me know it's a really great taxonomy I guess it's I don't want to like nitpick it to death the uh I guess why is proof of work like all bucketed into one and then proof of

space is separate and there's a lot of different versions of proof of work that could be um separate you're saying proof of space yeah how did you storage is different from proof of work how did you decide nine was enough and not like you know yeah that's a good question seven okay so why is proof of work not the same as proof of space or proof of delay that's that's correct um that could be also organized a bit differently on the other hand I would not really want I'm also looking at the protocol structures here how the protocols are structured what do you need to implement it how which kind of um techniques do you want to invest in for for either going this way or that way and then there are different right the protocols look quite different for the space and and for the

proof of work proof of work is really simple right uh but on the other hand many people have recognized that is also really wasteful I mean I guess I would push back and say like Bitcoin proof of work Nakamoto consensus is simple but there most of them didn't go anywhere in industry but there were all these other like hybrid proposals like uh Bitcoin NG and things like that where you sort of do proof of work and then elect a committee Al you're saying that the hybrids between proof of work and quum based protocols I left them out and that's true and that's true and I think it has to do with what I wanted to do here on this line usally showing the the the chains that actually use this model

and I am I'm not sure if this actually used if you know a chain that's somewhere somewhere has a one of the larger market caps that actually uses Bitcoin NG or one of these protocols I'll be very interested but maybe the Simplicity of the proof of work uh has made the pure proof of work here Prevail as opposed to the hybrid designs and so on where you still have some elements of this yeah I mean I also glossed over for example that in these D protocols like Phantom DC or or the conflux there needs to be a proof of work type thing as well and I auto tangle that happens as well yeah um but it's the structure of the protocol that looks different at the end of the day yeah it's also that there are

so many protocols it's really hard to keep track of them and this is just an attempt one attempt to keep track of of of them uh in in a in a man manageable enumeration yeah okay with that said let us go uh forward or in a sense backward and go back to these protocols where we have votes yeah and quum systems and votes and that's it the model of generalized trust is the model that is a first uh generalization of the original voting based uh Quorum System model and it's based now we have a technical audience here so let me just jump in with with a definition of a Byzantine Quorum system a Byzantine Quorum system

is this generalization of the threshold n bigger than 3F to arbitrary set systems right and it starts um so historically it starts in the work of Malin Ryder and concurrently with work by hton maer and here are the the the years of the corresponding uh Journal Publications and there's definitely happening two in these two different fields of cryptography distributed cryptography multiart computation research and distributed computing research happened concurrently so the idea time was ripe for these ideas um we start with an adversary structure you start with specifying who we think could fail yeah so we have a set system corresponding

it's called a fail prone system and the system is prepared to tolerate any set of these Roman F parti parties failing together yeah could be specified in arbitrary ways and now that makes it now interesting how do we actually specify them right what one can do from this is then derive a quorum system the simplest thing is just to say the complement of every fail prone set is a quorum but it's not necessary certainly not um in the cryptographic literature when we talk about access control it's much more often that we specify the quorums like the access systems like in a secret sharing context which corresponding groups are qualified to recover the secret so something here

is a quorum when it's part of that set of quorums which is called a quorum system if any two quorums overlap in at least one more node than a fail prone system okay a fail prone set so take the overlap of two quorums so you subtract any of those you're prepared to tolerate to fail and you have to have more and more known this is the one where the consistency in the protocol will reside on this is as I said symmetric trust and here's a picture of a quorum system where we can think that we can tolerate some combinations of two parties to fail namely among the XYZ parties any two could fail or among the pqr parties any two could fail but it's not possible

that any of the two higher and lower uh subsets fail together but it's possible that one of them fails right up to one so this set systems always uh closed on the subset and so the the fail pron system is listed here and the fail prone the quotum system cor corresponding quotum system is this yeah in this model um the nodes they are trusted differently but they have the same trust yeah uh so they trust all in the same way so it's a common trust assumption that they have to be buying into right and it's not so clear anymore why you should this use this or that trust assumption but that's how it is yeah in this model here with this model um there have been a lot of research results on

this with cryptography and also on uh consensus protocols as I as I say here it's it's well known in theory but it's not really deployed except for now now comes the the point with coinbase if you were at SBC The coinbase Vault their key management system does a kind of a threshold crypto system where there's an axis structure that's a monotone Boolean expression that's listed down here where there are there's an end at the top level and one of the three components here for subdivides into a um uh threshold access structure so you need one offline server and you need so you need the offline server you need the human approvers in

total and you need the NPC servers and there can be many NPC servers actually together K could be there and there's again a k out of K so at the top level this is a three out of three but the human approvers they're going to be anything like two out of 20 or even a more generalized access structure so these are this is an example of of um a generalized access structure in practice is it used for other things in practice is not clear um it's definitely possible to to Pro to to take the existing protocols and around them in this model A lot of them also a lot of threshold cryptography but it's not necessarily the case um I wanted to come to focus uh for a short

time on a typical protocol in this model maybe for those who haven't seen this yet and give you some background here of why Byzantine quorums make sense right and uh so this is like a bit of taking a step back here for those who are not into concurrency literature the very simplest thing that you can do with these quorums is Implement a shared storage space that's in concurrency called a register and um it's it's not pointless for consensus because at the core of every poos or pbfd or whatever modern optos Su type of protocol we have one of those registers that's in there there have been papers about the puxos register as well so this only this register the main thing is concurrency

you have concurrently a reader and a writer that's going to access it in the simplest case there's only a single reader and a single writer and what has to happen is but it's not implemented as a it's of course implemented in the distributed system right it's could be implemented with a generalized Quorum system here and so we have an event that when an operation starts the met the metal model is asynchronous the operation takes some time and after a moment it it terminates and completes and now what does it mean for two operations to be concurrent well it's when the first operation ends only after another operation has started right if operation starts there's a picture here of course yeah now I can even draw it okay so if if there is an invocation operation here and the completion

operation of this operation o there's an operation o Prime and the operation o Prime is invoked before operation o completes then these two operations are concurrent right and otherwise they are um preceding so the question of course is how should this register behave when you access it concurrently from one client or for maybe multiple clients and so there is this canonical uh taxonomy that also goes again back to Lampert and now how many of you have in the audience here have seen this before not even too many okay not even a majority okay so primarily you want this storage thing to be safe right you want that if a operation like there's a first

blue writing operation here that writes the X and then there's an operation like the one down here that reads and is not concurrent with the right operation you want to read uh sorry this is the wrong one you want to read the value that has been written there before okay so that would be an operation that starts here that must return the X because it's the x that has been WR written here in the very first operation the really interesting question comes up when you look at concurrent operations like a read concurrent with a right yeah so this orange read operation here is a read that already Returns the the value that is being written concurrently the X yeah and this is definitely possible in

implementations or something is well it's just a specification we call this a regular register if it does that it's also an atomic register that had this that had this feature this could happen an atomic register now is something you can imagine again easily namely as in a register where the value from the point of view of the of The Observers have has to change at an atomic point at a single point in this logical time the regular register the orange uh well the one that depicted in Orange here but also later is a register that may return the value that was written there before four or the value that is being concurrently written right if some nodes are already in the process of upgrading it it might

return the new value so the orange read operation here the first Returns the value that has been written there before and the second one Returns the value that is written is being written now the red one is concurrent to this orange read and it Returns the value that is being written also the V the Y that is being written here in the second part so this type of concurrencies it's this is what this is all about um the atomic register here so for the atomic register here in the purple read you have to ask then that it actually Returns the Y because the register has the part the node R2 here has already observed the new value so it cannot go flip back in

time if you're looking at only the regular semantics it might also return the value y that was written there before so you can have a flip forward and backward how to implement this while this is the the uh the the topic of of uh uh consensus protocols and and of of uh well it's at the core of all those consensus protocols and in the Byzantine model with the Byzantine Quorum system we do it like this we have a writer with a logical timestamp it's a single writer makes things easy with a digital signature scheme and whenever it's and it's implemented in a set of nodes that form this Quorum system the writer writes to a quorum of nodes and gets an acknowledgement from the chum of nodes that they have stored it okay and then

terminates the right operation the reader will do something similar it will ask all of those notes for their current value it will get values not from all because some actually might be faulty just like the writer may not make it values not from all the notes and we'll actually then go and validate the digital signature on the writer of the writer in this in this value and take the value that comes with the highest time stamp right right and it's possible to show an execution where we also flip back in time just because the message from the writer did not arrive at the reader uh did not arrive before the reader got his value in this case here the red right operation would already

have been recognized at this first note here we'll get back the new value would output this but it would be equally Poss possible that the two dots the two events the local events at the first process are swapped in the order and in this case you would realized that the blue reader would output uh the value X that was written had been written there before and not the new value so this is at the core of those consensus protocols and I'm showing the example here of course with the threshold Quorum with four noes and one of them faulty but we can generalize this to arbitrary quorums as I just said yeah I'm wondering so so it's obviously a

pretty general definition quum system so I'm wondering what is the Beyond like weighted voting what do you think is the most important thing that's what is the most important uh generalized quum Beyond vaded voting um you you mean important in practice maybe the one that coinbase uses for their thing but they're not using consensus it's maybe not a coincidence that this model is not used in practice because it could be difficult to agree ahead of time a priori on who is how much trusted right um it's certainly the case that many systems have some kind of exit not like there's a Super Key built in sometimes or somebody can has a somebody has like

a back door into something so there is a very special case of such a system running but for for a more generic uh type of uh cryptocurrency system I haven't seen it used yeah I can it has to do with a qualitative difference between the nodes that has to be discernable and I have to be all agreeing on it yeah and I guess a related question is how often is like the protocol you would write down for just unweighted voting extend easily to system in this in this case here the protocol is exactly the same okay and is that typical or you usually have to work hard to get in this case the protocols are exactly the same for so the protocols for the generalized quorums are exactly the same as the protocols for for the threshold quorums right if

we go to threshold cryptography and that's more interesting now then we have to use different types but we can also do it yeah uh threshold cryptography has been also very used a lot in uh in in Quorum like systems also but then we need to upgrade the threshold crypto yeah but it's largely known how to do this yeah we have some research work on actually doing it because nobody has done it in the industry on actually doing it and measuring performance and it turns out it's comparable right it we're not losing much because we can it essentially has to do with the complexity of specifying your quorums or your fail PR system your adversary sets if you can specify this in a if you do specify those in a Boolean formula that can have arbitrary like exponential complexity in the number of nodes that

you're dealing with then the protocols also have corresponding complexity if you can capture this in a uh what's called a monotone span program do have the this MSP here uh this is a linear algebraic expression of computation where you look at the Subspace that is spanned by the vectors held by the by by the nodes if you can do this then we you're efficient in polinomial time and so that's I think it's very interesting and it's it's overlooked it's too much overlooked this model uh at the moment yeah yeah as I said we can do this this uh just want to say we can do verifiable Secret sharing thres crypto threshold signatures in this model as well but practice has not been buying into it maybe it takes another 20 years we don't know yeah we don't know

about trust assumptions okay um then I want to go forward to asymmet trust but now one more question about the generalized trust I see occasional papers that say that the generalized ex structure secret sharing in general structure are still exponential the secret share size are still exponential there are one or two um so you're saying that paper claim that secret shars are sizes are exponential it's true but but it's actually a research topic but it's much more in theory uh it depends on the complexity of the access structure you're writing down in the first place how how is Is this different like why are you getting so efficient so much efficient oh because we we were restricting ourselves to the class of of

access structures that we can be captured uh in a in a small uh number of uh like in a config file with a small with a small expression this is not for all types of access structures uh for all type of booing formula because then we have too much complexity yeah this is like restricted class of monotron spans sorry this is yeah no the span programs are General so the span programs are always um if you can capture if you can formulate your axis structure as a span program then you have an efficient polinomial representation size representation if you are giving your axis structure as an enumeration of set system it's going to have exponential it

may have in the general case exponential size and in this case there's also exponential size cryp crypto or consensus protocols because you have to go and count in the model with asymmetric trust and I'm I'm relying a lot here on the corresponding generalized trust because it seems to be well it is actually the case that this asymmetric trust makes only sense when nose have this power to describe heterogeneous trust sets yeah so why are we interested in the asymmetric trust and some of you have seen this before well it's about taste right the Romans said you cannot argue about taste yeah either you like it or you don't like something yeah and it's about trust maybe as well either you like an assumption or you like you trust that entity to do the right thing or you

don't trust that entity do the right thing yeah so it's a representation also um of a certain social uh phenomenon right uh it's about assumptions okay it's about assumptions where if you do research in computer security there is very often a security assumption and then in the research world people argue for very long time about the validity of the Assumption in the first place because they cannot agree on whether this assumption is is is aable or not in practice uh they're going to be different assumptions right from an assumption um there will then follow a mechanism and if we want to build a blockchain protocol from such personal assumptions then we are in the

realm of these asymmetric uh quotum systems with asymmetric trust and it's also that um the idea that came up first in the Ripple system where Ripple system was designed to let you specify who you trust to give you back a little bit of this permissionless element that was in Bitcoin yeah and Stellar came later as a elaboration in some sense on bitcoin I have I have this listed here so Ripple is actually old yeah Ripple started something like more than 10 years ago and they have a I would call homegrown uh consensus protocol that was inspired by quum protocols and we looked at this in a paper here in 21 and that was actually the formal the first formal

specification in type of PSE suda code that we had for this protocol but it's not a type it's not a quotum protocol that we can derive from the textbook right it's rather the opposite we see some issues pretty soon when we go into these protocols it needs to be synchronous and so on so it's not a type of protocol that you could find or even derive from the textbook knowing the textbook helps you to understand what perhaps should go on there right in the Ripple system you define the set of notes from whom you listen uh from whom you receive votes so this is called this UNL a node list unique node list and you're only counting votes if they come from nodes on this UNL some of them could be faulty still

right and some of them in your list could also be faulty hopefully we have enough overlap between our lists so that we have a quum or have we have consistency today the xrp foundation publishes such a list and there are 35 notes on it and these 35 noes are just I would say downloaded automatically by every client and we don't have this uh asymmetric tust everybody has the same set of uh uh quorums in that system it means also that perhaps we could use a different protocol in that system but the system us uses that protocol for now Stellar came as a fork of Ripple initially and then they worked with David Maier to develop what's called Federate Byzantine quorums which is an

elaboration and a more complex a more structured version of the same idea where every node now has a local access structure I would say where they Define whom they trust how and here's an example now going back here this uh to answer Tim's question from earlier the example here is a config is a config specification in the config file of one of the Stellar development foundation notes you have eight noes here and you need six out of these eight to agree and among the lines here in the second level of the hierarchy you need always like a simple majority right is this a Byzantine Quorum system not it doesn't like doesn't look like a Byzantine

Quorum in the sense you need a 2/3 majority because there are like simple majorities on the lower layers here and largely looking at this and trying to understand what goes on is what motivated our research on asymmetric quorums because the protocols also that are running are different the protocols that are running in Stellar are different from the ones that run in that we find in the textbook but this is the best example we have of a um generalized access structure if we have a config file like this then you can compile this into efficient threshold crypto so the monotone span program and this is what what we have done in a in with u in our work also is takes inputs like this okay then you can do threshold crypto asymmetric trust every node now

specifies its own generalized Corum system okay and here and it does that also again through a fail prone system specification I say I don't trust these two together I trust these more in the picture here we have the blue note and it's view of the world among the six the blue note says it's immediate neighbors maybe one of them could conspire against me or the people who are living across the street here these X Y and Z nodes maybe two of them are conspiring against me right so this is going to Define our fail prone system and with a fail prone system like this so Q or r or X Y or XZ could and so on could conspire against uh this blue note and from this it's the Quorum system of

node P we would now could now in this example say that we go around the circle and rotate in the circle everybody has the same view of it of this system here this would be an asymmetric qu system okay this would be an asymmetric qu system it's it's an example notes they are not only trusted differently passively but they also actively Express different trust assumptions this is capturing the same idea as in the Stellar protocol and if I go back here then we can actually uh maybe not going to run in the full Glory through this but they can actually specify this here as well in the formal sense of a Byzantine Quorum system by taking the former specification and extending it such that we have Quorum a quorum system

for pi a quorum system for PJ for another process and it has to be the case that a quorum for I and a quorum for J overlaps in has an overlap even if we remove any fail prone set that either I or J is prepared to tolerate okay so together they have always somebody who is correct in their both views and for liveness for Ava availability we can concentrate on a single note only namely for each one of my quorums so for each one of my fail PR sets for the for the nodes that can fail in my view for each one of those sets there has to be a Quorum available that is not

intersecting with them and actually the model is coming from multiparty computation even more that was first formulated by damgard nilson Fitzy and uh and Desmet in a in an older paper but it was immediately forgotten again this 2007 paper now uh we can do uh we have I have mentioned this here there is the re the um a property where you can decide from looking at a asymmetric or a symmetric or threshold quum system whether or not this fail prone pattern can even be tolerated yeah this is why why we said n bigger than 3F in the threshold it has to be the case that n is bigger than 3F for certain things in the to to actually guarantee the

existence of the protocols or the threshold Quorum system for the generalized Quorum system we have to be able to say so generalized quum systems exist if and only if no three fail prone sets cover the space base of all participants yeah this is what has been called the Q3 property it was one of the slides but I didn't have time to go into and a further generalization of this is the so-called B3 property where we have to where where we look at a fail prone set of yours a fail pron set of yours the other party a fail pron set of both of yours and none of these combinations of fail pron sets must cover the whole Space then we have an asymmetric

Byzantine quum system none of the these three sets in any combination if if none of those are all participants then you actually have an asymmetric bantine quum system the whole goal of this approach here is to actually run roughly or ideally the same protocols that we have in the threshold model right why should we invent another consensus protocol for for this model with the security assumption is generalized from the other model and this is roughly also what one can do before I look list the protocols I I want to give you one more detail on this namely the execution model and the execution model are going to be nodes that are correct like before okay and

there are some nodes in an actual execution some notes are faulty corrupted by the adversary and in the threshold model a node is either correct and benefits from all the guarantees of the system or the node is faulty and we don't care in this model here we have nodes that are correct and made the right assumptions and we have notes that are correct and they just have the wrong assumptions yeah so there are notes uh about which we care and we can still well let's say we're going to take we're going to call them naive and we care about them in a protocol because they play a more bigger role in the traditional world we say what happens if f+ one nodes are actually corrupted well then we just

stop it right we normally don't uh look at this situation in assessing a protocol what happens if too many nodes are corrupted because we cannot say much about it actually we could but we don't right because there may still be this one or two correct notes but they're not getting consensus anymore in this picture here we have the naive noes there are new class of noes that come in that are correct but um have made the wrong assumptions yet the protocol still runs because it continues giving guarantees to the wise parties the wise parties are those who have made the correct assump the guarantees are given for the wise parties only na if we cannot give guarantees and moreover uh it looks like for many protocols we need

uh a so-called Guild which is a set of the wise parties that is closed that has a quorum inside for the for for each wise party and they're going to be the ones that provide liveness in the protocol this is the picture here to show that we can take an existing protocols and replace only the blue parts in the protocol where we listen for a Byzantine Quorum with the parts where the reader and the writer listen for their own Quorum a reader Quorum and a writer Quorum just like in the read write example we had before and they're going to be consistent and live if both of them are wise and we can do protocols like this register emulations the the normal the type of simple bantine

broadcast randomized consensus and and other things and uh it's an actually actually a very active area of research um there are other approaches that matter here like the flexible consensus which is a slightly different model um where the nodes adhere to a ordinary threshold quum system where the clients have a asymmetric subjective view or the heterogeneous pus work that is also uh breaking up the symmetric and generalized uh trust assumptions and that let me conclude now yeah bantin consensus Protocols are here to stay assumptions are more important than protocols these fields like generalized Pro trust assumptions and asymmetric

trust assumptions I think they're important and and relevant so for the asymmetric case so I'm sort of struggling like I feel like there's two competing forces like one you want to give people flexibility to specify their own assumptions what they believe on the other hand you do need for guarantees you need at least implicit coordination between people's trust assumptions so like how should I think about that like what like people doing their own thing why would those conditions hold need to correlation between people's trust assumptions even though they can be they should be individual right I think it's it's perhaps a way that we see in the Life Stellar Network how they specify their

things to what it could lead so let me give you an example it could be that we have a hierarchy and at the top level oh we have a couple of banks right now maybe we have a couple of trust providers for cryptocurrencies and they are sure to have among each other this this uh that their Quorum consistencies but they don't want to listen to their clients that that they actually cater and serve business to but I as a client I get I I am declaring a main bank and a second bank it's not going to be a bank okay a main note and a secondary note that I trust but I may not want to trust all these others out there that I've never heard of yeah so it naturally leads to sort of hierarchy

to manage the mental complexity of of specifying such a model I think this is a way of of looking at what could happen in practice um it's clear that from the protocol themselves if there is not enough correlation between the trust assumptions then there's no consensus and then that they just Fork right but it's actually giving back the element here of uh of it's giving back the to the Quorum based protocols the elements from the Bitcoin type protocols that if you just want to be live much more than safe right you can reduce your trust assumption a bit right and you can be

live with your friends this just doesn't matter anymore with respect to the other the rest of the system yeah and so it could naturally lead uh in in a sense naturally lead to Forks yeah in the in the space but we haven't thought nobody has really thought about joining these Forks again later but it's a social thing that it has to be connected with social processes I think otherwise it doesn't work yeah it needs to go through some social trust structures maybe we can use these protocols to actually understand what goes on in different contexts can we go back to the definition of consistency in the asymmetric case oh the definition of consistency in the asymmetric Quorum system right okay yes yeah I have two questions first of all should I think of this definition in terms of um wise or

naive nodes like the and the PJ here okay should should we think of this as wise or if there is no such notion yet because this is the abstract specification of your coron system when you set up the system before you are in an execution where some nodes are going to be faulty and some are going to be crushed only when you have an understanding of who is faulty you can say who is naive and who is wise isn't the set f um supposed to specify it ranges overall possible it ranges over all possibilities right but it only ranges over those possibilities that the protocol or the nodes here have foreseen right because it could be the case that that one of my

f so that the actual F in the execution is bigger than this F set that I as fi I'm prepared to tolerate in this case I'm going to be naive they have a second question yes uh the second question is why um should I have the intersection there of the Cor of notes I and j instead of the Union of those here yes ah because you are going to listen to a quorum of yours I'm going to listen to a quorum of mine okay and this still has to have at least this intersection has to have one load one node in there that you think is correct and I think is correct namely this then it will be

Union that's what my question is yes exactly here the union or or f i Union of jar that the intersection of our accepting Chums have at least one known that both of us trust so it's not equal to the union of uh Val that we don't okay maybe there's a typo I let's discuss of was okay again yeah you're saying for the F should be the union so the the the star is is is all subsets the star notation right I didn't say this it's not a singlet it's not a it's not a single set this the FI JW star here oh okay I think there is this Fi Fi star is a set of nodes

in fi star is a set of sets of nodes that it contains all the ones that Pi is prepared to tolerate right it's it's Clos on it's actually closed on subset I see I think there is second level which I'm not visualiz yes wa isn't it the ones that you're not prepared to tolerate because no no there the fs are the ones that you thinking could fail is a fail pron f is a fail prone system so it consists of so-called fail pron sets and every element in the fail pron set is a set of nodes so you think all of them together might conspire against me yeah for example any set of two yeah out of seven that's the simplest example I need to parse this a bit good I guess

yeah I guess we have time for more discussions also later but otherwise yeah thank you again