Video - Bitcoin - Proof Of Work

An explanation of cryptographic proof-of-work protocols, which are used in various cryptographic applications and in bitcoin mining. Traditional digital cash schemes solved the double spending problem by having a centralized (online) entity that could check for coins being spent repeatedly. Bitcoin provides a nifty solution that works without a centralized entity by leveraging the proof of work. As long as honest nodes control the majority of the collective computing power, it's an uphill battle for a dishonest node to successfully double spend. Instead, they are better off mining themselves.

TRANSCRIPT

A proof of work protocol is a vehicle really by which somebody can effectively prove to you. They've engaged in a significant amount of computational effort. And a proof of work protocols often amount into puzzles. And these puzzles that can on the one-hand be challenged itself and by that, I mean they require some serious computational effort and really can't be short-circuited. But on the other hand, that effort can actually be easily verified. And it can be verified far less time than it took to conduct an effort in the first place. Okay.

And there are a number of applications of such protocols. So, for example, if you've heard of the Bitcoin, the Bitcoin Electronic Payment System. That system actually leverages a proof of work scheme within the context of creating what are known as transaction Blockchains. Okay. Now, aside from Bitcoin which is a very recent user of these types of proof of work schemes. These schemes been proposed in the past for other applications. For example, proof of works schemes have been proposed for doing things like deterring denial of service attacks or DoS attacks. And here is the idea is that the requester looked the other particular service would have to solve a very specific computational problem of proof of work puzzle before being allowed to use the service. And the idea here is that the computational effort exerted is effectively a way to throttle the requester, okay. The respond that can in turn easily check that the requester carried out the requisite work and only if that work was carried out while the responder responds to that request for service, okay.

Now the original application for these types of proof of work protocol is the first place that I have seen it proposed is in the context of being able to deter spam email. And then obviously we all know what spam email is hopefully. These are messages that you don't want in your inbox that may become to you in an unsolicited fashion. And the idea here is that a proof of work protocol can be, it turns out it can be tied to a particular email message. And this is conceptually like with the affixing and postage stamp to a message. But rather than paying that stamp or paying for that stamp using money. You're basically paying for that stamp via CPU cycles.

So, for legitimate sender who is only sending out a small number of messages this type of proof of work protocol will not amount to very much. It's going to be a minor deterrent since it's only executed a very small number of times. It's kind of an impediment but it's not something that so unreasonable, okay. Now, for a spammer who might be sending out a lot of messages. Maybe hundreds of thousands or millions of messages it might be prohibitively expensive to repeatedly expend so many CPU cycles for each message and each sender to whom that message is being sent, okay. So far this gives you a flavor for some of the applications of these proof of work protocols. Let me actually dive into how they work in practice, okay.

So, first of all the way that I like to think of these protocols is that typically they work relative to a given challenge string. And I'm going to call this challenge string and we'll label it with the letter 'C'. So, 'C 'is going to be kind of a challenge string. And what the person trying to engage in the protocol will do the prover of the work will basically try to come up with a corresponding proof that is tied to this challenge string, it's going to be kind of response associated with this challenge that has a very specific mathematical property in relation to this challenge, okay?

And as you point out maybe that when I want to talk about a challenge string here. For example, in the context of spam. This challenge string might actually represent an email message, okay. So, it's going to be something very specific to the task at hand, okay? Now, what the prover will do is come up with a response string and let's call the response string, we'll call the response string R. Actually, let's use the terms P for it since maybe we can think of as a proof, okay, a prover response. Okay, and the idea is that the prover will come up with this proof or response string and he has to come up with a string such that when you can concatenate the challenge and the response and you take the two together and you apply a cryptographic hash function. So, let's say come up with a cryptographic hash function like SHA256 or anything of that nature. If I take the challenge string and the proof string and concatenate together and apply the cryptographic hash function, apply these mathematical transformations that represent the cryptographic hash function. I wanted to come up with a proof string such that the output under this hash function will have a very specific property. That property in the prefix of the output. The first large number of bits will all be 0. So, let's say the first 40 bits are first 30 bits or some number of bits will be 0, okay. And then the other bits can be whatever they would normally be, okay.

