Once I got to this idea, I heard about longest chain. So we can randomly cut existing chain keeping it at safe length. It could be done even per client (server will store the whole chain, while smartphones will keep only "safe"-length chain)

Anyway, all of this is just implementation problem which, I believe, could be solved.