Re:immudb – world’s fastest immutable database, built on a z...
by jeroiraz on Tuesday December 28, 2021 @06:42AM
(#29712772)
This is a very interesting point. Rollbacks are protected by consistency proofs and with inclusion proofs it's possible to detect such situation but it may require scanning over the transactions. immudb does not only provide access by key or key prefixes but it's also possible to fetch a particular tx by its unique identifier or scan over them.
For sure it's not the optimal solution, some ideas to cover this scenario were discussed but not yet fully defined.
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.