Are you using a rolling hash (such as the one employed in Rabin-Karp string search algorithm)? You can then store the hash at check points and the intermediate

Are you using a rolling hash (such as the one employed in Rabin-Karp string search algorithm)? You can then store the hash at check points and the intermediate hashes between checkpoints can be regenerated using the rolling hash. +[h1] +[batch1] +[h2] [batch2] -[h3] +[batch3] +[h4] You would then have the operations log for a replica as +[forwardhash(null)] +[hello] +[forwardhash(hello)] +[world] -[reversehash(world)] +[ ] +[forwardhash(wor) -[ld]+[k] This sequence would give the following replica states after processing each hash: +[forwardhash(null)] +[hello] -> hello +[forwardhash(hello)] +[world] -> helloworld -[reversehash(world)] +[ ] -> hello world +[forwardhash(wor) -[ld]+[k] -> hello work The direction of the roll is just a sign bit of the hash. We don't need to encode positions separately as it is a function of the state of the replica and the sign of the hash.