BLS Multi-Signatures for Blockchain Applications with Foteini Baldimitsi | a16z crypto research

Transcript

good morning everyone uh welcome to today's a16z crypto research seminar very happy to introduce fattini baldimski who we know well she was a faculty fellow with us last summer summer 2022 so it's great to have her back talking about something which is very relevant for us BLS multi-6 so 15. uh thank you so much Tim thanks everyone for being here I'm really glad to be here again next up since uh previous summer and I'm excited to talk to you about two recent results which are kind of still work in progress or works at an under submission so any feedback would be very very highly appreciated so what I'm going to talk about is two

different research projects that I've been working on this year with my collaborators but they have a common theme and the common theme is BLS multi-signatures so I thought that it would be nice to try to combine them I don't know if I will really spend an hour and a half but let's see how it goes and feel free to stop me at any point with questions so first step let me introduce What A multi-signatory is for those of you in the audience that haven't heard of multi signatures before um so traditional digital signatures um they're just run by one signer that has a pair of secret can public key uh you want to sign a message you sign it with your secret key and you get as I'll put your signature

now the multi-signer setting is a little bit different so the high level idea is that you now have n signers in my pixel I just have three that they all want to produce a signature under the same message m so here as you see everything is signer gets the same message as input they all have their own key Pairs and we also assume that this bold PK here is the combination of all the public keys of the science all right so what could be a very very trivial way to produce a multi-signature it would literally just be to Output the concatenation of all these underlying signatures but of course this is not great because this results in a linear

size of the signature to the number of signers so that's not good so most of the multi-signature schemes that we know and that we use in practice they actually managed to create a sort multi-signature via two different ways one is to assume an interactive protocol among the signers or the most classic one is to assume some sort of aggregation across the signatures that gives a very short signature at the end and we want the signature to have efficient verification and again we want this to be sub linear to the number of of signs additional many multi-signature schemes support what we call a key aggregation which is an additional algorithm that manages to combine these public Keys

together again in a public key that is of sublinear size to the number of signers and this makes verification uh even more efficient so this is a high level idea of how multi-signatures are defined so what do we care about multi-signatures well multi-signatures have various applications so in the non-blockchain setting we have seen uses of multi-signatures in Collective signing of digital certificates for example and most prominently in the blockchain setting we have seen applications of multi-signatures in multi-user wallets where you might want to authorize a payment by requiring a

certain a certain amount of signers to sign the transaction in various layer 2 blockchain protocols like mixing protocols or the lighting Network and additionally in a proof of stake protocols where you want a set of validators to sign together a new blocks that ends upon the blockchain so in today's talk I will be focusing on those two applications of multi-signia tubes and they will be discussing two results the first one will be decentralized issuance of a special type of digital certificates and that is the case of anonymous credentials and to do that I will introduce a new

building block which is relevant to multi-signatures but it builds more features and this is blind multi-signatures and then in the second part of this talk I will talk about again A variation of multi-signatures that is optimized for subsets of signers and I will explain what all these mean the common theme between those two Works beyond the fact that they are on multi-signatures is that they both of them are based on the concrete case of BLS multi-signatures which is one of the most well-known and efficient multi-signator schemes in the literature so I will get to all this in in details so let me start with the first part of

the talk and that is the decentralization of anonymous credentials via multi-signatures so let me start by introducing what an anonymous credential is so in high level an anonymous credential is a digital token and it typically contains information about the user so here for example you can have the name of the user date of birth address and so on and this digital credential is issued by some special Authority that we typically just call it the Asians Authority so the important property of anonymous credentials is that after the user obtains their credential they should be

able to use it to create proofs on their attributes in a privacy preserving way so for example let's say that this owner of this digital credential wants to buy alcohol and they want to prove that their date of birth corresponds to an AIDs that is over 21 years old and this is the only predicate that they're wishing to reveal and nothing else about the rest of their attributes so having an anonymous credential should allow a user to go ahead and create such a proof that only proves this very specific predicate to some proving set where to some verify a

server over there the important property is that this proof that they present with a verifier should be unlinkable to the original credential that they got in the first step so in other words this means that even if this is King Authority colludes with this verifier with this server here again they shouldn't be able to link together that credential without proof and in the typical case of anonymous credentials a user should be able to create more proofs on their on their credential potential on different predicates or even the same predicate and still those proofs should be unlinkable to each other and of course

still unlinkable to the original credential so that's the basic setting of anonymous credentials and if you think about how can we construct Anonymous credentials that's a pretty straightforward generic way that can gives us that can give us Anonymous credentials so what would be this generic and symbol Construction what is a credential what can we do during the Asians process so essentially we could just have the issuing authority to compute the signature on top of all the attributes of the user and this is the credential of the user okay so this is something that it's verified that it's coming from the Asians Authority

it's something that because of the digital signature we can easily tell that it has been vouched for from the Asian Asians Authority then how can we produce those private proofs on our credentials well we have this very powerful tools and cryptography that we call zero knowledge proofs and it's very very easy to come up with zero knowledge proofs on different predicates on our credentials and at the same time this proof should also be proving that we do own a valid signature from the issue air on these blind attribute that we are revealing some predicate on so these all sounds nice however

