Commons license.

Your support will help MIT OpenCourseWare

continue to offer high quality educational resources for free.

To make a donation or to view additional materials

from hundreds of MIT courses, visit MIT OpenCourseWare

at ocw.mit.edu.

PROFESSOR: Sorry.

I have a bit of a sore throat, hoarse voice.

I was talking a lot this weekend.

OK.

Also, today we're going to do transaction malleability,

segregated witness, and I'm endorsing

an ICO for the first time ever publicly,

and it's Anne's intermittent cookie offering.

So if you guys want cookies.

It's an airdrop and you just get them.

so it's my first ICO I'm endorsing.

OK.

So malleability.

So malleability is the ability to deform

under pressure formateer.

And so bitcoin is modeled off of gold, which

is the most malleable metal.

You can make gold leaf and stuff.

So clearly we need to design bitcoin to be malleable.

No, I'm joking.

OK.

Actually in the context of cryptography,

it's not super hard definition, but it

started with Cipher text, where if you can modify a Cipher

text and that modification will carry over into the plain text

when it's encrypted.

It also applies to sort of messages and signatures.

In our case, signatures can be malleable,

which means you can change the signature

and it's still a valid signature.

So given a signature S1 on message M1,

you modify the signature to S2 or S prime

and it still signs the same message.

It still validates as true.

So when we were defining signatures

this wasn't really an attack we'd considered.

There's still a signature and you can't forge a signature,

but you can dot an I or something

and the signature is slightly different.

You can't create one yourself, but given a valid signature

you can make a slightly different valid signature.

And that's how it works in the bitcoin signing algorithm.

But there's all sorts of different contexts

where malleability exists in cryptography.

And then part of it is things still

have to work for whatever definition.

So if you malleates a signature and it no longer validates,

well, that's sort of a trivial, like--

yeah, sure, you can do that to any bunch of bytes.

You can just flip some of them and the whole thing

doesn't work anymore.

That's easy.

But properties where it still works.

So this leads to some weird stuff in bitcoin

where you can change a transaction

and it's still valid.

And that's generally not what you want.

If you've got some kind of contract

or some kind of payment and you write a check,

you don't want someone to be able to modify the check

and still be able to cash it.

And I don't really use checks much, but they draw the line.

Like $100 and then they draw a line

so someone doesn't write and $0.99 or something after.

Not that that's like the greatest attack ever.

Or $100 and then someone puts like $1,000.

I don't know.

But it's sort of like that where someone

can change the thing you sign, can

change the thing you are agreeing to after the fact,

and it's still valid and it does something you don't expect.

OK.

So a review of the transaction format,

which should be probably in people's minds

if you were looking at the homework, the problem set.

And one thing to focus on is that the outputs

don't look like the inputs.

These are fundamentally different things.

The outputs specify a transaction ID and the inputs,

and then the outputs specify a script and an amount.

There's another 4 byte field here that doesn't matter.

So basically you're spending from a transaction and a sort

of row and you're spending too just this arbitrary pub key,

but you're not spending from a pub key

and you're not spending to a transaction.

You don't identify your transaction itself here.

Almost every website that shows blockchains is it

gets this wrong.

So if you look at like, I don't know,

blockchain.info is probably the most popular

and you just look at a transaction.

They don't have it anymore.

OK.

So you look at a block and then you look at a transaction

in the block.

We're going.

No.

No.

No, not yet.

There we go OK.

So you look at a transaction.

Yeah, it shows.

This address is sending to these two addresses.

And blockchain.info is particularly egregious

and that there may actually be more than one input and two

outputs in this transaction.

They hide change transactions.

So it looks like, hey, this address had some money in it

and it sent it to these two addresses.

And if I click, oh, where did this money come?

It come from 18eecz, and it shows

here's the bitcoin address, and, oh, it's

got multiple transactions this addresses has been involved in.

This is not how bitcoin works.

They are running their own database and sort

of making up this view of the network, which is incorrect.

Transactions don't send from an address,

they send from another transactions previous output.

And this is very confusing because in the case,

let's say in this transaction, there is a--

what is it?

767 something.

So it says, yeah, it's coming from 18ee whatever,

