6 ms·

ZeroDB – A Peek Under the Hood

56 points by mwilkison 12y ago

taariqlewis 12y ago
Nice follow-up ZeroDB. Looking forward to the beta!
swswsw 12y ago
good to see that you are adding more info about how it works. please keep posting more info. sounds like an interesting technology.
bojo 12y ago
How does this work without exposing the client keys in server memory? You still need to send the server your private key to query and decrypt data you specifically didn't make via other connected clients, right? Edit: I phrased that wrong. How do you usefully query other user's data with only your keys?
- michwill 12y ago
  Nope, query logic happens on the client, so server doesn't know the key. Client is the one who records data and indexes encrypted, and who uses indexes from remote.
  - bojo 12y ago
    Which doesn't sound very scalable at all. What is the use case for this?
    - michwill 12y ago
      It is scalable enough because you need to download log(index_size) rather than full index. The use case - any private data which you'd like to encrypt on the server while preserving ability to search. Medical records, financial data, emails are some examples. Easier to say what this database is not for. Big data applications where you need to use a significant portion of data in the db (like 10%) in map-reduce queries is probably not what ZeroDB would be practical for.
      - bojo 12y ago
        I appreciate the answers. I'm genuinely curious because I've contemplated such a database on the side but could never see my way to the goal. The final outstanding question I have though is: How do you deal with data you aren't the owner of? Is this strictly targeted at scenarios where you are the sole owner?
        michwill 12y ago
        Good question. We thought about two cases. One is when your are sole owner of the data. The other is when the owner of the data is some group (like JP Chase). In this case we can have server-side quotas for handling cases when one or several clients are compromised. So, in this case it's more about distributing trust
bkeroack 12y ago
Interesting that it's built on ZODB. For those that aren't familiar, in essence ZODB gives your Python application a 'magic dictionary' which automatically persists any keys written to it. It was probably my ignorance, but while I thought the concept was interesting I ultimately abandoned using it since I couldn't find any out-of-band way of inspecting saved data. Eg, sometimes you want to run some ad hoc SQL to see what is stored in a relational database but the only way to access data in ZODB (AFAICT) is within the application itself. It looks like ZeroDB abstracts away these issues, luckily. Is it intended to be a full-scale application data store, or something more specialized like a secrets store?
- michwill 12y ago
  You're right, good that someone is familiar with ZODB! We plan to make it a full-scale database. For that, we obviously require to have some convenient query language (similar or even compatible with Mongo's). We've talked to original developers of ZODB and they (independently) suggested that having a language-independent query language is something they constantly thought of :-) In fact, it seems like many of them dream to take ZODB (or a db based on it ;-) where Mongo is now.
sbt 12y ago
This is a very exciting project, but since the use cases are security related, I am hesitant to use a closed source project. Are there any plans to open source this?
- mwilkison 12y ago
  Yes, we plan on making this open source.
jdub 12y ago
Closed source database? Good luck with your acquisition!
- deleted 12y ago
  [deleted]
bmh100 12y ago
Do you have any comments on using this technology for (1) health information and (2) financial information?
- mwilkison 12y ago
  We think it could be very useful in verticals that need to comply with privacy regulations or store otherwise sensitive data (healthcare/HIPAA, education/FERPA, finance). We're in the process of exploring specific use cases, so we'll have more precise examples for you soon.
pjc50 12y ago
"The server doesn’t know how individual objects are organized within a tree structure, or whether they even belong to a tree structure at all. ... When a client performs a query, it asks the server to return buckets of the tree as it traverses it, in a just-in-time fashion" The server can however infer quite a lot from the order of bucket request, especially which buckets constitute a tree.
- michwill 12y ago
  Yes, we think about it. This information is not rock-solid and changes with time as the tree re-balances. But for ultimate security, I think, we need something like a proper Oblivious RAM protocol
siscia 12y ago
I definitely miss something, but... How it is different from a simple mongodb where I store encrypted documents ?
- michwill 12y ago
  With mongodb, you either pass your key along with query or lose your ability to search. In our case, we don't pass the key to the server, yet having the ability to query
  - siscia 12y ago
    Can you explain better how ? And what you mean by "search" ?
    - michwill 12y ago
      For example, full text search over your text queries, or range queries for your numerical data. The idea is that data in databases is organized in B-Trees, so we traverse those from a remote client. It is fast enough because usually only logarithmic fraction of a tree needs to be seen by the client.
      - mapgrep 12y ago
        OK but aren't you thus pushing much of the intelligence typically part of the database server to the database clients? In this case, the "database server" is basically a dumb remote B-tree server, right? It's not running queries of any sort, or maintaining indices? Not putting it down, just clarifying that the structure of this database system is very different. Or appears so, at least.
        michwill 12y ago
        Yes, you are right. The server stores indexes (which are actually trees), but the query logic is on clients.
