ZK Study Club - Sigma Protocols

Transcript

there we go oh I all right sweet I'm Chris I work for our cosmos sentiment and I'm going to talk about Sigma protocols primarily based on a dense but I thought informative paper by academic art so Sigma protocols I'm the I'm gonna cover the paper slightly out of order because I think it's easier to understand in by first introducing the class of protocols and then going into the example although dem card does the other way but Sigma protocols are I guess a very particular class of proof of knowledge protocols so they're not

quite zero knowledge protocols there are something called special honest verify or zero knowledge and then you can turn them into zero knowledge protocols but they are proof of knowledge protocols they're not general so unlike like Starks or snarks they don't exist for all languages within a class they just specific ones exist for specific relations so any Sigma protocol is defined over some binary relation R and a binary relation R is just a pair of bit strings so like some X and some W where if X and W are in R the length of

W is polynomial in the length of X and W is a sort of a witness to the solution of some computational problem X so X might be an instance of like the discrete logarithm problem or the hash of some witness and then W is exponent and the discrete logarithm problem or the witness of which X is a hash like the random Oracle relation some exam cool so then we can say that some protocol P is a sigma protocol for some

relation R if we start out with this three move construction so we have X and W where X is public so X is known to both approve our PR and the verify or VR can you see my mouse yes kind of but only the prover knows W and this protocol P is of a three move form so we start out by the prover sending some message called a verifier can utilize a and X and it sends back a challenge which we call e then the prover replies with a replies e and the verifier has to

decide to accept or reject based on the things they know which are X which is public a from the first message e which they determined randomly and Z which was the provers reply so there are only three possible rounds which is one of the reasons I think Sigma protocols are a nice initial proof of knowledge less Sara knows protocol to analyze because they're like structurally simple the number of rounds is constant it always takes his form and then so the protocol class is defined by three other properties one completeness if the prover and the verifier both followed the protocol then the verifier

x and the prover actually knows w then the verifier accepts with probability once the verifier always accepts if the Coover actually has knowledge of the secret w special soundness such that for any problem X and any pair of conversations which you just likes transcripts if the protocol runs so a conversation just consists of the triplet a II and Z's of the three messages if there are two conversations with the same a so the same so message from the approver but different challenges so E and D prime where a prime and E are not equal then Z and Z prime are not equal or I guess

that's not required but probably they're not equal then we can compute efficiently W so if like the verifier somehow the prover has to be careful because the prover sends the same challenge a and gets back to different sorry sends the same initial message a and gets back to different ease and like to protocol runs and they reply according to the protocol with Z and Z prime then the verifier can actually compute W is that special sadness which we can use to prove some other useful properties later on and then secret protocols are finally special on us verifier zero knowledge so they're not

malicious verify or zero knowledge but they're if the verifier follows the rules of the protocol they don't learn anything about w and that is defined by the existence of some polynomial time simulator called m which on an input computational problem X and a random challenge e outputs a conversation a e and Z which has the same probability distribution as conversations between an honest prover and verifier on the input X this means that the honest verifier can't distinguish this from ability distribution from the probability distribution in which prove ER actually

knows w so it's honest verifier zero knowledge because there's no knowledge imparted to the verifier questions so far yes on B&Q so what is the relation between P and Q like one of them how can they both be same or one of them will definitely be bigger than the other one or vice versa so between P and Q yes the two crimes in the discrete logarithm problem so in snores protocol which is a sigma protocol for proof of knowledge of

screen log Q is a prime divisor in P minus 1 so P is like some Prime and then music advisor and V minus 1 ok I see so snort Sigma does not dictate the relationship between P and Q but any protocol based on Sigma can have its own relation between P and Q so Sigma Sigma protocols are a class of protocols in any protocol which takes this 3 move form operates over a binary relation R and fulfills completeness special

soundness and special ons verify or zero knowledge is a single protocol like by construction so storage protocol is just an example many Sigma protocols might not have Prime's P and Q at all ok but they will have this X and W so in snores protocol P and Q are part of X they're part of the like problem the computation of problem ok thank you so in snores protocol which is the first section of paper X so the computational problem is a quadruplet of PQ G and H with and some secret W in natural numbers mod Q where

P is a prime Q is a prime divisor in P minus 1 G is an order q element in natural numbers mod p and h is G raised the W mod p so W is the secret exponent which the prover wishes to convince the verifier that he or she knows and then the prover does this in the Sigma protocol form as following River chooses some random R in the natural numbers odd Q and sends the

