ZK Whiteboard Sessions - S3M5: The Ligero Proof System, w/ Muthu Venkitasubramaniam

Transcript

Welcome to ZK Whiteboard sessions season 3. Today we have Mu, author of the kind of OG succinct proof ZK, you know, practical ZK paper, Liharo, um, who will be explaining to us actually how it works. I don't think you've done a whiteboard session before, have you? >> No, I haven't. >> Cool. Cool. And then what do you do nowadays? Actually, I know you're a professor, but you know, feel free to give a full intro. >> Um, hi, I am uh I'm Mutu. I am co-founder of the company Lihiro. Um, I am a professor at Georgetown University currently on leave trying to uh build this ZK and do something useful with it.

[laughter] >> So, what will we be talking about today? like what's the rough outline of the lesson plan so to speak? So I'm thinking that um I want to you mentioned about you know OG I mean I want to talk about the OGs of cryptography the introduction of zero knowledge proofs and multi-party computation as well as this concept MPC in the head. >> Okay >> that is the foundation of the Lihero ZK system. So this is going to be part one. Uh part two will be the description of the Lihero system and part three is going to be um more about uh where do we go >> efficiency >> um what's the end game >> okay yeah it'll be interesting because you know uh I think like at least my

version of it in Liara is normally like a boring you know straight shot linear algebra version that you're just like yeah you have some matrices you do some stuff you get the right thing out so I'm very curious about this NPC in the head I remember you mentioning something like you kind of get ZK for free if you think about it as an MPC in the head protocol and so I'm I'm quite curious to like hear like you know the the OG perspective on like the hero why it works why it is what it is and yeah so feel free to to get to it. Yeah, awesome. U maybe um I want to say that you know the one of the things that motivated us uh when we designed the system was also that we wanted it to be simple actually before being practical we wanted it to be simple. So um I would

uh you know be happy if at the end of the session people believe that Lihiro is actually a simple CK system. Uh in fact um I'm going to uh wager uh to someone that they can take the description I give here and write uh a prompt to chat GPT and build an end to end Z system. >> Um >> that's my goal. [laughter] >> All right. So um let's begin. I sort of want to uh start by saying um you know two works that uh um I want to talk about or mention um and the work that introduced zero knowledge

proofs actually did a lot more than just give us zero knowledge. Mhm. >> It forms the cornerstone of security of how to define security and how to think about it. Actually the ideas had originated already in this work of probabilistic encryption in this in the previous work by Gulwaser and Malli but it was refined in in this work where they introduced interactive proofs and zero knowledge proofs. >> So I want to start with um a little bit motivating motivating this right. So um to talk about zero knowledge as well as security or privacy >> mh >> you first want to capture what does it mean to you know u hide something or leak something or what does it mean to

say that the verifier gains knowledge without defining knowledge you can't define zero knowledge >> so for this I'm going to um repeat maybe almost verbatim what my adviser Rafael us taught me and I'm sure he heard it from his adviser Sylvio Malli. >> Um naturally >> and I'm going to share you know two YouTube links of Sylvio and Shafi introducing zero knowledge. If you haven't seen it don't watch the session go and watch these videos because I will guarantee you after watching it you will fall in love with zero knowledge. it just you know it cannot happen that you don't fall in love with uh with zero knowledge and both of them have really

different perspectives but here it's going to be the sylvvio way so he calls something um the knowledge act okay what's the knowledge act basically two principles one efficient computation is free >> mhm and the second randomness is free seem ben n really like to even call it an act. But uh I'm going to tell you the way um Sylvio says this. If I come to you say I have a bag of numbers and I'm going to say hey I have a proposal for you.

>> If you give me $1,000 I'm going to sort these numbers and give it to you. You're going to look at me strangely and like why the hell are you going to pay me $1,000? [laughter] I mean my phone maybe even my smartwatch can do this today. >> Oh yeah. Yeah. >> Right. I mean like a billion times a second or something. >> Billion times a second. You're not going to like pay me $1,000 for that. >> If I came to you again and I said, "Hey, okay, maybe that was not your thing. I'm going to toss a,000 coins. A dollar a coin. Sure." And you're going to be no thank you. Like I can do this. All the devices I have is capable of generating randomness. The knowledge act really is saying that for an adversary, an

attacker or an algorithm that can run efficiently with randomness, you cannot stop an adversary from learning what you can do with this. So you should imagine that an attacker of a system >> Mhm. >> when you're asking what can it learn? Well, it can learn anything based on what it sees in the system. But applying a efficient algorithm, what is an efficient algorithm? I mean from uh from a theory of computation perspective, this is what's called probabilistic polomial time algorithms. But these are the two things algorithms that run in good time and can use randomness. So

knowledge or something that you cannot prevent an attacker from learning in a system is efficient computation on what it sees. >> Okay. >> Okay. So this is what knowledge is. So when we define a system a protocol etc. you cannot prevent an adversary from learning what is free. >> True. Okay. Now zero knowledge actually this is in some sense I want to say a precise measure of what an algorithm can learn from a system and now you can define zero knowledge to be that an attacker should not learn anything more than what

is free >> okay >> okay okay and really zero knowledge the definition of security captures precisely this okay so let's go into this a little more uh slowly. So when you think of an interaction between a prover and a verifier >> in a zero knowledge proof system, I'm going to do the interactive version. I know that we are all familiar with the the non-interactive version. >> Now >> we're going to say that in a typical zero knowledge proof system, there is an input statement that both the prover and the verifier has and the prover has some additional sensitive information.

Now you're going to ask in this um uh there is also an algorithm or a predicate or a compliance check I want to say on the inputs of the prover that the verifier wants to know if it is yes or no. >> Sure. >> Okay. So this is what captures a typical instance of a zero knowledge proof. Mhm. >> So now uh you want to ask here what does the verifier learn from this uh interaction or does not learn from this interaction. What are we trying to hide using a zero knowledge proof system?

>> Sure. >> Okay. >> So here is what ideally you want. The verifier is going to learn the result of this which is that whether it's yes or no. And let's say that it learns it's yes. >> Okay. Because that's typically what you want. The prover is trying to convince the verifier of something. So the yes case is what you're looking at. And now you want to say the verifier should learn nothing more. >> Okay. >> Okay. That's zero knowledge. But what is this nothing more, right? And the nothing more basically says that the verifier remember this by the knowledge act the verifier can learn something. I cannot say that it learns nothing.

>> Mhm. >> Okay. What is the thing that it can learn? Well, it can learn any efficient computation on what it what it sees. Mhm. >> And ideally I want to say that that's all it can learn. >> Sure. >> Okay. Now in an ideal world where the prover was not there, the verifier was on its own and it knew that the statement was true, what it can learn is any efficient computation on X and the fact that this relation holds true for some double. >> Mhm. >> Okay. Now in an actual proof there is something more happening. In an actual proof actually the verifier in addition to learning this it's also learning there is a transcript of this

interaction there's also randomness that the verifier might use in the process. >> Mhm. Mhm. Mhm. >> So now I can no longer say that what it's learning is just efficient computation on the input. >> There is something more that it sees. So now to prove that this is a zero knowledge proof I'm going to say that this transcript carries no additional information. Okay. >> Okay. And I'm going to tell you again another part of this. It was not just defining what knowledge was but also how to show that it is you know zero knowledge. So that's a second part of uh this contribution.

>> But really what I'm going to tell you is that >> I'm going to claim whatever the verifier claims to have learned more because it saw the transcript >> Mhm. It could have leared on its own without even interacting with the prover. >> Interesting. >> Just on its own, just with the statement and this fact, it could have leared on its own. >> Okay. >> Now, the way you're going to so to demonstrate that a protocol is zero knowledge. In fact, this is exactly what I'm going to show you. I'm going to show that whatever an algorithm claims it could have learned from the interaction, it could have leared on its own.