shanemhansen 12y ago
I've heard nothing but bad things about ZODB. I question the wisdom of building a database on top of a python database.
- the-dude 12y ago
  I agree and I have worked with ZODB. It isn't a database, it is a mediocre persistence ... thingy. You store objects and now your database is tied to your code. Have experienced nightmarrish scenarios when updating codebases.
  - michwill 12y ago
    I consider ZODB as more like a framework for quickly building databases. ZODB developers (we've talked to many of them) consider upgrading objects as no-problem (because they have very well understood patterns for that) etc. While that's ok for Zope/ZODB developers, it's not for an average user. We need to wrap it up to make easily usable, without requiring developers to read tons of documentation and "Design patterns" in advance! And, obviously, some universal json query language is needed
    - the-dude 12y ago
      How are you going to manage querying ad-hoc fields? AFAIK every field within your ZODB-query needs to be indexed in ZODB first?
      - michwill 12y ago
        Indexes are created where you told them to. So, if you include an arbitrary field, it's probably not going to be indexed to start with. And yes, query is for indexed fields. I guess, we can have another type of behavior where all new fields are indexed. It doesn't sound like a "clean way" to me, however some developers could desire that
geoelectric 12y ago
So, if I get this right, ZeroDB ends up being a service to persist (to it) a flat dictionary of encrypted buckets. When a given bucket is requested and decrypted by the client, it will have the data as well as the references that let the client treat them as a B-tree, presumably because the clients put them there? I'm taking that assumption from "The server doesn’t know how individual objects are organized within a tree structure, or whether they even belong to a tree structure at all." What does this mean for adding a node? Does the client have to traverse the whole B-tree (requesting log(n) entries) down to the point of addition? How about rebalancing, etc? It seems like the clients would be wholly responsible for maintaining the tree.
- michwill 12y ago
  You're right, clients will be responsible for inserting data, re-balancing the tree etc.
  - beagle3 12y ago
    Ouch. Now, any memory overrun bug or a hardware memory error in any client can kill index integrity (and possibly data itself, if data is on pages rather than individual objects). I wouldn't run an important database on a server without ECC memory - but ZeroDB doesn't seem to make that an option. Are you addressing this in any way?
    - geoelectric 12y ago
      Well, if the indexes can all be updated with transactional integrity around the whole thing (which I think you need anyway, per thread below about having to do client-side rotates to self-balance the tree and keep log n) in theory this is no worse than a memory overrun/etc. in the original database server. Most fatal errors just mean you lose an entire atomic update, and the type where you "successfully" write bad data imply the same sort of repairs as server-side maintenance would. In practice, I think the biggest issue is that if you had to restore a backup, there'd be no way to restore only -your- tree, since the server doesn't know structure or ownership of the buckets. You'd have to roll back everyone in the bucket store. I don't want to be too negative, because I think having something like this is a good idea. It's plain there are challenges to be solved here though. Edit: though I do catch your point that N clients all maintaining the same index tree is potentially like having a non-redundant N-wide storage array--failure rate is cumulative. Think you could possibly mitigate this with a single-source-of-truth per table/index client-side design, but that's an obvious potential bottleneck.
oh_teh_meows 12y ago
What are the advantages of ZeroDB over a database that uses homomorphic encryption like CryptDB? Do they cater to different uses?
- michwill 12y ago
  CryptDB doesn't use homomorfic encryption. It is doing sortable deterministic encryption. E.g. after encryption the server can determine whether a > b or a == b. They have a very good understanding of what data does it leak, when can you do that and when cannot. In our db, random observer cannot see how data are ordered or whether elements are equal to each other. Homomorfic encryption would be ideal of course, but it is slow and impractical for the moment
  - quizotic 12y ago
    Actually, CryptDB does (or at least did originally) use homomorphic encryption (HE) for evaluating SQL arithmetic expressions. While the earliest suggestions for HE were terribly slow, CryptDB found one that was practical. If memory serves, there have since been HE improvements claimed by IBM and/or Google. But as michwill states (and CryptDB acknowledges), their approach either leaks information or precludes classes of expressions. For example, their order-preserving encryption could be susceptible to a brute-force attack via 'a > b' ... '(a+1) > b' ... '(a+2) > b'

56 points by mwilkison 12y ago

Nice follow-up ZeroDB. Looking forward to the beta!

good to see that you are adding more info about how it works. please keep posting more info. sounds like an interesting technology.

bojo 12y ago

How does this work without exposing the client keys in server memory? You still need to send the server your private key to query and decrypt data you specifically didn't make via other connected clients, right? Edit: I phrased that wrong. How do you usefully query other user's data with only your keys?

michwill 12y ago
Nope, query logic happens on the client, so server doesn't know the key. Client is the one who records data and indexes encrypted, and who uses indexes from remote.
- bojo 12y ago
  Which doesn't sound very scalable at all. What is the use case for this?
  - michwill 12y ago
    It is scalable enough because you need to download log(index_size) rather than full index. The use case - any private data which you'd like to encrypt on the server while preserving ability to search. Medical records, financial data, emails are some examples. Easier to say what this database is not for. Big data applications where you need to use a significant portion of data in the db (like 10%) in map-reduce queries is probably not what ZeroDB would be practical for.
    - bojo 12y ago
      I appreciate the answers. I'm genuinely curious because I've contemplated such a database on the side but could never see my way to the goal. The final outstanding question I have though is: How do you deal with data you aren't the owner of? Is this strictly targeted at scenarios where you are the sole owner?
      - michwill 12y ago
        Good question. We thought about two cases. One is when your are sole owner of the data. The other is when the owner of the data is some group (like JP Chase). In this case we can have server-side quotas for handling cases when one or several clients are compromised. So, in this case it's more about distributing trust

bkeroack 12y ago

Interesting that it's built on ZODB. For those that aren't familiar, in essence ZODB gives your Python application a 'magic dictionary' which automatically persists any keys written to it. It was probably my ignorance, but while I thought the concept was interesting I ultimately abandoned using it since I couldn't find any out-of-band way of inspecting saved data. Eg, sometimes you want to run some ad hoc SQL to see what is stored in a relational database but the only way to access data in ZODB (AFAICT) is within the application itself. It looks like ZeroDB abstracts away these issues, luckily. Is it intended to be a full-scale application data store, or something more specialized like a secrets store?

michwill 12y ago
You're right, good that someone is familiar with ZODB! We plan to make it a full-scale database. For that, we obviously require to have some convenient query language (similar or even compatible with Mongo's). We've talked to original developers of ZODB and they (independently) suggested that having a language-independent query language is something they constantly thought of :-) In fact, it seems like many of them dream to take ZODB (or a db based on it ;-) where Mongo is now.