first message a equals G raised to the power of r modulo P to the verifier then the verifier chooses some random challenge e which is in the natural numbers mod 2 raised to the power of T so T which is just the size of the challenge is a free parameter so we can construct different protocols which have different challenge sizes it affects like the error chance of the protocol the chance that the prover who doesn't actually know W convince the verifier the larger input size we take the lower that trances but we must have to raise to the power of T is less than

Q such that so that the challenge will be in the set of natural numbers mod Q then the prover says go ahead why is T distinct and security parameter or are they the same ah it is the same it's just a quality in this paper the prover then sends the final response Z equal to R so their initial message plus e times W modulo Q to the verifier and the verifier checks this equality that G

raised to the power of Z is equal to a times Atreus are eating modulo P so let's look and see if so this is like music island yes so this is the sonorous protocols definition under the Sigma protocol form so we start out with a problem instance and a witness constructed this way and we run these three steps now let's see if it satisfies these three properties property one completeness that one we can see by just checking the math so G to the Z Street to the rgw until Q is equal to a times T the W the e is equal

to a times H D so if the prover actually knows W then this will hold special soundness then so if the prove our answers sends two A's to the same A's and then answers two different challenges in a prime then we have some Z and Z Prime the prefers responses such that G to the Z is equal to H a times a to the e mod p and g 2z prime is equal to a times H Z prime mod p and we can

divide up these equations to solve for W so we can efficiently compute a w given two different challenges and responses to the same initial message and finally we check to see if our protocol is honest verifiers their knowledge this is just pretty simple so if we have if we want to construct a simulator M then we can just take a random Z and the natural numbers modulo P and computes given and our simulator knows the challenge so we

can compute a equal to G equal to z times h to the negative e modulo p and some notes which dem guard lists here it's as I mentioned it's not malicious verifiers their knowledge because Q and to the team must be exponentially large the security parameters inverse into the T sorry the like chance of error not the security parameter the Jazz Ameri is just the chance that the prover can convince the verifier that they know a w even if they don't actually know the

Associated W so with one over two to the T chance the verifier could incorrectly conclude the proof windows w another note is that p and q can safely be like constant and the verifier for many different w's in many different runs of this protocol the verifier can just check that they are prime once and then read the protocol many times so in practice like these constants are chosen for you know some program and just coated in this constants of the program like if the program is a blockchain client or something like that

questions on snores protocol [Music] cool so it's easy to change the input length with sorry the challenge length with Sigma protocols so they can be composed easily in parallel where the prover sends just two initial messages like a and a prime the verifier sends back to challenges a and a prime and the prover sends Z and Z primes this is like if we have a signal protocol we can

construct another signal protocol just by running the first signal protocol in parallel by sending like two messages at once know that the prover can't or shouldn't mistakenly send the same a twice because then per special soundness the verifier could compute W so we have to be careful there also with the input length can be shortened of course giving up some error probability by the prover just appending zeros and the verifier like treating this treating the challenge as if zeros were appended so if the prover and verify have some initial agreement that they will append ten zeros to the challenge value they

don't actually need to send the ten zeros so if you care about the communication complexity in this challenge and response that go from the b'ougar to verifier you can shorten that by appending service cool so the next in stink construction which will see little later on enables turning single protocols and zero knowledge protocol so malicious drivers are verify your knowledge protocols is an or construction sir proving constructing a single protocol to prove the knowledge of either one W or another W so there's

some public - public problem instances X naught and X 1 and the prover wants to prove that they know the solution to one of them but they don't want to prove which one they know the solution to so we start out this is like a medicine or protocol construction so we start out with some Sigma protocol P which operates over this binary relation or and we start out with two problem instances X naught and X 1 which are both known to both the prover at the verifier and then the prover knows the solution to one of them but presumably snow off the solution to the other one although they could know that - and still prove they know one of the other

so the intuition behind this as I interpret it is basically the approver completes two instances of the protocol but we allow them to to cheat we allow them to use the simulator on one of the instances and we construct the challenge in a way such that the verifier doesn't know which instance they use the simulator on so then they can't distinguish which W the prover actually knows but they know that they know one of them because the prover couldn't have used the simulator on both so to construct P or so like the or construction on top of a particular

Sigma protocol P here are three steps the first step is computation of a so the prover takes so I'm sorry the subscript B is the one for which the prover actually knows the solution so there's X naught and X 1 and if the prover knows W naught then B is 0 and the prover knows W 1 and B is one so to start out to compute a the first message from the food of the verifier prover takes the actual solution they know and uses the underlying signal protocol P to compute the first message a sub B for P then the prover chooses the challenge call Y sub 1 minus B so

