This is actually quite a common problem in cryptographic systems. This can be looked at as proving two different things:
- Is the server currently storing all of the elements a specific client has given it before in order (is it honest with us)?
- Is it giving us all of the other client's data (is it honest with others)?
- Will it continue to act as an append-only log in the future (will it always be honest)?
Is it honest with us?
This is and easy to solve problem, solvable by a simple Merkle tree (also hyped as a "blockchain"). Publish a list of tuples
<hash(previous_element), current_element> and the hash of the most recent one, known as the
head. Now a verifier can update by looking at the head and downloading it, then looking at the previous hash and downloading that, and so on until it reaches the head it previously stored.
This only verifies that nothing before the previous head has been altered or removed: an omission or alteration before the previous head would change the head's hash, so the client would be able to detect it.
Of course, the client doesn't need to store the whole history; they just need to verify the hashes all the way down to their previous head, and then store the new head's hash, making this very space efficient.
If you want to restrict who can append, add a ring signature to the tuple, and give each validated client a key in the ring.
Is it honest with others?
The second one cannot be proven without some form of communication between the clients. This is a simple information-theoretical result: there is no evidence the server could provide that would convince you that a client had not added something to the database, as it could just present you with the state it had when you last appended to it. However, if two clients have diverging histories, you can prove that either the client is lying, or the server is. If there is a group of clients that all trust each other, then even an evil server would have to act honestly with all of them. Conversely, this could be turned into a peer-to-peer protocol, with clients acting as servers for others, making it harder for an adversary to compromise completely.
If you are going down the authenticated route, the server would be unable to successfully forge an entry in the log.
Will it always be honest?
The last one is impossible to prove. My evil server could be simulating an honest one, maybe even running the honest code, up until a point where I chose to change it for a different one. Someone could unplug the cable to my server and plug it into theirs. I could maintain two logs, an honest one I show to you, and a dishonest one I show to everyone else, or even just show each client only the results they themselves had appended. These are problems that would apply to any system, not just the one that I set out above.
In the real world
A real-life example of this is the "Certificate Transparency Logs". These are used to prove that a CA has issued a TLS certificate (used for securing websites). This means that an attacker cannot surreptitiously create a certificate and use it to impersonate a site: they must publish it's issuance for the world to see (allowing it to be revoked). This record is a kept as a Merkle tree (with each CA contributing a branch) and replicated by multiple different servers, who watch for alterations in the others history. If you want to read up on this similar system, their website is here.