sub-senetic constructions are not necessarily very efficient and um that's why there has been all this line of work in the literature that we call Anonymous credentials which essentially tries to create customized protocols for this process so we're not using any digital signature we're using digital signatures with certain properties that we allow for efficiency zero knowledge proofs um or we use customize it analysis proofs and not generic and not genetic snacks so that said if you look more carefully in the literature of anonymous credentials you could Identify two basic categories of anonymous credentials the

first category is the one that we call multi-use Anonymous credentials and this fits better to the scenario that I have been explaining so far what is the idea of multi-use anonymous credentials these are credentials that I get issued once so I talked to the Asians Authority ones I get micro credensia and then I can use them multiple times I can use the same potential multiple times as long as I produce fresh proofs every single time I'm using that credential so typically this credentials as I said before they are based on digital signatures and zero knowledge proofs and again as I said a lot of work in the literature has been focused into

constructing signature schemes that allow for efficiency zero knowledge proofs on the underlying methods the second type of anonymous credentials is what we call single-use Anonymous credentials or what we very often also call Anonymous tokens what does the idea there the idea there is that every single credential that you get issued you can only use it once okay so you can think of this as like single-used Outlets how are these schemes typically constructed they are typically constructed using a special type of digital signatures which are which are called Blind signatures and I will

explain soon and optional zero knowledge proofs if you want to reveal more complicated policies on top of your credentials so that has been a very long line of work in the area I'm not even including everything here and Anonymous credentials have also received interest from the from the industry and we have seen various projects attempting to implement them but as far as I know there is again renewed interest for credentials from companies like Microsoft so let's see how how that goes all right so back to our decision between our distinction between multi-use and single users yes can you explain how signal uses

um and what Anonymous credentials they are yeah so uh they're using uh some sort of multi-use anonymous credentials and they essentially use it to prove properties when they create some groups I believe um so you want to prove that you satisfy some property to create some groups for messaging um I think that's that's what they're doing I'm not sure how uh I haven't really followed how at what point the implementation is but there was a paper on it I believe last year at ccs um and I'm happy to give you references okay so back to the distinction between the two types of credentials

um credentials are typically used in applications where you have some sort of Subscription Service you want to sign up once you want to get your credential ones and then be able to use it multiple times and if we ever end up having digital identities with privacy then again this would be some sort of multi-use credential you get you get it is good ones you use it many times um while single his Anonymous credentials are more natural for applications like single-use coupons electronic tasks electronic coins electronic voting and the main property of single-use credentials here is that what I'm going to claim is that they're more efficient

as long as you know that they're only going to be used for a small number of times they're also vehicle to vehicle Communications the U.S built this huge infrastructure for single-use credentials and the argument is this efficiency on the device on the car oh I didn't know that I'm happy to see references thank you um so again in general the main idea is that because they don't require they don't necessarily require the use of zero analytics proofs during presentation and presentation of a single-use credential is literally just verification of a signature they're much more efficient although again there is the caveat that you need to run the issuance Pro stations process every single time you want to obtain any

ingredients also don't you typically need to keep some list of spent credentials decentralized Anonymous so now that we're all experts themselves are let me complicate the system a little bit and talk about the centralization so all the classic Anonymous credential constructions that we had in the literature were credential constructions that were assuming a single is here a single issuance Authority however in second scenarios you might want to have more than one each years

issuing um the collectively a digital curtains so um the most relevant work for us in the setting and again I'm not being I'm not including every single work here was the work of uh credential decentralized credential issues by a paper that appeared I believe in nbh says 2017 Etc well quite a few years ago Sarah was one of the coasters and they were using threshold blind signatures for the credential issues um before that and since Matthew is in the audience there was another maybe the the first attempt to do decentralized

Anonymous credentials but the setting there was a little bit different so you were not just assuming that these issues were specific authorities it was embedded into a blockchain system so however here the idea was the following so the idea was that we want to construct a multi-use Anonymous credential scheme where there is a fixed set of valid issues and you have m issuers and whenever a user wants to obtain a credential they can get signatures from T out of these n users and this is what we call a threshold signature so threshold signatures and

multi-signatures share some common properties so you could view a multi-signature to be an N Out of n threshold signature however when you try to implement these schemes you're going to see that there are certain caveats so um here um just to wrap up this part it's not just that they needed a threshold signature for the issues they also needed to convert that into a blind signature why because um and again I'm gonna get into how the skin works but the idea was that they wanted to make sure that during issuance uh there is this unlinkability property between the credential that is being obtained so the caveat of this work that mainly

comes by the use of threshold signatures is the fact that there is this interactive and non-flexible threshold key generation phase so this set of signers here is fixed they need to run a protocol among each other in order to create their key pairs ahead of time if you want to add a signer you need to rerun the protocol so this gets pretty complicated and also the implement the verification of those schemes on the Chain was pretty expensive so in this work they were assuming that the decentralized