like the challenge for the problem instance 2 which they don't know the solution then the prover runs the simulator M so if we scroll back up we remember that if we had underlying signal protocol P then there is some polynomial time simulator M so he now here we're reusing because we know that the underlying protocol P is a single protocol we're assuming that the prover has access to the simulator and the prover can use the simulator on the problem instance that they don't know to produce an output transcript AE and Z for the problem instance which they don't know then the prover sends both a

0 and a 1 so one of which was its honestly computed computed with the secret which they didn't know and one of which was computed with a simulator to the verifier the verifier doesn't know which one was computed with a simulator and which one was computed with a real secret then basically as before the verifier chooses some string s and sends it river and to construct the response the prover sets the challenge to the problem instance to which they did know the solution to the exclusive-or of the challenge which the verifier sent

and the previous challenge from the problem instance which they didn't know the solution and then the prover computes the response message Ziza be using of the response message for which there were four the problem instance to which they do to the solution using the underlying c-more protocol P to this challenge and they get out with all their inputs and they send that back to the verifier and of course they already have so they send

that along with the final response which they computed earlier on with the simulator so one of these responses Z naught or z1 was computed actually in step 1 but the verifier SR the prove it didn't send it yet but one of the responses to the problem instance which the prover does actually know the solution to was computed according to this XOR challenge value so then the prover sends back to the verifier Enoch Z naught e 1 and Z 1 and the verifier checks that the exclusive worlds and that the underlying single protocol P accepts both

transcripts so accepts a knotty not Z not on the public problem instance X naught and accepts a 1 e 1 and Z 1 on the public problem isn't X 1 so turns out that this construction is a single protocol and it also has this other nice property called witness indistinguishability which means that the verifier can't learn anything about which problem instance that proven a is the solution to so basically the probability distribution sits a little more formally the probability distribution of these transcripts which the verifier sees is independent of this

index B which is 0 or 1 so is independent of which X naught or X 1 the proofer actually does the solution to later on we can use this to get Azera knowledge malicious verifier construction so it's complete just by construction special soundness so checking again to see if our metasoma protocol B or is fulfills the special status property which says that we can compute W if we have two conversations with the same first message but different challenges so we can check

that by saying if we have to accepting conversations a not a 1 s not a 1 C naught Z 1 and E naught a 1 s prime e prime not you probably one Z prime not Z prime 1 with s and s prime are not equal so different challenges then we know that one of these E's different because of the way we can we because they're constructed by +4 and then we can use that different e to plug in to the

underlying Sigma protocol which we also know especially sound so we get these two so for either sequels or sequels if one EMC is not equal to e sub C prime so either he said not doesn't equal B prime not or e1 doesn't equally prime 1 then whichever of these is not equal we can take a sub c e sub C and C sub C and they said C prime sub Z and Z prime sub C and plug it into the special sadness property of the underlying Sigma protocol P to get back the W so then we know that our or construction is also

specially sound then is it honest verifier so if we just take the again back to the property honest verifier is where if we have a polynomial time simulator which has access to both the input and the random challenge II can output an accepted conversation with the same probability distribution we can do that here by choosing me not anyone at random such that this s equals e not X or e one holds and then run em twice on X naught e naught and X 1 e 1 and we get out and accepting transcript then

finally witness indistinguishable so we want it to be the case that the probability distribution of these conversations select the transcripts of all these protocol runs is independent of which solution the prover knows which problem solution the proven is secret for so if we sort of look at this a downgrade explains it if we look at the form of the transcripts which are going to be just all of these values a naught a 1 s naught E 1 Z naught Z 1 then we assume a naught a 1 are choosing by honest prover so we have some verify of

e star where V star could be malicious it's not necessarily honest so V star determines the distribution of s but II not an e one a random Z naught and Z 1 have distribution determined by the arms prover which is sort of true for the one to which the prover does another problem instance and it follows for honest Farah from honest verify or zero knowledge for the one to which the prove it it's not another problem it's a solution so then since none of this distribution none of these things depend on this index B we know that no such algorithm v star could

differentiate between B equals 0 and B equals 1 I thought this expedition just a little bit hand-wavy so if you have questions totally ask them so oh okay I I didn't there's so much of this I don't follow but things that I what I really liked actually the way you just kind of like walked through it again and then compared it back because that actually has helped to illuminate it a little bit you mentioned there that you have to run so on the honest fair fire ZK so you're going through it once and once once with the real once with the simulation and