>> Okay? And that's why this proof system is zero knowledge specifically zero additional knowledge beyond what it can do on its own. >> Interesting. I mean so one question I have is right like if somebody tells me look define something like zero knowledge. My initial definition would be something much sillier. It would be something like the probability of like any satisfying witness that like satisfies this thing is yes given the public information is essentially uniform. Right? Like in other words, like whether there's a witness that like encapsulates, you know, the actual data the prover has or any other satisfying witness, I would have no idea which ones of those uh it would be, right? How does this differ? I don't know if that's a it

is kind of like a weird notion. It's very statistical in origin. I'm just curious if it is different or if it's similar in spirit or one implies the other or vice versa. >> The actual definition implies what you're saying. Okay. One of the parts what you're telling me is that or at least one of the properties you're identifying, let me give an example is that there could be two different satisfying solutions to this thing. >> The verifier should not learn which one. >> Correct. Exactly. Yeah. And for any two, they should not learn. And in particular, like I think that is enough to imply that you are uniform over the space of satisfying witnesses or something, but I'm not 100% sure. We'd have to think about that. But okay, cool. Cool. So this definition does indeed imply the statistical definition.

actually something called what you're saying is something called witness indistinguishability or at least a part of what you're saying is called witness and zero knowledge implies witness indistinguishability but not we don't know the other way around. >> Okay. >> Okay. >> Um so this is I'm going to not go very formal but the concept when someone says they have a zero knowledge proof system here is a question you need to ask. >> Where is your simulator? >> Okay. If you don't ask it it's not zero knowledge. >> Okay. Now they could use words perfect zero knowledge. ZK you give me a simulator. The simulator is what demonstrates a proof system is zero knowledge.

>> So what's a simulator is if I want to show that you know a protocol is I'm going to give actions for what the prover and the verifier has to do. >> Okay. Now to prove it's zero knowledge I need to give you another algorithm that's called the simulator that takes as input only the statement. Mhm. >> And what it can do is actually output a transcript and some um randomness. Okay. >> Okay. Now the property the simulator needs to satisfy is that what this the distribution of messages and random coins that the simulator outputs.

>> It should be hard to tell it apart from the actual transcript and the randomness that the verifier sees. So there is some actual distribution the verifier sees in an interaction >> and there is a distribution that the simulator outputs. Mhm. >> Now to prove it's zero knowledge I need to show first that this is efficient meaning polomial time it can use randomness >> and that no one can tell apart these two things. >> Now there is a way to define what does tell apart mean again you just use efficient computation. No efficient algorithm can tell it apart. >> Okay that these two distributions.

>> Interesting. >> So if something is claimed to be zero knowledge again I'm being very specific on the kind of zero knowledge the statistical zero knowledge etc. But in the context of practical systems, this is the zero knowledge that is more relevant in >> Sure. Sure. Sure. Yeah. I mean like you could imagine things are like get funny, right? Because it's one example is I have a hash of the witness or something, right? And like if it's, you know, the hash really is a reasonable one-way function, you know, you could imagine that like yes, technically if S is all powerful, it would obviously be able to figure out W or a satisfying witness very directly. So you need the constraint of >> there's actually another technical reason you need it. But I want to say

you stumbled upon another variant of zero knowledge which is related to something you said before is that if I'm able to construct a simulator that is not polomial time >> then I cannot prove zero knowledge but I can prove the witness indistinguishability property that is >> so that's a separating fact. Got it. Got it. Got it. Got it. Got it. But this is something more and something important. Why the simulator needs to be polinomial time? You will know I will tell you in 1 minute. >> Okay. Good. So to demonstrate something is zero knowledge. You give me the simulator and show you need to give a proof that these two cannot be told apart. This is where assumptions come.

You're going to use hash functions, oneway functions, uh whatever uh over there to show that these two things cannot be told apart. Okay, good. Now let's go back to the claim. If if you can demonstrate a simulator, I'm going to say that this proof carries no additional knowledge. Okay? Why? Now, you're going to come to me and say, "Hey, look, I have devised this algorithm verifier that actually learned something new." >> Okay? Um, it learned some the first bit of witness when it should not uh I mean, you should not be able to know because there could be witnesses with both the first bit one and zero. But you're going to come and tell me, hey, I learned that the first bit of this or I don't know the secret key to my uh Bitcoin account.

But >> that would be cool. But you know, [laughter] >> but now I'm going to tell, well, it's not something I gave you as the prover. You could have got this on your own. How are you going, how are you going to learn this on your own? >> You're going to consider another experiment where >> you have this algorithm that extracted out this secret information. Okay. >> Sure. Instead of interacting with the prover and generating this transcript and applying the algorithm on this, you're just going to run the simulator on your own. It does not have any private or sensitive information.

>> Yeah. Yeah. >> So the verifier will just run the simulator, generate this, which is the transcript of the interaction and the randomness of the verifier in this. So it's an equivalent transcript and then apply the algorithm on this to extract the information. >> Okay. >> I see. Okay. >> Now, there are two outcomes that can come from here. Either you learn >> the secret information, in which case my claim was right. Hey, you could have learned this on your own >> or you didn't learn. But now I'm going to arrive at a contradiction because if you didn't learn the same information, then really what the simulator output could be told apart.

>> Sure. >> Specifically, your algorithm could tell apart the distribution output by the simulator and this. >> So, this proof was incorrect. >> I see. Okay. Okay. And usually what that would mean is that this is based on I don't know some factoring assumption or some latice assumption or like some hash function. You have broken that. >> Sure. Sure. You have like reduced this to like a harder problem. But yeah, fundamentally the the the idea is look, if if you're able to extract any knowledge from this particular transcript, then necessarily you must have been able to tell apart the these two things which are like assumed to be a hard problem or statistically distinguishable not statistically sorry computationally statistically distinguishable I think it was name or whatever >> uh and which

>> all those variants are there but here I'm talking about computationally distinguishable okay so just one point and I want to go to MPC is that why should this be polinomial time because I was trying to say that this learned nothing more and now in as part of the argument I had this running this >> to claim that now if this was not efficient then I cannot claim that >> uh that you didn't learn anything more >> yeah the verifier itself could have run the s and figur okay >> all right >> okay so and I just want to say that the concept of this indistinguishability and the simulator was also like fundamental to these works it and you will see that this was also important for defining other Like all cryptographic primitives,

this concept is ingrained. >> Sure. >> Okay. All right. So, I'm going to segue from here to MPC. >> Okay. >> Right. Now, what is MPC? uh MPC allows a group of participants each with some sensitive information to jointly compute some function over their inputs with maximal privacy. Okay. Now, okay. And I need to define what maximum privacy is. Okay. But now given that you we've seen simulator you know what knowledge is this is going to be much

more easier to understand given this. >> Okay. >> Okay. >> Now first what I want by maximal privacy is that so I want maximal privacy against again you can define different things. I want to say against a collusion of parties. Okay. Okay. All right. Now let's say that P3 and P5 okay they are participants in this protocol. Now they interact in the protocol and they learn the output of the computation.

>> Okay. >> Okay. Now I want to say the maximal privacy one can hope for is what they can learn from this. >> Mhm. >> Okay. >> They should not like this you cannot stop because they know their inputs. >> Yes. >> They know the output. It did come from the computation. So any from the knowledge act any efficient computation on this they can learn. >> Sure. >> MPC says that if you want something with maximal privacy your protocol should carry no more information or no more knowledge than what can be efficiently computed from this.

>> Okay. >> Okay. So just like here I want to say that hey what this transcript and randomness did not reveal anything more than what you could have done on your own and actually you can see this already here that I said the efficient computation here was we the input X and the result of the computation which it learned and that's exactly here as well. It's the input and the result of the computation. So MPC to define a protocol is uh satisfies MPC for some function f against this collusion. Collusion is for any subset again you can do it threshold there are many variants for any threshold of participants they should learn nothing more than what can be

