# Bitcoin: Proof ofÂ work

## 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.