then it says like choose two points make sure that they work and then run it twice but I didn't really get that like white Y twice so M is M is the simulator for the underlying protocol and so we've constructed this protocol or on an underlying protocol P and M is the simulator for P so in our protocol or we're proving knowledge of either a solution to ax naught or a solution to X 1 so we need to produce Z naught and Z 1 because we that's what we send to the

verifier in step 3 so we're using we're using the simulator starting a meta simulator we want to simulator for P or and that stimulator for P or needs to produce both of these enid Z naught and E 1 z 1 pairs to send to the verifier as an accepting transcript since what we need to run the underlying simulator twice got it I think I thought of it as more like you're trying to prove something by doing it like I didn't I didn't get that you're actually just trying to get two outputs and that's why you're doing it twice yeah I mean I guess the intuition

behind the simulator maybe it's helpful is that if the prover can have access to the pollens which the verifier will send they can convince the verifier to accept without knowing anything about w so like zero knowledge mean that the the way we derive zero knowledge is by assuming that no one knows w and then it can convince the verifier anyway then clearly the verifier wasn't learning anything about w because the prover didn't know it okay so if the proof to do that then the proving needs access to what the verifiers challenge will be so like so some way to think about this is

if the prover and verifier we're running on you know a rewind able computer or something then the prover if they had the ability to keep rewinding could like rewind until they get an e which is equal to the e which they wanted today like if i rewrite the verifier infinitely many times and get such an e and then once they have such an e they can generate this accepting conversation at least that's how I read it is that is that how you read it there yeah thinking how it rewinds is I don't even simulators like you trying to simulate a thing you the you can use essentially

how the proof even think of a simulator as like approver that knows the verifiers input before it's committed to a thing I don't know yeah I mean I yeah it is the intuition that like by knowing the verifiers knowing the verifiers input is equivalent to being able to run the verify or any number of times until they use an input which you wanted them to use yeah as long as it's not like an exponential number so your senator has to be a poly-time simulator yeah okay

I think I might skip down to driving zero knowledge so if we want to end this I actually do need to end this on the hour so very briefly we want this definition of a hard relation the dunkirk goes over so this whole construction is only useful if it is hard for the verifier to find W so if the if it was easy because the verifier knows X so if it were easy for the verifier to just find W given X then our zero knowledge is not going to hold up because the verifier can just compute W so we want to kind of formalize the notion of what it means for it to be

hard to find W given a particular X and basically this means that we want there to be there to exist some probabilistic polynomial-time algorithm G called the generator which takes an input and input byte string a bit string and outputs a problem instance and then it be thing for it to be the case for this relation to be hard it must be the case that for all other possible probabilistic polynomial times algorithms a if we run this generator and we give the algorithm a the problem instance that we get X and

the problem and the algorithm a computes some W a the chance that this W a will be correct the chance that the pair of X and W a will actually be in this hard relation set is negligible in K so as negative on the size of our input to the generator so basically this means that a relation is hard if we can generate problem instances for which no polynomial time algorithm can find a solution with a non-negligible chance [Music] so then if we want so we want to derive

zero knowledge so the cool thing about this or construction widens are being very useful as we can use this witness and synchrony although Democrat doesn't go through and actually prove all of this so he just says it and I'm taking it a little bit on faith the intuition doesn't seem terrible but I don't know if I can differentiate from a case where the intuition was actually wrong but he says that if we take this generator G and we have some underlying single protocol P we can construct P or as above and then we can invert the Sigma protocol in a really cool way so we have some private public some public

problem statement X and the prover P R has some private solution W like usual then we run this three-step protocol so the verifier now uses a generator to generate a new problem instance unrelated to whatever the public X is a new problem instance X Prime and W Prime but that will be in this relation then the verifier sends this X prime to the prover and proves using the verify of proves the verifier is running the proof

algorithm using the underlying single protocol P knowledge of this whatever W prime that they generated so they prove that they know some W prime corresponding to this new problem instance X Prime then the prover checks that whatever the verifier just proved to them accepts with the underlying single protocol P and the prover then proves that they know using P or either W or W prime so they prove that they know either the private w that they actually know or the w prime which to verify are generated

and this is malicious verifiers their knowledge according to dem card because if we had some simulator against like any verification any verified algorithm the simulator could rewind the verification algorithm to extract this w prime so they could get out what W Prime the verifier generated is in the generator and then they could run step 3 proving knowledge of W prime instead of knowledge of W simulator doesn't know W but for any verifier as long as this as long as the underlying signal Protocol P

accepted then the simulator will be able to prove since they know W prime that they know that W or W prime and because if we go back up to how we constructed P or because of this witness indistinguishability property then this malicious possibly malicious verifier can't distinguish whether or not the prover knows W or W prime so that means that this will always produce like acceptable transcripts which is malicious verifiers their knowledge because the verifier in this case is arbitrary just like seems reasonable but