So, obviously what you're trying to do here is come up with a proof string that has a relationship with a challenge string and that relationship happens to be one that happens or that is taken with respect to a particular hash function and really incorporates or considers what the output of the hash function will be when the proof string is concatenated with the challenge string, okay.

Now, if you, let's say have a good cryptographic hash function then the only known way to find this type of a proof strings to effectively try a lot of possibilities effectively doing brute force by trying a lot of different proof strings until you find one that works. Now if you let say you needed to find an output that contained about 40 consecutive zeros in it that would require you to perform about two to the power forty steps. Two the power forty different hash function invocations. You have to try two to forty different strings and one of them would likely work if you tried two to the forty such strings. It actually requires you to try about in two to the forty just to get a sense is approximately one trillion.

So, if you try it a trillion different strings out and you hash them each you would likely come up with one string that had the first 40 bits being 0. Now, sometimes it might take you a lot less than a trillion steps. Sometimes it might take you a little bit more, okay, or you might get very lucky. You might get very unlucky but on average it will take you about one trillion steps to find a string where the first 40 bits are equal to 0, okay. So, it's something that's not easy but it's also not outside the realm of possibility.

Now, to understand why it's really hard to solve these types of proof of work schemes and more efficiently than maybe simply doing brute force. I think it's helpful to recall that the output of a cryptographic hash function looks more or less random. In fact, each output bit looks like a series of coin flips, okay. So, it's kind of like something of a coin and if it comes up heads you would have a 0 and if it comes up tails you can think of it as 1. And so, what you're really doing is saying if I flipped 40 coins what are the odds that you would have 40 consecutive heads on those forty coin flips? Now, obviously that likelihood is very small. But it's not outside the realm of possibility. If you took 40 coins and you flipped those 40 coins about a trillion times you would actually expect to see one instance in which all 40 coins came up as heads, okay, out of a trillion tries. Okay.

Now, one interesting thing with these proof of work schemes is they could be ratcheted up or ratcheted down. So, for example, let's say you want to require even more computational heavy lifting to come up with a correct proof string, okay. Let's say you want to increase the work that's going to be proved here. What you can effectively do in that case is you can just increase the requirement on the number of leading zeros. So, every time you add an additional zero you effectively double the computational horsepower needed on average. And that's because you're effectively requiring one more coin to come up heads and that entails doubling the number of coin flips, okay.

So, if I had 41 coins flips and I required 41 straight heads that would require about twice as much effort as this requiring 40 straight heads, okay. And likewise, every time you remove a zero from consideration or from the requirement that would reduce the competition horsepower needed to about half of what it was previously. So, for example, if I only required the first 39 bits to be 0 that would require about half as many coin flips as require in the first 40 bits to be 0, okay. Now, the neat thing is that once you come up with the solution. Let's say that somebody tries, you know, a trillion times and they finally come up with a proof string that works it's very easy to validate that this proof string in fact is a correct proof of work. All you have to do is you take the challenge and you take the proof string and you hash them together.

So, for example, just if somebody proposes this just one string let's call it P-prime all you do is you take the challenge and you take P-prime and you input that into a hash function. And you see if the first 40 bits are all 0. So all it requires you to do is apply a hash function once to the concatenation of C&P prime and you can verify that the output indeed has a requisite number of zeros in front of it. And if you see that the output has a requisite number of zeros then you can consider the proof of work valid because you know it must have taken somebody a lot of times, a lot of tries really to provide or come up with the string P-prime such that the concatenation of C&P prime gives you a number of zeros under the application of this cryptographic hash function.

So, as you can see these schemes are quite simple but quite clever at the same time. They really amount to coming up with a proof string that has a very specific mathematical relationship with the original challenge strings. Hopefully this video give you a flavor for the mechanics of how these proof of work protocols work.