Bitcoin: Proof of work

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 on a proof-of-work protocols often amount to puzzles and these puzzles that can on the one hand be challenged solve and by that I mean they require some 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 that 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 block chains okay now aside from Bitcoin which is a very recent user of these types of of proof-of-work schemes these schemes have been proposed in the past for other applications for example proof work seems have been proposed for doing things like deterring denial of service attacks or dos attacks and here the idea is that the requester let's say of a particular service would have to solve a very specific computational problem a proof-of-work puzzle before being a lot to use a service and the idea here is that the the computational effort exerted is effectively a way to throttle the requester okay the responder can in turn easily check the requester carried out the requisite work and only if that work was carried out while the responder respond to that request for service okay now the original application for these types of proof-of-work protocols 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 maybe come to you in a nussle 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 what's there fixing a 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 a 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 to turn since it's only executed a very small number of times it's kind of an impediment but it's not something that's 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 in each sender to invent messages being sent okay so 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 talents string I'm going to call this this challenge string and we will label it with the 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 prove of the work will basically try to come up with a corresponding proof that is tied to this challenge turn 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 one ate when I 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 are actually let's use the term P for it since maybe we can we can think of it as a proof okay approve for response okay and the idea is that the prover will come up with this proof or respond string and he has to come up with a string such that when you concatenate the challenging the response and you you take the two together and you apply a cryptographic hash function so let's that comes with a cryptographic hash function like sha-256 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 want to come up with a proof string such that the output under this hash function will have a very specific property that property the prefix of the output the first large number of bits will all be 0 so let's say the first 40 bits or first 30 bits or some number of bits will be 0 okay and then the other bits can be whatever whatever they would normally be ok 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 ok now if you let's say have a good cryptographic hash function then the only known way to find this temperature proof strings to effectively try a lot of different possibilities effectively doing good force by trying a lot of different proof strings until you find one that works now if you let's say need it to find an output that contained about 40 consecutive zeros in it that would require you to perform about 2 to the power 40 steps ok 2 to the power 40 different hash function invitations you have to try to to the 40 different strings and one of them would would likely work if you tried to to the 40 such strings that should requires you to try about and 2 to the 40 just to give you a sense is approximately 1 trillion so if you try to trillion different strings out and you hash them each you would like they come up with one string that had the first 40 bits being their own sometimes it might take you a lot less than a trillion steps sometimes it might take you a little bit more okay 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 zero okay so this is something that's not easy but it's also not outside the realm of possibility now the reason 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 like flipping a coin and if it comes up heads you would have a 0 - comes up tails you can think of it as a 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 point 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 they can be ratcheted up or ratcheted down so for example let's say you you want to require even more computational heavy lifting to come up with a correct proof spin okay let's say you want to increase the the 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 zeroes so every time you add an additional zero you effectively double the computational horsepower needed on average okay and that's because you're effectively requiring one more coin flip to come up heads and that entails doubling the number of coin flips okay so if I had 41 points lips never acquired 41 straight heads that would require about twice as much effort as just requiring 40 straight heads okay unlike wise every time you remove a zero from from the requirement that would reduce the computational horsepower needed to about half of what it was previously so for example if I only require the first 39 bits to be 0 that will require about half as many coin flips as requiring the first 40 bits to be 0 okay now the neat thing is that once you come up with a solution let's say that somebody tries you know a trillion times 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 the proof strings and you hash them together so for example just if somebody proposes this this one string let's call it P Prime all you do is you take the challenge and you take P prime and you in put them into a hash function okay and you see if the first 40 bits are all 0 so all this requires you to do is apply a hash function once to the concatenation of C and P Prime and you can verify that the output indeed has a requisite number of zeroes in front of it and if you see that the output has the requisite number of zeroes then you can consider the proof of work valid because you know it must have taken somebody a lot of time a lot of tries really to provide or come up with a string P prime such that the concatenation of C n P prime gives you a number of zeros under the application of this cryptographic hash function so as you can see these these things are quite simple but quite clever at the same time they really amount to coming up with a proof string that is a very specific mathematical relationship with the original challenge string hopefully this video gave you a flavor for for the mechanics of how these proof-of-work protocols work