Hacker News Reader

Hacker News

Comment by mtrimpe | Hacker News Reader

Parent Full thread

mtrimpe

Not to mention that the any ability to do proper range queries would offer relatively easy ways to hack the encryption.

I've been thinking a lot about this and the only way to handle the problem this tries to solve is to:

* treat the database as a collection of events

* let each event have a visibility that matches our concept of privacy (public | shared with X, Y & Z | private)

* have this communication encrypted using already existing OTR protocols (see some of Moxie Marlinspike's posts on it)

* make the database queryable on this aggregate of event data.

It's really just a case of finding the essential complexity and making it as simple, but not simpler, than that.

The annoying thing is that while it's a tough bullet to bite; it's not even that though. Something like Datomic could already get you halfway there.

View on HN

You've probably seen CryptDB from MIT. They make it possible to do certain types of queries (range etc) by making security compromises (giving some clues to hack encryption).

We don't make such compromises (zero compromises, yes!). The way we do it is to actually traverse encrypted b-trees from the client, while b-trees are on the server. So, we pretty much split it between client and server at the lowest level of how db operates

Doesn't that reveal information to the server based on which B-trees the client accesses?

Ops, I thought I'm responding here.

The server actually knows which pieces of B-Trees you access. But no more than that.

If it knows what pieces you access, how do you prevent the sever from learning ordering?

It knows the ordering of the encrypted data, but it doesn't know what the data is.

That seems like it reveals exactly the same kinds of information that range queries reveal.

How is that different than cryptDb then? CryptDb only reveals ordering as well (and only if the client requests it.)

Well, actually the server doesn't know the ordering and how pieces of B-Tree refer to each other, it doesn't even know which data form the index and which are the actual data.

Though, observing access patterns, it could probably deduce which data belong to the tree and some info about ordering (which will hold true until we re-balance the tree, which happens on inserts).

I think, if we change objects each time we do queries, we can prevent this data leak.

The net effect here is that each client must lock the database on insert.

A client can batch multiple inserts but the server cannot batch inserts from multiple clients.

No; each data producer (customer/person/identity) has their own serialized (as in ordered) queue of events.

Since the system is fully immutable each update would also include the state of the system it is an update to (which can be outdated.)

Essentially you're modelling human communication with each event being equivalent to a human speech act.

For most cases that would offer sufficient conflict resolution and more expensive commit strategies could be used only where more needed; much like how lattice/CALM-based programming languages such as Bloom deal with distribution.

I don't think there is a free lunch here.

Yes immutable data makes the inserts O(1) but increases the query costs proportionally to the number of producers.

You need to traverse all possible systems states to do a complete lookup.

Encryption also makes server side pruning and garbage collection of old system state difficult unless you just clear everything greater than n days old.

I'm not at all arguing there's a free lunch here. It's a tough cookie to crack and requires a reimagining of half of computing. I also think it's the only possible way to go.

1) As for the query costs; yes they are there. For public data you could still create pre-computed indexes but for privately shared data the recipients/accessors of that data would need to create appropriate indexes.

In general this scheme indeed requires each producer (person/identity) to also maintain their own indexes.

2) I don't get what you mean by doing a complete lookup.

3) Since this would be a fully federated/decentralized system there would not really be such a thing as server side pruning since the 'server' would just be a peer that indexes public data.

Given that data is immutable clients would simply hold on to the data they need for their calculations and could choose to depend on the server to keep a copy for them.

If nobody (wants to pay to) hold onto a copy of some data anymore then it has been garbage collected.

P.S. Have you looked at the Datomic model? It works quite similar to this proposal with regards to things like storage, peering, computing indexes etc.

Reply on news.ycombinator.com