efficiently computed from their inputs and the output of the computation. Sure, >> that's it. And I'm not going to go more into the details. Again, you can do this by defining a simulator and it works uh um you know the concepts work similarly as uh zero knowledge. >> Okay, fine. >> Okay, great. Now >> I can switch over with you. It's easier. >> Yeah. Now, what we want to talk about here and I do see that I'm going a little slow on time, but um you're totally good. >> It's okay. Yeah. So I want to talk about a connection between MPC and zero knowledge. First I want to tell you what's the obvious connection. Okay. The obvious connection is ZK is an instance of MPC.

>> Sure. >> Okay. So you just need to take two parties P1 P2. This party has input X comma W. This party has input X >> naturally. >> And you want the output the function that they are computing really is and I'm going to call this X prime. And you will see why is that u you you reveal x= x prime and r of x comm right >> fine >> so I can take any MPC protocol not any but just for the time being if I have an MPC protocol I can uh create a zero knowledge proof okay >> sure >> now in practice we all know MPC is less efficient than zero knowledge not just

because of the progress but you know MPC is less less efficient uh than zero knowledge. But what's more is if I use this generic instantiation of zero knowledge from MPC, I'm going to inherit the assumptions that MPC needs. >> Specifically, MPC needs public key assumptions. >> Okay, it needs in the most general sense, it needs uh uh so something called oblivious transfer. But you can just think of I need public key encryption. >> Okay. >> So, but we all know that zero knowledge can be done from hash functions. Yes. >> Okay. Okay. And there is a separation between hash functions and public key uh uh encryption.

>> Sure. >> Okay. So if I use this generic transformation, not only it's inefficient but also that I'm going to inherit these things. >> Mhm. >> Okay. Now this work that I want to talk about which is by Ishi, Kushi Levitz, Ostrovski and Sahai 07 gives an interesting connection from MPC to zero knowledge >> which is going to give efficient constructions as well as solve this problem of uh uh cryptographic assumptions that you have to do and one word I'm going to say and then I'm going to switch to how this MPC this this is sort of the paradigm NPC in the head

which I'm going to talk about next >> which I'm very curious about. >> Yeah. And I am super excited about uh uh talking here. Um MPC comes in two flavors. >> Mhm. >> Many flavors but the two the the category I'm going to talk about is one is called dishonest majority and the other is called honest majority. It's about how many collusion can you tolerate? Is it 50% like you know the consensus protocols that we know or can it be up to n minus one? >> Okay. So dishonest majority means that up to n minus one can collude.

>> Mhm. >> And honest majority means up to half or up to a third. Again there are many flavors that you can do. >> Okay. Now I want to talk about the flavor of the honest majority which is up to a half. >> Okay. >> Okay. >> Yeah. Right. Given the separation here it's going to make sense I assume. >> Exactly. I want to say that this trans this uh MPC to zero knowledge I can't apply to uh to honest majority protocols. >> Okay. Yeah. >> Because I cannot have an honest majority in two parties. >> Yes. >> Okay. So the minimum I need is like three parties but with three parties I can't do this generic transformation.

>> Okay. The second thing I also want to say is honest majority does not require assumptions like this. Like public key is not needed. In fact, no assumptions are needed to design MPC in the honest majority setting. >> Okay. >> All right. So, >> I'm going to now switch and I'm going to show this. >> Okay. Great. >> Want to go over here or up to you. All right. Let's see it. >> Great. And this is really uh I was a PhD student when this work came and I remember watching um uh this uh this the presentation by by

Yubal and I'll say just like I said I fell in love with uh ZK I fell in love with MPC in the head after this uh [laughter] this presentation and actually there's a tagline which maybe I should attribute to Yuval he says um honest majority is useful even when you don't have an honest majority. >> Oh, good. Okay. [laughter] >> You are. Okay. Great.

>> Interesting. Okay. So, um I'm going to give this construction. Um I'm going to need at least five parties for this construction. And again uh MPC in the head has been um used in several like both theory and you know we've explored a lot in practice. I also want to say there's an entire line of work that are building postquantum signatures using uh this approach. >> Okay. >> Um so it's been super influential in the in the field of cryptography in in general. >> Nice. >> Okay. So I have the same uh situation. I have a prover and a verifier um that wants to the prover wants to convince um the verifier that uh this statement holds

true. >> Okay, you're going to I'm going to the prover is going to imagine uh an MPC protocol is going to in fact emulate an MPC protocol between five parties. >> Okay. >> Okay. Now you'll see it's strange. Why am I doing this? Yeah. Um I am going to give these um I'm going to give these parties um a secret share of the private information. So for now you could think of this as a very simple like additive secret share which is >> um >> equals like w okay >> and what they're going to compute this

function on on these inputs um is going to be reconstruct w >> sure >> output r of x comma w and you can imagine that x is hardcoded in the in I mean essentially this is just the other way of putting this is RX comma W1 plus W5. >> Exactly. >> W5. >> Yes. >> Sure. Okay. >> So it's going to imagine this u this protocol. It's going to basically what does it mean? I'm going to give randomness to each of these parties. I'm going to emulate each of them. They're going to send messages to each other so forth. And now I'm going to define something called the view of a party PI.

And this I mean really means I mean what you would think what a view is. I'm a participant. What do I see in this interaction? My input my randomness and all messages that come into me. >> I don't need to talk about the messages that I send because I can compute it from the information my input randomness and the messages inbound. I can compute my outbound messages. So really the view of PI is its input um randomness and inbound messages. >> Okay. Okay. Now, what is the prover going to do? The prover is going to send a commitment. Let's call this vi. I'm going to define this to be vi. It's going to send a commitment to the the five views.

>> I see. >> Okay. What's a commitment for this purposes of this? Just a hash applied on it. >> But that's not technically true. You have to add nons etc. But just for the purpose of the discussion, I'm just hashing the view and I'm going to send it to the verifier. >> Okay. >> Okay. >> And the verifier is going to pick two of these parties at random I and J. And the prover is going to reveal the actual contents of VI and VJ along with what is called the decommitment. Okay? Like I need to prove that what was what was revealed here was what was committed in the first round. Now if you know Merkel trees this can be easily implemented using Merkel trees. Put all

of these in V1 through V5 in the leaves of a Merkel tree and when I open it I give you the Merkel paths and these two values and I get this. >> Sure. >> Okay. Now what is the verifier going to do? Very simple. The verifier is going to take these two views and it's going to compute the outbound messages of each of these parties. It has all the information. The view has the input randomness and inbound. I can compute all the outbound and I'm going to see if the outbound from VI matches the inbound of VJ. I see >> this is called consistency. I'm going to check if these views are consistent with each other.

>> If they are, >> I'm going to see what these parties output finally as the output of the computation because the output of the computation is this. If it says one, it's one. If it says zero, it's zero. >> I see. I see. And this is also why you can't have for example three parties and pick two is because two reasons. Number one is you want to have honest majority, right? So you need to have less than half. But number two is because you also want to be able you can't just pick a single player. You have to pick or single uh party. You have to pick two parties and check the consistency between the two, >> right?

>> Yes. And no, I want to say there are tricks you can do even for three party. There are tricks you can do even from two party that like I have a paper where I show I I would also say that's one of the simplest zero knowledge systems. Take garbble circuits. I can create a zero knowledge proof from there. you there are many tricks you can do but your intuition is absolutely right >> okay >> that's why I chose five for for exactly that reason okay now I want to >> conclude with the u the proof of why this is good first um >> three properties of a proof system completeness soundness zero knowledge like of a zero knowledge proof system completeness says prover can convince the verifier if it had a valid witness >> it would generate this honestly this will always be consistent great Mhm.

>> Now if the prover uh if the statement was wrong in the first place, meaning there is no witness w or no value that I can put here to make it, >> then you can conclude that some two parties will have inconsistent views. And here you need some level of induction argument to say that if all of them were consistent, there is a true execution of this and every true execution of this will give the right answer. So those are two things you have to do. But if you take that for granted, if I start with a wrong statement, then some two view here are not consistent.

