Main content

## Finance and capital markets

### Unit 8: Lesson 8

Bitcoin- Bitcoin: What is it?
- Bitcoin: Overview
- Bitcoin: Cryptographic hash functions
- Bitcoin: Digital signatures
- Bitcoin: Transaction records
- Bitcoin: Proof of work
- Bitcoin: Transaction block chains
- Bitcoin: The money supply
- Bitcoin: The security of transaction block chains

© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice

# Bitcoin: Proof of work

An explanation of cryptographic proof-of-work protocols, which are used in various cryptographic applications and in bitcoin mining. Created by Zulfikar Ramzan.

## Want to join the conversation?

- I am confused about how applying this scaling to bitcoin results in the difficulty changes seen in the wild. As near as I can tell, the 'number of leading zeroes' approach to scaling the work necessarily translates into the work increasing or decreasing by powers of two. Is this not true? While I am not a miner, I had the impression that the difficulty scaling was much finer-grained than simple powers of two. What am I missing?(8 votes)
- Yes, this also confused me at first. Just mentioning the number of leading bits is good for illustrative purposes, but is also a simplification.

The trick (and the way I think it is done in Bitcoin) is to look at the hash as a number in binary notation. Then we can say that this number has to be smaller than some limit, instead of just having a minimum of leading zeroes. Doing this is a lot more fine-grained.(19 votes)

- What is the challenge string in Bitcoin? Also, does it really use the 'leading number of 0s' as it's proof of work?(4 votes)
- The challenge string is a hashing together of all the transactions in the block and a few other things like the timestamp, the block number, and a link to the previous block. The miner then needs to put the challenge string and the proof string, known as the nonce, into the hashing algorithm SHA-256, and get a string with a certain number of leading zeroes. Numerically, you can think of it as the output having to be less than a certain value.(6 votes)

- Does exist a website where the current target for POW from difficulty or bits can be calculated?(3 votes)
- good stuff. this is way too confusing still. will there ever be a video on the step by step basics? Basic questions i am talking about are these:

alice Vka sends bob VKb 50. got it.

only 1 transaction must be made, no matter how big your account is, lets say Alice has 10,000 bitcoin.

she would have to send 50 bitcoin to bob and 9950 back to herself?

where is the bitcoin miner price listed?

is there a section where you could type it in?

i.e. bitcoin miner fee*____*

what about the rest of the transaction... Alice will not send Bob bitcoins for free...will bob send a product back to Alice?

what if many people , Jay, Alice, John, send Bob 50 bitcoin? how does BOB know alice sent the bitcoin and not Jon? so Bob knows where to send the product

could you please over the very basics? not what it is, but the process in a transaction? thanks(3 votes) - thanks for the great video,, i have two question that i couldn't figure out

1)how double spending can be bypassed? suppose the attacker has more CPU power than the honest nodes, he will generate a blockchain that is Not the same as the other nodes' block-chain; it's supposed to be easily detected?(for example, the attacker changed the ledger by generating a block that is 4 blocks before the last block and continued redoing the rest) even though he did a proof-of-work,, the block chain generated and broadcasted will NOT be the same as the block chain stored in honest nodes' computers. so how it can double spending be bypassed?? isn't supposed to lead to inconsistency between the attacker's generated blockchain and the others' ones?

also,2) how the longest chain is identified?(1 vote)- To have more CPU power than honest nodes, attacker must spend tens of millions dollars. That's amount of capital currently invested into mining equipment. You won't do that to fraudulently buy a TV set. If you try to use that power to play against the rules, Bitcoin value will crash to zero, and you will have nothing to double-spend. If, however, you use that power to honestly compete with other miners for block rewards, you will receive $millions in rewards and maybe even recoup your investment. In addition, Bitcoin will become more resistant to attacks and arguably more valuable, so you earn twice. So the system of economic incentives in Bitcoin strongly encourages playing by the rules. However, it is possible that the attacker does not care about economic gain, and just wants to destroy Bitcoin. It can be a nation state, or a large company for example. This is one of the known weaknesses of Bitcoin.(4 votes)

- I have some basic question in regards to the Bitcoin ecosystem. It is a very decentralized but it seems that some entity is doing administrative work, such as making the challenges for the nodes, updating the challenges, distributing the challenges etc. Who is doing these activities?(2 votes)
- That, too, is decentralized. The challenge string is created by the miner, and it is the result of hashing together all of the transactions in the block, a reference to the previous block, the timestamp, the node version the miner is using, and a few other things. Everyone involved knows exactly how to find what the challenge string is, and everyone can easily verify that all the rules are followed.(1 vote)

- Hi I understand the value of proof of work while there are still bitcoin to be mined but once all bitcoin are mined would it not be more useful to have bitcoin as a global currency that does not require a large amount of effort to be validated by nodes for every transaction? Therefore almost nullifying transaction fee's and the need for miners?(2 votes)
- The proof of work is there to make sure that the network is secure against double-spend attacks. That threat will exist whether or not there are still bitcoin to mine.(0 votes)