credentials would be eventually presented on a blockchain so in such a scenario we really really care about the cheapest verification possible and verification at least in this original scheme was pretty prohibitive so what are we trying to do there was I should also note that a few months ago there was also some work that was optimizing verification for the coconut scheme and they were essentially using bad zero knowledge proofs in order to combat the verification course on the same so our main goal when we started to work on this project was to come up with a

trade-off between this problem of requiring this interactive non-flexible key generation phase among the scientists yes like what was the actual construction they were using in the zebra scheme yeah they were using the Construction uh so this was a it's called Blind signature construction on top of BBM signatures um that I don't know how many details you want to know but uh basically what they did so in the original coconut construction they didn't do any optimizations on verification so I think they were just um and again I believe this was a 2017 paper so I think they were just um

evaluating the cost of every single verification which requires zero knowledge proofs and the this zebra work uh essentially batched the serial its proofs together and to be fair they also did some extensions to add some discussion on revocation and so on but I'm not cutting that on this but the main contribution was batsing Zero knowledge groups with tools that did not exist in 2017. all right so um our main observation the main problem that we're trying to tackle here um and offering a trade of essentially was to try to avoid this expensive kids and addiction phase among these years it

has a very flexible issuance um Construction so instead we said what if we build blind multi-signatures as opposed to Blind threshold signatures with um offer a very flexible signing process so the user can just pick on the fly with signers they want to sign their credential designers never need to interact with each other and um in this way we can have this issuance process to be very very ad hoc so of course this comes with a cost that you can either see it as a cost or a

benefit so multi-signatures as opposed to threshold signatures offer sign and accountability so when you're looking at the multi-signature you can immediately tell who are the issuers who are the signers of the signature and um in that sense it this might be a feature he might want to be able to tell when you're looking at an anonymous credential when you're looking at the proof of an anonymous credential who were the issues that vouched for it it might be important um especially in cases of misbehavior you want to be able to potentially penalize issues um and so on and um but the the main disadvantage here is that this reduces the set

anonymity okay so now your credential is kind of hidden only among credentials that have the same set of his years the good news is that if you run this on a blockchain setting you kind of have control set anonymity so you can see how many credentials have been issued with the same set of signers and you can decide which signers you want to pull over when you're designing your pregnancy so as I said it is a trade-off and you know it can be application it can depend on the application on what you want to do a second difference from this prior Works was that we focused on the case of single use credentials and none of this private prior Works were

doing single use credentials all of them were doing multi-use guidance case um our construction is based on BLS signatures and now I'm gonna go over how bla signatures work in order to first so you have our blind multi-bla signature works and then bind everything together for the credential scheme uh questions up to here so for the scheme the public keys are independent the public keys are completely independent and when the user is starting an issuance process for credential they can just decide which signers they want to sign so let's get into

um let's get into the construction of blind multi-signatures first and to do so let me have been talking about blind signatures um for quite a while now but let me now formally introduce with a blind signature is so a blind signature is a again special type of a digital signature which typically works as follows so you don't know have a signer that owns a message and they sign the message on its own instead you have a signer and you have a user who owns the message and wants to receive a signature on this message from the signer without the signered ever learning what the message was

so the genetic way to construct a blind signature is to start by having the user to Blind the message somehow commit to the method somehow send this commitment to the issue or the sign there the sign that is going to assign this committed value and then um the the user using their Randomness that they used in order to commit to the message in the first step they can unblind the signatures that they received the sigma Prime that they received from the issue so the main properties of blind signatures is that they have to be blind or as unlinkable and this essentially

says that if you look at the transcript of the protocol this commitment to your message and this initial signal to Sigma Prime you shouldn't be able to link that to the final signature on the final message all right so even if the sign gets to see the final signature Sigma and the message n of course they can tell that this is a signature that came from them it verifies under their public key but they cannot link it to any issuance process with any user the second property which is the natural property that we want from every digital signature scheme is that of affordability however we cannot just

assume plain unfortability here we cannot just say oh it should be the case that a user cannot afford signatures on their own um so the in the security definition we have to be a little bit more careful so typically in the unfortability definition of digital signatures we're just saying that you have an adversary that asks for signatures from a valid signer and then this adversary wins if it out with a signature on them on a message that they didn't query for so we cannot do that any longer in the case of blind signatures exactly because designer doesn't know which signatures it computes during the signing process so we don't have any way to check if the signature that the adversary outputs at

the end is one that the adversary created in the first place or not that's why in blind signatures we have a special flavor of unfortability that we call one more affordability and it essentially says that if you have an adversary that gets Q signatures during signing queries from this here they shouldn't be able to Output Q Plus One valid signatures and that's the main property of of blind signatures so in this work and for the first time we Define what we call blind multi-signatures so here the setting changes a little bit and instead of having a single sign and now we have multiple signs

so all of them are signing the same methods the user might be sending different commitments to each one of these issues it is saving their blind signatures and then aggregating the signatures to the one and final output multi-signature here or potential again you could have interaction among signers but everywhere in our work we don't want to assume any sort of interaction among signers and the particular signature scheme that we'll use the BLS signature scheme will allow for the segregation so now in terms of security properties again you want correctness you want this one more affordability that you had before but you also want to

