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.

ALIN TOMESCU: My name is Alin.

I work in Stata, in the Stata Center.

I'm a PhD student there in my fifth year.

And today we're going to be talking about one

of our research project called Catena.

And Catena is a really nice way of using bitcoin

to build append-only logs.

Bitcoin itself is an append-only log.

And a lot of people have been using it to put data in it.

And I'll describe a really efficient way

of doing that and its applications.

And if there is time, we'll talk about a tax and maybe colored

coins and some other stuff.

We'll talk about the what, the how and the why.

And that's the overview of the presentation.

So let's talk about this problem called the equivocation

problem.

So what is this?

In general, non-equivocation means saying the same thing

to everybody.

So for example, if you have a malicious service

and you have Alice and Bob, the service

should say the same thing to Alice and Bob.

So it would make a bunch of statements.

Let's say s1, s2, s3 over time and Alice and Bob

would see all of these statements.

So this is very similar to what bitcoin provides, right?

In bitcoin you see block one, block two, block three.

And everybody agrees on these blocks in sequence, right?

Does that make sense?

So this is non-equivocation and in some sense

this is what bitcoin already offers.

And in general with non-equivocation,

what you might get is some of these statements

might actually be false or incorrect.

Non-equivocation doesn't guarantee you

that this statement is a correct statement.

But it just guarantees you that everybody

sees the same statements.

And then they can detect incorrect statements.

In bitcoin you get a little bit more.

You actually know that if this is a block,

it's a valid block, assuming there are enough blocks on top

of it, right?

So equivocation means saying the same thing to everybody.

So for example, this malicious service at time four,

he might show Bob a different statement than Alice.

So Bob sees s4 and Alice sees s4 prime.

This is what happens in bitcoin sometimes.

And that's how you can double spend in bitcoin

by putting the transaction here sending money to the merchant,

and then putting another transaction

here sending money back to you.

Right, are you guys familiar with this?

Yeah, OK.

All right, so why does this matter?

Let me give you a silly example.

Suppose we have Jimmy and we have Jimmy's mom and Jimmy's

dad, right?

And Jimmy wants to go outside and play.

But he knows that mom and dad usually don't let him play.

So what he does is he tells dad, hey dad,

mom said I can go outside.

Right, and then he tells mom, hey mom.

Dad said I can go outside.

And let's say mom and dad are in different rooms

and they're watching soap operas and they're not

talking to one another.

So they can actually confirm that.

You know, mom can confirm that dad really said that.

And dad can really confirm that mom said that.

But they both trust Jimmy.

So you see how equivocation can be really problematic

because now mom and dad will say sure,

go outside as long as the other person said that, right?

But let me give you a more practical example.

So let's look at something called a public-key directory.

A public-key directory allows you to map user's public keys--

a user name to a public key.

Right, so here I have the public key for Alice

and here I have the public key for Bob.

And they look up each other's keys in this directory.

And then they can set up a secure channel.

How many of you guys use Whatsapp, for example?

So the Whatsapp server has a public-key directory.

And when I want to send you a message,

I look up your phone number in that directory

and I get your public key, right?

If that directory equivocates, the following thing can happen.

What the directory can do is it can create a new directory

at time two where he puts a fake public key for Bob

and he shows this to Alice, right?

And at time two also, he creates another directory for Bob

where he puts a fake public key for Alice, right?

So now the problem here is that when

Alice checks in this directory, she looks at her own public key

to make sure she's not impersonated.

And Alice looks in this version and sees, OK.

That is my public key.

I'm good.

She looks in this version, OK.

This is my public key.

I'm good.

So now I'm ready to use this directory.

And I'll look up Bob and I'll get his public key.

But Alice will actually get the wrong public key.

Does everybody see that?

And similarly Bob will do the same.

So Bob will look in his fork of the directory, right?

And he looks up his key here and his key here.

And he thinks he's OK.

He's not impersonated.

But in fact, Alice has impersonated there.

OK?

And now as a result, they will obtain fake keys

for each other.

And this man in the middle, attacker

who knows the corresponding secret keys

for these public keys can basically

