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.

TADGE DRYJA: So today will be some sort of future technologies, future developments that

might not be around yet, but are interesting things to look for.

And if you're interested in researching these kinds of things, you want to make a EmenG

out of this or want to make a-- who knows?

PhD probably is a little overkill for a lot of these things.

But if you're interested in this kind of research, here's some things we'll talk about today--

block slash block filters or committed bloom filters, sharding, accumulators, and UTXO

commitments.

OK, so, first one I'll talk about is block filters.

So I don't think I ever really talked about what a Bloom filter is.

I'm still not really going to explain how they work, but the basic idea, the sort of

high level-- here's the prototype.

Here's the function prototype.

Here's the interface that Bloom filters have.

So you make a filter from a bunch of objects.

And in this case, objects are just bytes, right?

Or some string of bytes.

And Bloom filters usually use hash functions under the hood.

A lot of times, they don't use cryptographic hash functions.

They can use sort of faster functions, where there may be collisions.

But in this case, it's not like a security problem.

So you've got a bunch of objects.

They might be addresses, which are 20 byte pubkey hashes, or your UTXOs, which you can

represent as a 36 byte TIXD and out point, or TIXD and index.

So they're small, right?

So either 20 bytes, 36 bytes, sometimes 32 bytes.

You put these list of data objects and make a filter, and you get a filter out.

And the filters are usually a kilobyte sometimes.

But the idea is it's sort of a mix of hash functions.

And then you say, OK, I want to match filters.

Usually, a different person does this and says, OK, I've got a filter that someone generated.

And I compare it against this object and see if there's a hit, all right?

So I see, OK, that matched.

This object matched the filter, or this object did not match the filter.

And this returns a true or false.

And so what's interesting about these is you can have false positives.

So it may be that this object was not in here.

It was not used when creating the filter, but it still returns true.

So it's sort of matching against multiple different hash functions, seeing, hey, do

any of these bits match?

And it says, oh, yeah, this object may have been in this filter.

However, there's no false negatives.

So if you did put, say, address A into this filter and then matched this filter against

address A, it would always return true.

There's no way you can put something into the filter, and then it doesn't show up when

you try to match against it.

So this is useful for lots of things.

Bloom filters are definitely not restricted to cryptocurrency, Bitcoin, or anything like

that.

They're used all the time in various databases, all the time in things like that.

The current way they're used in Bitcoin is for SPV filtering.

So we defined SPV, like, months ago.

The basic idea is I'm a client.

I don't want to download and verify the whole blockchain.

I want someone else to do that.

I assume the miners are doing the right thing.

I assume the rest of the network is doing the right thing.

And I just want to know about my data.

So I'm not going to download the whole block.

I'm not going to verify all the signatures or keep a UTXO set on my own.

I'm just concerned with my UTXOs in my wallet.

So what I do-- and this exists today.

You can do this.

You make a Bloom filter of all your UTXOs and addresses.

So you say, OK, here's all my addresses that I'm hoping to receive money on.

I've got 20 of them, 30 of them, 100 of them-- however many-- although Bloom filters don't

really work once you have too many.

But so the idea is if you have five addresses, let's say, you start a wallet.

You don't have any money.

You're pretty sure you don't know of any money yet existing.

But you say, OK, I made five addresses.

I told these addresses to people.

They might have sent me money.

That'd be nice.

So you make a Bloom filter of all these addresses, right?

So let's say you've got, OK, address A-- dot dot dot-- A through E. And you make a filter.

OK, so you say I've got my filter F. I then send that filter F to a remote server.

So there's the cloud.

There's some Bitcoin full node out here.

It receives filter F. OK, so this got filter F. And it knows that this filter F is specific

to me, right?

So it sees that, hey, I'm a client.

I'm an SPV client.

I connect to a full node, and I say, hey, I sent a message that's called load filter.

And I say, hey, load filter, here's my filter F. Only send stuff to me that matches this

filter.

99% of all the whole thing-- everything going on in Bitcoin, I don't care about.

Here's a filter, and only send me messages that match this filter.

And so when it sends a transact-- well, they send INV messages, right?

When it sends an INV message with inventory, saying, hey, I found this thing that you might

be interested in, normally, a full node to another full node-- so let's say there's communication

between two full nodes, Full2.

These guys will talk to each other about every transaction they see, right?

So if they see a transaction, it's valid.

There's nothing wrong with it.

They'll just send it to each other to propagate transaction throughout the network, so they

can get mined later.

However, if a filter has been loaded, it says, oh, OK, I will only send you INV messages

that match this filter.

So if there's a transaction that doesn't have any of these five addresses as an output,

they're just not going to send it to you.

Similarly, when a block comes out-- this is the big one.

