How to save the data in a non-trustworthy db, so the next time I read from the db, I know that I've read actual and not an old version of the data? Assume I encrypt a message, A1, and save it. Later I replace the message A1 with a new message, A2. I do not trust the message storage.
Now I want to read the last message. How can I verify that I've read the last message? An attacker can substitute the message A2 with A1 and I will not notice that. 

The first idea is to memorize the last message. This will work with last message, but how can I verify that I have all my messages in the database? I think I can save a signed list of message signatures together with the date of last modification of the database. This way I only need to memorize the last database edit date. Will call this the control message.
I also need to make sure that there was no substitution while I compose the control message.

How is this done usually?

What I need, is a secure counter. A counter with properties:


it is stored in an insecure database
can't be replaced by an older version without knowing the key
it only supports increment/decrement operations
if possible, two users, at the same time, should be able to increment the counter (concurrency) without side effects
the counter can fail with some probability. Instead of N, it can be sometimes set to N-1. I do not want an attacker to set the counter.
I'm not a professional cryptographer, but you don't seem to be asking a cryptography question. Set aside the encryption part for a second, and I think you're asking for something impossible.


The two parties in your example are only communicating over the storage system. 
The only way they are alerted to new versions is by checking the storage system.
And yet, you also say that the storage system is unreliable, or can be hacked.


In that case literally anything can happen.

Even if both parties "remembered" the last versions they saw, either one of them could change the state of the system, do something bad, and then flip it back to an earlier state before the other one noticed. Or, a third party could do the same and fool both of them.

If you had one secure channel, you could use it to prove some things about an insecure channel. But in your example that doesn't exist.