read all of their communications.

Any questions about this?

This is just one example of how equivocation

can be really disastrous.

So in a public-key directory, if you can equivocate,

you can show fake public keys for people

and impersonate them.

So in other words, it's really important

that Alice and Bob both see the same directory.

Because if Bob saw this directory,

the same one Alice saw, then Bob would notice that this is not

the public key he had.

He would notice his first public key and then

that there's a second one there.

And then he would know he's impersonated.

And he could let's say, talk to the New York Times,

and say, look.

This directory is impersonating me.

So in conclusion, equivocation can be pretty bad.

So this idea that you say different things

to different people can be pretty disastrous.

And what Catena does is it prevents that.

So in general, if you have this malicious service that is

backed by Catena, if it wants to say different things

to different people. it cannot do that.

It has to show the same thing to everybody.

And the way we achieve that is by building on top of bitcoin.

And that's what we're going to be talking about today.

So any questions about sort of the general setting

of the problem and our goals here?

So let's move on then.

So why does this matter?

So this matters for a bunch of other reasons,

not just public-key directories and secure messaging.

It matters because when you want to do secure software update,

equivocation is a problem.

And I'll talk about that later.

So for example, at some point bitcoin

was concerned about malicious bitcoin binaries

being published on the web and people

like you and me downloading those binaries

and getting our coins stolen.

Right, and it turns out that that's an equivocation problem.

Somebody is equivocating, right?

It's equivocating about the bitcoin binary.

It's showing us a fake version and maybe

other people the real version.

Secure messaging, like I said before,

has applications here and.

Not just secure messaging but also the web.

Like when you go on Facebook.com,

you're looking up Facebook's public key.

And if somebody lies to you about that public key,

you could be going to a malicious service

and you could be giving them your Facebook password.

Does that make sense?

And also it has applications in the sense

that if you have a way of building a append-only log,

you really have a way of building a blockchain right

for whatever purpose you want.

And we'll talk about that as well.

So the 10,000 feet view of the system

is we built this bitcoin based append-only log.

And the way to think about is that bitcoin is already

an append-only log.

It's just that it's kind of inefficient to look

in that log.

If you want to pick certain things from the Bitcoin

blockchain, like you put your certain bits and pieces of data

there, you have to kind of download

the whole thing to make sure you're not missing anything.

And I'll tell you why soon.

So instead of putting stuff naively

in the Bitcoin blockchain, we put it

in a more principled way.

And in a sense we get a log and another log.

We get our log and the bitcoin log.

And this generalizes to other cryptocurrencies.

Like you could do this in light coin,

for example, or even in ethereum.

Though I don't think you guys yet

talked about how the ethereum blockchain works.

And the cool thing about this Catena log that we're building

is that the Catena log is as hard to fork as the bitcoin

blockchain.

If you want to fork our log, you have to fork bitcoin.

However, unlike the Bitcoin blockchain,

Catena is super efficient to verify.

So in particular, remember, I described the log

in terms of the statements in it.

So if you have 10 statements, each statement

will be 600 bytes to audit.

So you don't have to download the whole Bitcoin

blockchain to make sure you're not missing a statement.

And you also have to download 80 bytes per bitcoin block.

And we have a Java implementation of this.

And if you guys are curious, you can go to my GitHub page,

and take a look at the code.

All right, so before we start, I know you guys already

know a lot about how the Bitcoin blockchain,

but it's important that I reintroduce some terminology

just so we're on the same page.

So this is the bitcoin blockchain.

We have a bunch of blocks connected

by hash chain pointers.

And we have Merkle trees of transactions.

And you know, these arrows indicate hash pointers.

It means that block n stores a hash of block n minus 1 in it,

right?

So in that sense.

Block n has a hash pointer to block n minus 1.

All right, and like I said, each tree has a Merkle tree.

Each block has a Merkle tree.

And everybody agrees on this chain

of blocks via proof of work consensus, which all of you

already know.

And importantly, in the Merkle trees, we have transactions.

And transactions can do two things.

Right, a transaction can mint coins, create new coins.

So here I have transaction a.