That in order to commit to a value message,

we're going to generate a random 256 bit value and call it the key.

And then we're going to, as the commitment,

return the hash of the key concatenated together with the message.

And as the key value, we're going to return H of this key.

And then later, to verify, someone is going to compute this same hash of

the key they were given, concatenated with the message.

And they're gonna check whether that's equal to the commitment that

they saw, okay?

So this is a way of using hash functions of both in the commitment and

in the verification.

So now the security properties.

If we go down to the security properties that were at the bottom of the previous

slide, and we just plug in the definitions of how we're going to implement this here.

That is, this used to say com, given com infeasible to find msg,

we just plug in what com is.

Com is the hash of key concatenated with msg.

And similarly down here, this is what happens when we take

what was written there before and plug in the definition of verify in com.

Okay, so now what these properties become, the first one is given H(key | msg),

it's infeasible to find msg.

Well, it turns out that that's exactly the hiding property

that we talked about before.

Key was chosen random 256-bit value.

And therefore, the hiding property says that if we take the message, and

we put before it something that was chosen from a very spread out distribution,

like I said a random 256-bit value, then it's infeasible to find the message.

So this is exactly the hiding property.

And this one down here turns out to be exactly the collision-free property.

So that if someone can find two messages which have the same hash like this,

well then they have an input value here and

an input value there that are different, and yet those have the same hash.

And so because of the two security properties we've talked about for

hashes so far, this commitment scheme will work,

in the sense that it will have the necessary security properties.

Okay, so that's the second security property of hashes, that they're hiding.

And the application of that is commitments.

The third security property we're going to need is that they're puzzle-friendly.

And this is, again, a little bit more complicated,

but let me just go through it bit by bit.

That for any possible output value y that you might want from the hash function.

We're going to use y as an output value of the hash later.

That if k is chosen from a distribution that has high min-entropy.

That is, k is chosen randomly from some set that's super spread out.

Then there's no way to find an x, such that the hash of k and x is equal to y.

So, what this means is basically that if someone wants to target the hash function,

if they want it to come out to some particular output value y.

That if there's part of the input that is chosen in a suitably randomized way,

that it's very difficult to find another value that hits exactly that target.

So the application we're going to use of this,

is we're going to build a search puzzle.

And what that means is we're going to build a mathematical problem,

which requires searching a very large space in order to find the solution.

And where there's no shortcuts,

a way to find a good solution, other than searching that large space.

That's a search puzzle.

To be more specific, the idea is that if we're given a puzzle ID,

which is chosen from some high min-entropy distribution.

That is some very spread out probability distribution.

And we're given a target set, Y,

which someone wants to make the hash function fall into.

Then we wanna try to find a solution, x.

So that if we hash the puzzle ID together with the solution X,

we get a result that's in the set Y.

So the idea is Y is a target range or a set of hash results that we want.

ID specifies a particular puzzle, and x is a solution to the puzzle.