Bitcoin: Proof of work An explanation of cryptographic proof-of-work protocols, which are used in various cryptographic applications and in bitcoin mining.
Bitcoin: Proof of work
- A proof of work protocol is a vehicle,
- by which somebody can effectively prove to you
- they've engaged in a significant amount of computational effort.
- Proof of work protocols often amount to puzzles.
- These puzzles can, on the one hand, be challenged and solved
- and 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.
- It can be verified in far less time than it took to conduct that effort in the first place.
- There are numer of applications of such protocols.
- For example, if you've heard of a bicoin electronic payment system,
- that system actually leverages a proof of work scheme
- within the context of creating what are known as transaction block chains.
- Aside from bitcoin, which is a very recent user of these types of proof of work schemes,
- these schemes were being proposed in the past for other applications.
- For example, proof of work schemes have been proposed
- for doing things like deterring of denial-of-service attacks, or DoS attacks.
- Here, the idea is that the request to allow you to a particular service
- would have to solve a very specific computational problem, a 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.
- The responder can in turn easily check
- if the requester carried out the requisite work
- and only if that work was carried out
- will the responder respond to that request for service.
- The original application for these types of proof of work protocols,
- the first place that I've seen it proposed,
- is in the context of being able to deter spam email.
- Obviously, we all know what spam email is.
- These are messages that you don't want in your inbox
- and maybe come to you in an unsolicited fashion.
- The idea here is that a proof of work protocol can be tied to a particular email message.
- This is conceptually like affixing a post SSM to a message,
- but rather than paying for that stamp using money
- you are basically paying for that stamp via CPU cycles.
- For a legitimate centre only sending out a small numer of messages
- this type of proof of work protocol will not amount to very much.
- It's gonna be a minor deturn since it's only executed a very small number of times.
- It's kind of an impediment, but it's not something that is so unreasonable.
- 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 expand so many CPU cycles
- after each message and each sender to whom that message is being sent.
- So far I just gave you a flavour of some of the applications of these proof of work protocols.
- Let me actually dive into how they work in practice.
- First of all, the way that I like to think about these protocols
- is that typically they work in relation to a given challenge string.
- I would call this challenge string and would label it with the letter "c",
- so "c" is gonna be kind of a challenge string.
- What the person trying to engage in the protocol will do,
- the prover of the work will basically try to come up with the corresponding proof
- that is tied to this challenge string.
- It's gonna be kind of response associated with this challenge
- that has a very specific mathematical property in relations to this challenge.
- As you pointed out, when I talked about the challenge string, for example in the context of spam,
- this challenge string might actually represent message.
- So it's gonna be something very specific to the task at hand.
- What the prover will do is come up with the response string.
- Let's call the response string "r".
- Actually, let's use the letter "p" for it.
- We can think of it as a proof.
- A proof or response.
- The idea is that the prover will come up with this proof or response string
- and he is to come up with a string such that when you can coordinate the challenge and the response
- and you take the two together and apply a cryptographic hash function,
- something like SHA-256 or anything of that nature,
- if I take the challenge string and the proof string, combine it together
- and apply the cryptographic hash function,
- apply these mathematical transformations that represent the cryptographic hash function,
- I wanna come over the proof string
- such that the output under this hash function will have a very specific property.
- The prefix of the output, the first large numeral bits will all be zeros.
- Let's say the first forty bits, or first thirty bits, or some number of bits will be zero.
- And the other bits can be whatever they would normally be.
- Obviously, what we are trying to do here is come up with proof string
- that has a relationship with the challenge string
- and that relationship happens to be one that happens
- or 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.
- If you have a good cryptographic hash function
- then the only known way to find this type of a proof string
- is to effectively try a lot of different possibilities.
- Trying a lot diffeent proof strings until you find one that works.
- If you needed to find an output that contained about forty consecutive zeros in it,
- that would require to perform about two to the power of forty steps.
- Two to the power of forty different hash function invocations.
- If you try two to the forty different strings and one of them would likely work
- if you tried two to the forty such strings.
- That would require, just to give you a sense, it's approximately one trillion.
- So if you try that trillion different strings out and you hash them each,
- you would likely come up with one string that had the first forty bits being zero.
- Sometimes it may take a lot less than a trillion steps,
- sometimes it may take you a little bit more.
- You may get very lucky, you may get very unlucky.
- On average, it will take you about one trillion steps
- to find a string where the first forty bits are equal to zero.
- It is something that is not easy but it is also not outside the realm of possibility.
- To find the reason why it's really hard to solve these types of proof of work schemes
- more efficiently than 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.
- It is like flipping a coin and if it comes up heads, you would have a zero
- and if it comes up tails, you can think of it as a one.
- So what you are really doing is saying:
- "If I flipped forty coins what are the odds that I would have forty consecutive heads
- on those forty coin flips."
- Obviously, that likelihood is very small,
- but it's not out of the realm of possibility.
- If you took forty coins
- and you flipped those forty coins about a trillion times,
- you would actually expect to see one instance in which all forty coins came up as heads.
- Out of the trillion tries.
- One interesting thing with these proof of work schemes
- is they can be ratcheted up or ratcheted down.
- For example, let's say you wanna require even more computational heavy lifting
- to come up with the correct proof string.
- You want to increase the work that is gonna be proved here.
- What you can effectively do in that case
- is you can just increase the requirement on the numer of leading zeros.
- Every time you add additional zero,
- you effectively double the computational force power needed on average.
- That's because you are effectively requiring one more coin to come up heads.
- That entails doubling the numer of coin flips.
- If I had forty one coin flips and I required forty one straight heads
- that would require about twice as much effort as is required with forty straight heads.
- Likewise, every time you remove a zero from consideration of the requirement
- that would reduce the computational force power needed to about a half of the one needed previously.
- So for example, if I only required the first thirty nine bits to be zero
- that will require about half as many coin flips
- as required in the first forty bits to be zero.
- The neat thing is that once you come up with the solution,
- let's say that somebody tries and they finally come up with a proof string that works,
- it is 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 check the proof string and you hash them together.
- For example, if somebody proposes this one string...
- let's call it "p prime"
- ...all you do is you take the challenge and you take p prime
- and you input them into a hash function.
- You see if the first forty bits are all zero.
- All this requires you to do is apply hash function once to the concatentaion of c and p prime
- and you can verify that the output indeed has a requisite numer of zeros in front of it.
- If you see that the output has the requisite numer of zeros,
- 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 the string p prime,
- such that the concatentaion of c and p prime
- gives you a numer of zeros under the application of this cryptographic hash function.
- As you can see, these schemes are quite simple
- but quite clever at the same time.
- They really amount to coming up with the proof string
- that has a very specific mathematical relationship with the original challenge string.
- Hopefully, this video gave you a flavour for the mechanics of how these proof of work protocols work.
Be specific, and indicate a time in the video:
At 5:31, how is the moon large enough to block the sun? Isn't the sun way larger?
Have something that's not a question about this content?
This discussion area is not meant for answering homework questions.
Share a tip
When naming a variable, it is okay to use most letters, but some are reserved, like 'e', which represents the value 2.7831...
Thank the author
This is great, I finally understand quadratic functions!
Have something that's not a tip or thanks about this content?
This discussion area is not meant for answering homework questions.
At 2:33, Sal said "single bonds" but meant "covalent bonds."
For general discussions about Khan Academy, visit our Reddit discussion page.
Here are posts to avoid making. If you do encounter them, flag them for attention from our Guardians.
- disrespectful or offensive
- an advertisement
- low quality
- not about the video topic
- soliciting votes or seeking badges
- a homework question
- a duplicate answer
- repeatedly making the same post
- a tip or thanks in Questions
- a question in Tips & Thanks
- an answer that should be its own question