YogurtFiend

While this isn't true with Go's GC, a GC that's stop-the-world can avoid these cache coherency issues altogether. If you pause every thread before marking and sweeping, then you won't run into problems--only the GC is running. While this may sound silly, stopping the world will oftentimes lead to higher throughput than concurrent collectors, at the cost of higher latency (which is why it's not suitable for Go, which is often used for building servers where latency is a priority).

I don't know why you're being downvoted. Memory reclamation is hard in the face of parallelism. It's much easier to design lock-free algorithms in languages with a garbage collector, because memory reclamation issues are taken care of for you (and often times in a batched manner, which won't affect the hot path of your code). There _are_ techniques to avoid using a garbage collector: atomic reference counting, epoch-based reclaimation, hazard points, and more. But they can be quite difficult to implement and difficult to use.

I agree 100% with the need for the threat model. I think the current system is, at-best, a system with a tamper-evident audit log. Which, could still be interesting, but the authors' use of ill-defined terms makes it easy for people to think their software does something that it's not.

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.

I'm not sure that this is a _useful_ tool. Let's talk about the threat model or the attacks that this defends against.

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.)