immudb – world’s fastest immutable database, built on a zero trust model
github.com
github.com
What's supposed to happen is that the server will give the client a path in a https://en.wikipedia.org/wiki/Merkle_tree to the current state, the prove that the key-value pair is included in the Merkle tree.
There are, however, some subtle issues which can arise if you're not careful. In particular, what happens if I set the key k to value v1, and then set the key k to value v2? If I subsequently ask for the value of k, I ought to see v2, and a proof that k is v1 shouldn't check out. However, in order for this to work, it's not sufficient for the server to prove that (k, v) is in the audit log, since that would allow for the server to maliciously roll-back the state. What you really want to prove is that v is not just _a_ value that k was set to, but _the most recent value_.
It's unclear to me whether the code actually does this--there's no architecture guide which describes the cryptographic algorithms at play (or what the threat model is), and the code appears to be mostly devoid of comments. There is a reference to separate inclusion and consistency proofs, which might be this distinction. But it's really hard to tell from the digging that I've done.
For sure it's not the optimal solution, some ideas to cover this scenario were discussed but not yet fully defined.
Basically a hash value denotes the entire state of the database (including the entire history). This hash may be cryptographically signed and exported from the server. immudb SDKs keeps track of the last verified state, each time a new one is received, it's cryptographically validated.
Whenever a particular entry or transaction is verified, the latest validated hash also used. If the entry was tampered in, hashes won't match.
> Basically a hash value denotes the entire state of the database (including the entire history). This hash may be cryptographically signed and exported from the server. immudb SDKs keeps track of the last verified state, each time a new one is received, it's cryptographically validated.
Okay, but how do you persist that hash across eg. client restarts? You obviously can't store it in the database. And this does not sound like "zero trust" to me - that's a much higher bar to meet, and would allow for eg. untrusted writers.
As I understand it right now, immudb works more or less the same way that Git does; it's a DAG of database (instead of file) mutations, and you can persist the latest commit hash to ensure that someone hasn't messed with what a branch points to.
Which can be useful, don't get me wrong, but it's not "zero trust" and it's certainly a fairly niche security feature.
Edit: To be clear, I'm very much in favour of what immudb seem to be trying to do - getting enterprises away from ultimately dysfunctional "blockchains" by providing something more sound with nominally the same features/appeal. But it's always important to be very clear about what your tech does or doesn't provide, blockchain or not.
if entering an email for downloading the paper is a concern, we'll consider it.
immudb should be used as a traditional database (log, key-value or even a relational store - with limitations of course), so it's up to your deployment to whom you give user credentials with read/write permissions. The key difference is the state being captured by a single hash value.
Given the hash value denoting the entire state can be signed and exported. It's out of control of the server how many copies or when a validation is going to be made. Currently, official SDKs are storing the latest validated hash in a local file, but it's perfectly possible to store the hash in a remote storage, other database, etc. This will ensure data is only added but never changed once written, please note with never changed I mean it's subject to detection when a proof is requested.
immudb does not pretend to provide a complete security solution, but a key component when you deal with sensitive data.
> immudb can be used as a key-value store or relational data structure and supports both transactions and blobs, so there are no limits to the use cases.
This is game changing. Use it for say a secondary data store for high value audit logs. I'll consider using it in the future.
You can truncate a BQ table and reload it if you want to change things. Had to do this at a previous gig (twice a day!) because the data warehouse people would only take data from BQ but the main data was in Firebase (yes, it was an insane place.)
I guess we must consider what can go in an immutable storage and what must not.
To achieve "client does not need to trust the database engine", it would need to be possible for the client to independently walk the history of the database and verify that neither its mutations nor its order has been tampered with. For that, the actual data needs to somehow be taken into account in the signature, commit hash, whatever.
So when you logically delete data, how are you _not_ breaking that hash chain? The original data that produced a signature/hash is no longer available, and therefore not verifiable anymore. This means that the relevant commit cannot be trusted, and therefore neither can anything that comes before it.
Or are you just trusting that any 'redacted' commit is valid without actually verifying its hash? In that case you'd be compromising the trustless nature, because the database engine could autonomously decide to redact a commit.
Generally HW is the main factor with performance, then quality of coding and functionality that exists. For example in MS SQL BulkInsert is fastest ie importing from a txt/csv file then batch inserts then single record inserts.
Now the next factor is how many records need to be inserted?
Companies like Experian have been using a custom ISAM (dbase/clipper type) database where Mon-Sat users can read the data and all data is updated on Sunday.
It was the only way to serve a country wide levels of users with 90's HW.
It also meant the speed gains were found by doing stuff in RAM then writing out data in a serial manner to disk.
Things havent changed that much in 30 years, RDBMS systems are just another layer between HW and the end users app!
After working in the fintech space, nothing is truly immutable because of compliance.
Fintech -- the customer which should want this most -- can't use it.
1: https://stackoverflow.com/questions/35919167/create-insert-o...
Seems pretty useful actually. Can anyone with a relevant background comment on when this would be a bad idea to use?
But in some cases you don't have that same constraint. For example, databases that store logs (Elastic, Splunk, etc) might have many readers and writers, including humans.
In that case enforced immutability might be a nice property to have. Attackers who get access to your Splunk/ES cluster certainly will have fun with it.
We evaluated AWS QLDB for these things in our application as a financial ledger and were impressed at their progress with a novel data store. They invented some of the tech in house for this product instead of grabbing an off the shelf open product. Lockin would be a downside here.
Immudb looks promising because it's not locked to a cloud host.
not an "all or nothing" question.. for example, a fast-enough "return the most recent in a time series" is not exactly time-series, but solves many use cases
Also, what are the system requirements for immudb? What kind of machine would I need to run a medium to large website (say, 1TB of data, 5-25K qps, e.g. Wikipedia)?
It mentioned in the documentation that it can use S3 as its storage? Are there performance implications if you do this?
I'm sceptical, but particularly because they make a deliberate comparison to blockchain that I doubt they'll be able to deliver.
The PoW immutability of e.g. BTC and ETH is strong as it yields the following guarantees for stored data:
- Immutability of the BTC blockchain is protected through all cummulative work that has happened on a specific branch of the chain. Even if someone replayed BTC, it'd take millenias to recompute the work on an average machine
- The immutability isn't enforced on a file level, as I suspect it is with immudb. Immutability is enforced through the network that has additionally shown to have conservative political views too. You can go, sync a BTC node and change the underlying level db. Still that won't change the network state. Immutability on a single system is physically impossible if e.g you consider deleting the file as mutation.
- immudb says "it's immutable like a blockchain but less complicated", but Bitcoin isn't more complicated than some sophisticated enterprise db solution.
- I think immudb should be maximally upfront what they mean by immutability: It seems they want to communicate that they're doing event sourcing - that's different from immutability
Finally there's a rather esotheric argument. If you run an immutable database as an organizatiom where one individual node cannot alter the network state but you have (in)direct control over all nodes: Isn't it always mutable as you could e.g. choose to swap out consensus?
So from a philosophical perspective, then immutability can truly only occur if mutability is out of an individual's control.
Why do I have the authority to say this? Because I too have once worked for a database with blockchain characteristics called https://www.bigchaindb.com
Edit: The best solution that also has a theoretically unlimited throughput is this toy project: https://github.com/hoytech/quadrable
Conceptually, it computes a merkle tree over all data and regularly commits to Ethereum. Through this commitment the data may still change locally: But then at least would be provably tampered. So I guess for databases, the artibute we can really implement is "tamper-proof".
If you wanted to identify a fraudulent rollback, I think you had to constantly replicate all transitions and recompute the on-chain merkle hash. If you found discrepancies in the on-chain hash and yours, it'd mean that either node ran out of synch for some unknown reason.
Then, if e.g. other nodes too replicated your state, you may be able to conclude that the wrong-hash node had a (byzantine) fault etc.
But I think that at least in the case of the Ethereum Plasma architecture, just committing a state aggregate in form of a hash wasn't enough because of some block withholding attack. From my understanding, hoytech's quadrable is just a chain committment. Similar to Plasma.
Modern rollup architectures end up storing all transition state in Ethereum calldata state. This way proving fraudulent validation is possible and things become conceptually simpler as you can rely on the strong guarantees of e.g. data availability of the PoW chain.
It is, however, hundreds of thousands times slower as a database.
Do you just store the hash but not the underlying KV pair?
Truncating transaction headers should be possible, but each physical deletion will be associated to a real lost of data, so proof generation may be affected on deleted data.
From an operational standpoint, it allows you to roll out a change in exactly the way you tested, confident that it will work the way it's intended. It also allows you to roll back or forward to any change with the same confidence. It also means you can restore a database immediately to the last known good state. Changes essentially cannot fail; no monkey-patching a schema or dataset, no "migrations" that have to be meticulously prepared and tested to make sure they won't accidentally break in production.
From a security and auditing standpoint, it ensures that a change is exactly what it's supposed to be. No random changes by who-knows-who at who-knows-when. You see a reliable history of all changes.
From a development standpoint, it allows you to see the full history of changes and verify the source or integrity of data, which is important in some fields like research.
The inability to mutate data pointed to in prior areas of the log does come with tradeoffs regarding other performance optimizations that expressly rely on mutability, but in my experience constraining the application to work with an immutable log (i.e. dealing with stale reads & compensating transactions) usually results in substantial performance uplift compared to solutions relying on mutability. One recent idea that furthers this difference is NAND storage, where there may be a substantial cost to be paid if one wants to rewrite prior blocks of data (depending on the type of controller/algorithm used by the device).
Now I'm wondering if we can have immutable versioned APIs
Know how they have this tool Terraform that "orchestrates infrastructure" ? It's actually a configuration management tool for APIs; it expects the state to unexpectedly change under it, and it will attempt to "fix" it (in some cases). Because the APIs don't support immutable versioned calls, the result can (and does) randomly fail or result in different outcomes each time you run Terraform. There's really no way to know if a call will succeed until you call it, leading to regular situations where production is half-deployed, half-broken, until someone can manually fix it. Not only that, but multiple people can apply conflicting changes to different components one after the other, leading to an untested and possibly broken result. (Terraform makes an attempt to track its own changes in a state file, but the state file is not the same as the actual state of AWS, so often the state file actually prevents Terraform from fixing conflicts)
The only way to avoid that whole mess of constantly-mutating unreliable changes is for the APIs to support immutable operations, so that all changes necessary can be applied at once, and you can safely revert to previous tested state if necessary.
Semi-relatedly, Stripe has a great post[0] on how they handle backwards-compatibility with their API.
How is this different from preserving a database UNDO/REDO log permanently?
Immutability brings a bunch of perf short-cuts which is usually impossible to build with a mutable store.
You'll find a lot of metric stores optimized for fast ingest to take advantage of the immutability as a core assumption, though they don't tend to do what immudb does with the cryptographic signatures to check for tampering.
Look at GE Historian or Apache Druid for most of what I'm talking about here.
You can build out a tiered storage system which pushes the data to a remote cold store and keep only immediate writes or recent reads locally.
You can run a filter condition once on an immutable block/tablet, then never run it again (like a count(*) where rpm > X and plane_id = ?) can be remembered as compressed bitsets of each column, rather than as final row selection masks. Then reuse half of that when you change the plane_id = ? parameter.
The fact that the data will never be updated makes it incredibly fast to query as you stream more data constantly while refreshing the exact same dashboard every 3 seconds for a monitoring screen - every 3s, it will only actually process the data that arrived in those 3 seconds, not repeat the query over the last 24h all over again.
The moment you allow even a DELETE operation, all of this becomes a complex mess of figuring out how to adjust for changes (you can invalidate the bit-vectors of the updated cols etc, but it is harder).
The whole point of shipping cold storage off to S3 was to solve that kind of scale problem.
You can keep your ingest nodes scaled up to the incoming data (per-day, approx), replicate 3-way for HA and use SSDs for commit throughput.
The query nodes scaled up to the working set sizes, but auto-scale up/down based on the workload scan sizes (no need to keep them running 24x7, cheaper to throw away the cache after a workday - no need for replicas, just jitter them so that the entire cache doesn't go poof at the same time + hit s3 throttling on the next query).
And the S3 bucket is literally infinite storage (more like caps out when the metadata about the s3 backed items hits 8 Tb).
Run the equivalent of an fsck every quarter to check the checksums, then re-encrypt them with a new key or to recompress the blocks by swapping them (go from lz4 to zstd as they age out).
There is a mechanism to expire data after 7 years of storage (I guess it won't be queried anymore, so there'd be nothing "live" to expire?), but that might be longer than the current architecture lives on without a refactor.
submitting several transactions at the same time is also possible and convenient, processing is concurrently done until the last step which requires a strict serialization.
benchmarking is a huge topic and we'd love to have contributions on this. It may refer to using embedded immudb, as a stand-alone server, kv, sql, etc....
https://docs.microsoft.com/en-us/azure/azure-sql/database/le...
If a Client is malicious, they might try to manipulate the data in the database in an untoward way. In a "normal" database, this might cause data loss, if the database isn't being continuously backed up. But immudb does continuous backups (effectively, since it's immutable) so, if a malicious client has been detected, it's possible to restore an older version of the database. The real problem is how would you know that a client has tampered with your database? Well, because this database is "tamper-proof," duh! But the issue lies in the definition of tamper-proof. From my reading of the source code and documentation, the "proof that no tampering has occurred" is a proof that the current state of the database can be reached by applying some database operations to a previous state. As a result, a malicious client could simply ask the database to "delete everything and insert this new data," to make the database look like whatever it wanted. This is a valid way to transition the state of the database from its old state to the new state, and so shouldn't be rejected by the tamper detection mechanism.
"Ah," but you say, "it would look super sus [as the kids say] to just delete the entire database. We'd know that something was up!" The problem with this solution is how are you going to automate "looking super sus?" You could enact a policy to flag any update that updates more than N records at a time, but that's not really a solution. The "right" solution is to trace the provenance of database updates. Rather than allowing arbitrary database updates, you want to allow your database to be changed only by updates that are sensible for your application. The _actual_ statement you want to prove is that "the current state of the database is a known past state of the database updated by operations that my application ought to have issued." Of course what are "operations that my application ought to have issued?" Well, it depends how deep you want to go with your threat model. A simple thing you could do is have a list of all the queries that your application issues, and check to make sure all operations come from that list. This still allows other attacks through, and you could go even more in depth if you wanted to.
Importantly, immudb doesn't appear to contend with any of this. They claim that their database is "tamper-proof," when in reality you'd need a complicated external auditing system to make it meaningfully tamper-proof for your application. (Again, a threat model ought to include a precise definition of "tamper-proof," which would help clear up these issues.)
It's also worth comparing this to https://en.wikipedia.org/wiki/Certificate_Transparency, which is an append-only database. Compared to immudb, the _exposed data model_ for certificate transparency logs is an append-only set, which means that it doesn't have any of these same problems. The problem with immudb is that the data model it exposes is more complicated, but it's built-in verification tools haven't been upgraded to match.
(Also, for context, I've tried to obtain a copy of their white paper, but after an hour the email with the link to it never arrived.)
Sounds like maintaining this over longer term with evolving data would be quite painful.
A clone and remove/update per GDPR request seems like undue delay, certainly one that could be avoided by alternative architecture choices (keep the personally identifiable information (PII) in a mutable store)
> Under Article 12.3 of the GDPR, you have 30 days to provide information on the action your organization will decide to take on a legitimate erasure request. This timeframe can be extended up to 60 days depending on the complexity of the request.
even if they ask for more time, first communication has to come within 30 days
It looks pretty straightforward English to me.
GDPR is published in 24 languages, including English, I don't know why people still don't get it and what's so hard to understand.
It's not a single law, it's a collection of articles, the 17th says that data should be erased without undue delay.
We don't have common law in Europe, EU is mostly civil law (emphasis on civil) or Romano-Germanic law. The only exception is Scandinavian law, which is very similar to (and a subgroup of) civil law anyway.
Don't forget to star this repo if you like immudb!