## Subtitles section Play video

• The following content is provided under a Creative

• Your support will help MIT OpenCourseWare

• To make a donation, or to view additional materials

• from hundreds of MIT courses, visit MIT OpenCourseWare

• at ocw.mit.edu.

• PROFESSOR: OK.

• So yeah, problem set 2.

• There's a lot of work done.

• Congratulations, all the workers.

• 16 trillion hashes performed.

• How can we prove that?

• So this is a personal gripe that I hear a lot.

• That people say that proof of work doesn't scale.

• And that really bugs me because sometimes I

• think I sort of know what they're talking about,

• and they mean like, bitcoin doesn't scale, or like,

• these block chains have poor scalability properties,

• which sure, sure.

• They definitely do.

• But proof of work, it scales perfectly,

• in a theoretical sense.

• There's nothing that can scale better.

• You can prove an arbitrary amount of work in 0 of 1.

• Right?

• So in this case, well, how big were these headers?

• They were less than 100 bytes, right?

• 100 characters.

• And with that space, you can prove actually

• the entire work that happened over the entire problem set.

• So yeah.

• block chains, whole bunch of scalability problems.

• There's complex systems, all sorts of scaling issues.

• But proven work itself, in this pure form, scales really great.

• OK.

• So question.

• Not super intuitive, but how do you

• prove all the work ever done throughout the entire problem

• set in one line?

• how do you prove all the work from all 1,800 blocks with just

• one piece of data?

• AUDIENCE: Well you know that for each block, 2 to 33,

• work had to go into it.

• So you just need to know the number

• of blocks produced times the--

• PROFESSOR: OK.

• Yeah, so the thing is how do I prove the number of blocks

• without showing all of them, right?

• So OK, it's a weird trick question.

• Andrew-- I think--

• I remember Andrew Miller, who's now a professor at somewhere,

• Cornell?

• in the bitcoin forums.

• What you do is you just show the luckiest block,

• and I have not yet defined luckiest block.

• But in this case, it was mined by turtle.

• This is the block, the previous block reference was of 0065a2

• turtle 1654244 and the hash of that block is 000c49a414 blah,

• blah, blah.

• that you can see?

• It's not--

• AUDIENCE: [INAUDIBLE]

• PROFESSOR: What?

• AUDIENCE: It's better than...

• PROFESSOR: It's better.

• There's more work.

• So we didn't count the things as having more or less work just

• by a sum number of zeros.

• We just looked at the threshold, did it have enough 0 bits

• and accepted or rejected.

• But in this case, these 4 bytes, right?

• You needed 4 bytes and then 1 extra bit.

• You needed 33 bits.

• So these 4 are always worth 0.

• But then in c and red, there's another extra byte

• that's all 0s.

• And another extra half a byte that's all 0s.

• And then a c means for that nibble,

• that the highest bit was 1, right?

• So you've got this red stuff.

• There's a byte and a half extra-- or almost a byte

• and a half extra.

• So, yeah.

• So what you can do for a compact proof work.

• So if you look at this again, there's 4 green bytes, byte

• and a half is red, right?

• So that's 5 and 1/2 bytes, so 44 bits.

• And 2 to the 44 is 17 trillion, right,

• if you do out 17 something, which is what we expect,

• that's our proof, right?

• We did 16 trillion hashes for our calculation,

• and it shows up here.

• And another way to look at it is we needed 33 bits

• for a valid block.

• We have 44 bits here.

• That's 11 bits extra.

• That's 11 bits of being lucky.

• And so that's 11 bits to the 11, that's

• 2,048, which is pretty close to the 1,862

• that we actually performed, right?

• So in this case, we're a little lucky.

• We might have only had 2 of the 10

• and then we could only prove that we'd

• done like 8 trillion work instead of 16 trillion work.

• So there's probabilities here, but this

• is an interesting property that actually does work.

• You can prove all the work, to some approximation usually

• within a factor of 2, that the system has ever

• done just with 1 block header.

• So, yeah.

• This is fun because another way to look

• at it is that you've got this metagame,

• where for every block found, take the, I'm doing a hash

• and I need to find a hash with a lot of 0s

• to prove that I've done work.

• And you go a level deeper and say, OK, I'm finding a block.

• And I want to prove that I found an even better block

• than everyone else, right?

• The entry for admission here is find a valid block.

• And then from those blocks, since it's

• a uniform distribution with 1s and 0s,

• you're going to have this tail-end of like, happened

• to have lots of 0s that you didn't need in the beginning.

• And that can prove all the work ever done.

• There's a really interesting paper called, HyperLogLog,

• that uses this for non-bitcoin applications