be able to bind this with properties of blinds of multi-signatures so the setting becomes a little bit more tricky and now this adversary that can obtain signatures can also corrupt all but one of the signers and in order for this adversary to win it should be the case that in the four there is that it outputs at the end it still includes this uh key from the only signer that has not corrupted so far so we need to essentially combine the properties of multi-signatures and blind signatures finally as before we want blindness and the blindness ceramic ability property is very similar to Blind signatures as I

stated before and we typically model that by having the adversary to run two sessions of signing so here the adversary is um the signer and they should not be able to decide when they see the signature whether the signature corresponds to signing method 0 or method one so again um we need to combine properties of blind and multi-signatures together all right so having defined that new building block let's see how we can build that out of BLS signatures and the construction is

actually um pretty easy since we already have blind daily signatures and BLS multi-signatures so we just need to put them together so to see how this work uh let me first introduce how plain bla signatures work and then get into the case of blind BLS and multi-dls so bla signature as I said before is a very popular signature scheme that is defined over pairing friendly elliptic curves um so the idea is that the in order for the BLS signatures to be verified they need to assume what is

called a binary pairing mode that has this property here that will allow us to do verification by moving the exponents around so how do BLS signatures work um you have to define a set of parameters a group G of param order Q with some generator like exe where the discrete logarithm problem is hard uh when you generate Keys your keys essentially have the discrete log relation you pick a secret key randomly from the Star queue and you set the public key to be Z to the secret key when you want to sign a message you ask the message with a special hash function that has two curve points and you raise that to the secret key

and then in order to verify you check if this pairing equation holds I could give us the input the signature and the generator Z and you'd check whether this is equal to the pairing that takes as input the hash of the message and the public key and if you replace the public key here with Z to the secret key you can see and the signature here with half of the methods of the secret key you can see that it's pretty trivial um why verification Works since it allowed since because of the properties of the pairing you can move around the exponents so bla signatures are deterministic and unique and let's now see how we can turn them over to Blind signatures so now

um as I said the blind signature it is a two-step process so you start with a user that has the methods and that's the first step they want to Blind the message that they hold before sending it over to the signer for the signals how can we do that we have the message and we randomize it with some random value R by taking uh the multiplication of the half of the methods with t to the r and we send this commitment to the methods over the signer the signer will literally just erase this value to its secret key in order to compute the signature and we'll send this blinded signature back to the user the user now can unblind the signature

by multiplying with the public key of the sign raised to minus r where R was the blinding factor that used in the first step so again if you do the algebra here you're gonna see that you will end up with a signature that verifies on the original message then okay so blind signatures blind balance signatures are not something new um they were proposed by baldereva in 2003 blindness holds unconditionally and unfortability works under [Music] um strong assumption that is called The Chosen Target cd8 assumption and the proof was done in the random Oracle

model so a first contribution of this work although it's kind of a side thing is that we came up with a new invisibility proof for blind dla signatures that uses a more standard assumption the key the QD log assumption uh in the random Oracle model but also requiring the algebraic group model so to be fair it's really hard to compare those two settings uh it's not really clear which one is preferable or not so on the one head here you have you have this like chosen Target assumption which is not ideal but you're only using the random Oracle model here you have a more standard

assumption QD log but you also require the ADM model um but the advantage of our proof is that it gives them much tighter security reduction compared to the original one and this is kind of important if you imagine the schemes being implemented in a large scale with multiple signers signing messages at the same time so the tightness of the reduction might be a benefit here again you can use this as a kind of side contribution of of this work having an alternative proof for blind periods 15 you can see a little bit about um why it seems like you need stronger assumptions for this for the blind construction

well blind signatures are actually very flimsy cryptographic building block proving the security has been pretty tough uh there have been results a couple of years ago at crypto that they actually so in particular breaking um concurrent security so if you want to have a sign there that opens multiple signing sessions at the same time um it's pretty hard to get this level of concurrent security people have shown that there are these Ross problem based attacks that you can actually do if you have many concurrent sessions open so getting organic security has been pretty

tough and um typically this is resolved by using Hardware assumptions yes alternative way of blinding when you just take cage to the H of M Embrace to the power of our like this is kind of maybe additive blinding but you can also do multiplicative I guess right when you uh for for the C4 if you see instead of yeah so you're saying just literally blinded by raising it to R yeah people looked into that and then you compute yeah Sigma Prime you just raise it to one over r

to remove the r i I'm not so sure okay I would have to double it okay I'm not sure how do we feel about these assumptions like or these reductions in like the AGM and the random Oracle model are we like happy with that yeah that's that's a fair question uh so uh you know ADM my video at least is that it is a new model that we still don't understand very well um so there are some proofs that we managed to do that you know were Impossible by just assuming the random Oracle before there were certain flaws in some of these proofs as it was sewn by some papers of had criticism in the of the AG model so at least my take

