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.

AWESOME!!!!

sounds like commercial

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.

WAIT WHERE IS SAL?

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.

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!

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.

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.

*$1billion, not $100million

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.

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.

Good point. $500k is a bit low imo.

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?

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

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.

lol true man jesus this guy

does it realy work inbox me ?

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?

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.

You mean to tell me that's all we were talking about all day?

… and you didn't understand the concept 🙂

you are veryyyy quiet…..

I love this bitcoin series. Very helpful.

Great Job! This series is one of the best on YouTube..

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?

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

Congressional Report Warns of Potential Bitcoin Threat to US Dollar http://cur.lv/68atl

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 –

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.

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.

lemme tell you a strory of a mouse name delorie, deloiris was a mouse in a big long houseeeeeeeee

ok?

Easiest video to understand in YouTube for proof of work!

ok

This is a very easy to understand video that I will be recommending to people.

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.

Volume is crazy low. Maybe increase it a bit?

might be good but can't hear correctly Sound too low by far

Ótimo! Obrigado ao tradutor que traduziu este vídeo para português!

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

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?

https://en.bitcoin.it/wiki/Block_hashing_algorithm

How hash is actually calculated

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.

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?

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

It seems like a massive waste of CPU and electric power.