• that uses it for set counting.

• Where, like on a website, you want to see how many

• unique visitors you've gotten or something.

• And you can store that in 0 of 1 space

• because you could keep track of OK,

• let me keep track of every IP address that's ever visited

• or something like that, or cookie.

• But instead, you hash them.

• See if the hash starts with a bunch of 0s

• or any arbitrary character, and then just store the lowest.

• And then, every time someone visits, hash it, compare.

• If it's lower, replace.

• If not, ignore.

• And then you have a very compact indication

• of how many visitors have visited.

• Anyway, that's like a super high-level view of it.

• But if you're interested in this stuff, HyperLogLog is a paper.

• It builds off of some other things.

• It has nothing to do with bitcoin,

• other than this property, where you've got this random function

• and you see how many 0s are in it.

• But I think these are cool, and so to me, this is a fun--

• this is not used in bitcoin, right?

• but people have written papers about how you could use it.

• If long term the headers are big, you could prove.

• Have some checkpoint, where look,

• I proved all the previous work and now I build from there.

• Yes?

• AUDIENCE: It's not really a proof.

• It's just a probability weighted.

• PROFESSOR: Yes, but the proof of work itself is the same.

• Not of real proof because you might have gotten lucky.

• So finding a block, it's like, well that's not a proof.

• There could be luck involved, there could be probability,

• but it's the exact same luck and probability

• that the underlying proof of work uses.

• So there's no further reduction in security or certainty

• because of this.

• Not really.

• a few years ago and saying, yeah proof of work is a misnomer.

• It's not really a proof, right?

• Maybe it's an argument of work or some probabilistic argument

• of work.

• How could you make it more certain as a proof?

• There's a bunch of ways.

• One way would be to have multiple nonces, where

• instead of just finding one nonce that satisfies it,

• you have to find several replaceable nonces

• and then iterate through them.

• That would be a much more certain proof.

• It would remove the idea of probability, to some extent.

• It would also completely break the system

• in a way that's like fairly unintuitive,

• and so I always was sort of joking like,

• I should make an altcoin, where you've got multiple nonces,

• and you could be like, yes, for more security and then people

• would buy it, but it completely breaks.

• The completely broken incentives and system, maybe I'll get to--

• I'll let you guys think about it til Wednesday,

• and then draw it out and be like, why wouldn't this work?

• It's fun.

• It breaks in subtle but bad ways.

• This is talking about proof of work optimization.

• So if you look at this slide anyway,

• you've got these headers or blocks

• or whatever we're mining.

• So you've got kezike17, tomriddle, Thalita,

• all these people mining.

• It's interesting to see what people use.

• Some people use looks like base64,

• some people just use a decimal number,

• all sorts of different things.

• Who knows.

• There was also a lot of invalid blocks

• with valid work submitted, where there

• was four or five different things in my spaces.

• So there's been count, but actually a lot

• more work was done, and that's not even

• counting the human work of doing all these assignments.

• So sending this over the wire, or storing it on disk,

• some inefficiencies may jump out at you.

• What do you think you could do to make this more efficient

• or compress it or?

• Yeah?

• AUDIENCE: [INAUDIBLE]

• PROFESSOR: OK.

• That's an easy one.

• Oh, this doesn't work when I gave you

• the slides because you can just look at the next slide.

• Whoops, OK.

• Never mind.

• Yeah, so the first 8 characters are always

• going to be 0s by definition.

• If it's not, it's an invalid block

• so don't even bother sending it.

• So the first characters are 0, don't send them over the wire.

• Just have that implied and just start at the ninth character.

• That saves, well, really you'd have the serializing binary,

• so it only saves 4 bytes.

• In our case, it would say 8 bytes.

• That's cool.

• And then, also the entire previous hash.

• When you're sending a list of 5 here, like here, in order

• for it to be valid, this has to be

• the hash of the line above it.

• So just don't send the whole thing, right?

• Just send name nonce.

• The hash is also computable from anyone receiving it.

• That takes almost all of this space

• and we could compress this entire blockchain

• to just the first line, and that's

• the only full line we need.

• After that, it's just named nonce named nonce,

• and we get rid of 70-something percent of this base.

• That's pretty cool, right?

• Yeah this kind of header optimization

• is also very much possible in bitcoin,

• and it's not implemented.

• It's not done.

• If you want to, you could program it, change bitcoin,

• make a pull request.

• I think-- I mean, we've discussed it,

• and people are like, yeah that'd be cool but, no one's done it.

• So if you want to leave your mark and be like,

• I'm a bitcoin core contributor, and I optimized

• the proof of work propagation system or something