# Order-preserving appending log

Sorry for not having a better name, but I cannot seem to find a better name.

Each client will append an element $$a_i$$ to the server at some time, and the server keeps appending the element to the database $$\{a_1,a_2, \dots, a_i\}$$.

Is there a way for the server to "cryptographically" prove to the clients that it behaves honestly? one trivial example is to publish the whole database/hash of each element and handle one client at a time.

I am not sure if people have looked into this problem before

• Could you describe the scenario in a bit more detail? In which case is this required and what exactly needs to be proven? If the client does not know other a than the one submitted by it, what good is the hash to them? – Jagrut May 5 '20 at 7:21
• Not exactly clear question. Are you looking for order preserving encryption? – kelalaka May 5 '20 at 11:32
• I was thinking about a relay server that compiles a bunch of "write" requests before processing, and because it's a write request, ordering matters – DiamondDuck May 5 '20 at 17:19
• sorry i can't provide a synopsis, Hartung 2016 provides extensive treatment: "Secure Audit Logs with Verifiable Excerpts" (section4) eprint.iacr.org/2016/283.pdf "It is a desirable feature of secure logging schemes to have verifiable excerpts. We have defined a security notion for such logging schemes, and proposed a new scheme that provably fulfills this notion. Our scheme can be instantiated with an arbitrary forward-secure signature scheme, and can therefore be tuned to specific performance requirements and based on a wide variety of computational assumptions." – brynk May 5 '20 at 20:42
• Thanks for the link, I will take a look. – DiamondDuck May 5 '20 at 21:34

This is actually quite a common problem in cryptographic systems. This can be looked at as proving two different things:

1. Is the server currently storing all of the elements a specific client has given it before in order (is it honest with us)?
2. Is it giving us all of the other client's data (is it honest with others)?
3. 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.

• @MaartenBodewes It was my understanding that "blockchain" referred to the data structure, which is a Merkle tree, rather than the system used to guarantee authenticity of the data within it (generally signatures) or even the timestamping system (generally PoW). I hate to cite Wikipedia, but it appears to agree with me on this. However, I could very well be wrong: please tell me if there is a more trustworthy published source that disagrees with me! – Cyclic3 May 5 '20 at 13:49
• Yeah, you're right of course. Hmm. I really have to implement a blockchain to fuse the ideas into memory. Currently working on TLS though. – Maarten Bodewes May 5 '20 at 13:54