Okay. Time to change gears again. Now we're gonna talk about doing a multi-party lottery in Bitcoin, and hopefully doing it in a secure way. So again, we'll start with the offline version of what we're trying to build here. How do we do a real world lottery between two people without any trusts, and I'll get back to what without any trust means in a second. But there's a very simple solution for this. If Alice and Bob wanna bet five bucks, they'll both agree to a bet. Bob will flip a coin, one of them will call it hopefully while it's in the air, and then they'll both have a very clear understanding of who won, and they'll trust that this was a random process and that neither one of them was able to influence the outcome. So maybe betting on a coin flip is sort of boring, [COUGH] but this is very easy to do in the offline world. And of course they have to trust that whoever loses is actually gonna pay. Maybe this isn't actually legally enforceable, so it's just an agreement of honor between Alice and Bob. That's a hard problem in the offline world. We'd like in the online world to do a lottery and solve both problems. So both the problem of generating randomness that both parties can agree is fair, and having the party who loses actually be forced to pay. Okay, so how can we do that online? So, if a network is between Alice and Bob they can't see the same physical coin in the same place but they wanna bet on a coin flip. So Alice might say let's bet $5, I'll flip the coin here it is. Maybe she'll turn on her video camera or something. And Bob might say I don't know if I trust you here. I can't see your coin maybe you're showing me a video stream that you've already pre-recorded. I'm out, I don't wanna do this. I don't have any trust that you're not gonna cheat me. So a solution is to use Hash commitments, our old friend from the first section of this lecture. So this is the same information and we remember that you can publish a Hash commitment when not revealing any information, and we can later reveal the input to the Hash function to open the commitment and show what our data was. So how can we do this to build an online lottery? So we'll have three parties now, Alice, Bob, and Carol, who all wanna do a lottery together. So to start with, all of them will choose a random number, often called a nonce in cryptography. And they're gonna keep that random number to themselves. And as long as each one chooses a random number, they should trust that the final outcome is random and that nobody else is able to cheat them. Now there's gonna be two phases of communication in this protocol. In round one, everybody is gonna publish a commitment to their random data. So all three parties are just gonna publish a hash of the random number that they chose. And remember, this doesn't reveal anything about the random number, as long as it's chosen from a large enough space. So say each one of them chooses a 128 bit random string, they can publish the hash with no worries, they haven't given away any useful information. Now, [COUGH] we have to make sure that the second phase happens strictly after the first phase is over. So after everybody has committed to the randomness that they chose, now we'll have a second round where everybody reveals the random number that they've committed to. And of course everybody should check that those values that they reveal actually match the hashes that they published earlier and that the commitment was actually valid, but assuming that actually happens, now everybody has published this random number that they all chose independently. Now there's a fairly simple program that will determine who wins the lottery. There's a lot of ways to do this of course, but the simplest way is we could just take all three random numbers, take the x or of them, which is gonna mix in bits from everybody's random number. Then we'll take the hash of that, divide it mod 3, and that will give us randomly one of three outcomes. And we'll just assign each outcome to one of the participants and that will determine that either Alice, Bob or Carol is the winner. And everybody can run this protocol themselves and trust that this was a fair process. So an important property of that hash function is that it guarantees randomness. Nobody could try to choose their random number in such a way that it makes it more likely that the final outcome is them winning. Especially considering that they don't know the randomness that everybody else is choosing. So without getting into a long, formal definition of randomness and pseudo randomness and hash functions, it's safe to say that the way hash functions currently work, with a good hash function, there's no way to cheat at this game. There's no better strategy than just choosing a random number, which gives you a one-third chance of winning. So what happens if somebody fails to reveal their commitment? So let's go back to round two of the protocol, and let's say that Alice and Bob each publish their commitments, and then Carol looks at these, and she says, hm, if I publish my commitment, I'm gonna lose. I can see the random numbers that Alice and Bob chose, and I know which random number I chose, and I can run that script and tell that I'm not going to win. So if Carol wants to be malicious here, what she can do is not publish her random number and just say, oh I'm sorry I forgot it. Or maybe she could go offline, or for whatever other reason provides a plausible reason why she can't reveal what her random number is. And now it's impossible to run this final script, because you don't have one of the inputs. And Alice and Bob can see this and they can say, Carol, that's not cool. You just wrecked the lottery, you probably did this because you were going to lose, you cheated us, but they don't have any real recourse here. So, by itself this protocol doesn't really work if any of the participants are malicious. Because, whoever the last party is to reveal what their random number is could just refuse to do so if it's going to make them lose. So what we'd like is a scheme to publish a commitment that we have to reveal within some certain time and BitCoin is going to provide a really cool means for us to do that. So how can we do this? And again, the idea is we want to force the party that has chosen this random number and committed to it to reveal what the random number was to open their commandment before time t. So let's say that Alice is trying to enter into a timed hash commitment with Bob. So Alice is gonna put up a bond, and she's gonna have a transaction that will pay the bond in two cases. So if Alice and Bob both sign, that's enough to claim the bond, or if Alice signs and reveals what her data was, and you can check this in a Bitcoin script, you can check that there's a value in the redemption script, the script sig that includes that value x, it has a certain hash. So Bitcoin, without changing anything about the script, allows us to include this property that you have to specify this data with a certain hash in order to claim payment. So in that case Alice can claim the money all by herself, but she has to reveal her chosen value. She has to open her hash. Okay, so now how can we use this funny and complicated transaction with two different ways to claim the money? Well, Alice and Bob are both going to sign a transaction that pays the entire value to Bob. And they're gonna use this n_lock_time, which we talked about earlier, to ensure that Bob can't claim the bond before some time t. So now they've set up essentially a ticking time bomb where if Alice doesn't do anything else, Bob is going to get the value of that bond at time t. So as an alternative, Alice can publish a transaction before time t reclaiming her bond sending the money back to herself, but if she does that, she has to not only sign it, she has to reveal x. So I said that there were two ways to claim this original transaction, and either one of them are valid outcomes of the protocol. So either Bob, gets this bond, some money that Alice put up, or Alice has to reveal her commitment. So it's not exactly forced. If Alice doesn't reveal her commitment, she's not going to be thrown in jail, but she will lose this entire bond that she put up. So her guarantee that she'll reveal the commitment is as strong as how much money she's willing to put behind it. So, how can we use this primitive of timed hash commitments to do a more secure lottery? We'll have almost the exact same structure as before except instead of using the simple hashed commitments now everybody is going to use a timed commitment. Where if they don't reveal their random value by a certain time, there's a bond that the other two players will get to keep. So if we get into that same situation, where Carol can look at the other two parties' random values and say, I'm about to lose this lottery, the other possibility for Carol of not publishing is also not very appealing because if she refuses to publish a random value she's going to lose her bond anyway. So if the bond is higher than the value that's at stake in the lottery, we except that Carol will publish her value and the lottery will go on as usual and everybody will get their bond back. So this lottery in Bitcoin using time commitments has been proposed and can actually be implemented on top of Bitcoin today. Now the downside is that this is fairly complicated. Doing those timed hash commitments, requires multiple transactions. And when you have N players in a lottery it's actually an N squared logarithm. And you also have to put money up in the form of a bond, and the key property is that the bond money you put up has to be more than the amount that you're actually betting. So this isn't the most efficient way to do a lottery because you have to put up more money than is actually at stake in the lottery. But it's pretty good and for a small number of people it might work okay.