and if I click on it I get three different transactions.

There is a specific transaction that 18ee

was involved in that is being spent from in this transaction.

I can look it up because I have an actual full node.

So if I say get raw transaction and I put it in here

and I can see, OK, it was spending from c838.

It was spending from this transaction, not just

an address.

So I mean if you're coming at this sort of new it's like, OK,

fine, why do you keep talking about this?

But if you've been working on these things, a lot of people,

myself included, for like six months a year

I looked at these websites and I'm like,

oh, this is how it works and then six months in or something

looking for code, and I'm like, wait, huh?

This code is wrong, but no, this is the bitcoin code

that actually is running.

And so it's a weird thing to sort of get used to.

Like no, you're not spending from an address.

You don't show the address at all when you spend from it,

you spend from a specific output.

OK.

So that leads to some weird issues.

Specifically, what gets signed?

So to some extent you're signing the whole transaction.

You sign.

You want to sign everything.

When you're saying I'm sending money from here,

I'm sending it to here, you want to make sure

that your signature covers the entire transaction so

that people can't add stuff after or remove stuff.

So you want to sign the inputs and outputs.

But the inputs contain signatures

and you can't sign the signature.

That doesn't make any sense.

The signature is the thing you're putting on at the end.

So it's sort of weird.

You've got this document and you have a little line

at the bottom for the signature.

But should the signatures be maybe a separate page that

refers to the previous page?

It's actually kind of a weird confusing problem.

So in practice, in bitcoin, what Satoshi did in 2009,

you take the whole transaction, but you

remove the signature fields.

You basically zero them out.

Just put a zero there and then you

sign that sort of signatureless transaction.

And then you put that signature in after the fact.

And so that means if you change any bit of the stuff that gets

signed other than the signature, the signature will break.

So does that make sense?

You have these empty lines kind of,

and the idea is you empty them out, you make them blank lines,

and then you take that whole message, hash it, including

the empty parts, and then paste in those signatures

after you've signed.

You don't empty out every line, the line that you're

specifically putting the signature in,

you actually put a different few bytes

in there, which leads to other problems

that I can maybe mention if I've done.

So this seems OK.

It's like well, look, I can't sign the signatures, sure,

but if you change any bit of the stuff I'm signing,

the signatures now break.

So this seems perfectly safe.

No one can change the amounts I'm sending.

No one can change where I'm sending it to.

No one can change where I'm sending from.

All these things get covered in my signature, so I'm good.

Problem.

The transaction ID, the way you refer to transactions

is the hash of the whole thing.

The txid does not zero out the signature fields.

So the identity of the transaction itself, the way

to point to and indicate where you're spending from,

that includes the signatures.

So that also seems like, well, that's OK.

When I point to something I'm indicating

the whole transaction, the whole signed transaction.

But the problem is that can change.

The signature itself may be malleable,

and in bitcoin it is.

There's third party malleability problems.

So the simplest one was leading zeros

where all these things are numbers.

You could say, OK, someone's got a signature.

It's this big, long string of bytes.

I'm just going to put zeros in the front.

I'm going to put a zero byte in the front of it,

and that doesn't change the meaning.

If someone says, I'm sending you $1,000

and I put a 0 front of the one and 1,000.

Well, it's still 1,000.

However, for the purpose of a hash function,

if you have a zero byte in front,

that changes the whole hash.

And so they got rid of this pretty early.

They sort of made it so that you had

to have the exact right number.

You can't have any leading zeros.

But the first one was just, oh, I put a 0 in the front.

The harder one is called low s, where part

of the ecdsa signature scheme.

I showed before that it's this curve that's

symmetric about the x-axis.

Whether the thing you're indicating

is on top of the curve or it's sort of reflection

on the bottom, it's valid either way.

So for any given signature, there's

another signature that will be valid.

You just sort of flip it, make it negative or positive.

So now there's a standard, OK, you need to have high s.

Low s signatures should be invalid.

Both of these are really tricky because they're

third party malleability.

Anyone can just listen on the network, see a transaction,

change the signature.

And in doing so they will change the txid,

which is how all the software refers to transactions.