The One Question bounty closes Thursday 10 December.

Join in
We Them Media logo We Them Media Support us

Scroll Technical Workshop - Wisdom Ogwu

The picture loads from YouTube. The player loads only when you press Play. Turn on captions in the player if you need them.

Wisdom, who says they are a senior ZK engineer at Scroll, teaches secret sharing with polynomials. Using seven housemates and a shared cash box that needs four approvals, they show how lines and curves fixed by a set number of points can split a secret into shares. They suggest uses such as splitting a private key.

Not by We Them Media Channel: Web3Bridge. Published Thursday 3 October 2024.

Titles are the owner’s. It plays from their channel.

Transcript

This transcript may contain errors. This video belongs to Web3Bridge. Letters mark each change of speaker.

These are the speakers’ own words. We have not checked their claims.

0:06 A: Wisdom. All right. Hey guys, my name is Wisdom. I am a senior ZK engineer at Scroll working on the next generation prover for Scroll. Today I'm going to be talking about secret sharing and we're going to use this as a way to explore the power of polynomials. It's going to be very simple, interactive, not too complex, so don't worry about it. So we'll start with the problem and then we'll try and solve this problem. And through that, we're going to learn a lot of things about polynomials and how we can do some really interesting stuff with them. So just, you know, if you guys are tired, just wake up a bit and then, um, just pay some attention. Okay, cool. I remember you guys from yesterday. So we have 7 individuals, 7, 7 guys living in the same house. Then we have a single deposit box. So every morning, each of them, they save, let's say, ₦1,000 every morning. Okay, so this is like a community pool of cash. Then the question is, how should they spend this money? How would they coordinate on spending this money? They have a requirement which is basically that in order to withdraw from this box, you need to input a code. So once you put in the code, the box will open, you can pull out money and you can spend it on whatever. Now, the desired situation is that 4 of them have to agree in order to spend from that box. Okay, so one person cannot just go and say, oh, let me go and pull out all the money, I want to go and buy pizza or something. It has to be something that the group as a whole has agreed that, okay, this is worth spending money on. So at least 4 people must agree before a withdrawal can occur. Does the problem make sense? So the question is, how can this be done? Does anyone have any idea on how this could potentially be done? Set it down. Okay. So something similar to Morotis again. Exactly. Yeah. MPC, something similar to MPC. So you guys have said some of the applications of what I'm about to talk about. Which is like, this is more like a foundational element and then it was built on top of that. So someone could assume that this could be a potential solution, right? You give everybody the code to the withdrawal box, but obviously this doesn't work, right? Because anybody can just go to the box and put in the code and then carry everything. Exactly. So this does not, this doesn't work. So the problem with this is that it doesn't stop the minority from being able to withdraw from the box. But obviously if 4 people go there, 1 person has the code, right? So they can open it. So the happy part is good, but the minority part is not good. So what's another solution? We could break up the code into different parts. Yeah. So let's say the code was 1, 2, 3, 4, 5, 6, 7, 8. We could give the first person 1, 3. Then 2, 7, 5, 6, 4, 8, 1, 5, 2, 6, 3, 7. So a single person doesn't have enough to open the box. But then let's assume that 1, 2, 3, and 4 come together. Now 1 is there, 2 is there, 3 is there, 4 is there, 5, 6, 7, 8, right? So they have enough to reconstruct the secret and open up the box. Does this make sense? Okay, cool. Now we can also see 4, 5, 6, 7, 8. They have 1, 2, 3, 4, 5, 6, 7, and 8, so they can still open it. This makes sense. But now what if we had 2, 3, 4, and 5 coming together? We'll notice a problem. We have 1, we have 2, But we have no 3. Okay, we have 4, 5, 6, 7, and 8. So this solution kind of works, but it's not like complete. But there's even a bigger problem here. I'm sure that you can come up with an algorithm that can efficiently like send or set the shares so that every combination of 4 will always have something. But one thing you can notice is what if 1, 2, 3 came together? They're not 4, right? They are 3. If they came together, they will start to see like the partial secret. So 1, 2, 3, there's no 4. 5, 6, 7, there's no 8. So all that they're missing is just 2 slots. Now they can brute force those 2 values in order to get the code that will actually open it. So the work is easier when 3 people come together. But what we want is we don't want a situation whereby if you're not complete, you should not learn anything about the secrets, basically. So if 1 person is there and if 3 people are there, the people that are- the ones that have 3 should not have any advantage over the person that has 1 or over the person that has none. Okay, so you should not- it should not be easy to brute force the more people are together. So some of them would not have- when in this example, when we combine 2, 3, 4, 5, they couldn't get the secret. So that's the first problem. Then the second problem is that it leaks information about the secret, basically making it easy to attack by a strong enough minority. Does this make sense so far? Cool. So now let's look at Points and curves. So this is, this is where we're going to find the solution essentially. So I don't know if you guys have done graphs. I think everybody here should have done graphs at least, but even though, um, we'll go over it. So this is the x-axis, this is the y-axis. Now this is a point, 0, 3. So 0 represents x, that's here, and 3 represents y, that's here. Okay, so that's how we specify this point here. So 0, 3. Then the question is, how many straight lines can we pass through this point? Is it just 1? Is it just 2? So, um, yes, we can pass 1 straight line, right? But then we can also pass another straight line. The point didn't change, right? Still same point. 2 straight lines are passing them. But then we can pass the 3rd one. We can pass as many as we want, right? So through that straight line, we can pass an infinite number of- through that single point, we can pass an infinite number of straight lines. Okay? So that means that a single point is not enough to specify a particular straight line, right? This is not enough information for us to pick a particular straight line. Now let us add another point. Okay? So we have and we have . How many straight lines can pass through this now? One. Yes, it must pass through both points. Just one? So that's a straight line. Can we pass another straight line through those 2 points? No, exactly. Why? Because of- in order to These 2 points are fixed. If you move this line slightly left or right, it's going to unfix the other points, right? So because we have 2 points and the line is passing through both of them, it's just impossible to move the line. So what does this tell us? It tells us that 2 points are enough to uniquely specify a straight line. So you can think of a straight line as having a name, right? And you can call that straight line by its name. So the way to call a straight line by its name is by calling 2 points that that straight line passes through. So every time anybody hears those 2 points, they know that, oh, it's this particular straight line that we're talking about, as opposed to before where we had just one point and there are a lot of straight lines that share that maybe first name or share that surname or something. So everything makes sense. Now on this same straight line, this is the exact same straight line we had before. We have a series of points on it, an infinite number of points on it. The cool thing is that we can pick any other 2 and it will still specify this particular straight line. So a unique straight line has multiple names essentially, right? But then only it shares that name, those names. Does that make sense? So now I'm picking 2 more points from it, and from the same straight line. Now, if I start with these 2 points, I can draw a straight line through it. This straight line is the same straight line as the other one we got from 0, 3 and 2, 5. Okay, so we have been able to get the same straight line from 2 different points. So basically, the straight line has 2 different names that we could have- that we used to call it. And I'm showing you now that 0, 3 and 2, 5 still stays on that same straight line, just to prove that it is exactly the same straight line. So what have we learned? Every straight line is unique. Okay, this unique is- they don't share. 2 straight lines are not the same. And then, um, to identify a straight line, we need at least 2 points. Okay, so given those 2 points, we can uniquely identify that straight line. And, um, given any 2 points on that line, we can draw back that same straight line. Does this make sense? Cool. So let's use this to share a secret. Like, let's try and apply this to share a secret. So let's reduce the problem a bit. Now assume we have 4 individuals in the house. We still have 1 deposit box and the withdrawal code is 2356, but then we want 2 individuals in the house to agree before you can spend. Okay, does the problem make sense? Cool. So how do we do this using the straight line? Does anyone have any idea? Like, we have all the ingredients in there to construct a way to share it. Do you have one? Okay, okay, no problem. Uh-huh. Yeah, exactly. So you are on the right track. So let's see how to do this. So we want to give 4 shares, right, to 4 individuals. And if 2 individuals come with their shares, we should be able to get back this 2356. That is the goal. So how do we do this? The first step is to encode the secret, which is the code, as a point on the graph. So our code is 2356. We encode it this way. So we put a point 0, 2356. So this is our secret. Now we have the requirement that 2 persons must be present before we can get it And what line- is a line basically that requires 2 points in order to construct it. So a line fits this problem really well. So what we do is that we just draw a random line through that point, any line essentially, just draw a random line through that point. So we can imagine that this is the random line that I drew through the point. Now we want to generate 4 shares. So from this line, we're going to pick 4 other points. that rests on this line because any 2 will be able to reconstruct this line. So the only requirement is that you don't give the secret, right? It doesn't make sense to give someone like 0, 2356 because you are basically giving the code. So you need to give everything other than that particular point. Exactly. So we can imagine that the first person gets that, second person gets this, next person gets this, and next person gets this. Except for the secret. So the secret is still hidden. So these are the shares. First person gets the minus 3,000, blah blah blah, then that's the fourth person's done. So now a single person here cannot reconstruct the line, right, on their own because of- they just have a point, and we showed that there are a lot of straight lines that can pass through that point. So there's no way that they'll be able to get that exact straight line that has that secret there. But then if any 2 come together, they have 2 points in order to construct one straight line. And then you can now check, okay, that line, what is this value at 0? So when you check the value at 0, you get the secret. So that is how any 2 persons can come together to basically get the secret to withdraw. Any questions so far? Cool. That means everybody's understanding. Okay. So to recover the secret, we need to make sure that 2 shares are present. Then we draw the exact same straight line through those 2 points, and then we evaluate the straight line at 0, and that basically gives us the secret. So does that make sense? So we know how to share a secret such that any 2 persons can recover it, but then What if we wanted 3 persons to recover it, not just 2, right? You know, in our original example, we needed 4, not 2, but let's build 3 and then I will generalize it so that we can see how to do it for a larger domain. So we use a straight line. A straight line had this unique property that it can be uniquely defined with 2 points. So the next thing we want is, A curve that has a unique property that it can be uniquely defined with 3 points. That's the idea. That curve is basically a quadratic curve. Okay, so if you see this curve, I'm only using 2 points right now, here and here. I want to show you that 2 points are not enough to uniquely describe a quadratic curve. 2 points were enough to describe a straight line, but they are not enough to describe a quadratic curve. And the way I'll show that is by showing another quadratic curve that passes through those 2 points. Can you see this? So this is another curve that passes through those 2 points. So it's here and here. So does that make sense? It's like the straight line being able to- we had an infinite number of straight lines that could pass through one point. we have an infinite number of quadratic curves that can pass through 2 points. So to make it unique, we need to specify 3 points. So this is now the general formula for how we do like secret sharing. So we determine how many shares need to be present. Okay, so 3, 4, 7, whatever. And then given that, we identify a polynomial that requires those number of shares in order to be uniquely defined. Then we set the secret to be 0, secret on the graph. We then draw a random version of that polynomial. You know, in the initial case, we drew a random straight line. We could draw a random quadratic curve, we could draw a random cubic curve, all depends on the threshold. Then once we have done that, we can now pick as many shares as we need from that polynomial and then give it out to the different parties. So when the required number come together, then they can reconstruct the curve and you just check the value at 0 and that's basically your secret. Does it make sense? Any questions? Cool. So a very interesting application of this is imagine you had your private key, right? Normally you store your private key somewhere safe. Maybe you write it down or you store it in a hardware wallet, but usually your private key is usually in one, one location, right? You're storing your secrets in one point of failure. So if someone should get access to where you have stored your secrets, they basically have access to your, your private key. What you could do is you could convert your private key into shares the same way we converted that code into shares. You convert your private key into shares, multiple shares, maybe like 5 shares or 6 shares, your private key or seed phrase. Yes. So you could do either, but this is a general method for splitting up some information. All right, so You split it up into 5 different shares. And then there's this really cool thing you could do where you could store information in pictures. I don't know if you guys have heard of this. Like, there is a way to store information into pictures. So one really nice thing you could do is you could take your private key, split it into 5 shares, then convert each of those shares into your picture. So you have your picture, you combine it in there. And then you could literally just post it on like social media or something. Like you could post on Twitter, you could, you could send it to your friend, you could do whatever. And then you have your threshold, right? Like as long as you can recover 3 pictures or 2 pictures, you can extract the share from it and then you can draw the line and basically get your original seed phrase from there. So this is now like converting a secret. This is converting a secret into making a secret open, essentially. Like, your secret is literally hiding in plain sight. And you can do some really crazy things with this because of- you could add a password. Like, right now, you know, we put our secret at 0, secret. Everybody knows it's at 0, secret. So if someone knows you are doing this, they'll pull your pictures, they'll construct a straight line, and then go and evaluate at 0. But who says it has to be at 0, right? You could literally put your secret at any value of x. How would they know which value of x you put it there? So that serves as a password, kind of, right? You just choose a random value, let's say 1648, secret, and then nobody is going to know that. The only way they're going to be able to know that is if they like brute force. But as they are brute forcing, how would they know which one is valid, which one is the seed phrase? So this is like something really interesting that one could do with this. Another thing that could be explored is like creating shares that are worth more than others. So you could have like in that house scenario where you have 7 people and then you needed 4, there might be someone that contributes a lot more, right? So you want that person's share to have a lot more power than other people. So that person only needs one other person. Other people need 4. So you could have something similar. So these are really interesting directions that any curious folks here can decide to explore. I'm always on the lookout for like really smart people. So please reach out to me if things like this sound really interesting to you. We also have like, so I don't know, you saw Francis today where he was talking about ZK. So it is me and Francis that are running that ZK study group. And if you guys are interested in things like this, we go really in-depth, like hardcore stuff, writing code, reading papers. But in a- you see, what we did today was not that difficult, right? If you hear ZK, you think that, oh, ZK is crazy, ZK is too hard. No, we will break it down for you. We'll make sure that it is really understandable. And, um, If you are- if, if you haven't joined yet, just, just please join. And, um, it was, um, yeah, I think that's the end. All right, thank you guys. Oh, that's at the beginning. Any questions? So you can reach out to me on Telegram or Twitter.

More from this hub

Something wrong, or a video you want off this page? Write to wethem.xyz@gmail.com and it is fixed or taken down within 48 hours.