Bitcoin – Proof of work


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.

46 thoughts on “Bitcoin – Proof of work”

  1. new coins come into existence when new blocks are created as a reward to the miner. Coins have to "mature" after a miner mints them and this takes a while. So its highly unlikely by that point that he will be in the possession of the longest blockchain which he could then use to attempt to double-spend. And so he could not double spend any more easily than anyone else for the same reasons why everyone else cant double spend.

  2. This answer is spot on. 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.

  3. The intent was more to provide a detailed explanation of the mechanics of bitcoin since it's a question on many peoples' minds. Whether it's safe to put your money in bitcoins is an entirely different question. There are definitely many risks in doing so!

  4. No. Its not like a physical coin. its just a number, or a value, of the amount of wealth you own, that is verified by the network.

  5. Yep. But there was a good article on read on this. Lets say an avalon miner runs at 60ghs and costs $1,500. BTC guild which do half of all mining is currently pooled at 35,757 ghs. So assume total is 2x this. So cost of creating a competing node would be $1,500×1000 or lets round up to $2m. Current value of BTC is ~$100m. $2m gamble, but do able.

  6. Perhaps I would believe this whole bitcoin thing – the thing is, it's NOT open source as they claim it to be. I'm a software developer and I'd really like to look at the code of it to really confirm that bitcoin is legit and some hackers can't just create an infinite amount of it.
    Plus bitcoin was introduced to the public only a year and a half after it was created – someone out there must have created in that time LOTS of it.

  7. The current value may be $100m but the market is not $100m deep at all. I can only guesstimate but would be surprised if you could sell over $500k in coins (fake or not) within a reasonable time.

  8. Doesn't such a proof of work protocol open up the responder to application level DoS? For example I constantly send an intentionally wrong proof string to the responder, without trying to generate a valid one, to dismiss the proof as invalid the responder has to check the proof first by running it through the proof of work algorithm (such as sha256(sha256()) ), which should be significantly more computational power than to send the same packet over network @ 100mbit/s, am I on the right track?

  9. can you improve the audio, you're lowering Khan Academy standards. You should practice more. This is not up with Khan Academy quality.

  10. Wow. That was amazing.
    How did you manage to talk for so long about such a simple thing?
    You spoke until your mouth got dry and all.
    Very well done sir, very well done indeed.

    While you could have just said "Some people want to verify that there is a person at the other end of the transaction. To do so they lay out a test. A test that an individual can solve with hard work much faster then a computer can. That test must then have a solution that is easy to check. Such as captcha." you didn't.

  11. I'm trying to understand how ButCoins work!! A "Miner" or a "Proof-of-Work" "node" appears to be nothing more than an accountant, A "node" being the person or volunteer mining (looking) for BitCoins. The BitCoin system relies of these "Nodes" – volunteer – to "Mine" for BitCoins by matheatically proving a "Transaction Block."

    Cas someone tell me if I'm beginning to understand?

  12. bitmessage . org uses proof of work to forward messages throughout the network. It is still beta (and there has not been a security audit yet) but imho it looks stabel and secure.

    And, it's fun: you can create addresses for private messages at any time on your own and even join channels where you can post anonymously or authenticated.

  13. I have a question. It'd be great if someone can explain.

    It seems like this whole process depends on the hash function (both the proof of work, and validation). If an hash function is just an algorithm, or a mathematical formula, then one can work backwards as well as forwards.

    What's stopping someone from finding out the hash algorithm and working backwards to find a valid hash code without working through the 1 trillion inputs?

  14. @AlexNOSAM from six months ago–
    https://github.com/bitcoin/bitcoin
    idk about six months ago, but a search for "bitcoin source code" on google yielded it as the first result.

  15. God you for this priceless education – without these videos this member of the general public would be completely lost – you should seriously consider putting all of this information into a book format –

  16. This video would be a lot more valuable if you walked through an actual example, start to finish. You say 'for example', but then still work on a theoretical level (e.g. first 40 bits are 0). Show an example with actual data as to what it would look like on a website to how the calculations would be done, and how you would pick/create a challenge.

  17. Couldn't you get lucky? I was expecting the proof of work to show that you didn't in fact just get lucky.

    Obviously the odds of getting lucky are very small .. hence the 'luck'. Also I realize you mentioned luck at the 7 minute mark, but didn't say much about it.

  18. 5:20 No need to reiterate portions of what you were building up to say. That confuses a typical person trying to understand every detail. In fact, the video editor should have cut that out, or replaced it — with you restating a more clear message.

  19. Is it possible to do a proof of work crypto without destroying the planet in using more electricity than man can possibly generate?

  20. Just so that I understand, when you are trying to login to a site, to avoid multiple attempts, it is asking you to prove that you are human by selecting few images – do you call this "proof of work" – as it is work done by you to claim that you are actually human?

  21. Fantastic videos. I send a link of your videos to people who want me to explain to them how cryptocurrency Et. al work.

    I would like to mention however that the volume in these videos are extremely low which forces me to turn my speakers to 100% and I still have a hard time to hear what your saying.

  22. In bitcoin, what is the challenge part and who validates it? What prevents a miner from just randomly generating a string with the correct number of zeros?

  23. Bitcoin provides a nifty solution that works without a centralized entity by leveraging the proof of work.

Leave a Reply

Your email address will not be published. Required fields are marked *