>> Okay? >> So that will be caught with probability at least five choose two. >> Sure. >> Okay. So the soundness of this uh system is 1 - 1 over 5. >> Okay. >> The soundness doesn't sound Sorry. The soundness doesn't sound great. >> Yeah. But I mean you repeat it a few times. You're good. >> Yeah. >> You know, >> good. So this is MPC in the head. And uh I want to say that what is lio? Lihiro takes an optimized version of the MPC protocol itself. >> Okay, >> that when I apply it once, I will get a target soundness that I want.

>> But it also does something. It adds more things to the MPC and to the compiler to get efficiency. Maybe just one nugget is that I might have to assume that there is a broadcast channel to the MPC. And I can tell you broadcast can be easily implemented here in the two party. This compiler can bear a broadcast very easily. >> I believe that. >> Um but really in a in a nutshell this is MPC in the head. It's very simple. >> Nice. >> And um the next part I'm going to say how the Lehiro system is built. >> Perfect. Very cool.

>> So part two is what are we going to cover? >> We're going to describe the Lehi pro system. >> Okay. Now it's official. promised you follow this I will tell you you can u you can code a zero knowledge system a zk snark with succinctness succinct verification right after this part. All right. Okay. This is uh I'm going to present this work that we published back in 2017 uh at ACM uh CCS.

>> Sure. >> Okay. I'm going to um start with one basic preliminary >> um which is uh secret sharing. >> Yep. >> For the purposes of uh this presentation, you will need to know secret sharing, hash functions. I'm not going to go into the proof. If you want to go to the proof, proximity gaps, etc. But the description itself merkel trees secret sharing you don't need anything uh more than that and I'm going to also assume that we are operating over some finite field we can talk about extensions etc. So for now just assume it's either the goldilocks prime baby bear circle stocks bn254 any any of these primes uh that that you love like

we are going to fix one of them the circuit are going to be over that and the secret sharing all of that is going to be over that field. >> Okay. Okay. So, um what I'm going to do is I'm going to uh recently I saw a presentation by Abi U and it was a very nice way of presenting this and I'm going to kind of uh be inspired by that and I'm going to tell this right. [laughter] So, I'm going to define this algorithm encode and decode. Not going to talk about codes much but I'm going to use the words encode decode and then for secret sharing I'm going to talk about sharing and reconstruct.

>> So, what is encode? um I'm going to have um k values and this is going to output um n values. >> Okay. >> Yep. >> I'm going to call this an encode procedure. What does this procedure do? Well, it computes the unique polomial P such that P of 1 is A1. P of K is A K. Um the degree I said unique. So this is degree K minus one. Okay, there is a unique K minus one degree polomial that passes through K points. Let P be this

point and B I is going to be P of K + I. Okay, it's the evaluation of this very same polomial in the next end points. >> Okay, so the first k points the evaluation of the polomial give me what I'm encoding. Then the rest of them is uh what I call is the encoding of these values. >> Okay. And you can also imagine there is the reverse of this decode will give me uh uh from b1 through bn I can get a1 through through a k but you know the decode does need the parameter k

>> to because I need to say that and the decode can fail if this doesn't work in the sense that I have to take these values and I have to find a unique I need to find a k minus one degree polomial that passes through these >> it might not if B1 through BN is not a result of this procedure. It might not be that. >> Mhm. >> In which case I'm going to say it's an error. >> Sure. >> Okay. But decode is the reverse of encode. >> Mhm. >> Okay. Now given this I'm going to say what uh secret sharing is. And the variant of secret sharing I'm talking about is something called the packed secret sharing which means I can secret share more values than one. And um again I should uh credit this to Franklin and Young and I I'm hoping all my years are are

correct in here. >> This is impressive you're writing them with a two. >> Um okay. So what's secret sharing? I'm going to give the share procedure here. >> So um the share procedure it's going to take um I'm going to say l secrets. >> Mhm. >> And it still has this parameters uh k and n. It also has L U that's implicit is going to be encode of S1 through S L plus R1 through R T where you know L + T equals K.

>> Okay, >> that's it. This is share. I'm going to use this encode procedure. I'm where each of these RI's are random field elements. >> Sure. >> Okay, that's it. So this is secret sharing. Um I can give properties of this. I mean you know I have um I'm taking L values. I'm outputting N values. What these N values? As long as N is bigger like the field has to be bigger than uh some size and as long as N is also big. I can say that any t subset uh of these values will leak nothing about these shares. Okay. This just follows from uh you know polomials.

>> Yeah. Yeah. I mean that this follows from the fact for the fancier people I guess this follows from the fact that the um generator matrix for the polinomials is non zero at every point below the like specifically because we've defined it this way the the coefficients of this with respect to the AI through AK are all non zero. >> So these become uniform when you add the noise. >> Exactly. All right. >> Okay. >> Great. Um, and I can also talk about uh the reconstruct procedure. Um, I'm not going to write it here. Decode can be used for reconstruct. I just do decode and output the first L values.

>> Okay. >> Um, okay. Good. So now I'm going to define the the Lihero proof system. >> All right. >> I do think I'm going to run out of board space. I should have started. [laughter] >> That's okay. So um you know it's a sync so we got to [laughter] Sure. Um I'm going to define a new system of equations a little different. All of you are familiar with like you're familiar with R1 CS. It's going to look like a variant of R1 CS. Okay.

>> Okay. Uh my system of equations I'm going to imagine my witness to be a concatenation of three vectors. Say these are ml length vectors. Okay. Mhm. Meaning they are in f to the m. And my constraints are going to be two things. One is pointwise x * y= z. >> Mhm. >> And that there is uh a matrix a such that a * w= b. So a and b are public. >> Okay.

and um a * w= b. I want to say that any circuit you know over a finite field with addition and multiplication gates you can reduce it to this. All you will have to do is collect all the inputs and outputs of multiplication gates put it in x y and z. So imagine that you're evaluating the circuit pick all the multiplication gates you know when you encounter a multiplication gate add one to x add one to y and the output to z. Perfect. >> And then the rest of the constraints can all be wrapped inside a system of linear equations.

>> Yeah. Yeah. So essentially what we're going to get is like if we wanted to take a big thing is you could reduce them into like three block equations which is the ones over X the ones over Y equaling Z and then the last block being the standard linear constraint. >> Right? So this is over all X Y and Z. So the >> Yeah. Sorry. Sorry. I meant if we start with standard R1CS we can reduce it to that way by essentially these block equations. Yeah. Totally agree. Yep. uh but it's easier to think of it this way for for okay I'm going to uh this is what we want to prove like I want to prove I know a w such that these two uh these two constraints are satisfied >> perfect >> I'm going to start with a warm-up case >> okay in this warm-up case I'm going to

imagine that I have W1 through um WL >> okay >> L witnesses of this kind and I want to prove these constraints for each of these L instances So I want to prove the same set of constraints for each of these witnesses. >> So this is what is sometimes referred to as the batch setting. >> I have a batch of instances with the same system of constraints. >> Okay. >> Mhm. >> Um the description of Lihiro becomes remarkably simple for the batch setting and then I'm going to tell you how to do it for arbitrary uh constraints. Okay.

So I'm going to give the prover algorithm. Okay. W I is X I Y Y I Z Z I >> Okay, so it's a >> and each of them are m bit vectors. So I have to write XY 1 Y I1 Z I1 and all the way to oh X11 Z1 and then X1 M >> Y1 M >> Z1 M >> Mhm. >> And the last one is going to be XL >> one.

>> Yep. >> So forth. Okay, it's the just for the EL instance. I'm going to write it over here. Okay, now what I'm going to do is I am going to um take row by row and I'm going to pack secret share. Actually, let me call this PSS for short. Okay, >> sure. >> So, it's P SS with these parameters K and N. And I'm going to get a matrix. >> Sorry, dumb question. What is N here? So n is the the number of shares. >> It's the number of shares. Exactly.

>> Perfect. Okay. >> Okay. Um and I'm going to say that the iat row here I'm going to denote it by ui. >> Okay. >> Okay. Now the first step actually let me um describe this system. I forgot to mention I'm going to describe this not in the MPC in the head flavor. I'm actually going to discuss this as what people love these days as an IOP because it is >> okay like u an interactive interactive oracle proof is I can send you proof oracles that'll allow you to query a few spots and then we interact and we can send multiple oracles in this case I'm going to send only one oracle >> okay so I'm going to describe in this we all know how to compile these things

