6 ms·
Immutable Databases
- hirundo 6y ago"Art. 17 GDPR: Right to erasure ('right to be forgotten') 1. The data subject shall have the right to obtain from the controller the erasure of personal data concerning him or her without undue delay..." How does this right affect a website backed by an immutable database? Is it enough for data to be superseded by later data, such as an assertion that the prior data is defunct? Or does it have to be actually erased? Can it be considered erased for Article 17 purposes if the database owner can still access it? Is a website with an immutable database illegal under the GDPR after a court order to delete something has been received? Datomic devs want to know. https://gdpr-info.eu/art-17-gdpr/ https://gdpr-info.eu/art-17-gdpr/
- toolslive 6y agoyou could encrypt every record (with its individual nonce), and do the merkle tree has over the encrypted record. To erase the contents of the record, you just have to forget the encryption key. A variation of this trick is used in block devices that offer a fast wipe. Instead of having to fill every block with a bit pattern to wipe the contents, they just have to change the current encryption key. Once that's done the device is effectively filled with random bits.
- specialist 6y agoExactly. Just like a password wallet. Store the hash of passwords, not the actual passwords. Then disallow password resets. Then you effectively "forget" your account if you lose your password. The book Translucent Databases (2nd ed) [2009] explains clever strategies for applying this technique to protect sensitive data. It's brilliant. https://www.wayner.org/node/39 https://www.wayner.org/node/39 https://www.amazon.com/gp/product/1441421343 https://www.amazon.com/gp/product/1441421343 Meta: I remain disappointed by the obscurity of this book and translucent techniques. A long time friend recently asked me about GDPR compliance and so forth, in prep for reworking stuff to allow proper audits. Very tech savvy. The translucent notions just could not compute. So their efforts went down the conventional rabbit hole of actually deleting data. Which I don't consider practical or auditable. How can you be sure an org deleted every record, log, backup, etc? You can't.
- toolslive 6y agoencryption the records. fine, but how do you handle the indexing of the attributes?
- specialist 6y agoI think I understand your question. "Translucent" was coined to describe somewhere between all cleartext (transparent) and all encrypted (opaque). Generally, only sensitive fields are encrypted, so no record level encryption. The cleartext fields can still be searched, indexed. The book shows many clever schemas for mixing and matching hashes, keys, and cleartext. I used translucent strategies for storing patient data. It's pretty straightforward after some experience. Though I admit I didn't have any resources to review, audit our efforts.
- szemet 6y agoIANAL but I recall some vauge memories that Datomic was to be modifed, to provide real physical deletion according to the GDPR reqs...
- slifin 6y agoI think you can https://docs.datomic.com/on-prem/excision.html https://docs.datomic.com/on-prem/excision.html on prem you can choose not to store history with :db/noHistory per fact then just update the record in place Datomic cloud though I'm not sure
- 6gvONxR4sf7o 6y agoAn in-place update seems counter to the whole immutable premise. There must be a middle ground of in-place with record. Like, (1/2/2020, John, oldAddress) becomes (1/2/2020, John, oldAddress) --> (3/4/2020, John, newAddress) becomes (1/2/2020, deletionRequestName1, deletionRequestAddress1) --> (3/4/2020, deletionRequestName1, deletionRequestAddress2) --> (5/6/2020, GDPRDelete, deletionRequestName1, deletionRequestAddress1, deletionRequestAddress2) or something. That doesn't feel quite right, but it feels like there's some nice combo somewhere that keeps the auditing and history and most of the simplicity. Or maybe there's a cryptographic solution, like (1/2/2020, ALKXJDS, CNDSLKDJ) becomes (1/2/2020, ALKXJDS, CNDSLKDJ) --> (3/4/2020, ALKXJDS, QWERTYYUIOP) becomes (1/2/2020, ALKXJDS, CNDSLKDJ) --> (3/4/2020, ALKXJDS, QWERTYYUIOP) --> (5/6/2020, we threw away the cryptographic keys to decode ALKXJDS's info).
- derefr 6y agoIf it's anything like CouchDB, there's a compaction sweep that normally puts small history chunks together into larger history chunks, but which also has the responsibility of dropping any history before a tombstone record on the floor.
- ashtonkem 6y agoDatomic stores its data in a list of “facts”. Normally these facts are append only, but excision is a special case. Think of it this way: normally a database entry is represented as a row. You could also represent this exact same data as a list of triples: primary key, attribute name, and attribute value. Same data, different representation. Datomic stores its data in a series of quadruples: primary key, attribute name, attribute value, and transaction. These facts are append only; when data is normally deleted the transaction includes the fact that the data is being deleted, not added. Under the hood Datomic processes these facts to produce the current state of the world, but the old data is there if you ask for it. Excision deletes facts from the database, which both violates a lot of assumptions about how the database works, and permanently removes the data. In the process of excision it leaves a single record to indicate that something was removed, without clarifying what. It’s something they only recommend for regulatory compliance, as it eliminates a lot of the value in the database.
- jasonwatkinspdx 6y agoImmutable doesn't necessarily mean that it's literally impossible to rewrite history or redact history. It's more a change in the default of how things are done. Some merkle tree variants directly support deletions. You keep around the hash of the deleted subtree, so the overall structure still has a verifiable hash history, but you lose the data that generated the hash. Another simple approach is to use per user encryption keys, and when a user wants deletion just nuke their key in the system that stores keys.
- smitty1e 6y agoMy understanding from reading the O'Reilly book on the subject is that the blockchain is 'just' cryptographic hashes, not the data proper.
- vbezhenar 6y agoWhat does it mean "actually erased"? If I delete file, its contents are still on disk. If SSD remaps block, it might be inaccessible by operating system at all but it still technically contains data.
- derefr 6y agoThe spirit of "right to be forgotten" is a right to not have past events unduly influence your public image. I would assume that—unless it's been proven that you can GDPR-takedown-request a credit agency to erase your credit history—there's no "right to be forgotten" as applies to never-publicized, company-internal data about you.
- ealexhudson 6y agoThat's not quite it. The different legal bases for processing personal data come with different rights; one of them is the right of erasure. It doesn't matter if the data is public or private. This isn't a general bazooka - you'd be unlikely to erase the data that generates a credit score, for example, but then there will be equivalent rights (right to explanation of an automated decision, plus the right to correct a mistaken record). All of these rest on the ability of the subject to gain access to their record in the first place too. Immutability isn't an automatic problem for GDPR - you're allowed to take backups of databases too! - but it is axiomatically more difficult to be in compliance with such an arrangement.
- ashtonkem 6y agoOther immutable databases (Datomic) provide the ability to permanently erase entities from the database to meet regulatory needs. It leaves behind a single record to indicate that something was excised from the database.
- Smaug123 6y agoI have a possibly very stupid question: how is this not "basically just Git"? Git is a content-addressable distributed filesystem which represents its history immutably and verifiably as a tree of committed transactions. Is the point that you need much more data throughput than Git can handle, or something?
- carapace 6y agoI don't know yet how it will turn out but I'm making a simple prototype DB using Prolog-syntax flat files stored in git. (SWI Prolog provides a specialized `persistency` module that is kind of "log-oriented" ( https://www.swi-prolog.org/pldoc/man?section=persistency https://www.swi-prolog.org/pldoc/man?section=persistency ) but I want to see how well just plain ol' Prolog files work.)
- throwaway_pdp09 6y agoLike this https://en.wikipedia.org/wiki/Datalog https://en.wikipedia.org/wiki/Datalog perhaps?
- carapace 6y agoNah, just plain old Prolog. (I've only been working with Prolog for about a year. I know there are other things out there like Datalog, Mercury, and Kowalski's Logic Production Systems, but I want to grok the root in fullness before I get to those.)
- dustingetz 6y agoYou need graph queries and graph transactions basically, git is geared for text and diffing
- Smaug123 6y agoWell, yes and no - while it does provide diffing, it's not native to how Git works. Diffs are inferred, or are used internally as a performance optimisation, rather than being fundamental. I suspect this is the kind of place where the answer is "just go and do it, you'll find out why soon enough".
- tuxxy 6y ago> ... where instead of using Merkle Trees, other cryptographic primitives could be use to ensure tamper proofness, such as Zero Knowledge Proofs What would your zero knowledge proof _prove_ exactly without some data structure behind it? In many applications, the zero knowledge proof is being used to prove that something in a data structure is correct/valid/etc. You can't just replace these data structures with zero knowledge proofs arbitrarily.
- toolslive 6y agoWhy is it called "immutable" iso "persistent"? https://en.wikipedia.org/wiki/Persistent_data_structure https://en.wikipedia.org/wiki/Persistent_data_structure
- convolvatron 6y agonothing is ever deleted in an immutable store. a persistent store survives across reboots, but you can delete elements if you can deal with the consequences, removing deletes makes dealing with concurrency a lot easier
- TheColorYellow 6y agoTo me the usage of "immutable" is to imply some element of verifiably provable data exists in the database or system. Persistence would rather imply data longevity in the face of disaster, downtime, or under load, etc. Not the greatest use of terms but that's how I view it.
- toolslive 6y ago"a persistent data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. The term was introduced in Driscoll, Sarnak, Sleator, and Tarjans' 1986 article". It's effectively the same thing. A third name for the same thing is "append only".
- kreetx 6y agoIn databases I think what they mean with persistence is writing to disk, i.e committing to the new state. Immutable on the other hand appears to mean a similar thing both in databases and data structures.
- amelius 6y agoWould such a database be practical when dealing with laws like GDPR where you have to actually delete stuff sometimes?
- philips 6y agoRelatedly: Go’s module proxy uses a similar sort of Merkle tree and rsc has an open source sqlite backed version of that service up on GitHub: https://github.com/rsc/tlogdb https://github.com/rsc/tlogdb I built a curl/wget like application recently that does URL binary transparency and is backed by tlog. https://github.com/transparencylog/btget https://github.com/transparencylog/btget It is a prototype but some folks might find it interesting. I think the critical thing for these sorts of immutable databases is having lots of clients with long lived cache’s of the proofs to keep the db’s accountable.
- ithkuil 6y agoI made the same thing but (ab)using the go module proxy own transparent log infrastructure: https://github.com/mkmik/getsum https://github.com/mkmik/getsum
- philips 6y agoI built it initially on top of certificate transparency in a similar vain. However it really wasn't a good experience for users and hard to onboard projects since lots of folks have different formats and URL structures https://github.com/merklecounty/rget https://github.com/merklecounty/rget
- deleted 6y ago[deleted]
- ashtonkem 6y agoI believe that Immutable databases sans crypto have quite a large amount of utility for some use cases, since you can use such a database to give you change history for free, separate from your domain schema. Datomic is pretty close to what I have in mind, but it’s far too Clojure specific to gain traction outside of that language, IMHO.
- krn 6y ago> Datomic is pretty close to what I have in mind, but it’s far too Clojure specific to gain traction outside of that language, IMHO. I believe that Crux[1] might be the solution, especially with its open nature. [1] https://opencrux.com/ https://opencrux.com/
- jacques_chester 6y agoAs a note, the idea of using chained hashes to verify sequential records predates blockchain: it was called "hash chaining". The "block" in block chain refers to batching these up to reduce the total number of network interactions required. https://en.wikipedia.org/wiki/Hash_chain https://en.wikipedia.org/wiki/Hash_chain
- CuriousSkeptic 6y agoAren’t you thinking of Merkle Trees? https://en.m.wikipedia.org/wiki/Merkle_tree https://en.m.wikipedia.org/wiki/Merkle_tree
- jacques_chester 6y agoI was prepared to say "yes and no", insofar as Merkle trees are more general. But some poking around reveals that Merkle's original patent was filed in 1979, whereas Lamport's paper introducing a cryptographic hash chain (S/KEY) was published in 1981. For an append-only linear data structure like a log or database table configured to be append-only, hash chaining is fine. I've used it for that purpose. Merkle trees are much more useful for anything that needs to fan out or (as git shows) fan in. My real point was meant to be that these ideas predate blockchain, they don't necessarily need new names. https://crypto.stackexchange.com/questions/68290/when-was-hash-chain-first-used https://crypto.stackexchange.com/questions/68290/when-was-ha...
- yogthos 6y agoCrux https://opencrux.com https://opencrux.com and Datomic https://www.datomic.com https://www.datomic.com are worth mentioning as well. Both are able to leverage existing relational databases like Postgres internally.
- dzonga 6y agolooked at those a while back. seem to be only available for clojure.
- kot-behemoth 6y agoJuxt were very vocal about making Crux available beyond Clojure (can't find the exact quote right now, unfortunately). Perhaps the last time you checked it, any non-Clojure support was still WIP. However, since then they definitely have Java API available (Javadoc here: https://crux-doc.s3.eu-west-2.amazonaws.com/crux-javadoc/20.05-1.8.4-alpha/crux/api/package-summary.html https://crux-doc.s3.eu-west-2.amazonaws.com/crux-javadoc/20....), as well as REST API (see https://opencrux.com/docs#restapi https://opencrux.com/docs#restapi).
- refset 6y agoThat's right, we're certainly keen to help all JVM users who wish to embed Crux, and for users sitting outside the JVM we have significantly more comprehensive JSON support and SQL queries in the works too. Our upcoming SQL module is based on Apache Calcite which does a lot of heavy lifting and compiles SQL joins to Crux's native Datalog. For the curious: https://github.com/juxt/crux/blob/0f7d9c66db952a65efb4cba7e3f797ef19db6132/crux-sql/test/crux/calcite_test.clj https://github.com/juxt/crux/blob/0f7d9c66db952a65efb4cba7e3...
- yogthos 6y agoBoth are implemented in Clojure, but there's nothing Clojure specific involved in their usage.
- peterwwillis 6y agoThis is a misuse of the term immutable to latch onto its cache as a popular term. Immutability has nothing to do with verifiability or security or integrity. Immutable just means 'does not change'. It's like saying read-only. I really like the idea of a database with integrity and verifiability and repeatability and fast recovery, but let's not muddy the definition of immutable or people won't understand its use in other contexts.
- scottfr 6y agoI was reading BigQuery the Definitive Guide last week and I was surprised to learn that BigQuery is actually immutable at its core even when using DML statements. This is surfaced in the query language and you can query the table as it existed in the past using the syntax: SELECT * FROM table_name FOR SYSTEM TIME AS OF TIMESTAMP_ADD(CURRENT_TIMESTAMP(), INTERVAL -5 DAY) The tables get rewritten periodically squashing this change history so you can only access states for the past week.
- jacques_chester 6y agoWhat you're seeing is an SQL:2011 thing -- system-versioned tables. It's from a more general concept of bitemporal databases. It's not quite the same. A cryptographic chain or Merkle tree can prove that the history has gaps which appeared since the original recording was made. A system-time table's safety rely on the guarantees of the implementing database.
- akudha 6y agoThis book is in the current humble bundle. How do you like the book?
- beobab 6y agoI remember reading "Heirs of Empire" by David Weber, and it casually mentioned that Dakax had a database that was immutable. I remember thinking that was a good idea, and planned to think about it later, but alas I had forgotten about it by the time I'd finished the book. [edit: added who's database it was]
- bobbiechen 6y ago>Actually, I expect to start seeing immutable databases applied to some of these use cases in no time: > To immutably store every update to sensitive database fields (credit card or bank account data) of an existing application database. Would this cause legal issues, for example, with GDPR deletion requests? I can't imagine that regulators would accept the answer "Sorry, my database doesn't allow me to delete data". So then you would need a way to make a "real delete", which seems like it might erode the benefits described.
- deleted 6y ago[deleted]
- tetromino_ 6y agoData, especially old data, is very often a liability. It carries storage costs, legal and regulatory risks, and makes a tempting target for attackers. Outside of a few domains like source code management, wouldn't you by default want a mutable database that auto-scrubs old data based on retention rules?
- mD5pPxMcS6fVWKE 6y agoWell, immutable database is just a database without the "delete" and "update" operations. Blockchain, on the other hand, is something entirely different - it's a distributed consensus protocol.