is that it is a model that it's not very well understood yet um but this doesn't mean that we cannot you know play with it so at least the fact that it gives us a more tight reduction it's something that is interesting it doesn't you know it doesn't it's not the only proof that we have for this scheme it's an alternative proof yeah there's like a like some kind of discrete one more discrete log proof you could probably yeah well uh The Chosen yeah so the chosen Target is also some sort of like one more assumption yeah so again it's not the only proof it's the proof that at least currently would give us the tighter the tightest reduction so how much you believe in idea might think it's still something to be you

know it will take some time and again I'm happy to talk about this I should as a disclaimer I should note that uh um co-authors in this paper are the inventor of the AGM model is Julian laws and also zone cards uh who is one of the people that criticized the idea model but they were still happy with it again as long as it gives a tight reduction at this point all right so um let us now see how we can turn this BLS blind signature into a multi-signature as I said this blind multi-signator is a new primitive but we already have blind BLS and multi-bls so we essentially just have to combine them

together we didn't do anything super Innovative in the in this cryptographic being blocked so again we're gonna do blind signature but with multiple issuers each one of them has a pair of secret key in the public key um in BLS multi-signatures you can do the public key aggregation in the following way so you can multiply all the public keys of the signers together after um Computing the exponentiation of them to these randomizing Factor AI which for every for every public key works as follows you has

together all the set of designers and the public key of the corresponding signal for whom you want to compute AI okay so you compute this randomizing factor for every single public key and then you multiply all the exponentiations of the public keys to this random Factor together to compute your joint publicly so then the user can compute all these commitments to the methods that they want to get a signature on and they randomize them for different random values they get back these blind signatures

from each one of the signers so I only have this for the first signer here but essentially as we said before every single sign or Signs by just um erasing to their secret key erasing this commitment to their secret key and then um the output is again the aggregation of all the signatures obtained by the issuers by again raising this raising this to this randomizing Factor so something to note here is that you don't necessarily have to do the key aggregation at this step you can do it here and the nice part as I said is that you can have flexibility even if one of the issuers doesn't complete the

protocol and they disappear that's perfectly fine if the user is okay to uh to have a potential issued by the rest of the issues they don't have to do anything they don't have to restart the protocol again they can just combine together whatever signatures they got potentially fits another one and put their signature together the signers on their side again they they're completely oblivious on who else is signing the credential they don't have to know they don't have to interact with each other okay so everything is on the sinus side on the on the user side is it clear how the protocol works again nothing you hear the way that we do this aggregation of signatures for the BLS

Epping and this aggregation of the public key it's very standard is exactly how it happens for BLS multi signatures all right um verification uh the nice thing about and one of the most important properties of BLS multi-signatures is that you can combine together multiple signatures and the verification it will still cost you just two buying our pairings um because you are only verifying using the combine the aggregated signature and disaggregated public key all right so uh we do prove unfortability of this uh BLS blind multi-signature again as I said this is

a new primitive and we essentially do a reduction to our blind BLS proof and thus we require the same set of assumptions it wouldn't be impossible if we didn't want to use the setting to again reduce our proof to the original proof Bible data if you don't want to assume it so uh maybe I I missed it but why why are all the the C values that the user is sending blinded separately like is there a version of this where you use the same blinding Factor that's that's a good point so the reason that we do it separately is because we want the um at least at the point of issues the signers to not even if they talk to each other to not see that they're interacting with the same user but you could do it

separately as well another note that I wanted to mention here was that the nice property now also of this BLS multi-signatures is that you can support further aggregation of BLS multi-signatures so if you have like multiple credentials issued by the same set of issuers when you're verifying them you can also aggregate them together before verification and further reduce verification costs in pretty much exactly the same way so you can keep on aggregating the um the message the signatures this way as long as APK is the same as long as the set of features Remains the Same okay so again in our credential setting

if when you're trying to verify this credential on saying you see that there are more credentials coming from the same set of issuers from different users and different messages before verifying them you can aggregate them together if like one of them doesn't respond with their their signatory you can still Aggregate and just leave out that oh exactly yeah so I basically said that this key aggregation process doesn't have to happen first it can happen here oh okay so the order doesn't really matter okay yeah so again as long as the user is happy with the signatures that it got from issuers they can just move along the nice properties that you don't have to deran the protocol all right so how do we use that

primitive now in order to build um single-use credentials and let me first assume that we want to build a very very plain case of single disk credentials of anonymous tokens that do not have any special properties on you know they don't try to encode into the digital token any attributes of the user or anything like that think of this credential as just literally being random numbers some sort of like random serial numbers think of this as being one-time tokens that you want to uh to get issued so in that case if you don't have attributes in the picture then using our scheme is very straightforward what do you do you literally have the user pick this random serial number and run the

Asians process with whatever is here they like they can obtain the signature and then using this token essentially means presenting the signature and verifying the signature of course there is this very valid question in all these single use credential schemes that there are days before how do we avoid um double use of the same token and the most simple way especially these tokens will end up being verified in a blockchain setting is to literally just observe all the signatures that are being presented and um uh take if something has been used before in order to to just drop it if it appears again there are other techniques that people