using Merkel trees so that part I'm going to skip uh for the moment >> so what's my proof oracle my proof oracle um that I am going to uh compute basically contains in um position I the column the ayat column over here okay >> mhm and if we want actually this whole matrix in you know let me call it capital U and this uh you know I know I'm abusing small U and capital U but we can imagine that the column is denoted by UI.

>> So wait, so sorry, just to be sure here, UI is the E >> um is the like all the shares for the E row of this matrix. >> Yes. >> So in this so just just to like make sure that the numbers are right in my head here. So this matrix is M rows, right? And L columns. This matrix is similarly M rows. >> Yeah. Um, actually three M rows, but >> Oh, sorry. Three M rows. Yeah. Yes. >> Three M rows and >> and then in this case N columns. Okay. Okay. Okay. Right. Yeah. Sorry.

Transposes versus not transposes and stuff. But yeah. Okay. >> Bear with me. I Yes. >> Right. So it's perfect. So, so what we're doing essentially is when we do one of these shares or when we do this uh this proof oracle, the proof oracle is we're going to take all of the shares or the the E share for each of these rows, right? And that will become proof oracle at position I. >> Yeah, typically people when they think of I I guess now people are okay with a column of things being in a proof oracle but >> in the history of like you know probabistically checkable proofs etc.

you would imagine that's a single field element or a single bit which is what they optimized for but here I'm really thinking of a column of values sitting in a position of this proof >> oracleh >> um okay so the the provers this as the proof oracle and now this is I'm going to give the interactive version of the hero system can make it non-interactive using the fiat shamir heristic you don't have to worry about the recent uh fiat shamir attacks because this is constant we are constant round then you're out of the business.

>> Okay. So I'm going to imagine that the verifier gives me a single random field element >> and then the prover is going to compute three aggregates of these rows scaled using this randomness and some uh >> some additional operations. Okay. So one we're going to call this and I'm going to call this the proximity test. But if you read the paper, we called it the code test. But I think everyone understands now proximity test better. Uh the second is um uh the multiplication test or quadratic test and the third is linear test.

>> Okay. So really these three are going to capture whether the prover uh has not cheated in this uh in this process in terms of have I not the first one checks whether the prover encoded things correctly >> or computed the secret shares correctly the second one makes sure that this constraint satisfies for everything and the third one checks if this is satisfied for everything >> okay perfect >> good so I'm going to go there >> over here yeah please >> and I'm going to try to write a little more succinctly so But uh [laughter] >> totally up to you if you want to erase or not.

>> Totally up to you if you want to erase that part or not. >> I'm going to erase this part. >> Okay, let's talk about what happens in each of these tests. Right. Okay. >> So, first the proximity test. Super simple. [laughter] Okay. The analysis isn't but the the the actual proof step is is pretty simple. I construct this vector 1 R r 2 R to the 3m and I give this times uh uh the U matrix. >> Mhm.

>> And really what this is is summation R to the I UI. >> Mhm. >> Okay. >> This is to be clear little UI. >> Little UI. Yeah. >> Yep. I will say that the the test fits in about a page and a half of uh of um math. So it's not so bad actually. Yeah, >> you know, there are some tests that do not fit in a page and a half. So, this is like uh >> that is true. >> Um, okay. The multiplication test also I'm going to tell you is actually pretty simple. >> Mhm.

>> Uh, it's going to be I'm not going to write it in the vector form. I'm going to say that it's going to be uh r to the i u 3 i - 2 u 3 i -1. I know the the indices look a little crazy but um bear with me for a second. Okay. >> Yep. Perfect. >> Okay. >> Uh >> what is this? Yeah. >> This is pointwise product of these two rows >> and then I'm going to subtract this row.

Now if you look here, let's look at the when I instantiate I equals 1, it's really uh 1 2 and 3. And it's the encoding of the x, the y, the z. Okay. So it's u1 dotproduct u2 um minus the the third row. >> Mhm. Okay. >> As you will see, there are these properties of this encoding that will make sure that when I reconstruct this value, it will be all zeros if x * y is z for all of these elements. Okay? And then I'm just taking a combination of all the the multiplication gates across all these things. So I'm grouping it three at a time. I'm multiplying the

first the X and Y and then I'm subtracting out the Z >> not for the values but for the >> encoding or the secret shares. >> Okay. >> Okay. This is the multiplication test. >> Makes sense. >> And uh the linear test is a little more complicated but not that much more. And I'm going to say that it's going to be I = 1 2 3 M of what I'm going to say R hat I >> of UI. >> Yep. >> What is R hat? So R hat is going to be this vector 1 R R 2 times the A matrix.

>> Yep. >> Okay. >> Uh >> the A matrix is the constraint matrix. >> So this but this should be equal to R hat. Oh, so we have >> I've not told you I've not told you what the verifier is doing, but we will come to that in a minute. >> Right. So, I've just defined the R hat vector to be to be this. >> Um, really what it is trying to do is it's computing this * A * each of these columns. >> And if you see this, I'm going to multiply this vector on both the left and right hand side of this equation.

I'm going to say that R A W equals RB. >> Exactly. >> Okay, >> this is it. the the in this round the prover let's call this uh I'm going to call this VP I'm going to call this uh V uh L and I'm going to call this VM okay and the prover is just going to give VP V L VM cool >> and actually in the IOP setting that's it like no more interaction this is the this is the proof now I have to tell you uh what the verifier is going to And I want to say this is this is the description of the uh whole proof.

>> Yep. >> Okay. Like I'm going to construct this matrix and then I'm going to um give that as the proof oracle and then compute these tests. >> Mhm. Mhm. >> Okay. >> Makes sense. >> Now what is the verifier going to do? And I'm using a lot of board space. [laughter] >> Okay. Um the verifier um is going to first um check some properties of VP, V L and VN. >> Okay. So it's going to check if VP reconstructs correctly.

Okay. >> Mhm. And this really means that decode of K, you know, doesn't give an error. >> Mhm. >> Okay. That's it. >> Mhm. and um nothing really much is happening. If all the encodings were done correctly, then a random linear combination of this should also be uh um should satisfy that >> indeed. >> Okay, we >> in other words, yeah, it's it's all linear, right? So, we're >> you're going to reconstruct, but there's a a slight caveat in the reconstruction.

The parameter is going to be 2k instead of >> I think 2k minus one, but uh >> you know, bear with me. So I have to do reconstruct and then check if uh all entries are zero. >> Okay. >> Mhm. Mhm. Mhm. Mhm. >> And really what this is saying is that you know this you know if x * y equals z this encodes zero a random linear combination of that should also be zero. Okay, V L I'm going to reconstruct with parameter K and I'm going to check if all entries are are um this transpose B. So let me just say 1 R r 2

uh inner product with B. Okay. Or I should say transpose B. But that's okay. That's all I'm checking. And then so this is basic checks. There's one more check I have to do. I don't know if the prover gave this correctly. I is it related? Is it actually done with the proof oracle? I need to check. So I'm going to query the oracle at T positions. I1 >> through it. >> Okay. >> Mhm. Mhm. Mhm. And I am going to recomputee the VP VM VL exactly at those positions.

I'm going to recomputee VP of you know J V M of J. >> Mhm. >> And V L of J. >> Mhm. >> Now if you see the way this is done actually they are all row operations which means I can compute these columnwise. Mhm. >> So I can given the values in the columns I can recomputee what these values should be on those uh indices. So just recomputee them and check against this VP. This is really in in at least in many places it's a cut and choose argument. I don't know if you did it correctly. I sample a few places. I recompute it and I check if you did it correctly.