sbt 12y ago

This is a very exciting project, but since the use cases are security related, I am hesitant to use a closed source project. Are there any plans to open source this?

mwilkison 12y ago
Yes, we plan on making this open source.

jdub 12y ago

Closed source database? Good luck with your acquisition!

deleted 12y ago
[deleted]

bmh100 12y ago

Do you have any comments on using this technology for (1) health information and (2) financial information?

mwilkison 12y ago
We think it could be very useful in verticals that need to comply with privacy regulations or store otherwise sensitive data (healthcare/HIPAA, education/FERPA, finance). We're in the process of exploring specific use cases, so we'll have more precise examples for you soon.

pjc50 12y ago

"The server doesn’t know how individual objects are organized within a tree structure, or whether they even belong to a tree structure at all. ... When a client performs a query, it asks the server to return buckets of the tree as it traverses it, in a just-in-time fashion" The server can however infer quite a lot from the order of bucket request, especially which buckets constitute a tree.

michwill 12y ago
Yes, we think about it. This information is not rock-solid and changes with time as the tree re-balances. But for ultimate security, I think, we need something like a proper Oblivious RAM protocol

siscia 12y ago

I definitely miss something, but... How it is different from a simple mongodb where I store encrypted documents ?

michwill 12y ago
With mongodb, you either pass your key along with query or lose your ability to search. In our case, we don't pass the key to the server, yet having the ability to query
- siscia 12y ago
  Can you explain better how ? And what you mean by "search" ?
  - michwill 12y ago
    For example, full text search over your text queries, or range queries for your numerical data. The idea is that data in databases is organized in B-Trees, so we traverse those from a remote client. It is fast enough because usually only logarithmic fraction of a tree needs to be seen by the client.
    - mapgrep 12y ago
      OK but aren't you thus pushing much of the intelligence typically part of the database server to the database clients? In this case, the "database server" is basically a dumb remote B-tree server, right? It's not running queries of any sort, or maintaining indices? Not putting it down, just clarifying that the structure of this database system is very different. Or appears so, at least.
      - michwill 12y ago
        Yes, you are right. The server stores indexes (which are actually trees), but the query logic is on clients.