Normally, blocks get propagated the same.

They just send you the block.

Here, we do something called a Merkle block.

I don't send you a regular block.

I filter everything within the block and send you only the things that match to that filter.

So generally, it gets very small.

So the Merkle block might just have one transaction in it.

And it has the sort of Merkle proof up to the root.

So the server sends only the matching transactions in the block, which can drop from a megabyte

to less than a kilobyte.

And then the client says, oh, cool.

There's a transaction where I received money.

Great.

Also, let me update my filter to include this new transaction that I received.

So if that gets spent later, I want to know about it, even if it doesn't send to one of

these five addresses, right?

So if you're only matching on addresses, you can only sort of get money.

But if you're matching on these UTXOs, you can lose the money as well.

And you don't want to lose money, but you sort of want to know when everyone else thinks

you lost money.

So this works today.

This was implemented 2012-ish.

The history behind it was the first Android Bitcoin wallet.

Andreas Schildbach wrote it, and it didn't do this, right?

It just downloaded the whole block and then threw away most of the data and only kept--

it wasn't a full node, and then it didn't keep a UTXO set.

But it did download everything.

And then they were saying, OK, this is really slow.

We want a decentralized way to do this kind of thing, where instead of just connecting

to a server-- so the other model I explained, again, weeks ago was, you just have some server.

And you tell it the address and say, hey, here's my address.

How much money do I have?

And it sends you transactions, and you maintain your wallet that way.

This is nicer because it's decentralized, right?

Every full node can do this.

And by default, if you download Bitcoin 0.16 or whatever recent versions-- not even recent--

since like 0.7?

I don't know.

Most of the versions will have this capability, where if a client says, hey, here's a Bloom

filter.

Load it.

Your full node will load that filter.

And then every block that comes in or every block that's requested, they will match against

the filter.

The filter match function call's not too heavy.

It involves a bunch of hash functions.

It's not too slow, but it's slower than doing nothing, right?

It's slower than just sending it directly.

OK, so this is nice, right?

You can sync the entire chain in way less data and having SPV security.

Problems-- it's really bad for privacy.

You're sending a Bloom filter, right?

So it's this thing that's created from your list of addresses.

But in practice, it's got about the same security as just telling them all your addresses, right?

So it's sort of like, oh, I'm sending a hash of my address, instead of my address.

Well, yeah, but I know all the addresses in existence on the Bitcoin network.

I can just try to match it, try to hash and stuff like that.

When you do Bloom filters, there's this sort of false positive rate that's sort of a knob

you can twist.

And you can say, oh, I'm going to make a Bloom filter where 10% of the time, when you perform

this match filter for any given object, I'm going to create a filter where 10% of the

time, it'll just return true.

So I can dial in a false positive rate.

So I can say, OK, I'll make it 1%.

And then when I get these matching transactions from the full node, yeah, I'll get an extra

few transactions that don't match my filter.

Or they match my filter, but they don't actually match anything I'm looking at.

And that will improve my privacy, right?

Because then the full node doesn't see what's-- he doesn't know what's truly mine.

In fact, you don't even know what the false positive rate is.

When you receive a filter, you don't know what the false positive rate is.

You just see, OK, these things match, and you send them.

Another strategy is OK, I'm a SPV client.

I connect to a bunch of full nodes, and I can give different filters to each one.

I think the initial software did this.

And because you can sort of put some randomness into your different filters to hope-- why

did they do this?

It actually makes it worse.

It actually makes it worse because if these full nodes collude-- collaborate-- whatever.

If these full nodes share the information of the filters, it makes it easier to determine,

to sort of filter out the false positives.

Because they'll have different false positives because they had a different filter.

And so if they collaborate, if they work together, they can say, oh, well, I got some false positive

transactions.

I did, too.

We can filter out the ones that one of us had as a false positive and not the other,

right?

So we can detect the false positives we're sending to the client.

So privacy is really bad.

There's a paper written I think 2013 or 2014, where they basically broke the whole privacy

argument for this Bloom filter based SPV.

And they said in practice, you can get like 90 something percent of the addresses and

UTXOs that people are sending for the software.

And their recommendations were like, yeah, I don't see how you make this work privately.

There's just no privacy here.

It's slow for the servers, so when you're running-- I don't know if you can see.

When you're running a full node-- OK, I should close that.

Don't even know what that is.

When you're running a full node, you can see here's all the nodes that are connected to

my full node and running downstairs.

Most of them are other full nodes.

Oh, OK, these are not.

I don't know what those are.

Those are not true.

All these 0.9, 0.99s, they're not actually nodes at all.

They don't seem to ask for anything.

And then some people put their version message.

They put an address.