>> Mhm. Mhm. >> Okay. >> And this is it. >> Yep. >> Okay. This is the entire proof system. >> Yeah. Yeah. Now I want to point out this is actually it is sublinear meaning the proof is shorter than the size and it is succinct verification. >> Sure. >> Okay. Which is again there is a conception that hey liu is not succinct in this setting it is succinct. If I have a batch system of equations it is succinct. Mhm. >> Um, okay. Now, I'm going to maybe use uh maybe just a couple of sentences on uh why this is uh sound or like I mean just following why this is uh why this is correct.

>> Okay. Now, so for that I need to argue completeness, soundness and zero knowledge. Now zero knowledge I need to do a little bit more which I kind of pushed it under under the rug but I will u uh I will fix it when we come to do uh zero knowledge. Just one small change I have to do for zero knowledge. Okay. Completeness. I need to show that if I used honestly did everything honestly as the prover all of these will pass. >> Yes. >> Okay. Now we can see that um VP reconstructs correctly this will work. If I use codes I do the random linear combination there's not going to be a challenge.

>> Y >> now all entries are zero. What I'm going to tell you is that reconstruct distributes over multiplication. And one of the things I want to tell you is that this is where we really use that these are polomials and read Solomon codes they have this property of multiplicity because they are polomials. I multiply two polomials with you know P of 1 and P of two being this. >> Then the product polomial will be the secrets or the values at 1 2 3 will be the product of those values. So I am using I'm going to use the fact that reconstruct of this distributes over here. So now if it distributes over here reconstruct of this time this minus this if they were correctly computed as multiplication they will have to be all

zero. >> Mhm. Mhm. Mhm. Mhm. >> Okay. And I mean we all know all these codes that we use are linear meaning that if I add two things and reconstruct I'm going to get the sum of them. But multiplication is something that read solment codes satisfy. >> That's right. >> Not uh all codes do. >> Correct. The linear constraint also actually just follows from the linearity of reconstruct because um when I apply I'm applying r hat I on ui when I say reconstruct it basically becomes like I'm going to say rh hat of u um rhpose of u when I do reconstruct of this I just get you know r hat transpose of

this matrix which let's call double value. >> Mhm. >> And this becomes actually r the this vector let me just use r transpose a times my uh witness vector >> and we know that ranspose a if I use here r like the vector rpose a w should be rpose b >> okay so um >> so completeness is direct yes >> from at least for vl >> from these things >> okay soundness uh I'm going to give you a high level of the soundness >> first. Uh this is what's called a proximity test.

>> Um >> it says that instead of checking now the prover can prover is supposed to compute the secret shares but it doesn't have to. It can do whatever it wants. >> Now what I'm going to check is that hey like >> I'm going to check a random linear combination of this if it's you know a valid encoding or a valid secret sharing. Proximity test says that if the prover succeeds in convincing the verifier in both that the what was revealed is a valid secret sharing and the random columns I sampled were consistent.

>> Yep. Then with high probability and here there are many parameters but the errors in each of these like you know where the prover did not really put the right value >> is restricted to a few columns. >> Yes. >> Okay. And for people from coding theory if you can if the number of errors this is what we use for our parameters is less than the distance over two of the code then it means that each row can be uniquely decoded. >> Yep. Okay, this is important because to talk about multiplication and the linear I need to say what they encode.

>> Yes. >> And the prover can make errors and can like I mean then I need a handle on what are we talking about in the multiplication and linear test. So the proximity test says that only a few columns have the error which means now I can define unique values by saying decode each of these rows and you will get this matrix and my multiplication test and linear test applies on these values. Mhm. >> Okay. So the proximity test tells me I it's uniquely bound to some values and then I can argue that hey like if you give the incorrect answer I'm going to catch you with just by looking randomly sampling these columns I will catch you on the multiplication and the linear test. Now

>> just a connection to more recent work like were stir as well as like Ben Saison's work on proximity tests >> they have tried to push this beyond the unique decoding bound to the you know some uh some >> scaling of the yeah the Johnson's bound Johnson's bounds and capacity bound >> now >> we've at least in our implementation not used any of these conjectures but we are actually working I mean when they show uh you know when they can isolate it prove this proximity test we'll be able to uh inherit those those features >> I want to say the way it applies in the lio system is a little different you also need to make sure that the multiplication test and the linear test

also holds because when you go beyond the unique decoding bound as you can imagine there are multiple values that can be satisfied >> so then you need to make sure that these also follow and now we have actually we have an analysis that even if you go up to the Johnson's bound all of these will work and we have the soundness parameters but I want to say there are still conjectures today. >> Yep. >> Um but I hear that you know this is going to change pretty soon >> hopefully. You know we'll see. [laughter] >> Okay great so this is a complete description what the verifier does what the prover does for the batch setting. >> Sure.

>> Okay. Uh I'm going to say one more uh thing and that'll be the end of the description of Lihiro. This is for the batch setting. What do I do when it is um not the batch setting? Okay. Um what is going to really change if you think about it is I have taken some advantage over here. So both the multiplication and the linear where I had to check values within a column. >> Yes, >> I strategically used it because all these constraints are within like they were l separate instances and I was able to check them.

>> Okay, >> but now for a general circuit that's a liberty I cannot take. At least it's not a liberty I can take for both multiplication and linear. >> Sure, >> I can take it. I can assume that my multiplication is still like highly like you know isol like uh aligned this way but the linear test can you know refer to values across this matrix now. Okay. So everything here I said works exactly for uh even a circuit that isn't the batch setting except the linear test. So I need to fix the linear test.

>> Interesting. Okay. Okay. So, I'm going to show how to fix the linear test. >> Okay. >> So, I'm going to erase that side as well. >> Yeah, I'll try there. >> Yeah. Okay. So, um actually it is worth u just redrawing this matrix because it'll be helpful. Now, I'm going to assume still they are ml length vectors. I think it's not going to affect too much. Um, I'm going to have X1 through XL. Um, and then I'm going to have Y1 through Y L, Z1 through Z L and so forth. And then at the end

I'll have in the last row, you know, Z - L + 1 through Z M, right? I'm just going to take all the multiplication this X, Y, and Z. I'm just writing it in order over here. like pick the first value, put it here, the second value, so forth, and then after I've exhausted the row, I go to the next three. >> Okay. I see. I see. I see. I see. I see. Got it. So, you're just like you're aliasing on the on the rows here. So, it's that you get all the way to Sure. Okay. >> That's nice. I like that aliasing over the [laughter] >> Yeah, that's the that's the old school signal engineering. I know, >> you know. Yeah. Yeah. Yeah.

>> Good. So, um this is what I'm going to do. And you know you're going to do similar as before which is like you know pack secret share each row and everything here will work except the linear test. >> Mhm. >> Okay. >> Mhm. Mhm. >> Now recall what do we want in the linear test is really to compute this value. >> Mhm. >> Okay. If I look at this a little more carefully, I think of this as the inner product of this vector rpose a and w. Okay. Now w is really these rows. Okay, all of these.

>> Now um I'm going to just uh write it here. What is the inner product I want to compute? And I'm going to use the rh hat notation for for this. I'm going to use rh hat for this. I'm going to say this is r hat 1. >> This is rh hat l and then I come here all the way. This is um rhus l + 1 all the way through rh. >> Mhm. >> Right. Okay. Now if you recall what happened I told in the multiplication test it distributes over multiplication.

If I had an encoding of two values I if I multiply them pointwise I get the product of them. >> Now if you imagine here what do I want? I want to multiply these all of these values together and then I want to sum it all up. >> Okay that's what I want. I I've written it in a way that this is the inner product like I multiply these you know this is going to be r hat l + one here. >> Yep. >> Right. And I'm going to multiply them u and do this. >> Okay.

>> Okay. Now I'm going to ask the prover to encode all these r hat values. Okay. This is not in the oracle or anything like when I have to compute the linear test >> I'm going to ask the prover to arrange these values just like I had arranged the witness and I'm going to ask the prover to encode these values and I used ui for you know the iat row of the witness I'm going to use v1 or vi for >> for that okay uh this is I should say actually >> it's going to be like m over l >> no this is actually three >> or sorry yeah 3 m.