have built on top of that like adding Expedition dates uh changing the keys of the issues and so on but these are all kind of orthogonal to what we're doing so now what can you do if you actually want to also have attributes in the issued credential so when you also want to have attributes this naturally requires a two-step process during acms so you have to assume that every single user that holds these credentials will first run some sort of registration process with the issuers and in that registration process they will have to essentially disclose their attributes or formally do a zero knowledge proof on

their attributes and the point is that during this registration phase both or this kind of account opening phase both these here and the user will agree on a common commitment over the user's attributes and this will be kind of you know the uh account number of the user with this is here whenever later you want to get credential uh signed by this issue you will have to somehow encode that same commitment to the user attributes during this issuance process and of course there is a science here how do you do that in a way that still maintains an

inability okay so how if I know if the issue knows that it's signing on top of the commitment of the user how can we make sure that later when this credential will be revealed that the issue I cannot just legally say hey this includes this commitment of this user that I I have an account for so it must be him so a way to avoid that is during the Asians process to have the user to send the randomized commitment along with the proof that this commitment is a correct randomization of its original committee

okay so um and again you can use this as a generic way to build a single use credential from a blind signature um the interesting part here is that specifically for the case of BLS signatures doing this uh zero knowledge proof on top of the commitment that needs to get signed uh it is a little bit expensive because uh in Daily signatures you have to do this has to a care point of the methods so this gets a little bit tricky because then if you're zero know it's proof you have to prove something about the output of this class functions that has cheaper issuance but more

expensive verification is and again you can view those two protocols as you know genetic ways to construct single-use credentials with attributes from blind signatures um so this third protocol that we present it essentially uses a novel cut and shoes technique in order to convince the issue that they're using that the user is using the correct commitment of attributes in the acute credential and the trade of here is that this requires multiple rounds you will essentially end up with more than one signatures to verify at the end and you're gonna have more expensive verification so this protocols offers some trade-offs

and again depends on depending on what your application wants to focus on more efficient ecms or more efficient verification you can pick between between one of them again if you don't care about attributes things are much easier you literally just saw signatures at the end and this is it so um just uh some basic verification uh some some basic evaluation results evaluation is still working in progress in this work so first of all again compared to Prior decentralized credential schemes that use threshold signatures we do achieve a flexibility selection of signers but with small and anonymity sets and we also give the first construction for

single use decentralized credentials um we have a proof of concept verification results using ethereum so assuming that you want to verify all these credentials on the ethereum blockchain so um recall that zebra was the optimized version that was doing like zero knowledge bad things on top of the original coconut credentials so for our scheme if you want to verify a bats of 64 credentials the amortized course would be with using May 2000 uh three prices it would be 0.64 cents per credential while for zebra it will be 2 2.24 and for a batch of 512 credentials

again you can see that it goes from 0.4 to 1.6 um again the important thing to note is that for our credentials and this was the basic scheme that you don't have any attributes or anything it just requires a single BLS verification a while for verifying this coconut or zebra style credentials you have to assume that the underlying blockchain supports zero knowledge proof verification yes are you using the precompiles for doing pairing based I'm sorry are you using the the BN uh 250.

the built-in one yes which I know that they're not they might not be ideal got it okay but that would be the same pre-compile used for snark verification I I would assume so yes previous slide slide cannot you use um group elements as attributes or just use some algebra cache function like pidders and hashes like I don't know the attribute would be M and or G to the m or something like you don't want to use this ugly no no the problem comes from the fact that you don't need to cast the message in the BLS signature so the commitment uh the the problem is not how I construct a commitment the problem comes from the fact that the signature needs to be a hash of the

commitment and cannot you use some algebraic hash functions you mean a different house function um or something or well it still needs to map to an analytical point for the for the BLS construction right yeah I'm happy to talk about this more but it for like for for BLS signatures you still need the fact that it has function Maps the electrical problems all right so moving to the second part which is uh as I said much shorter uh keeping the same the same theme of BLS multi-signatures we are going to look into a different application and this is um

signing blocks um in a proof of stake protocols so I'm not gonna spend too much time explaining what proof of stake is but the thing that they're going to focus on is that in this proof of stake consensus protocols in every Epoch you have a static set of validators and then subsets of these validators sign every single block that ends up on the same so um to set up notation we're going to have a fixed Committee of n validators by repo and we're going to have subsets of M validators Computing multi-signatures in every single block so multi-signatures have been very popular in this proof of

stake setting because you want to have sort signatures by a set of signers on the same method with the essential year block here have actually been a very popular primitive for proof of stake protocols exactly in order to do this um the signature aggregation so let me in the previous slides I showed you how blind DLS multi-signatures work so let me just abstract out the DLS multi-signature path so as before you have this like group D or prime order Q with generator G relation to sign a message every

validator in the multi-sync setting is going to pass the block raise the output to its secret key and randomize it by this Factor AI um and I'm going to say what this Factor AI is we saw that before as well and you aggregate the signatures by just multiplying them together so this AI factor is the same factor that you use to randomize your keys during key aggregation and again this Ai and I should note here that those are two different has functions um this AIS again the house of all the public keys of the signers of this block are concatenated with the public key of the particular signer that you're