shanemhansen 12y ago

I've heard nothing but bad things about ZODB. I question the wisdom of building a database on top of a python database.

the-dude 12y ago
I agree and I have worked with ZODB. It isn't a database, it is a mediocre persistence ... thingy. You store objects and now your database is tied to your code. Have experienced nightmarrish scenarios when updating codebases.
- michwill 12y ago
  I consider ZODB as more like a framework for quickly building databases. ZODB developers (we've talked to many of them) consider upgrading objects as no-problem (because they have very well understood patterns for that) etc. While that's ok for Zope/ZODB developers, it's not for an average user. We need to wrap it up to make easily usable, without requiring developers to read tons of documentation and "Design patterns" in advance! And, obviously, some universal json query language is needed
  - the-dude 12y ago
    How are you going to manage querying ad-hoc fields? AFAIK every field within your ZODB-query needs to be indexed in ZODB first?
    - michwill 12y ago
      Indexes are created where you told them to. So, if you include an arbitrary field, it's probably not going to be indexed to start with. And yes, query is for indexed fields. I guess, we can have another type of behavior where all new fields are indexed. It doesn't sound like a "clean way" to me, however some developers could desire that

geoelectric 12y ago

So, if I get this right, ZeroDB ends up being a service to persist (to it) a flat dictionary of encrypted buckets. When a given bucket is requested and decrypted by the client, it will have the data as well as the references that let the client treat them as a B-tree, presumably because the clients put them there? I'm taking that assumption from "The server doesn’t know how individual objects are organized within a tree structure, or whether they even belong to a tree structure at all." What does this mean for adding a node? Does the client have to traverse the whole B-tree (requesting log(n) entries) down to the point of addition? How about rebalancing, etc? It seems like the clients would be wholly responsible for maintaining the tree.

michwill 12y ago
You're right, clients will be responsible for inserting data, re-balancing the tree etc.
- beagle3 12y ago
  Ouch. Now, any memory overrun bug or a hardware memory error in any client can kill index integrity (and possibly data itself, if data is on pages rather than individual objects). I wouldn't run an important database on a server without ECC memory - but ZeroDB doesn't seem to make that an option. Are you addressing this in any way?
  - geoelectric 12y ago
    Well, if the indexes can all be updated with transactional integrity around the whole thing (which I think you need anyway, per thread below about having to do client-side rotates to self-balance the tree and keep log n) in theory this is no worse than a memory overrun/etc. in the original database server. Most fatal errors just mean you lose an entire atomic update, and the type where you "successfully" write bad data imply the same sort of repairs as server-side maintenance would. In practice, I think the biggest issue is that if you had to restore a backup, there'd be no way to restore only -your- tree, since the server doesn't know structure or ownership of the buckets. You'd have to roll back everyone in the bucket store. I don't want to be too negative, because I think having something like this is a good idea. It's plain there are challenges to be solved here though. Edit: though I do catch your point that N clients all maintaining the same index tree is potentially like having a non-redundant N-wide storage array--failure rate is cumulative. Think you could possibly mitigate this with a single-source-of-truth per table/index client-side design, but that's an obvious potential bottleneck.

oh_teh_meows 12y ago

What are the advantages of ZeroDB over a database that uses homomorphic encryption like CryptDB? Do they cater to different uses?

michwill 12y ago
CryptDB doesn't use homomorfic encryption. It is doing sortable deterministic encryption. E.g. after encryption the server can determine whether a > b or a == b. They have a very good understanding of what data does it leak, when can you do that and when cannot. In our db, random observer cannot see how data are ordered or whether elements are equal to each other. Homomorfic encryption would be ideal of course, but it is slow and impractical for the moment
- quizotic 12y ago
  Actually, CryptDB does (or at least did originally) use homomorphic encryption (HE) for evaluating SQL arithmetic expressions. While the earliest suggestions for HE were terribly slow, CryptDB found one that was practical. If memory serves, there have since been HE improvements claimed by IBM and/or Google. But as michwill states (and CryptDB acknowledges), their approach either leaks information or precludes classes of expressions. For example, their order-preserving encryption could be susceptible to a brute-force attack via 'a > b' ... '(a+1) > b' ... '(a+2) > b'