>> No, this is M. But this is 3 M. >> Yeah. >> Okay. There are Yeah. And this is going to be uh M. Okay. It's M over three. That's uh No, this is also going >> No, this is this is M, right? I think >> is it M over L? >> No, not M over L or is it M over L? >> Right. Because we have M elements in each row's L size. So, >> uh there's three M over L. >> It might be 3 M over L. Yeah, >> yes, there are three M values. Okay, good. Great. Anyways, corresponding to every row here, I have a V. Okay. So, corresponding to every UI, I have a VI.

>> Mhm. >> Now, this VI can be computed, recall, both by the prover and the verifier because it depends only on R which the verifier chose and A. >> Yep. >> Okay. So, now this is what I want to claim. Just look at the um computation UI product VI. >> Mhm. >> Okay. It's basically a pointwise product of ui and u1 v1 u2 v2 and I'm summing it up. >> Now remember that reconstruct distributes over multiplication. It's really computing this times this and adding it up.

>> Now this is still not the inner product but we are almost there. I have partial sums. >> Yeah. As you sum the rest, right? >> And then you sum the rest. >> Exactly. Cool. >> Okay. >> Okay. >> So uh here two points to note. um the prover will compute this and give this uh as part of the linear test. Mhm. >> Now the what the U verifier is going to check is not uh R transpose it's not going to be all B right it's going to sum the values >> that it reconstructs and checks if it's equal to Rpose B because Rpose B is the inner product and I got partial sums I add it up and I check if it's RRPOSE B.

>> Mhm. Mhm. >> Okay. So um and note here that the verifier needs to compute the vi to do the query and recomputing. >> That's right. >> Okay. It because uh if it needs to know what happens in a particular column I need to know the contents of vi >> to repeat the computation in that column and check against what I give in the linear test. >> This is important because this is where we lose succinctness. >> Sure. I have to recomputee and because you know this is the size of the entire computation. R hat is the size of the entire computation with the with the linear linear constraints.

>> I see. >> So this is why for an arbitrary circuit it's not succinct. At least we're going to fix that. I'm going to tell you how to do it. But uh it's uh uh as I have described it is not uh succinct. >> Good. I'm going to say one more thing and then we can go to other features of Lihero. um completeness soundness will work. I didn't talk about zero knowledge in the batch setting. I forgot that. But let me talk about zero knowledge here. Okay. Okay. For zero knowledge, I just need to do um I need to add three more rows to what is being encoded in the um uh as part of the oracle.

>> Okay. >> These are called masking rows. Sure. >> Okay. These are to mask what we want to make sure that what I reveal in these values don't reveal anything about my witness. And if you see here the first one it's a random linear combination of the rows but I know R and I know a specific random linear combination of the actual wire values which is bad. >> Okay. If it's zero knowledge it needs to hide it. >> Yes. >> So what I can do is I can just add three more rows to blind each of these things. Okay. And I'll ask the prover to add it to these computations. It'll still keep the invariance that the verifier is going to check.

>> So what's the invariant for the proximity test? It should just be a valid code word. So I'm just going to add a use zero which is which encodes a completely random secrets. >> Okay? So it'll mask everything out. You don't see anything. >> For a multiplication test, I'm going to add like a row which I'll call um N. >> Okay? >> Which is just an encoding of all zeros. Okay, >> wouldn't that be a zero? >> No, because there is randomness. If you recall in the secret sharing, there is randomness and also the encoding needs the twice parameter. It's 2K, not K. So, because I need to mask this in the >> the degree 2K polom or something. Yeah, >> this one is interesting like I can't

just mask it because the verifier needs to check that the sum is equal to our transpose. >> But there's a very simple trick. I'm going to choose secrets that add up to zero >> which means that the sum will remain invariant but the individual values uh >> uh will change like you won't know any of it but when I sum the values I'll still get what I want. >> Okay. Yeah. >> Okay. Makes sense. >> Now I want to point out here that um you have to ask me the question if it's zero knowledge give me a simulator. >> Yes. There you go. All right. >> Good. So >> where's the simulator? Give me the simulator. So the simulator really needs to see it needs to let me tell the easy part.

>> Okay, >> how do I um simulate the columns that the verifier is going to query. The secret sharing has this property that they are all uniformly at random. So this verifier is going to query the oracle. Now the simulator has the power to decide what is inside after it sees the queries. >> Okay, so I can just put it uniformly at at random. >> But that's only if you don't have enough queries to reconstruct, It's it's only random up until the degree. >> Good. But here is the caveat is that okay I can't really do that because I have to give you these values VP VM VL before the queries are determined. The verifier sees these things before doing it.

>> Sure. >> So what I'm going to do first I'm going to generate these things. Okay. For VP I'm just going to give a uniformly random code word. >> Okay. For VM, I'm going to give you um a uniformly random code word that satisfies that they are all zero. And for the linear test, I'm going to give a uniformly random code word that encodes this the sum of the values is RRpose B. >> Okay. >> Okay. This is all polinomial time. I I just have to do secret sharing of like ranspose B and then encode it like >> and then when I open the columns I can actually manipulate the the blinding rows so that they sum up to the value I want. That's the only thing. Everything

else can be completely random like the encoding of all these things can be completely random. But these masks I'll make sure that when the verifier recomputes on those columns they will match what I gave for VPV MVL. >> Sure. >> This is polinomial time. >> Mhm. >> Okay. And this is why it's uh uh it's zero knowledge. >> I see. And I want to say again I probably can't go very deep into it but the reason other systems like starks or um uh some check GKR the problem getting zero knowledge all of them can be made zero knowledge it's the multiplication part it's not easy to make it the masking there is way more complicated okay here is where because we use we

abstract out the multiplication and use multiplicative codes that becomes super simple >> I see I see >> so It's probably uh it it makes it simple. That's what I should tell you. >> Okay. So that's Liro. >> Awesome. Very very cool. >> So just bringing back the um the part here of succinct verification. Um I'm going to give like a very short version of even for arbitrary circuit lio can be made uh succinct.

>> Mhm. But before that I want to make a point which I'm sure most people know but I would like to stress this that you cannot get succinct verification. Okay like you can get succinct verification only in a specific case. Meaning that if I don't tell you what's the circuit ahead of time the verifier needs to spend time looking at the circuit one way or the other. >> Sure. >> Okay. If you think see in grot 16 I really have to do the the setup before that. Mhm. >> But even in others, the verifier needs to spend time at least once looking at the entire program.

>> Where you can get succinct verification is where you imagine that the same circuit is used many many times. >> Mhm. >> Like in rollups like it's the same kind of circuit that you do many many times in in many situations also like I'm trying to prove the same statement many times. In these cases, you can give a succinct representation of the constraints to the verifier so that not the first one but every subsequent verification can be done succinctly. >> Sure. >> And uh these type of ZK snarks are actually called pre-processing or holographic.

>> So the question is uh I mean holographic proofs were introduced a long time. >> Sure. Sure. No, it's a cool name. It's just it's weird because like you know in physics holography means something very specific. So, but I mean I think most people refer to it as pre-processing because you do some pre-processing on the constraints to to do it. >> Sure. Okay. Makes sense. >> So, let's make Liro a pre-processing snark. >> And I'm going to do this um computer sciency thing to say that this problem has already been solved and like I'm just going to point to point to there.

>> Okay. [laughter] So if just recalling here the reason this is not succinct is because the verifier needs to recomputee the R hat polom the R hat values and the encoding. >> But what if someone actually gave me what I needed and what I needed was not really the RH hat values. >> It was just those columns in the VI shares >> that would help me recomputee the values to check that the linear test was done correctly. So recall that the prover gives me something >> and the verifier queries the oracle and then recomputes it on those values that this linear test agrees on those indices.

>> Sure. >> Okay. Now I need the values of these vis >> on those columns. The verifier needs only those. >> Sure. >> It's just that it doesn't know how to do it otherwise. So it has to start from here and code it and do it. But what if the prover gave this? >> Sure. Okay. Now, of course, you don't trust the prover. So, you attach a second proof that this was done correctly. >> Okay. So, now I'm going to point to you can use any snark because this doesn't have to be zero knowledge.