randomizing the public key uh verification is again just checking this pairing equation and the observation here is that in proof of stake this process is going to repeat for every subset of M validators okay so every single time that you have a subset of M by dators that they want to sign the next block they will have to repeat this process so in this work we had this very simple observation and we said well in proof of stake protocols you do have this large committee this larger Committee of n members which is static during the whole epoch

you just have subsets of this committee signing blocks um again during the same app so having this very specific structure can we do something better so this was the question that we asked and the observation here was that it turns out that it is possible to run this key aggregation process once at Epoch for the full set of all the end validators no matter which subsets of invalidators compute signatures later so what is the benefit of this the benefit of this is that you are going to save you're not gonna you're not going to save anything on verification so

you're not going to save anything on the binary pairings but during the signature process you are going to save a lot of exponentiations by not having to repeat this key aggregation process so here is how our scheme works and just to see the the difference I'm keeping the original scheme of BLS multi-signatures on the one side of my slide so now again we have this fixed Committee of N signets and then we have subsets of s signers of M signers the validators the validate every single block so the kids generation algorithms exactly as before

every single signer is going to um create this the key as a regular BLS might be seek but no we assume the following at the beginning of the epoch once the whole Community has been identified all end committee members will run this Kitty randomization process as follows they will re-randomize their key by taking these AI factors that you use for key aggregation using the full committee okay that you know ahead of time so you're going to randomize your public Keys using these randomizing factor that uses the full committee

and you're also going to re-randomize your secret key okay you do that once you pay all these exponentiations once at the beginning of the Epic oh every single time that you want to sign now also keep in mind that when you're signing you have these subsets of this smaller number of validators and I'm realizing that the selection of M for the number of validators is kind of is bad notation because I'm using M for my message as well but um anyway the idea now is that every single one of these invalidators when they want to sign they sign using a regular um BLS signature but using the

randomized key where again for the randomization they use the full set Without Really mattering who is the who is participating in the subset that is signing now and you aggregate the signatures again just by multiplying them together the key aggregation doesn't need to do any new exponentiations you're just aggregating the keys of all the subset by multiplying together this randomized keys so again the observation here is that you have to do this exponentiations only once at the beginning of the epoch every single time you sign you just sign like doing a regular dla signature and

you just multiply the signatures together without X electron cities like a you know a pretty reasonable way to save verification is the same as before this seems like a pretty reasonable way to save uh you know some quite significant costs during signing and you essentially save MX pronunciations by signature assuming that you pay these cost once and um just to convince you we have some implementation results so just to um decode this graph so this is SMS is how we call our subset multi-signing scheme for different number of signers

um here you can see the execution time that it takes to compute a signature you see two versions of the scheme so in BLS signatures you might depending on which care if you want to have your signature shown and in which care if you want to have your keys on you might end up with different implementations um so these are the two different the mean Sig and the mean public here the two different cases that you see depending on whether you want to minimize your public keys or your signatures here and you can see for its case two different costs how much does it cost to just aggregate the signatures together during signing and how much

does it cost to aggregate the keys together and verify so obviously verification because it also includes the padding computation is always higher than just signatures uh just signature aggregation and again the observation here is that you don't have to do any exponentiation some signature aggregation you can just literally multiplying signatures together if you compare that with the original scheme the original BLS multi-signatures um where these are basically this red and golden lines here you can see that this exponentiations they can actually have pretty high costs during signing and while in other case as you also

observed from the previous slide they kind of remain pretty flat with the increase of of multiple signers because again the only cost that you're playing you're paying is multiplications so the interesting part though is that proving security of this scheme with its chains ended up very very tricky so when I first saw these chains of the of the BLS multi-signatures scheme I said oh yeah that seems very natural I bet that we can reduce security to the original DLS multi-signa too so as it turns out the original BLS multi-signature scheme is secured under the difficult man in the random Oracle model and it is using a special technique that is called the forking technique

technique in the security proof which essentially means that you have to rewind the adversary and rerun the protocol again so when we try to work on a similar proof for our protocol we realize that the fact that our adversary can pick different subsets of messages during the the signing queries it could essentially make this proof technique to fail so our first approach and the first proof that we have in this key in the in the paper is a proof under a wicked adversary that fixes the subset ahead of time and says this is the subset for which I'm going to create a forgery so if the subset is fixed ahead of time

this forking technique and this rewinding in the security proof works as before so in this case for this wicked adversary we can get a security proof under the same assumptions under the original one now if we don't want to assume this week adversary then we can again engage we can again use the ADM model and have a security under discrete log but unfortunately the security proof will have an exponential security loss which again is not ideal as a matter of fact we saw that this exponential loss is inherited in this protocol and we actually saw that if there is an adversary that can break

this problem that is called the random modular subset sum problem they can break the security of the scheme so in this problem this problem it basically says that if you have a set of integers and an indicate Target you're trying to find out if there is a subset of integers that sums to the targeting so this assumption is deeply related to how the security proof works here and I'm happy to spend more time offline later explaining how that works um so in order to come up with our second proof we had to use this assumption as well and the interesting part that I want to say

