Crux https://opencrux.com and Datomic https://www.datomic.com are worth mentioning as well. Both are able to leverage existing relational databases like Postgres internally.
Juxt 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....), as well as REST API (see https://opencrux.com/docs#restapi).
That'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.
This 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.
I 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.
What 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.
Relatedly: 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
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.
I 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
I 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.
As 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.
I 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.
I 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?
(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.)
Well, 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".
I work on Scuttlebutt, which in another "basically just Git" kind of thing, and after porting Scuttlebutt to "just Git" I can comment on this a bit.
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.
I'd wager that in most programming ecosystems (the non-FP ones in particular), "persistent" means "sticks around after a crash/restart/etc", i.e. in practice, that it's saved to disk.
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)
"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.
To 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.
Could be an issue. For that reason, the two immutable databases with which I'm familiar (Crux and Datomic[1]) provide operations for removing bits of data from history.
[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).
> ... 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.
"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.
Other 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.
Immutable 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.
What 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.
The 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.
That'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.
you 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.
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.
An 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).
If 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.
Datomic 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.
Data, 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?
I 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.
Well, 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.
>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.