>> Sure. Sure. Sure. Yeah. Yeah. >> These r hat these values depend only on a and r and r is public and a is known ahead of time. Use any pre-processing snark for this. >> Got it. Okay. So make the prover reveal again this might not be the most efficient way but you know given all the progress in sn two things I want to tell you that this doesn't have to be even done on the device that you generate the proof a third party can do this for you >> mh >> okay like this proof can be generated by uh a third party given and given the R for the thing you can do it >> and that's it now the verification is succinct and whatever is the pre-processing needed for that snark is

the key that the verifier needs and using that you can verify it succinctly. >> So interesting that's succinct verification. We are of course doing some optimizations in this space to make this much more uh efficient but that makes the Lihero verifier succinct. But what I want to talk maybe in the last few minutes is memory efficiency. >> Okay. >> So we talked a lot about ZK MPC Lihiro. So I want to sort of maybe set the stage a little bit. If you're caring about ZK, you're caring about to some extent client side proving. Okay? Cuz you're caring about privacy and you're caring about it can be privacy for individuals, privacy for organizations.

>> Sure. >> And you know, this is about regulatory compliance on chain etc. which is something that Lihiu is is trying to build infrastructure. >> Now when it comes to individuals, it's their devices. You have to generate these proofs where the sensitive information rests. Yep. If you don't care about ZK, you don't need to do it on device. >> Okay. So, if you're caring about ZK, it's about getting it on a portable device, which means that you want to be memory efficient. >> Mhm. >> Okay. >> Um, an iPhone Safari browser, a Safari browser on an iPhone has at most 1 GB of RAM.

>> Okay. So, your proof system should be able to run in uh with that much memory. >> Sure. The second point I also want to make is when someone comes up with these tools for ZK and privacy. The second question you're going to ask is what size of computation you can do. If it is like 1 to 2 million I want to say today Groth 16 is super performant in that regime. >> Okay. >> Okay. So really like if you're going to compete in that space sure but I think the real applications lies in like much larger 50 million to 100 million. you want to do livveness checks, video checks and uh other computations when you want to think of KYC or AML.

>> So you want your ZK to scale to like I mean I'm saying even if you want to do benchmarks etc you're thinking about large computations >> and also you want to build systems that can scale to that size right like some 50 to 100 or maybe even more than that uh we have an ambitious goal of being able to prove an Ethereum block on a browser so that I think could run to billions of gates. >> Sure. I believe that. >> Okay. So, memory efficiency right now as you can see in Lihiro like we want to ask how much space does the or how much memory the prover needs. Okay. Now, first I need to build this oracle and if you recall the compilation of an IOP to a snark, I need to build a Merkel tree to represent the oracle.

>> Now, it's nice that you know these these things are done rowby row. >> Mhm. Which means that like after I have done the first set of you know uh values in these multiplication gates um I can already hash them and just maintain a running hash for the Merkel tree. The leaves of the Merkel tree contains the hash of these columns. I can have a running hash an aggregate hash that I do. >> Mhm. >> Uh this is also called like the Merkel Damgard process of computing the the hash uh iterative hash of of a string.

Um, and the point is that after this is done, I can garbage collect it. I don't need these rows anymore. So when I'm preparing this oracle, I can do it in a memory efficient way as long as I can stream these values. >> Sure. >> Okay. Even when I have to reveal these values for the verifier for some queries and give the Merkel decommitment, I can do this as well. Okay. Like I can recomputee all these values and just pick out what are the queries that the the verifier wants. >> Mhm. Mhm. Mhm. Now the prover now we have to talk about the prover computing these tests.

>> Yes. >> Okay. Now I want to say that the proximity test and the multiplication test can be done in a memory efficient way. You can see this because after I have done this computation for every set of three rows I don't need that anymore. >> The proximity test is even more easier as >> you're aggregating the the rows in this case as you go. Right. >> The linear test is the challenging part. >> Okay. >> Okay. or at least um we don't know if that can be done in a memory efficient way but I'm just going to punt it by saying that for getting memory efficiency of the linear test the prover needs these RH hat values okay the question is can these RH hat values be done in a streaming way and I can I garbage collect these R hat values and

we're going to uh assume that the constraints are local >> mhm >> right if I think of this a matrix if they're like you know block matrices like after the first block I can I don't need [snorts] to worry about the values over there. >> And also just a small optimization here is like when I compute these R hat values I don't need to compute a and r and do this matrix multiplication in fact you can comp compute this you know uh in place implicit like I can directly compute these r hat values for these constraints.

>> Mhm. >> So just these two observations will tell you that you can do this in a memory efficient way. >> Sure. That being said, I don't want to discount the engineering effort that takes to make this for a compiler like a ZKVM that we have done like the engineer who coded this, you know, uh for a web assembly like you know it takes uh a lot of more compiler techniques to make sure that this doesn't go out of uh uh memory but theoretically speaking um it is uh memory efficient. >> Very cool. Yeah.

Um the last point I want to make is that um here is the core of memory efficiency. I cannot keep all these values in memory as you have seen. That's why I say I I keep saying about garbage collecting these rows. So when you see a memory efficient and this is just my conjecture and I probably can be totally wrong. Um at least for hashbased systems people are going to use like a square root by square root matrix of this form to do it. Even Starks or others I think this is they are going to I mean Starks are I think much more leaner when it comes to these matrices.

>> Yeah. >> To get memory efficiency they are going to have to compromise and make it more lio style in doing this. I agree that >> the second thing I'm going to tell you which you have to pay attention to is the number of passes I have to take on the witness. >> Yes. >> Okay. As everyone knows, the hardest or the the one that takes the most time in ZK is not coding, is not NT, is not hashing, is not any of those. It's witness generation. We in this protocol it when you compile it down, we have to run through the witness three times. So when you run it on the browser from our platform, >> we are running through the witness three times.

>> Mhm. So you can also interpret it. If I did it on a server, I could get 3x speed up just like that by keeping it in in memory. But when you see these new techniques that are going to try to do ZK and memory efficiency, you're going to they're going to run into this. How many times do I have to pass through the witness to >> uh to to get it? at uh very interesting space and like I think there's going to be a lot of uh exciting work and it since we reveal unveiled our platform in Denver a lot of people are working on this and like I think amazing works are going to come out of it. No, no. I mean, it's cool stuff. It's crazy that like, you know, this this stuff was in many ways kind of a bit of a fever dream even

up until like I'd say six years ago, seven years ago. You know, it was it was a thing that was very cool and it was a thing you could do and it was a bold thing in theory and a little bit of practice. I mean, some some people will say much more practice than I think it was actually. But now, you know, I mean, like, you know, you guys are doing, right? You can run this stuff in a browser, you can run it on a phone, you can prove real things. I mean, these aren't these aren't toys anymore. They're quite quite useful, quite good. And it's it's yeah it's funny to see you know something that like some people would have called very esoteric math honestly even 5 years ago is now now being quite quite useful very real available to everybody is I don't know

I'm curious to see where it goes. >> Yeah and uh I'm curious to see what's going to come of Liharito which is uh [laughter] very interesting in trying to optimize the proof length of of Lihiro. >> Yeah, we'll see. We'll see. No, no promises there about anything but you know it's uh it's yeah very much inspired by by this like very very cool piece of work. I remember, you know, to be for for the whole bit is uh I remember reading Mihara and being like, "Wow, this is this is so simple. It's so nice." You know, it's a very nice vertical. So that's why we ended up uh doing a story on it. But no, thank you so much for this. This is very fun. It's in many ways a different perspective than the one that I certainly I take to um a lot of these free systems. But it's

uh no, it's cool seeing where it comes from. The MPC and the head paradigm and uh the whole mechanics of it. So um do you have anything else? Any thoughts? last notions constructions >> um more zk more client side proving [laughter] >> wow thank you all for uh listening thank you mu for joining us and >> thank you for having me >> thanks >> [music]