here though is that you don't necessarily need this assumption if you know that the size of your committee is not very large so in particular if you know that the total number of possible subsets is negligible to the output of this has one has function that you're using when you're randomizing your keys then the probability of finding such a subset some solution is negligible how does this translate in practice so we have this and ice in the paper that I have not included here which basically says that if you know that you're committee size is a few dozens or like you know a hundred committee members then the

probability of breaking the scheme using this rmss based attack is negatable and you don't necessarily need to make this assumption for your skin um I'll take my questions about those exponents that you're getting from hashing that you were putting into the thing and you're basically saying is there's a combination yeah you actually there is actually an attack on this I assume because they were at the outputs of a random Oracle yeah there is an attack you can you can model it as an rmss attack um yeah I can I can tell you more we have to go through the security through details of the security group to explain that so I don't know if you mentioned this paper that was like four or five years

ago the accountable subgroup multi-sig paper for BLS but it's I mean it's a very similar thing um so I don't know how the constructions yeah so I think that this accountable construction was part of this multi-bls construction oh no no this is a paper from like 2018 or something well this monthly DLS construction oh I see I think I know which paper you're talking about there's something they're not doing the same the same thing I'm pretty sure they're not doing the same thing um so I mean they're a countable subgroup construction is pretty similar basically saying an arbitrary group subset of the signers can combine

to have a multi-sig but you like can tell which signers did it you can tell here as well I'm pretty sure I don't remember how that construction works but I'm pretty sure we have seen it and it is different I'm happy yeah oh I'm not saying it I'm sure but my point was I mean they prove that they can prove security without the exponential loss so I'm curious what I mean they they have to use the forking limit it's a really like gnarly proof and stuff but I'm just curious like why why you think they why it worked for their protocol and it doesn't work I don't remember how the security proof works but um yeah okay I'm happy to take it okay yeah and I think that's pretty much it

thank you everyone I as I said this is a combination of the works um the first one is a company is a work with my student Dion who's actually sitting back there and collaborators from University of Maryland and cispa and the second work is a work that is done at mistlin Labs research for the optimization of field signature Center I should say that we have also used the help of physics team Z for the second work it is a project that we have discussed with later and Dan I was wondering if you know something is called a proof of possession so I was just wondering how you compare your work with proof of possession because in that case you don't have to do the random Oracle exponentiation right so that's a

good point so in [Music] where do you use proof of process possessions so in many of these multi-signature schemes well there are two different ways to construct multi-signature schemes in order that they avoid the so-called Rocky attacks one approach is to use this proof of proof of possession which essentially says that every user needs to prove knowledge of their secret key the corresponds to the public key so that you cannot have select donkey attacks or you can build signatures like the BLS multi-signature that I I that essentially secured against Rocky attacks without the need of crucial possession right so um in the proof of stake setting we have seen uses of signatures that require loss of possession

um so again this is a trade-off here really on whether you want to do proofs of possession or not um so again in certain cases we've also seen criticism on groups of possession for the blockchain setting uh you know the faculty guide sex residential looks proof it can be annoying um but yeah again like proofs of possession or not it is a trade-off that is well known for multi signatures for the consensus for the second project when you're hashing a list of public keys uh yeah those are some of the previous slides where you showed the construction yeah hearsay yeah can you just use the hash of the latest block say and instead of the list of the public keys

because you can imagine this hash will attest to registrations of all of those public keys and possibly you can just reuse it if you're part of multiple consensus protocols with the same validator set of multiple communities so you're saying randomize your keys in a different way yeah in different instead of using by using just the hash of the latest block assuming everything kind of is written there yeah that's that's interesting we can certainly think about that yeah I'm not sure that it would help us with the problem of the um of the subsets being defined in the security proof so I I'm not exactly sure what the benefit would be on this yeah but yeah well imagine your proof maybe

you will need a tweak yeah maybe you're working on that yeah that's interesting yeah yeah that's it that's that's definitely interesting yeah yep does the hash function need to be do we need to feed it a superset of the public keys for the correctness to work like what do we need from the thing we're feeding to age yeah so viscous function takes all the public keys of your original committee yep yep um and you run meat so every time that you want to randomize every time assigner they want to randomize their own key they have to run this class function with all the keys of the committee and their own key so that they

get different albums I guess I was saying that like you can add the hash of the previous block for example you can clearly add Randomness to it but I was asking whether it's important that you at the very least feed it a super set of the public keys of the Committees that you will later need to verify like basically if I give you just one subset and it was guaranteed that that is the only subset you wouldn't need to Hash so you need to be a little bit careful here because of this Rocky attacks in in multi-signatures you need to make sure that whatever you're asking there it does somehow include information for all the possible signers um so you need to be a little bit careful with what it has in here so assuming that the information of the previous block is already including all

the information that you need as what the letter was saying before is already including all the information you need for the next committee selling selection this might work but again you have to be very very careful because of these Rocky attacks thank you [Applause]