- I have a question about the verification of proof of work. If I understand correctly the result of the pow is the p (proof response) and it is easily verified by putting it as input together with the c (challenge) into the hash function and making sure you get an acceptable result. To make this happen the one who wants to show his pow must show the p. That means that the one who wants to verify the pow will get the p. If p is the pow then the verifier will have the pow without putting in the work. If this is true, someone wanting to make a blockchain can just ask for all the p´s in the chain and make a new false one without most of the work. There must be a function no one talks about thet prohibits this but I have not seen it anywhere. What am I missing.(1 vote)
- I think that you are missing the fact that the PoW not only needs as an input a p but also a message. The p will only give PoW for that input message.

In blockchains this means that if you get someone elses p then you can only use it to spread the block that he used to create his p with since the p will be invalid for other blocks. And since the reward is part of the block you can only use his p to spread a block that will send the reward to his address of choosing.(1 vote)

- Why do we want the first 40 bit to be zeros ?(1 vote)
- Because that is hard to do and would require a lot of guesses. Also note that 40 is an arbitrary number, in Bitcoin this number changes depending on the desired difficulty.(1 vote)

- Why do miners need to provide a proof of work? What if a miner provides an acceptable proof of work without actually verifying the transactions?(1 vote)

## Video transcript

A proof of work protocol
is a vehicle really by which somebody
can effectively prove to you that
they've engaged in a significant amount
of computational effort. Proof of work protocols
often amount to puzzles. And these puzzles that
can, on the one hand, be challenging to
solve-- 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 in far less time than it took to conduct that
effort in the first place. OK. 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. Now aside from Bitcoin,
which is a very recent user of these types of
proof of work schemes, these schemes have been
proposed in the past for other applications. For example, proof
of work schemes have been proposed
for doing things like deterring denial-of-service
attacks, or DoS attacks. And here the idea is
that the requester of a particular
service would have to solve a very specific
computational problem, a proof of work puzzle, before being
allowed to use a 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. Now 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. 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
an unsolicited fashion. And the idea here is that
a proof of work protocol, it turns out it can be tied
to a particular email message. And this is conceptually
like affixing a postage stamp to a message, but rather than
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
deterrent 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. 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. So hopefully this
gives you a flavor for some of the applications of
these proof of work protocols. Let me actually dive in to
how they work in practice. 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-- we'll label
it with the letter c. So c's 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 a response associated with this challenge. It has a very specific
mathematical property in relation to this challenge. And as you point out, maybe when
I talk about a challenge string here, for example in
the context of spam, this challenge
string might actually represent an email message. So it's going to
be something very specific to the task at hand. Now what the prover will do is
come up with a response string, and let's call the
response string r. Actually, let's use
the term p for it, since maybe we can think
of it as a proof, a proof or a response. 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 concatenate the
challenge and the response, and you take the two
together, and you apply a cryptographic hash
function-- so let's say I come up 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. 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. And then the other bits can be
whatever they would normally be. So obviously, what
you're trying to do here is come up with a
proof string that has a relationship with
the challenge string. And that relationship
happens to be one 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. And if you, let's say, 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, effectively doing
brute force, by trying a lot of different proof strings
until you find one that works. Now if you, let's
say, needed to find an output that contained about
40 consecutive 0's in it, that would require you to
perform about 2 to the power 40 steps, 2 to the power
40 different hash function indications. You'd have to try 2 to the
40 different strings, and one of them what would likely
work if you tried 2 to the 40 such strings. That actually requires you to
try about, and 2 to the 40 just to give you a sense, is
approximately 1 trillion. So if you tried a trillion
different strings out, and you hashed 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. You may get very lucky. You might get very unlucky. But on average, it will take
you about 1 trillion steps to find a string where the
first 40 bits are equal to 0. So this is 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 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. So it's kind of like
flipping the coin, and if it comes up heads,
you would have a 0, and if it 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 40 coin flips? Now obviously that
likelihood is very small, but it's not outside the
realm of possibility. If you flipped 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 out of
a trillion tries. Now one interesting thing with
these proof of work schemes, is they can 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. 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 could just increase
the requirement on a number of leading 0's. So every time you
add an additional 0, you effectively double the
computational horsepower needed on average. And that's because
you effectively requiring one more coin
flip to come up heads, and that entails doubling
the number of coin flips. So if I had 41 coin flips and
I required 41 straight heads, that would require about
twice as much effort as just requiring
40 straight heads. And likewise, every time you
remove a 0 from consideration, or the requirement,
that will reduce the computational 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 requiring the
first 40 bits to be 0. Now the neat thing is that once
you come up with a solution-- let's say that somebody
tries a trillion times and they finally come up
with a proof string that works-- it's very easy to
validate that this proof string is in fact 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, 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, 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 the requisite number
of 0's in front of it. And if you see that the output
has the requisite number of 0's, 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 concatenation of c and p prime gives
you a number of 0's 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 string. So hopefully this
video gave you a flavor for the mechanics of how these
proof of work protocols work.