Immutable Databases
adlrocha.substack.com
adlrocha.substack.com
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/0f7d9c66db952a65efb4cba7e3...
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.
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)
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.
I built a curl/wget like application recently that does URL binary transparency and is backed by tlog. 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.
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.
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-ha...
(SWI Prolog provides a specialized `persistency` module that is kind of "log-oriented" ( https://www.swi-prolog.org/pldoc/man?section=persistency ) but I want to see how well just plain ol' Prolog files work.)
(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.)
I suspect this is the kind of place where the answer is "just go and do it, you'll find out why soon enough".
Git is a hash chain with a few constraints:
- Each commit has at least one previous commit, unless it's the root.
- Each commit has author and committer metadata with embedded timestamps.
- Each commit references a merkle tree of files at that specific commit.
You have the option of setting the authors to some minimal example value (example@example.com, Jan 1 1970) and using an empty tree, but then your payloads are being stored in the "commit message". Streaming these payloads is hard, getting them by sequence numbers is hard, enforcing extra constraints (e.g. only one previous commit, no merges) requires a Git hook, and at all times you're acutely aware that Git wasn't built to act as a distributed NoSQL database.
Using Git as a database is possible, but I think it's about as practical as writing your application logic in some technically-Turing-complete language like PostScript.
if you can deal with the consequences, removing deletes makes dealing with concurrency a lot easier
Not the greatest use of terms but that's how I view it.
A third name for the same thing is "append only".
Immutable on the other hand appears to mean a similar thing both in databases and data structures.
[1]on-prem, not cloud
However even if the DB doesn't offer that operation, you could use "crypto shredding" where you encrypt the data before putting it in the immutable db and then store the key in some kind of mutable store. (Then delete the key when you want to delete its corresponding data).
There's also this post which describes some other methods of making a Datomic cloud system gdpr compliant: https://vvvvalvalval.github.io/posts/2018-05-01-making-a-dat...
Sure, some academics used the term for a class of in-memory data structures too, and it got taken over in some programming circles, but it's a niche term at best. Now, so far so good, but using that term for databases might be maximally confusing. After all, isn't a database's primary purpose to persist data? Then, aren't all databases persistent? Oh, no, the author meant that other meaning of "persistent" that many people aren't familiar with.
I think the author made the right call :-)
(I know that immutable and persistent aren't the same thing: you can make an immutable data structure that isn't persistent in that it doesn't reuse data - but it's the best we got)
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.
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.
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
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).
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.
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.
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.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.
"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.
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.
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.
[edit: added who's database it was]
> 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.