he doesn't go through all the proof details does that seem reasonable X prime is the where's the challenge or approver so this would be more than that I get there coincidentally three points here but this would actually be more than three steps because the verifier and the prover needs to run need to run two similar protocols between them also the better commits to this like uh sends their proof first and then the prove the / begins right so so first the verifier generates a problem instance

then the verifier playing as the prover runs a three-step Sigma protocol to prove that they no knowledge of W prime then the prover once they've run that three-step Sigma protocol runs a second three-step second protocol P or proving that the prover now knows W or W prime okay this thing's this would be six steps I guess or seven if they need to send X run first then finally it's quite easy and it turns out exceptionally

convenient to transform signal protocols using random Oracle's into non-interactive non-interactive versions so if there's some random Oracle which Maps bitstrings of some lengths of bit strings and some other lengths where the outputs is completely random conditions on the inputs but the random Oracle always returns the same output for the same input then instead of the verifier choosing a random challenge we can simply use the random Oracle to compute what the random challenge the verifier

will use is from the initial a and if the prover can produce this a and Z and the computed challenge using a random Oracle then the verify are like operating after the fact can simply check that the random challenge as the verifier also has access to the random Oracle verifier can check that the challenge is equal to the random Oracle computed on the input a and that the final transcript a ez accepts so maybe the prover is like some blockchain wallet sending it and the verifier is a blockchain client which is verifying the transaction you know many years later but still has

access the same random Oracle so in practice random articles or the best instantiations of random Oracle's our hash functions but they're not perfect because we at the moment don't have any which for which we can prove that the output is totally random conditional on the input but in practice that seems to be good enough it's good enough for block chains and many kinds of high value capture graffito criticals thanks for is that helpful yeah I I think so I mean I think the thing I really liked was that you took you kind of changed

the pattern of this paper that's like as I mentioned before the call jumping into it I was just like whoa you like jump in right away and I actually think the way you extracted that part and then continuously like referred back to it I thought that was really good cool I mean what I like about singer protocols is that they're relatively simple to understand and reason through don't require prior knowledge beyond like very basic group theory for snares protocol and practice I I don't think they're all that useful dam guard mentions using them for our commitment scheme which which is possible I was not sure why you

would really want to but I guess maybe because it's perfectly hiding whereas like something like hash function might not be if it wasn't properly it's also like it's also hand underneath if you're giving things over your group okay like some computation well in practice not in terms of time but like for right now a camera for camera Arwen cs4 zero knowledge proof systems this is then a cheap commitment scheme there's only a couple group expectations I see okay do you know of any instance of Sigma protocols being used in practice short signatures so shortening

ensures you take the Schnoor identification protocol which I think you discovered earlier then you just do a pH me transform mm-hmm and then horse legs are like better outside of DC TSA I think are they like do you use a signal protocol versus the snore what the call yeah like would you would you be either/or or because I for some reason I always see them sort of together let's know they're uh you do a future Shamir transformation on this thing called the straw identification particle I remember the names correctly then you get the snarf signature okay but basically the

argument for the short signatures being like the storm signature is a zero knowledge proof and the argument you have is that suppose someone like so suppose someone did create a signature and suppose you can rewind them to create it's the same thing try different challenge and on the same message then you can recover their secret therefore they know the secret mm-hmm which sells the same property is this like this signal protocol cool maybe that's another we do is but oh the next one we're doing is gonna be at Shimer in depth witness alistair but i think

it's not gonna be next week because he I think he can't do it so yeah it's gonna come soon so we're like I wonder if we didn't kind of do that in Reverse but would it have been helpful do you think would be helpful to like see the Fiat from here before diving into this stuff where do you think it's fine to do it separately for me Fiat Ramirez like simple compared to the other parts Sigma protocols but maybe they're more complex versions okay yeah well I'm gonna I'm curious to see what he wants to do with that yeah the hard part of single protocol it's yours aren't you're just saying that a inside

of the verifier sending you some madness you use the hash as a proxy for randomness there's like some there's a lot of complex subtleties that gets me a profile we're like there are things that are actually not safe to pH mere air but uh so we don't know it's like if it's actually a safe transformation in general hmm okay cool well listen thanks so much for doing this and yeah I'm gonna post this to YouTube now so if anyone wants to share it or see it later yeah so thanks again yeah absolutely cool to continue with some others our knowledge protocol maybe I can go over cuz he has those lectures

or something yeah I do that that's good all right well I'm stopping